Browsing by Author "Yan, JT"

Now showing 1 - 12 of 12

A simple yet effective genetic approach for the orientation assignment on cell-based layout
(1995)
Yan, JT
;
資訊工程學系
;
Department of Computer Science
An efficient cut-based algorithm on minimizing the number of L-shaped channels for safe routing ordering
(1995)
Yan, JT
;
資訊工程學系
;
Department of Computer Science
An ILP formulation for minimizing the number of feedthrough cells in a standard cell placement
(1999)
Yan, JT
;
交大名義發表
;
National Chiao Tung University
It is well known that standard cells have been widely used to implement VLSI circuits in the automation of physical design. Since one major aim of a cell-based design is to minimize total layout area in a standard cell placement, the number of feedthrough cells will be minimized to reduce total cell area in a standard cell placement. In this paper, first, we model a partitioning-based row assignment (PRA) problem to minimize the number of feedthrough cells in a standard cell placement. Furthermore, an integer linear programming (ILP) approach is proposed to solve the PRA problem in a standard cell placement. Finally, the ILP approach has been implemented and two standard-cell net-lists, Primary 1 and Primary 2, have been tested by the proposed approach, Bose's approach [4] and an exhaustive search approach,respectively The experimental results show that the ILP approach obtains fewer feedthrough cells than Bose's approach in a partitioning-based standard cell placement.
An improved optimal algorithm for bubble-sorting-based non-Manhattan channel routing
(1999-02-01)
Yan, JT
;
交大名義發表
;
National Chiao Tung University
It is well known that a non-Manhattan channel router always uses fewer routing tracks than a Manhattan router in a channel, To our knowledge, for a bubble-sorting-based non-Manhattan channel routing (BSNMCR) problem, Chaudhary's O(kn(2)) heuristic algorithm [8] and Chen's O(k(2)n) optimal algorithm [9] have been, respectively, proposed, where n is the number of terminals and k is the number of routing tracks in a channel. However, the time complexity of the two algorithms is in O(n(3)) time in the worst case. In this paper, based on optimality-oriented swap-direction selection in an optimal bubble-sorting solution, an improved optimal algorithm for a BSNMCR problem is proposed, and the time complexity of the proposed algorithm is proven to be in O(kn) time and in O(n(2)) time in the worst case.
An O(NlogN) algorithm for region definition using channels switchboxes and ordering assignment
(1996)
Yan, JT
;
Hsiao, PY
;
交大名義發表
;
資訊工程學系
;
National Chiao Tung University
For a building block placement, the routing space can be further partitioned into channels and switchboxes. In general, the definition of switchboxes releases the cyclic channel precedence constraints and further yields a safe routing ordering process. However, switchbox routing is more difficult than channel routing. In this paper, an O(NlogN) region definition and ordering assignment (RDAOA) algorithm is proposed to minimize the number of switchboxes for the routing phase, where N is the number of vertices in a channel precedence graph. Several examples have been tested on the proposed algorithm, and the experimental results are listed and compared.
An optimal ILP formulation for minimizing the number of feedthrough cells in standard cell placement
(1996)
Yan, JT
;
資訊工程學系
;
Department of Computer Science
Connection-oriented net model and fuzzy clustering techniques for k-way circuit partitioning
(1995)
Yan, JT
;
資訊工程學系
;
Department of Computer Science
Correspondence on 'Planar constrained terminals over-the-cell router'
(1998-07-01)
Yan, JT
;
友訊交大聯合研發中心
;
D Link NCTU Joint Res Ctr
A new routing model with constrained terminal structure for over-the-cell channel routing and a graph theoretical algorithm for solving the planar constrained terminals over-the-cell routing problem have recently been published. The routing model with constrained terminal structure assigns the connection constraint between adjacent layers on terminals and makes use of the vacant locations on each layer for over-the-cell routing. Based on the constrained terminal structure, a graph theoretical algorithm is proposed to complete planer routing layer by layer for over-the-cell channel routing. The new routing model and the graph theoretical algorithm are shown to be flawed, and corrections are suggested.
Designing a channel router by hybrid methodology of top routing and bottom routing
(1999-01-01)
Yan, JT
;
交大名義發表
;
National Chiao Tung University
In this paper, based on the hybrid methodology of top routing and bottom routing, we propose an O(N-col) approach for the channel routing problem, where N-col is the number of columns in a channel. Basically, top (bottom) routing is a track-assignment-based routing approach in a channel, i.e. a channel is routed track by track from top (bottom) to bottom (top) by running top (bottom) routing. In the proposed routing approach, the routing process is divided into two phases: iterative-construction phase and merging- improvement I phase. In the iterative-construction phase, the net interval of each routing net is split into horizontal segments and these segments are further assigned track by track in a top-down or bottom-up manner. In the merging-improvement phase, the routing result is further improved by merging shorter segments in different tracks into longer segments for the reduction of the total wire length and the number of vias. Finally, the proposed approach has rested many published channels and the routing results are in the optimal number of tracks. For example, the Deutsch's difficult channel is routed in 19 tracks with automatic introduction of doglegs. In addition to the optimality of the number of tracks, the proposed approach obtains fewer vias and shorter total wire length than all other Manhattan channel routers. (C) 1999 Elsevier Science Ltd. All rights reserved.
Genetic-based rotation assignment in macro cell layout
(1996)
Yan, JT
;
資訊工程學系
;
Department of Computer Science
Minimizing the number of switchboxes for region definition and ordering assignment
(1996-03-01)
Yan, JT
;
Hsiao, PY
;
交大名義發表
;
資訊工程學系
;
National Chiao Tung University
For a building block placement, the routing space will be fully defined into channels and switchboxes because the definition of switchboxes releases all the cycles in a channel precedence graph and further yields a safe routing ordering, However, switchbox routing is more difficult than channel routing. Due to the requirements in the routing phase, it is important for us to minimize the number of switchboxes in the definition of channels and switchboxes, In this paper, a region definition and ordering assignment (RDAOA) algorithm on minimizing the number of switchboxes is proposed. First, the routing space is modeled as a floorplan graph. According to the routing precedence in one ''T'' type junction, the graph is further transformed into a channel precedence graph, Hence, the problem of minimizing the number of switchboxes in region definition will correspond to the minimum feedback vertex set (MFVS) problem in the channel precedence graph. Second, based on the cyclic properties in a channel precedence graph, the MFVS problem is solved by the minimal-cycle phase and the long-cycle phase. All the minimal cycles and most of the long cycles are broken in the minimal-cycle phase, and the remaining long cycles are further broken in the long-cycle phase, As a result, fewer switchboxes are defined, and these channels and switchboxes are assigned to guarantee a safe routing ordering, The time complexity of the algorithm is proved to be in O(n) time, where n is the number of line segments in a given floorplan graph, Finally, several examples have been tested on the proposed algorithm and other published algorithms, and the experimental results show that our algorithm defines fewer switchboxes than other algorithms.
Routability crossing distribution and floating pin assignment for T-type junction region
(1999)
Yan, JT
;
交大名義發表
;
National Chiao Tung University
Based on non-crossing relations, vertical constraint relations and net-geometry relations in one T-type junction region, two kinds of routability crossing distributions are proposed to improve routing performance in one T-type junction region. For routability crossing distribution in one T-type junction region, a routability-ordering graph is built to decide a net ordering in O(n(2)) time. For routability quota crossing distribution in one T-type junction region, if the number of net crossings in base channel is more than a given quota, this net ordering in routability crossing distribution will be further adjusted to satisfy the quota requirement by using a net interchange operation in O(n) time. For floating pin;assignment in one;T-type junction region, global nets are assigned on the boundary between top channel and base channel by interleaving vacant pins in O(n) time according to a net ordering in routability crossing distribution.