Optimization of the maximum delay of global interconnects during layer assignment

Traditionally, interconnects in multilayer routing technologies have been r outed greedily, one at a time. This yields good routings for the first few interconnect trees, but poor routings for the remaining trees. In contrast, we present a new performance-driven approach for layer assignment and rout ing in which the quality of the routing is largely order independent, minim izing the peak tree delays in the process. We introduce a dynamically adjus ted area quota for each tree on each routing layer This ensures that no tre e uses up excessive routing space on the "good" layers. Since the parasitic coupling of different layers varies over a large range, assignment of the edges in the trees to specific routing layers has a large impact on the int erconnect delay. Furthermore, we derive an expression for the contribution of an edge in a tree to the total delay of that tree as a function of the l ayer to which the edge is assigned, We use this expression to introduce a l ookahead keg for each edge of each tree that enables us to decide whether t o route that edge immediately on the current layer or to postpone it to a s ubsequent layer. Our approach can be used to construct a performance-driven layer assignment and routing algorithm specifically tailored toward any gi ven combination of the timing, routing and technology models, Our experimen tal results demonstrate that this approach consistently outperforms the mul tipass greedy scheme currently in vogue, both in worst case delay and in ro utability.