Track assignment: A desirable intermediate step between global routing and detailed routing

Shabbir Batterywala, Narendra Shenoy, William Nicholls, Hai Zhou

Research output: Contribution to journalArticlepeer-review

9 Scopus citations


Routing is one of the most complex stages in the back-end design process. Simple routing algorithms based on two stages of global routing and detailed routing do not offer appropriate opportunities to address problems arising from signal delay, cross-talk and process constraints. An intermediate stage of track assignment between global and detailed routing proves to be an ideal place to address these problems. With this stage it is possible to use global routing information to efficiently address these problems and to aid the detailed router in achieving the wiring completions. In this paper we formulate routing as a three stage process; global routing, track assignment and detailed routing. We describe the intermediate track assignment problem and suggest an efficient heuristic for its solution. We introduce cost metrics to model basic effects arising from connectivity. We discuss extensions to include signal integrity and process constraints. We propose a heuristic based on weighted bipartite matching as a core routine. To improve its performance additional heuristics based on lookahead and segment splitting are also suggested. Experimental results are given to highlight the efficacy of track assignment stage in routing process.

Original languageEnglish (US)
Pages (from-to)59-66
Number of pages8
JournalIEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers
StatePublished - Jan 1 2002

ASJC Scopus subject areas

  • Software
  • Computer Science Applications
  • Computer Graphics and Computer-Aided Design


Dive into the research topics of 'Track assignment: A desirable intermediate step between global routing and detailed routing'. Together they form a unique fingerprint.

Cite this