We present a very fast algorithm for topology generation of repeater trees. Based on the criticality of the individual sinks, which is estimated taking their required signal arrival times and their distance from the root of the repeater tree into account, this topology connects very critical sinks in such a way as to maximize the minimum slack and to minimize wiring for non-critical sinks.We establish theoretical bounds on the optimum solution and prove that our algorithm produces results that are close to optimum with respect to slack and wirelength. Experimental results on industrial designs in 130 nm and 90 nm technologies demonstrate the excellent quality of our algorithm. Moreover, one million nontrivial repeater tree topologies are constructed in less than one minute of computing time.
展开▼
