Scalable Graph Algorithms on Distributed UpDown Accelerators

Graphs are a fundamental tool for representing and analyzing relationships in data, with applications spanning social networks, the web, and the biological sciences. As the volume of data continues to grow, so too do the size and complexity of the graphs we must process. Extracting insights from these massive graphs requires scalable, high-performance algorithmsWhile many graph algorithms exhibit substantial parallelism, it is often extremely fine-grained—just a few instructions—making it difficult to exploit efficiently on conventional architectures. In this work, we demonstrate how to restructure graph algorithms to run efficiently on UpDown, a scalable, programmable accelerator designed specifically for fine-grained parallelism. UpDown enables scaling graph processing algorithms to systems with millions of concurrent hardware threadsThrough detailed simulation of UpDown systems with up to one million cores, we show that our approach achieves over 100,000× parallel speedup and absolute performance that outperforms the best reported distributed systems in terms of power efficiency. At the same time, our load-balanced approach retains strong performance at smaller scales, outperforming optimized multicore implementations under similar power budgets—all using a single, unified implementation.