article · 2024

Low-Depth Spatial Tree Algorithms

Yves Baumann, Tal Ben‐Nun, Maciej Besta, Lukas Gianinazzi, Torsten Hoefler, Piotr Łuczyński

Cited by 2Abstract and details only

Abstract

Contemporary accelerator designs exhibit a high degree of spatial localization, wherein two-dimensional physical distance determines communication costs between processing elements. This situation presents considerable algorithmic challenges, particularly when managing sparse data, a pivotal component in progressing data science. The spatial computer model quantifies communication locality by weighting processor communication costs by distance, introducing a term named energy. Moreover, it integrates depth, a widely-utilized metric, to promote high parallelism. We propose and analyze a framework for efficient spatial tree algorithms within the spatial computer model. Our primary method constructs a spatial tree layout that optimizes the locality of the neighbors in the compute grid. This approach thereby enables locality-optimized messaging within the tree. Our layout achieves a polynomial factor improvement in energy compared to utilizing a PRAM approach. Using this layout, we develop energy-efficient treefix sum and lowest common ancestor algorithms, which are both fundamental building blocks for other graph algorithms. With high probability, our algorithms exhibit near-linear energy and poly-logarithmic depth. Our contributions augment a growing body of work demonstrating that computations can have both high spatial locality and low depth. Moreover, our work constitutes an advancement in the spatial layout of irregular and sparse computations.

Cite this paper

APA 7

Baumann, Y., Ben‐Nun, T., Besta, M., Gianinazzi, L., Hoefler, T., & Łuczyński, P. (2024). Low-Depth Spatial Tree Algorithms. https://doi.org/10.1109/ipdps57955.2024.00024

MLA 9

Baumann, Yves, et al. “Low-Depth Spatial Tree Algorithms.” 2024, https://doi.org/10.1109/ipdps57955.2024.00024.

Chicago

Baumann, Yves, Tal Ben‐Nun, Maciej Besta, Lukas Gianinazzi, Torsten Hoefler, and Piotr Łuczyński. 2024. “Low-Depth Spatial Tree Algorithms.” https://doi.org/10.1109/ipdps57955.2024.00024.

Harvard

Baumann, Y. et al. (2024) ‘Low-Depth Spatial Tree Algorithms’. Available at: https://doi.org/10.1109/ipdps57955.2024.00024.

BibTeX

@article{baumann2024depth,
  title = {{Low-Depth Spatial Tree Algorithms}},
  author = {Baumann, Yves and Ben‐Nun, Tal and Besta, Maciej and Gianinazzi, Lukas and Hoefler, Torsten and Łuczyński, Piotr},
  year = {2024},
  doi = {10.1109/ipdps57955.2024.00024}
}

Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.