Parallel binary reflected Gray code sequence generation on multicore architectures

摘要

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.