본 논문에서는 Quadratic Programming(QP)을 이용한 효과적인 광역배치 기법을 제안한다. QP를 이용한 배치 기법의 단점인 셀 밀집 문제를 해결하기 위해 추가적인 힘(additional force)과 Grid Pre-warping 기법을 사용하였다 추가적인 힘은 밀집도에 기반한 값으로 적절한 힘을 구하기 위해 새로운 밀집도 함수를 고안하였다. Grid Pre-warping은 셀 좌표 사이의 상대적인 순서에 따라 셀들을 전체 영역에 재배치하는 기법이다. 새로운 밀집도 함수를 통해 구해진 추가적인 힘과 Pre-warping 기법을 반복적으로 적용하여 셀들이 효과적으로 분산된 광역배치를 얻었다. 이렇게 얻어진 배치를 "middle-down" 방식의 배치기인 Mongre의 초기배치로 적용하여 최종 상세배치 결과를 얻었다 제안하는 기법을 적용한 실험결과, FM 기법을 이용한 광역배치에 비해 향상된 결과를 보였으며, 우수한 배치기로 알려진 FengShui, Dragon과도 비교할만한 결과를 얻었다.
In this paper, we propose an effective global placement technique using quadratic programming(QP). In order to resolve cell congestion problem which is a drawback of QP based placement techniques, additional force and grid pre-warping technique are used. We devised a new density function for evaluating proper additional force which depends on density. Grid pre-warping technique relocates cells over entire area according to the relative ordering between coordinates of cells. Using the additional force obtained by the new density function and applying the pre-warping technique iteratively we obtained a well-distributed global placement. Mongrel which is a middle-down methodology based placer takes such a good global placement as an initial placement and produces a final detailed placement. Experimental results show that proposed technique outperforms the FM algorithm based global placement and are comparable with the well-known leading placers, FengShui, Dragon.
