GENERATIONAL SCHEDULING FOR DYNAMIC TASK MANAGEMENT IN HETEROGENEOUS COMPUTING SYSTEMS

Heterogeneous computing (HC) is the coordinated use of different types of machines, networks, and interfaces in order to maximize performanc e and/or cost effectiveness. In recent years, research related to HC h as addressed one of its most fundamental challenges: how to develop a schedule of tasks on a set of heterogeneous hosts that minimizes the t ime required to execute the given tasks. The development of such a sch edule is made difficult by diverse processing abilities among the host s, data and precedence dependencies among the tasks, and other factors . This paper outlines a straightforward approach to solving this probl em, termed generational?al scheduling (GS).;GS provides fast, efficien t matching of tasks to hosts and requires little overhead to implement . This study introduces the GS approach and illustrates its effectiven ess in terms of the time to determine schedules and the quality of sch edules produced. A communication-inclusive extension of GS is presente d to illustrate how GS can be used when the overhead of transferring d ata produced be some tasks and consumed by others is significant. Fina lly, to illustrate the effectiveness of GS in a real-world environment , a series of experiments are presented using GS in the SmartNet sched uling framework, developed at US Navy's facility at the Naval Command, Control, and Ocean Surveillance Center in San Diego, California. (C) 1998 Elsevier Science Inc. All rights reserved.