Loop Tiling

Loop tiling partitions large loop iteration spaces into smaller blocks, or tiles. This ensures that the data accessed within a tile fits entirely within the processor's cache memory. By reusing this cached data for multiple computations before it is evicted, the technique drastically reduces the number of costly accesses to slower main memory (SRAM/DRAM).

• Example: A large matrix multiplication C = A * B is tiled so that sub-blocks of A and B are loaded into cache once and used for multiple partial calculations of C.

The primary performance benefit is the reduction of cache misses. Without tiling, traversing large arrays can exhibit a strided access pattern that evicts useful data from cache before it can be reused, leading to thrashing. Tiling creates a localized access pattern, maximizing cache hit rates. This directly lowers the required memory bandwidth, a critical bottleneck for energy-efficient inference on microcontrollers where external memory access is power-intensive.

The effectiveness of tiling depends heavily on choosing the optimal tile size. This size is a trade-off constrained by:

• Cache Capacity: The tile's working set must fit within the L1/L2 cache size.
• Translation Lookaside Buffer (TLB) Coverage: To minimize page walk overhead.
• Register File Limits: For further register tiling within the CPU.

Optimal tile sizes are often determined empirically or via auto-tuning frameworks, as they are hardware-specific.

Tiling creates a predictable, blocked computation structure that serves as a foundation for other critical optimizations:

• Loop Unrolling: The inner loops of a tile can be unrolled to reduce branch overhead.
• SIMD Vectorization: Tiled data accesses are often contiguous, enabling efficient use of Single Instruction, Multiple Data (SIMD) instructions.
• Register Blocking: The smallest tiles can be scheduled to reside entirely within CPU registers, the fastest memory level.

This hierarchy of optimizations (register → cache → RAM) is essential for peak performance.

In TinyML, loop tiling is a core optimization within hand-tuned or auto-generated kernels for dense linear algebra operations:

• Convolutional Layers: Tiling across input channels, output channels, and spatial dimensions.
• Fully Connected Layers: Tiling the matrix-vector or matrix-matrix multiplication.
• CMSIS-NN and TFLM Kernels: Libraries like Arm CMSIS-NN and TensorFlow Lite Micro use extensively tiled kernels optimized for Cortex-M cache hierarchies.

It is often combined with operator fusion to manage the memory footprint of intermediate tensors.

Loop interchange is a complementary transformation that changes the nesting order of loops. It is frequently used in conjunction with tiling to achieve the desired data access pattern.

• Goal: Make the inner loop traverse data in the memory layout order (e.g., row-major for C/C++ arrays) to enable unit-stride accesses, which are cache-friendly.
• Combination: First, loops are interchanged to create a stride-1 access pattern. Then, tiling is applied to the new loop nest to exploit cache locality. This two-step process is standard in optimizing compilers for linear algebra.

The manual or automated low-level tuning of fundamental neural network operation implementations (kernels) for a specific microcontroller architecture. This involves writing highly efficient, hand-crafted assembly or C code for operations like convolution and matrix multiplication to exploit specific CPU features, minimize pipeline stalls, and reduce instruction count. It is the foundation upon which higher-level optimizations like loop tiling are built.

A compiler optimization that combines multiple sequential neural network operations into a single, fused kernel. For example, a common pattern is fusing a Convolution, Batch Normalization, and ReLU activation into one operation. This eliminates the need to write large intermediate tensors back to slow main memory, reducing memory bandwidth pressure and overall latency. It complements loop tiling by reducing the number of operations that need to be scheduled and tiled.

A memory management strategy where all buffers for model weights, activations, and intermediate tensors are pre-allocated at compile-time. This eliminates the overhead and non-determinism of runtime memory allocation (malloc/free), prevents memory fragmentation, and is essential for real-time systems. Loop tiling decisions directly influence the size of these statically allocated buffers, as the tile size defines the peak working memory requirement.

An optimization where the output of a neural network layer is written directly into the memory location of its input, reusing the buffer. This drastically reduces the peak RAM footprint during inference, which is often the limiting factor on microcontrollers. Loop tiling must be carefully coordinated with in-place strategies to ensure data dependencies are respected and correct results are maintained when reusing memory.

The peak amount of volatile working memory (RAM) required during the execution of a machine learning model. This includes storage for activations, intermediate tensors, and runtime buffers. It is the primary hardware constraint for TinyML. Loop tiling is a direct technique for controlling and minimizing the RAM footprint by ensuring the working set of data for a tile fits entirely into faster cache or SRAM, avoiding spill-over to slower memory.