A Breadth-First Greedy Mapping Algorithm for Reducing Internal Congestion in NoC

With the widely using of network-on-chip in VLSI systems, mapping has been one of the most critical and general problem in VLSI design and test. In this paper, a breadth-first greedy algorithm is proposed to reduce internal congestion and solve the application mapping with the structure of the task topology and the shape of the mapping area. The experimental results show our solution achieves the performance close to that of the exhausting method, while its time complexity is at low order polynomial level. Compared with the existing method, it reduces 22%-44% energy consumption and 16%-57% executing time of the whole application.