MinUn: Accurate ML Inference on Microcontrollers

In plain words

A microcontroller has only a few kilobytes of working memory, and a standard machine learning runtime needs more than that. This paper describes a compiler that turns a small model into plain C++ code sized for such a chip. The compiler stores most of the model's numbers with few bits and keeps a small set of important ones with more bits, so accuracy stays close to the full-precision model.

Each intermediate result of the model is given a place in one fixed block of memory, and the compiler searches for a placement that wastes no space between results. The authors compare the output with other tiny-model compilers on several datasets and on a large image classifier, and report lower memory use with similar accuracy. The number format is pluggable, so the same method can be used with other formats.

TL;DR

MinUn compiles a model description into C++ for ARM microcontrollers. It decides, per tensor, whether to store values at a low or a high bitwidth, using a search guided by value error and tensor size under a RAM limit. It then assigns memory addresses by solving an exact-cover problem, so the scratch buffer has no fragmentation. Author-reported results show lower peak RAM than earlier TinyML compilers at similar accuracy, and a 3.81x RAM reduction on SqueezeNet relative to float32 §6.7 app. D. The evaluation uses a small set of models and datasets, and the paper's code link could not be verified (see Paper vs code).

Problem

Microcontrollers in the paper have very little RAM: an Arduino Uno has 2 KB §1 app. D. Interpreter-based frameworks such as TensorFlow need more memory than that and cannot run there §1. Reducing every tensor to 8 bits loses too much accuracy for some models, notably an RNNPool-based face detector §1 §6.3. Choosing precisions tensor by tensor gives 2^N combinations for N tensors, so an exhaustive search is not practical §1 §4.1. Fixed scratch-memory layouts waste RAM, and greedy allocation can fragment memory and miss a feasible layout §1 §4.3. The search takes a RAM limit and an accuracy measurement as its inputs §4.1.

Method

The compiler takes a program in a small ML description language, builds an abstract syntax tree, chooses a bitwidth for every tensor, lays tensors out in a scratch buffer, and emits device C++ that is cross-compiled for the board §3. The paper describes the bitwidth search (called Haunter) as three stages §4.1:

1. Preprocessing (Stage I). Fix the data-dependent parameters. For posits these are the exponent size es for the 8-bit and 16-bit formats, chosen by measured accuracy §4.1.1 alg. 1. For fixed-point, per-tensor scales come from profiling the float code over a set of inputs, following the earlier Shiftry approach §4.1.1.
2. Heat map (Stage II). Run the code with every promotable tensor at the high bitwidth and again with every tensor at the low bitwidth, logging tensor values in each run §4.1.2 alg. 2. For each tensor, take the absolute difference between the two runs element by element, then the 95th-percentile deviation, and divide it by the tensor's element count. This is the promotability score §4.1.2 alg. 3.
3. Promotion (Stage III). Sort tensors by promotability to get the promotion order. Promote tensors cumulatively in that order while the estimated memory use stays under the soft-limit threshold. Tensors that cross the threshold are collected as overshooting tensors §4.1.3 alg. 4. The search then tries each overshooting tensor on its own and then all of them together, measuring accuracy each time, and returns the configuration with the best accuracy §4.1.3 alg. 5.

Memory placement is a separate step that uses the bitwidth map §4.3:

• Each tensor is a rectangle on a canvas whose horizontal axis is the program's instruction index and whose vertical axis is bytes. Its width is its live range and its height is its size §4.3.
• An exact cover of the canvas that uses the minimum height M gives an offset for every tensor in a single scratch buffer of M bytes §4.3.
• The authors solve the cover with Knuth's Algorithm X, using dancing links. Tensors are visited in decreasing order of rectangle area §4.3.
• Sizes can be rounded up to a multiple of a coarsening constant k, which shrinks the canvas to M/k rows. With k = 1 the search is exact §4.3.

# Haunter: choose a bitwidth per tensor  [§4.1] [alg. 1-5]
# Input:  tensors, memory_limit, soft_limit, low_bits, high_bits
# Output: rho, a map from each tensor to low_bits or high_bits

def haunter(tensors, memory_limit, soft_limit, low_bits, high_bits):
    # Stage I: fit data-dependent parameters, e.g. posit es  [alg. 1]
    preprocess(low_bits, high_bits)
    # Stage II: run all-high and all-low, log values per tensor  [alg. 2]
    high_values, low_values = create_value_maps(low_bits, high_bits)
    # Rank by 95th-percentile error over element count  [alg. 3] [§4.1.2]
    order = promotion_order(high_values, low_values)
    # Stage III: promote in order while under the soft limit  [alg. 4]
    overshooting = promote_within_limit(order, memory_limit, soft_limit)
    # Try each overshooting tensor alone, then together  [alg. 5] [§4.1.3]
    candidates = explore(order, overshooting, memory_limit, soft_limit)
    # Keep the candidate with the best measured accuracy  [alg. 5]
    return best_accuracy(candidates)

# Lower bound on the scratch size for one bitwidth map  [§4.3]
# Input:  tensors with size in bytes and live range [start, end]
# Output: budget M in bytes, the minimum height of the stacked live tensors

def min_budget(tensors, num_instructions, k):
    # Tight stacking of live tensors at each instruction, in units of k  [§4.3]
    budget = 0
    for instr in range(num_instructions):
        alive = [t for t in tensors if t.start <= instr <= t.end]
        height = sum(ceil(t.size / k) for t in alive)
        budget = max(budget, height)
    return budget

Both blocks above are our reading of the text and of alg. 1 to alg. 5. The paper does not give the lower-bound routine as code.

Hyperparameters

Results

Author-reported. Setup: the headline comparison is SqueezeNet, an ImageNet-scale CNN, evaluated on 48,000 RGB images across 1000 classes, against a float32 gold standard §6.7. Baselines are TensorFlow Lite with 8-bit zero-skew §6.7 and Shiftry, which uses 8- and 16-bit fixed-point §6.7.

The 1.44 MB first-fit figure is from the text §6.7, not from the table. The text reports that exact-cover placement gives about 20% lower RAM than first-fit on this model §6.7.

Fixed-point results on the classification and face models, run at the Shiftry RAM limit. Each column is the average accuracy or MAP drop, relative to MinUn's fixed-point result, for that search strategy:

Posit results, same RAM limit and column meaning, relative to MinUn's posit result §6.5:

Posit configuration against float32, half precision and bfloat16 for each model app. D. Values are the peak RAM figures from the table, in KB or as printed:

Other headline figures stated in the text: the face-detection model's RAM drops from about 600 KB to about 180 KB §1; the average accuracy drop of MinUn fixed-point models stays within a fraction of a percent except RNNPool §6.5; compilation time for fixed-point code drops by 33% to 45% on classification models, and is about 2% higher on the face model §4.2 §6.6 app. D. Inference latency on the boards changes by under 1% for FastGRNN and RNNPool, and by about -7% and -10% for ProtoNN and Bonsai, as printed §6.6 app. D.

Paper vs code

The paper's footnote links github.com/krantikiran68/EdgeML, branch shikhar_posit_vbw_haunter §1. Not verified. The default branch of that repository (commit e5c7bd7c56884ca61f6d54cedb0074553cfdc896 at clone time) is a copy of Microsoft's EdgeML with a Microsoft copyright notice in License.txt and no files named for Haunter or MinUn; a clone of that default branch was removed. The named branch's top-level listing shows no Haunter or MinUn folder, and GitHub code search requires a sign-in, so the Haunter source could not be read. No commit is recorded for the MinUn branch. Until someone reads that branch, every code-level claim (algorithm details, defaults, the lower-bound routine above) rests on the paper text alone.

Pitfalls

• Section and table numbers come from the LaTeX source order, not from the compiled PDF, which we did not check. Table numbers are cited by section and caption where the source order is uncertain.
• Memory numbers disagree across the paper. The introduction gives about 600 KB to about 180 KB for the face model §1. The appendix gives 614K to 192K for posit Face-B and 218 KB to 165 KB for fixed-point Face-B app. D. Check which configuration a figure refers to before implementing or citing it.
• The 2.9x to 5.1x reduction claim. The text says the posit configuration reduces peak RAM by 2.9x to 5.1x even against half precision or bfloat16 §6.4. The table's own RAM columns give smaller ratios against those 16-bit baselines, roughly 1.3x to 4x (for example, 1280 to 960 bytes for FastGRNN MNIST-10 and 160 to 40 bytes for Bonsai CIFAR-2). Treat the 2.9x to 5.1x range as unverified against the table.
• Accuracy is measured on different sets. Accuracy and drop figures for different models come from different validation or test splits. The face model uses 20% of SCUT-HEAD Part-B (405 images) §6.2. The paper does not analyse the variance of these measurements.
• Overshoot test boundary. In the promotion helper, a tensor is reverted to the low bitwidth when the usage is strictly above memoryLimit * softLimitFactor, and it is added to the overshooting list when the usage is at or above that value alg. 4. A tensor that lands exactly on the threshold therefore stays high and is still listed as overshooting.
• Scope of the state map. The promotion helper assigns to a local map rho. The outer procedure reads and writes its own rho alg. 4 alg. 5. The paper does not say whether the helper's changes persist. Implement the outer loop as the only owner of the map unless the code shows otherwise.
• Heat-map pseudocode is ambiguous. The inner loop in the heat-map routine iterates over two sets together, and the paper does not say how to pair the low and high values element by element alg. 3. The 95th-percentile method (nearest rank or interpolation) is not stated.
• Tie-breaking in the final choice. The routine that returns the best configuration does not say how ties are broken alg. 5.
• Exact cover can be slow. Algorithm X is exponential in the worst case. The authors cap it at 2 hours §5, and a complexity analysis of the search is in §4.2. The paper does not give a worst-case runtime for the packing step.
• Coarsening can lose the optimum. A coarsening constant k greater than 1 rounds tensor sizes up and can produce a larger scratch buffer than necessary. The face models use k = 64 §5 §4.3.
• Lower bound is not always achievable. The minimum height computed by stacking live tensors is a lower bound §4.3. The paper does not say what happens when no exact cover exists at that height. The text implies a larger budget is then needed, but gives no procedure.
• Fixed-point overflow is ruled out. The fixed-point search does not allow overflow. The authors report a loss of about 2% on FastGRNN HAR-6 from this, which is the only case where the fixed-point average drop is negative for FastGRNN §6.8.1.
• Only two bitwidths are searched. The search uses one low and one high bitwidth. More options were tried for posits and gave no measurable benefit in the paper's experiments §6.8.2.
• Per-tensor width is uniform. Within one tensor all elements share one bitwidth, to avoid per-element bookkeeping §1.
• Posit exponent support is library-limited. For 9-, 10-, 12- and 32-bit posits, only es = 2 was available in the posit library the authors used §5.
• No latency for the face model on the Uno. The Uno latency table covers fixed-point classifiers only app. D.
• The paper gives no variance over runs. All results are single reported values. The posit accuracy targets are within 0.2% of float32 for each dataset, which is a narrow band relative to the sample sizes.
• Compile time for the face model got slightly worse. The reported change for RNNPool compile time is -2.25% app. D, so do not assume the search is faster for every model.

Lineage

• Builds on: the TensorFlow Lite zero-skew 8-bit scheme §2 §A; Shiftry's data-driven fixed-point scales and its 8/16-bit assignment §2 §4.1.1 §6.5; SeeDot's 16-bit fixed-point compilation §2; posit arithmetic §A; Knuth's Algorithm X with dancing links for exact cover §4.3.
• Compared against: TensorFlow Lite zero-skew 8-bit §6.7; Shiftry, fixed-point 8/16-bit §6.5 §6.7; and a size-based and accuracy-based bitwidth search on the same models §6.5. SeeDot is not compared, because the authors say it is guaranteed to use more RAM than MinUn §6.
• Superseded by: not stated.