How is Perfect shuffle a better interconnect scheme for parallel processing? For example if we consider a problem of sum reduction, I want to understand how this scheme is useful when implementing sum reduction in parallel , for example on a GPU?


1 Answer 1


The perfect shuffle alone has never been used as an interconnection network; it always included exchange links, in order to allow for a worst-case $O(\lg n)$ routing algorithm. Algorithms for reduction, broadcast, parallel prefix, transpose etc are given in

Yosi Ben-Asher , David Egozi , Assaf Schuster, SIMD Algorithms for 2-D Arrays in Shuffle Networks.

Stone was the first researcher to provide algorithms for the perfect shuffle network, including algorithms for the FFT, matrix transpose etc.

This network has been used in several parallel machines, but mostly in multi-stage shuffle-exchange networks such as the Omega network (which uses the perfect shuffle between stages). An example is the IBM SP3 machine.

Note that these are message-passing algorithms, whilst you refer to a GPU, which is instead a shared-memory device.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.