# Maximum Flows in Parametric Graph Templates

Preprint · Tal Ben-Nun, Lukas Gianinazzi, Torsten Hoefler, Yishai Oltchik

- Archive id: arxiv:2307.08420
- Published: 2023-07-17
- DOI: https://doi.org/10.1007/978-3-031-30448-4_8
- arXiv: https://arxiv.org/abs/2307.08420
- Source URL: https://arxiv.org/abs/2307.08420
- PDF: https://arxiv.org/pdf/2307.08420
- Provenance: arxiv

## Abstract

Execution graphs of parallel loop programs exhibit a nested, repeating structure. We show how such graphs that are the result of nested repetition can be represented by succinct parametric structures. This parametric graph template representation allows us to reason about the execution graph of a parallel program at a cost that only depends on the program size. We develop structurally-parametric polynomial-time algorithm variants of maximum flows. When the graph models a parallel loop program, the maximum flow provides a bound on the data movement during an execution of the program. By reasoning about the structure of the repeating subgraphs, we avoid explicit construction of the instantiation (e.g., the execution graph), potentially saving an exponential amount of memory and computation. Hence, our approach enables graph-based dataflow analysis in previously intractable settings.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.