This thesis deals with the simulated annealing approach to task allocation problem in parallel computing system, especially in hypercube. Simulated annealing has been given much attention for its insensitivity to the problem in concern, its capability to adapt any complex objective functions and constraints, its simplicity to implement any kinds of problem, and its performance to find "good" solutions, compared to other combinatorial optimization methods. On the contrary it needs very large computational efforts and this shortcoming makes it intractable to use simulated annealing to solve task allocation problem.
We found, however, that task allocation problem has some peculiar characteristics which cannot be met in other combinatorial problems. This thesis points out such characteristics and, by utilizing them to the best, attempts to make simulated annealing be tractable one for solving task allocation problem in computational time. We show that the size of the configuration space for task allocation problem can be reduced in great extent. New algorithms for generating set of moves are proposed. By using these algorithms, the efficiency of simulated annealing algorithm is ever increased and hence less computation time is required. We empirically show that no serious local optima are exist in the task allocation problem if the target processor architecture has degree of regularity and symmetry, which are quite realistic assumptions for today's most existing parallel computing systems, and by using this fact an argument for setting the initial value of temperature parameter is described.
In the second part of the thesis, we present another view point of simulated annealing; while most previous works on simulated annealing have focused on the "optimization" aspect of annealing, we pay much attention to the "simulation" aspect of it. By changing the view point of simulated annealing in this way, more efficient annealing schedules can be developed with the aids of known simulation techniques. As a working example, we present a method which dynamically determines the necessary length of the Markov chain in simulated annealing by applying the sequential procedure used in conventional simulation analysis.
Finally, to reduce the necessary computational time to solve task allocation problem, the approaches to run task allocation algorithm itself on a parallel computing system, not on uniprocessor system, are presented. The execution of simplex method, which is the central technique of solving linear programming problem, on hypercube parallel computing system is described and the parallel execution of simulated annealing algorithm on parallel computing system is discussed, too.
본 논문은 하이퍼큐브 구조를 갖는 병렬처리 컴퓨터에서 시뮬레이티드 어닐링을 이용하여 일을 할당하는 방법에 대해 주로 다루었다. 시뮬레이티드 어닐링은 다른 방법들에 비해서 구현이 쉽고, 풀고자 하는 문제에 대해 비교적 독립적이며, 대개의 경우 가장 좋은 해를 찾아낸다는 등의 이유로 널리 사용되어지고 있으나, 소요되는 계산시간이 너무나 많이 걸리는 단점으로 인해 일의 할당 문제를 푸는 방법으로는 적당하지 않은 것으로 여겨져 왔다.
시뮬레이티드 어닐링의 이러한 단점을 극복하기 위해 본 논문에서는 크게 세가지의 방법을 제시하였다. 첫째는 일의 할당 문제가 가지는 일반적인 특성 및 하이퍼큐브 컴퓨터가 구조적으로 가지는 특징들을 최대한 이용하여 최적상태를 찾아내는 탐색공간의 크기를 대폭 줄이는 방법을 제안하였으며, 탐색효율이 높아질 수 있도록 하는 새로운 교란 (perturbation) 알고리즘을 유도하였다. 아울러 하이퍼큐브 상에서의 일의 할당 문제인 경우 어닐링의 초기온도를 매우 낮은 값으로 두더라도 국부적 최적상태 (local optimum) 에 빠질 확률은 극히 작다는 것을 실험적으로 밝혔다.
두번째 방법은 시뮬레이티드 어닐링과 시뮬레이션 (simulation) 과의 상호연관관계를 밝혀냄으로써 기존의 시뮬레이션에서 사용되어지던 각종 기법들을 시뮬레이티드 어닐링에 그대로 사용할 수 있도록 하는 것이다. 효율적인 시뮬레이션을 위한 방법들은 예로부터 많이 연구되어져 왔는데, 이러한 방법들을 시뮬레이티드 어닐링에 적용하여 마찬가지로 효율적인 어닐링 스케듈을 이끌어 내도록 하였다.
마지막 세번째 방법은 병렬처리컴퓨터 자체를 이용하여 일의 할당 문제를 병렬로 푸는 방법에 대한 것이다. 최적상태를 찾아내는데 널리 사용되어지는 선형 프로그래밍 (linear programming) 문제를 하이퍼큐브 컴퓨터 상에서 병렬로 풀어나가는 방법에 대해 다루었으며, 이와 더불어 시뮬레이티드 어닐링 알고리즘을 시뮬레이션과 연관시켜 병렬 시뮬레이션이 가능하도록 하여 이를 이용한 새로운 병렬 시뮬레이티드 어닐링 알고리즘을 제안하였다.
