The automatic placement becomes more and more important in Computer Aided Design (CAD) as the integrated-circuit density increases. However, the placement problem has been known NP-complete, and thus several heuristic algorithms have been developed. In this thesis, the simulated annealing algorithm, a general-purpose method of combinatorial optimization problem, is applied to the following placement problems, i.e., fixed grid placement, rigid random block placement and printed circuit boards placement. For each of these problems, the generation method of a new configuration, the definition of a cost function and the control philosophies of various parameters, which are considered on applying the algorithm, are presented and their effects to the convergence of the algorithm are analyzed.
최근 들어 IC 의 집적도가 매우 높아져서 하나의 IC 에 들어가는 기능불럭의 수도 매우 많아졌다. 그래서 Computer Aided Design (CAD) 에서의 자동배치 문제는 더욱 더 중요하게 되었다. 그러나 배치문제는, 각각의 블럭의 크기가 같다고 하더라도 algorithm 적으로 NP-complete 로 알려져 있다. 그래서 이러한 복잡한 배치문제를 풀기 위하여 여러 가지 heuristic algorithm 들이 개발되어 왔다. 그러나 이러한 heuristic algorithm 들은 global optimum 을 보장하지 못하고 local optimum 에 머무르는 것으로 알려져 있다. 본 논문에서는, 이러한 local opimum 으로 부터 벗어나기 위하여 문제의 크기가 큰 combinatorial 문제를 푸는데 일반적으로 사용되는 simulated annealing algorithm 을 이용하여 배치문제를 풀었다.
본 논문에서는 세 가지 경우의 배치문제에 대하여 적용하여 보았다. 첫 번째로는 simulated annealing algorithm 의 여러 가지 매개변수들의 개념을 익히기 위하여 간단하고, optimum solution 을 쉽게 알고 있는 고정격자에 블럭이 놓이는 문제를 먼저 풀었고, 이 문제에서는 optimum 에 수렴하는 것을 확인하였다. 두 번째로는 각 불럭의 크기도 다르고, 놓이는 위치도 불규칙하게 놓일 수 있는 문제에 대하여 연구하였다. 마지막으로는 다층인쇄기판 에서의 IC 들의 배치에 대하여 적용시켜보았다.
