Early in the VLSI design process, designers must make far reaching decisions based on incomplete or tentative information. The external interface of the cells that correspond to the constituents (size and shape of components and the positions of the pins) must sometimes be determined before the cells have been designed. Floorplanning consists of finding positions for the constituent components and determining constraints on external interfaces for the corresponding cells that have flexibility in their interface. That is, the floorplanning problem is concerned with the placement of rectangular cells of varying sizes and shapes such that the total area occupied by the cells and the interconnections is minimum.
Floorplanning is related to placement, and many of the same techniques are used. However, the extra degree of freedom (the flexibility of the interfaces of the cells that comprise the design) significantly expands the size of the design space that must be exposed to component placement.
In the physical design, due to the high complexity of the problem, most systems divide the physical design process into four steps: floorplanning, pin assignment, global routing and detailed routing. However, because these steps are very closed related to each other, these problems must be considered at same time.
We propose a new floorplanning algorithm which handles a mixture of fixedshaped and flexible-shaped blocks in a chip aspect ratio within a given range combining the floorplanning step, the pin assignment step and global routing step. This algorithm consists of three stages. In the first stages, overlapped blocks in the initial placement obtained using FDR (Force Directed Relaxation) are spread out uniformly over the whole chip area using the so-called Ratioed Rectangular Voronoi Diagram such that each block finds enough space without significant overlap with its neighboring blocks. In the second stage, each block is reshaped or moved by the independent move of each block edge according to the attractive force and repulsive force exerted on it due to the overlap and dead space, respectively. In the third stage, each block is reshaped or moved by the independent move of each block edge according to the attractive force and repulsive force exerted on it due to the overlap and wiring area, respectively, after the pin assignment and the global routing. Experimental results were obtained on MCNC placement benchmark circuit. Significant improvement of the chip utilization factor has been obtained, compared to the earlier works.
An important step in general problem of floorplanning and routing of general cells is the assignment of pins to positions on the boundaries of the general cells. A major reason for pin assignment is potential of obtaining better routing results. Pin assignment problem has been handled independently of floorplanning and global routing. However these problems are very closed related to each other.
We propose a new pin assignment algorithm which can be used in floorplanning to minimize the total wiring length and channel area while satisfying the minimum distance constraint among pin positions on the block boundary. This algorithm is included as a part of the floorplanning in which block shapes are iteratively modified by the channel density obtained as a result of global routing. The proposed pin assignment algorithm consists of three stages; approximate pin assignment, global routing and detailed pin assignment. Experimental results were obtained using MCNC placement and floorplanning benchmark examples and have demonstrated the fastness and the performance of the proposed algorithm.
VLSI 설계에서 설계자는 집적도를 높이기 위하여 블록들의 내부구조가 결정되어 있지 않은 상태에서 블록을 배치하고 블록의 모양을 결정해야 하는 경우가 많다. 이와 같이 floorplanning은 배선 길이와 전체 chip 면적을 최소화하면서 블록들을 배치하고 주어진 범위 내에서 블록의 모양을 결정하는 문제이다. 일반적으로 설계의 복잡성 때문에 floorplanning은 핀 할당, 대략적 배선과는 분리되어 독립적으로, 배선영역의 근사적 추정에 의해 수행되어져 왔다.
이 논문에서는 floorplanning과 핀 할당, 대략적 배선을 동시에 실행함으로써 배선면적을 정확하게 확보하며, chip의 종횡비의 범위를 임의의 값으로 주어줄 수 있고, 내부가 설계되어 모양이 결정된 블록과 그렇지 않은 블록들이 섞여져 있는 경우에도 좋은 결과를 얻을 수 있는 알고리즘을 제안하고 있다. 이 알고리즘은 배치 시 임의의 초기배치를 입력으로 할 수 있으며 사용자에 의한 개략적인 배치 변경을 자동으로 적절한 배치로 마무리 지울 수 있는 기능을 보유하고 있다.
그리고 앞서 제안한 floorplanning에 적합한 핀 할당 알고리즘을 제안하였다. 핀 할당은 전체 배선 길이가 최소가 되도록 블록의 가장자리에 출력 또는 입력 신호핀의 위치를 결정하는 문제이다. 이 논문에서는 floorplanning, 대략적 배선을 동시에 수행하는 시스템의 한 부분이므로 빠른 계산 시간을 요구한다. 이 알고리즘은 대략적 배선을 실행한 후에 이를 근거로 하여 휴리스틱 방법에 의해 빠른 시간 내에 전체 배선 길이를 최소화하고 있으며 거의 최적해를 구하고 있다.
