Inc-Part: Incremental Partitioning for Load Balancing in Large-Scale Behavioral Simulations
文献类型：期刊论文
| 作者 | Zhang Yu; Liao Xiaofei; Jin Hai; Tan Guang; Min Geyong |
| 刊名 | IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS
 |
| 出版日期 | 2015 |
| 英文摘要 | Large-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. |
| 收录类别 | SCI |
| 原文出处 | http://www.computer.org/csdl/trans/td/preprint/06844883.pdf |
| 语种 | 英语 |
| 源URL | [http://ir.siat.ac.cn:8080/handle/172644/6893]  |
| 专题 | 深圳先进技术研究院_数字所 |
| 作者单位 | IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS |
| 推荐引用方式 GB/T 7714 | Zhang Yu,Liao Xiaofei,Jin Hai,et al. Inc-Part: Incremental Partitioning for Load Balancing in Large-Scale Behavioral Simulations[J]. IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS,2015. |
| APA | Zhang Yu,Liao Xiaofei,Jin Hai,Tan Guang,&Min Geyong.(2015).Inc-Part: Incremental Partitioning for Load Balancing in Large-Scale Behavioral Simulations.IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS. |
| MLA | Zhang Yu,et al."Inc-Part: Incremental Partitioning for Load Balancing in Large-Scale Behavioral Simulations".IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS (2015). |
入库方式： OAI收割
来源：深圳先进技术研究院
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。