MaizeRouter: Engineering an Effective Global Router. In this paper, we present the complete design and architectural details of MaizeRouter. MaizeRouter reflects a significant leap in progress over existing publicly available routing tools yet relies upon relatively simple operations, including extreme edge shifting, a technique aimed primarily at the efficient reduction of routing congestion, and edge retraction, a counterpart to extreme edge shifting that serves to reduce unnecessary wirelength. We present enhanced variations of these operations to enable the rapid exploration of candidate paths, along with a form of dynamic cost deflation that provides our various path computation procedures with progressively more accurate (and less optimistic) cost information as search continues. These algorithmic contributions are built upon a framework of interdependent net decomposition, a representation that improves upon traditional two-pin net decomposition by preventing duplication of routing resources while enabling cheap and incremental topological reconstruction. Collectively, these operations permit a broad search space that previous algorithms have been unable to achieve, resulting in solutions of considerably higher quality than those of well-established routers.

References in zbMATH (referenced in 3 articles )

Showing results 1 to 3 of 3.
Sorted by year (citations)

  1. Samanta, Radhamanjari; Erzin, Adil I.; Raha, Soumyendu; Shamardin, Yuriy V.; Takhonov, Ivan I.; Zalyubovskiy, Vyacheslav V.: A provably tight delay-driven concurrently congestion mitigating global routing algorithm (2015)
  2. Chaudhry, M. A. R.; Asad, Z.; Sprintson, A.; Hu, J.: Efficient congestion mitigation using congestion-aware Steiner trees and network coding topologies (2011) ioport
  3. Moffitt, Michael D.: Maizerouter: engineering an effective global router (2008) ioport