Partitioning Based Low Power Network-on-Chip Design Algorithm

Low Power Design and Interconnect Technology have become significant requirement when the CMOS technology entered the nanometer era. On the one hand, with technology scaling, the number of processor, memory and other cores on the chip is increasing. On the other hand, In order to overcome the limitations of traditional bus architectures, and solve the problem of interconnection better among IP cores in the large-scale or very large scale system on a chip, one new interconnect technology on-chip, Network-on-Chip, is quickly becoming the hot spot of international research.The synthesis of the topology of Network-on-Chip, especially application specific Network-on-Chip, is a new design problem proposed in recent years, and there are still many challenges in it. The topology of Network-on-Chip defines the physical layout and interconnection of the internal nodes on network, and determines the link length of the network, the network bandwidth, throughput and the area of chip. For the problems of the topology synthesis in the past, we proposed a two-stage design process.On the first phase of the synthesis of the topology, the power-driven partitioning and floorplanning are integrated together, considering the communication between modules and the physical location. Different partition strategies may lead to different outcome. Considering the communication requirement only but without the consideration of power consumption, the min-cut partitioning solver such as hMetis can provide good solution. But our goal is to find the partition which minimizes not only the communication costs but also the power consumption. Therefore a tree-based partitioning approach is proposed to find the cut between branches so that the cores can be clustered into groups to optimize the performance and power.On the second phase of the synthesis of the topology, firstly, to minimizing the link power consumption as objective function, we solve the problems of switch and network interface insertion with integer linear programming formulation. Considering computational complexity, integer linear programming is one of the known NP-hard problems. Therefore, we propose a heuristic method for the insertion of switch, and a minimum cost flow method for the insertion of network interface. After the switch and network interface insertion, we adopt an incremental shortest path algorithm to solve the problem of path selection.