A routing algorithm that generates a Steiner route for a set of sinks with near optimal Elmore delay to the critical sink is presented. The algorithm outperforms the best existing alternative for Elmore-delay-based critical sink routing. With no critical sinks present, the algorithm produces routes comparable to the best previously existing Steiner router. Since performance-oriented layout generators employ iterative techniques that require a large number of calls to the routing algorithm for layout evaluation, a fast algorithm for routing is desirable. The algorithm presented here has a fast (O(n2), where n is the number of points) and practical implementation using simple data structures and techniques.
|Number of pages
|IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
|Published - 1997
All Science Journal Classification (ASJC) codes
- Computer Graphics and Computer-Aided Design
- Electrical and Electronic Engineering