Hardware-Algorithm Co-Design for Hyperdimensional Computing Based on Memristive System-on-Chip

Venue: NeurIPS_cc_2024_Workshop_MLNCP
Published: 2024-09-11 20:02:09

Abstract: Hyperdimensional computing (HDC), with its highly efficient computing paradigm, provides a parallel and fast-learning algorithm for artificial intelligence (AI), making it well-suited for resource constrained applications like edge intelligence. In-memory computing (IMC) systems based on memristive devices complement this by offering energy-efficient hardware solutions. To harness the advantages of both memristive IMC hardware and HDC algorithms, we propose a hardware-algorithm co-design approach for implementing HDC on a memristive System-on-Chip (SoC). On the hardware side, we utilize the inherent randomness of memristive crossbar arrays for encoding and employ analog IMC for classification. At the algorithm level, we develop hardware-aware encoding techniques that map data features into hyperdimensional vectors, optimizing the classification process within the memristive SoC. Experimental results in hardware demonstrate 90.71\% accuracy in the language classification task, highlighting the potential of our approach for achieving energy-efficient AI deployments on edge devices.

Main paper: 
 introduction: 
 As artificial intelligence (AI) models continue to grow in complexity and scale, the energy consumption required for these models has been increasing dramatically Patterson et al. [2021] . The surge in energy demand has highlighted the energy efficiency in developing future AI systems, especially in scenarios where resources are limited, such as edge applications. Therefore, advancements at both hardware and algorithm levels are highly demanded for deploying AI models across a diverse range of applications and devices.At the hardware level, in-memory computing (IMC) hardware based on memristor devices offers a promising solution by enabling computing within where data is stored Huang et al. [2024] . This approach reduces the time and energy associated with data transfer between memory and processing units, a bottleneck in von Neumann architectures. Memristive IMC hardware leverages the inherent properties of memristor devices to implement parallel vector-matrix multiplication (VMM) by using physical laws, accelerating the inference of neural networks Li et al. [2018] , Wan et al. [2022] , Wen et al. [2024] . Advancements at the device level, such as the increased number of conductance states of memristor devices Rao et al. [2023] , combined with progress at the circuit level, such as the integration of multiple memristor crossbar arrays into a single chip Gallo et al. [2023] , Zhang et al. [2023] , have enhanced the overall capability of IMC systems. In parallel, hardware-algorithm co-designs for memristive crossbar arrays, aimed at achieving arbitrary precision in weight matrix, have enabled high-precision analog IMC Song et al. [2024] .At the algorithm level, hyperdimensional computing (HDC), inspired by biological brains, provides an energy-efficient and hardware-friendly approach by using hyperdimensional vector (HV) repre- sentations of data Kanerva [1988] , Chang et al. [2023] . In HDC, all computations are executed in high-dimensional space, facilitating fast training and parallel inference for the classification tasks at the edge. HDC typically includes two stages: the encoding stage, where original data is transformed into HVs that capture the key features, and the inference stage, where encoded HVs are compared with pre-trained HVs to produce final classification results. Various encoding methods, including low-power sparse encoding Imani et al. [2017a] and encoding based on Nyström method Zhao et al. [2023] , have been explored to achieve efficient and diverse data representations. For the inference of HDC, adaptive training methods have been proposed for robust and efficient inference Hernandez-Cano et al. [2021] . Beyond the conventional similarity checks widely employed as classifiers, neural networks have also been used to enhance the voice recognition accuracy Imani et al. [2017b] .To fully unleash the energy efficiency of IMC hardware and HDC algorithm, existing research has explored the implementation of HDC using IMC hardware based on different memristive devices.Early studies on resistive random-access memory (RRAM)-based IMC hardware for HDC focused on three-dimensional integration of memristor devices to increase device density, facilitating the storage and computation of HVs Li et al. [2016] , Wu et al. [2018] . These works adhere to conventional HDC computing paradigm but improve the speed and energy efficiency of HDC by exploiting the parallelism inherent in IMC hardware and HDC algorithms. With the development of memristor devices, encoding and classifiers based on phase change memory (PCM) Karunaratne et al. [2020] and ferroelectric FET (FeFET) Huang et al. [2023] have been developed with tailored peripheral circuits to further enhance energy efficiency of HDC. Meanwhile, as the computing resources increase, there is a growing need in hardware-algorithm co-designs for HDC to fully harness the potential of IMC hardware. The results shown in Iwasaki and Shintani [2023], and Thomann et al. [2023] highlight the co-design approach to balance energy efficiency and classification accuracy. However, existing works primarily focus on utilizing limited number of conductance states of memristive devices to implement HDC with digital IMC. There has been no exploration of analog IMC hardware for HDC. Moreover, most HDC designs for IMC hardware have been validated primarily through simulations based on memristor models. While these simulations provide valuable insights, there is a lack of studies that demonstrate these designs using experimental hardware. Additionally, the energy efficiency of HDC algorithms using IMC hardware is compromised by the need for off-chip peripherals. These peripherals are required for data transfer and the processing of intermediate data, which detracts from the inherent parallelism of HDC based on IMC hardware.To address these issues and utilize analog IMC for HDC, we propose a hardware-algorithm co-design approach to improve HDC algorithm for our memristive System on Chip (SoC), which integrates ten memristive crossbar arrays to perform analog VMM. The major contributions of our work are:1. Utilizing the inherent randomness of memristor devices to map data features to HVs with a single-step VMM.2. Taking advantage of on-chip peripheral circuits to mitigate the impact of noise from hardware non-idealities on classification accuracy.3. Implementing both encoding and a one-layer memristive perceptron in hardware for classification by coordinating multiple memristive macros within one SoC, achieving experimental accuracy of 90.71 % in language classification.2 Hardware and Algorithm Co-Design for HDC with Analog IMC 
memristive soc and analog vmm: 
 The analog IMC hardware used in this work is an evaluation kit with a memristive SoC. TetraMem [2024] As shown in Figure 1 , the SoC includes ten macros, each integrating one memristive crossbar array and peripheral circuits, such as digital-to-analog converters (DACs) and analog-to-digital converters (ADCs). Each macro, named neural processing units (NPUs), contains a 256 × 256 one-transistor-one-memristor (1T1R) crossbar array, which is used to perform analog VMM. In addition to the NPUs, the SoC incorporates a RISC-V CPU that manages data transfers between multiple NPUs and handles various peripheral functions, along with other digital circuits, such as on-chip memory for intermediate data storage and the interface for on-chip communications.To implement the analog VMM with memristive crossbar arrays, input vectors are converted to voltages by on-chip DACs and applied to the rows of the memristive crossbar arrays. These input voltages are then multiplied by the matrix values, which are represented by the conductance of memristor devices. The output vectors are generated from the accumulated currents collected from the columns of the memristive crossbar array. On-chip transimpedance amplifiers (TIAs) convert the output currents to voltages, which are then digitized by ADCs for further processing. From the computation perspective, conventional HDC using fully digital processing is not well-suited to fully leverage the parallel analog VMM capabilities of multiple NPUs. To take advantage of the energy efficiency of the memristive SoC, it is necessary to develop analog hardware-friendly encoding methods and classifiers for HDC. Furthermore, with limited hardware resources, specifically, the ten 256 × 256 NPUs for both encoding and classifiers, it is challenging to use vectors with high dimensions, such as the 10000 dimensions typically employed in conventional digital HDC, seen in studies by Hernandez-Cano et al. [2021] , Rahimi et al. [2016] . Therefore, it is essential to balance energy efficiency and classification accuracy through HDC algorithm designs. To address these challenges, we propose hardware-aware encoding and a one-layer memristive perceptron as the classifier, enabling us to fully unleash the parallelism and efficiency of analog IMC and HDC.The workflow of conventional HDC and our co-design approach for a language classification task is illustrated in Figure 2 . Initially, the letters in sentences from different languages are mapped to feature vectors, which are represented by voltages applied to the rows of memristive crossbar arrays in the hardware implementation. These feature vectors are then encoded into HVs using a single-step VMM with multiple NPUs within the SoC. After mapping the feature vectors to HVs, post-processing steps are performed to generate a set of HVs for each language, which are used for the training and inference of the classifier. To address the imperfections of analog VMM caused by hardware nonidealities, we apply the hardware-aware processing to the HVs before feeding them to the classifier.In conventional HDC, associative memory is often used as the classifier to achieve higher energy efficiency, though at the cost of lower accuracy. However, since implementing associative memory and one-layer perceptron using analog VMM requires the same amount of hardware resources, we use a one-layer perceptron implemented in memristive crossbar arrays for classification during inference.This approach provides a better balance of accuracy and energy efficiency.The first step in encoding for HDC is the transformation of data features into HVs. Unlike conventional HDC, which relies on random basis HVs generated in software and stored in memory, we utilize the inherent randomness of memristor devices to create a random matrix for the transformation. By employing the hardware-based random matrix, the transformation can be efficiently implemented using a single-step VMM on memristive crossbar arrays.In the language classification task, we first map each letter in text samples to a binary vector, where Different from encoding implemented in software, encoding based on analog hardware is subject to noise due to the non-idealities of memristor devices and peripheral circuits, such as TIAs and ADCs. In the VMM-based transformation, output currents fluctuate within a small range, leading to shifts in the ADC results we used to determine the HVs. Since the least significant bits of ADC results are highly sensitive to the fluctuations of output currents, the HVs from the ADC results propagate the noise to the classifiers, impacting classification accuracy. However, upon analyzing experimental VMM results from the memristive SoC, we observe that most outputs fluctuate within a small range of ±2.77mV , which only impacts the lower few bits of ADC results for the 8-bit on-chip ADCs. To mitigate the impact of these fluctuations on outputs from identical inputs, we choose another bit position of the ADC results to determine the sign of the corresponding entry in the HVs by analyzing the noise introduced by the memristive crossbar arrays used for encoding. For instance, using the third least significant bit of the ADC results ensures this bit remains consistent when the fluctuations only affect the least two bits of the ADC results. This approach can tolerate noise from the non-idealities of analog VMM on the memristive SoC while effectively distinguishing feature vectors from text samples in different languages.After determining the sign of the entries of the HVs, all HVs from one text sample are summed to generate an encoded HV that represents the features of the text sample. Since the HVs from each trigram vector contain both -1 and 1, the resulting encoded HVs range from negative to positive values. In conventional HDC, these encoded HVs are binarized before being used as inputs to the classifier, as binary representation is more friendly to digital computing systems. However, our memristive SoC allows for multilevel voltage inputs to the classifier because there are 8-bit on-chip DACs connected to each row of the memristive crossbar arrays. Therefore, instead of binarizing the encoded HVs, we quantize their values to 8-bit for the classifier. These multilevel HVs preserves more feature information from each text sample, which compensated the relatively low dimensions of HVs used due to the limitation of hardware resources (512 dimensions instead of the typical 10000 dimensions). The noise-tolerant processing to generate the encoded HVs can all be implemented in the on-chip CPU as illustrated in Figure 2 .After encoding the text data features into HVs, language classification becomes a relatively simple task. In conventional HDC, associative memory is commonly used as the classifier due to its efficiency.However, a neural network trained with the stochastic gradient descent (SGD) algorithm can achieve higher classification accuracy, as demonstrated by Imani et al. [2017b] . Conventional HDC prioritizes energy efficiency over accuracy because neural networks typically consume more energy than associative memory. However, our approach utilizes memristive crossbar arrays to implement a one-layer perceptron in a single step using parallel analog VMM. This implementation leverages the same computational demand as associative memory and enables us to benefit from both the energy efficiency of the memristive hardware and the improved accuracy of a neural network-based classifier, compared to using associative memory approach for classification.In the language classification task, we use a perceptron with 512 input neurons and 21 output neurons  
experimental results: 
 The dataset for the language classification task consists of short text samples from 21 European languages, each includes 1000 text samples that are all transliterated into the Latin alphabet Hernandez-Cano et al. [2021] . We use 70 % of these samples for training while the remaining 30 % for evaluation.To evaluate the HDC algorithm design for our memristive SoC, we first simulate the encoding and classifier in software using the hardware-aware encoding method and one-layer perceptron. The average classification accuracy achieved is 96.71 %, as shown in Figure 3 . This result demonstrates that our proposed hardware-aware encoding, combined with the one-layer perceptron, can achieve comparable classification accuracy, even with 512-dimensional HVs for encoding, much lower than 10000 dimensions typically used in conventional HDC.After confirming the accuracy achieved by our proposed co-design method through simulations, we implement both the encoding and classifier separately on our memristive SoC to study the impact of non-idealites in memristor devices and peripheral circuits on classification accuracy.  
conclusion: 
 In conclusion, we propose a hardware-algorithm co-design approach to leverage analog IMC and HDC within a memristive SoC. By coordinating multiple NPUs within the SoC to implement hardwareaware encoding and one-layer perceptron, we demonstrate the effectiveness of the proposed co-design with a language classification task. The simulation results, achieving an average classification accuracy of 96.71% validate our modifications to the HDC algorithm, while the experimental results with an average classification accuracy of 90.71 % confirm the feasibility of our hardware implementations. The hardware-algorithm co-design paves the way to harness analog IMC for energy-efficient HDC in edge intelligent applications. Future work will focus on increasing the dimensions of HVs as hardware resource allows and applying this approach to other classification tasks involving more complicated data. 
 
 Appendix:  



Reviews: review: title: title: Hardware-Algorithm Co-Design for HDC
main_review: main_review: The authors devleop a HDC application using a SoC from TetraMem.

While I don't agree with the authors' statement that there have not been previous analog / memristive demonstrations of HDC, I think it is commenable to have mapped a simple HDC problem onto a SoC containing Memristors and demonstrated an application on the hardware while keeping the task performance relatively high. 

The principle of using intrinsic noise of memristor programming to generate random basis' is also novel and this claim should be tempered since it appears as one of the main contributions of this paper.

I did not understand the phrase "Taking advantage of on-chip peripheral circuits to mitigate the impact of noise from hardware non-idealities on classification accuracy" because I did not see in the paper how peripheral circuits of the SoC achieved this in the paper. What I understoof was that you didn't use the LSbits of the ADC since they were subject to noise, but I wouldn't consider this taking advantage ?
title: title: HDC Hardware-Algorithm co-design use Analog IMC for simple language processing task
main_review: main_review: This paper proposed an simple HDC  Hardware-Algorithm co-design based on analog IMC for on chip computing. Co-design is an interesting topic with practical benefits, especially for HDC-based methods which have desirable properties for hardware implementation.

Strong points:
- Analog implementation of HDC applications seems to be an promising direction. Although authors should definitely consider adding more motivation for analog vs. digital design in the future.
- Although a bit un-organized, authors provided many details regarding analog SoC implementation which is important.

Weak points:
- Writing and structure of the paper should be improved significantly. At its current stage it is difficult to follow some of the design decisions are not well motivated (i.e. why trigram).
- The capability of proposed system seems to be very limited, it is only suitable for tasks with a small number of symbols (i.e. the European language dataset demonstrated in the paper) and low HDC dimensionality. How would it performs in other more challenge tasks.
-  Although the authors claims algorithm co-design, there is little novelty regarding proposed algorithms as N-gram based encoding has been extensive studies in the context of HDC even with simple binary HDC architecture. 
- Following previous point on novelty, it is unclear what is new being offered here by using a perceptron instead of traditional HDC retraining steps (which is also perceptron algorithm by considering class hypervectors the weights and adjusting them iteratively). Furthermore, why does this part needs pretraining and is it an realistic assumption.
- Hardware-Algorithm co-design is an popular research field for HDC but this paper does not include any comparisons to other design.
- Evaluation section failed to show the benefits of proposed design (efficiency? time?), and accuracy degradation seem quite significant (96->90).

Overall, my main concern for this paper is the lack of novelty and the lack of valid evaluations and comparisons that can demonstrate the practical benefits of the design.