Hardware-Aware Static Optimization of Hyperdimensional Computations
Open Access
- 16 October 2023
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Programming Languages
- Vol. 7 (OOPSLA2) , 1-30
Abstract
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 hypervector , 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 guarantees 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. 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 – for both emerging technologies, we find usages where the emerging hardware imparts significant benefits.Keywords
All Related Versions
This publication has 49 references indexed in Scilit:
- Approximate computation with outlier detection in TopazACM SIGPLAN Notices, 2015
- Monolithic 3D integration of logic and memory: Carbon nanotube FETs, resistive RAM, and silicon FETs2014
- ChiselACM SIGPLAN Notices, 2014
- Computing with 10,000-bit words2014
- Representing Objects, Relations, and SequencesNeural Computation, 2013
- SIMILARITY‐BASED RETRIEVAL WITH STRUCTURE‐SENSITIVE SPARSE BINARY DISTRIBUTED REPRESENTATIONSComputational Intelligence, 2012
- The gem5 simulatorACM SIGARCH Computer Architecture News, 2011
- On the bound of proximity of the binomial distribution to the normal oneDoklady Mathematics, 2011
- Representing word meaning and order information in a composite holographic lexicon.Psychological Review, 2007
- Analogy retrieval and processing with distributed vector representationsExpert Systems, 2000