The International Conference for High Performance Computing, Networking, Storage, and Analysis
The International Conference for High Performance Computing, Networking, Storage, and Analysis
Workshop: IA^3 2023 - 13th Workshop on Irregular Applications: Architectures & Algorithms
Authors: Prachatos Mitra and Alexandros Daglis (Georgia Institute of Technology)
Abstract: Breadth-First Search (BFS) is a common building block for several graph processing algorithms today. In this work, we highlight that a large fraction of vertex visits across the network in distributed BFS results in wasteful work. We investigate methods to identify and filter such wasteful cross-network vertex visits to save network bandwidth for energy and performance improvements. We analyze the metadata requirements to perform such filtering in modern hierarchical distributed architectures and identify the tradeoffs between storage and filtering rate. We perform our experiments using the graph500 benchmark and provide a model to scale results to larger graphs. Finally, we propose heuristics to reduce the storage for a BFS message filter and explore the design space for implementing such filtering logic in software, hardware, or a combination.