Efficient Realization of Frequently Used Bijections on Cube-Connected Cycles  

作　　者：刘群 刘志勇 张祥 

机构地区：[1]InstituteofComputingTechnology,TheChineseAcademyofSciences,Beijing100080

出　　处：《Journal of Computer Science & Technology》1995年第4期298-309,共12页计算机科学技术学报（英文版）

摘　　要：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.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.

关 键 词：HYPERCUBE cube-connected cycles linear complement permutation routing algorithm conflict complexity 

分 类 号：TP338.6[自动化与计算机技术—计算机系统结构]