Via design rule consideration in multilayer maze routing algorithms

Maze routing algorithms are widely used for finding an optimal path in detailed routing for very large scale integration, printed circuit board and multichip modules. In this paper, we show that finding an optimal route of a two-pin net in a multilayer routing environment under practical via design...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on computer-aided design of integrated circuits and systems 2000-02, Vol.19 (2), p.215-223
Main Authors: Cong, Jason, Fang, Jie, Khoo, Kei-Yong
Format: Article
Language:English
Subjects:
Algorithm design and analysis
Algorithms
CMOS
CMOS process
CMOS technology
Costs
Design engineering
Graphs
Joining processes
Joints
Multichip modules
Multilayers
Nonhomogeneous media
Optimization
Printed circuit boards
Printed circuits
Routing
Studies
Very large scale integration
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Maze routing algorithms are widely used for finding an optimal path in detailed routing for very large scale integration, printed circuit board and multichip modules. In this paper, we show that finding an optimal route of a two-pin net in a multilayer routing environment under practical via design rules can be surprisingly difficult. A straightforward extension to the maze routing algorithm that disallows via-rule incorrect routes may either cause a suboptimal route to be found, or more seriously, cause the failure to find any route even if one exists. We present a refined heuristic to this problem by embedding the distance to the most recently placed via in an extended connection graph so that the maze routing algorithm has a higher chance of finding a via-rule correct optimum path in the extended connection graph. We further present efficient data-structures to implement the maze routing algorithm without the need to preconstruct the extended connection graph. Experimental results confirmed the usefulness of our algorithm and its applicability to a wide range of CMOS technologies.
ISSN:0278-0070
1937-4151
DOI:10.1109/43.828550