Application-specific network-on-chip architecture synthesis based on set partitions and Steiner trees
Shan Yan, Bill Lin · 2008
Abstract — This paper considers the problem of synthesizing application-specific Network-on-Chip (NoC) architectures. We propose two heuristic algorithms called CLUSTER and DECOM-POSE that can systematically examine different set partitions of communication flows, and we propose Rectilinear-Steiner-Tree (RST) based algorithms for generating an efficient network topol-ogy for each group in the partition. Different evaluation functions in fitting with the implementation backend and the correspond-ing implementation technology can be incorporated into our so-lution framework to evaluate the implementation cost of the set partitions and RST topologies generated. In particular, we exper-imented with an implementation cost model based on the power consumption parameters of a 70nm process technology where leakage power is a major source of energy consumption. Ex-perimental results on a variety of NoC benchmarks showed that our synthesis results can on average achieve a 6.92 × reduction in power consumption over the best standard mesh implementation. To further gauge the effectiveness of our heuristic algorithms, we also implemented an exact algorithm that enumerates all distinct set partitions. For the benchmarks where exact results could be obtained, our CLUSTER and DECOMPOSE algorithms on aver-age can achieve results within 1 % and 2 % of exact results, with execution times all under 1 second whereas the exact algorithms took as much as 4.5 hours. I.