Optimal Embedding of Hierarchical Cubic Networks into Linear Arrays of NoC

Abstract

With the advent of the era of big data,the demand of large-scale computing makes the requirements on the performance of chips constantly increasing.Network-on-Chip(NoC),as a network-communication-centered interconnection structure on chips,has achieved a good tradeoff in all aspects of communication.The physical layout and interconnection mode of NoC components have a significant impact on the overall performance of the chip(such as signal delay,circuit cost).Due to the limited area of the chip,minimizing the total length of wires connecting components,in other words,minimizing wirelength,is considered as the key of chip design.The hierarchical cubic network is an excellent interconnection network which has less communication delay,better reliability and greater scalability while the linear array is one of the common topologies of NoC.When the hierarchical cubic network is ported to the linear array,the structure and algorithm of hierarchical cubic network can be simulated on the linear array.Graph embedding is a key technology to realize network porting.In graph embedding,the goal of minimizing the total wire length can be achieved by finding the optimal embedding with minimum wirelength.This paper mainly studies the optimal embedding problem of hierarchical cubic networks into linear arrays with minimum wirelength.Firstly,by studying the optimal set of the hierarchical cubic network,an embedding scheme hel of hierarchical cubic networks into linear arrays is proposed,and it is proved that the wirelength under hel is minimum compared with other embedding schemes,that is, hel is an optimal embedding.Then,the exact value of the wirelength under hel and an embedding algorithm with O(N) time complexity are given,where N=22n is the number of vertices of the n-dimensional hierarchical cube network.Furthermore,an algorithm of physical linear layout in NoC for hierarchical cubic networks is proposed.Finally,comparison experiments are conducted to evaluate the performance of embed-ding hel.

Keywords

• network-on-chip|graph embedding|wirelength|hierarchical cubic networks|linear arrays