ISSN:
1432-0541
Keywords:
VLSI-design
;
Efficient algorithms
;
Channel-routing
;
Knock-knee mode
;
Layer assignment
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract In this paper we consider the channel-routing problem in the knock-knee mode. An algorithm is presented to construct a layout that is wirable in only three conducting layers. When the channel consists of top-to-bottom nets only, the layout is optimal with respect to the area. In case there are one-sided nets, the algorithm introduces at most one additional column. The algorithm improves all previously known layout algorithms which either use up toN/2 (N number of nets) additional columns to produce a three-layer wirable layout [6], [11], [12] or construct a layout which might not be three-layer wirable [4], [5], [10], [18]. Using a special kind of segment tree as the basic data structure, the algorithm can be implemented to run inO(N logN) time. Previous algorithms with linear running time use either additional columns [6], [12] or solve only special cases [18], [19]. For any layout constructed by the algorithm (or a slightly modified layout) a three-layer assignment can be constructed in timeO(N) with onlyO(N) vias.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01955047
Permalink
