Two heuristic algorithms are proposed in this thesis for solving the task allocation problem encountered in distributed computing systems. A cost function defined in terms of a single unit, time, is proposed for evaluating the effectiveness of task allocation. This cost function represents the maximum time for a task to complete module execution and communication in all the processors. The proposed approaches allow various system constraints to be included for consideration. Graphs are used to represent the module relationship of a given task and the processor structure of a distributed computing system. Contrary to an optimal approach which is computationally complex and inefficient, the proposed heuristic approaches find near-optimal solutions very fast and, thus, are more practical than the optimal approach. Algorithm I formulates the task allocation problem as a graph partitioning probpartition a given problem graph. Algorithm II formulates the task allocation problem as a state space search problem, and solves it with a best first strategy to find a suboptimal solution fast. A useful heuristic evaluation function based on the greedy-method is used to estimate the upper-bound h(n) of $h^*(n)$. Illustrative examples and some experimental results are also included to show the effectiveness of the proposed algorithms. The final goal of this thesis is to give the facility of task allocation to the hypercube computer currently being developed in our laboratory. The hardware structure of our hypercube computer is presented, and some illustrative examples applicated to the hypercube structures are also included. The proposed algorithms work well enough even though they do not always guarantee optimal solutions.,
본 논문에서는 분산처리 system 에서의 일의 할당에 대한 두가지 heuristic algorithm을 제시하였다. 일의 할당에 대한 효율을 측정하기 위해 time이라는 하나의 단위로 정의된 cost function을 사용하며, 이것은 주어진 일을 수행하는데 소요되는 총 시간을 나타낸다. 여기서 제시하는 접근방법은 여러가지의 system 제약조건들을 쉽게 수용할 수가 있다. 분산처리 system의 일(task)과 processor 구조를 graph으로 표현했으며, 최적 접근방법(optimal approach)이 시간이 많이 걸리고 비효율적인데 반해, 본 접근방법은 최적에 가까운(near-optimal) solution을 빨리 찾기 때문에 보다 실용적이다. 알고리즘1은 graph 분할 문제(partitioning problem)로, 알고리즘2는 상태공간조사 문제(state space search problem)로써, 각각 일의 할당 문제를 풀었다. 이 두 알고리즘에 대한 효율을 보이기 위해 몇 가지 보기와 실험 결과들을 제시하였다. 본 논문의 최종 목적은 현재 본 실험실에서 개발하고 있는 하이퍼큐브 컴퓨터에게 일의 할당을 잘 할 수 있는 방법을 제공함으로써 동시 수행(parallel processing)을 효율적으로 하고자 함에 있다. 하이퍼큐브 컴퓨터의 하드웨어 구조와, 이러한 구조에서의 두 알고리즘에 대한 몇 가지 보기도 본 논문에 제시되어 있다. 실험 결과에서 알 수 있듯이, 본 논문에서 제시한 두 알고리즘은 항상 최적 solution을 찾지는 못하지만, 최적에 가까운 solution을 충분히 빨리 찾는다.
