dc.contributor.authorDelorimier, Michael
dc.contributor.authorKapre, Nachiket
dc.contributor.authorMehta, Nikil
dc.contributor.authorDehon, André
dc.identifier.citationDelorimier, 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.en_US
dc.description.abstractHow 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.en_US
dc.format.extent20 p.en_US
dc.relation.ispartofseriesACM Transactions on Autonomous and Adaptive Systems*
dc.rights© 2011 Association for Computing Machinery (ACM).en_US
dc.subjectSpatial computing
dc.subjectCompute model
dc.subjectParallel programming
dc.subjectGraph algorithm
dc.titleSpatial hardware implementation for sparse graph algorithms in GraphStepen_US
dc.typeJournal Article
dc.contributor.schoolSchool of Computer Engineeringen_US

Files in this item


There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record