How Fast Can Graph Computations Go on Fine-grained Parallel Architectures
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866909670454591488 |
|---|---|
| author | Wang, Yuqing Colley, Charles Wheatman, Brian Su, Jiya Gleich, David F. Chien, Andrew A. |
| author_facet | Wang, Yuqing Colley, Charles Wheatman, Brian Su, Jiya Gleich, David F. Chien, Andrew A. |
| contents | Large-scale graph problems are of critical and growing importance and historically parallel architectures have provided little support. In the spirit of co-design, we explore the question, How fast can graph computing go on a fine-grained architecture? We explore the possibilities of an architecture optimized for fine-grained parallelism, natural programming, and the irregularity and skew found in real-world graphs. Using two graph benchmarks, PageRank (PR) and Breadth-First Search (BFS), we evaluate a Fine-Grained Graph architecture, UpDown, to explore what performance codesign can achieve. To demonstrate programmability, we wrote five variants of these algorithms. Simulations of up to 256 nodes (524,288 lanes) and projections to 16,384 nodes (33M lanes) show the UpDown system can achieve 637K GTEPS PR and 989K GTEPS BFS on RMAT, exceeding the best prior results by 5x and 100x respectively. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_00949 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | How Fast Can Graph Computations Go on Fine-grained Parallel Architectures Wang, Yuqing Colley, Charles Wheatman, Brian Su, Jiya Gleich, David F. Chien, Andrew A. Distributed, Parallel, and Cluster Computing Hardware Architecture Large-scale graph problems are of critical and growing importance and historically parallel architectures have provided little support. In the spirit of co-design, we explore the question, How fast can graph computing go on a fine-grained architecture? We explore the possibilities of an architecture optimized for fine-grained parallelism, natural programming, and the irregularity and skew found in real-world graphs. Using two graph benchmarks, PageRank (PR) and Breadth-First Search (BFS), we evaluate a Fine-Grained Graph architecture, UpDown, to explore what performance codesign can achieve. To demonstrate programmability, we wrote five variants of these algorithms. Simulations of up to 256 nodes (524,288 lanes) and projections to 16,384 nodes (33M lanes) show the UpDown system can achieve 637K GTEPS PR and 989K GTEPS BFS on RMAT, exceeding the best prior results by 5x and 100x respectively. |
| title | How Fast Can Graph Computations Go on Fine-grained Parallel Architectures |
| topic | Distributed, Parallel, and Cluster Computing Hardware Architecture |
| url | https://arxiv.org/abs/2507.00949 |