The task assignment resides in the main part of automatic parallel compilers or interactive parallel programming tools. A parallel program is converted into a task interaction graph, an intermediate form of the program behavior, by a program analysis. The task assignment problem seek to assign M tasks of the task graph to N processors of a parallel system so as to achieve some goals such as minimization of interprocessor communication cost, good load balancing among the processors, quick turnaround time, and efficient utilization of system resources. This thesis discusses three task assignment problems on parallel computing environments. The first focuses on the assignment problem on a heterogeneous computing systems with the aim to minimize the total execution and communication times with financial constraints. The second problem deals with a tractable multicomputer systems on which a task assignment problem can be solved optimally. In the final, we investigated the effects of assignment strategies on the solution qualities in generalized array multicomputers. We first deal with static and dynamic task assignment problems in heterogeneous computing systems. A heterogeneous computing system is a suite of various parallel machines connected with a high-speed network. In the static assignment the existing assignment model is extended to incorporate the communication overhead. And the financial constraint is relaxed to utilize the trade-off between execution times and financial cost. With the extended model an optimal assignment is found on a appropriately defined layered-graph using a shortest path algorithm within O(M N$^2$). Next we consider the dynamic task assignment problem in heterogeneous linear array systems. A heterogeneous linear array system is assumed to consist of the heterogeneous machines connected linearly with communication links of different capacities. A dynamic task model is proposed and is shown that an efficient graph theoretic approach finds optimal solutions for the dynamic problem which permits relocation of each task during the program execution. The problem is solved by applying the well-known network flow algorithm in the related two-terminal network graph with the time complexity of O(N$^2$M$^2\Phi^2$ log NM$\Phi$). Secondly, the static assignment on a multicomputer system in which each processor may have unique capability is concerned. While the problem on a fully connected multicomputer is NP-hard, our network flow approach finds an optimal solution on multicomputers with cuttable topologies. The cuttable topology is recursively defined with the two graph operators product $\odot$ and bridge $oplus$. This simple but powerful definition enables the cuttable topologies to include various famous topologies such as linear array, tree, star, mesh, 3-dimensional array, hypercube and complex combined topologies. The algorithm CUTTABLE is an implementation of our approach for the cuttable topologies. Using the Goldberg-Tarjan's maximum flow algorithm, the task assignment problem on cuttable multicomputers is solved in time no worse than O(M$^3$N). The time complexity can be reduced to O(M$^3$ log N) if the interconnection structures are binary tree or hypercube. Finally, the performances of six assignment algorithms on generalized array multicomputers which contain linear array, mesh, 3-D array, and hypercube multicomputers are investigated. The algorithms correspond to six assignment strategies, called two-phase (TPA), one-phase (OPA), full-sensitive (FSA), partial-sensitive (PSA) balanced-cost one-phase (BOP), and balanced-cost full-sensitive (BFS) approaches. The algorithms are implemented by modifications of the well-known Kernighan and Lin's graph partitioning algorithm. The experimental results show that TPA and TSA (topology-sensitive) can be good candidates in designing assignment algorithms for generalized array multicomputers. But the TPA performs poorly on the high dimensional systems such as hypercubes. Therefore we recommend the usage should be restricted to mesh multicomputers. The OPA shows poor solution quality even though it can view the solution space globally. The balanced-cost approach BOP and BFS improve the assignment qualities of the OPA and FSA about 5\%. As the result, the best approach for a generalized array system is the FSA or PSA with the balanced-cost approach.
타스크 할당은 자동 병렬 컴파일러 혹은 상호작용 병렬 프로그래밍 기구의 중요한 부분이다. 병렬 프로그램은 프로그램 분석에 의해 프로그램 형태를 나타내는 타스크 상호작용 그래프로 표현된다. 타스크 할당 문제 (task assignment problem) 는 프로세서간 통신을 최소화하고, 프로세서들의 부하를 균등화시키며, 빠른 수행을 찾고, 시스템의 자원을 효율적으로 활용하기 위해, 타스크 그래프의 M 타스크들을 병렬 시스템의 N 프로세서로의 사상을 찾는 문제이다. 본 논문에서는 병렬 계산 환경에서의 세가지 타스크 할당 문제를 다룬다. 첫번째 문제는 총 수행과 통신 시간을 재정 조건 내에서 최소화하는 목적으로 이질 계산 시스템에서의 할당 문제를 다루고 두번째는 타스크 할당 문제가 최적으로 풀릴 수 있는 다중컴퓨터 시스템의 연결망 구조를 다룬다. 마지막으로 일반적 어레이 다중컴퓨터에서 할당 전략이 해에 미치는 효과를 조사한다. 첫째로 이질 계산 시스템에서의 정적 및 동적 타스크 할당 문제를 다룬다. 이질 계산 시스템은 고속 네트웍으로 연결된 다양한 병렬 기계들의 집합이다. 동적 할당에서는 기존의 할당 모델을 통신의 과부담을 고려한 모델로 확℃壤쳔같 }재정 조건을 수행 시간과 재정 비용의 적절한 선택을 위한 형태로 바꾼다. 이렇게 확장된 모델로 적절히 정의된 단계 그래프(layered graph)상에서 최단 경로 알고리즘을 이용하여 $O(MN^2)$의 시간 복잡도로 최적의 해를 구할 수 있음을 보인다. 다음으로 이질 선형 어레이 시스템에서 동적 타스크 할당 문제를 다룬다. 이질 선형 어레이 시스템은 다른 전송률을 가진 통신 링크들이 선형적으로 연결된 이질 기계들로 구성된다. 우리는 프로그램의 수행중 각 타스크들의 동적 재이동을 허용하는 동적 타스크 모델을 제안한다. 이 모델에서 효율적인 그래프 이론적 접근방법이 동적 문제에 대해 최적해를 구함을 보여준다. 이는 관련된 두 정점(two-terminal) 네트웍 그래프에서 잘 알려진 네트웍 흐름 알고리즘을 적용함으로써 $O(N^2M^2\Phi^2\log{NM}\Phi)$의 시간 복잡도로 풀릴 수 있다. 두번째로 각 프로세서가 독특한 능력을 가지고 있는 다중컴퓨터 시스템에서의 정적 할당 문제를 다룬다. 완전 연결망 다중컴퓨터의 경우는 NP-hard 문제이지만 커터블 (cuttable) 토폴로지의 경우 네트웍 흐름 접근방법은 최적 해를 구할 수 있게 한다. 케더블 토폴로지는 두개의 그래프 연산자 프러덕트 $\odot$ 와 브리지 $\oplus$ 를 사용하여 재귀적으로 정의 된다. 간단하지만 강력한 이 정의는 커터블 토폴로지로 하여금 선형 어레이, 트리, 스타, 메쉬, 3-차원 어레이, 하이퍼큐브, 그리고 복잡한 형태의 다양한 토폴로지를 포함하고 있다. CUTTABLE 알고리즘은 커터블 토폴로지의 경우 우리의 접근방법을 기술한 것이다. Goldberg 와 Tarjan 의 최대 흐름알고리즘을 사용하여 커터블 다중컴퓨터에서의 타스크 할당 문제는 $O(M^3N)$ 시간내에 풀릴 수 있다. 시간 복잡도는 이진 트리 또는 하이퍼큐브의 경우와 같이 특별한 경우들에서 $O(M^3 \log {N})$으로 감소할 수 있다. 마지막으로 선형 어레이, 메쉬, 3-차원 어레이, 그리고 하이퍼큐브 구조를 포함하는 일반적 어레이 다중컴퓨터에서 여섯 가지 할당 알고리즘의 성능을 조사한다. 각 알고리즘은 다음과 같은 여섯 가지 전략을 구현한 것이다: 이단계 (TPA), 일단계 (OPA), 전적고려 (FSA), 부분고려 (PSA), 균등비용 일단계 (BOP), 균등비용 전적고려 (BFS). 알고리즘들은 잘 알려진 Kernighan 과 Lin 의 그래프 분할 알고리즘을 변형하여 구현하였다. 실험 결과는 TPA 와 TSA (FSA 와 PSA) 가 일반적 어레이 다중컴퓨터상에서 할당 알고리즘을 구현하는데 좋은 전략이 될 수 있음을 밝히고 있다. 그러나 TPA 의 경우 하이퍼큐브와 같이 큰 차원의 경우 성능이 나빠지기 때문에 그 사용이 메쉬와 같이 낮은 차원에 국한해서 써야 한다. OPA 의 경우 해의 공간을 전역적으로 살필 수 있는 능력이 있음에도 불구하고 좋지 않은 성능을 보였다. 균등비용 접근방법, BOP 와 BFS, 은 OPA 와 FSA 의 성능을 5\% 정도 올릴 수 있음을 확인하였다. 결과적으로, 일반적 어레이 다중컴퓨터에서 가장 좋은 접근방법은 균등비용 접근방법을 사용한 FSA 또는 PSA 이다.
