A Perfect Shuffle Network for the Partitioning

J.-D. Lee (Korea)


Perfect Shuffle Network, Partitioning,Interconnection network, Parallel processing, SingleStage network


This paper addresses the problem of partitioning the Recirculating Single-State Perfect Shuffle Network (RPSN). Additional links are needed in order to partition an RPSN. An algorithm, named RPSN_to_PPSN, is devised to transform an RPSN into a Partitionable Perfect Shuffle Network (PPSN) by adding a number of additional links. A Partitionable Perfect Shuffle Network(PPSN) can be partitioned into independent sub-RPSNs of various sizes (powers of two), such that each sub-RPSN can be used in parallel. By partitioning, a large Partitionable Perfect Shuffle Network in a massively parallel machine can compute various problems for multi-users simultaneously, thereby the processing efficiency of the machine is improved.

Important Links:

Go Back