Presentation
SIGN IN TO VIEW THIS PRESENTATION Sign In
Filtering Wasteful Vertex Visits in Breadth-First Search
DescriptionBreadth-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.
Event Type
Workshop
TimeSunday, 12 November 20235:10pm - 5:20pm MST
Location702
Algorithms
Applications
Architecture and Networks
W