DC Field | Value | Language |
---|---|---|
dc.contributor.advisor | Kyung, Chong-Min | - |
dc.contributor.advisor | 경종민 | - |
dc.contributor.author | Yang, Yeong-Yil | - |
dc.contributor.author | 양영일 | - |
dc.date.accessioned | 2011-12-14 | - |
dc.date.available | 2011-12-14 | - |
dc.date.issued | 1989 | - |
dc.identifier.uri | http://library.kaist.ac.kr/search/detail/view.do?bibCtrlNo=61337&flag=dissertation | - |
dc.identifier.uri | http://hdl.handle.net/10203/36074 | - |
dc.description | 학위논문(박사) - 한국과학기술원 : 전기 및 전자공학과, 1989.8, [ x, 93 p. ] | - |
dc.description.abstract | This thesis introduces two heuristic algorithms for layout generation, which consists of two parts. In the first part, a three-step heuristic algorithm for PLA column folding and row folding of column-folded PLA is presented. The three steps are i) Min-Cut partition of vertices in the column(or row) intersection graph, ii) determination of products order using Fiduccia``s Min-Net Cut algorithm, and iii) head tail pairing for column folding, while some heuristics are proposed for deciding row folding pairs. For test PLA``s, the proposed algorithm is significantly faster than the earlier works and provides nearly optimal results. In the second part, an efficient heuristic algorithm for the placement of standard cells in a rectangular or rectilinear region using successive alternating-direction ordering (SADO) is proposed, which is fast and provides good results. An advantage of the proposed algorithm is that, compared to the Min-Cut placement which only minimizes the number of nets when the cells are partitioned into two, this algorithm partitions the cells with the consideration of the potential location of each cell from the very beginning. Successive cell-ordering and bi-partitioning method coupled with a slicing structure determines the positions of the cells hierarchically, which removes the greedy nature of the greedy clustering approach in positioning the cells. The computational complexity of the algorithm is proven to be $O(n(logn)^2)$. for test circuits, the measured costs, the number of routing tracks or the half-perimeter routing length, were smaller than those of the other algorithms. | eng |
dc.language | eng | - |
dc.publisher | 한국과학기술원 | - |
dc.title | Two heutistic algotithms for integrated circuitlayout | - |
dc.title.alternative | 집적회로 레이아웃을 위한 두가지 휴리스틱 알고리즘 | - |
dc.type | Thesis(Ph.D) | - |
dc.identifier.CNRN | 61337/325007 | - |
dc.description.department | 한국과학기술원 : 전기 및 전자공학과, | - |
dc.identifier.uid | 000835224 | - |
dc.contributor.localauthor | Kyung, Chong-Min | - |
dc.contributor.localauthor | 경종민 | - |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.