Parallel binary reflected Gray code sequence generation on multicore architectures |
| |
Authors: | Md. Mohsin Ali Mst. Shakila Khan Rumi |
| |
Affiliation: | 1. The Australian National University (ANU), CanberraACT 0200, Australia;2. Khulna University of Engineering and Technology (KUET), Khulna 9203, Bangladesh |
| |
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. |
| |
Keywords: | Gray code work span parallelism speedup multithreading multicore monospace" >Cilk++ |
|
|