The psi-cube: a bus-based cube-type clustering network for high-performance on-chip systems

This paper proposes a bus-based cube-type network, called psi-cube, that alleviates the two problems, long wires and a limited number of I/O pins, against the on-chip systems through a small diameter and dynamic clusters, respectively. The 2n-node psi-cube is organized on the sets of node-partitions produced with an extended n-bit Hamming code ψ(n, k) [M. Takesue, Ψ-Cubes: recursive bused fat-hypercubes for multilevel snoopy caches, in: Proceedings of the International Symposium on Parallel Architectures, Algorithms, and Networks, IEEE CS Press, 1999, pp. 62–67] if we connect the nodes in each partition to the bus owned by the leader of the partition. Owing to the routing between the leaders separated by the distance of 1–3, the diameter equals ⌊n/2⌋ if n≠2p − 1 or ⌈n/2⌉ otherwise. The maximum bus length is O(2p−1) or O(2k−1) when the psi-cube is mapped onto an array. We dynamically produce separate sets of clusters for different off-chip targets such as memory blocks, so the traffic to the leaders of clusters is much smaller than in static clusters fixed in hardware. From simulation results, the psi-cube outperforms over the mesh if the bus delay is less than 4 times the mesh link’s, and the dynamic clusters increase the psi-cube bandwidth by over 60%.