Project Motivation and Goals

The k-Nearest-Neighbours (kNN) algorithm is a popular Machine Learning technique that can be used for a variety of supervised classification tasks. In contrast to other machine learning algorithms which "encode" the knowledge gained from training data to a set of parameters, such as weights and biases, the parameter set of a kNN classifier consists of just labelled training examples. Classification of an unlabelled example takes place by calculating its Euclidean distance (or any other type of distance metric) from all the stored training examples. The label of the unknown example is determined by the majority of the labels of the k closest examples.

In contrast to other Machine Learning methods, kNN classification doesn't require an explicit training phase, which makes it a potential candidate for learning directly from the data captured by an embedded system. However, the computation of the distance metrics between a new unclassified example and the labelled examples stored as the classifier's parameter set acts as a bottleneck in the classification process, if it is implemented in software. Through the development of dedicated hardware for calculating the required distance metrics, it is possible to reduce inference time.

The goal of this project is to build a hardware implementation of a kNN classifier that can achieve reduced inference time when compared to a kNN classifier implemented fully in software, through the parallelisation of distance metric computations. The project has an educational purpose and it expected that by its completion, the contributors will have gone through the complete design cycle of a SoC.

Design Specification

The first step in defining the design specification for the accelerator was to determine the type of data that need to be processed by it. The Fashion-MNIST dataset has been selected as the primary data source. Therefore, the accelerator should be able to handle grayscale image vectors with a size of 28 x 28 pixels. We assume that some of these images will be labelled (training set), while some of them won't (test set). The accelerator should help with computing the distance between all the labelled images and each unknown image in the unlabelled set.

Data to be processed: N 28 x 28 8-bit (grayscale) labelled image vectors and M unlabelled image vectors, stored in SRAM.

Image vectors a⁽ⁱ⁾, b^(j) have D elements, where D = 28 x 28 = 784. Each element is represented as an 8-bit unsigned integer value. If N = 200 and M = 50, the total storage requirements for matrices A and B are:

N x 785 + M x 784 = 200 x 785 + 50 x 784 = 196,200 bytes, which is approximately equal to 192 kB. It is assumed that one byte of storage is required for storing every label. This is the reason why the number of labelled examples N is multiplied by 785 and not 784.

We would like to compute the Squared Euclidean distance between each pair of vectors a⁽ⁱ⁾, b^(j). This computation is given by the sum of 3 dot products, as shown below:

The self-dot products a⁽ⁱ⁾⋅a⁽ⁱ⁾ and b^(j)⋅b^(j) can only be computed once and then reused for another computation.

Design Rationale

Constraints introduced by the SoC infrastructure

The nanosoc infrastructure provided by SoCLabs was used as the core of the design. At the early design stages, it was decided not to use a DMA peripheral for writing/reading data to/from the accelerator engine to keep things simple. Therefore, all the data movements to/from the accelerator were happening through the AHB-Lite Bus.

Accelerator Dataflow

The accelerator's input data consist of high-dimensional image vectors. In contrast, its output data consist of just three scalar values. In addition, the rate at which data need to be written to the engine is much higher than the rate at which computed values need to be moved out. The above two observations indicate that the accelerator's dataflow is highly asymmetric. Writing a complete image vector to the accelerator engine instantaneously is not possible due to the bus constraints. However, computing the desired dot-products can happen incrementally, using parts of the image vectors delivered as packets.

The size of each input packet was set arbitrarily to 128 bits (16 bytes). An image vector with 784 byte long elements, can be split into 784 / 16 = 49 packets. The AHB-Lite Bus can deliver a 32-bit data word, which means that 4 write operations are required to create a packet of 128 bits.

I/O Ports

Input port:

• 128-bit Valid/Ready signal port

Output port:

• Register interface for reading the contents of the dot product accumulators and monitoring internal control/status registers.

System overview

To properly interface the Fast-kNN engine with the AHB-Lite bus, the accelerator wrapper IP provided by SoCLabs was used. Data words delivered through the AHB-Lite bus are passed to the AHB Packet Constructor which packages them into 128-bit packets. These packets are then passed to the engine though a valid-ready handshake. Reading the accumulator registers that hold the results of the computation required the use of the AHB Register Interface IP.

Fast-kNN Engine

The Fast-kNN accelerator consists of the following parts:

• A byte long buffer with a depth of 784 elements, whose purpose is to store a complete unlabelled image vector.
• A byte long buffer with a depth of 16 elements that temporarily holds a data packet from a labelled image.
• Three 32-bit accumulator registers that hold the computed dot products. The contents of these registers are updated incrementally as new data packets become available.
• A 3-bit control register, where each bit has the following role:
  • Bit 0 - Packet data ready flag. This flag is pulled low when the transfer of the input data packet from the packet constructor to the engine is complete and the dot product computation can begin.
  • Bit 1 - Priming mode flag. This flag is pulled low when the unlabelled image buffer becomes full.
  • Bit 2 - Software reset bit

After a reset, all data registers are empty and the priming mode flag is high. Delivered packets are written to the unlabelled image buffer and the self-dot product for the unlabelled image is incrementally accumulated. When a complete unlabelled image vector has been written to the engine, the priming mode flag is pulled low. Packets from a labelled image can then be delivered to the engine for the computation of the other two dot products to take place. Once all elements of the labelled image vector have been delivered to the engine, the accumulated values can be read through the AHB register interface. The same process is repeated for all labelled images. Before writing a new labelled image to the engine,  all the data registers need to be cleared and the priming mode flag needs to be pulled high.

Backend Flow

Accelerator Synthesis

Synthesis was run using Cadence Genus, using the scripts provided by SoClabs. The final accelerator area using a packet width of 128 was 139,000 µm². Whilst running synthesis it was found that there was an unsynthesisable construct in the main accelerator engine, which was due to an incorrect definition of an asynchronous reset. This was fixed by ensuring the reset was in the sensitivity list of the always block and an if/else statement was used for the reset case.

Floor Planning

The relative placement of the accelerator to the rest of the SoC required partitioning the die into two power domains, one for the SoC and one for the accelerator, allowing for direct external measurement of the power used by the accelerator. The percentage of the entire ASIC tacken up by the accelerator was about 18%, this was mostly due to the large number of registers used within the accelerator. 

Tapeout

The final GDS design has been sent off for fabrication. The final specs for the design are:

• Max clock frequency: 240 MHz
• Accelerator Power consumption (20% activity): 55.1 mW
• Total SoC Power consumption (20% activity): 146.5 mW
• Leakage Power: 39 µW
• Internal Memory: 48 kB (16 kB Instruction and Data memory + 2x 8 kB accelerator memory)
• Supply voltage: 1.2 V
• Interfaces: UART, FT1248, SWD
• GPIO: 8 pins x 2 ports