Browse Prior Art Database

Multi-Channel Optimization in Gate-Array Layout Disclosure Number: IPCOM000128582D
Original Publication Date: 1986-Dec-31
Included in the Prior Art Database: 2005-Sep-16
Document File: 7 page(s) / 25K

Publishing Venue

Software Patent Institute

Related People

Lishin Lin: AUTHOR [+4]


We present enhancements to the multi-channel optimizatiou, heurisUc proposed by Aoshima and Kuh(AOSH83J.

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

Page 1 of 7


Multi-Channel Optimization in Gate-Array Layout


Lishin Lin Sartaj Sahni Eugene Shragowitz

Computer Science Department

136 Lind Hall

Institute of Technology

University of Minnesota

Minneapolis, Minnesota 554r5 An Enhanced Heuristic for

TR 86-7

February 1986

Technical Report MULTI_ AN ENHANCED HEURISTIC F R EEL OPTIMIZATION IN GATE- ARR " Lislain Lioa., Sa.rPaj S'a.lani Computer Science Department University of Minnesota

136 Lind Hall 207 Church Street S.E. Minneapolis, MN 55455 ( 612) 376-31 99 Eugene Shragowitz Control Data Corporation 2800 E. Old Shakopee Road Minneapolis, MN 55420 ( 612) 853-3721 * This research wa, _upported, in part, by a grant from Control Data Corporation and by the National Sci-ence Fundation ur.c:- grant A4CS-83-05567 LAYOUT*


We present enhancements to the multi-channel optimizatiou, heurisUc proposed by Aoshima and Kuh(AOSH83J.

1, Introduction

1.1. The problem

in the mufti-channel optimization problem [.r10SH83j, we are given a chip in which the cells (or macros) are placed in uniformly separated rows (Figure 1). There is a horizontal routing channel between each pair of adjacent cell rows. Vertical routing is done on the second layer. Each cell sow has uniformly spaced terminals on either side. Terminals are labeled -1, 0, 1, 2, ..., k, where k is the number of nets. If a ter-minal is labeled i, 1 < i< k then it is a terminal of net i. A blocked terminal is labeled -1 and a feedthrough location is labeled 0. The objective of the mufti-channel optimization problem is to decompose the nets in such a way that they can be routed using

University of Minnesota Page 1 Dec 31, 1986

Page 2 of 7

Multi-Channel Optimization in Gate-Array Layout

horizontal routing channels of least capacity (all channels are assumed to have the same capacity). Since the output of the mufti-channel optimization problem is the input for classical channel routing, and since channel routers are generally able to route using as many tracks as the channel density ((DEUT76J and (RIVE82J), it is reasonable. to modify the objective of the multi-channel optimization problem to:

Decompose the stets so that the maxinnvzn density i1-r any channel is Ininimvan.

For this objective function, Aoshima and Kulh [AOSH83J have proposed two heuristics, respectively called, optimum decomposition and practical approach. In both of these, net decomposition is done one net, at a time. When a net is being decom-posed, available information about the decomposition of all other nets is utilized. One complete iteration of each heuristic involves decomposing or modifying the decompo-sition of each of the nets. As many iterations of each heuristic as desired can be per-formed. One may terminate the heuristic either when an iteration does not improve the decomposition (i.e., does not reduce the maximum channel density) or when one has exhausted the available computation resources.

1.2. The h...