{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:29:23Z","timestamp":1750307363388,"version":"3.41.0"},"reference-count":38,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2008,10,5]],"date-time":"2008-10-05T00:00:00Z","timestamp":1223164800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["6.10E+23"],"award-info":[{"award-number":["6.10E+23"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Archit. Code Optim."],"published-print":{"date-parts":[[2010,9]]},"abstract":"<jats:p>Memory accesses limit the performance of stream processors. By exploiting the reuse of data held in the Stream Register File (SRF), an on-chip, software controlled storage, the number of memory accesses can be reduced. In current stream compilers, reuse exploitation is only attempted for simple stream references, those whose start and end are known. Compiler analysis, from outside of stream processors, does not directly enable the consideration of other more complex stream references. In this article, we propose a transformation to automatically optimize stream programs to exploit the reuse supplied by loop-dependent stream references. The transformation is based on three results: lemmas identifying the reuse supplied by stream references, a new abstract representation called the Stream Reuse Graph (SRG) depicting the identified reuse, and the optimization of the SRG for our transformation. Both the reuse between the whole sequences accessed by stream references and between partial sequences is exploited in the article. In particular, partial reuse and its treatment are quite new and have never, to the best of our knowledge, appeared in scalar and vector processing. At the same time, reusing streams increases the pressure on the SRF, and this presents a problem of which reuse should be exploited within limited SRF capacity. We extend our analysis to achieve this objective. Finally, we implement our techniques based on the StreamC\/KernelC compiler that has been optimized with the best existing compilation techniques for stream processors. Experimental results show a resultant speed-up of 1.14 to 2.54 times using a range of benchmarks.<\/jats:p>","DOI":"10.1145\/1839667.1839673","type":"journal-article","created":{"date-parts":[[2010,10,5]],"date-time":"2010-10-05T14:38:15Z","timestamp":1286289495000},"page":"1-35","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Exploiting the reuse supplied by loop-dependent stream references for stream processors"],"prefix":"10.1145","volume":"7","author":[{"given":"Xuejun","family":"Yang","sequence":"first","affiliation":[{"name":"National University of Defense Technology, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ying","family":"Zhang","sequence":"additional","affiliation":[{"name":"National University of Defense Technology, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xicheng","family":"Lu","sequence":"additional","affiliation":[{"name":"National University of Defense Technology, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jingling","family":"Xue","sequence":"additional","affiliation":[{"name":"The University of New South Wales, Sydeny, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ian","family":"Rogers","sequence":"additional","affiliation":[{"name":"The University of Manchester, Manchester, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gen","family":"Li","sequence":"additional","affiliation":[{"name":"National University of Defense Technology, Changsha, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Guibin","family":"Wang","sequence":"additional","affiliation":[{"name":"National University of Defense Technology, Changsha, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xudong","family":"Fang","sequence":"additional","affiliation":[{"name":"National University of Defense Technology, Changsha, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2008,10,5]]},"reference":[{"doi-asserted-by":"publisher","key":"e_1_2_1_1_1","DOI":"10.1145\/339647.339691"},{"doi-asserted-by":"publisher","key":"e_1_2_1_2_1","DOI":"10.1145\/1188455.1188540"},{"doi-asserted-by":"publisher","key":"e_1_2_1_4_1","DOI":"10.1109\/12.166606"},{"unstructured":"}}AMD Inc. AMD FireStream stream processor.  }}AMD Inc. AMD FireStream stream processor.","key":"e_1_2_1_5_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_6_1","DOI":"10.1145\/1015706.1015800"},{"doi-asserted-by":"publisher","key":"e_1_2_1_7_1","DOI":"10.1145\/93542.93553"},{"doi-asserted-by":"publisher","key":"e_1_2_1_8_1","DOI":"10.1002\/spe.4380240104"},{"doi-asserted-by":"publisher","key":"e_1_2_1_9_1","DOI":"10.1137\/0915023"},{"doi-asserted-by":"publisher","key":"e_1_2_1_11_1","DOI":"10.1145\/115372.115320"},{"doi-asserted-by":"publisher","key":"e_1_2_1_12_1","DOI":"10.1145\/1048935.1050187"},{"doi-asserted-by":"publisher","key":"e_1_2_1_13_1","DOI":"10.1145\/1152154.1152164"},{"doi-asserted-by":"publisher","key":"e_1_2_1_14_1","DOI":"10.1016\/0743-7315(88)90014-7"},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the Solid-State Circuits Conference","author":"Horowitz M.","year":"2004","unstructured":"}} Horowitz , M. and Dally , W . 2004. How scaling will change processor architecture . In Proceedings of the Solid-State Circuits Conference , 2004 . IEEE, Los Alamitos, CA, 132--133. }}Horowitz, M. and Dally, W. 2004. How scaling will change processor architecture. In Proceedings of the Solid-State Circuits Conference, 2004. IEEE, Los Alamitos, CA, 132--133."},{"doi-asserted-by":"publisher","key":"e_1_2_1_17_1","DOI":"10.1109\/HPCA.2004.10007"},{"doi-asserted-by":"publisher","key":"e_1_2_1_18_1","DOI":"10.5555\/1148882.1148891"},{"volume-title":"Proceedings of the International Conference on Computer Design. IEEE","author":"Kapasi U. J.","unstructured":"}} Kapasi , U. J. , Dally , W. J. , Rixner , S. , Owens , J. D. , and Khailany , B . 2002. The Imagine stream processor . In Proceedings of the International Conference on Computer Design. IEEE , Los Alamitos, CA, 282--288. }}Kapasi, U. J., Dally, W. J., Rixner, S., Owens, J. D., and Khailany, B. 2002. The Imagine stream processor. In Proceedings of the International Conference on Computer Design. IEEE, Los Alamitos, CA, 282--288.","key":"e_1_2_1_19_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_20_1","DOI":"10.1109\/MC.2003.1220582"},{"doi-asserted-by":"publisher","key":"e_1_2_1_21_1","DOI":"10.5555\/1025127.1026015"},{"doi-asserted-by":"publisher","key":"e_1_2_1_22_1","DOI":"10.1109\/CGO.2006.13"},{"doi-asserted-by":"publisher","key":"e_1_2_1_23_1","DOI":"10.1109\/MM.2008.31"},{"doi-asserted-by":"publisher","key":"e_1_2_1_24_1","DOI":"10.1145\/277650.277659"},{"doi-asserted-by":"publisher","key":"e_1_2_1_25_1","DOI":"10.1145\/258915.258943"},{"unstructured":"}}Mattson P. Rixner S. Dally W. J. Khailany B. Ahn J. H. Mattson P. and Owens J. D. 2004. Imagine Programming System Developer's Guide. http:\/\/cva.stanford.edu.  }}Mattson P. Rixner S. Dally W. J. Khailany B. Ahn J. H. Mattson P. and Owens J. D. 2004. Imagine Programming System Developer's Guide. http:\/\/cva.stanford.edu.","key":"e_1_2_1_27_1"},{"doi-asserted-by":"crossref","unstructured":"}}Narayanan M. Oliker L. Janin A. Husbands P. Ye X. and Li S. 2002. Scientific kernels on VIRAM and Imagine media processors. Lawrence Berkeley National Laboratory. http:\/\/escholarship.org\/uc\/item\/37v9j259#page-1  }}Narayanan M. Oliker L. Janin A. Husbands P. Ye X. and Li S. 2002. Scientific kernels on VIRAM and Imagine media processors. Lawrence Berkeley National Laboratory. http:\/\/escholarship.org\/uc\/item\/37v9j259#page-1","key":"e_1_2_1_28_1","DOI":"10.2172\/860303"},{"volume-title":"Proceedings of the International Conference on Computer Design. IEEE","author":"Owens J. D.","unstructured":"}} Owens , J. D. , Kapasi , U. J. , Mattson , P. , Towles , B. , Serebrin , B. , Rixner , S. , and Dally , W. J . 2002. Media processing applications on the Imagine stream processor . In Proceedings of the International Conference on Computer Design. IEEE , Los Alamitos, CA, 295--302. }}Owens, J. D., Kapasi, U. J., Mattson, P., Towles, B., Serebrin, B., Rixner, S., and Dally, W. J. 2002. Media processing applications on the Imagine stream processor. In Proceedings of the International Conference on Computer Design. IEEE, Los Alamitos, CA, 295--302.","key":"e_1_2_1_29_1"},{"volume-title":"Stream Processor Architecture","author":"Rixner S.","unstructured":"}} Rixner , S. 2002. Stream Processor Architecture . Kluwer Academic Publishers , The Netherlands . }}Rixner, S. 2002. Stream Processor Architecture. Kluwer Academic Publishers, The Netherlands.","key":"e_1_2_1_30_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_31_1","DOI":"10.1145\/277650.277656"},{"doi-asserted-by":"publisher","key":"e_1_2_1_32_1","DOI":"10.1145\/1360612.1360617"},{"doi-asserted-by":"publisher","key":"e_1_2_1_33_1","DOI":"10.1007\/s002360050095"},{"unstructured":"}}Tahoori M. and Lee P. Mapping vector codes to stream processor Imagine. http:\/\/webcache.googleusercontent.com\/search?q=cache:0d4wHF102bUJ:citeseerx.ist.psu.edu\/viewdoc\/download?doi%3D10.1.1.112.7965%26rep%3Drep1%26type%3Dpdf+TAHOORI +M.+ AND+LEE +P.+Mapping+vector+codes+to+stream+processor+Imagine.&hl=en&gl=us.  }}Tahoori M. and Lee P. Mapping vector codes to stream processor Imagine. http:\/\/webcache.googleusercontent.com\/search?q=cache:0d4wHF102bUJ:citeseerx.ist.psu.edu\/viewdoc\/download?doi%3D10.1.1.112.7965%26rep%3Drep1%26type%3Dpdf+TAHOORI +M.+ AND+LEE +P.+Mapping+vector+codes+to+stream+processor+Imagine.&hl=en&gl=us.","key":"e_1_2_1_34_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_35_1","DOI":"10.1109\/MM.2002.997877"},{"unstructured":"}}West D. 2001.Introduction to Graph Theory. Prentice Hall Upper Saddle River NJ.  }}West D. 2001.Introduction to Graph Theory. Prentice Hall Upper Saddle River NJ.","key":"e_1_2_1_36_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_37_1","DOI":"10.1145\/113445.113449"},{"doi-asserted-by":"publisher","key":"e_1_2_1_38_1","DOI":"10.1145\/216585.216588"},{"volume-title":"Proceedings of the 10th Workshop on Languages and Compilers for Parallel Computing. Springer","author":"Xue J.","unstructured":"}} Xue , J. and Huang , C . -H. 1997. Reuse-driven tiling for data locality . In Proceedings of the 10th Workshop on Languages and Compilers for Parallel Computing. Springer , Berlin, 16--33. }}Xue, J. and Huang, C.-H. 1997. Reuse-driven tiling for data locality. In Proceedings of the 10th Workshop on Languages and Compilers for Parallel Computing. Springer, Berlin, 16--33.","key":"e_1_2_1_39_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_40_1","DOI":"10.1145\/1454115.1454121"},{"doi-asserted-by":"publisher","key":"e_1_2_1_41_1","DOI":"10.1145\/1273440.1250689"},{"doi-asserted-by":"publisher","key":"e_1_2_1_42_1","DOI":"10.1109\/ISPASS.2008.4510743"}],"container-title":["ACM Transactions on Architecture and Code Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1839667.1839673","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1839667.1839673","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T11:22:36Z","timestamp":1750245756000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1839667.1839673"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,10,5]]},"references-count":38,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2010,9]]}},"alternative-id":["10.1145\/1839667.1839673"],"URL":"https:\/\/doi.org\/10.1145\/1839667.1839673","relation":{},"ISSN":["1544-3566","1544-3973"],"issn-type":[{"type":"print","value":"1544-3566"},{"type":"electronic","value":"1544-3973"}],"subject":[],"published":{"date-parts":[[2008,10,5]]},"assertion":[{"value":"2009-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-10-05","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}