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 Θ(2n/log n) and achieves a linear speedup on 12 cores for input data of sufficiently large size. Show more