Tiling turns one large matrix product into many smaller pieces. Parallelism adds a second question: which worker is allowed to update each piece of the result?
A clean answer is the owner-computes rule:
Assign every C tile to exactly one thread. That thread performs every K contribution for that tile.
Open the interactive thread-owned matrix multiplication demo
The demo uses a small matrix so ownership is visible. Advance one parallel wave at a time and watch several threads read overlapping parts of A and B while writing disjoint regions of C.
The dangerous way to split the work
Dense matrix multiplication can be written as a sequence of outer products:
for k = 0 .. K-1
C += A[:,k] outer-product B[k,:]
This form is attractive because every k produces a large, parallel rank-1 update. But a naive split over k is unsafe:
thread 0 handles some k values
thread 1 handles other k values
Both threads then update the same C elements. If they perform ordinary read-modify-write operations at the same time, one update can overwrite another. The result is a data race.
Locks or atomics could serialize the writes, but the synchronization cost would sit directly inside the hottest part of the algorithm. Another option is to give every thread a private full-size C matrix and reduce them later, but that multiplies memory use and adds a second large pass.
The better decomposition changes what the threads own.
Split C into independent tiles
Suppose C has shape M × N. Choose tile dimensions TM × TN, then divide C into a grid:
C tile (0,0) C tile (0,1) C tile (0,2)
C tile (1,0) C tile (1,1) C tile (1,2)
C tile (2,0) C tile (2,1) C tile (2,2)
Each output tile has a corresponding row range from A and column range from B. To complete one C tile, its owner must accumulate across the entire K dimension:
for each C tile owned by this thread
zero or load the local C tile
for k = 0 .. K-1
C_tile += A[tile_rows,k] outer-product B[k,tile_columns]
store the completed C tile
The crucial detail is where the parallel loop lives. It surrounds C tiles, not k.
What each thread reads and writes
For a C tile covering rows ii .. ii+TM-1 and columns jj .. jj+TN-1, the owner reads:
- A values from rows in that tile and every k,
- B values from every k and columns in that tile, and
- optionally the initial C tile if the operation is
C = beta × C + alpha × A × B.
It writes only:
C[ii:ii+TM, jj:jj+TN].
Other threads may read the same A or B cache lines. Shared reads are safe because A and B are immutable during the multiplication. The safety requirement applies to writes: no two threads may own overlapping C regions.
This gives a simple invariant that can be checked without understanding the processor’s timing:
owner_for_C(i,j) is unique for every valid result coordinate
If the invariant holds, arbitrary thread interleaving cannot create a C write race.
A parallel wave in the demo
The interactive page groups simultaneous work into waves. In one wave, each active thread:
- selects its currently owned C tile,
- reads one A column slice for that tile’s rows,
- reads one B row slice for that tile’s columns,
- forms a small outer product, and
- accumulates it into only its own C tile.
Several threads can be active in the same wave. Their A and B highlights may overlap because reads can be shared. Their colored C write regions remain disjoint.
The No-stomp audit makes the invariant explicit. It lists every active thread’s output region, making any overlap visible instead of relying on the animation alone.
How a very large matrix is scheduled
A practical implementation may have far more C tiles than threads. For example, a 4096 × 4096 result with 128 × 128 C tiles contains:
32 tile rows × 32 tile columns = 1,024 C tiles
With 16 threads, the runtime assigns multiple tiles to each worker. Common schedules include:
- Static round-robin: tile number t goes to thread
t mod thread_count. - Static blocked: each thread receives a contiguous group of tile rows or tile indices.
- Dynamic queue: threads request another unclaimed tile when they finish.
Static schedules have almost no scheduling overhead and predictable ownership. Dynamic schedules can balance irregular edge work or heterogeneous cores, but the queue adds coordination. In either case, a tile must be claimed by only one worker at a time.
The demo uses a deterministic assignment so the colors and thread lanes remain easy to follow.
Edge tiles remain independent
If M or N is not divisible by the tile dimensions, the bottom and right tiles are partial. Their owners use bounds checks or predicates for the valid lanes.
A partial tile does not change the ownership rule. Its rectangle is simply smaller:
row_end = min(ii + TM, M)
col_end = min(jj + TN, N)
No padding is required for correctness. Some optimized kernels do pack or pad temporary panels, but only valid C coordinates are ultimately stored.
Where the K dimension belongs
Each thread processes all K contributions for its owned C tile. This has several benefits:
- partial sums can remain in registers or a local accumulator,
- the final C tile can be written once,
- no atomics are required,
- no cross-thread reduction is required, and
- correctness does not depend on execution order between threads.
K may still be blocked into cache-sized panels:
for each owned C tile
for each K panel kk
for k inside that panel
accumulate the outer product
Blocking K changes data reuse. It does not change ownership. The same thread remains responsible for the tile from its first partial sum through its final store.
Cache and locality consequences
Owner-computes removes write races, but schedule quality still affects performance.
Nearby C tiles may reuse parts of A or B. Assigning a worker several tiles in the same tile row can reuse an A panel. Assigning tiles in the same tile column can reuse a B panel. Packing and shared-cache behavior influence which direction is best.
There is also false sharing to consider. Two threads may own different C elements that happen to occupy the same cache line, especially with very small or awkwardly aligned tiles. They are not logically racing, but the cache-coherence protocol may repeatedly move that line between cores. Tile dimensions and alignment should therefore keep ownership boundaries away from heavily shared cache lines when possible.
Mapping the pattern to matrix hardware
The owner-computes pattern fits processors with matrix accumulators particularly well. An ARM SME-style kernel can:
- enter streaming mode,
- zero a ZA accumulator tile,
- loop over k,
- load an A vector slice and a B vector slice,
- outer-product-accumulate them into ZA, and
- store the finished tile to C.
The hardware microtile may be much smaller than the cache-level C tile. A thread can own a larger C region and cover it with multiple accumulator-sized microtiles. The invariant remains the same: another thread never writes those C coordinates.
The repository accompanying the demo includes a C++ owner-computes example with portable and guarded SME/SME2 paths.
When splitting K can still make sense
There are cases where a matrix is so narrow in M and N that it has too few C tiles to occupy all workers. A split-K algorithm can expose more parallelism, but it must give each worker a private partial result and then reduce those partials safely.
That is a deliberate trade-off:
- more parallel work,
- more temporary storage,
- an explicit reduction step, and
- usually more memory traffic.
Split-K is not wrong. It is simply a different algorithm with synchronization and reduction costs. Owner-computes is the simpler default whenever the C tile grid already provides enough parallelism.
The key lesson
The outer-product mechanism and safe parallelism fit together when the responsibilities are separated correctly:
- use outer products inside a C tile,
- distribute C tiles across threads,
- keep A and B read-only, and
- keep the full K accumulation with the tile’s owner.
This turns race freedom from a timing hope into a structural property of the schedule.
Launch the thread-owned C-tile visualizer
For the single-threaded foundation, read how tiled matrix multiplication works.