Efficient realization of frequently used bijections on cube-connected cycles |
| |
Authors: | Zhiyong Liu Qun Liu Xiang Zhang |
| |
Affiliation: | Institute of Computing Technology; The Chinese Academy of Sciences; Beijing 100080; |
| |
Abstract: | CCC has lower hardware complexity than hypercube and is suited for current VLSI technology LC-permutations are a large set of important permutations frequently used in various parallel computations. Existing routing algorithms for CCC cannot realize LC-permutations without network conflict. Wepresent an algorithm to realize LC-permutations on CCC. The algorithm consists of two periods of inter-cycle transmissions and one period of inner-cycletransmissions. In the inter-cycle transmissions the dimensional links of CCCare used in a "pipeline" manner and in the innercycle transmissions the datapackets are sorted by a part of its destination address. The algorithm is fast(O(log2 N)) and no conflict will occur. |
| |
Keywords: | Hypercube cube-connected cycles linear complement permutation routing algorithm conflict complexity |
本文献已被 CNKI 维普 SpringerLink 等数据库收录! |
| 点击此处可从《计算机科学技术学报》浏览原始摘要信息 |
|
点击此处可从《计算机科学技术学报》下载全文 |