A constant queue partial permutation routing algorithm for cube-connected-cycles multicomputer systems
Gene Eu Jan, Ming-Bo Lin, Albert Chao, Deron Liang · 2002
A general routing paradigm is considered and then applied to the routing and partial permutation routing problems on CCC(n, 2/sup n/) networks. The major idea of the general routing paradigm is based on the binary radix sorting scheme in which each bit of keys (i.e., destination addresses) from MSB is separated in sequence until the LSB is reached. The result is a sorted sequence. Based on this scheme, the partial permutation routing problem on CCC(n, 2/sup n/) networks can be solved in O(n/sup 2/) time with O(1) buffers for each node, where n is the dimension of CCC(n, 2/sup n/) networks.