Efficient Rerouting Algorithms for Congestion Mitigation Conference Paper uri icon

abstract

  • Congestion mitigation and overflow avoidance are two of the major goals of the global routing stage. With a significant increase in the chip size and routing complexity, congestion and overflow have become critical issues in physical design automation. In this paper we present several routing algorithms for congestion reduction and overflow avoidance. Our methods are based on ripping up nets that go through the congested regions and replacing them with congestion-aware Steiner trees. We propose several efficient algorithms for finding congestion-aware Steiner trees and evaluate their performance using the ISPD routing benchmarks. We also show that the novel technique of network coding contributes to further improvements in routability and reduction of congestion. Accordingly, we propose an algorithm for identifying efficient congestion-aware network coding topologies and evaluate its performance. © 2009 IEEE.

author list (cited authors)

  • Chaudhry, M., Asad, Z., Sprintson, A., & Hu, J.

citation count

  • 3

publication date

  • January 2009

publisher