Inside EIE: dataflow, the PE and its storage formats

Start with the picture from part 07. An 8 x 4 weight matrix is split across four processing elements by interleaving rows: PE0 owns rows 0 and 4, PE1 rows 1 and 5, PE2 rows 2 and 6, PE3 rows 3 and 7. In general, with N PEs, PE k holds every row i with i mod N = k, together with the output b_i it will produce and the input a_i of the same index (Han et al., 2016). The input vector for the layer is a = (0, a1, 0, a3): two of its four entries are zero, which is typical of what ReLU leaves behind.

The whole computation is a sequence of broadcasts. A central control unit scans a for its next nonzero, finds a1 at index 1, and sends the pair (a1, 1) to every PE at once. Each PE then does something entirely local: it looks up column 1 of its own rows in compressed form, multiplies each nonzero weight it finds there by a1, and adds the product into the output entry for that row. When every PE has finished (or, as the next concept shows, has at least queued the work), the controller finds the next nonzero, a3, and the same thing happens for column 3. Columns 0 and 2 are never visited, because the activations that would multiply them are zero, and W x 0 = 0. Inside each visited column, the zero weights are never visited either, because 0 x A = 0 and the compressed format simply does not store them.

Written as a rule, each output is a sum over only the intersection of two index sets. X_i is the set of columns where row i has a nonzero weight, fixed once pruning is done, and Y is the set of nonzero activations, which changes with every input. That is the static versus dynamic distinction from part 07 written into the arithmetic: weight sparsity shrinks X_i before deployment, activation sparsity shrinks Y at run time, and the hardware only pays for pairs in both.

The S[I_ij] inside the sum is a reminder that the PE never stores the weight itself, only a 4-bit code into a shared table, which the third concept unpacks. Notice also what the four PEs did not do: they never exchanged a partial sum. Every product for row i is produced in the one PE that owns row i, so the only communication in the whole layer is the broadcast of (a_j, j) pairs, which the paper carries on an H-tree so that every PE receives it in the same cycle (Han et al., 2016).

Now stand inside PE0 while (a3, 3) arrives. The pair lands in a small queue at the front of the PE. The index 3 is used to look up where column 3 starts and ends in this PE's compressed storage. Those two addresses fetch the entries for the column, each an encoded weight plus a relative row index. The weight code is expanded to a real number, the relative index is turned into an absolute row, the multiply and add happen, and the result is written into the destination register for that row. When the layer is complete, ReLU and a leading nonzero detector turn the destination registers into the next layer's input. The slide draws this as the queue, then four dashed regions, then a ReLU and detector tail, and every EIE exam answer should be able to name the five stages in order.

The same trace, with the paper's bit widths

The queue head is (a3, 3). The pointer unit reads two 16-bit pointers, p3 and p4. In PE0's arrays for the running example they are 3 and 5 (the third concept derives them), so column 3 occupies entries 3 and 4. The sparse matrix unit fetches those entries. Each is 8 bits: a 4-bit weight code and a 4-bit relative index. The SRAM is 64 bits wide, so a single read returns eight entries; the high 13 bits of a pointer select the SRAM row and the low 3 bits select the entry inside it, and the unit hands one entry per cycle to the arithmetic unit (Han et al., 2016). Why eight? With 64 PEs and about 10 percent density, a column of length 4096 leaves each PE about 6.4 nonzeros per column, so one 64-bit read usually covers a whole column.

The two entries for column 3 are (code of w03, x = 0) and (code of w43, x = 0). The weight decoder expands each 4-bit code through the layer's 16-entry table into a 16-bit fixed-point value. The address accumulator keeps a running sum of the relative indices plus one per entry, producing local rows 0 and 1, which are absolute rows 0 and 4 for PE0. The multiplier forms a3 x w03, the adder adds it to destination register 0, then a3 x w43 is added to destination register 1. Had two consecutive entries hit the same register, the adder's output would have been routed straight back to its input through the bypass path instead of waiting for the register write (Han et al., 2016).

The activation read and write unit is two register files, source and destination, each holding 64 activations of 16 bits, enough for a 4096-long vector across 64 PEs. The destination file collects this layer's outputs while the source file supplies this layer's inputs; when the layer is done they exchange roles, so no activation is ever copied between layers. Vectors longer than 4096 spill into a 2 KB activation SRAM and are processed in batches (Han et al., 2016).

The pointer read deserves one more sentence, because it is a favorite exam question. A single-ported SRAM serves one read per cycle, but every column needs two pointers. EIE stores the pointers in two banks and uses the least significant bit of the address to choose the bank. Since p_j and p_(j+1) are adjacent addresses, they always land in different banks, and both are read in the same cycle without paying for a dual-ported (larger, hotter) memory (Han et al., 2016).

The last two rows explain the shape of the whole chip. SRAM is 93 percent of a PE's area and 59 percent of its power, and 64 PEs fill about 40.8 mm² at 590 mW (Han et al., 2016). That is the point, not a flaw: the paper's energy argument starts from the fact that a 32-bit DRAM access costs 640 pJ against 5 pJ for SRAM, about 128 times, which the paper rounds to a 120x energy saving, so a compressed model that fits entirely on chip wins before any arithmetic trick is counted. Everything in this PE is arranged to keep the model small enough to stay there.

Go back to the worked example and count the multiplies per PE: 3, 0, 3, 1. That uneven count is the first of four problems the PE design must solve, and the slides walk through the solutions one dashed region at a time: a queue for load balance, a detector for activation sparsity, a compressed format for weight sparsity, a decoder for weight sharing, and finally the arithmetic and write-back that ties them together. The storage format is the thread through all of them, so this concept ends with its bit widths.

Load balance: let the fast PEs run ahead

Because rows are interleaved, each PE may hold a different number of nonzeros in any given column. In the example, the a3 broadcast gives PE0 and PE2 two multiplies each and PE1 and PE3 none. If the controller waited for every PE before broadcasting the next activation, PE1 and PE3 would idle for two cycles on every such column. The activation queue is the fix. Each PE holds a FIFO of broadcast (value, index) pairs, the controller keeps broadcasting as long as no queue is full, and a PE with little to do in one column simply moves on to the next pair in its queue while a busier PE catches up. The paper puts it plainly: the queue lets each PE build up a backlog of work to even out load imbalance, and the broadcast is disabled only if some PE's queue is full (Han et al., 2016).

The paper measured this. It swept the queue depth from 1 to 256 and defined load balance efficiency as one minus the starvation bubble cycles over the total. At depth 1, around half of all cycles are idle; efficiency climbs steeply to depth 8 and flattens afterwards, so 8 was chosen as the queue depth (Han et al., 2016, Figure 8). The visual above is illustrative and uses small integer loads, but the shape of the result is the paper's: a shallow queue wastes about half the machine.

Activation sparsity: never queue a zero

The queue only helps if what enters it is worth doing. Zero activations must be filtered out before the broadcast, and this is the job of leading nonzero detection. It is distributed, not central: each group of four PEs does a local detection over the activations it stores, the results feed up a quadtree of detector nodes, and the root of that tree is the central control unit, which selects the next nonzero and broadcasts it over an H-tree so that every PE receives it in the same cycle. For64 PEs that is 21 detector units (16 leaves, 4 intermediate, 1 root), each tiny at about 189 µm² and 0.023 mW (Han et al., 2016). Since about 70 percent of activations are zero after ReLU, this alone removes roughly two thirds of the potential broadcasts, which is the 3x factor in the paper's energy accounting.

Weight sparsity: CSC with a relative index

The pointer read and sparse matrix access regions implement the compressed format, a variation of compressed sparse column. Standard CSC, as in SciPy's csc_matrix, stores three arrays: the nonzero values, the row index of each, and a pointer array such that column j occupies positions p_j to p_(j+1) - 1 (SciPy). EIE keeps the values and the pointers but replaces the absolute row index with a relative one: for each nonzero, the number of zeros since the previous nonzero in that PE's slice of the column. Both the value and the relative index are 4 bits. When more than 15 zeros precede a nonzero, the encoder inserts a padding entry with value 0 and index 15 and continues counting from there (Han et al., 2016).

Why a relative index at all? For a layer with 4096 rows split across 64 PEs, each PE-local row still needs 6 bits to name absolutely, and the absolute row across the whole matrix needs 12. A 4-bit relative index cuts even the local figure by a third, and, more importantly, matches the 4-bit weight code so that one 8-bit entry carries both. The price is the occasional padding entry, and the paper notes that padding zeros are treated as nonzeros and lead to wasted computation; its Figure 12 shows that more PEs mean fewer padding zeros, because each PE's slice of a column is shorter and long gaps become rarer (Han et al., 2016).

Weight sharing: 4-bit codes, 16-bit arithmetic

The value stored in each entry is not a weight. It is a 4-bit index into a per-layer table of 16 shared weights, the codebook produced by the k-means quantization of Deep Compression (Han, Mao and Dally, 2016). The weight decoder reads the code out of the sparse matrix entry and looks up the 16-bit fixed-point value it stands for, every cycle, on the way to the multiplier. This is the 8x memory factor in the paper's accounting: the SRAM holds 4-bit codes, the multiplier sees 16-bit numbers, and the layer's whole set of distinct weight values is 16 entries long.

The 16-bit choice is not arbitrary. The paper reports that 16-bit fixed point costs half a percentage point against 32-bit floating point, while 8-bit fixed point collapses to 53 percent, and that a 16-bit fixed multiply uses about 5 times less energy than a 32-bit fixed multiply and 6.2 times less than a 32-bit floating point one (Han et al., 2016). Four bits of storage and sixteen bits of arithmetic is the compromise that keeps both the SRAM and the accuracy where they need to be.

Arithmetic and write-back

The last region closes the loop. The arithmetic unit computes b_x = b_x + v x a_j, where the address x comes from the address accumulator's running sum of relative indices and v from the decoder. The destination register selected by x is read, the product is added, and the sum is written back. If two adjacent cycles select the same accumulator, the bypass path forwards the adder output directly to its input so the second add does not wait on the register (Han et al., 2016). At the end of the layer the destination file becomes the source file, ReLU and the detector run over it, and the first nonzero of the next layer enters the queue.