A performance-driven layer assignment algorithm for multiple interconnect trees

With the advent of DSM technologies, interconnect delays increasingly overshadow the transistor delays. Furthermore, since the electrical characteristics of different layers in multilayer routing technologies vary widely, the assignment of the interconnect tree edges to specific routing layers has a large impact on the interconnect delays. Traditionally, critical global interconnect trees were routed greedily, one at a time. This caused the "good" layers to be used up largely for the first few trees, yielding poor routings for the remaining trees. Multiple passes with different tree orderings were usually used to remedy the situation, although with limited success. We propose the use of dynamically adjusted area quotas to prevent the first few trees from monopolizing the "good" layers. Our approach is independent of the routing model or the router employed, and reduces the maximum tree delays by around 15% as compared to traditional algorithms.