Many real-world design problems are formulated as combinatorial optimization problem in which we seek to find some combinatorial configuration that optimizes the predefined evaluation criterions. Simulated annealing has been proposed as a stochastic approach to the combinatorial optimization problems, and it has produced higher quality (near optimal) solutions for many practical design problems. There has been a great deal of interest in speeding up the simulated annealing algorithms to reduce the burdensome processing time. Multiprocessing is one of the promising research direction to massively speed up the simulated annealing algorithms.
This thesis studies the parallelization schemes of the simulated annealing algorithm for efficient implementations on multiprocessor computer systems. The fundamental aspects of the combinatorial optimization problem and the basic ideas of the simulated annealing algorithm are reviewed. The basic decomposition strategies for parallel annealings are categorized into four schemes : decomposition by functions, parallel generations / serializable acceptance, decomposition by objects, and decomposition by Markov chains. The previously proposed parallel annealing algorithms are introduced for their multiprocessor architectures, the application fields, and the decomposition schemes.
A new parallel annealing scheme, called stepwise-overlapped parallel annealing, is proposed. It can provide a massive speedup on a multiprocessor system with a large number of processors. The new parallel annealing scheme decomposes the annealing process by the Markov chains. It assigns each Markov chain to each P processors in stepwise-overlapped manner, and let processors generate different Markov chains simultaneously. Each Markov chain takes P (number of processors) information transfers to its following Markov chain. It improved the parallel annealing schedule of the systolic algorithm that was proposed by Aarts et. al. The new parallel annealing scheme keeps a good temperature profile even with a large number of processors. Also the communication pattern is enhanced.
The new parallel annealing algorithm is analyzed through a series of systematic experiments. For various problem instances, experiments with 1128 processors have been performed. Experimental results of the stepwise-overlapped parallel annealing algorithm for the traveling salesman problems show high efficiency even when a large number of processors are used; it produces near optimal solutions with the speedup ratio of 70.8 by using 128 processors. The new parallel annealing algorithm is also applied to the task allocation problems and the floorplan design problems, and the experimental results are analyzed.
Throughout the analysis of the new parallel annealing scheme, the aspects of the modeling of application problems and the convergence property of the parallel annealing algorithm are also discussed. The new parallel annealing algorithm can be efficiently implemented on a message-passing multiprocessor system with a large number of processors, such as a hypercube computer.
대부분의 설계문제는 조합 최적화 문제로 표현될 수 있으며, 이는 많은 매개변수들의 조합 형태 중 주어진 조건에 가장 최적화된 구성을 찾는 문제로 귀착된다. 시뮬레이티드 어닐링방법은 이러한 조합 최적화 문제에 대한 접근방법 중의 하나인 통계적 해결방안으로써 제안되었으며, 여러 분야의 설계문제에 잘 적용될 수 있음이 많은 연구, 실험 결과들을 통하여 발표되고있다. 그러나 시뮬레이티드 어닐링을 사용하는 알고리즘들은 과도한 실행시간을 요구한다는 것이 단점으로 지적되며, 최근 이 단점을 개선하기 위한 많은 연구들이 진행되어 왔다. 다중처리 시스템을 사용한 병렬 어닐링 방법은 이러한 방안 중 큰 개선(고속화)을 얻을 수 있는 가장 바람직한 방법이다.
본 논문에서는 많은 프로세서들로 구성된 다중처리 시스템에 효율적으로 구현될 수 있는 병렬 시뮬레이티드 어닐링 방법에 관하여 연구한다. 먼저 조합 최적화 문제와 시뮬레이티드 어닐링에 관한 기본개념 및 수학적 모델에 대하여 설명한다. 병렬 어닐링 알고리즘들에서 사용되었던 분할방법 (decomposition strategy)들을 기본적인 네가지 형태, 즉 기능 (subfunctions)에 따른 분할, 병렬 생성 및 직렬화 선택 (parallel generations / serializable acceptance), 응용 문제의 개체 (object)들에 따른 분할, 그리고 마르코프 체인 (Markov chain)의 분할 및 병렬처리 등으로 분류하며, 이들의 장단점에 대하여 분석한다. 새로운 병렬 시뮬레이티드 어닐링 방법으로서 '단계적으로 중첩된 병렬 시뮬레이티드 어닐링방법'을 본 논문에서 제시한다. 이는 마르코프 체인에 따른 분할방법을 채택하며, 기존의 순차적 어닐링 (sequential annealing)방법에서 인접한 두 마르코프 체인 사이에서 정보전달이 한번만 이루어졌던 것을 P (프로세서 갯수)번의 정보전달을 할 수 있게하고, 각 마르코프 체인을 P개의 프로세서가 단계적으로 중첩된 병렬처리를 하게한다.
본 논문에서 제시한 새로운 병렬 어닐링방법을 일련의 체계적인 실험을 통하여 그 성능을 분석한다. Traveling Salesman Problem (TSP), 프로그램 할당문제 (Task allocations) 및 VLSI 설계에서의 배치문제 (Floorplan design) 들에 새로운 병렬 어닐링 방법을 적용하며, 각 실험에서 1~128 개의 프로세서를 사용한 경우에 대하여 그 성능을 분석한다. 새로운 병렬 어닐링방법을 사용하여 225-city TSP 인 경우 128개의 프로세서를 사용하여 70.8배의 속도증가를 얻을 수 있었으며, 20개 모듈로 구성되는 VLSI 배치문제에서는 16개의 프로세서를 사용하여 14.45배의 속도증가를 얻을 수 있었다. 이상의 실험결과로부터 단계적으로 중첩된 병렬 어닐링방법은 다량의 프로세서가 사용되는 경우에도 우수한 성능을 발휘함을 알 수 있다.
병렬 어닐링방법의 분석에 있어서 적용문제의 모델링방법, 알고리즘의 접근특성 (convergency property)에 관하여 분석, 토의한다. 새로운 병렬 시뮬레이티드 어닐링방법은 적용문제의 형태에 따른 영향을 받지않고 알고리즘의 설계가 쉬운 장점이 있다. 특히 프로세서간의 통신에 따른 부하가 작으므로 하이퍼큐브와 같은 메세지 전달형 다중처리 시스템에 잘 적용 될 수 있다. 새로운 병렬 어닐링방법을 사용하여 기존의 순차적 어닐링방법보다 더 좋은 해답을 찾을 수 있었다. 앞으로 계속 연구되어야 할 부분으로서 이 새로운 병렬 어닐링방법의 이론적인 분석이 필요하다.
