Count useful sparse work and the metadata around it
Map nonzeros and events through storage, scheduling, routing, and quality constraints instead of inferring proportional speedup.
On this page
The question for today
What you’ll understand
- Compute sparse storage including indices and row pointers.
- State the independence assumption behind multiplying nonzero densities.
- Distinguish input events, routed messages, synaptic work, and inference latency.
Skipping zeros can reduce arithmetic and movement, but finding the nonzeros and combining their results costs work. Sparse accelerators must encode positions, schedule irregular tasks, and route partial sums. Event-driven machines add another distinction: one input event can create many messages and updates. A small average activity rate can still produce bursts or hot destinations. Define the exact sparse representation and executed work before comparing it with a dense baseline. A percentage of zeros is a workload property, not a runtime or energy guarantee.
Include the representation and load balance
Compressed sparse formats store values together with indices, offsets, or masks. For small values or very short rows, this metadata can rival the useful numeric payload. The right representation depends on sparsity structure, dimensions, and available decoder hardware. Structured blocks may reduce metadata and improve vectorization while retaining some zero arithmetic. Unstructured sparsity may skip more mathematical work but require irregular gather, accumulation, and routing. Include conversion and packing costs if the application does not already produce that format.
Sparse work can also be distributed unevenly. Equal numbers of rows do not imply equal nonzeros or equal accumulation cost, so one processing element can determine completion while others wait. SCNN and EIE demonstrate specific compressed execution mechanisms and must be read with their operator and precision scope attached. Report actual executed operations separately from dense-equivalent operation counts. Calling skipped operations executed throughput can make an architecture appear to exceed a physical limit without explaining the counting convention.
Treat activity distributions as part of the mapping
For a fixed collection of candidate multiply pairs, the fraction with both operands nonzero is a joint probability. Multiplying weight and activation densities is valid only with an appropriate independence assumption for those pairs. Correlated masks can change useful work substantially. Record measured joint patterns by layer and input regime, not just global density. The scheduler may need extra capacity for bursts, and a static average can understate the worst hot-spot load.
An event-driven spiking system has several distinct counters: input spikes, routed packets and hops, destination updates, and the decision’s integration window. One spike can fan out to many targets. Background state updates, synchronization, and idle power can remain between spikes, so inactivity is not automatically free. The Loihi architecture paper describes a particular event-based design; its per-operation and simulation-window quantities cannot be read as whole-system inference energy or wall-clock decision latency without the relevant execution boundary.
Compare sparse designs on matching tasks
Sparsity changes produced through pruning, thresholds, quantization, or event encoding can alter model quality. Evaluate that change using the same dataset and task requirement as the dense or conventional baseline. Include any retraining and conversion process in the released recipe. A sparse kernel benchmark at a fixed mask is useful for mechanism analysis, while an application claim needs representative input-dependent masks and complete inference behavior.
Measure the costs that survive zero skipping: index decoding, memory transactions, irregular reductions, communication, and load imbalance. Report latency distributions when sparse patterns vary per request, and separate low-load efficiency from saturated throughput. For event systems, state the decision window and count all messages and updates needed for that decision. A matched comparison may reveal a useful sparse mapping, but density alone cannot choose the winner without the surrounding representation and scheduling evidence.
Work it through
Metadata dominates the nonzero payload in a tiny matrix
A fictional 64×16 matrix uses 2-byte values and has 128 nonzeros. Store it in CSR with 2-byte column indices and 4-byte row pointers. Compute dense and CSR bytes, the compression factor, and the fraction of stored CSR bytes that is metadata.
The dense matrix has 64×16=1024 values, using 1024×2=2048 bytes. Its nonzero fraction is 128/1024=0.125, so zero fraction is 87.5 percent.
CSR stores 128×2=256 value bytes, 128×2=256 index bytes, and (64+1)×4=260 pointer bytes. Total is 256+256+260=772 bytes.
Dense-to-CSR storage factor is 2048/772≈2.65, rather than eight. Metadata is 256+260=516 bytes, or 516/772≈66.8 percent of CSR storage, before other overheads.
An 87.5 percent zero rate does not imply an eightfold storage or runtime improvement. Position information and the execution mapping determine which savings can actually be realized.
The living notebook
Explore the model
Interactive lab · cache
Indirection can change locality without changing request count
Reset, set Cache capacity C to 4 and Request stride s to 4. Predict a four-address working set and 12 hits among the initial 16 requests; one Step adds a hit. Reset, explicitly set C=4 and s=3, then Step: predict zero hits among 17 requests. The deterministic fully associative LRU trace caps at 4096 requests. It illustrates access locality, not sparse decoding, spike routing, or measured accelerator performance.
- Hits / requests
- 0 / 16
- Hit rate
- 0%
- Address-stream period
- 16 addresses
A fully associative LRU cache starts empty and requests address (i·s) mod 16. Hits move an address to the newest position; misses evict the oldest when full. Playback starts with 16 requests and adds two per second, capped at 4096 explicitly simulated requests. This toy stream is not a processor-cache benchmark. Parameter changes pause playback and recompute the model at the current elapsed time. Reset restores both parameters and returns time to zero. Playback starts paused. Adjust either parameter, then choose Play or Step.
Look forEqual request counts can produce different reuse when index patterns change.
Pause & reason
Check your understanding
Your turn
Try it yourself
For a fixed candidate-pair population, weight nonzero density is 0.2 and activation nonzero density is 0.5. Under independence, what fraction of pairs has both nonzero? Separately, 100 input events each fan out to 8 destination updates: how many updates are required before considering packet aggregation or other overhead?
Take a moment to make a prediction or work it out on paper. Open a hint when you need one.
Give me a hint
Multiply densities only after accepting independence, and keep events distinct from their fanout work.
Compare with the solution
The independent joint density is 0.2×0.5=0.1, or 10 percent of candidate pairs. One hundred events with fanout eight require 800 destination updates under the specified mapping. This is not necessarily 800 network packets, because aggregation, routing, and local expansion can change packet counts.
Keep the idea
Take it with you
- Count indices, offsets, conversion, and imbalance alongside skipped arithmetic.
- Use measured joint sparsity unless independence is justified.
- Keep events, packets, updates, decision windows, and energy boundaries distinct.
Read further
Original sources and deeper explanations to follow at your own pace.
Optional progress, saved in this browser when available. Revisit any lesson at any time.
Lesson not marked complete.