TitleA Reconfigurable Architecture for the Detection of Strongly Connected Components
Publication TypeJournal Articles
2015
AuthorsO. Attia, K. Townsend, P. Jones and J. Zambreno
JournalACM Transactions on Reconfigurable Technology and Systems (TRETS)
Volume9
Issue2
Date PublishedDecember

The Strongly Connected Components (SCC) detection algorithm serves as a keystone for many graph analysis applications. The SCC execution time for large-scale graphs, as with many other graph algorithms, is dominated by memory latency. In this paper, we investigate the design of a parallel hardware architecture for the detection of SCCs in directed graphs. We propose a design methodology that alleviates memory latency and problems with irregular memory access. The design is composed of 16 processing elements dedicated to parallel Breadth-First Search (BFS) and 8 processing elements dedicated to finding intersection in parallel. Processing elements are organized to reuse resources and utilize memory bandwidth efficiently. We demonstrate a prototype of our design using the Convey HC-2 system, a commercial high-performance reconfigurable computing coprocessor. Our experimental results show a speedup of as much as 17x for detecting SCCs in large-scale graphs when compared to a conventional sequential software implementation.

Paper attachments: