MaizeRouter: Engineering an effective global router

In this paper, we present MaizeRouter, winner of the inaugural Global Routing Contest hosted at ISPD 2007. MaizeRouter reflects a significant leap in progress over existing publicly-available routing tools, and abandons popular algorithms such as multicommodity flow-based techniques, ILP formulations, and congestion-driven Steiner tree generation. Instead, the foundation of our algorithm draws upon simple yet powerful edge-based 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. 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. A maintenance mechanism, named garbage collection, is introduced to eliminate leftover routing segments. 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.