A Low-Power Multi-Pin Maze Routing Methodology

Ahmed Youssef,  Tor Myklebust,  Mohab Anis,  Mohamed Elmasry
University of Waterloo


As VLSI technologies scale into the deep submicron (DSM) realm, the minimum feature size continues to shrink. In contrast, the average die size is expected to remain constant or to slightly increase with each technology generation. This results in an average increase in the global interconnect lengths. In order to mitigate the impact of these global wires, buffer insertion is the most widely used technique. However, unconstrained buffering is bound to adversely affect the overall chip performance. In fact, the number of global interconnect buffers is expected to reach several hundreds of thousands to achieve an appropriate timing closure. This increase in buffers is destined to have a huge impact on the chip power consumption. In order to mitigate the impact of the power consumed by the interconnect buffers, a low power multi-pin routing methodology is proposed. The problem is tackled based on a graph theoretic representation of the interconnects that explores the various buffer sizing options in order to identify the lowest power path that can be assigned to the interconnect being routed. The formulation was found to be of a pseudo-polynomial complexity which fits well within the context of the increased number of buffers. The methodology is tested using the MCNC floorplan benchmarks to verify the correctness and the complexity. These tests showed that an average power saving as high as 45% with a 10% sacrifice in delay is observed.