Impact of Data-Reuse and Multiple Data-Copies in a Heterogeneous Computing System with Sequentially Executed Subtasks
Document Type Article
Abstract
In a heterogeneous computing (HC) environment, an application program is decomposed into subtasks, then each computationally homogeneous subtask is assigned to the machine where it is best suited for execution. It is assumed that, at any instant in time during the execution of a specific application program, only one machine is being used for program execution and only one subtask is being executed. A mathematical model is presented for three of the factors that affect the execution time of an application program in an HC system: matching, scheduling, and data relocation schemes. Two data relocation situations are identified, namely data-reuse and multiple data-copies. It is proved that without considering multiple data-copies, but allowing data-reuse, the execution time of given application program depends only on the matching scheme. A polynomial algorithm, which is minimum spanning tree based, is introduced to find the optimal scheduling scheme and the optimal data relocation scheme with respect to an arbitrary matching scheme when data-reuse and multiple data-copies are considered. Finally, a two-stage approach for matching, scheduling, and data relocation in HC is presented