Digits in C

Digit recognition in C, step by step

A complete application, in one file of plain C, that recognises handwritten digits with every vector operation running on the Sparsr device.

It reaches 79.58% on the full MNIST test set, after training on all 60,000 training images. The device does integer bit operations throughout. Training reads the data once, with no gradients and no training loop.

This page is the walkthrough. The Getting Started page does the same task in Python, through the PyTorch device. Read this one if you want to see what the library is doing underneath, or if you are writing your own HDC code in C.

The source is one file, examples/mnist/main.c , in the HDC library's repository.

Build and run it

This runs on Linux on x86-64. You supply a host C compiler and the HDC library. A RISC-V toolchain is not one of the things you need. The device programs this example runs are already compiled inside libsparsr_hdc.so, and the library loads them into instruction memory when hdc_init() runs.

Download sparsr-hdc-<version>.tar.gz from the Sparsr Developer Zone and unpack it, then fetch the one source file and compile against the extracted directory:

curl -O https://raw.githubusercontent.com/Sparsr/libsparsr-hdc/main/examples/mnist/main.c

cc main.c -I include -L lib -lsparsr_hdc -lsparsr_host -o mnist_hdc

MNIST itself is about 55 MB and is in no download, so you supply it. Four uncompressed files:

train-images-idx3-ubyte   train-labels-idx1-ubyte
t10k-images-idx3-ubyte    t10k-labels-idx1-ubyte

Both common naming styles work, with a dot or a dash before idx. If your copies end in .gz, gunzip them first.

SPARSR_BACKEND=vm LD_LIBRARY_PATH=lib ./mnist_hdc --data /path/to/mnist

This runs on the Sparsr VM. The library's device programs are RV32I, and the VM runs RV32I.

A full run takes about half a minute. For a quicker look, use a slice:

SPARSR_BACKEND=vm LD_LIBRARY_PATH=lib ./mnist_hdc --data /path/to/mnist --train 6000 --test 1000

What it prints

  encoding   60000 images   (21.2 s)
  training   10 prototypes   (0.3 s)
  testing    10000 images   (4.4 s)

Accuracy: 79.58%  (7958 of 10000 correct)

  digit   trained on   tested   correct   accuracy   prototype bits   lanes
      0         5923      980       882       90.0%              692      48
      1         6742     1135      1054       92.9%              694      48
      2         5958     1032       752       72.9%              714      48
      3         6131     1010       846       83.8%              733      48
      4         5842      982       771       78.5%              693      48
      5         5421      892       523       58.6%              701      48
      6         5918      958       804       83.9%              703      48
      7         6265     1028       839       81.6%              708      48
      8         5851      974       707       72.6%              703      48
      9         5949     1009       780       77.3%              696      48

Digit 1 is the easiest and digit 5 is the hardest, which is what an HDC classifier usually finds on MNIST.

Read the timings as what they are. They are wall-clock seconds on the Sparsr VM, a software model of the device. They say the application runs end to end. They compare it against nothing else, and they are not a benchmark.

The algorithm, in four steps

Each step is one call into the library, and the library runs it as wide instructions on the device.

1. Item memory. Give each of the 784 pixel positions a fixed random hypervector, drawn once with hdc_random_dense() and never changed. Two positions get unrelated vectors, which is what makes the encoding below say which pixels were lit.

2. Encode. An image is the majority vote of the hypervectors of its lit pixels, computed by hdc_bundle_majority(). A bit of the result is set where more than half of those pixels' vectors had it set. Two images of the same digit light similar pixels, so they encode to similar vectors.

3. Train. A class prototype is the majority vote of every training image of that digit. The same call, over thousands of members instead of about 150. One pass over the data, and each class is one vector.

4. Classify. Encode the test image, score it against all ten prototypes with hdc_similarity(), and pick the best. Each score is one wide instruction: the intersection and its population count are the same instruction, because the reduce is a mode on the ALU's result bus. The host never reads a 4,096-bit row back to count its bits.

Before you write your own

Dense codes, and the 48-lane limit

A hypervector is stored in a wide memory row, and a row holds at most 48 non-zero four-byte lanes out of 128. The limit counts lanes, never set bits, and it stores each occupied lane whole, so bits inside an occupied lane are free.

That makes two very different codes storable, and they are not equally good:

This example uses the dense one, and it matters. A dense code has about 768 bits of signal where a sparse one has 48, and it classifies far better. Every vector here stays inside those 48 lanes by construction, because a majority vote can only set bits its members already had. That is why the lanes column above reads 48 on every row.

This is the constraint you will hit first. Design your encoding so its results stay storable, rather than finding out afterwards that they do not.

Why the vote, and not the union

The library gives you two ways to superpose hypervectors, and picking the wrong one here produces a classifier no better than chance.

• hdc_bundle() is the union: OR every member together. Two wide instructions per member, exact, and it never loses a member. But it grows. OR a few hundred images of one digit together and every bit is set, so the prototype says nothing about that digit and every class looks identical.
• hdc_bundle_majority() is the majority vote. It stays informative however many members it has, which is what a prototype needs.

The vote costs 8 to 13 instructions per member against the union's 4, and more for a longer bundle, because its ripple carry is then longer. That gap is not a quirk of the library. Counting how many of N vectors set each of 4,096 bit positions needs an instruction that counts per bit position, and Sparsr's wide instruction set has none, so the device builds 4,096 counters as bit-planes with a carry-save adder. The whole 60,000-image training set is one such vote per class, and it takes 0.3 seconds once the images are encoded.

Options

--lanes is the density knob, and narrowing it costs accuracy directly. Measured on 6,000 training and 1,000 test images:

48 is the widest a wide memory row holds, so 1,536 bits is the most this example can use today.

Where to go next

• The HDC library - the full API, the algebra, and what each operation costs.
• Getting Started - the same task in Python, and how to move it to real hardware.
• Kernel Development - writing your own device programs, if the four library operations are not the ones you need.