Horizontal Fusion

Horizontal fusion combines independent operators that execute in parallel within the computational graph. Unlike vertical fusion, which chains dependent producer-consumer pairs, horizontal fusion targets operations that have no data dependencies on each other but can be executed simultaneously. For example, applying separate activation functions (e.g., Sigmoid and Tanh) to different channels of the same input tensor can be fused into a single kernel that processes all channels in one pass.

A core enabling condition for horizontal fusion is that the operators being fused consume the same input tensor or slices of the same tensor. This shared data access pattern allows a fused kernel to load the input data once from global GPU memory, perform all parallel computations in-register or in shared memory, and then write the results. This drastically reduces the memory bandwidth pressure that would occur if each operator launched separately and redundantly loaded the same input data.

The primary performance benefit is the amortization of kernel launch overhead. Each GPU kernel launch incurs fixed latency for scheduling, argument passing, and setup. By fusing N parallel operations:

• Launch overhead is reduced from N times to 1 time.
• This is particularly impactful for lightweight, elementwise operations (e.g., pointwise activations, scaling) where the launch overhead can be a significant fraction of the total execution time.
• The fused kernel presents a larger, more substantial workload to the GPU scheduler, improving hardware occupancy and utilization.

Horizontal fusion enhances data locality by keeping intermediate results within the GPU's fast memory hierarchy. When operators are separate, the output of one must be written to global memory (DRAM) before the next can read it. A fused kernel can:

• Keep intermediate tensors in registers or shared memory.
• Promote cache reuse across the fused operations.
• This reduces the total volume of data transferred through the memory subsystem, which is often the bottleneck for performance.

Horizontal fusion is typically performed automatically by deep learning compilers like XLA, TVM, and PyTorch's Inductor (via torch.compile). These systems use pattern matching and cost models to identify profitable fusion opportunities. The compiler:

1. Analyzes the computational graph for independent operators with shared inputs.
2. Estimates the performance benefit using a fusion profitability heuristic.
3. Generates a single, optimized fused kernel (e.g., via CUDA or ROCm) that implements the combined logic.

Fusion is not always profitable. Key trade-offs include:

• Register Pressure: A fused kernel may require more GPU registers to hold intermediate values, potentially reducing warp occupancy.
• Control Flow Divergence: Combining unrelated operations can lead to divergent execution paths within a warp, harming performance.
• Compiler Complexity: Identifying safe and profitable horizontal fusion groups is a complex optimization problem. Over-fusing can create monolithic kernels that are difficult to optimize and may exceed hardware resource limits (e.g., shared memory).

This is the most common form of horizontal fusion, where multiple pointwise operations applied to the same tensor are combined. For example, a sequence like y = relu(x) + sigmoid(x) * tanh(x) involves three independent reads of tensor x. A fused kernel performs all three computations in a single pass:

• Single memory load for the input tensor x.
• Parallel execution of ReLU, Sigmoid, and Tanh functions on each element.
• Single memory store for the final output y. This eliminates redundant data movement and kernel launch overhead, turning a memory-bound workload into a more compute-efficient one.

In transformer blocks, the feed-forward network (FFN) often consists of two parallel linear projections (often an up-projection and a gate projection) whose outputs are combined (e.g., via SiLU activation). Naively, these are two separate matrix multiplications (GEMMs). Horizontal fusion combines them:

• Single, batched GEMM kernel that computes W_up * x and W_gate * x simultaneously.
• Shared input x is read once for both operations.
• Fused activation like SiLU is applied elementwise to the combined results. This pattern is critical in models like LLaMA's SwiGLU FFN, significantly reducing the memory bandwidth required for the input activations.

Horizontal fusion is not always profitable. Compilers use cost models to decide when to fuse. Key trade-offs include:

• Register Pressure: Fusing many operations can increase the number of live variables, exhausting GPU registers and causing spilling to slower memory.
• Reduced Parallelism: Extremely large fused kernels may leave GPU streaming multiprocessors underutilized if they cannot hide memory latency effectively.
• Kernel Complexity: Hand-tuning fused kernels (e.g., FlashAttention) is complex, requiring expert knowledge of hardware memory hierarchies.
• Dynamic Shapes: Fusion decisions made at compile-time (AOT) may be suboptimal for runtime-varying input shapes, favoring Just-In-Time (JIT) fusion approaches.

Vertical fusion merges a producer operator with its immediate consumer operator in the computational graph. This chains sequentially dependent operations to minimize intermediate memory writes and reads.

• Key Mechanism: Fuses operations where the output of one is the direct input to the next (e.g., a matrix multiplication followed by a bias add).
• Contrast with Horizontal: While horizontal fusion combines parallel branches, vertical fusion compresses a linear sequence.
• Primary Benefit: Reduces memory bandwidth pressure by keeping intermediate results in fast registers or cache.

Operator fusion is the high-level, graph-level optimization that merges adjacent computational nodes in a neural network's dataflow graph. It is the overarching goal that horizontal and vertical fusion techniques achieve.

• Scope: Works on the abstract computational graph before low-level kernel code is generated.
• Objective: To create compound operations that replace multiple primitive ops, minimizing data movement between the GPU's global memory and its cores.
• Compiler Role: Frameworks like XLA, TVM, and PyTorch's torch.compile perform automatic operator fusion by pattern matching and cost-based analysis.

Kernel fusion is the low-level implementation of operator fusion, where multiple GPU computational kernels are combined into a single, unified kernel. This is the concrete result of fusion optimizations.

• Implementation Level: Occurs at the level of CUDA, Metal, or Vulkan kernel code.
• Core Benefit: Dramatically reduces kernel launch overhead—the latency of scheduling work on the GPU—by issuing one launch instead of many.
• Example: A hand-written or compiler-generated fused kernel that performs elementwise addition, ReLU, and scaling in one pass over the data.

Graph fusion is the automated process of identifying and merging subgraphs within a full computational graph. It uses algorithms to find optimal fusion groups—sets of operators to combine.

• Process: Employs pattern matching and fusion heuristics to discover profitable fusion opportunities across the entire model graph.
• Planner Component: A fusion planner explores a search space of possible fusions, guided by a cost model for fusion that predicts performance impact.
• Outcome: Creates a new, optimized graph where entire subgraphs are replaced with single, efficient fused operators.

Elementwise fusion is a specific, common type of horizontal fusion where multiple pointwise operations are combined. These operations perform independent computations on each element of a tensor.

• Operations Included: Functions like ReLU, Sigmoid, Add, Multiply, and Scale that apply uniformly across all tensor elements.
• Fusion Simplicity: Highly profitable and straightforward to fuse because there are no complex data dependencies between the operations; they all read from and write to the same memory locations.
• Performance Gain: Elimates multiple passes over the same data, maximizing arithmetic intensity and cache locality.

A fusion compiler is a specialized compiler backend responsible for performing fusion optimizations. Major examples include XLA, TVM, and MLIR.

• XLA (Accelerated Linear Algebra): Google's compiler for TensorFlow/JAX. Performs aggressive fusion using its own HLO IR, a key reason for its performance on TPUs and GPUs.
• Apache TVM: Uses its auto-scheduling and Ansor tuner to generate highly optimized, fused kernels for diverse hardware targets.
• MLIR (Multi-Level Intermediate Representation): Provides dialects like Linalg and transformation passes to represent and perform fusion in a hardware-agnostic way, enabling fusion-aware scheduling.
• Role: Transforms a high-level operator graph into a minimal set of high-performance, fused kernels for execution.