MINIMIZING THE APPLICATION EXECUTION TIME THROUGH SCHEDULING OF SUBTASKS AND COMMUNICATION TRAFFIC IN A HETEROGENEOUS COMPUTING SYSTEM

In a heterogeneous computing (HC) environment consisting of different types of machines, an application program is decomposed into subtasks, each of which is computationally homogeneous. The goal is to execute subtasks on the machines in such a way that the total program executio n time is minimized. A mathematical framework is presented that models the matching of subtasks to machines, scheduling of subtasks' computa tion, scheduling of intermachine communication steps, and selection of sources of shared data items for intermachine communication (data rel ocation). The goal of this work is to generate a provably optimal sche me for communicating shared data among subtasks as an enhancement to a ny given matching and scheduling. Initially, it is assumed that at any instant in time, only one machine is being used for program execution and only one subtask is being executed. Based on this assumption, a p olynomial algorithm is introduced to optimize scheduling and data relo cation with respect to any given matching of subtasks to machines. The data relocation scheme is then extended to reduce intermachine data c ommunication time in an HC environment with a given matching and sched uling of subtasks' computation where: Ij multiple subtasks' computatio ns can be performed concurrently on different machines; 2) subtask com putation stteps can be overlapped with other subtasks' communication s teps for intermachine date transfers; and 3) machines in the HC suite are interconnected by a shared-bus type of network.