Browse Prior Art Database

A NEW CHANNEL ROUTING ALGORITHM

IP.com Disclosure Number: IPCOM000127923D
Original Publication Date: 1982-Dec-31
Included in the Prior Art Database: 2005-Sep-14
Document File: 10 page(s) / 38K

Publishing Venue

Software Patent Institute

Related People

Wan S. Chan: AUTHOR [+3]

Abstract

This paper presents a new algorithm for solving the two-Layer channel routing problem with doglegging. Based on a set of intuitive and reasonable heuristics, the algorithm tries to obtain a channel routing configuration with a minimum number of tracks. For every benchmark problem tested, the algorithm gives a routing configuration with the smallest number of tracks reported in the literature. The research was carried out during the author's tenure as a Hewlett-Packard representative at Caltech Silicon Structures Project.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 9% of the total text.

Page 1 of 10

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

A NEW CHANNEL ROUTING ALGORITHM

Wan S. Chan California Institute of Technology Pasadena, California 91125

TM# 5038

September 1982

ABSTRACT

This paper presents a new algorithm for solving the two-Layer channel routing problem with doglegging. Based on a set of intuitive and reasonable heuristics, the algorithm tries to obtain a channel routing configuration with a minimum number of tracks. For every benchmark problem tested, the algorithm gives a routing configuration with the smallest number of tracks reported in the literature.

The research was carried out during the author's tenure as a Hewlett-Packard representative at Caltech Silicon Structures Project.

I. INTRODUCTION ,

In this paper we present a new algorithm for solving the two- layer channel routing problem with restricted doglegging, identical to the problem considered in [1,3]. Although the algorithm was developed as part of a silicon compiler [5], it can be applied to any channel

routing environment.

Our algorithm is based on the following new improved ideas: (a) by viewing each two-pins subnet as a basic component, we eliminate the need for the "zone" concept introduced in [1]; (b) at each iteration of our algorithm, we identify the set of subnets to be considered for assignment, based on both the vertical and horizontal constraints rather than on the horizontal constraint alone, as proposed in [1]; (c) to determine the assignment of subnets to tracks, we attach weights onto the edges of the bipartite graph and use the max-min matching [4], a refinement of the maximum cardinality matching [4] used in [1]9 (d) by appropriately defining the weight on these edges one can introduce various heuristics into the algorithm. In our algorithm, the weight has been defined to control the growth in the length of the longest path through the vertical constraint graph, which is a lower bound on the number of tracks needed; (e) instead of starting from a density column and assigning all the subnets on one side of the column before considering any subnet on the other side of the column, our algorithm considers assigning subnets on both sides of the column simultaneously. We also derive an algorithm and a theorem to detect the constraint loops for the bidirectional case, which reduce to those presented in [1] for the unidirectional case. We tested our algorithm on four channel routing problems taken from the literature and obtained the same best results reported among various papers [1,3].

California Institute of Technology Page 1 Dec 31, 1982

Page 2 of 10

A NEW CHANNEL ROUTING ALGORITHM

The paper is organized as follows: in Sec. II we formulate the two-layer channel routing problem with restricted doglegging; in Sec. III we discuss all the important ideas behind our algorithm, using several examples for illustration; in Sec. IV we present our algorithm in high level pseudo code; in Sec. V we summarize the experimental res...