• Home
• People
• Jobs
• Visit
• Thesis Topics
• Publications
• Conference Rankings
• Research
• Bcast
• Teaching
• Contact

SPONSORS

COLLABORATIONS

The documents distributed by this server have been provided by the contributing authors as a means to ensure timely dissemination of scholarly and technical work on a noncommercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

Publications of SPCL

Y. Baumann, T. Ben-Nun, M. Besta, L. Gianinazzi, T. Hoefler, P. Luczynski:
	Low-Depth Spatial Tree Algorithms (In Proceedings of the 38th IEEE International Parallel and Distributed Processing Symposium (IPDPS'24), presented in San Francisco, CA, USA, pages 180-192, IEEE Press, May 2024) Publisher Reference 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. Documents download article: access preprint on arxiv: download slides:
	BibTeX
@inproceedings{,   author={Yves Baumann and Tal Ben-Nun and Maciej Besta and Lukas Gianinazzi and Torsten Hoefler and Piotr Luczynski},   title={{Low-Depth Spatial Tree Algorithms}},   year={2024},   month={05},   pages={180-192},   booktitle={Proceedings of the 38th IEEE International Parallel and Distributed Processing Symposium (IPDPS'24)},   location={San Francisco, CA, USA},   publisher={IEEE Press},   doi={10.1109/IPDPS57955.2024.00024}, }