CMUCS02172
Computer Science Department
School of Computer Science, Carnegie Mellon University
CMUCS02172
SetA* Applied to Channel Routing
Rune M. Jensen, Randal E. Bryant, Manuela M. Veloso
CMUCS02172.ps
CMUCS02172.pdf
Keywords:
This report describes an application of the SetA* algorithm to VLSI
channel routing. We consider an extended form of the classical routing
problem where pins of nets can occur anywhere within the channel. The
derived algorithm can use general cost functions and heuristics given
that the total routing cost equals the sum of routing costs for each
column. For this class of problems we show a graphbased approach for
deriving an admissible heuristic for any cost function. The approach
is evaluated on a subset of classical routing problems generated from
ISCAS84. We obtain results similar to the most efficient current
approaches.
pages
