A Framework to Analyze the Performance of Load Balancing Schemes for Ensembles of Stochastic Simulations

Simple item page
dc.contributor.authorAhn, Tae-Hyuken
dc.contributor.authorSandu, Adrianen
dc.contributor.authorWatson, Layne T.en
dc.contributor.authorShaffer, Clifford A.en
dc.contributor.authorCao, Yangen
dc.contributor.authorBaumann, William T.en
dc.contributor.departmentComputer Scienceen
dc.date.accessioned2013-06-19T14:36:39Zen
dc.date.available2013-06-19T14:36:39Zen
dc.date.issued2012en
dc.description.abstractEnsembles of simulations are employed to estimate the statistics of possible future states of a system, and are widely used in important applications such as climate change and biological modeling. Ensembles of runs can naturally be executed in parallel. However, when the CPU times of individual simulations vary considerably, a simple strategy of assigning an equal number of tasks per processor can lead to serious work imbalances and low parallel efficiency. This paper presents a new probabilistic framework to analyze the performance of dynamic load balancing algorithms for ensembles of simulations where many tasks are mapped onto each processor, and where the individual compute times vary considerably among tasks. Four load balancing strategies are discussed: most-dividing, all-redistribution, random-polling, and neighbor-redistribution. Simulation results with a stochastic budding yeast cell cycle model is consistent with the theoretical analysis. It is especially significant that there is a provable global decrease in load imbalance for the local rebalancing algorithms due to scalability concerns for the global rebalancing algorithms. The overall simulation time is reduced by up to 25%, and the total processor idle time by 85%.en
dc.format.mimetypeapplication/pdfen
dc.identifierhttp://eprints.cs.vt.edu/archive/00001189/en
dc.identifier.sourceurlhttp://eprints.cs.vt.edu/archive/00001189/01/LoadBalancingTPDS12.pdfen
dc.identifier.trnumberTR-12-06en
dc.identifier.urihttp://hdl.handle.net/10919/19444en
dc.language.isoenen
dc.publisherDepartment of Computer Science, Virginia Polytechnic Institute & State Universityen
dc.rightsIn Copyrighten
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/en
dc.subjectParallel computationen
dc.titleA Framework to Analyze the Performance of Load Balancing Schemes for Ensembles of Stochastic Simulationsen
dc.typeTechnical reporten
dc.type.dcmitypeTexten

Files

Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
LoadBalancingTPDS12.pdf
Size:
4.19 MB
Format:
Adobe Portable Document Format
Download

Collections

Computer Science Technical Reports
Scholarly Works, Computational Science Laboratory