Placement and global routing of arbitrarily sized rectangular functional blocks in the chip plane are studied according to their interconnectivities.
The objective of the placement is to minimize the chip area and the interconnection wire lengths. The placement process consists of three major phases: the clustering phase to analyze the block connectivities, the packing phase to deal with the size and the shape of blocks, and the trade off phase to minimize the interconnection wire lengths.
In global routing, the classical shortest path algorithm is used to select the path through the routing channels to be used for interconnection net.
Currently, this system runs on a MV 10000 under AOS/VS system. Tectronix 4114A or 4107 terminal is used as the graphic display, and tectronix 4631 hard copy unit is used for the final output. The entire system is implemented in C language. Many examples have been tested. For an example chip with 20 blocks and 100 pins, it takes 0.017 CPU seconds to finish the placement and the global routing.
기능 블럭을 칩 평면에 배치함에 있어서 전체 칩 면적을 작게하고 배선 길이를 짧게 하기 위한 방법을 연구하였다.
기능 블럭 상호간의 연결도를 분석하여 배치 순서를 결정하고 그 순서에 준하여 이미 배치된 블럭과 배치될 블럭과의 크기와 모양을 고려하여 칩 면적을 줄이는 방향으로 전체 칩 평면에 구불 구불한 모양으로 배치한 후 각 블럭을 회전 또는 뒤집어 보면서 전체 배선 길이가 짧아지도록 한다.
전체적 배선 문제는 수직 및 수평 채널을 정의한 다음 각 채널의 최단 경로를 찾는 문제로 바꾸어 해결하였다. 또한 각 채널의 밀도를 계산하여 100% 배선 가능하도록 블럭들을 재배치하였다.
100개의 연결 핀을 갖는 20개 블럭을 배치 및 재배치하는 경우 0.017CPU시간이 소요된다.
