{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,12,29]],"date-time":"2022-12-29T05:17:03Z","timestamp":1672291023639},"reference-count":33,"publisher":"Association for Computing Machinery (ACM)","issue":"2","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Archit. Code Optim."],"published-print":{"date-parts":[[2005,6]]},"abstract":"<jats:p>Techniques to detect aliasing between access patterns of array elements are quite effective for many numeric applications. However, although multimedia codes usually follow very regular memory access patterns, current commercial compilers remain unsuccessful in disambiguating them due mainly to complex pointer references. The Dynamic Memory Interval Test is a runtime memory disambiguation technique that takes advantage of the specific behavior of multimedia memory access patterns. It evaluates whether or not the full loop is disambiguated by analyzing the region domain of each load or store before each invocation of the loop.This paper provides a detailed evaluation of the approach, compares it against an advanced interprocedural pointer analysis framework, and analyzes the possibility of using both techniques at the same time. Both techniques achieve similar speedups separately (1.25X in average for a 8-issue width architecture). Furthermore, they can be used together to improve performance (reaching an average speed-up of 1.32X). Results also confirm that memory disambiguation is a key optimization to exploit the available parallelism in multimedia codes, especially for wide-issue architectures (1.50X average speed-up when scaling from 4- to 12-issue width in contrast to a low 1.10X for the baseline compiler).<\/jats:p>","DOI":"10.1145\/1071604.1071608","type":"journal-article","created":{"date-parts":[[2005,8,1]],"date-time":"2005-08-01T17:31:42Z","timestamp":1122917502000},"page":"199-219","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Dynamic memory interval test vs. interprocedural pointer analysis in multimedia applications"],"prefix":"10.1145","volume":"2","author":[{"given":"Esther","family":"Salam\u00ed","sequence":"first","affiliation":[{"name":"Universitat Polit\u00e8cnica de Catalunya (UPC), Barcelona, Spain"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mateo","family":"Valero","sequence":"additional","affiliation":[{"name":"Universitat Polit\u00e8cnica de Catalunya (UPC), Barcelona, Spain"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2005,6]]},"reference":[{"key":"e_1_2_2_1_1","volume-title":"Technical Report HPL-98-128, Information Technology Center.","author":"Aditya S.","year":"1998","unstructured":"Aditya , S. , Kathail , V. , and Rau , B. R . 1998 . Elcor's machine description system: Version 3.0. Technical Report HPL-98-128, Information Technology Center. Aditya, S., Kathail, V., and Rau, B. R. 1998. Elcor's machine description system: Version 3.0. Technical Report HPL-98-128, Information Technology Center."},{"key":"e_1_2_2_3_1","volume-title":"Proceedings of the 27th Annual International Symposium on Microarchitecture. 105--111","author":"Bernstein D.","year":"1927","unstructured":"Bernstein , D. , Cohen , D. , and Maydan , D. E . 1994. Dynamic memory disambiguation for array references . In Proceedings of the 27th Annual International Symposium on Microarchitecture. 105--111 . 10.1145\/ 1927 24.192737 Bernstein, D., Cohen, D., and Maydan, D. E. 1994. Dynamic memory disambiguation for array references. In Proceedings of the 27th Annual International Symposium on Microarchitecture. 105--111. 10.1145\/192724.192737"},{"key":"e_1_2_2_4_1","volume-title":"Proceedings of the 1994 Conference on Supercomputing. 528--537","author":"Blume W.","unstructured":"Blume , W. and Eigenmann , R . 1994. The range test: a dependence test for symbolic, non-linear expressions . In Proceedings of the 1994 Conference on Supercomputing. 528--537 . Blume, W. and Eigenmann, R. 1994. The range test: a dependence test for symbolic, non-linear expressions. In Proceedings of the 1994 Conference on Supercomputing. 528--537."},{"key":"e_1_2_2_5_1","volume-title":"Proceedings of the 6th International Conference on Architectural Support for Programming Languages and Operating Systems. 252--262","author":"Carr S.","year":"1954","unstructured":"Carr , S. , McKinley , K. S. , and Tseng , C . -W. 1994. Compiler optimizations for improving data locality . In Proceedings of the 6th International Conference on Architectural Support for Programming Languages and Operating Systems. 252--262 . 10.1145\/ 1954 73.195557 Carr, S., McKinley, K. S., and Tseng, C.-W. 1994. Compiler optimizations for improving data locality. In Proceedings of the 6th International Conference on Architectural Support for Programming Languages and Operating Systems. 252--262. 10.1145\/195473.195557"},{"key":"e_1_2_2_6_1","volume-title":"Proceedings of the 20th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages","author":"Choi J.-D.","unstructured":"Choi , J.-D. , Burke , M. , and Carini , P . 1993. Efficient flow-sensitive interprocedural computation of pointer-induced aliases and side effects . In Proceedings of the 20th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages ( Charleston, SC). 232--245. 10.1145\/158511.158639 Choi, J.-D., Burke, M., and Carini, P. 1993. Efficient flow-sensitive interprocedural computation of pointer-induced aliases and side effects. In Proceedings of the 20th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (Charleston, SC). 232--245. 10.1145\/158511.158639"},{"key":"e_1_2_2_7_1","volume-title":"Proceedings of the ACM SIGPLAN'94 Conference on Programming Language Design and Implementation. 242--256","author":"Emami M.","unstructured":"Emami , M. , Ghiya , R. , and Hendren , L. J . 1994. Context-sensitive interprocedural points-to analysis in the presence of function pointers . In Proceedings of the ACM SIGPLAN'94 Conference on Programming Language Design and Implementation. 242--256 . 10.1145\/178243.178264 Emami, M., Ghiya, R., and Hendren, L. J. 1994. Context-sensitive interprocedural points-to analysis in the presence of function pointers. In Proceedings of the ACM SIGPLAN'94 Conference on Programming Language Design and Implementation. 242--256. 10.1145\/178243.178264"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01407931"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/195470.195534"},{"key":"e_1_2_2_11_1","volume-title":"Proceedings of the ACM SIGPLAN'91 Conference on Programming Language Design and Implementation. 15--29","author":"Goff G.","unstructured":"Goff , G. , Kennedy , K. , and Tseng , C . 1991. Practical dependence testing . In Proceedings of the ACM SIGPLAN'91 Conference on Programming Language Design and Implementation. 15--29 . 10.1145\/113445.113448 Goff, G., Kennedy, K., and Tseng, C. 1991. Practical dependence testing. In Proceedings of the ACM SIGPLAN'91 Conference on Programming Language Design and Implementation. 15--29. 10.1145\/113445.113448"},{"key":"e_1_2_2_12_1","volume-title":"Proceedings of the 2000 ACM SIGSOFT International Symposium on Software Testing and Analysis. 113--123","author":"Hind M.","unstructured":"Hind , M. and Pioli , A . 2000. Which pointer analysis should I use? In Proceedings of the 2000 ACM SIGSOFT International Symposium on Software Testing and Analysis. 113--123 . 10.1145\/347324.348916 Hind, M. and Pioli, A. 2000. Which pointer analysis should I use? In Proceedings of the 2000 ACM SIGSOFT International Symposium on Software Testing and Analysis. 113--123. 10.1145\/347324.348916"},{"key":"e_1_2_2_13_1","volume-title":"Proceedings of the 21st International Symposium on Computer Architecture. 200--210","author":"Huang A.","year":"1919","unstructured":"Huang , A. , Slavenburg , G. , and Shen , J . 1994. Speculative disambiguation: A compilation technique for dynamic memory disambiguation . In Proceedings of the 21st International Symposium on Computer Architecture. 200--210 . 10.1145\/ 1919 95.192012 Huang, A., Slavenburg, G., and Shen, J. 1994. Speculative disambiguation: A compilation technique for dynamic memory disambiguation. In Proceedings of the 21st International Symposium on Computer Architecture. 200--210. 10.1145\/191995.192012"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01205185"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/5.476079"},{"key":"e_1_2_2_16_1","volume-title":"Technical Report HPL-93-80(R.1), Hewlett--Packard Lab.","author":"Kathail V.","year":"2000","unstructured":"Kathail , V. , Schlansker , M. , and Rau , B. R . 2000 . Hpl-pd architecture specification: Version 1.1. Technical Report HPL-93-80(R.1), Hewlett--Packard Lab. Kathail, V., Schlansker, M., and Rau, B. R. 2000. Hpl-pd architecture specification: Version 1.1. Technical Report HPL-93-80(R.1), Hewlett--Packard Lab."},{"key":"e_1_2_2_17_1","unstructured":"Lab. H. P. Group R.-I. and Group I. 1998. Trimaran user manual. http:\/\/www.trimaran.org\/docs.html.  Lab. H. P. Group R.-I. and Group I. 1998. Trimaran user manual. http:\/\/www.trimaran.org\/docs.html."},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/161494.161501"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/143103.143137"},{"key":"e_1_2_2_20_1","volume-title":"Proceedings of the 30th International Symposium on Microarchitecture. 330--335","author":"Lee C.","unstructured":"Lee , C. , Potkonjak , M. , and Mangione-Smith , W. H . 1997. Mediabench: A tool for evaluating and synthesizing multimedia and communicatons systems . In Proceedings of the 30th International Symposium on Microarchitecture. 330--335 . Lee, C., Potkonjak, M., and Mangione-Smith, W. H. 1997. Mediabench: A tool for evaluating and synthesizing multimedia and communicatons systems. In Proceedings of the 30th International Symposium on Microarchitecture. 330--335."},{"key":"e_1_2_2_21_1","volume-title":"Proceedings of the 25th International Symposium on Microarchitecture. 45--54","author":"Mahlke S. A.","unstructured":"Mahlke , S. A. , Lin , D. C. , Chen , W. Y. , Hank , R. E. , and Bringmann , R. A . 1992. Effective compiler support for predicated execution using the hyperblock . In Proceedings of the 25th International Symposium on Microarchitecture. 45--54 . Mahlke, S. A., Lin, D. C., Chen, W. Y., Hank, R. E., and Bringmann, R. A. 1992. Effective compiler support for predicated execution using the hyperblock. In Proceedings of the 25th International Symposium on Microarchitecture. 45--54."},{"key":"e_1_2_2_22_1","volume-title":"Proceedings of the ACM SIGPLAN'91 Conference on Programming Language Design and Implementation. 1--14","author":"Maydan D.","unstructured":"Maydan , D. , Hennessy , J. , and Lam , M . 1991. Efficient and exact data dependence analysis . In Proceedings of the ACM SIGPLAN'91 Conference on Programming Language Design and Implementation. 1--14 . 10.1145\/113445.113447 Maydan, D., Hennessy, J., and Lam, M. 1991. Efficient and exact data dependence analysis. In Proceedings of the ACM SIGPLAN'91 Conference on Programming Language Design and Implementation. 1--14. 10.1145\/113445.113447"},{"key":"e_1_2_2_23_1","volume-title":"Proceedings of the ACM Symposium on Principles Practice of Parallel Programming. 84--95","author":"Moon S.","unstructured":"Moon , S. and Hall , M. W . 1999. Evaluation of predicated array data-flow analysis for automatic parallelization . In Proceedings of the ACM Symposium on Principles Practice of Parallel Programming. 84--95 . 10.1145\/301104.301112 Moon, S. and Hall, M. W. 1999. Evaluation of predicated array data-flow analysis for automatic parallelization. In Proceedings of the ACM Symposium on Principles Practice of Parallel Programming. 84--95. 10.1145\/301104.301112"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/12.24269"},{"key":"e_1_2_2_25_1","volume-title":"Proceedings of the ACM SIGPLAN'98 Conference on Programming Language Design and Implementation. 60--71","author":"Paek Y.","unstructured":"Paek , Y. , Hoeflinger , J. , and Padua , D . 1998. Simplification of array access patterns for compiler optimizations . In Proceedings of the ACM SIGPLAN'98 Conference on Programming Language Design and Implementation. 60--71 . 10.1145\/277650.277664 Paek, Y., Hoeflinger, J., and Padua, D. 1998. Simplification of array access patterns for compiler optimizations. In Proceedings of the ACM SIGPLAN'98 Conference on Programming Language Design and Implementation. 60--71. 10.1145\/277650.277664"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/291889.291900"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/186025.186041"},{"key":"e_1_2_2_29_1","volume-title":"Proceedings of the ACM International Conference on Supercomputing (Manchester, England). 10","author":"Rauchwerger L.","year":"1811","unstructured":"Rauchwerger , L. and Padua , D . 1994. The PRIVATIZING DOALL test: A run-time technique for DOALL loop identification and array privatization . In Proceedings of the ACM International Conference on Supercomputing (Manchester, England). 10 .1145\/ 1811 81.181254 Rauchwerger, L. and Padua, D. 1994. The PRIVATIZING DOALL test: A run-time technique for DOALL loop identification and array privatization. In Proceedings of the ACM International Conference on Supercomputing (Manchester, England). 10.1145\/181181.181254"},{"key":"e_1_2_2_30_1","volume-title":"Proceedings of the International Conference on Compilers, Architecture, and Synthesis for Embedded Systems. 117--126","author":"Salam\u00ed E.","unstructured":"Salam\u00ed , E. , Corbal , J. , Alvarez , C. , and Valero , M . 2002. Cost effective memory disambiguation for multimedia codes . In Proceedings of the International Conference on Compilers, Architecture, and Synthesis for Embedded Systems. 117--126 . 10.1145\/581630.581649 Salam\u00ed, E., Corbal, J., Alvarez, C., and Valero, M. 2002. Cost effective memory disambiguation for multimedia codes. In Proceedings of the International Conference on Compilers, Architecture, and Synthesis for Embedded Systems. 117--126. 10.1145\/581630.581649"},{"key":"e_1_2_2_31_1","volume-title":"Proceedings of the 1st Workshop on Media Processors and DSPs. 100--109","author":"Salam\u00ed E.","unstructured":"Salam\u00ed , E. , Corbal , J. , Espasa , R. , and Valero , M . 1999. An evaluation of different dlp alternatives for the embedded media domain . In Proceedings of the 1st Workshop on Media Processors and DSPs. 100--109 . Salam\u00ed, E., Corbal, J., Espasa, R., and Valero, M. 1999. An evaluation of different dlp alternatives for the embedded media domain. In Proceedings of the 1st Workshop on Media Processors and DSPs. 100--109."},{"key":"e_1_2_2_32_1","volume-title":"Proceedings of the ACM Symposium on Principles of Programming Languages. 1--14","author":"Shapiro M.","unstructured":"Shapiro , M. and Horwitz , S . 1997. Fast and accurate flow-insensitive points-to analysis . In Proceedings of the ACM Symposium on Principles of Programming Languages. 1--14 . 10.1145\/263699.263703 Shapiro, M. and Horwitz, S. 1997. Fast and accurate flow-insensitive points-to analysis. In Proceedings of the ACM Symposium on Principles of Programming Languages. 1--14. 10.1145\/263699.263703"},{"key":"e_1_2_2_33_1","volume-title":"Proceedings of the 23rd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. 32--41","author":"Steensgaard B.","year":"1996","unstructured":"Steensgaard , B. 1996 . Points-to analysis in almost linear time . In Proceedings of the 23rd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. 32--41 . 10.1145\/237721.237727 Steensgaard, B. 1996. Points-to analysis in almost linear time. In Proceedings of the 23rd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. 32--41. 10.1145\/237721.237727"},{"key":"e_1_2_2_34_1","volume-title":"Proceedings of the ACM SIGPLAN'95 Conference on Programming Language Design and Implementation. 1--12","author":"Wilson R. P.","year":"2071","unstructured":"Wilson , R. P. and Lam , M. S . 1995. Efficient context-sensitive pointer analysis for c programs . In Proceedings of the ACM SIGPLAN'95 Conference on Programming Language Design and Implementation. 1--12 . 10.1145\/ 2071 10.207111 Wilson, R. P. and Lam, M. S. 1995. Efficient context-sensitive pointer analysis for c programs. In Proceedings of the ACM SIGPLAN'95 Conference on Programming Language Design and Implementation. 1--12. 10.1145\/207110.207111"},{"key":"e_1_2_2_35_1","volume-title":"Proceedings of the ACM SIGPLAN'91 Conference on Programming Language Design and Implementation. 30--44","author":"Wolf M. E.","unstructured":"Wolf , M. E. and Lam , M. S . 1991. A data locality optimizing algorithm . In Proceedings of the ACM SIGPLAN'91 Conference on Programming Language Design and Implementation. 30--44 . 10.1145\/113445.113449 Wolf, M. E. and Lam, M. S. 1991. A data locality optimizing algorithm. In Proceedings of the ACM SIGPLAN'91 Conference on Programming Language Design and Implementation. 30--44. 10.1145\/113445.113449"},{"key":"e_1_2_2_36_1","volume-title":"SIGPLAN Conference on Programming Language Design and Implementation. 91--103","author":"Yong S. H.","unstructured":"Yong , S. H. , Horwitz , S. , and Reps , T. W . 1999. Pointer analysis for programs with structures and casting . In SIGPLAN Conference on Programming Language Design and Implementation. 91--103 . 10.1145\/301618.301647 Yong, S. H., Horwitz, S., and Reps, T. W. 1999. Pointer analysis for programs with structures and casting. In SIGPLAN Conference on Programming Language Design and Implementation. 91--103. 10.1145\/301618.301647"}],"container-title":["ACM Transactions on Architecture and Code Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1071604.1071608","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T13:17:38Z","timestamp":1672233458000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1071604.1071608"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,6]]},"references-count":33,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2005,6]]}},"alternative-id":["10.1145\/1071604.1071608"],"URL":"https:\/\/doi.org\/10.1145\/1071604.1071608","relation":{},"ISSN":["1544-3566","1544-3973"],"issn-type":[{"value":"1544-3566","type":"print"},{"value":"1544-3973","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,6]]},"assertion":[{"value":"2005-06-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}