CyGraph: A Reconfigurable Architecture for Parallel Breadth-First Search

被引：39

作者：

Attia, Osama G. ^{[1
]}

Johnson, Tyler ^{[1
]}

Townsend, Kevin ^{[1
]}

Jones, Philip ^{[1
]}

Zambreno, Joseph ^{[1
]}

机构：

[1] Iowa State Univ, Dept Elect & Comp Engn, Ames, IA 50011 USA

来源：

PROCEEDINGS OF 2014 IEEE INTERNATIONAL PARALLEL & DISTRIBUTED PROCESSING SYMPOSIUM WORKSHOPS (IPDPSW) | 2014年

基金：

美国国家科学基金会;

关键词：

Reconfigurable Computing; Breadth-First Search; Graphs; FPGA; Convey HC-2;

D O I：

10.1109/IPDPSW.2014.30

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Large-scale graph structures are considered as a keystone for many emerging high-performance computing applications in which Breadth-First Search (BFS) is an important building block. For such graph structures, BFS operations tends to be memory-bound rather than compute-bound. In this paper, we present an efficient reconfigurable architecture for parallel BFS that adopts new optimizations for utilizing memory bandwidth. Our architecture adopts a custom graph representation based on compressed-sparse raw format (CSR), as well as a restructuring of the conventional BFS algorithm. By taking maximum advantage of available memory bandwidth, our architecture continuously keeps our processing elements active. Using a commercial high-performance reconfigurable computing system (the Convey HC-2), our results demonstrate a 5x speedup over previously published FPGA-based implementations.

引用

页码：228 / 235

页数：8

共 23 条

[1]

Agarwal Virat, 2010, P INT C HIGH PERF CO

[2]

[Anonymous], 2010, INTRO GRAPH 500

[3]

[Anonymous], UCBEECS20132

[4]

Augustin Werner, 2011, P INT WORKSH NEW FRO

[5] HIGH-PERFORMANCE HETEROGENEOUS COMPUTING WITH THE CONVEY HC-1 [J].

Bakos, Jason D. .

COMPUTING IN SCIENCE & ENGINEERING, 2010, 12 (06) :80-87

[6]

Betkaoui B., 2012, 2012 22nd International Conference on Field Programmable Logic and Applications (FPL), P99, DOI 10.1109/FPL.2012.6339247

[7]

Betkaoui B, 2012, IEEE INT CONF ASAP, P8, DOI 10.1109/ASAP.2012.30

[8] INSTRUCTION SET INNOVATIONS FOR THE CONVEY HC-1 COMPUTER [J].

Brewer, Tony M. .

IEEE MICRO, 2010, 30 (02) :70-79

[9]

Checconi F., 2012, P INT C HIGH PERF CO

[10]

Gjoka M., 2010, P IEEE INT C COMP CO

← 1 2 3 →