SetA* Applied to Channel Routing

Rune Møller Jensen, Randal E. Bryant, Manuela M. Veloso

Research output: Book / Anthology / Report / Ph.D. thesisReportResearch

Abstract

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 graph-based approach for deriving an admissible heuristic for any cost function. The approach is evaluated on a subset of classical routing problems generated from ISCAS-84. We obtain results similar to the most efficient current approaches.
Original languageEnglish
PublisherCarnegie Mellon University
EditionTechnical Report CMU-CS-02-172
Number of pages12
Publication statusPublished - 2002
Externally publishedYes

Keywords

  • SetA* algorithm
  • VLSI channel routing
  • admissible heuristics
  • general cost functions
  • ISCAS-84 routing problems

Fingerprint

Dive into the research topics of 'SetA* Applied to Channel Routing'. Together they form a unique fingerprint.

Cite this