서지주요정보
Heuristic algorithms for standard cell placement in VLSI design = 집적회로 설계시에 표준셀 배치문제를 위한 휴리스틱 알고리즘에 관한 연구
서명 / 저자 Heuristic algorithms for standard cell placement in VLSI design = 집적회로 설계시에 표준셀 배치문제를 위한 휴리스틱 알고리즘에 관한 연구 / Hwan-Gue Cho.
저자명 Cho, Hwan-Gue ; 조환규
발행사항 [대전 : 한국과학기술원, 1990
Online Access 원문보기 원문인쇄

소장정보

등록번호

8000392

소장위치/청구기호

학술문화관(문화관) 보존서고

DCS 9005

휴대폰 전송

도서상태

이용가능

대출가능

반납예정일

초록정보

In this thesis, we consider the standard cell placement problem in VLSI design works. At first, we present two fast heuristic algorithms for the constructive placement of standard cells based on Constrainted Multi-Stage Graph(CMSG) model for the rectangle-shaped chip. One has a linear time complexity and another has $O(n^{1.5})$ time complexity in the number of cells. Experimental results on the benchmarking testing data show that the proposed algorithms yield near optimal results in terms of the feed-through cells and channel density, which was verified by the comparison of the proposed algorithm with the simulated annealing and other iterative improvement algorithms. So the ample experimental results prove that CMSG model is a naturally reasonable and more efficient model for standard cell placement in the rectangle region than models of the previously studied algorithm such as min-cut partition. Moreover we studied the standard cell placement for the arbitrary rectilinear region, which is the remaining region after some macro modules such as ROM, RAM and PLA were placed in building block design. For this problem we propose a new model called Flow Model in the Closed Region (FMCR). In FMDR the quantity of flows running over the boundary is approximated to the number of signal wires crossing over the boundary line. Rather than placement in the rectangle, arbitrary rectilinear region may have a very congested region, which is carefully considered. So it is a critical work to suppress the number of wires on the region to guarantee the complete routing work. For this we propose the concept of the maximal flow-density for the plane subdivision. We proved that partition which maximizes the flow-density is the bipartition. And some properties on the maximal flow density bipartition are characterized. Several experiments to support the validity of our flow model are presented. By these experiments we show that the proposed algorithm gives the comparable wiring length and significantly reduces the wires crossing over the congested region comparing to the previously studied approach in the rectilinear region placement problem.

서지기타정보

서지기타정보
청구기호 {DCS 9005
형태사항 vii, 96 p. : 삽도 ; 26 cm
언어 영어
일반주기 저자명의 한글표기 : 조환규
지도교수의 영문표기 : Kyung-Yong Chwa
지도교수의 한글표기 : 좌경룡
학위논문 학위논문(박사) - 한국과학기술원 : 전산학과,
서지주기 Reference : p. 92-96
주제 Electric circuit analysis.
Integrated circuits --Very large scale integration.
회로 설계. --과학기술용어시소러스
Standard cells.
QR CODE qr code