Loading...
Please wait, while we are loading the content...
Similar Documents
A Performance Study of Diffusive vs . Remapped Load-Balancing Schemes
| Content Provider | Semantic Scholar |
|---|---|
| Author | Schloegel, Kirk Karypis, George Kumar, Vipin Biswas, Rupak Oliker, Leonid |
| Copyright Year | 1999 |
| Abstract | For a large class of irregular grid applications, the computational structure of the problem changes in an incremental fashion from one phase of the computation to another. Eventually, as the graph evolves, it becomes necessary to correct the partition in accordance with the structural changes in the computation. Partitioning the graph from scratch and then intelligently remapping the resulting partition will accomplish this task. Two different types of schemes to accomplish this task have been developed recently. In one scheme, the graph is partitioned from scratch and then the resulting partition is remapped intelligently to the original partition. The second type of scheme use a multilevel diffusion repartitioner. In this paper, we conduct a comparison study on repartitioning via intelligent remapping versus repartitioning by diffusion. We show that multilevel diffusion algorithms generally produce significantly lower data migration overhead for adaptive graphs in which low magnitude localized or non-localized imbalances occur and for graphs in which high magnitude imbalances occurs globally throughout the domains than partitioning from scratch and remapping the resulting partition. We show that for the class of problems in which high magnitude imbalances occur in localized areas of the graph, partitioning from scratch and remapping the resulting partition will result in very low edge-cuts and data migration overheads which are similar to those obtained by diffusive schemes. Finally, we show that the run times of the various schemes are all similar. This work was supported by NSF CCR-9423082, by Army Research Office contract DA/DAAH04-95-1-0538, by Army High Performance Computing Research Center cooperative agreement number DAAH04-95-2-0003/contract number DAAH04-95-C-0008, by the IBM Partnership Award, and by the IBM SUR equipment grant. Access to computing facilities was provided by AHPCRC, Minnesota Supercomputer Institute. Related papers are available via WWW at URL: http://www.cs.umn.edu/ ̃karypis yUniversity of Minnesota, Department of Computer Science & Engineering / Army HPC Center, Minneapolis, MN zUniversity of Minnesota, Department of Computer Science & Engineering / Army HPC Center, Minneapolis, MN xUniversity of Minnesota, Department of Computer Science & Engineering / Army HPC Center, Minneapolis, MN {NASA Ames Research Center, Moffett Field, CA kNASA Ames Research Center, Moffett Field, CA |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://www.msi.umn.edu/general/Reports/rptfiles/UMSI2000-55/UMSI_2000-55.pdf |
| Alternate Webpage(s) | http://glaros.dtc.umn.edu/gkhome/fetch/papers/amlICPP98.pdf |
| Alternate Webpage(s) | http://www.msi.umn.edu/general/Reports/rptfiles/UMSI2000-55/UMSI_2000-55.ps |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
