{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,13]],"date-time":"2026-11-13T18:04:58Z","timestamp":1794593098742,"version":"4.9.1"},"reference-count":21,"publisher":"Association for Computing Machinery (ACM)","issue":"5s","license":[{"start":{"date-parts":[[2017,9,27]],"date-time":"2017-09-27T00:00:00Z","timestamp":1506470400000},"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. Embed. Comput. Syst."],"published-print":{"date-parts":[[2017,10,31]]},"abstract":"<jats:p>The efficiency of spatial computing depends on the ability to achieve maximal parallelism. This necessitates memory interfaces that can correctly handle memory accesses that arrive in arbitrary order while still respecting data dependencies and ensuring appropriate ordering for semantic correctness. However, a typical memory interface for out-of-order processors (i.e., a load-store queue) cannot immediately meet these requirements: a different allocation policy is needed to achieve out-of-order execution in spatial systems that naturally omit the notion of sequential program order, a fundamental piece of information for correct execution. We show a novel and practical way to organize the allocation for an out-of-order load-store queue for spatial computing. The main idea is to dynamically allocate groups of memory accesses (depending on the dynamic behavior of the application), where the access order within the group is statically predetermined (for instance by a high-level synthesis tool). We detail the construction of our load-store queue and demonstrate on a few practical cases its advantages over standard accelerator-memory interfaces.<\/jats:p>","DOI":"10.1145\/3126525","type":"journal-article","created":{"date-parts":[[2017,9,27]],"date-time":"2017-09-27T12:33:53Z","timestamp":1506515633000},"page":"1-19","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":36,"title":["An Out-of-Order Load-Store Queue for Spatial Computing"],"prefix":"10.1145","volume":"16","author":[{"given":"Lana","family":"Josipovic","sequence":"first","affiliation":[{"name":"\u00c9cole Polytechnique F\u00e9d\u00e9rale de Lausanne, Switzerland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Philip","family":"Brisk","sequence":"additional","affiliation":[{"name":"University of California, Riverside, US"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Paolo","family":"Ienne","sequence":"additional","affiliation":[{"name":"\u00c9cole Polytechnique F\u00e9d\u00e9rale de Lausanne, Switzerland"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2017,9,27]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463209.2488796"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISPASS.2005.1430572"},{"key":"e_1_2_1_3_1","volume-title":"Pegasus: An Efficient Intermediate Representation. Technical Report CMU-CS-02-107","author":"Budiu M.","year":"2002","unstructured":"M. Budiu and S. C. Goldstein . 2002 . Pegasus: An Efficient Intermediate Representation. Technical Report CMU-CS-02-107 . Carnegie Mellon University , May 2002. M. Budiu and S. C. Goldstein. 2002. Pegasus: An Efficient Intermediate Representation. Technical Report CMU-CS-02-107. Carnegie Mellon University, May 2002."},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the 1st International ACM\/IEEE Symposium on Code Generation and Optimization","author":"Budiu M.","year":"2003","unstructured":"M. Budiu and S. C. Goldstein . 2003. Optimizing memory accesses for spatial computation . In Proceedings of the 1st International ACM\/IEEE Symposium on Code Generation and Optimization . San Francisco, Calif., 216- -27, Mar. 2003 . M. Budiu and S. C. Goldstein. 2003. Optimizing memory accesses for spatial computation. In Proceedings of the 1st International ACM\/IEEE Symposium on Code Generation and Optimization. San Francisco, Calif., 216--27, Mar. 2003."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/43.945302"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2966986.2967077"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1146909.1147077"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2593069.2593143"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3020078.3021754"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2656106.2656109"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2435264.2435296"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/785168.785360"},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the International Conference on Computer Aided Design (Nov.","author":"Kam T.","year":"2008","unstructured":"T. Kam , M. Kishinevsky , J. Cortadella , and M. Galceran-Oms . 2008. Correct-by-construction microarchitectural pipelining . Proceedings of the International Conference on Computer Aided Design (Nov. 2008 ), 434--41. T. Kam, M. Kishinevsky, J. Cortadella, and M. Galceran-Oms. 2008. Correct-by-construction microarchitectural pipelining. Proceedings of the International Conference on Computer Aided Design (Nov. 2008), 434--41."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/FCCM.2015.31"},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the 36th Annual International Symposium on Microarchitecture","author":"Park I.","year":"2003","unstructured":"I. Park , C.-L. Ooi , and T. N. Vijaykumar . 2003. Reducing design complexity of the load\/store queue . In Proceedings of the 36th Annual International Symposium on Microarchitecture . San Diego, Calif., 411- -22, Dec. 2003 . I. Park, C.-L. Ooi, and T. N. Vijaykumar. 2003. Reducing design complexity of the load\/store queue. In Proceedings of the 36th Annual International Symposium on Microarchitecture. San Diego, Calif., 411--22, Dec. 2003."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2754930"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISCA.2008.10"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250662.1250705"},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the International Conference on Computer Aided Design","author":"Tan M.","year":"2015","unstructured":"M. Tan , G. Liu , R. Zhao , S. Dai , and Z. Zhang . 2015. ElasticFlow: A complexity-effective approach for pipelining irregular loop nests . In Proceedings of the International Conference on Computer Aided Design . Austin, Tex., 78- -85, Nov. 2015 . M. Tan, G. Liu, R. Zhao, S. Dai, and Z. Zhang. 2015. ElasticFlow: A complexity-effective approach for pipelining irregular loop nests. In Proceedings of the International Conference on Computer Aided Design. Austin, Tex., 78--85, Nov. 2015."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/1715759.1715781"},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the IEEE International Conference on Field Programmable Technology. Kyoto, 442--445","author":"Wong H.","year":"2013","unstructured":"H. Wong , V. Betz , and J. Rose . 2013. Efficient methods for out-of-order load\/store execution for high-performance soft processors . In Proceedings of the IEEE International Conference on Field Programmable Technology. Kyoto, 442--445 , Dec. 2013 . H. Wong, V. Betz, and J. Rose. 2013. Efficient methods for out-of-order load\/store execution for high-performance soft processors. In Proceedings of the IEEE International Conference on Field Programmable Technology. Kyoto, 442--445, Dec. 2013."}],"container-title":["ACM Transactions on Embedded Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3126525","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3126525","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T19:05:02Z","timestamp":1750273502000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3126525"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,9,27]]},"references-count":21,"journal-issue":{"issue":"5s","published-print":{"date-parts":[[2017,10,31]]}},"alternative-id":["10.1145\/3126525"],"URL":"https:\/\/doi.org\/10.1145\/3126525","relation":{},"ISSN":["1539-9087","1558-3465"],"issn-type":[{"value":"1539-9087","type":"print"},{"value":"1558-3465","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,9,27]]},"assertion":[{"value":"2017-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-09-27","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}