Loop Fission

Loop fission is often a prerequisite for effective kernel fusion. By splitting a monolithic loop, the compiler can isolate specific statement groups. It can then selectively fuse only the loops containing compatible, data-dependent operations into a single, efficient kernel. This reduces the overhead of multiple kernel launches and minimizes intermediate data writes to global memory.

A single loop with many live variables can exceed the limited physical register file of an NPU streaming multiprocessor, forcing register spilling to slower memory. Fission splits the live variable ranges across multiple loops, reducing the number of concurrently live variables in each loop body. This prevents spilling, keeps data in fast registers, and can significantly improve instruction-level parallelism (ILP).

Fission can improve temporal and spatial locality. Separating statements that operate on different arrays or memory regions allows each new loop to have a smaller, more focused working set. This increases the likelihood that the data remains in faster cache levels (L1, shared memory) between loop iterations, reducing accesses to high-latency global memory.

Some statements in a loop may have dependencies (e.g., a recurrence) that prevent parallelization or vectorization, while others are fully parallel. Fission isolates the parallelizable statements into a separate loop, which the compiler can then safely parallelize across threads or vectorize using SIMD/SIMT units. The sequential part remains in its own loop, preserving correctness.

After fission, each resulting loop becomes an independent entity for the compiler's optimization passes. This allows applying different, optimal transformations to each loop:

• Apply loop unrolling to a compute-intensive inner loop.
• Apply loop tiling to a memory-bound loop.
• Apply software pipelining to a loop with long-latency operations. This targeted approach is more effective than trying to optimize a single, complex loop nest.

A common pattern involves a map operation (independent element-wise computation) followed by a reduction (summing across elements). The reduction creates a loop-carried dependency. Loop fission separates these into two loops: a parallel map loop and a subsequent reduction loop. This allows the map phase to be highly parallelized, and the reduction can be optimized using specialized hardware primitives or parallel reduction algorithms.

Loop fission is often a prerequisite for kernel fusion. A single loop may contain statements that cannot be fused with a neighboring loop due to dependencies or differing iteration spaces. By splitting the loop via fission, the compiler creates separate, simpler loops. It can then apply loop fusion to merge one of the resulting sub-loops with an adjacent, compatible loop.

• Example: A loop computing A[i] = B[i] + C[i]; D[i] = A[i] * E[i]; cannot be directly fused with a subsequent loop computing F[i] = G[i] - H[i]; due to the dependency on A[i]. Fission splits it, creating Loop1: A[i] = B[i] + C[i]; and Loop2: D[i] = A[i] * E[i];. Now, Loop1 can be fused with the subsequent loop on F[i], while Loop2 remains separate.

A primary driver for loop fission is to lower register pressure. A complex loop body with many live variables may require more registers than the hardware provides, forcing register spilling to slower memory (e.g., DRAM or cache).

Fission distributes the statements into multiple loops, each with a smaller working set of live variables. This reduces the number of concurrently live values per loop, allowing the register allocator to keep all active variables in fast hardware registers.

• Impact: Eliminates costly spills/fills, improving instruction-level parallelism and reducing memory traffic. This is critical for NPUs and GPUs with limited register files per thread.

Loop fission can expose or enhance parallelism. A single loop may contain a reduction operation (e.g., sum += A[i]) that creates a loop-carried dependency, preventing parallelization of other independent statements within the same loop.

By fission, the reduction is isolated into its own sequential loop. The remaining, now dependency-free statements can be executed in a separate loop that is fully parallelizable or vectorizable.

• Example: Loop body: C[i] = A[i] + B[i]; total += C[i]; The total dependency blocks vectorization. Fission creates: Loop1 (parallel): C[i] = A[i] + B[i]; followed by Loop2 (sequential): total += C[i];

Fission improves data locality and enables kernel tiling by separating statements with conflicting memory access patterns. One set of statements may exhibit high spatial locality on array A, while another set streams through large array B, evicting A from cache.

Splitting the loop allows each new loop to be independently optimized:

• The loop accessing A can be tiled to fit working sets into L1 cache or shared memory.
• The loop streaming B can be optimized for memory coalescing.

This prevents destructive interference in the cache and allows tailored memory hierarchy management for each computational phase.

Complex loops often contain conditional branches (if/else) that lead to warp divergence on SIMT architectures or inefficient predicated execution. Fission can separate the conditional paths into distinct loops, each with a uniform control flow.

• Process: The compiler creates a mask or index list for the true condition in the first loop. It then executes the true branch body in a new loop iterating only over the masked indices, followed by a second loop for the else branch.
• Benefit: Eliminates divergence within a warp, improves instruction-level parallelism, and can enable vectorization for each path. This is a form of control flow optimization.

Software pipelining is a compiler technique to overlap execution of multiple loop iterations by scheduling instructions from different iterations concurrently. An overly complex loop body with many operations and long latency dependencies can create a prohibitively large initiation interval.

Loop fission simplifies the body of each new loop, reducing resource conflicts and dependency chains. This allows the compiler to construct a more efficient software pipeline for each resultant loop, achieving a higher degree of instruction-level parallelism and better hiding of operation latencies (e.g., memory loads).

The inverse transformation of loop fission. Loop fusion combines two or more adjacent loops that share the same iteration space into a single loop. This reduces loop overhead (e.g., increment and branch instructions) and improves data locality by keeping intermediate results in faster memory hierarchies like registers or caches, rather than writing and reading them from slower memory.

• Example: Fusing a loop that computes element-wise squares with a subsequent loop that sums the results.
• Trade-off: While fusion improves locality, it can increase register pressure and potentially reduce opportunities for parallel execution.

A higher-level optimization often enabled by loop-level transformations. Kernel fusion merges multiple, separate computational kernels (e.g., in a GPU or NPU execution graph) into a single, larger kernel. This eliminates the overhead of multiple kernel launches and the costly intermediate data transfers between global memory and registers or shared memory that would occur between kernels.

• Primary Benefit: Dramatically reduces latency and improves throughput by minimizing data movement, which is often the bottleneck.
• Relation to Loop Fission: Loop fission can be a preparatory step, splitting a complex loop so that specific sub-loops can be independently fused with other kernels.

The overarching discipline that includes loop fission. Loop nest optimization is a class of compiler transformations applied to nested loops to maximize data locality, parallelism, and hardware resource utilization. Key transformations include:

• Loop Tiling: Partitions iteration space into blocks to fit caches.
• Loop Interchange: Swaps loop order to improve memory access patterns.
• Loop Unrolling: Replicates loop body to reduce overhead.
• Loop Fission/Distribution: Splits loops for parallelism or reduced register pressure.

LNO uses polyhedral models to mathematically analyze and apply these transformations legally and optimally.

A critical performance problem that loop fission can help mitigate. Register spilling occurs when a compiler's register allocator runs out of fast, on-chip registers. It is forced to “spill” live variable values to slower memory (like the stack or DRAM), causing expensive load/store operations.

• Cause: Loops with many live variables or complex computations exceed the architecture's fixed register file size.
• Fission's Role: By splitting a loop, fission can reduce the number of live variables that must be held in registers simultaneously within each new loop, potentially eliminating spills.
• Impact: Spills can degrade performance by 10x or more due to increased memory traffic.

A hardware capability that loop fission can expose. Instruction-level parallelism is a measure of how many independent instructions a processor can execute simultaneously within a single thread. Modern CPUs use superscalar and out-of-order execution to exploit ILP.

• Fission's Contribution: A large, complex loop body may have long chains of dependent instructions, creating critical paths that limit ILP. Splitting the loop can shorten these dependency chains, allowing the processor's scheduler to find more independent instructions to execute in parallel.
• Contrast with Thread-Level Parallelism: ILP is extracted from a single thread, whereas fission often aims to enable multi-threading across loop iterations.

The empirical method used to decide when to apply transformations like loop fission. Auto-tuning is an automated process that searches a vast space of possible implementation parameters—including whether to apply fission, optimal tile sizes, or unroll factors—to find the best-performing configuration for a specific kernel and hardware target.

• Process: The compiler or a separate tool generates many code variants, executes them with representative data, and selects the fastest.
• Necessity: The performance impact of fission is highly dependent on hardware characteristics (cache sizes, register count) and problem dimensions. Auto-tuning makes this decision data-driven.
• Frameworks: Used in projects like TVM, AutoKernel, and cuBLAS.