{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,27]],"date-time":"2026-03-27T17:13:19Z","timestamp":1774631599573,"version":"3.50.1"},"reference-count":63,"publisher":"Association for Computing Machinery (ACM)","issue":"OOPSLA2","license":[{"start":{"date-parts":[[2023,10,16]],"date-time":"2023-10-16T00:00:00Z","timestamp":1697414400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2023,10,16]]},"abstract":"<jats:p>\n            Binary spatter code (BSC)-based hyperdimensional computing (HDC) is a highly error-resilient approximate computational paradigm suited for error-prone, emerging hardware platforms. In BSC HDC, the basic datatype is a\n            <jats:italic>hypervector<\/jats:italic>\n            , a typically large binary vector, where the size of the hypervector has a significant impact on the fidelity and resource usage of the computation. Typically, the hypervector size is dynamically tuned to deliver the desired accuracy; this process is time-consuming and often produces hypervector sizes that lack accuracy guarantees and produce poor results when reused for very similar workloads. We present Heim, a hardware-aware static analysis and optimization framework for BSC HD computations. Heim analytically derives the minimum hypervector size that minimizes resource usage and meets the target accuracy requirement. Heim\n            <jats:italic>guarantees<\/jats:italic>\n            the optimized computation converges to the user-provided accuracy target on expectation, even in the presence of hardware error. Heim deploys a novel static analysis procedure that unifies theoretical results from the neuroscience community to systematically optimize HD computations.\n          <\/jats:p>\n          <jats:p>We evaluate Heim against dynamic tuning-based optimization on 25 benchmark data structures. Given a 99% accuracy requirement, Heim-optimized computations achieve a 99.2%-100.0% median accuracy, up to 49.5% higher than dynamic tuning-based optimization, while achieving 1.15x-7.14x reductions in hypervector size compared to HD computations that achieve comparable query accuracy and finding parametrizations 30.0x-100167.4x faster than dynamic tuning-based approaches. We also use Heim to systematically evaluate the performance benefits of using analog CAMs and multiple-bit-per-cell ReRAM over conventional hardware, while maintaining iso-accuracy \u2013 for both emerging technologies, we find usages where the emerging hardware imparts significant benefits.<\/jats:p>","DOI":"10.1145\/3622797","type":"journal-article","created":{"date-parts":[[2023,10,16]],"date-time":"2023-10-16T15:41:29Z","timestamp":1697470889000},"page":"1-30","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Hardware-Aware Static Optimization of Hyperdimensional Computations"],"prefix":"10.1145","volume":"7","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6669-6520","authenticated-orcid":false,"given":"Pu (Luke)","family":"Yi","sequence":"first","affiliation":[{"name":"Stanford University, Stanford, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3444-1544","authenticated-orcid":false,"given":"Sara","family":"Achour","sequence":"additional","affiliation":[{"name":"Stanford University, Stanford, USA"}]}],"member":"320","published-online":{"date-parts":[[2023,10,16]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2858965.2814314"},{"key":"e_1_2_2_2_1","volume-title":"Suat Gumussoy, and Umit Y Ogras.","author":"Basaklar Toygun","year":"2021","unstructured":"Toygun Basaklar , Yigit Tuncel , Shruti Yadav Narayana , Suat Gumussoy, and Umit Y Ogras. 2021 . Hypervector de sign for efficient hyperdimensional computing on edge devices. arXiv preprint arXiv:2103.06709, https:\/\/doi.org\/10.48550\/arXiv.2103.06709 10.48550\/arXiv.2103.06709 Toygun Basaklar, Yigit Tuncel, Shruti Yadav Narayana, Suat Gumussoy, and Umit Y Ogras. 2021. Hypervector design for efficient hyperdimensional computing on edge devices. arXiv preprint arXiv:2103.06709, https:\/\/doi.org\/10.48550\/arXiv.2103.06709"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2024716.2024718"},{"key":"#cr-split#-e_1_2_2_4_1.1","unstructured":"Kenneth L Clarkson Shashanka Ubaru and Elizabeth Yang. 2023. Capacity Analysis of Vector Symbolic Architectures. arXiv preprint arXiv:2301.10352 https:\/\/doi.org\/10.48550\/arXiv.2301.10352 10.48550\/arXiv.2301.10352"},{"key":"#cr-split#-e_1_2_2_4_1.2","unstructured":"Kenneth L Clarkson Shashanka Ubaru and Elizabeth Yang. 2023. Capacity Analysis of Vector Symbolic Architectures. arXiv preprint arXiv:2301.10352 https:\/\/doi.org\/10.48550\/arXiv.2301.10352"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCSI.2021.3100266"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1162\/neco_a_01084"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1162\/NECO_a_00467"},{"key":"e_1_2_2_8_1","volume-title":"Analogy Conf. 9.","author":"Gayler Ross W","year":"2009","unstructured":"Ross W Gayler and Simon D Levy . 2009 . A distributed basis for analogical mapping. In New Frontiers in Analogy Research; Proc. of 2nd Intern . Analogy Conf. 9. Ross W Gayler and Simon D Levy. 2009. A distributed basis for analogical mapping. In New Frontiers in Analogy Research; Proc. of 2nd Intern. Analogy Conf. 9."},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/TED.2019.2894387"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/MWSCAS47672.2021.9531748"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3489517.3530553"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/IEDM19573.2019.8993514"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2019.2954472"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3195970.3196060"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICRC.2017.8123650"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/HPCA.2017.28"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3287624.3287667"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/FCCM.2019.00034"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1037\/0033-295X.114.1.1"},{"key":"e_1_2_2_20_1","volume-title":"Hyperdimensional computing: An introduction to computing in distributed representation with high-dimensional random vectors. Cognitive computation, 1, 2","author":"Kanerva Pentti","year":"2009","unstructured":"Pentti Kanerva . 2009. Hyperdimensional computing: An introduction to computing in distributed representation with high-dimensional random vectors. Cognitive computation, 1, 2 ( 2009 ), 139\u2013159. Pentti Kanerva. 2009. Hyperdimensional computing: An introduction to computing in distributed representation with high-dimensional random vectors. Cognitive computation, 1, 2 (2009), 139\u2013159."},{"key":"e_1_2_2_21_1","volume-title":"symposium series.","author":"Kanerva Pentti","year":"2010","unstructured":"Pentti Kanerva . 2010 . What we mean when we say\" What\u2019s the dollar of Mexico?\": Prototypes and mapping in concept space. In 2010 AAAI fall symposium series. Pentti Kanerva. 2010. What we mean when we say\" What\u2019s the dollar of Mexico?\": Prototypes and mapping in concept space. In 2010 AAAI fall symposium series."},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/ALLERTON.2014.7028470"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/MDAT.2018.2890221"},{"key":"e_1_2_2_24_1","first-page":"10000","article-title":"Fully distributed representation","volume":"1","author":"Kanerva Pentti","year":"1997","unstructured":"Pentti Kanerva . 1997 . Fully distributed representation . PAT , 1 , 5 (1997), 10000 . Pentti Kanerva. 1997. Fully distributed representation. PAT, 1, 5 (1997), 10000.","journal-title":"PAT"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1038\/s41565-023-01357-8"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.23919\/DATE48585.2020.9116397"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1162\/neco_a_01590"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/JPROC.2022.3209104"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNNLS.2016.2535338"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3558000"},{"key":"e_1_2_2_31_1","doi-asserted-by":"crossref","unstructured":"Denis Kleyko Dmitri A Rachkovskij Evgeny Osipov and Abbas Rahimi. 2021. A Survey on Hyperdimensional Computing aka Vector Symbolic Architectures Part I: Models and Data Transformations. ACM Computing Surveys (CSUR) https:\/\/doi.org\/A Survey on Hyperdimensional Computing aka Vector Symbolic Architectures \t\t\t\t  Denis Kleyko Dmitri A Rachkovskij Evgeny Osipov and Abbas Rahimi. 2021. A Survey on Hyperdimensional Computing aka Vector Symbolic Architectures Part I: Models and Data Transformations. ACM Computing Surveys (CSUR) https:\/\/doi.org\/A Survey on Hyperdimensional Computing aka Vector Symbolic Architectures","DOI":"10.1145\/3538531"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00521-019-04397-1"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNNLS.2023.3237381"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1038\/s41565-023-01357-8"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/TED.2021.3097975"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/IEDM.2016.7838428"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2714064.2660231"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3195970.3196096"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISLPED.2019.8824908"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1134\/S1064562411010030"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/IECON.2017.8216554"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.11591\/eei.v9i3.1720"},{"key":"e_1_2_2_43_1","unstructured":"Tony A Plate. 1994. Distributed representations and nested compositional structure. Citeseer. \t\t\t\t  Tony A Plate. 1994. Distributed representations and nested compositional structure. Citeseer."},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1111\/1468-0394.00125"},{"key":"e_1_2_2_45_1","unstructured":"Tony A Plate. 2003. Holographic Reduced Representation: Distributed representation for cognitive structures. \t\t\t\t  Tony A Plate. 2003. Holographic Reduced Representation: Distributed representation for cognitive structures."},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/DAC18074.2021.9586166"},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8640.2011.00423.x"},{"key":"e_1_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICRC.2016.7738683"},{"key":"e_1_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCSI.2017.2705051"},{"key":"e_1_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.1109\/JPROC.2018.2871163"},{"key":"e_1_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.1109\/IV48863.2021.9576028"},{"key":"e_1_2_2_52_1","doi-asserted-by":"publisher","DOI":"10.1109\/IJCNN55064.2022.9892158"},{"key":"e_1_2_2_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/3437801.3446108"},{"key":"e_1_2_2_54_1","doi-asserted-by":"publisher","DOI":"10.1109\/IEDM.2014.7047120"},{"key":"e_1_2_2_55_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.future.2019.04.010"},{"key":"e_1_2_2_56_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-19803-8_2"},{"key":"e_1_2_2_57_1","doi-asserted-by":"publisher","DOI":"10.1613\/jair.1.12664"},{"key":"e_1_2_2_58_1","volume-title":"PBA: Percentile-Based Level Allocation for Multiple-Bits-Per-Cell RRAM. In ICCAD.","author":"Wei Anjiang","year":"2023","unstructured":"Anjiang Wei , Akash Levy , Pu (Luke) Yi , Robert Radway , Priyanka Raina , Subhasish Mitra , and Sara Achour . 2023 . PBA: Percentile-Based Level Allocation for Multiple-Bits-Per-Cell RRAM. In ICCAD. Anjiang Wei, Akash Levy, Pu (Luke) Yi, Robert Radway, Priyanka Raina, Subhasish Mitra, and Sara Achour. 2023. PBA: Percentile-Based Level Allocation for Multiple-Bits-Per-Cell RRAM. In ICCAD."},{"key":"e_1_2_2_59_1","doi-asserted-by":"publisher","DOI":"10.1109\/JSSC.2018.2870560"},{"key":"e_1_2_2_60_1","unstructured":"Thomas Yerxa Alexander Anderson and Eric Weiss. 2018. The hyperdimensional stack machine. Cognitive Computing 1\u20132. \t\t\t\t  Thomas Yerxa Alexander Anderson and Eric Weiss. 2018. The hyperdimensional stack machine. Cognitive Computing 1\u20132."},{"key":"e_1_2_2_61_1","doi-asserted-by":"publisher","DOI":"10.5281\/zenodo.8329813"},{"key":"e_1_2_2_62_1","first-page":"1157","article-title":"Understanding hyperdimensional computing for parallel single-pass learning","volume":"35","author":"Yu Tao","year":"2022","unstructured":"Tao Yu , Yichi Zhang , Zhiru Zhang , and Christopher M De Sa . 2022 . Understanding hyperdimensional computing for parallel single-pass learning . Advances in Neural Information Processing Systems , 35 (2022), 1157 \u2013 1169 . Tao Yu, Yichi Zhang, Zhiru Zhang, and Christopher M De Sa. 2022. Understanding hyperdimensional computing for parallel single-pass learning. Advances in Neural Information Processing Systems, 35 (2022), 1157\u20131169.","journal-title":"Advances in Neural Information Processing Systems"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3622797","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3622797","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:37:04Z","timestamp":1750178224000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3622797"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,10,16]]},"references-count":63,"journal-issue":{"issue":"OOPSLA2","published-print":{"date-parts":[[2023,10,16]]}},"alternative-id":["10.1145\/3622797"],"URL":"https:\/\/doi.org\/10.1145\/3622797","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,10,16]]},"assertion":[{"value":"2023-10-16","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}