MaizeRouter: Engineering an Effective Global Router
Michael D. Moffitt · IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems · 2008
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, includingextremeedgeshifting, a technique aimed primarily at the efficient reduction of routing congestion, andedgeretraction, a counterpart to extreme edge shifting that serves to reduce unnecessary wirelength. We present enhanced variations of these operations to enable therapidexplorationof candidate paths, along with a form ofdynamiccostdeflationthat 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 ofinterdependentnet 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.