Task Matching and Scheduling in Heterogeneous Computing

Task Matching and Scheduling in Heterogeneous Computing Environments Using a Genetic-Algorithm-Based Approach 1 Lee Wang,* ,2 Howard Jay Siegel,* ,2 Vwani P. Roychowdhury,† ,3 and Anthony A. Maciejewski* ,2 *Parallel Processing Laboratory, School of Electrical and Computer Engineering, Purdue University, West Lafayette, Indiana 47907-1285; and †Electrical Engineering Department, UCLA, Los Angeles, California 90095-1594 To exploit a heterogeneous computing (HC) environment, an application task may be decomposed into subtasks that have data dependencies. Subtask matching and scheduling consists of assigning subtasks to machines, ordering subtask execution for each machine, and ordering intermachine data transfers. The goal is to achieve the minimal completion time for the task. A heuristic approach

based on a genetic algorithm is developed to do matching and scheduling in HC environments. It is assumed that the matcher/scheduler is in control of a dedicated HC suite of machines. The characteristics of this genetic-algorithm-based approach include: separation of the matching and the scheduling representations, independence of the chromosome structure from the details of the communication subsystem, and consideration of overlap among all computations and communications that obey subtask precedence constraints. It is applicable to the static scheduling of production jobs and can be readily used to collectively schedule a set of tasks that are decomposed into subtasks. Some parameters and the selection scheme of the genetic algorithm were chosen experimentally to achieve the best performance. Extensive simulation tests were conducted. For small-sized problems (e.g., a small number of subtasks and a small number of machines), exhaustive searches were used to verify that this genetic-algorithm-based approach found the optimal solutions. Simulation results for larger-sized problems showed that this genetic-algorithm-based approach outperformed two nonevolutionary heuristics and a random search. © 1997 Academic Press 1. INTRODUCTION Different portions of an application task often require dif- ferent types of computation. In general, it is impossible for a single machine architecture with its associated compiler, op- erating system, and programming tools to satisfy all the com- putational requirements in such an application equally well. However, a heterogeneous computing (HC) environment that 1 This research was supported in part by NRaD under Subcontract 20- 950001-70 and by the DARPA/ITO Quorum Program under NPS Subcontract N62271-97-M-0900. 2 E-mail: {lwang,hj,maciejew}@ecn.purdue.edu. 3 E-mail: vwani@ee.ucla.edu. consists of a heterogeneous suite of machines, high-speed in- terconnections, interfaces, operating systems, communication protocols, and programming environments provides a variety of architectural capabilities, which can be orchestrated to per- form an application that has diverse execution requirements [Fre89, FrS93, KhP93, SiA96, Sun92]. In the HC environ- ment considered here, an application task can be decomposed into subtasks, where each subtask is computationally homoge- neous (well suited to a single machine), and different subtasks may have different machine architectural requirements. These subtasks can have data dependences among them. Once the application task is decomposed into subtasks, the following decisions have to be made: matching, i.e., assigning subtasks to machines, and scheduling, i.e., ordering subtask execution for each machine and ordering intermachine data transfers. In this context, the goal of HC is to achieve the minimal com- pletion time, i.e., the minimal overall execution...

Website: www.cisr.us | Filesize: -
No of Page(s): 15
Download Task Matching and Scheduling in Heterogeneous Computing - CISR.pdf