TL;DR
Arknife is a new retargetable compiler that treats tensor data layouts as first-class instruction requirements rather than mere performance hints. By using a unified layout algebra and a global constraint solver, it automatically generates high-performance kernels for diverse hardware—including x86 CPUs, NPUs, and GPUs—outperforming vendor-optimized libraries by up to 3.78x.
What Problem Does This Paper Address?
Modern hardware accelerators (like GPUs and NPUs) derive their massive performance from specialized instructions, such as NVIDIA's Tensor Cores or Qualcomm's HMX units. However, these instructions are incredibly "picky": they require data to be in very specific "layouts" in memory or registers to execute correctly and efficiently. For example, an NPU might require rows to be interleaved in pairs, while a GPU wants data distributed across parallel "lanes" in a complex, non-linear pattern.
Currently, developers must manually manage these layouts or use compilers that are locked into a single hardware target. This makes porting code to new chips a manual, error-prone nightmare. Furthermore, if a compiler makes a layout choice locally that doesn't fit a later instruction, it must insert expensive "repair" operations (like data shuffles), which can be orders of magnitude slower than the actual computation.
Methods
The authors introduce Arknife, a compiler built on a unified layout algebra. Instead of hardcoding data movement, Arknife treats layouts as a set of constraints to be solved.
- Constraint-Based Algebra: It maps logical tensor axes (like "row" and "column") to hardware axes (like "register index" or "thread ID"). Instructions simply declare their requirements as partial mappings.
- Instruction Binding & Feasibility: The compiler selects target instructions and checks if their layout needs can be met. If there is a conflict, it inserts "provisional repairs" (e.g., a transpose or shuffle).
- Global Optimization: Arknife uses e-graph rewriting to find and eliminate redundant repairs. For instance, two back-to-back transposes might be simplified or canceled out.
- Global Solver: Finally, it uses an Integer Linear Programming (ILP) solver to find a single, consistent layout for every tensor in the program that satisfies all instruction requirements simultaneously across the entire compute graph.
Datasets
The researchers evaluated Arknife on three distinct architectures using standard deep learning workloads:
- x86 CPU: Intel Xeon with AVX-512 VNNI instructions.
- Qualcomm Hexagon NPU: Utilizing HMX matrix instructions.
- NVIDIA A100 GPU: Utilizing Tensor Core MMA instructions.
Workloads included GEMM (General Matrix Multiplication), Multi-Head Attention (MHA), LayerNorm, Softmax, and quantized operations. They compared Arknife against vendor libraries (oneDNN, QNN, cuBLAS) and state-of-the-art compilers like Halide, Hydride, MISAAL, and Triton.
Key Insights and Ideas
- Layout is Semantic: The paper argues that layout is part of an instruction's functional interface. If the layout is wrong, the instruction might produce incorrect results or fail to run entirely.
- Global vs. Local Solving: Most compilers fix layout mismatches locally. Arknife’s "aha moment" is that by solving for layouts globally, you can often choose an initial layout that makes all subsequent instructions "just work" without any expensive data movement.
- Retargetability via Abstraction: Because the layout algebra is independent of any specific Instruction Set Architecture (ISA), adding support for a new chip only requires writing a short description of its instructions and their layout needs—the compiler's core logic remains unchanged.
Key Results
Arknife delivers significant speedups by drastically reducing data movement overhead:
- x86 Performance: It achieves a 2.17x geometric mean speedup over Intel's oneDNN and 5.08x over the retargetable compiler MISAAL.
- Hexagon NPU Performance: It outperforms the vendor library QNN by 3.78x and MISAAL by 4.53x.
- NVIDIA A100 Performance: It reaches 97% of the performance of the highly optimized cuBLAS on TF32 GEMM and is 5.04x faster than unfused PyTorch for FP16 MHA.
- Programming Efficiency: Arknife can implement complex kernels like MHA with just 68 lines of code, compared to 117–650 lines for manual implementations in other frameworks.
Limitations and Future Work
- Complex Domains: The current model assumes regular, rectangular tensor domains. It does not yet handle "ragged" tensors or data-dependent access patterns.
- Weight Management: While it excels at kernel execution, the authors note that automatic weight preprocessing and managing where weights reside in memory (residency) are areas for future work.
- Fusion Scope: The authors suggest expanding the scope of "megakernel" fusion to even larger operator graphs to further minimize global memory traffic.
Summary updated