NDLI: CyGraph: A Reconfigurable Architecture for Parallel Breadth-First Search

Content Provider	IEEE Xplore Digital Library
Author	Attia, O.G. Johnson, T. Townsend, K. Jones, P. Zambreno, J.
Copyright Year	2014
Description	Author affiliation: Dept. Electr. & Comput. Eng., Iowa State Univ., Ames, IA, USA (Attia, O.G.; Johnson, T.; Townsend, K.; Jones, P.; Zambreno, J.)
Abstract	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 5× speedup over previously published FPGA-based implementations.
Starting Page	228
Ending Page	235
File Size	267409
Page Count	8
File Format	PDF
e-ISBN	9781479941162
DOI	10.1109/IPDPSW.2014.30
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2014-05-19
Publisher Place	USA
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Algorithm design and analysis Convey HC-2 FPGA Bandwidth Breadth-First Search Graphs Reconfigurable Computing Arrays Indexes Kernel Optimization
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Accelerating all-pairs shortest path using a message-passing reconfigurable architecture

A Reconfigurable Architecture for the Detection of Strongly Connected Components (TRETS, Vol.9, Issue 2)

A Reconfigurable Computing Approach for Efficient and Scalable Parallel Graph Exploration

Analysis of a Dynamically Reconfigurable Dataflow Architecture and its Scalable Parallel Extension for Multi-FPGA Platforms

A message-passing multi-softcore architecture on FPGA for Breadth-first Search

Hybrid breadth-first search on a single-chip FPGA-CPU heterogeneous platform

A reconfigurable computing approach for efficient and scalable parallel graph exploration.

Solving Sudoku in reconfigurable hardware

A breadth first search approach for minimum vertex cover of grid graphs

CyGraph: A Reconfigurable Architecture for Parallel Breadth-First Search

Similar Documents

Accelerating all-pairs shortest path using a message-passing reconfigurable architecture

A Reconfigurable Architecture for the Detection of Strongly Connected Components (TRETS, Vol.9, Issue 2)

A Reconfigurable Computing Approach for Efficient and Scalable Parallel Graph Exploration

Analysis of a Dynamically Reconfigurable Dataflow Architecture and its Scalable Parallel Extension for Multi-FPGA Platforms

A message-passing multi-softcore architecture on FPGA for Breadth-first Search

Hybrid breadth-first search on a single-chip FPGA-CPU heterogeneous platform

A reconfigurable computing approach for efficient and scalable parallel graph exploration.

Solving Sudoku in reconfigurable hardware

A breadth first search approach for minimum vertex cover of grid graphs

CyGraph: A Reconfigurable Architecture for Parallel Breadth-First Search