Bayesian Optimization

A probabilistic model (typically a Gaussian Process) that approximates the expensive, black-box objective function. It provides a predictive distribution (mean and variance) over the function's output for any input configuration, quantifying uncertainty where data is sparse. This model is cheap to evaluate and is updated after each observation.

• Primary Role: Acts as a fast, statistical proxy for the costly performance evaluation of an NPU kernel configuration.
• Key Output: For a given parameter set (e.g., tile size, workgroup size), it predicts both the expected performance (mean) and the uncertainty (variance) of that prediction.

A utility function that guides the search by quantifying the desirability of evaluating the objective function at a new point. It uses the surrogate model's predictions to balance exploration (sampling high-uncertainty regions) and exploitation (sampling near the current best-known optimum). The next point to evaluate is chosen by maximizing this function.

• Common Functions: Expected Improvement (EI), Upper Confidence Bound (UCB), Probability of Improvement (PoI).
• Decision Engine: Translates the surrogate's statistical predictions into a single, actionable score for selecting the next configuration to test on the NPU.

The set of input-output pairs collected from previous evaluations of the expensive black-box function. For NPU auto-tuning, this is the log of tested kernel configurations (e.g., {tile_size: 32, unroll_factor: 4}) and their measured performance metrics (e.g., execution time in microseconds).

• Core Data: This history is the training data for the surrogate model.
• Sequential Nature: The history grows by one pair after each iteration, making the surrogate model progressively more accurate in promising regions of the parameter space.

The sequential process that iteratively refines the search for the optimum. Each cycle consists of:

1. Fit/Update the surrogate model using the current observation history.
2. Maximize the acquisition function to propose the next most promising parameter configuration.
3. Evaluate the proposed configuration by running the kernel on the NPU and measuring its performance (the expensive step).
4. Augment the observation history with the new result.

The loop terminates based on a budget (e.g., max evaluations) or convergence criteria.

The domain of tunable parameters defining all possible kernel configurations to be searched. This is the input space for the objective function. For an NPU kernel, this space is defined by discrete and/or continuous parameters.

• Examples: Thread block dimensions (blockDimX, blockDimY), loop unroll factors, memory tile sizes, vectorization width.
• Definition: Must be carefully bounded and structured. It can be categorical (e.g., use algorithm A or B), integer (e.g., tile size from 16 to 128), or continuous (e.g., a learning rate). The surrogate model must be able to model this space.

The expensive black-box function being optimized. In NPU auto-tuning, this is the performance evaluation process for a given kernel configuration. It takes a point from the configuration space as input, runs the kernel with those parameters on the target hardware, and returns a scalar performance metric.

• Typical Form: f(config) -> performance_metric (e.g., execution time, throughput, energy efficiency).
• Key Characteristics: It is noisy (measurements can vary), derivative-free (gradients are unavailable), and costly to evaluate (each run consumes time and energy on the NPU). The goal of Bayesian Optimization is to find its minimum or maximum with as few calls as possible.

The automated process of searching a configuration space to find the optimal set of parameters (e.g., tile size, workgroup size) for a computational kernel on specific hardware. It replaces manual trial-and-error with systematic search algorithms like Bayesian Optimization.

• Goal: Maximize a performance metric like throughput or minimize latency.
• Process: Iteratively runs kernel variants, measures results, and uses a surrogate model to guide the next test.

An analytical or machine-learned model that predicts the execution time or resource usage of a computational kernel. In Bayesian Optimization, this is the probabilistic surrogate model (like a Gaussian Process) that guides the search.

• Analytical Models: Use first-principles of hardware (e.g., roofline model) to estimate bounds.
• Surrogate Models: Learn the relationship between kernel parameters and performance from empirical data, quantifying prediction uncertainty.

The set of all possible combinations of tunable parameters that define the search domain for an auto-tuning process. For an NPU kernel, this often includes:

• Workgroup/Thread Block Size
• Loop Unrolling Factor
• Tile Size for memory hierarchies
• Vectorization Factor

The efficiency of Bayesian Optimization depends on a well-defined, constrained space to avoid combinatorial explosion.

A software tool that measures the execution characteristics of a computational kernel. It provides the empirical data (the objective function) that Bayesian Optimization seeks to optimize.

• Metrics Collected: Execution time (latency), compute throughput (FLOPS), memory bandwidth utilization, and hardware performance counter events (e.g., cache misses).
• Types: Sampling profilers (low overhead) and instrumentation profilers (high precision).

The decision-making component of Bayesian Optimization that uses the probabilistic surrogate model to select the next parameter set to evaluate. It formalizes the exploration-exploitation trade-off.

• Expected Improvement (EI): Favors points likely to outperform the current best.
• Upper Confidence Bound (UCB): Balitates the predicted mean and its uncertainty.
• Probability of Improvement (PI): Focuses on the chance of simple improvement.

A probabilistic model used to approximate the expensive-to-evaluate objective function (e.g., kernel runtime). Bayesian Optimization uses it to reason about unseen configurations.

• Gaussian Process (GP): A common choice that provides a mean prediction and a measure of uncertainty (variance) for any point in the configuration space.
• Tree-structured Parzen Estimator (TPE): Often used in hyperparameter tuning tools like Hyperopt.
• Random Forest: Can also be used as a probabilistic surrogate.