In this thesis, we investigate the problem of task assignment in distributed computer system. The task assignment problem is unavoidable whenever we use distributed program composed of several task modules communicating each other on several computers connected each other. The motives of distributing program by task modules varies from taking benefits of specialized computing environment to integrating computing power of processor elements in the network. We shall confine our domain as benefits of specialized computing. The distribution of a program takes some overhead from interprocess communication. There is a trade-off between communication and computation. The objective function of our model is based on the minimization of total execution and communication costs.
It was proven for the graph theoretic method will find an efficient algorithm to assign tasks to processors. This method was limited to 2 processor model. Recently it was extended to n-processor with limited topology. In this thesis, some meta-properties of homogeneous network is exploited:
(1) What kind of topology has efficient task assignment algorithm.
(2) What is the criterion to distinguish easier graph.
(3) How to use the principles of the criterion.
This is modeled as the existence of a set of useful partitions over processor network which have approachability, convergency. If every node in the network is identifiable by the useful partitions, the network is reducible to two terminal problem.
The existence of useful partition depends on the topology of the network. If the network has cycles, the network may be not reducible. This model shows that some regular graph such as tree, k-dimensional mesh, is reducible to two terminal problem. Some irregular graph obtained from deleting several communication links from regular graphs is also reducible. We apply the result of homogeneous network problem to the task assignment problem is heterogeneous network whose processor element has different computing environment or execution costs. The transformation method to construct a homogeneous network from heterogeneous one is introduced. Thus the task assignment in heterogeneous network can be regarded as a kind of homogeneous one.
We have solved another problem, task assignment is completely connected graph. We introduce a transformation method to construct the tractable graph from intractable one: a star topology from completely connected graph by inserting communication relay. The concept of communication relay without execution of any tasks is novel one. Its meaning is that when two graphs have same distance matrix for some subsets and the remainders can be regarded as communication relays, they can be treated equivalently each other.
이 논문에서는 분산 컴퓨터 환경에서의 태스크 할당 문제를 연구하였다. 서로 통신이 필요한 태스크 모듈이 여럿 있는 작업을 서로 연결된 복수의 컴퓨터 위에서 처리하고자 할 때마다 태스크 할당 문제는 피할 수 없다. 프로그램을 여러개의 태스크 모듈로 분산 시키는 데에는 특수한 계산 환경을 활용하는 것에서 네트워크 위에 있는 처리장치들의 계산 능력을 종합하려는 것까지 다양하다. 여기서의 문제 영역을 특수한 계산환경의 활용으로 제한한다. 프로그램을 분산시키면 프로세스간 통신이라는 오버해드가 발생한다. 통신과 계산사이에는 트레이드 오프관계가 있다. 이 논문에서의 목적함수는 수행비용과 통신비용의 합을 최소화하는 것으로 하였다.
그래프 이론 방법으로 태스크를 처리장치에 할당하는 효율적인 알고리즘을 발견할 수 있음이 증명되었다. 이 방법은 처리장치가 2개뿐인 것으로 제한이 있었다. 최근에 제한된 형상에 대해서는 n 개의 처리장치를 갖는 것으로 확장이 되었다. 이 논문에서는 동질 네트워크에서의 몇몇 성질을 추구하였다.
(1) 어떤 형상이 효율적인 태스크 할당 알고리즘을 갖는가
(2) 이렇게 용이한 그래프를 구분하는 기준은 무엇인가
(3) 이 기준을 사용하는 방법
이것을 접근성과 수렴성을 지닌 처리장치 네트워크에 대한 유용한 분할의 존재로 모형 화하였다. 네트워크에 있는 모든 노드를 유용한 분할로 구분 할 수 있으면 그 네트워크는 축약가능하다. 유용한 분할의 존재 여부는 네트워크의 형상에 달렸는 데, 네트워크에 사이클이 있으면 그 네트워크는 축약 가능하지 않을 것이다.
이 모형으로 트리나 k-차원의 메시같은 정형화된 그래프가 2 단자 네트워크로 축약 가능함을 보였다. 몇몇 통신 연결을 삭제해 얻은 비 정형의 네트워크도 역시축약 가능하다.
동질 네트워크 문제에서 얻은 결과를 계산환경과 수행비용이 서로 다른 비동질 네트워크에서의 태스크 할당문제에 적용하였다. 비동질 네트워크에서 동질 네트워크를 구축하는 변환방법이 제시되었다. 따라서 비동질 네트워크에서의 태스크 할당은 동질의 한 경우로 여길 수 있게 되었다.
완전히 연결된 네트워크에서의 태스크 할당 문제를 풀었다. 어려운 형태의 그래프를 손댈 수 있는 형태로 구축하는 변환 방법이 제시되었다. 통신 연계 노드를 삽입하여 완전 연결 그래프를 별 모양으로 만들었다. 어떤 태스크도 수행하지 않는 통신 연계 노드 개념은 새로운 것이다. 두개의 그래프의 서브그래프가 있어서 각각의 거리 매트릭스가 동일하며 나머지는 통신연계로 여길 수 있다면, 그 두개의 그래프는 동일하게 취급할 수 있다는 뜻이다.
