A Reconfigurable Architecture for the Detection of Strongly Connected Components
| Authors | Osama Attia, Kevin Townsend, Phillip Jones, and Joseph Zambreno |
|---|---|
| Type | Journal Article |
| Journal | ACM Transactions on Reconfigurable Technology and Systems (TRETS) |
| Volume | 9 |
| Date | December 2015 |
Abstract
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.
BibTeX
@article{AttTow15A,
title = {A Reconfigurable Architecture for the Detection of Strongly Connected Components},
journal = {ACM Transactions on Reconfigurable Technology and Systems (TRETS)},
volume = {9},
year = {2015},
month = dec,
author = {Attia, Osama and Townsend, Kevin and Jones, Phillip and Zambreno, Joseph}
}