Parallel binary reflected Gray code sequence generation on multicore architectures

Abstract

We propose a novel parallel algorithm for generating all the sequences of binary reflected Gray code for a given number of bits as input, targeting machines with multicore architectures. A theoretical analysis of work and span, as well as parallelism of this algorithm, is carried out following a multithreaded implementation using Cilk++ on a multicore machine. Theoretical analysis of this algorithm shows a parallelism of Θ(2ⁿ/log n) and achieves a linear speedup on 12 cores for input data of sufficiently large size.

Keywords::

• Gray code
• work
• span
• parallelism
• speedup
• multithreading
• multicore
• Cilk++