Operator Reordering

The primary objective is to minimize data movement between memory hierarchies. By reordering operators that consume the same tensor outputs, the compiler can schedule them consecutively. This ensures the data remains in faster cache levels (L1, L2, shared memory) between operations, drastically reducing expensive accesses to global memory (DRAM). For example, placing all convolutional layers that process a feature map sequentially before an element-wise operation maximizes reuse of the activated data.

Reordering creates adjacency between compatible operators, which is a prerequisite for graph fusion. Fusing adjacent operators (e.g., a convolution followed by ReLU and batch normalization) into a single compound kernel eliminates intermediate tensor writes to memory and reduces kernel launch overhead. This is critical for NPUs, where kernel launch latency and memory bandwidth are significant bottlenecks. Effective reordering can transform a chain of small operations into one efficient, fused kernel.

By strategically ordering computations, the compiler can schedule the lifetime of intermediate tensors to overlap minimally. This allows for aggressive memory planning where the same memory buffer is reused for multiple tensors that are not live simultaneously (in-place optimization). For instance, an early activation can be consumed and its memory buffer immediately reused for a later layer's output, lowering the total working memory (peak RAM) required for graph execution, which is essential for edge devices.

Reordering can separate independent subgraphs to reveal opportunities for parallel execution. Operators with no data dependencies can be scheduled to run concurrently on different NPU cores or streams. The compiler analyzes the graph's dependency edges (dataflow) to identify these independent chains and reorders them to minimize critical path latency. This is especially valuable for models with branches (e.g., Inception modules) or models processing multi-modal inputs.

NPU architectures often have asymmetric performance for certain operations. A compiler may reorder to place computationally intensive operators (like large matrix multiplications) onto specialized matrix engines first, while lighter operations (like additions) are deferred. It can also reorder to align with data layout preferences (e.g., NHWC vs. NCHW) of the hardware, inserting layout transformations at optimal points to minimize their cost across the entire graph.

Reordering is not arbitrary; it must preserve the semantic correctness of the model. The compiler performs rigorous dataflow analysis using the graph's dependency edges. It can only reorder operators that are mutually independent (no direct or transitive data dependency). Furthermore, it must respect numerical stability constraints; for example, the order of floating-point additions may be fixed if the model is sensitive to non-associative arithmetic.

Vendor-specific compilers deeply integrate reordering with hardware-aware optimizations.

• NVIDIA TensorRT reorders and fuses layers in its graph optimization phase to minimize data transfers and maximize the use of Tensor Cores.
• Apple Core ML Tools compiler reorders operations when converting models to its ML Program format, aligning sequences with the optimal execution patterns for Apple Neural Engine (ANE) and GPU, often combining channel operations for better spatial locality.

Graph fusion is a compiler optimization that merges multiple adjacent operators in a computational graph into a single, compound kernel. This is a primary motivation for operator reordering, as bringing compatible operators together enables their fusion.

• Reduces kernel launch overhead by executing multiple operations in one GPU/NPU kernel call.
• Minimizes intermediate memory accesses by keeping data in fast registers or cache between fused operations.
• Common fusion patterns include element-wise operations followed by activations (e.g., Conv + ReLU) or sequence operations like LayerNorm + Dropout.

Common Subexpression Elimination is a compiler optimization that identifies and eliminates redundant computations of identical expressions within a graph. While operator reordering changes sequence, CSE removes duplicate work.

• Identifies identical subgraphs or tensor expressions that are computed more than once.
• Replaces duplicates with a reference to a single computed value, storing it in a temporary buffer.
• Crucial for graphs generated from high-level frameworks where abstraction can introduce hidden redundancy.

Memory planning (or memory allocation optimization) is a compiler pass that allocates memory buffers for all tensors in a graph, aiming to minimize peak memory usage. Operator reordering directly influences this process.

• Enables buffer reuse by scheduling operations so that the memory of a no-longer-needed tensor can be overwritten by a new tensor.
• Performs in-place optimization where possible, allowing an operator to write its output directly into the memory of an expired input tensor.
• Peak memory reduction is often a key goal, allowing larger models to run on memory-constrained devices.

Graph canonicalization is a compiler transformation that rewrites a computational graph into a standard, simplified, and predictable form. This often precedes optimizations like reordering.

• Eliminates syntactic variations (e.g., (A+B) vs. (B+A)) to present a consistent structure to subsequent passes.
• Decomposes complex, compound operators into their primitive constituents, giving the optimizer more fine-grained operations to reorder.
• Applies algebraic simplifications (e.g., x * 1 -> x) to clean up the graph before more complex analysis.

Static shape inference is a compiler analysis that determines the dimensions (shape) and data types of all tensors in the graph at compile time. This analysis is a prerequisite for effective operator reordering.

• Enables memory planning by knowing the exact size of every input, output, and intermediate tensor.
• Allows cost modeling for reordering decisions; the compiler can estimate the memory footprint and compute cost of different execution orders.
• Facilitates kernel selection by knowing precise tensor shapes, allowing the compiler to choose optimally tiled or vectorized kernels.

Loop fusion is a loop-level optimization that merges adjacent loops. It is the intra-operator analog to the inter-operator graph fusion. Reordering operators can create opportunities for loop fusion within the resulting fused kernel.

• Improves data locality by executing multiple operations on the same data element before it evicts from cache.
• Reduces loop overhead by combining multiple loop control structures into one.
• Example: Fusing a convolution output loop with a subsequent ReLU activation loop within a single fused kernel.