Parameter Search

The configuration space is the set of all possible parameter combinations that define how a kernel executes. For an NPU, this space is defined by hardware-specific and algorithmic parameters. Key dimensions include:

• Workgroup/Thread Block Size: The number of threads grouped for cooperative execution on a single compute unit.
• Tile/Loop Block Sizes: The dimensions of data blocks used in loop tiling to optimize cache locality.
• Vectorization Factor: The number of data elements processed per SIMD instruction.
• Loop Unroll Factor: The number of times a loop body is replicated to reduce overhead.
• Memory Layout Parameters: Such as padding or swizzling patterns to optimize access. The size of this space grows exponentially with the number of parameters, making exhaustive search infeasible.

Different strategies navigate the configuration space, balancing thoroughness with computational cost.

• Exhaustive/Grid Search: Tests all points in a discretized grid. Guarantees finding the global optimum within the grid but is computationally prohibitive for large spaces.
• Random Search: Samples configurations randomly. Often more efficient than grid search for high-dimensional spaces, as it doesn't waste cycles on uniformly spaced, potentially poor points.
• Bayesian Optimization: A model-based approach that builds a probabilistic performance model of the configuration space. It uses an acquisition function to intelligently select the next promising configuration to evaluate, efficiently balancing exploration of unknown regions and exploitation of known good areas. This is highly effective for expensive-to-evaluate functions (like kernel runs).
• Evolutionary Algorithms: Use principles of natural selection (mutation, crossover, selection) to evolve a population of configurations toward higher performance.

Effective parameter search is guided by or used to build performance models. These models predict execution time or resource usage (e.g., cycles, cache misses) based on parameters and hardware specs.

• Analytical Models: Use first-principles equations derived from hardware architecture (e.g., roofline model). Fast to evaluate but may oversimplify complex interactions.
• Empirical/Machine-Learned Models: Trained on profiling data from actual kernel runs. Can capture non-linear interactions and hardware idiosyncrasies but require initial data collection. Search algorithms use these models to prune the space or to suggest promising configurations without needing to run the full kernel each time, dramatically reducing tuning time.

The search is not free; it is bounded by hardware limits and targets specific optimization goals.

• Hardware Constraints: Parameters must respect limits like maximum workgroup size, available shared memory per block, register count per thread, and total thread count. Invalid configurations cause launch failures.
• Optimization Objectives: The search typically aims to minimize kernel latency or maximize compute throughput (e.g., FLOPS). However, objectives can be multi-faceted, also considering power efficiency (operations per watt) or memory bandwidth utilization. A configuration might maximize throughput at the cost of unacceptable latency or power draw.
• Bottleneck Awareness: The search must identify if the kernel is compute-bound or memory-bound and adjust parameters accordingly (e.g., increasing arithmetic intensity for compute-bound, optimizing memory coalescing for memory-bound).

Parameter search is the core of an auto-tuning pipeline, which is an automated workflow:

1. Kernel Generation: A parameterized kernel template or a code generator produces variants.
2. Profiling & Measurement: Each candidate configuration is compiled (often using vendor-specific SDKs) and executed on the target NPU. A kernel profiler collects metrics like execution time, occupancy, and performance counter data (cache misses, compute throughput).
3. Search & Selection: The search algorithm analyzes results, updates its model, and selects the next configuration to test.
4. Validation & Deployment: The optimal configuration is validated on a broader dataset and then baked into the deployed kernel or a runtime database for dynamic selection. Tools like a kernel tuner automate this entire pipeline.

Real-world parameter search faces several challenges:

• Measurement Noise: Kernel execution time can vary due to system noise (other processes, thermal throttling). Robust tuning requires multiple runs and statistical analysis.
• Portability vs. Specificity: An optimal configuration for one NPU model (or even individual chip due to silicon variance) may be suboptimal for another. Tuning may need to be performed per hardware generation or in the field.
• Cost of Search: The time required for search must be amortized over the lifetime of the kernel's use. For long-running production kernels, extensive tuning is justified. For one-off tasks, a quick heuristic may suffice.
• Multi-Objective Optimization: Often, trading off between latency, throughput, and power is necessary, leading to a Pareto front of optimal solutions rather than a single best point.

The workgroup size (or thread block size) defines the number of threads grouped for cooperative execution on a single NPU compute unit. This parameter critically impacts occupancy and resource utilization.

• Too small: Underutilizes the parallel execution units (ALUs) and registers within a core.
• Too large: Can exceed shared memory or register file limits, forcing threads to spill to slower memory.
• Optimal Tuning: Balances parallel efficiency with the constraints of on-chip memory to hide instruction and memory latency. The search space is defined by hardware limits (e.g., 1024 threads/block) and divisibility rules for the problem domain.

Tile size parameters determine the dimensions of data blocks loaded into fast on-chip memory (e.g., shared memory or cache) during loop tiling transformations. This optimization targets memory-bound kernels.

• Primary Goal: Maximize data locality to reuse loaded data across multiple computations, reducing demands on main memory bandwidth.
• Trade-off: Larger tiles increase reuse but compete for limited shared memory, potentially reducing occupancy. Smaller tiles may not adequately amortize memory transfer costs.
• Search Complexity: Often multi-dimensional (e.g., TILE_M, TILE_N, TILE_K for matrix multiplication), requiring exploration of a large configuration space to find the optimal balance for a specific NPU's memory hierarchy.

The vectorization factor specifies how many data elements are processed by a single SIMD (Single Instruction, Multiple Data) or vector instruction. It is a key parameter for optimizing data-parallel loops.

• Hardware Alignment: Must match the native vector width of the NPU's execution units (e.g., 4, 8, or 16 elements for FP32).
• Memory Coalescing: Higher factors can improve effective memory bandwidth by ensuring memory accesses are contiguous and aligned.
• Tuning Impact: Insufficient vectorization leaves hardware capacity unused. Over-vectorization on misaligned data can cause inefficient scatter/gather operations. Auto-tuners test factors that align with both data type size and problem dimensions.

The loop unroll factor controls how many times a loop body is replicated, eliminating branch instructions and reducing loop overhead.

• Benefits: Increases instruction-level parallelism (ILP), allows the compiler to schedule more independent operations, and can improve register usage.
• Drawbacks: Excessive unrolling increases register pressure, potentially leading to register spilling to slower memory, and can bloat instruction cache footprint.
• Search Strategy: Auto-tuners empirically test factors (e.g., 2, 4, 8, 16) to find the point where diminishing returns set in due to resource constraints. It is often tuned in conjunction with tile size and workgroup size.

This parameter defines the depth of explicit software pipelining used to overlap memory transfers with computation, a crucial technique for hiding memory latency.

• Mechanism: Breaks a kernel into stages (e.g., load, compute, store) that execute concurrently on different thread subsets or via asynchronous operations.
• Tuning Goal: Find the optimal number of stages to keep both the memory units and compute units continuously busy, minimizing pipeline stalls.
• Constraint: Limited by available registers and shared memory per thread. More stages require more on-chip storage for in-flight data. The optimal value is highly dependent on the specific operation's compute-to-memory ratio.

For NPUs with banked shared memory, the memory bank configuration and allocation strategy are tunable parameters to avoid bank conflicts.

• Bank Conflicts: Occur when multiple threads in a workgroup attempt to access different data within the same memory bank simultaneously, causing serialized access.
• Tuning Actions:
  • Padding: Adding padding to data structures in shared memory to shift addresses across banks.
  • Access Pattern Modification: Changing how threads index into shared memory arrays.
• Performance Impact: Eliminating bank conflicts can dramatically improve effective shared memory bandwidth, which is vital for kernels that rely on it for inter-thread communication or fast scratchpad storage.

The complete set of all possible combinations of tunable parameters that define the search domain for an auto-tuning process. For an NPU kernel, this space is defined by hardware and algorithmic constraints.

• Parameters include workgroup size, loop unroll factor, tile dimensions, and vectorization width.
• Constraints are imposed by hardware limits (e.g., maximum threads per block, shared memory size) and algorithmic correctness.
• The dimensionality of this space grows exponentially with the number of parameters, making exhaustive search infeasible and necessitating intelligent search strategies like parameter search.

The automated process of searching a configuration space to find the parameter set that yields optimal performance (e.g., lowest latency, highest throughput) for a given kernel on specific hardware. It abstracts the manual trial-and-error process of performance optimization.

• Workflow: Typically involves a kernel tuner that iteratively generates kernel variants, executes them, and measures performance.
• Goal: To find a hardware-optimal configuration that may be non-intuitive and highly specific to the NPU microarchitecture, data size, and kernel operation.
• Application: Critical for vendor-portable performance, as optimal parameters differ between NPU generations and architectures.

An analytical, heuristic, or machine-learned model that predicts the execution time or resource usage of a computational kernel based on its parameters, hardware characteristics, and input data. It guides efficient parameter search.

• Analytical Models: Use first-principles equations based on hardware specs (e.g., peak FLOPS, memory bandwidth) and kernel operation counts.
• Machine-Learned Models: Trained on profiling data from previous kernel runs to predict performance for unseen configurations.
• Role in Search: A good model can prune the search space dramatically, allowing the tuner to focus on promising regions and avoid costly empirical measurements of poor configurations.

A software tool or library that automates the process of searching for optimal launch parameters and code transformations for computational kernels targeting accelerators like NPUs. It is the engine that executes parameter search.

• Core Function: Manages the configuration space, generates kernel variants, executes benchmarks, and records results.
• Search Strategies: May implement various algorithms, including exhaustive search (for small spaces), random search, Bayesian optimization, or genetic algorithms.
• Examples: OpenTuner, CLTune, and KTT (Kernel Tuning Toolkit) are research tools; vendor SDKs (e.g., NVIDIA's nvprof/cupti with scripting) often provide tuner-like capabilities.

A sequential, model-based optimization technique that uses a probabilistic surrogate model (often a Gaussian Process) to guide the search for optimal parameters. It is particularly effective for expensive-to-evaluate functions, like kernel profiling.

• Mechanism: Builds a statistical model of the performance landscape from sampled points. It uses an acquisition function (e.g., Expected Improvement) to decide the next most promising configuration to test, balancing exploration of uncertain regions and exploitation of known good areas.
• Advantage: Often finds near-optimal configurations with far fewer empirical measurements than random or grid search, making it ideal for parameter search where each kernel run has a cost.

A fundamental tunable parameter representing the number of threads grouped together for cooperative execution and synchronization within a single compute unit (CU) on an NPU or GPU. Its selection is a primary target of parameter search.

• Impact: Directly affects occupancy (CU utilization), memory coalescing efficiency, and usage of shared resources like registers and local memory.
• Trade-offs: A larger workgroup may increase parallelism but can reduce occupancy if resource limits are exceeded. The optimal size is hardware-dependent and non-obvious.
• Search Dimension: Typically searched in multiples of the hardware's warp or wavefront size to avoid thread divergence inefficiencies.