{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,31]],"date-time":"2026-01-31T05:50:50Z","timestamp":1769838650302,"version":"3.49.0"},"reference-count":71,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2019,8,20]],"date-time":"2019-08-20T00:00:00Z","timestamp":1566259200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CNS-1909099, CCF-1717877, CCF-1629376"],"award-info":[{"award-number":["CNS-1909099, CCF-1717877, CCF-1629376"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61328201, 61432018, 61602443"],"award-info":[{"award-number":["61328201, 61432018, 61602443"]}],"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":[[2019,9,30]]},"abstract":"<jats:p>In many areas of program and system analysis and optimization, locality is a common concept and has been defined and measured in many ways. This article aims to formally establish relations between these previously disparate types of locality. It categorizes locality definitions in three groups and shows whether and how they can be interconverted. For the footprint, a recent metric, it gives a new measurement algorithm that is asymptotically more time\/space efficient than previous approaches. Using the conversion relations, the new algorithm derives with the same efficiency different locality metrics developed and used in program analysis, memory management, and cache design.<\/jats:p>","DOI":"10.1145\/3341109","type":"journal-article","created":{"date-parts":[[2019,8,20]],"date-time":"2019-08-20T19:51:56Z","timestamp":1566330716000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":19,"title":["A Relational Theory of Locality"],"prefix":"10.1145","volume":"16","author":[{"given":"Liang","family":"Yuan","sequence":"first","affiliation":[{"name":"SKL of Computer Architecture, Institute of Computing Technology, CAS, Haidian District Beijing, China"}]},{"given":"Chen","family":"Ding","sequence":"additional","affiliation":[{"name":"University of Rochester, Rochester, NY"}]},{"given":"Wesley","family":"Smith","sequence":"additional","affiliation":[{"name":"University of Edinburgh"}]},{"given":"Peter","family":"Denning","sequence":"additional","affiliation":[{"name":"Naval Postgraduate School, Monterey, CA"}]},{"given":"Yunquan","family":"Zhang","sequence":"additional","affiliation":[{"name":"SKL of Computer Architecture, Institute of Computing Technology, CAS, Haidian District Beijing, China"}]}],"member":"320","published-online":{"date-parts":[[2019,8,20]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Ullman","author":"Aho Alfred V.","year":"2006"},{"key":"e_1_2_1_2_1","volume-title":"Optimizing Compilers for Modern Architectures: A Dependence-based Approach","author":"Allen Randy"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/HPCA.2012.6169042"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/11847366_23"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3210563.3210565"},{"key":"e_1_2_1_6_1","volume-title":"Rethinking Randomness: A New Foundation for Stochastic Modeling.","author":"Buzen Jeffrey P.","year":"2015"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3210563.3210571"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/HPCA.2005.27"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3192366.3192402"},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the International Symposium on High-Performance Computer Architecture. 329--340","author":"Chen Xi E."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/301618.301635"},{"key":"e_1_2_1_12_1","volume-title":"Denning","author":"Coffman Edward G.","year":"1973"},{"key":"e_1_2_1_13_1","volume-title":"Engineering a Compiler","author":"Cooper Keith","edition":"2"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/363095.363141"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/356733.356735"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/800213.806539"},{"key":"e_1_2_1_17_1","volume-title":"Martell","author":"Denning Peter J.","year":"2015"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/361268.361281"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/359588.359598"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2003.09.005"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11390-014-1460-7"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/359619.359634"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1944862.1944885"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISPASS.2010.5452069"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2676726.2677010"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/PACT.2005.26"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1542431.1542446"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2013.01.010"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/800076.802486"},{"key":"e_1_2_1_30_1","volume-title":"Proceedings of USENIX Annual Technical Conference. 351--364","author":"Hu Xiameng","year":"2016"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3185751"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICPP.2010.43"},{"key":"e_1_2_1_33_1","volume-title":"Wang","author":"Jacob Bruce","year":"2010"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/511334.511340"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2837614.2837669"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3297858.3304067"},{"key":"e_1_2_1_37_1","volume-title":"Proceedings of the 28th Annual International Conference on Computer Science and Software Engineering. 289--292","author":"Liu Yumeng","year":"2018"},{"key":"e_1_2_1_38_1","volume-title":"Proceedings of the International Conference on Distributed Computing. 460--474","author":"Lu Li"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/3240302.3240419"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/3018743.3018759"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/HPCA.2017.11"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/1005686.1005691"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1147\/sj.92.0078"},{"key":"e_1_2_1_44_1","volume-title":"Advanced Lectures. Lecture Notes in Computer Science","volume":"2625","author":"Meyer Ulrich"},{"key":"e_1_2_1_45_1","volume-title":"Proceedings of the International Symposium on High-Performance Computer Architecture.","author":"Nugteren Cedric"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/503272.503283"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/503272.503287"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/1854273.1854286"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/2465529.2465756"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-89740-8_14"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/1190216.1190227"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/355620.361167"},{"key":"e_1_2_1_54_1","volume-title":"Proceedings of the International Conference on Software Engineering.","author":"Smith A. J.","year":"1976"},{"key":"e_1_2_1_55_1","volume-title":"Technical Report DCS-R-2005-2564. Computer Science Deptartment","author":"Snir M.","year":"2005"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/377792.377797"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/1508244.1508259"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1109\/HPCA.2019.00056"},{"key":"e_1_2_1_59_1","volume-title":"Proceedings of the Symposium on Operating Systems Design and Implementation. USENIX Association, 335--349","author":"Wires Jake","year":"2014"},{"key":"e_1_2_1_60_1","volume-title":"High Performance Compilers for Parallel Computing","author":"Wolfe M. J."},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/2427631.2427632"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1109\/PACT.2011.58"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1145\/2485922.2485965"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1145\/1941553.1941567"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1109\/PACT.2011.66"},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1145\/2451116.2451153"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1145\/3190508.3190511"},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1145\/3134437"},{"key":"e_1_2_1_69_1","volume-title":"Proceedings of the Workshop on Languages and Compilers for Parallel Computing.","author":"Yuan Liang","year":"2018"},{"key":"e_1_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1145\/1111037.1111040"},{"key":"e_1_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2007.50"},{"key":"e_1_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1145\/1552309.1552310"}],"container-title":["ACM Transactions on Architecture and Code Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3341109","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3341109","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:38:24Z","timestamp":1750199904000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3341109"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,8,20]]},"references-count":71,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2019,9,30]]}},"alternative-id":["10.1145\/3341109"],"URL":"https:\/\/doi.org\/10.1145\/3341109","relation":{},"ISSN":["1544-3566","1544-3973"],"issn-type":[{"value":"1544-3566","type":"print"},{"value":"1544-3973","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,8,20]]},"assertion":[{"value":"2018-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-08-20","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}