Minimizing the application execution time through scheduling of subtasks and communication traffic in a heterogeneous computing system
- 1 August 1997
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Parallel and Distributed Systems
- Vol. 8 (8) , 857-871
- https://doi.org/10.1109/71.605771
Abstract
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 execution time is minimized. A mathematical framework is presented that models the matching of subtasks to machines, scheduling of subtasks' computation, scheduling of intermachine communication steps, and selection of sources of shared data items for intermachine communication (data relocation). The goal of this work is to generate a provably optimal scheme for communicating shared data among subtasks as an enhancement to any 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 polynomial algorithm is introduced to optimize scheduling and data relocation with respect to any given matching of subtasks to machines. The data relocation scheme is then extended to reduce intermachine data communication time in an HC environment with a given matching and scheduling of subtasks' computation where: multiple subtasks' computations can be performed concurrently on different machines; subtask computation steps can be overlapped with other subtasks' communication steps for intermachine data transfers; and machines in the HC suite are interconnected by a shared-bus type of network.Keywords
This publication has 20 references indexed in Scilit:
- A Selection Theory and Methodology for Heterogeneous SupercomputingPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2005
- A Case Study in Metacomputing: Distributed Simulations of Mixing in Turbulent ConvectionPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2005
- Matching and scheduling in a generalized optimal selection theoryPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Estimating execution time for parallel tasks in heterogeneous processing (HP) environmentPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Modeling and characterizing parallel computing performance on heterogeneous networks of workstationsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Loop scheduling for heterogeneityPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- A parallel approach for multiprocessor schedulingPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Heterogeneous computing: challenges and opportunitiesComputer, 1993
- Heuristic algorithms for task assignment in distributed systemsIEEE Transactions on Computers, 1988
- A Shortest Tree Algorithm for Optimal Assignments Across Space and Time in a Distributed Processor SystemIEEE Transactions on Software Engineering, 1981