DocumentCode :
3017518
Title :
Improving and Stabilizing Parallel Computer Performance Using Adaptive Backfilling
Author :
Talby, David ; Feitelson, Dror G.
Author_Institution :
Hebrew Univ., Jerusalem, Israel
fYear :
2005
fDate :
04-08 April 2005
Abstract :
The scheduler is a key component in determining the overall performance of a parallel computer, and as we show here, the schedulers in wide use today exhibit large unexplained gaps in performance during their operation. Also, different scheduling algorithms often vary in the gaps they show, suggesting that choosing the correct scheduler for each time frame can improve overall performance. We present two adaptive algorithms that achieve this: One chooses by recent past performance, and the other by the recent average degree of parallelism, which is shown to be correlated to algorithmic superiority. Simulation results for the algorithms on production workloads are analyzed, and illustrate unique features of the chaotic temporal structure of parallel workloads. We provide best parameter configurations for each algorithm, which both achieve average improvements of 10% in performance and 35% in stability for the tested workloads.
Keywords :
parallel algorithms; parallel machines; performance evaluation; processor scheduling; resource allocation; adaptive algorithm; adaptive backfilling; algorithmic superiority; chaotic temporal structure; parallel computer performance; parallelism; parameter configuration; production workloads; Adaptive algorithm; Algorithm design and analysis; Analytical models; Chaos; Computer performance; Concurrent computing; Parallel processing; Processor scheduling; Production; Scheduling algorithm;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Parallel and Distributed Processing Symposium, 2005. Proceedings. 19th IEEE International
Print_ISBN :
0-7695-2312-9
Type :
conf
DOI :
10.1109/IPDPS.2005.252
Filename :
1419908
Link To Document :
بازگشت