Cost Model

Cost models are categorized by their derivation method. Analytical models use first-principles formulas based on hardware specs (e.g., FLOPs, memory bandwidth). Heuristic models rely on empirical rules or learned patterns from profiling data. Modern compilers often use a hybrid approach, where an analytical baseline is refined with heuristic corrections for complex, hardware-specific behaviors like cache contention.

A cost model operates at different levels of the computational graph:

• Operation-level: Estimates cost for a single operator (e.g., a Conv2D layer).
• Subgraph-level: Estimates cost for a fused cluster of operators, crucial for evaluating fusion decisions.
• Schedule-level: Estimates cost for a specific execution plan, including loop tiling factors and memory layout choices. Higher granularity provides more accurate guidance for complex optimizations but increases model complexity.

The primary metrics a cost model predicts are:

• Latency: Execution time, often the primary optimization target.
• Memory Usage: Peak working memory and persistent buffer sizes.
• Energy Consumption: Critical for mobile and edge devices.
• Hardware Utilization: Metrics like MAC (Multiply-Accumulate) efficiency or cache hit rates. A model may be multi-objective, trading off between these metrics based on a deployment target's constraints.

An effective cost model must encapsulate target hardware characteristics. This includes:

• Compute Throughput: Peak FLOP/s for different data types (FP32, INT8).
• Memory Hierarchy: Bandwidth and sizes of L1/L2/L3 caches and DRAM.
• Kernel Launch Overhead: Particularly important for GPU execution.
• Specialized Units: Accounting for accelerators like Tensor Cores or NPU vector units. Without this awareness, the model's predictions will not correlate with real-world performance.

A cost model is useless in isolation; it drives an optimization search. It is the objective function for algorithms like:

• Greedy Algorithms: Making locally optimal choices (e.g., fuse if cost reduction > threshold).
• Dynamic Programming: Finding optimal graph partitioning.
• Genetic Algorithms or Simulated Annealing: Exploring vast schedule spaces. The model must be fast to evaluate, as it may be called millions of times during a compilation search.

Cost models are validated and refined through profiling. This involves:

• Micro-benchmarking: Executing kernel prototypes to gather ground-truth data.
• Error Analysis: Comparing predicted vs. actual latency to identify systematic underestimation or overestimation.
• Continuous Calibration: Updating model parameters as compiler versions or hardware drivers change. The Roofline Model is often used as a theoretical upper bound to sanity-check cost model predictions.

Cost models are categorized by their derivation method.

• Analytical Models use first-principles formulas based on hardware specs (e.g., FLOPs, memory bandwidth) and operation characteristics to calculate a theoretical cost like latency or energy.
• Heuristic Models rely on empirical rules, lookup tables, or machine learning trained on profiling data to predict costs, often better capturing complex, non-linear hardware behaviors like cache effects.

Most modern compilers, such as TVM's Ansor or MLIR's scheduling systems, use a hybrid approach.

A cost model predicts one or more critical resource metrics to guide optimization passes.

• Latency: The execution time for an operation or subgraph, often the primary optimization target.
• Memory Usage: Peak working memory or persistent buffer sizes, crucial for memory-constrained edge devices.
• Energy/Power: Estimated consumption, key for battery-powered inference.
• Compute Throughput: Utilization of hardware compute units (e.g., GPU SMs, NPU MAC arrays).

Optimizers use these estimates to make trade-offs, such as increasing memory usage to reduce latency via operator fusion.

A primary use of cost models is to decide when to fuse sequential operations. The compiler evaluates the cost of the original separate kernels versus a single fused kernel.

Considerations include:

• Reduction in intermediate tensor write/read bandwidth.
• Overhead of kernel launch and synchronization.
• Potential for improved data locality and cache reuse.
• Limitations of fused kernel implementation complexity or register pressure.

The cost model must accurately compare these factors to identify profitable fusion opportunities, a central task in frameworks like Apache TVM and XLA.

In auto-scheduling compilers, the cost model is the objective function for a search algorithm. The system:

1. Generates many valid schedules (ways to tile, vectorize, parallelize a loop nest).
2. Estimates the cost of each schedule using the model.
3. Selects the lowest-cost schedule for final code generation.

This is used in TVM's Ansor and Halide's autoscheduler, where the cost model must be fast to evaluate thousands of candidates. It often uses a learned model trained on profiling data from the target hardware.

An accurate cost model must encapsulate target hardware characteristics.

• CPU: Models must account for cache hierarchy (L1/L2/L3), vector unit width (AVX-512, Neon), and branch prediction.
• GPU: Models consider thread block occupancy, shared memory usage, and global memory coalescing.
• NPU/Accelerators: Models are built around dedicated matrix multiplication units, specialized memory hierarchies, and fixed-function pipelines.

This is why compilers like TensorFlow Lite for Microcontrollers and ONNX Runtime have different delegate backends with their own cost models.

A compiler optimization that combines multiple sequential operations into a single, more efficient kernel. A cost model is essential for deciding which operator sequences to fuse, as it estimates the trade-off between reduced kernel launch overhead and the potential for increased register pressure or decreased parallelism.

• Example: Fusing a convolution, batch normalization, and ReLU activation into one kernel.
• Decision Point: The cost model evaluates if the fused kernel's estimated latency is lower than the sum of the individual kernels, considering memory access patterns.

The process of dividing a large computational graph into smaller subgraphs for parallel execution across multiple devices (e.g., GPUs, NPUs). A cost model guides partitioning by estimating the communication cost between partitions versus the computation speedup from parallelism.

• Key Metric: The model estimates data transfer latency across interconnects (PCIe, NVLink).
• Objective: Minimize the estimated end-to-end latency, balancing compute and communication costs.

An automated process that searches for optimal implementation parameters (e.g., tile size, thread block size) for a computational kernel. It relies on a cost model—either analytical or empirical—to predict the performance of thousands of candidate kernel variants without exhaustively running each one.

• Empirical Cost Model: May use a performance predictor trained on hardware telemetry.
• Output: Selects the kernel configuration with the lowest predicted execution time.

A compile-time optimization that pre-allocates and reuses memory buffers for tensors by analyzing their lifetimes in the graph. A cost model informs this planning by estimating the peak memory footprint of different buffer allocation strategies, enabling the selection of a plan that stays within device memory limits.

• Lifetime Analysis: Determines when tensors are born and die.
• Cost Function: Minimizes estimated peak memory usage or fragmentation.

Transforming the in-memory arrangement of tensor data (e.g., from NCHW to NHWC format) to better match hardware access patterns. A cost model evaluates the performance impact of different layouts by estimating cache efficiency, vectorization potential, and data transformation overhead.

• Hardware-Specific: Optimal layout depends on the target accelerator's memory subsystem.
• Cost: Must include the latency of any required layout conversion transposes.

An intuitive visual performance model used to bound the maximum achievable performance of a kernel. It serves as a high-level analytical cost model, plotting operational intensity against performance. Compilers use it to identify whether a kernel or subgraph is compute-bound or memory-bound, guiding optimization strategy.

• Compute-Bound: Optimize by increasing arithmetic intensity or improving instruction mix.
• Memory-Bound: Optimize via better data locality, prefetching, or operator fusion.