Show simple item record

dc.contributor.authorZhang, Y.*
dc.contributor.authorLiao, X.F.*
dc.contributor.authorJin, H.*
dc.contributor.authorTan, G.*
dc.contributor.authorMin, Geyong*
dc.date.accessioned2016-09-21T15:46:32Z
dc.date.available2016-09-21T15:46:32Z
dc.date.issued2015
dc.identifier.citationZhang Y, Liao XF, Jin H et al (2015) Inc-Part: Incremental Partitioning for Load Balancing in Large-Scale Behavioral Simulations. IEEE Transactions on Parallel and Distributed Systems. 26(7): 1900-1909.
dc.identifier.urihttp://hdl.handle.net/10454/9259
dc.descriptionNo
dc.description.abstractLarge-scale behavioral simulations are widely used to study real-world multi-agent systems. Such programs normally run in discrete time-steps or ticks, with simulated space decomposed into domains that are distributed over a set of workers to achieve parallelism. A distinguishing feature of behavioral simulations is their frequent and high-volume group migration, the phenomenon in which simulated objects traverse domains in groups at massive scale in each tick. This results in continual and significant load imbalance among domains. To tackle this problem, traditional load balancing approaches either require excessive load re-profiling and redistribution, which lead to high computation/communication costs, or perform poorly because their statically partitioned data domains cannot reflect load changes brought by group migration. In this paper, we propose an effective and low-cost load balancing scheme, named Inc-part, based on a key observation that an object is unlikely to move a long distance (across many domains) within a single tick. This localized mobility property allows one to efficiently estimate the load of a dynamic domain incrementally, based on merely the load changes occurring in its neighborhood. The domains experiencing significant load changes are then partitioned or merged, and redistributed to redress load imbalance among the workers. Experiments on a 64-node (1,024-core) platform show that Inc-part can attain excellent load balance with dramatically lowered costs compared to state-of-the-art solutions.
dc.relation.isreferencedbyhttp://dx.doi.org/10.1109/Tpds.2014.2333511
dc.subjectBehavioral simulation
dc.subject; Load balancing
dc.subject; Incremental partitioning
dc.subject; Multi-agent system
dc.subject; Group migration
dc.subject; Transportation simulations
dc.subject; Fish schools
dc.subject; Dynamics
dc.subject; Colonies
dc.subject; Cluster
dc.titleInc-Part: Incremental Partitioning for Load Balancing in Large-Scale Behavioral Simulations
dc.status.refereedYes
dc.typeArticle
dc.type.versionNo full-text available in the repository


This item appears in the following Collection(s)

Show simple item record