research28 min studyLesson 999 in Engineering

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

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.

DCSR=nnz(bv+bi)+(r+1)bpD_{\rm CSR}=n_{\rm nz}(b_v+b_i)+(r+1)b_p
This simple compressed-sparse-row storage model counts nnz values, one column index per value, and r+1 row pointers. bv, bi, bp are bytes per entry. It excludes alignment, allocator, padding, and additional runtime metadata; dense storage is r×c×bv for r rows and c columns.↔ Scroll wide equations horizontally.

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.

ρuseful=Pr⁡(W≠0, A≠0),W⊥A ⟹ ρuseful=ρWρA\rho_{\rm useful}=\Pr(W\ne0,\ A\ne0),\qquad W\perp A\ \Longrightarrow\ \rho_{\rm useful}=\rho_W\rho_A
W and A denote operands drawn from the explicitly defined candidate-pair population; densities are dimensionless. Without independence, the product rule does not follow. Useful pair counts still do not account for metadata, scheduling, or accumulation overhead.↔ Scroll wide equations horizontally.

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.

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.

  1. 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.

  2. 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.

  3. 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.

The result

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.

Explore the model

Interactive lab

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.

Indirection can change locality without changing request countA 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. Current readings: Hits / requests: 0 / 16; Hit rate: 0%; Address-stream period: 16 addresses. All parameters are adjustable with the labeled controls below.Fully associative LRU cache after 16 deterministic requests: 0 hits and 16 misses.Most recent 16 requestsaddress = i × 3 mod 160M3M6M9M12M15M2M5M8M11M14M1M4M7M10M13MCurrent cache order · oldest → newest471013Latest address 13 · miss: inserted as newestToy address stream · period 16 · starts empty
Cached addressMiss / evictionMost recent request
Hits / requests
0 / 16
Hit rate
0%
Address-stream period
16 addresses
t = 0 s

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.

Check your understanding

When may the useful nonzero-pair density be computed as weight density times activation density?

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.

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.