Name
Title | ||
|---|---|---|
Performance modeling for hierarchical graph partitioning in heterogeneous multi-core environment |
Abstract | ||
|---|---|---|
A model to estimate the performance of graph partitioning running on heterogeneous multi-core clusters is proposed.We discover pitfalls of conventional methodologies in obtaining model parameters from multi-core systems.The impact of intra-node contention is too significant to be ignored.Modeling accuracy depends on whether overlap is adequately considered.Characteristics of input meshes may affect memory access behavior and hence become a determinant factor. Considering application behavior in graph partitioning is an arduous task because of the chicken-and-egg problem: the application behavior depends on how the graph is decomposed while achieving load balance requires the knowledge of how the application utilizes the underlying resources. Advances in multi-core processors further complicate the endeavor by introducing hardware diversity and intra-node contention. As an attempt to quantify performance for partitioning refinement, we propose a model that predicts execution times of iterative mesh-based applications running on heterogeneous multi-core clusters. Apart from considering resource heterogeneity, the model takes into account hierarchical communication characteristics, overlap between computation and communication, as well as performance penalties due to intra-node contention. We present a detailed methodology on how to obtain key parameters from a real system and highlight potential pitfalls of conventional approaches in obtaining the parameters. Experiments were conducted using a synthetic application benchmark solving a partial differential equation. Evaluation shows a good agreement between actual time measurement and the performance model. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1016/j.parco.2014.05.001 | Parallel Computing |
Keywords | Field | DocType |
Performance model,Benchmark,Graph partitioning,Memory hierarchy,Multicore processing | Cluster (physics),Polygon mesh,Memory hierarchy,Computer science,Load balancing (computing),Parallel computing,Theoretical computer science,Graph partition,Partial differential equation,Multi-core processor,Distributed computing,Computation | Journal |
Volume | Issue | ISSN |
46 | C | 0167-8191 |
Citations | PageRank | References |
1 | 0.35 | 37 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Siew Yin Chan | 1 | 7 | 0.80 |
| Teck Chaw Ling | 2 | 31 | 2.92 |
| Eric Aubanel | 3 | 57 | 9.75 |