Browsing by Author "SHEW, PW"

Now showing 1 - 3 of 3

A ROBUST OVER-THE-CELL CHANNEL ROUTER
(1993-10-01)
CHANG, LD
;
HSIAO, PY
;
YAN, JT
;
SHEW, PW
;
資訊工程學系
In this paper, we present an efficient algorithm for over-the-cell routing in the standard cell layout design technology. Two variations are discussed: one aims to minimize the channel density with fewest tracks over the cells while the other aims to minimize the final channel width. Our algorithm can fit both the two-layer and three-layer routing models. With the two-layer model, there is a single routing layer over the cells for intercell connections. While with the three-layer model, there are two disjoint routing layers over the cells for intercell connections. In our approach, we decompose the problem into two phases: (1) over-the-cell routing and (2) conventional channel routing. The over-the-cell routing phase, which is executed iteratively, consists of two steps, routing over the cells and choosing net segments within the channel. For each iteration in the over-the-cell routing phase, our algorithm removes a net or a subnet which intersects the column with highest column density and route it over the cells according to some prioritized criteria. In comparison with the previous researches, our approach achieved the best effectiveness and has used the least CPU-time. On the average, the execution speed of our router is 163 and 4163 times faster than that of [8] and [9], respectively. Besides, our algorithm can produce results comparable to those produced by the WISER algorithm [10].
EFFICIENT HEIGHT REDUCTION OVER-THE-CELL CHANNEL ROUTER
(1995-07-01)
SHEW, PW
;
HSIAO, PY
;
LIM, YC
;
資訊工程學系
;
Department of Computer Science
The authors present a new algorithm for both two-layer and three-layer over-the-cell channel routing in the standard cell VLSI design. The approach exploits vacant terminals on the channel boundary effectively. It considers the following factors simultaneously to select net segments for routing over the cells: density distribution in the channel, the longest path in the vertical constraint graph, elimination of cycles in the vertical constraint graph and reduction in maximum cliques in the horizontal constraint graph. With respect to the PRIMARY 1 benchmark examples, the router achieved a 41.3% improvement over the Greedy channel router (one without using over-the-cell area) for a two-layer routing model and a 61.0% improvement for a three-layer routing model. This outperforms all previous algorithms.
OPTIMAL TILE PARTITION FOR SPACE REGION OF INTEGRATED-CIRCUITS GEOMETRY
(1993-05-01)
HSIAO, PY
;
LIN, CY
;
SHEW, PW
;
資訊工程學系
;
Department of Computer Science
An optimal tile partition (OTP) is presented for partitioning the space region of a VLSI layout plane into rectangular space tiles. It modifies the corner stitching data structure to optimise the space tile partition. There is a serious restriction in the original corner stitching data structure, i.e. the solid rectangles cannot overlap each other, whereas our OTP allows overlapping. This paper also shows three theorems with rigorous proofs and experimental results to obtain the minimal number of the space tiles through the OTP. Moreover, a dynamic plane-sweep algorithm based on region query for the OTP has been developed. Using the OTP, the memory efficiency and the local query operations of the original corner stitching data structure have been enhanced.