A new timing-driven multilayer MCM/IC routing algorithm

In high-performance multilayer routing, time delay is an important performance issue which has not been appropriately addressed by previous multilayer routing approaches. This paper proposes a new timing-driven MCM/IC multilayer routing algorithm, named MLR, considering the Elmore delay as well as some other fundamental performance issues, such as the number of layers, vias and the total wirelength. Algorithm MLR assigns all the nets into the routing layers layer-pair by layer-pair based on the layer assignment algorithm. During each pair-layer routing, the timing-driven Steiner area routing algorithm SOAR is used to generate a Steiner tree for each net while minimizing the Elmore delay of the net. For two nodes to be connected for the net being routed, an optimal path from one node to the other is created by the (α,β)* algorithm. Additionally, when power and ground nets are considered, some signal nets are routed in the limited routing space on the power and ground layer-pair, which is very useful in decreasing the number of layers needed to complete the routing. The proposed algorithm has been implemented and tested on CBL/NCSU and MCC benchmarks and the experimental results are very promising