Hardware Optimizations of Dense Binary Hyperdimensional Computing: Rematerialization of Hypervectors, Binarized Bundling, and Combinational Associative Memory

Manuel Schmuck, Luca Benini, Abbas Rahimi

Introduction

Hyperdimensional (HD) computing is a brain-inspired computational paradigm that represents information using massive pseudo-random bit-vectors, typically with dimensions $D \ge 10,000$. While HD computing offers significant robustness and efficiency for tasks such as biosignal processing, its implementation on resource-constrained hardware is often hindered by a "memory wall." Traditional architectures require storing thousands of seed hypervectors in memory and performing bit-sequential distance calculations, leading to high latency ($O(D)$) and significant memory footprints. This paper introduces hardware optimizations designed to trade memory for combinational logic, making HD computing more feasible for embedded systems.

Proposed Hardware Modules

The authors propose three primary hardware modules, integrated into a synthesizable VHDL library, to optimize the HD computing pipeline:

1. Rematerialization (MAN Module)

To eliminate the need for storing large Item Memory (IM) or Continuous Item Memory (CIM) in RAM, the authors introduce the Hypervector Manipulator (MAN). This module uses simple OR-XOR gates and hardwired connections to "rematerialize" hypervectors on the fly based on input signals. This approach exploits the holographic nature of HD computing—where the overall pattern is more critical than individual bits—to drastically reduce memory requirements.

2. Binarized Back-to-Back Bundling (B2B)

Learning in HD space involves "bundling" multiple hypervectors into a single prototype, usually via majority voting. Standard implementations use multibit counters, which are resource-intensive. The Binarized Back-to-Back (B2B) bundling module replaces counters with a probabilistic weighting system. In this scheme, the $i$-th vote has a $1/i$ probability of flipping the current bit, allowing the system to remain entirely in the binary domain without sacrificing classification accuracy.

3. Combinational Associative Memory (CMB)

Classification is often the primary bottleneck in HD systems. The Combinational Associative Memory (CMB) module replaces bit-sequential distance calculations with deep adder trees. This allows the hardware to compute the Hamming distance between a query and all learned prototypes in a single clock cycle, reducing latency from $O(D)$ to $O(1)$.

The overall HD architecture for gesture recognition, showing the mapping, spatial encoding, and associative memory stages.

Experimental Evaluation

The proposed optimizations were evaluated using a four-channel Electromyography (EMG) dataset for hand gesture recognition. The task involved identifying five distinct gestures (closed hand, open hand, 2-finger pinch, point index, and rest) across five subjects. The goal was to demonstrate that the optimized hardware could achieve "iso-accuracy" compared to a non-optimized baseline while significantly improving area and throughput.

Key Results and Insights

The design space exploration revealed significant improvements across multiple metrics:

  • Throughput: The configuration utilizing the Combinational Associative Memory (LUT+BC+CMB) achieved a 2337× throughput improvement over the baseline.
  • Area Efficiency: The MAN+B2B+VS configuration achieved a 2.39× area saving, fitting the entire learner and classifier into 18,340 Configurable Logic Blocks (CLBs) on a Xilinx FPGA.
  • Complexity Trade-offs: The paper provides a taxonomy of modules based on their Cycles Per Data Item (CPDI), as shown in the table below. This allows designers to select the optimal module based on their specific area and speed constraints.
Cycles Per Data Item (CPDI) for different library modules, highlighting the O(1) complexity of the CMB module.

Conclusion

By prioritizing logic over memory and utilizing probabilistic approximations, the authors demonstrate that HD computing can be highly optimized for FPGA-based embedded devices. The proposed modules offer a flexible library for designers to navigate the trade-offs between throughput and area. Future work will focus on ASIC implementations to further enhance energy efficiency for wearable biosignal processing applications.

Summary updated

Abstract

Brain-inspired hyperdimensional (HD) computing models neural activity patterns of the very size of the brain’s circuits with points of a hyperdimensional space, that is, with hypervectors. Hypervectors are D-dimensional (pseudo)random vectors with independent and identically distributed (i.i.d.) components constituting ultra-wide holographic words: D=10,000 bits, for instance. At its very core, HD computing manipulates a set of seed hypervectors to build composite hypervectors representing objects of interest. It demands memory optimizations with simple operations for an efficient hardware realization. In this article, we propose hardware techniques for optimizations of HD computing, in a synthesizable open-source VHDL library, to enable co-located implementation of both learning and classification tasks on only a small portion of Xilinx UltraScale FPGAs: (1) We propose simple logical operations to rematerialize the hypervectors on the fly rather than loading them from memory. These operations massively reduce the memory footprint by directly computing the composite hypervectors whose individual seed hypervectors do not need to be stored in memory. (2) Bundling a series of hypervectors over time requires a multibit counter per every hypervector component. We instead propose a binarized back-to-back bundling without requiring any counters. This truly enables on-chip learning with minimal resources as every hypervector component remains binary over the course of training to avoid otherwise multibit components. (3) For every classification event, an associative memory is in charge of finding the closest match between a set of learned hypervectors and a query hypervector by using a distance metric. This operator is proportional to hypervector dimension (D), and hence may take O(D) cycles per classification event. Accordingly, we significantly improve the throughput of classification by proposing associative memories that steadily reduce the latency of classification to the extreme of a single cycle. (4) We perform a design space exploration incorporating the proposed techniques on FPGAs for a wearable biosignal processing application as a case study. Our techniques achieve up to 2.39× area saving, or 2,337× throughput improvement. The Pareto optimal HD architecture is mapped on only 18,340 configurable logic blocks (CLBs) to learn and classify five hand gestures using four electromyography sensors.
BibTeX
@article{schmuck2019hardware,
  author = {Manuel Schmuck and Luca Benini and Abbas Rahimi},
  title = {{Hardware Optimizations of Dense Binary Hyperdimensional Computing: Rematerialization of Hypervectors, Binarized Bundling, and Combinational Associative Memory}},
  journal = {ACM J. Emerg. Technol. Comput. Syst.},
  year = {2019},
  doi = {10.1145/3314326},
}
Figure