Efficient Congestion Mitigation Using Congestion-Aware Steiner Trees and Network Coding Topologies

[摘要] In the advent of smaller devices, a significant increase in the density of on-chip components has raised congestionand overflow as critical issues in VLSI physical design automation. In this paper, we present novel techniques forreducing congestion and minimizing overflows. Our methods are based on ripping up nets that go through thecongested areas and replacing them withcongestion-awaretopologies. Our contributions can be summarized as follows. First, we present several efficient algorithms for findingcongestion-awareSteiner trees that is, trees that avoid congested areas of the chip. Next, we show that the noveltechnique ofnetwork codingcan lead to further improvements in routability, reduction of congestion, and overflowavoidance. Finally, we present an algorithm for identifying efficient congestion-aware network coding topologies. We evaluate the performance of the proposed algorithms through extensive simulations.

[学科分类] 电子、光学、磁材料