In a multi-computer systems, a job is usually decomposed into several cooperating modules which are then assigned to a set of processors in the system to exploit the inherent parallelism in job execution and to make use of computational capabilities and resources of the system efficiently.
In this thesis, we investigated the problem of assigning tasks onto multi-computers. The problem involves the development of task allocation models for the multi-computer system. The model must allocate tasks among processors to archive the following goals:
$\bullet$ To accommodate specification of a large number of constraints to facilitate a variety of engineering application requirements.
$\bullet$ To balance the utilization of individual processors in the distributed computing system. and
$\bullet$ To minimize interprocessor communication cost.
In this thesis, we first deal with static task assignment problem for the host-satellite multi-computer system. The assignment problem, which is the problem of assigning the task modules of a task to the processors of a multi-computer system is known to be NP-complete in its most general cases. Previous work on this problem has shown in tractable for a system of two processors[Stone77]. We propose a graph theoretic approach which finds optimal solutions for the general multiple-satellite system. Our work is an extension of the Stone's two-processor approach to the case for the multiple-satellite system. The problem is solved by applying the well-known network flow algorithm in the related two-terminal network graphs. Therefore, the task assignment problem in a homogeneous satellite system can be solved in time no worse than $O(NM^3)$ by applying the network flow algorithm, where N and M are the number of satellites and the number of modules, respectively.
Secondly, the task allocation problem for the heterogeneous multi-computer system is concerned. In general, we are considering a heterogeneous processor system in which each processor may have different performance and reliability characteristics. In order to fully utilize this diversity of processing power it is advantageous to assign the program modules of a distributed program to the processors in such a way that the execution time of the entire program is minimized. This assignment of tasks to processors to maximize performance is commonly called load balancing, since the overloaded processors can be perform its own processing with the performance degradation. If a processor is over-loaded, the amount by which its load is upper it's load capability is a measure of loss or price paid because of imbalance, compared to the case when each processor has the suitable load. We propose a new objective function which formulate this imbalance cost efficiently. Thus the task allocation problem is to be carried out so that each module is assigned to a processor whose capabilities are most appropriate for the module, and the total cost is minimized that sum of inter-processor communication cost and execution cost and imbalance cost of the assignment. The finding optimal assignment is NP-hard, thus we propose an efficient heuristic algorithm with time complexity O($NM^2$). We also consider the task assignment problem for the homogeneous multi-computer system. In this case, all processors are functionally identical, thus communication overhead becomes important factors in an assignment. An heuristic algorithm which finding a good assignment is proposed. The performance of the proposed algorithms are examined using a variety of task graphs including tree, cube, mesh and random graphs.
Finally, the simulated annealing(SA) algorithm and the genetic algorithm(GA) for the assignment problem are presented. The simulated annealing approach is based on an analogy between the annealing process in which a material is melted and cooled very slowly and the solution of difficult combinatorial optimization problem. The running times required by simulated annealing approach are thus excessive. Genetic algorithms are parallel search algorithms based on principles from population genetics. The performances of SA and GA algorithms are examined using a variety of task graphs including tree, cube, mesh and random graphs. The algorithms are implemented in C on a SPARC II workstation. hypercube multicomputers are used for target systems to represent the generalized array systems. Experimental results indicate that the algorithms performs quite well on a variety of program-processor systems.
단일의 프로세서로 운영되는 컴퓨터는 프로세서 기술의 한계로 인하여 컴퓨터 시스템의 성능향상의 포화상태에 있다. 이러한 점을 극복하기 위하여 한 시스템 내부에 복수개의 프로세서를 사용하는 다중컴퓨터 시스템이 등장하게 되었다. 이러한 다중컴퓨터 시스템을 효율적으로 활용하기 위해서는 수행될 작업과 시스템의 구성에 따라서 부가적으로 수행되어야 하는 일이 있다. 일단 작업을 각각의 프로세서에서 수행될수있는 작은 모듈로 분리하는 작업분할 단계와 이를 시스템의 프로세서에 할당하는 할당이 매우 중요한 문제로 대두된다. 본 논문은 분할된 작업모듈을 시스템에 할당하는 할당 문제를 다룬다.
분할된 작업모듈 간에는 다른 작업모듈과 연관성을 가지게 되고 이는 모듈과의 정보교환이 필요함을 나타낸다. 따라서 분할된 작업이 수행하기 위하여 필요한 비용은 모듈이 할당된 프로세서 에서 수행되는대 소요되는 계산비용과 모듈간의 정보교환을 위해 소요되는 통신비용으로 대별된다. 계산비용과 통신비용은 상호 연관되어 있음은 자명하다. 다중프로세서 시스템에서 분할된 작업을 효율적으로 수행하기 위해서는 계산비용과 통신비용이 적게 소요되는 할당을 필요로 하게 된다. 이렇게 분할된 작업을 다중프로세서 시스템에 할당하는 문제를 작업할당문제 라고 하는데 최적의 할당을 구하는 문제는 몇몇의 제한된 경우를 제외하고는 NP-hard 의 범주에 포함되고 이는 다항식의 복잡도를 가지는 최적할당 알고리즘이 존재하지 않음을 뜻한다.
이종의 2개의 프로세서에의 할당방법은 Stone[Stone77] 에의하여 제시 되었다. 이때의 할당비용은 계산비용과 통신비용의 합으로 정의하고 할당의 문제를 그래프의 문제로 변환한후 네트웍 플로우의 알고리즘을 적용하는것이다. 이러한 방법을 통하여 거의 모든경우의 할당문제가 NP-hard 범주에 포함됨에 불구하고 이경우에는 다항식의 복잡도를 가지는 해결방법을 보인것이다. 하지만 프로세서가 3 개 이상일때는 역시 다항식의 복잡도를 가지는 할당방법이 존재하지 않는다. 우리는 Stone 의 방법을 확장하여 프로세서가 별 모양의 구성을 가지는 경우에 최적의 할당을 구하는 방법을 제시 하였다.
Stone 의 방법은 이론적으로 간결한 모양을 가지지만 실제의 경우 프로세서의 능력이 크게 다르지 않고 이때문에 계산비용보다 통신비용을 줄이려는 경향이 강하게 나타난다. 따라서 특정한 프로세서에 과한 부하가 부과되고 이는 전체적인 시스템의 성능을 저하시키는 요인이 된다. 최근에 발표되는 다중프로세서 시스템은 거의 대부분이 동종의 프로세서를 채용하고 있으며 이 경우에의 할당문제는 각각의 프로세서에 균등한 부하가 부가되도록 하는 할당이 필요하다. 이를 해결하기 위하여 각각의 프로세서에 일정량의 부하를 부과할수있는 제약조건을 도입하게 되는데 본논문에서는 이 제약조건을 비용함수로 변환하는 방법을 도입하였다.
만약 다중시스템의 프로세서들이 모두 같다면 계산비용은 모듈이 어떠한 프로세서에 할당되더라도 같아지게 되고 이때는 통신비용을 줄이려는 방향으로 할당이 이루어 지게 된다. 단지 통신비용만을 최소로 하려는 할당은 모든 모듈을 하나의 프로세서로 할당하게 하고 이때는 단일프로세서에서 작업하는것과 같게된다. 다중프로세서 시스템의 특징을 최대로 살리게 하기 위해서는 각각의 프로세서에 균일한 양의 작업을 할당하도록 하는것이 최선이고 이때의 할당비용은 단지 통신비용을 최소화 하는것이 된다.
이때 할당된 모듈간의 통신은 다중컴퓨터의 시스템의 통신 체널을 통하여 이루어 지는데 통신 비용만을 고려한 할당은 각각통신채널의 능력을 고려하지 않았기 때문에 특정한 채널에 통신이 집중되는 현상이 발생한다. 이로인하여 실제 수행된는 작업은 과중부하를 가진 채널에 의하여 종속되게 된다. 따라서 단순히 통신비용을 줄이는 할당은 적합하지 않음을 알수 있다. 이를 위하여 본 논문에서는 통신의 부하를 고려한 새로운 비용함수를 제안하였으며 이 비용함수를 고려한 할당을 구하는 문제를 풀수있는 휴리스틱 알고리즘을 제안 하였다. 제안된 알고리즘은 다양한 시믈레이션을 통하여 알고리즘의 효율을 검정하였다.
시뮬레이티드 어닐링(SA) 방법과 유전자 알고리즘(GA)은 국부적 최적값에서 벗어나서 최적값에 도달할수 있는 가는성을 제공하는 방법이다. 일반적으로 이들 방법은 휴리스틱 방법에 비하여 훨신 긴 시간을 소요하게되면서 보다 나은 할당을 구해낸다. 우리는 앞에서 제시한 휴리스틱의 방법을 채용한 SA, GA 알고리즘을 구성 하였다. 이들 알고리즘의 특성과 성능의 비교도 진행되었는데 GA 알고리즘은 단순 감소하는 비용을 가진 할당을 지속적으로 찾아가는데 비하여 SA 알고리즘은 때로 증가하는 할당도 찾고있음이 관찰되었다. 계산시간또한 GA 알고리즘이 SA 알고리즘에 비하여 짧게 소요 되었다. 단지 GA 의 방식은 SA 방식에 비교하여 훨신 많은 메모리를 소요하였다.