Block Processing for L1 Cache Optimization

Block processing breaks large arrays into cache-sized blocks, dramatically improving performance for operations that access the same data multiple times.

Why block processing matters:

• L1 cache is typically 32-48 KB per core
• A 100,000-element double array = 800 KB — far exceeds L1
• Without blocking: each operation reads from main memory (slow)
• With blocking: data stays in L1 cache across operations (fast)

The BlockInit/BlockNext/BlockEnd pattern:

var a, b, c: Vector;
begin
    a.Size(100000);
    b.Size(100000);
    // Fill a, b with data...

    a.BlockInit;     // set up block iteration for a
    b.BlockInit;     // set up block iteration for b

    while not a.BlockEnd do
    begin
        c.Sin(a);      // operates on current block of a
        c.Add(b);      // b's block is in cache alongside a's block

        a.BlockNext;   // advance to next block
        b.BlockNext;
    end;
end;

How it works:

1. BlockInit — records original size, sets Length to the global MtxVecBlockSize (default 800 elements for double precision, 1600 for single)
2. Processing — all operations see only the block-sized view
3. BlockNext — shifts internal pointers to next block (zero-copy, like SetSubRange)
4. BlockEnd — returns true when all blocks processed, restores original size

Block size selection: The block length is the global MtxVecBlockSize variable (unit Math387), preset to 800 elements for double precision and 1600 for single — about 6.25 KB either way, sized so 4-5 vectors fit together in a 32 KB L1 cache. Adjust MtxVecBlockSize to tune for a different cache size.

Common pitfalls:

1. All arrays must be block-iterated together — if a and b are in the same loop, both need BlockInit/BlockNext/BlockEnd.

2. Scalar reductions need accumulation:

// WRONG — only gets sum of last block
a.BlockInit;
while not a.BlockEnd do
begin
    result := a.Sum;   // overwrites on each block
    a.BlockNext;
end;

// CORRECT — accumulate across blocks
total := 0;
a.BlockInit;
while not a.BlockEnd do
begin
    total := total + a.Sum;  // accumulate
    a.BlockNext;
end;

3. Output arrays are also blocked:

a.BlockInit;
c.BlockInit;   // destination must also be blocked!
while not a.BlockEnd do
begin
    c.Sin(a);    // writes to current block of c
    a.BlockNext;
    c.BlockNext;
end;

When to use block processing:

• Arrays bigger than ~30 KB (roughly L1 cache size) AND multiple operations on same data
• Inner loops of algorithms where same vectors are accessed repeatedly
• Before multithreading — block processing is prerequisite for efficient threading

When not needed:

• Single operation on an array (Sin, Add, etc. already internally optimized)
• Small arrays that fit in cache
• Operations that only read data once (single-pass)