{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,10]],"date-time":"2026-01-10T18:44:57Z","timestamp":1768070697308,"version":"3.49.0"},"reference-count":23,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2007,9,1]],"date-time":"2007-09-01T00:00:00Z","timestamp":1188604800000},"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. Archit. Code Optim."],"published-print":{"date-parts":[[2007,9]]},"abstract":"<jats:p>The performance of memory hierarchies, in which caches play an essential role, is critical in nowadays general-purpose and embedded computing systems because of the growing memory bottleneck problem. Unfortunately, cache behavior is very unstable and difficult to predict. This is particularly true in the presence of irregular access patterns, which exhibit little locality. Such patterns are very common, for example, in applications in which pointers or compressed sparse matrices give place to indirections. Nevertheless, cache behavior in the presence of irregular access patterns has not been widely studied. In this paper we present an extension of a systematic analytical modeling technique based on PMEs (probabilistic miss equations), previously developed by the authors, that allows the automated analysis of the cache behavior for codes with irregular access patterns resulting from indirections. The model generates very accurate predictions despite the irregularities and has very low computing requirements, being the first model that gathers these desirable characteristics that can automatically analyze this kind of codes. These properties enable this model to help drive compiler optimizations, as we show with an example.<\/jats:p>","DOI":"10.1145\/1275937.1275940","type":"journal-article","created":{"date-parts":[[2007,9,14]],"date-time":"2007-09-14T13:44:55Z","timestamp":1189777495000},"page":"16","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":11,"title":["Precise automatable analytical modeling of the cache behavior of codes with indirections"],"prefix":"10.1145","volume":"4","author":[{"given":"Diego","family":"Andrade","sequence":"first","affiliation":[{"name":"Universidade da Coru\u00f1a, Coru\u00f1a, Spain"}]},{"given":"Basilio B.","family":"Fraguela","sequence":"additional","affiliation":[{"name":"Universidade da Coru\u00f1a, Coru\u00f1a, Spain"}]},{"given":"Ram\u00f3n","family":"Doallo","sequence":"additional","affiliation":[{"name":"Universidade da Coru\u00f1a, Coru\u00f1a, Spain"}]}],"member":"320","published-online":{"date-parts":[[2007,9]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/258915.258924"},{"key":"e_1_2_1_2_1","volume-title":"Proc. 19th Int'l Workshop on Languages and Compilers for Parallel Computing (LCPC'06)","volume":"4382","author":"Andrade D."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.sysarc.2005.04.004"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/782814.782842"},{"key":"e_1_2_1_5_1","unstructured":"Bai Z. Day D. Demmel J. and Dongarra J. 1996. A test matrix collection for non-Hermitian eigenvalue problems release 1.0.  Bai Z. Day D. Demmel J. and Dongarra J. 1996. A test matrix collection for non-Hermitian eigenvalue problems release 1.0."},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","unstructured":"Barrett R. Berry M. Chan T. F. Demmel J. Donato J. M. Dongarra J. Eijkhout V. Pozo R. Romine C. and der Vorst H. V. 1994. Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods. Philadalphia: Society for Industrial and Applied Mathematics. Also available as postscript file on http:\/\/www.netlib.orgtemplatesTemplates.html.  Barrett R. Berry M. Chan T. F. Demmel J. Donato J. M. Dongarra J. Eijkhout V. Pozo R. Romine C. and der Vorst H. V. 1994. Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods. Philadalphia: Society for Industrial and Applied Mathematics. Also available as postscript file on http:\/\/www.netlib.orgtemplatesTemplates.html.","DOI":"10.1137\/1.9781611971538"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/2.546612"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/645677.663790"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/378795.378859"},{"key":"e_1_2_1_11_1","volume-title":"Tech. Rep. CERFACS TR-PA-92-96. Oct.","author":"Duff I. S.","year":"1992"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/277851.277910"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2003.1183947"},{"key":"e_1_2_1_14_1","unstructured":"Fraguela B. B. Carmueja M. G. and Andrade D. 2005. Optimal tile size selection guided by analytical models. In Procs. of Parallel Computing 2005 (ParCo 2005). Malaga Spain. 565--572.  Fraguela B. B. Carmueja M. G. and Andrade D. 2005. Optimal tile size selection guided by analytical models. In Procs. of Parallel Computing 2005 (ParCo 2005). Malaga Spain. 565--572."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/325478.325479"},{"key":"e_1_2_1_16_1","volume-title":"SODA '99: Proc. of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics","author":"Ladner R. E.","year":"1999"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/106972.106981"},{"key":"e_1_2_1_18_1","volume-title":"ICCS '01: Proc. of the Int'l. Conf. on Computational Sciences-Part I. Lecture Notes in Computer Science","volume":"2073","author":"Mitchell N."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/183018.183047"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/254180.254184"},{"key":"e_1_2_1_21_1","volume-title":"Proc. of the 8th Int'l Symposium on High-Performance Computer Architecture (HPCA 8). IEEE","author":"Vera X."},{"key":"e_1_2_1_22_1","volume-title":"Proc. 12th Intl. Conf. on Parallel Architectures and Compilation Techniques (PACT'03)","author":"Vera X."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/11596110_22"},{"key":"e_1_2_1_24_1","volume-title":"Proc. of the 12th Intl Conf. on Parallel Architectures and Compilation Techniques (PACT'03)","author":"Zhong Y."}],"container-title":["ACM Transactions on Architecture and Code Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1275937.1275940","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1275937.1275940","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T14:58:00Z","timestamp":1750258680000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1275937.1275940"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,9]]},"references-count":23,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2007,9]]}},"alternative-id":["10.1145\/1275937.1275940"],"URL":"https:\/\/doi.org\/10.1145\/1275937.1275940","relation":{},"ISSN":["1544-3566","1544-3973"],"issn-type":[{"value":"1544-3566","type":"print"},{"value":"1544-3973","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,9]]},"assertion":[{"value":"2007-09-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}