Three classes of placement algorithms for gate array, standard cell and macro cell were implemented using simulated annealing which is one of combinatorial the optimization methods, and the effects of several parameters such as the number of inner loop and the ratio of weights on the final results were investigated. Overall, it was confirmed through wide experimental results that simulated annealing has proven to give consistently good quality layouts.
A new constructive placement algorithm called 'Constrained Clustering Placement (CCP)' was proposed to solve placement problems in a very short time. The results of this algorithm were shown to be comparable to those of the classical methods such as FDR (Force Directed Relaxation) and Min-Cut, while the computation time needed in CCP was much shorter, so that this algorithm can be used as a good initial placement for simulated annealing. By using CCP as initial placement rather than random placement in simulated annealing, we were able to save around 30% of computation time.
집적회로의 설계 및 공정 기술이 발전함에 따라 선로 저항과 소비전력때문에 이미 설계된 회로블락을 chip 내에 효과적으로 배치하여야 한다.
본 논문에서는 회로블락의 효과적인 배치를 위하여 최적화 기법의 하나인 simulated annealing을 이용하여 3가지 종류의 블락에 대하여 프로그램을 구현하였다. 또한 simulated annealing의 초기 배치로서 효율적인 Constrained Clustering Placement (CCP)라는 알고리즘을 제안하였다.
CCP를 초기 배치로 사용하는 경우 임의의 초기 배치를 사용하는 것보다 30 % 정도의 계산 시간을 줄일 수 있었으며 CCP의 출력은 기존의 FDR ( Force Directed Relaxation)과 같은 배치 방법의 출력과 10% 내의 차이를 가지지만 시간상으로는 훨씬 짧다는 장점을 가진다.
회로블락은 gate array, standard cell과 macro cell의 3가지로 구분할 수 있으며, 본 논문에서는 이들 각각에 대하여 효과적인 cost function과 cooling schedule을 제시하였고 최종 결과에 큰 영향을 주는 parameter 에 대한 조사를 하였다.
Macro cell의 배치에서는 simulated annealing의 최종 출력이 블락의 겹침을 가질 수 있으므로 이들 겹침을 제거하면서 기존의 블락의 위치는 거의 변화시키지 않는 새로운 알고리즘을 제시하였다. Standard cell의 배치에서는 문제의 크기에 관계없이 매 transition의 cost 변화량 계산 시간이 일정하게 할 수 있는 자료 구조를 사용하였다. 전체적으로 simulated annealing은 매우 좋은 결과를 보여주고 있다.
