Please use this identifier to cite or link to this item: https://hdl.handle.net/10356/81195
Title: Spatial hardware implementation for sparse graph algorithms in GraphStep
Authors: Delorimier, Michael
Kapre, Nachiket
Mehta, Nikil
Dehon, André
Keywords: Languages
Spatial computing
Compute model
Algorithms
Performance
Parallel programming
Graph algorithm
graphStep
Issue Date: 2011
Source: Delorimier, M., Kapre, N., Mehta, N., & Dehon, A. (2011). Spatial hardware implementation for sparse graph algorithms in GraphStep. ACM Transactions on Autonomous and Adaptive Systems, 6(3), 1-20.
Series/Report no.: ACM Transactions on Autonomous and Adaptive Systems
Abstract: How do we develop programs that are easy to express, easy to reason about, and able to achieve high performance on massively parallel machines? To address this problem, we introduce GraphStep, a domain-specific compute model that captures algorithms that act on static, irregular, sparse graphs. In GraphStep, algorithms are expressed directly without requiring the programmer to explicitly manage parallel synchronization, operation ordering, placement, or scheduling details. Problems in the sparse graph domain are usually highly concurrent and communicate along graph edges. Exposing concurrency and communication structure allows scheduling of parallel operations and management of communication that is necessary for performance on a spatial computer. We study the performance of a semantic network application, a shortest-path application, and a max-flow/min-cut application. We introduce a language syntax for GraphStep applications. The total speedup over sequential versions of the applications studied ranges from a factor of 19 to a factor of 15,000. Spatially-aware graph optimizations (e.g., node decomposition, placement and route scheduling) delivered speedups from 3 to 30 times over a spatially-oblivious mapping.
URI: https://hdl.handle.net/10356/81195
http://hdl.handle.net/10220/39184
ISSN: 1556-4665
DOI: 10.1145/2019583.2019584
Schools: School of Computer Engineering 
Rights: © 2011 Association for Computing Machinery (ACM).
Fulltext Permission: none
Fulltext Availability: No Fulltext
Appears in Collections:SCSE Journal Articles

SCOPUSTM   
Citations 20

16
Updated on Mar 22, 2024

Web of ScienceTM
Citations 20

15
Updated on Oct 24, 2023

Page view(s) 50

445
Updated on Mar 28, 2024

Google ScholarTM

Check

Altmetric


Plumx

Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.