Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2510.12196 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914389374795776 |
|---|---|
| author | Samoldekin, Petr Schulz, Christian Woydt, Henning |
| author_facet | Samoldekin, Petr Schulz, Christian Woydt, Henning |
| contents | Process mapping asks to assign vertices of a task graph to processing elements of a supercomputer such that the computational workload is balanced while the communication cost is minimized. Motivated by the recent success of GPU-based graph partitioners, we propose two GPU-accelerated algorithms for this optimization problem. The first algorithm employs hierarchical multisection, which partitions the task graph alongside the hierarchy of the supercomputer. The method utilizes GPU-based graph partitioners to accelerate the mapping process. The second algorithm integrates process mapping directly into the modern multilevel graph partitioning pipeline. Vital phases like coarsening and refinement are accelerated by exploiting the parallelism of GPUs. The first algorithm has, on average, about 12 percent higher communication costs than the state-of-the-art solver and thus remains competitive with it. However, in terms of speed, it vastly outperforms the competitor with a geometric mean speedup of 22 times and a maximum speedup of 934 times. The second approach is even faster, with a geometric mean speedup of 1454 times and a peak speedup of 12376 times. Compared to other algorithms that prioritize speed over solution quality, this approach has the same quality but much greater speedups. To our knowledge, these are the first GPU-based algorithms for process mapping. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_12196 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | GPU-Accelerated Algorithms for Process Mapping Samoldekin, Petr Schulz, Christian Woydt, Henning Distributed, Parallel, and Cluster Computing 8W10 Process mapping asks to assign vertices of a task graph to processing elements of a supercomputer such that the computational workload is balanced while the communication cost is minimized. Motivated by the recent success of GPU-based graph partitioners, we propose two GPU-accelerated algorithms for this optimization problem. The first algorithm employs hierarchical multisection, which partitions the task graph alongside the hierarchy of the supercomputer. The method utilizes GPU-based graph partitioners to accelerate the mapping process. The second algorithm integrates process mapping directly into the modern multilevel graph partitioning pipeline. Vital phases like coarsening and refinement are accelerated by exploiting the parallelism of GPUs. The first algorithm has, on average, about 12 percent higher communication costs than the state-of-the-art solver and thus remains competitive with it. However, in terms of speed, it vastly outperforms the competitor with a geometric mean speedup of 22 times and a maximum speedup of 934 times. The second approach is even faster, with a geometric mean speedup of 1454 times and a peak speedup of 12376 times. Compared to other algorithms that prioritize speed over solution quality, this approach has the same quality but much greater speedups. To our knowledge, these are the first GPU-based algorithms for process mapping. |
| title | GPU-Accelerated Algorithms for Process Mapping |
| topic | Distributed, Parallel, and Cluster Computing 8W10 |
| url | https://arxiv.org/abs/2510.12196 |