Maze routing steiner trees with effective critical sink optimization

Abstract

This paper addresses the problem of generating good topologies of rectilinear Steiner trees using path search algorithms. We present AMAZE, a fast maze router based algorithm that employs selected techniques to build optimized steiner trees. A biasing technique proposed for wire length improvement produces trees that are within 2% from optimal topologies in average. By introducing a sharing factor and a path-length factor we show how to trade-off wire length for delay. Our experimental results show that AMAZE is more effective to optimize delay to critical sinks than state of the art heuristics for Steiner trees, such as AHHK (from 26% to 40%) and P-Trees (from 1% to 30%) while keeping the properties of a routing algorithm. We also analyzed the ability of AMAZE to handle blockages and verified experimentally that AMAZE produces tree with better delay to the critical sinks than P-Trees from 6% (5 pin nets) to 21% (9 pin nets). An important motivation for this work lies in the fact that, due to its acceptable run time and quality of results, AMAZE can be used for estimation in the early stages as well as for actual routing, thereby improving the convergence and timing closure of the design significantly. Copyright 2007 ACM.