EIE: the first accelerator for sparse, compressed networks

Take AlexNet's FC6 layer, a 9216 x 4096 matrix that Han's Pruning left 91 percent zeros. Feed it one input vector. The EIE paper timed exactly this layer on a desktop CPU and a Titan X GPU, once with the dense matrix and once with the sparse one stored in a compressed format and run through the vendor's sparse kernels (MKL and cuSPARSE). The results are the whole motivation for this part.

Removing 91 percent of the multiplications bought only 2.5x on the CPU and 4x on the GPU, not the 11x the arithmetic promises. Worse, once the GPU batches 64 inputs so that the dense kernel can use its full width, the sparse kernel falls 4.8x behind. The paper's summary is blunt: "the irregular pattern caused by compression hinders the effective acceleration on CPUs and GPUs". A general-purpose core cannot skip a zero for free. It has to read an index, compute an address, gather a scattered activation and suffer the cache miss, and that bookkeeping costs more than the multiply it avoided. Custom accelerators before EIE did no better: sparse matrix-vector (SpMV) engines from scientific computing handle the static zeros in the weights but not the run-time zeros in the activations, and DNN accelerators of the day "must expand the network to dense form" before they can run it.

Why memory is the real enemy

The table is the second half of the argument, the one that decides whether a model can run on a phone at all: the 128x gap between an on-chip and an off-chip read dwarfs the multiply itself. A network with one billion connections evaluated at 20 Hz spends 20 x 10^9 x 640 pJ = 12.8 W on DRAM traffic alone, far past any mobile power budget. The lesson that Deep Compression drew from this is that the goal is not fewer FLOPs but a model small enough to live entirely in SRAM: AlexNet shrinks from 240 MB to 6.9 MB and VGG-16 from 552 MB to 11.3 MB, both with no loss of accuracy. Once the whole model fits on chip, every weight read is the cheap kind.

This is the point at which the five questions of the outline slide (what pruning is and how to formulate it, which granularity, which criterion, what ratio per layer, and how to fine-tune) hand over to a sixth that the outline never lists: on what hardware. All five are now answered, in lecture 04-1 and in parts 02 to 06 here, and the constraint ||W_P||_0 <= N has produced a model with few nonzeros. The rest of the lecture is about turning that small N into small time and small energy.

Han's paradigm: co-design the compression and the engine

Slide 56 draws the conventional flow as training on a server, then a big network shipped to a phone for slow, power-hungry inference. The proposed flow inserts a model compression stage between them and replaces the phone's generic processor with accelerated inference. The labels under each stage are five papers by the same group, and reading them as a set is the fastest way to see that compression and the engine were designed together. Neither is useful alone: a compressed model on a GPU gives the Table IV numbers above, and an engine for sparse models with nothing sparse to run is idle silicon. Together they deliver what the slide calls fast and power efficient: EIE with 64 PEs at 800 MHz draws about 600 mW and beats both baselines on the same nine FC and LSTM benchmarks by the margins below.

Three systems, three kinds of sparsity

Slide 54 lists the hardware this section covers, and each entry targets a different sparsity. EIE exploits Weight sparsity and Activation sparsity at the same time, which is what made it the first of its kind. The NVIDIA sparse tensor core accepts only structured M:N sparsity, trading flexibility for a dense-friendly pattern. TorchSparse and PointAcc exploit activation sparsity of a very different origin: point clouds are mostly empty space, so the zeros are in the input, not in the weights.

Look at one fully connected layer of AlexNet, FC7, a 4096 x 4096 matrix of 16.8 M weights that occupies 64 MB in 32-bit floating point. A dense engine stores all 16.8 M values and performs 16.8 M multiply-accumulate operations (MACs) for every input. After Deep Compression, the EIE paper reports that only 9% of the weights survive, about 35% of the input activations are nonzero, and 3% of the original FLOPs remain. EIE reaches that 3 percent by combining three savings that the slide states in round numbers.

The first column is Weight sparsity. Pruning zeroed about 90 percent of the matrix, so a product 0 x A is known to be zero without looking at A. An engine that never stores those weights skips their multiplications for free, hence 10x less computation. The second column is Activation sparsity. About 70 percent of the input vector is zero because it came out of a ReLU, so W x 0 is also known without looking at W. Skipping those columns removes another factor of roughly 1 / 0.3 = 3.3, which the slide rounds to 3x, and the paper measures that skipping them saves about 65 percent of the computation cycles. The third column is Weight sharing: the surviving weights are not stored as32-bit floats but as 4-bit indices into a per-layer codebook of 2^4 = 16 shared values, which is where the crossed-out 2.09, 1.92 => 2 comes from. Both weights snap to the same centroid and are stored as the same index, and 32 / 4 is the 8x memory saving.

The formula packs all three savings into one line. The sum runs only over X_i ∩ Y, the columns that are nonzero in both the weight row and the activation vector, which is the 10x and the 3x. Each weight appears as S[I_ij], a codebook lookup, which is the 8x. The two computation factors multiply to 10 x 3 = 30x, which is why the paper can describe 102 GOPS (giga operations per second) of work on the compressed network as about 3 TOPS (tera operations per second) on the uncompressed one. The 8x from the codebook is a memory factor and does not reduce the operation count.

Why memory shrinks 5x and not 10x

The one number that trips students is the 5x. Ten percent of the weights survive, so why not 10x less memory? Because a nonzero that is stored without its neighbors must carry its position. EIE stores each surviving weight together with a 4-bit relative index (the number of zeros since the previous nonzero in the column), a scheme explained fully in part 08 under Compressed sparse column (CSC). The retrospective on the paper states it directly: "the weight and index are both 4bit giving a 50% storage overhead". Half of every stored entry is bookkeeping, so the 10x from sparsity is halved to 5x. Computation keeps its full 10x, since the index is read but never multiplied.

Static versus dynamic

The italic words on the slide, static and dynamic, are the conceptual core of this part and the key to Static versus dynamic sparsity. The paper defines X_i as the set of columns where row i of W is nonzero and Y as the set of indices where a is nonzero, then says: "The set X_i is fixed for a given model. The set Y varies from input to input." Weight zeros are decided once, when pruning and Fine-tuning finish, so the storage format can be laid out offline with every zero already gone. Activation zeros are made fresh by ReLU for every input, since a different image produces a different set of negative pre-activations. No format can remove them in advance; the engine must find them at run time, which is the job of the Leading non-zero detection unit in part 08.

Slides 58 to 60 show the same small figure three times, and it is worth working it with real numbers before reading the rule. The input is a = (0, a1, 0, a3), the weight matrix is 8 x 4 with eleven nonzeros, and there are four processing elements. Give the symbols values: a = (0, 2, 0, 1), and in the matrix w00 = 1, w01 = 3, w03 = -2, w12 = 5, w21 = -1, w23 = 1, row 3 empty, w42 = 2, w43 = -3, w50 = 6, w63 = 2, w71 = -4. The colors on the slide say who owns what: row 0 is PE0, row 1 is PE1, row 2 is PE2, row 3 is PE3, and row 4 wraps around to PE0 again.

The rule: interleave rows, broadcast activations

The paper states the partition in one sentence: with N PEs, "PE_k holds all rows W_i, output activationsb_i, and input activations a_i for which i (mod N) = k". Rows are dealt out round-robin like cards, so PE0 gets rows 0, 4, 8 and so on. Each PE keeps only the nonzeros of its rows, in its own CSC arrays and its own SRAM, so no PE ever sees the full matrix and no zero weight is stored anywhere. That is the rule of thumb 0 x A = 0 made physical. On the left of slide 58 the same idea appears as hardware: a grid of identical PEs wired to one central control unit that does the scanning and broadcasting (the slide draws 16; the EIE configuration evaluated in the paper uses 64).

The dataflow follows from the ownership. The paper describes it as "scanning vector a to find its next non-zero value a_j and broadcasting a_j along with its index j to all PEs. Each PE then multiplies a_j by the non-zero elements in its portion of column W_j, accumulating the partial sums in accumulators for each element of the output activation vector b." The broadcast is necessary because a_j lives in a column, and a column cuts across every PE's rows: any of the four might hold a nonzero in column j, and only the PE that owns row i is allowed to update b_i. The reward is that every output belongs to exactly one PE, so there is no reduction step between PEs at the end. The paper weighs this explicitly among three ways to partition the matrix and concludes that distributing rows gives "full locality for vector b. The drawback is that vector a needs to be broadcast". The broadcast is cheap: a is about 4 K long and about 30 percent dense, so around 1.2 K broadcasts per layer, each followed by many cycles of local work, and FIFOs decouple the controller from the PEs so the broadcast is not on the critical path.

Zero activations, the Activation sparsity of the previous concept, are handled by the scan itself. A zero is never broadcast, so its whole column is skipped for all N PEs in one decision, which is W x 0 = 0 made physical and what slide 60 highlights by boxing a0 = 0. In part 08 that scan is the Leading non-zero detection unit, and the word "logically" on slide 59 is a reminder that the tidy 8 x 4 grid is the logical view only. Physically PE0 holds a compressed slice with five entries and never sees the zeros that the figure draws.

Why interleave rather than block

The paper weighs three partitions (Section VII-A). Splitting by columns gives each a_j to one PE but needs a reduction across PEs and becomes unbalanced because a is 70 percent zero. 2D blocks need both a broadcast and a reduction. Splitting by rows keeps each b_i local and costs only one broadcast per column. Dealing rows out round-robin (rather than in contiguous blocks, a choice the paper does not justify explicitly) spreads each column's nonzeros across PEs. The small example already shows the residual problem: column 3 gives PE0 and PE2 two multiplications each while PE1 and PE3 get none, and over the whole product PE1 does nothing at all. The busiest PE sets the pace of every broadcast. This is the Load balance issue that the activation queue in part 08 softens by letting PEs run ahead, and that ESE later attacked at pruning time.