Cost Model for Fusion

This is the fixed latency and resource cost of submitting a kernel for execution on a GPU or accelerator. A primary goal of fusion is to amortize this overhead by reducing the total number of kernel launches. The cost model must estimate the saved overhead against the increased execution time of a larger, fused kernel.

• Quantifiable Latency: Includes driver API calls, argument marshaling, and scheduler queueing.
• Amortization Benefit: Most significant when fusing many small, rapid-fire operations.

Fusion can dramatically reduce the volume of data movement between slow global memory and fast on-chip caches (L1, L2, shared memory). The cost model analyzes the dataflow graph to estimate savings from keeping intermediate tensors resident in registers or cache.

• Intermediate Tensor Elimination: Fusing a producer and consumer operator avoids writing a full tensor to global memory and immediately reading it back.
• Cache Reuse Potential: Evaluates if fused operations can reuse data across multiple computational steps within the same kernel.

This factor assesses whether the fused kernel's performance will be limited by memory bandwidth or computational throughput. Arithmetic Intensity (FLOPs per byte of DRAM access) is a key metric.

• Memory-Bound Fusion: Profitable when fusing light, elementwise ops (e.g., ReLU, Add) with a heavy operation (e.g., Conv). The light ops become 'free' as they hide behind memory latency.

• Compute-Bound Fusion: May be unprofitable if fusing already compute-saturated operations leads to register spilling or underutilized parallelism.

A larger, fused kernel competes for finite hardware resources. The cost model must predict constraints to avoid performance degradation.

• Register Pressure: Combining operations increases register usage per thread, which can limit active thread occupancy.
• Shared Memory Usage: Fused kernels may require more shared memory for communication between warps, reducing the number of concurrent thread blocks.
• Instruction Cache Pressure: Very large kernels may exceed the capacity of the instruction cache, causing thrashing.

Fusion can reduce opportunities for parallel execution. The cost model evaluates the parallelizability of the fused operation group.

• Horizontal Fusion: Merging independent operators that could run in parallel may reduce overall throughput.
• Vertical Fusion: Chaining dependent operators is typically safe and beneficial.
• Loop Fusion Implications: Merging loops affects tiling, vectorization, and parallel loop scheduling strategies.

Certain operator sequences have known, hand-tuned fused implementations. The cost model assigns high profitability to these canonical patterns.

• Fused Conv-BN-ReLU: The standard pattern in CNNs; fusion provides massive speedup by folding batch norm parameters into the convolution weights.
• Fused Multi-Head Attention (e.g., FlashAttention): A single kernel for the entire attention mechanism, optimizing IO to achieve near-theoretical minimum memory movement.
• Elementwise Op Chains: Sequences like Sigmoid → Log → Multiply are ideal for fusion into a single pass.

Across all compilers, fusion cost models evaluate a core set of hardware-aware factors to determine profitability:

• Kernel Launch Overhead: Amortizing fixed per-launch latency (synchronization, driver calls).
• Memory Traffic: Reduction in reads/writes of intermediate tensors to DRAM.
• Cache Locality: Improved data reuse in L1/L2 cache or GPU shared memory.
• Register Pressure: Negative cost from increased live variables in a fused kernel, potentially reducing occupancy.
• Parallelism: Potential loss of independent parallelism from fusing independent (horizontal) ops.
• Arithmetic Intensity: Fusing a memory-bound op with a compute-bound op can better saturate compute units. The optimal balance of these factors varies by hardware architecture (CPU, GPU, TPU).

The compiler component that uses the cost model to construct an execution plan. It explores the search space of possible operator groupings, queries the cost model for estimated performance, and selects the set of fusion groups that yield the optimal or near-optimal schedule. Its effectiveness is directly dependent on the accuracy of the underlying cost model.

The binary outcome determined by the cost model. It answers whether fusing a specific group of operators will result in a net performance gain. The analysis weighs:

• Benefits: Reduced kernel launch overhead, improved data locality, fewer global memory accesses.
• Costs: Increased register pressure, decreased parallelism, potential for resource contention. A cost model's primary job is to predict this profitability accurately.

The overall process that a cost model guides. It involves automatically identifying and merging subgraphs (fusion groups) within a computational graph. The cost model provides the quantitative rationale for which subgraphs to fuse, moving the optimization from simple pattern matching to a performance-driven search. This is a core pass in compilers like XLA, TVM, and MLIR.

Rule-based algorithms that often serve as a simpler alternative or a fallback to a full cost model. These are hand-crafted rules (e.g., "always fuse elementwise ops with their producer") that make fast, deterministic fusion decisions. A sophisticated system may use heuristics for common patterns and a cost model for complex, ambiguous cases where performance trade-offs are less obvious.

A primary performance metric that fusion aims to amortize. This is the latency and resource cost of submitting a single GPU kernel for execution, involving driver calls and scheduling. A key prediction of a cost model is how much this overhead can be reduced by merging N kernels into 1. For very small, memory-bound operations, launch overhead can be the dominant cost, making fusion highly profitable.

The two fundamental optimization targets a cost model must distinguish.

• Memory-Bound Fusion: Focuses on fusing ops to reduce data movement between slow global memory and fast caches. The cost model estimates reduced DRAM bandwidth.
• Compute-Bound Fusion: Aims to increase arithmetic intensity by combining light ops (e.g., ReLU) with heavy ones (e.g., MatMul). The cost model estimates improved FLOP utilization. The optimal strategy depends on the hardware's balance of compute and memory bandwidth.