Hyperdimensional Computing (HDC) is a novel brain-inspired learning paradigm based on the observation that brains perform cognitive tasks by mapping sensory inputs to high-dimensional neural representation [1][2][3]. It enables the brain to carry out simple, low-power, error-resilient, and parallelizable operations all in the hyperspace. Such characteristics of HDC make it appealing for a wide variety of applications such as IoT domain that generates an increasing amount of data with tight resource and energy constraints [4,5].
HDC uses specific algorithms to encode raw inputs to a highdimensional representation of hypervectors with D ℎ𝑣 ≈2-5𝐾 dimensions. The encoding takes place by deterministically associating each element of an input with a binary or bipolar (±1) hypervector and bundling (element-wise addition) the hypervectors of all elements to create the encoded hypervector. Training is straightforward and involves bundling all encoded hypervectors of the same category. For inference, the query input is encoded to a hypervector in the same fashion and compared with all class hypervectors using a simple similarity metric such as cosine.
The bit-level massively parallel operations of HDC do not accord well with conventional CPUs/GPUs due to, e.g., memory latency and data movement of large vectors and the fact that these devices are over-provisioned for majorly binary operations of HDC. Previous works on custom HDC accelerators support a limited range of applications or achieve low accuracy. The authors of [6] and [7] propose custom HDC inference designs that are limited to a specific application. More flexible HDC inference ASICs are proposed in [8] and [9], but as we quantify in Section 3.2, the utilized encoding techniques achieve poor accuracy for particular applications such as time-series. The authors of [10] propose a trainable HDC accelerator, which yields 9% lower accuracy than baseline ML algorithms. An HDC-tailored processor is proposed in [11], but it consumes ∼1-2 orders of magnitude more energy than ASIC counterparts. The in-memory HDC platform of [12] uses low-leakage PCM cells to store hypervectors, but its CMOS peripherals throttle the overall efficiency.
In this paper, we propose GENERIC (highly efficient learning engine on edge using hyperdimensional computing) for highly efficient and accurate trainable classification and clustering. Our primary goal is to make GENERIC compact and low-power to meet year-long battery-powered operation, yet fast enough during training and burst inference, e.g., when it serves as an IoT gateway. To this end, we make the following contributions.
(1) We propose a novel HDC encoding that yields high accuracy in various benchmarks. Such a generic encoding is fundamental to develop a custom yet flexible circuit.
(2) We perform a detailed comparison of HDC and various ML techniques on conventional devices and point out the failure of these devices in unleashing HDC advantages.
(3) We propose the GENERIC flexible architecture that implements accurate HDC-based trainable classification and clustering. (4) GENERIC benefits from extreme energy reduction techniques such as application-opportunistic power gating, on-demand dimension reduction, and error-resilient voltage over-scaling.
(5) Comparison of GENERIC with the state-of-the-art HDC implementations reveals GENERIC improves the classification accuracy by 3.5% over previous HDC techniques and 6.5% over ML techniques. GENERIC improves energy consumption by 4.1× and 15.7× compared to previous HDC accelerators [8] and [10], respectively. The similarity of hypervectors indicates their proximity [1], which can be used to cluster data in the hyperspace [13]. Initially, 𝑘 encoded hypervectors are selected as clusters centroids. At each iteration, all encoded inputs are compared with the centroids and added to the closest (highest score) centroid hypervector. In classification, the model is updated right away. However, in clustering, the model is fixed and used for finding the similarities, and a new model is created from scratch, which replaces the current model in the next iteration.
Encoding is the major step of HDC; hence, previous works have proposed several encoding techniques to map the inputs to highdimensional space. Most encodings associate hypervectors with the raw input features (elements), called level hypervector (see Figure 2(a)), which are hyperspace representative of scalar elements. Usually, inputs are quantized into bins to limit the number of levels. If there is a meaningful distance between the input elements (as in the values of white and black pixels), this distance is also preserved when generating the levels.
Encoding of an input is accomplished by aggregation the level hypervectors of its elements. To handle the positional order of elements, which is essential in most datasets such as image or voice, HDC uses variants of binding. The permutation encoding of Figure 2(b) carries out binding by circular shift of the level hypervectors; the level hypervector of 𝑚 th feature is permuted by 𝑚 indexes. Some other encodings such as random projection (RP), shown in Figure 2(c), or level-id use id hypervectors for binding. In these encodings, each input index has a random (but constant) binary id, which is multiplied (XOR in the binary domain) with its level, and the result vector is aggregated with that of other indexes.
The encoding techniques discussed in Section 2.2 achieve low accuracy for certain datasets such as language identification which generally need extracting local subsequences of consecutive features, without considering the global order of these subsequences (see subsection 3.2). Previous studies use ngram encoding for such datasets [6,7,14]. Ngram encoding extracts all subsequences of length 𝑛 (usually 𝑛∈{3-5}) in a given input, encodes all these subsequences and aggregates them to produce the encoded hypervector. However, ngram encoding achieves very low accuracy for datasets such as images or voices in which the spatio-temporal information of should be taken into account.
We propose a new encoding, dubbed GENERIC, to cover a more versatile set of applications. As shown in Figure 2(d), our encoding processes sliding windows of length 𝑛 by applying the permutation encoding. That is, for every window consisting of elements {𝑥 𝑘 , 𝑥 𝑘+1 , 𝑥 𝑘+2 } (for 𝑛=3), three level hypervectors are selected, where ℓ (𝑥 𝑘 ), ℓ (𝑥 𝑘+1 ), and ℓ (𝑥 𝑘+2 ) are permuted by 0, 1, and 2 indexes, respectively. The permuted hypervectors are XORed elementwise to create the window hypervector. The permutation accounts for positional information within a window, e.g., to distinguish "abc" and "bca". To account for global order of features, we associate a random but constant id hypervector with each window, which is XORed with the window hypervector to perform binding. To skip the global binding in certain applications, id hypervectors are set to {0} D ℎ𝑣 . Equation (1) formalizes our encoding, where 𝜌 ( 𝑗) indicates permutation by 𝑗 indexes, multiplies (XOR in binary) the levels of 𝑖 th window, 𝑖𝑑 𝑖 applies the binding 𝑖𝑑, and adds up the window hypervector for all windows of 𝑑 elements.
We use 𝑛=3 as it achieved the highest accuracy (on average) for our examined benchmarks (see subsection 3.2), however, GENERIC architecture can adjust the value of 𝑛 for every application.
We compiled eleven datasets from different domains, consisting of the benchmarks described in [10], seizure detection by skull surface EEG signals, and user activity recognition by motion sensors (PAMAP2) [15]. We implemented the HDC algorithms using an optimized Python implementation that leverages SIMD operations. For ML techniques, we used Python scikit-learn library [16]. We discarded the results of logistic regression and 𝑘-nearest neighbors as they achieved lower accuracy. For DNN models of benchmarks, we used AutoKeras library [17] for automated model exploration.
Table 1 summarizes the accuracy results (RP: random projection, MLP: multi-layer perceptron, SVM: support vector machine, RF: random forest). The proposed GENERIC encoding achieves 3.5% higher accuracy than the best baseline HDC (level-id), 6.5% higher than best baseline ML (SVM), and 1.0% higher than DNN. The RP encoding fails in time-series datasets that require temporal information (e.g., EEG). As explained in subsection 3.1, the ngram encoding [6,14] do not capture the global relation of the features, so it fails in datasets such as speech (ISOLET) and image recognition (MNIST). Except for the ngram and the proposed GENERIC, other HDC techniques fail in the LANG (text classification) as they enforce capturing sequential information and ignore subsequences.
HDC's operations are simple and highly parallelizable, however, conventional processors are not optimized for binary operations such as one-bit accumulation. Also, the size of hypervectors in most settings becomes larger than the cache size of low-end edge processors, which may impose significant performance overhead. For a detailed comparison, we implemented the HDC and ML algorithms on the datasets of subsection 3.2 on a Raspberry Pi 3 embedded processor and NVIDIA Jetson TX2 low-power edge GPU, and also a desktop CPU (Intel Core i7-8700 at 3.2 GHz) with a larger cache. We used Hioki 3334 power meter to measure the power of the Raspberry Pi.
Figure 3 compares the training and inference (a) energy consumption and (b) execution time of the algorithms, reported as the geometric mean of all benchmarks (for eGPU, we omitted the results of conventional ML as it performed worse than CPU for a variety of libraries we examined). We can observe that (i) conventional ML algorithms, including DNN, unanimously consume smaller energy than HDC on all devices, (ii) GENERIC encoding, due to processing multiple hypervectors per window, is less efficient than other HDC techniques, and (iii) our eGPU implementation, by data packing (for parallel XOR) and memory reuse, significantly improves the HDC execution time and energy consumption. For instance, eGPU improves the energy usage and execution time of GENERIC inference by 134× and 252× over running on low-end Raspberry Pi (70× and 30× over CPU). However, GENERIC running on eGPU still consumes 12× (3×) more inference (train) energy, with 27× (111×) higher execution time than the most efficient baseline (random forest). Nonetheless, eGPU numbers imply substantial energy and runtime reduction potential for HDC by effectively taking advantage of low-precision operations (achieved by bit-packing in eGPU) and high parallelism.
Figure 4 shows the main components of GENERIC architecture. The main inputs include (i) input port to read an input (including the label in case of training) from the serial interface element by element and store in the input memory before starting the encoding, (ii) config port to load the level, 𝑖𝑑, and class hypervectors (in case of offline training), and (iii) spec port to provide the application characteristics to the controller, such as D ℎ𝑣 dimensionality, 𝑑 elements per input, 𝑛 length of window, 𝑛 𝐶 number of classes or centroids, 𝑏𝑤 effective bit-width, and mode (training, inference, or clustering). Output port returns the labels of inference or clustering.
The controller, by using spec data, handles the programmability of GENERIC and orchestrates the operations. For instance, the encoder generates 𝑚=16 (architectural constant) partial dimensions after each iteration over the stored input, where the variable D ℎ𝑣 signals the end of encoding to finalize the search result, 𝑑 denotes the number of input memory rows to be proceeded to fetch features (i.e., the exit condition for counter), 𝑛 𝐶 indicates the number of class memory rows that need to be read for dot-product and so on. The class memory layout of GENERIC also allows trade off between the hypervectors length 𝐷 ℎ𝑣 and supported classes 𝑛 𝐶 . By default, GENERIC class memories can store 𝐷 ℎ𝑣 =4K for up to 𝑛 𝐶 =32 classes. For an application with less than 32 classes, higher number of dimensions can be used (e.g., 8K dimensions for 16 classes). We further discuss it in subsection 4.3. These application-specific input parameters enable GENERIC the flexibility to implement various applications without requiring a complex instruction set or reconfigurable logic.
Features are fetched one by one from the input memory and quantized to obtain the level bin, and accordingly, 𝑚 (16) bits of the proper level hypervector are read. The levels are stored as 𝑚-bit rows in the level memory. The stacked registers (reg 𝑛 to 1) facilitate storing and on-the-fly sliding of level hypervectors of a window. Each pass over the input features generates 𝑚 encoding dimensions, which are used for dot-product with the classes. The class hypervectors are distributed into 𝑚 memories (CM 1 to CM 𝑚) to enable reading 𝑚 consecutive dimensions at once. The dot-product of partial encoding with each class is summed up in the pipelined adder • 6 , and accumulated with the dot-product result of previous/next 𝑚 dimensions in the score memory • 7 .
After D ℎ𝑣 𝑚 iterations, all dimensions are generated, and the dotproduct scores are finalized. We use cosine similarity metric between the encoding vector H and class C 𝑖 :
; hence, we need to normalize the dot-product result with L2 norms. The H 2 can be removed from the denominator as it is a constant and does not affect the rank of classes. In addition, to eliminate the square root of C 𝑖 2 , we modify the metric to
without affecting the predictions. The norm2 memory of Figure 4 • 8 stores the squared L2 norms of classes, and similarly, the squared score is passed to the divider • 9 . We use an approximate log-based division [18]. of all class memories. The controller uses the input label and the iteration counter to activate the proper memory row. In the next retraining epochs, the model is examined and updated in case of misprediction (see Figure 1). Thus, during retraining, meanwhile performing inference on the training data, the encoded hypervector is stored in temporary rows of the class memories (through the second input of mux • 3 ). If updating a class is required, the class rows are read and latched in the adder • 4 , followed by reading the corresponding encoded dimensions from the temporary rows and writing the new class dimensions back to the memory. Hence, each update takes 3× D ℎ𝑣 𝑚 cycles. Training also requires calculating the squared L2 norm of classes in the norm2 memory • 8 . As it can be seen in Figure 4, the class memories are able to pass the output into both ports of the multipliers (one direct and another through the mux) to calculate and then accumulate the squared elements.
GENERIC selects the first 𝑘 encoded inputs as the initial cluster centroids and initializes 𝑘 centroids in the class memories. It allocates two sets of memory rows for temporary data; one for the incoming encoding generated in the encoding module and another for the copy centroids (as mentioned in Section 2.1, clustering generates a new copy instead of direct update). Similarity checking of the encoding dimensions with the centroids is done pipelined similar to inference, but the encoded dimensions are stored to be added to the copy centroid after finalizing the similarity checking. After finding the most similar centroid, the copy centroid is updated by adding the stored hypervector (similar to retraining). The copy centroids serve as the new centroids in the next epoch.
We take advantage of the properties of GENERIC architecture and HDC for utmost energy efficiency. The following elaborates energy-saving techniques that benefit GENERIC. These techniques can also be applied to other HDC accelerators.
The 𝑖𝑑 memory naturally needs 1K×4K=512 KB (for up to to 1K features per input, and D ℎ𝑣 =4K dimensions) which occupies a large area and consumes huge power. However, GENERIC generates 𝑖𝑑s on-the-fly using a seed 𝑖𝑑 vector, where 𝑘 th 𝑖𝑑 is generated by permuting the seed 𝑖𝑑 by 𝑘 indexes. Therefore, the 𝑖𝑑 memory shrinks to 4 Kbit, i.e., 1024× reduction. Permutation preserves the orthogonality. It is implemented by the tmp register in Figure 4 • 2 , by which, for a new window, the reg id is right-shifted and one bit of tmp is shifted in. The tmp register helps to avoid frequent access to the 𝑖𝑑 memory by reading 𝑚 (16) bits at once and feeding in the next 𝑚 cycles.
For an application with 𝑛 𝐶 classes and using D ℎ𝑣 dimensions, GENERIC stripes the dimensions 1 to 𝑚 (16) of its 1 st class vector in the 1 st row of 𝑚 class memories, the 2 nd class vector in the 2 nd row, and so on (see Figure 4). The next 𝑚 dimensions of the 1 st class vector are therefore written into 𝑛 𝐶 + 1 th row, followed by the other classes. Thus, GENERIC always uses the first 𝑛 𝐶 ×D ℎ𝑣 32×4K portion of class memories. The applications of Section 3.2, on average, fill 28% of the class memories (minimum 6% for EEG/FACE, and maximum 81% for ISO-LET) using D ℎ𝑣 =4K dimensions. Accordingly, GENERIC partitions each class memory into four banks and power gates the unused banks. With four banks, 1.6 out of four banks are activated on average, leading to 59% power saving. With more fine-grained eight banks, 2.7 banks (out of eight) become active, saving 66% power. However, eight banks impose 55% area overhead compared to 20% of four banks (see Section 5.1 for setup). We concluded that the fourbank configuration yields the minimum area×power cost. Since the power gating is static (permanent) for an application, no wake-up latency or energy is involved.
GENERIC can trade the energy consumption and performance with accuracy. Recall that GENERIC generates 𝑚 dimensions of the encoding per iteration over the features. By feeding a new D ℎ𝑣 value as input, GENERIC can seamlessly use the new dimension count by updating the counter exit condition, so smaller hypervectors of the encoding and class hypervectors will be used. Nevertheless, GENERIC stores the squared L2 norms of the whole classes for similarity metric (𝛿 𝑖 =
) while for arbitrary reduced encoding dimensions, only the corresponding elements (and their L2 norms) of the classes are needed. As Figure 5 shows, using the old (Constant) L2 values causes significant accuracy loss compared to using the recomputed (Updated) L2 norm of sub-hypervectors. The difference is up to 20.1% for EEG and 8.5% for ISOLET. To address this issue, when calculating the squared L2 norms during the training, GENERIC stores the L2 norms of every 128 th -dimension sub-class in a different row of the norm2 memory • 8 .Thus, dimensions can be reduced with a granularity of 128 while keeping the norm2 memory small (2 KB for 32 classes).
Voltage Over-scaling: GENERIC has to use 16-bit class dimensions to support training. As a result, the large class memories consume ∼80% of the total power. HDC exhibits notable tolerance to the bit-flip of vectors [19], which can be leveraged to over-scale the memory voltage without performance loss. Figure 6 shows the accuracy of select benchmarks (ISOLET and FACE) with respect to the class memory error. The static (s) and dynamic (dyn) power saving as a result of corresponding voltage scaling (without reducing clock cycle) is also shown in the right axis (based on the measured data of [20]). The figure shows the result of the HDC models with different bit-width (𝑏𝑤 input parameter of GENERIC)
of classes by loading a quantized HDC model (the mask unit • 5 in the architecture masks out the unused bits). As it can be seen, error tolerance not only depends on application but also on the bit-width.
1-bit FACE model shows a high degree of error tolerance (hence, power saving) by up to 7% bit-flip error rate, while ISOLET provides acceptable accuracy by up to 4% bit-flip using a 4-bit model. Quantized elements also reduce the dynamic power of dot-product.
Voltage over-scaling also depends on the application's sensitivity to dimension reduction and its workload. For instance, FACE has a higher tolerance to voltage scaling than dimension reduction (see Figure 5). On the other hand, ISOLET is more sensitive to voltage reduction but achieves good accuracy down to 1K dimensions (Figure 5), which means 4× energy reduction compared to 4K dimensions. Thus, voltage over-scaling for ISOLET is only preferred in workloads with a higher idle time where the static power dominates (voltage scaling reduces the static power more significantly).
We implemented GENERIC at the RTL level in SystemVerilog and verified the functionality in Modelsim. We used Synopsys Design Compiler to synthesize GENERIC targeting 500 MHz clock with 14 nm Standard Cell Library of GlobalFoundries. We used Artisan memory compiler to generate the SRAM memories. The level memory has a total size of 64×4K = 32KB for 64 bins, the feature memory is 1024×8b, and class memories are 8K×16b (16 KB each). We obtained the power consumption using Synopsys Power Compiler. GENERIC occupies an area of 0.30 mm 2 and consumes a worst-case static power of 0.25 mW when all memory banks are active. For datasets of Section 3.2, GENERIC consumes a static and dynamic power of 0.09 mW, and 1.79 mW, respectively (without voltage scaling). Figure 7 shows the area and power breakdown. Note that the level memory contributes to less than 10% of area and power. Hence, using more levels does not considerably affect the area or power.
Since previous HDC ASICs have not reported training energy and performance, we compare the per-input energy and execution time of GENERIC training with RF (random forest, most efficient baseline) and SVM (most accurate conventional ML) on CPU, and DNN and HDC on eGPU. Figure 8 shows the average energy and execution time for the datasets of Section 3.2. GENERIC improves the energy consumption by 528× over RF, 1257× over DNN, and 694× over HDC on eGPU (which, as discussed in Section 3.3, is the most efficient baseline device for HDC). GENERIC consumes an average 2.06 mW of training power. It also has 11× faster train time than DNN and 3.7× than HDC on eGPU. RF has 12× smaller train time than GENERIC, but as we mentioned, the overall energy consumption of GENERIC is significantly (528×) smaller than RF. Also, we used constant 20 epochs for GENERIC training while the accuracy of most datasets saturates after a few epochs.
We compare the energy consumption of GENERIC inference with previous HDC platforms from Datta et al. [10], and tiny-HD [8]. We scale their report numbers to 14 nm according to [21] for a fair comparison. We also include the RF (most efficient ML), SVM (most-accurate ML) and DNN on HDC on eGPU (mostefficient HDC baseline). Figure 9 of GENERIC and aforementioned baselines. Since GENERIC achieves significantly higher accuracy than previous work (e.g., 10.3% over [10]), GENERIC-LP applies the low-power techniques of Section 4.3 to leverage this accuracy benefit. GENERIC-LP improves the baseline GENERIC energy by 15.5× through dimension reduction and voltage over-scaling. GENERIC-LP consumes 15.7× and 4.1× less energy compared to [10] and tiny-HD [8], respectively. Note that despite tiny-HD [8], GENERIC supports training which makes it to use larger memories. GENERIC is is 1593× and 8796× more energy-efficient than the most-efficient ML (RF) and eGPU-HDC, respectively.
Table 2 compares the normalized mutual information score of the K-means and HDC for the FCPS [22] benchmarks and the Iris flower dataset. On average, K-means achieves slightly (0.031) higher score, but for datasets with more features, the proposed GENERIC can better benefit from using windows (windows become less effective in a smaller number of features).
Figure 10 compares the per-input energy consumption of GENERIC with K-means clustering running on CPU and Raspberry Pi. GENERIC consumes only 0.068 𝜇J per input, which is 17,523× and 61,400× more efficient than K-means on Raspberry Pi and CPU. The average per-input execution time of Raspberry Pi and CPU is, respectively, 394 𝜇Sec and 248 𝜇Sec, while GENERIC achieves 9.6 𝜇Sec (41× and 26× faster than R-Pi and CPU, respectively).
We proposed GENERIC, a highly-efficient HDC accelerator that supports classification (inference and training) and clustering using a novel encoding technique that achieves 3.5% (6.5%) better accuracy compared to other HDC (ML) algorithms. GENERIC benefits from power-gating, voltage over-scaling, and dimension reduction for utmost energy saving. Our results showed that GENERIC improves the classification energy by 15.1× over a previous trainable HDC accelerator, and 4.1× over an inference-only accelerator. GENERIC HDC-based clustering consumes 17,523× lower energy with 41× higher performance than Raspberry Pi running K-means with similar accuracy, facilitating ultra-efficient continuous learning on edge.