DocumentCode :
2986544
Title :
Scheduling of dynamic divide-and-conquer computations on multicomputers
Author :
Karamcheti, Vijay ; Wah, Benjamin W.
Author_Institution :
Coordinated Sci. Lab., Urbana, IL, USA
fYear :
1993
fDate :
1-5 Nov 1993
Firstpage :
352
Lastpage :
359
Abstract :
The scheduling of tasks for applications with dynamic behavior traditionally rely on externally observable metrics such as the number of active processes. This paper presents a new scheduling strategy based on the observation that it may be possible to capture the near-term resource requirements of active tasks by expressions involving task parameters. Run-time evaluation of these expressions yields estimates of task behavior that are valid over a short, future interval of time. The heuristics proposed, which when used in conjunction with information supplied by profiling, can be used to annotate the source program with such expressions. Preliminary simulation results show that the use of near-future estimates in a dynamic scheduling strategy for divide-and-conquer algorithms consistently improves over traditional dynamic strategies. The performance of this strategy approaches that of the best-known deterministic strategy while incurring an overhead of the same order as other dynamic strategies
Keywords :
divide and conquer methods; parallel algorithms; parallel programming; problem solving; processor scheduling; software performance evaluation; task analysis; active tasks; divide-and-conquer algorithms; dynamic divide-and-conquer computations; expressions; heuristics; multicomputers; near-term resource requirements; profiling; run-time evaluation; simulation; source program; task parameters; task scheduling; Aerodynamics; Control systems; Dynamic scheduling; High performance computing; Job shop scheduling; Problem-solving; Processor scheduling; Runtime; Scheduling algorithm; Yield estimation;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Computer Software and Applications Conference, 1993. COMPSAC 93. Proceedings., Seventeenth Annual International
Conference_Location :
Phoenix, AZ
Print_ISBN :
0-8186-4440-0
Type :
conf
DOI :
10.1109/CMPSAC.1993.404240
Filename :
404240
Link To Document :
بازگشت