@inproceedings{anastasiadis26a,
author = {Anastasiadis, Petros and Jelovina, Denis and Yzelman, A. N.},
title = {{PaHiS}: A Hierarchical Synchronous Parallel Model for Irregular Workloads},
year = {2026},
isbn = {9798400727610},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3816782.3819197},
doi = {10.1145/3816782.3819197},
abstract = {Large-scale solvers are critical in scientific and engineering domains, where achieving portable and near-optimal performance remains a challenge. Existing high-level parallel performance models provide coarse-grain communication cost estimates but fail to capture the hierarchical memory behavior and irregular access patterns prevalent in modern sparse solver workloads. Conversely, sparse modeling techniques focus on low-level kernel details and lack support for solver-level reasoning. To bridge this gap, we introduce PaHiS, a hierarchical cost model that represents hardware and algorithms through a multi-level abstraction of their communication, computation, and synchronization characteristics. We integrate this model into a GraphBLAS library and couple it with an automated microbenchmarking pipeline for hardware characterization, enabling solver cost estimation and thread autotuning for algorithms expressed in GraphBLAS. We evaluate the model on three CPU architectures for two solvers, demonstrating i) strong correlation between predicted and measured performance, ii) high-performance thread-level autotuning in ALP GraphBLAS, and iii) reliable guidance for high-level HW-SW co-design decisions such as hardware selection and algorithm comparison.},
booktitle = {Proceedings of the 38th ACM Symposium on Parallelism in Algorithms and Architectures},
pages = {430–444},
numpages = {15},
keywords = {performance modeling, bulk-synchronous models, autotuning, sparse linear algebra, GraphBLAS},
location = {Royal Holloway, University of London, London, United Kingdom},
series = {SPAA '26}
}