Task assignment on parallel computing environments

Abstract

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 find...