Self-Adapting Scheduling forTaskswithDependencies inStochastic Environments*t
Florina M. Ciorba, T. Andronikos · 2006
Thispaperaddresses dynamic loadbalancing algorithms fornon-dedicated heterogeneous clusters of workstations. Wepropose analgorithm called SelfAdapting Scheduling (SAS), targeted atnested loops with dependencies inastochastic environment. Thismeans that theloadentering thesystem, notbelonging tothe parallel application under execution, follows anunpredictable pattern whichcanbemodeled byastochastic process. SAStakes intoaccount thehistory ofprevioustiming results andtheload patterns inorder tomake accurate loadbalancing predictions. Westudy theperformance ofSASincomparison withDTSS.Weestablished inprevious workthat DTSSisthemostefficient self-scheduling algorithm forloops withdependencies onheterogeneous clusters. Wetest ouralgorithm undertheassumption that theinterarrival times andlifetimes ofincoming jobs areexponentially distributed. The experimental results showthat SASsignificantly outperforms DTSSespecially withrapidly varying loads.