In this thesis, we investigate the problem of task assignment in multiple computer systems, i.e., given a set of interacting task modules comprising a distributed program to be executed on a multiple computer system, to which processor should each task module be assigned? A module is taken to be a collection of procedures of subroutines, or could be one or more data files. There are bindings or linkages between some pairs of modules since a procedure in one module may wish to transfer control to another procedure in a different module or access data contained in a different module. The task assignment problem is a fundamental aspect for distributed computing, and has received quite a lot of attention in the past decade. It arises whenever the procedures or modules of a program are distributed over several interconnected computers so that program activity moves among processors as execution proceeds. The assignment problem deals with the question of assigning task modules to processors so as to minimize the cost of running a program. The cost may be time, money or some other measure of resource usage.
We consider two major problems on task assignment in multiple computer systems. The first problem is how to assign the task modules of a distributed program to the processors of a multiple processor system so as to minimize the total execution and interprocessor communication costs. The second one is how to minimize interprocessor communication costs with constraints on the degree to which the processors' loads are balanced.
The first problem is known to be NP-complete in its most general version. Previous work on this problem has shown that it is tractable for a system of two processors and for distributed programs whose task relationships are constrained. We first suggest a solution for a linear array network of any number of processors using the two-terminal network flow approach pioneered by Stone [Ston77]. We then propose an efficient modeling technique that transforms the assignment problem into a multi-terminal network flow problem. It is shown that the modeling technique can be successfully applied to solve the assignment problem in homogeneous systems such as an n-dimensional array network, an N processor tree network, and a single-host multiple-satellite system.
The second problem is much more intractable because of the constraints on load balance. In fact, the problem is NP-hard even for the dual-processor system. It is not easy to devise heuristic algorithms since the problem has two conflicting goals, i.e. minimizing IPC and load balancing. It is shown that the task assignment problem can be transformed into the minimum N-cut problem which has only one objective whereas the original problem has two objectives to optimize. We suggest a heuristic algorithm for the transformed problem which addresses the two conflicting goals in a fully coherent way. Experimental results indicate that the algorithm performs quite well on a variety of program-processor systems.
본 논문은 다중 컴퓨터 시스템에서 수행해야할 프로그램을 구성하는 모듈들을 어떻게 각 프로세서들에게 할당하는가 하는 일의 할당(task assignment) 문제를 다룬다. 여기에서 모듈이란 프로시저나 서브루틴들의 집합 또는 하나 혹은 여러개의 화일 집합으로 볼 수 있다. 각 모듈들은 필요에따라 콘트롤이나 데이타를 주고 받는다. 이러한 일의 할당 문제는 병렬 및 분산 처리를 위해 선결되어야 할 중요한 문제이며 지난 10 년 간 많은 연구가 되어 왔다. 일의 할당 문제는 주어진 프로그램을 수행하는데 필요한 비용을 최소화 하는데 그 목적이 있으며, 여기에서 비용이란 시간, 돈, 또는 자원 사용의 어떠한 척도로 볼 수 있다.
본 논문에서는 이러한 일의 할당에 대한 두 가지의 중요한 문제를 다룬다. 첫 번째 문제는 모듈들을 할당함에 있어서 어떻게 하면 전체 수행 및 통신 비용을 최소화 하는가 하는 문제이고, 두 번째 문제는 어떻게 하면 각 프로세서들의 로드(load)를 발란스 시키면서 동시에 통신 비용을 줄이는가 하는 문제이다.
첫 번째 문제는 프로세서가 두 개인 경우나 프로그램을 구성하는 모듈들의 구조가 특정한 경우에는 그 해가 있으나, 일반적으로는 NP-complete로 알려져 있다. 본 논문에서는 먼저 Stone이 제시한 양 단자 네트워크 플로우 방법을 확장하여 여러 프로세서로 구성된 선형 배열 시스템에서의 해를 제시한다. 그리고 일의 할당 문제를 다단자 네트워크 플로우 문제로 변형시키는 효율적인 모델링 방법을 제시한다. 또한, 제시된 모델링 방법을 이용하여 동종의 프로세서들로 구성된 일반적인 배열 네트워크, 트리 네트워크, 그리고 위성 시스템에서의 해들이 존재함을 보인다.
두 번째 문제는 로드 발란스의 제한 때문에 훨씬 다루기 어려운 문제로써, 프로세서가 두 개인 경우에도 NP-hard이다. 또한, 통신 비용의 최소화 와 로드 발란스의 두 가지 상반되는 목적을 추구해야 하므로 휴어리스틱 알고리즘을 구현하기도 쉽지가 않다. 본 논문에서는 이러한 두 번째 문제가 최소 다중 분할 문제로 변형됨을 보인다. 원래의 문제가 두 가지 상반되는 목적을 가짐에 반하여, 변형된 최소 다중 분할 문제는 하나의 목적만을 가진다. 이러한 변형된 최소 다중 분할 문제에 대한 휴어리스틱 알고리즘을 제시하며, 이것은 두 가지 상반되는 목적을 하나의 목적으로 밀착시켜 효율적으로 문제를 다룰 수 있다. 실험 결과에 의해 여러 프로그램-프로세서 시스템에 대하여 제시한 방법이 잘 적용됨을 보인다.
