Parallel binary reflected Gray code sequence generation on multicore architectures.

We propose a novel parallel algorithm for generating all the sequences of binary reflectedGray codefor a given number of bits as input, targeting machines with multicore architectures. A theoretical analysis ofworkandspan, as well asparallelismof this algorithm, is carried out following a multithreaded implementation usingCilk++on a multicore machine. Theoretical analysis of this algorithm shows aparallelismof Θ(2n/log n) and achieves a linearspeedupon 12 cores for input data of sufficiently large size. [ABSTRACT FROM AUTHOR]