{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,23]],"date-time":"2026-04-23T06:25:07Z","timestamp":1776925507283,"version":"3.51.2"},"reference-count":42,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2011,9,1]],"date-time":"2011-09-01T00:00:00Z","timestamp":1314835200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Auton. Adapt. Syst."],"published-print":{"date-parts":[[2011,9]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.1145\/2019583.2019584","type":"journal-article","created":{"date-parts":[[2011,9,27]],"date-time":"2011-09-27T14:02:19Z","timestamp":1317132139000},"page":"1-20","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":15,"title":["Spatial hardware implementation for sparse graph algorithms in GraphStep"],"prefix":"10.1145","volume":"6","author":[{"given":"Michael","family":"Delorimier","sequence":"first","affiliation":[{"name":"University of Pennsylvania, Philadelphia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nachiket","family":"Kapre","sequence":"additional","affiliation":[{"name":"University of Pennsylvania, Philadelphia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nikil","family":"Mehta","sequence":"additional","affiliation":[{"name":"University of Pennsylvania, Philadelphia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andr\u00e9","family":"Dehon","sequence":"additional","affiliation":[{"name":"University of Pennsylvania, Philadelphia"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2011,9,29]]},"reference":[{"key":"e_1_2_2_1_1","volume-title":"ACTORS: A model of Concurrent Computation in Distributed Systems","author":"Agha G.","year":"1998","unstructured":"Agha , G. 1998 . ACTORS: A model of Concurrent Computation in Distributed Systems . MIT Press , Cambridge, MA . Agha, G. 1998. ACTORS: A model of Concurrent Computation in Distributed Systems. MIT Press, Cambridge, MA."},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/155332.155343"},{"key":"e_1_2_2_3_1","volume-title":"Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. 648--655","author":"Boykov Y.","unstructured":"Boykov , Y. , Veksler , O. , and Zabih , R . 1998. Markov random fields with efficient approximations . In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. 648--655 . Boykov, Y., Veksler, O., and Zabih, R. 1998. Markov random fields with efficient approximations. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. 648--655."},{"key":"e_1_2_2_4_1","unstructured":"Brook Project. 2004. Brook project web page. http:\/\/brook.sourceforge.net.  Brook Project. 2004. Brook project web page. http:\/\/brook.sourceforge.net."},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/368434.368864"},{"key":"e_1_2_2_6_1","series-title":"Lecture Notes in Computer Science","volume-title":"Proceedings of the International Conference on Field-Programmable Logic and Applications","author":"Caspi E.","unstructured":"Caspi , E. , Chu , M. , Huang , R. , Weaver , N. , Yeh , J. , Wawrzynek , J. , and DeHon , A. 2000. Stream computations organized for reconfigurable execution (SCORE): Extended abstract . In Proceedings of the International Conference on Field-Programmable Logic and Applications . Lecture Notes in Computer Science . Springer , 605--614. Caspi, E., Chu, M., Huang, R., Weaver, N., Yeh, J., Wawrzynek, J., and DeHon, A. 2000. Stream computations organized for reconfigurable execution (SCORE): Extended abstract. In Proceedings of the International Conference on Field-Programmable Logic and Applications. Lecture Notes in Computer Science. Springer, 605--614."},{"key":"e_1_2_2_7_1","volume-title":"Proceedings of the Parallel and Distributed Processing Symposium. IEEE, 823--832","author":"Castanos J.","unstructured":"Castanos , J. and Savage , J . 2000. Repartitioning unstructured adaptive meshes . In Proceedings of the Parallel and Distributed Processing Symposium. IEEE, 823--832 . Castanos, J. and Savage, J. 2000. Repartitioning unstructured adaptive meshes. In Proceedings of the Parallel and Distributed Processing Symposium. IEEE, 823--832."},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/358690.358717"},{"key":"e_1_2_2_9_1","unstructured":"Cormen T. Leiserson C. and Rivest R. 1990. Introduction to Algorithms. MIT Press Cambridge MA.   Cormen T. Leiserson C. and Rivest R. 1990. Introduction to Algorithms. MIT Press Cambridge MA."},{"key":"e_1_2_2_10_1","volume-title":"Proceedings of the Symposium on Operating System Design and Implementation. 137--150","author":"Dean J.","unstructured":"Dean , J. and Ghemawat , S . 2004. MapReduce: Simplified data processing on large clusters . In Proceedings of the Symposium on Operating System Design and Implementation. 137--150 . Dean, J. and Ghemawat, S. 2004. MapReduce: Simplified data processing on large clusters. In Proceedings of the Symposium on Operating System Design and Implementation. 137--150."},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/341800.341824"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.micpro.2006.02.003"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1046192.1046203"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/FCCM.2006.45"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.7551\/mitpress\/4917.001.0001"},{"key":"e_1_2_2_16_1","first-page":"21","article-title":"The earth simulator system","volume":"44","author":"Habata S.","year":"2003","unstructured":"Habata , S. , Yokokawa , M. , and Kitawaki , S. 2003 . The earth simulator system . NEC Res. & Develop. 44 , 1, 21 -- 26 . Habata, S., Yokokawa, M., and Kitawaki, S. 2003. The earth simulator system. NEC Res. & Develop. 44, 1, 21--26.","journal-title":"NEC Res. & Develop."},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.6028\/jres.049.044"},{"key":"e_1_2_2_18_1","volume-title":"The Connection Machine","author":"Hillis W. D.","unstructured":"Hillis , W. D. 1985. The Connection Machine . MIT Press , Cambridge, MA . Hillis, W. D. 1985. The Connection Machine. MIT Press, Cambridge, MA."},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/7902.7903"},{"key":"e_1_2_2_20_1","volume-title":"Proceedings of the IFIP CONGRESS 74","author":"Kahn G.","year":"1974","unstructured":"Kahn , G. 1974 . The semantics of a simple language for parallel programming . In Proceedings of the IFIP CONGRESS 74 . North-Holland Publishing Company, 471--475. Kahn, G. 1974. The semantics of a simple language for parallel programming. In Proceedings of the IFIP CONGRESS 74. North-Holland Publishing Company, 471--475."},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/FPT.2009.5377665"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/FCCM.2006.55"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827595287997"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/512927.512945"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/69.243507"},{"key":"e_1_2_2_26_1","doi-asserted-by":"crossref","unstructured":"Koelbel C. H. Loveman D. B. Schreiber R. S. Guy L. Steele J. and Zosel M. E. 1994. The High Performance Fortran Handbook. MIT Press Cambridge MA.   Koelbel C. H. Loveman D. B. Schreiber R. S. Guy L. Steele J. and Zosel M. E. 1994. The High Performance Fortran Handbook. MIT Press Cambridge MA.","DOI":"10.7551\/mitpress\/3499.001.0001"},{"key":"e_1_2_2_27_1","volume-title":"Proceedings of the IEEE International Conference on Computer Vision.","volume":"2","author":"Kolmogorov V.","unstructured":"Kolmogorov , V. and Zabih , R . 2001. Computing visual correspondence with occlusions using graph cuts . In Proceedings of the IEEE International Conference on Computer Vision. Vol. 2 . 508--515. Kolmogorov, V. and Zabih, R. 2001. Computing visual correspondence with occlusions using graph cuts. In Proceedings of the IEEE International Conference on Computer Vision. Vol. 2. 508--515."},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/T-C.1971.223159"},{"key":"e_1_2_2_29_1","unstructured":"Lee E. 2005. UC Berkley ptolemy project. http:\/\/www.ptolemy.eecs.berkeley.edu\/.  Lee E. 2005. UC Berkley ptolemy project. http:\/\/www.ptolemy.eecs.berkeley.edu\/."},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/PROC.1987.13876"},{"key":"e_1_2_2_31_1","volume-title":"Proceedings of the 3rd Caltech Conference On VLSI.","author":"Leiserson C.","unstructured":"Leiserson , C. , Rose , F. , and Saxe , J . 1983. Optimizing synchronous circuitry by retiming . In Proceedings of the 3rd Caltech Conference On VLSI. Leiserson, C., Rose, F., and Saxe, J. 1983. Optimizing synchronous circuitry by retiming. In Proceedings of the 3rd Caltech Conference On VLSI."},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.5555\/4492.4495"},{"key":"e_1_2_2_33_1","volume-title":"Concurrent Object-Oriented Programming in Act 1","author":"Lieberman H.","unstructured":"Lieberman , H. 1987. Concurrent Object-Oriented Programming in Act 1 . MIT Press , Cambridge, MA . Lieberman, H. 1987. Concurrent Object-Oriented Programming in Act 1. MIT Press, Cambridge, MA."},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/MM.2008.31"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1023\/B:BTTJ.0000047600.45421.6d"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/368273.368557"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/12.769433"},{"key":"e_1_2_2_38_1","unstructured":"Microsystems S. 1995. The java language environment. White paper. http:\/\/java.sun.com\/docs\/white\/langenv\/.  Microsystems S. 1995. The java language environment. White paper. http:\/\/java.sun.com\/docs\/white\/langenv\/."},{"key":"e_1_2_2_39_1","volume-title":"Types and Programming Languages","author":"Pierce B. C.","unstructured":"Pierce , B. C. 2002. Types and Programming Languages . MIT Press , Cambridge, MA . Pierce, B. C. 2002. Types and Programming Languages. MIT Press, Cambridge, MA."},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/MM.2004.53"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/79173.79181"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/611817.611824"}],"container-title":["ACM Transactions on Autonomous and Adaptive Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2019583.2019584","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2019583.2019584","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T09:48:27Z","timestamp":1750240107000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2019583.2019584"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,9]]},"references-count":42,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2011,9]]}},"alternative-id":["10.1145\/2019583.2019584"],"URL":"https:\/\/doi.org\/10.1145\/2019583.2019584","relation":{},"ISSN":["1556-4665","1556-4703"],"issn-type":[{"value":"1556-4665","type":"print"},{"value":"1556-4703","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,9]]},"assertion":[{"value":"2009-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-09-29","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}