Optimization strategies¶

Kernel Tuner supports many optimization strategies that accelerate the auto-tuning search process. By default, Kernel Tuner uses ‘brute force’ tuning, which means that Kernel Tuner will try all possible combinations of all values of all tunable parameters. Even with simple kernels this form of tuning can become prohibitively slow and a waste of time and energy.

To enable optimization strategies in Kernel Tuner, you simply have to supply the name of the strategy you’d like to use using the strategy= optional argument of tune_kernel(). Kernel Tuner currently supports the following strategies:

“basinhopping” Basin Hopping

“bayes_opt” Bayesian Optimization

“brute_force” (default) iterates through the entire search space

“dual annealing” dual annealing

“diff_evo” differential evolution

“firefly_algorithm” firefly algorithm strategy

“genetic_algorithm” a genetic algorithm optimization

“greedy_ils” greedy randomized iterative local search

“greedy_mls” greedy randomized multi-start local search

“minimize” uses a local minimization algorithm

“mls” best-improvement multi-start local search

“ordered_greedy_mls” multi-start local search that uses a fixed order

“pso” particle swarm optimization

“random_sample” takes a random sample of the search space

“simulated_annealing” simulated annealing strategy

Most strategies have some mechanism built in to detect when to stop tuning, which may be controlled through specific parameters that can be passed to the strategies using the strategy_options= optional argument of tune_kernel(). You can also override whatever internal stop criterion the strategy uses, and set either a time limit in seconds (using time_limit=) or a maximum number of unique function evaluations (using max_fevals=).

To give an example, one could simply add these two arguments to any code calling tune_kernel():

results, env = tune_kernel("vector_add", kernel_string, size, args, tune_params,
                           strategy="random_sample",
                           strategy_options=dict(max_fevals=5))

A ‘unique function evaluation’ corresponds to the first time that Kernel Tuner tries to compile and benchmark a parameter configuration that has been selected by the optimization strategy. If you are continuing from a previous tuning session using cache files, serving a value from the cache for the first time in the run also counts as a function evaluation for the strategy. Only unique function evaluations are counted, so the second time a parameter configuration is selected by the strategy it is served from the cache, but not counted as a unique function evaluation.

Below all the strategies are listed with their strategy-specific options that can be passed in a dictionary to the strategy_options= argument of tune_kernel().

kernel_tuner.strategies.basinhopping¶

The strategy that uses the basinhopping global optimization method.

kernel_tuner.strategies.basinhopping.tune(searchspace: Searchspace, runner, tuning_options)¶

Find the best performing kernel configuration in the parameter space

This basin hopping strategy supports the following strategy_options:

method: Local optimization algorithm to use, choose any from [‘Nelder-Mead’, ‘Powell’, ‘CG’, ‘BFGS’, ‘L-BFGS-B’, ‘TNC’, ‘COBYLA’, ‘SLSQP’], default L-BFGS-B.

T: Temperature parameter for the accept or reject criterion, default 1.0.

Params runner:: A runner from kernel_tuner.runners
Parameters:: tuning_options (kernel_tuner.interface.Options) – A dictionary with all options regarding the tuning process.
Returns:: A list of dictionaries for executed kernel configurations and their execution times. And a dictionary that contains information about the hardware/software environment on which the tuning took place.
Return type:: list(dict()), dict()

kernel_tuner.strategies.bayes_opt¶

Bayesian Optimization implementation from the thesis by Willemsen.

kernel_tuner.strategies.bayes_opt.generate_normalized_param_dicts(tune_params: dict, eps: float) → Tuple[dict, dict]¶: Generates normalization and denormalization dictionaries.

kernel_tuner.strategies.bayes_opt.normalize_parameter_space(param_space: list, tune_params: dict, normalized: dict) → list¶: Normalize the parameter space given a normalization dictionary.

kernel_tuner.strategies.bayes_opt.prune_parameter_space(parameter_space, tuning_options, tune_params, normalize_dict)¶: Pruning of the parameter space to remove dimensions that have a constant parameter.

kernel_tuner.strategies.bayes_opt.tune(searchspace: Searchspace, runner, tuning_options)¶

Find the best performing kernel configuration in the parameter space.

Params runner:: A runner from kernel_tuner.runners
Parameters:: tuning_options (kernel_tuner.interface.Options) – A dictionary with all options regarding the tuning process. Allows setting hyperparameters via the strategy_options key.
Returns:: A list of dictionaries for executed kernel configurations and their execution times.
Return type:: list(dict()), dict()

kernel_tuner.strategies.brute_force¶

The default strategy that iterates through the whole parameter space

kernel_tuner.strategies.brute_force.tune(searchspace: Searchspace, runner, tuning_options)¶

Find the best performing kernel configuration in the parameter space

This Brute Force strategy supports the following strategy_options:

Params runner:: A runner from kernel_tuner.runners
Parameters:: tuning_options (kernel_tuner.interface.Options) – A dictionary with all options regarding the tuning process.
Returns:: A list of dictionaries for executed kernel configurations and their execution times. And a dictionary that contains information about the hardware/software environment on which the tuning took place.
Return type:: list(dict()), dict()

kernel_tuner.strategies.diff_evo¶

The differential evolution strategy that optimizes the search through the parameter space.

kernel_tuner.strategies.diff_evo.tune(searchspace: Searchspace, runner, tuning_options)¶

Find the best performing kernel configuration in the parameter space

This Differential Evolution strategy supports the following strategy_options:

method: Creation method for new population, any of [‘best1bin’, ‘best1exp’, ‘rand1exp’, ‘randtobest1exp’, ‘best2exp’, ‘rand2exp’, ‘randtobest1bin’, ‘best2bin’, ‘rand2bin’, ‘rand1bin’], default best1bin.

popsize: Population size, default 20.

maxiter: Number of generations, default 100.

Params runner:: A runner from kernel_tuner.runners
Parameters:: tuning_options (kernel_tuner.interface.Options) – A dictionary with all options regarding the tuning process.
Returns:: A list of dictionaries for executed kernel configurations and their execution times. And a dictionary that contains information about the hardware/software environment on which the tuning took place.
Return type:: list(dict()), dict()

kernel_tuner.strategies.dual_annealing¶

The strategy that uses the dual annealing optimization method.

kernel_tuner.strategies.dual_annealing.tune(searchspace: Searchspace, runner, tuning_options)¶

Find the best performing kernel configuration in the parameter space

This Dual Annealing strategy supports the following strategy_options:

method: Local optimization method to use, choose any from [‘COBYLA’, ‘L-BFGS-B’, ‘SLSQP’, ‘CG’, ‘Powell’, ‘Nelder-Mead’, ‘BFGS’, ‘trust-constr’], default Powell.

Params runner:: A runner from kernel_tuner.runners
Parameters:: tuning_options (kernel_tuner.interface.Options) – A dictionary with all options regarding the tuning process.
Returns:: A list of dictionaries for executed kernel configurations and their execution times. And a dictionary that contains information about the hardware/software environment on which the tuning took place.
Return type:: list(dict()), dict()

kernel_tuner.strategies.firefly_algorithm¶

The strategy that uses the firefly algorithm for optimization.

class kernel_tuner.strategies.firefly_algorithm.Firefly(bounds)¶

Firefly object for use in the Firefly Algorithm.

compute_intensity(fun)¶: Evaluate cost function and compute intensity at this position.

distance_to(other)¶: Return Euclidian distance between self and other Firefly.

move_towards(other, beta, alpha)¶: Move firefly towards another given beta and alpha values.

kernel_tuner.strategies.firefly_algorithm.tune(searchspace: Searchspace, runner, tuning_options)¶

Find the best performing kernel configuration in the parameter space

This firefly algorithm strategy supports the following strategy_options:

popsize: Population size, default 20.

maxiter: Maximum number of iterations, default 100.

B0: Maximum attractiveness, default 1.0.

gamma: Light absorption coefficient, default 1.0.

alpha: Randomization parameter, default 0.2.

Params runner:: A runner from kernel_tuner.runners
Parameters:: tuning_options (kernel_tuner.interface.Options) – A dictionary with all options regarding the tuning process.
Returns:: A list of dictionaries for executed kernel configurations and their execution times. And a dictionary that contains information about the hardware/software environment on which the tuning took place.
Return type:: list(dict()), dict()

kernel_tuner.strategies.genetic_algorithm¶

A simple genetic algorithm for parameter search.

kernel_tuner.strategies.genetic_algorithm.disruptive_uniform_crossover(dna1, dna2)¶

Disruptive uniform crossover.

uniformly crossover genes between dna1 and dna2, with children guaranteed to be different from parents, if the number of differences between parents is larger than 1

kernel_tuner.strategies.genetic_algorithm.mutate(dna, mutation_chance, searchspace: Searchspace, cache=True)¶: Mutate DNA with 1/mutation_chance chance.

kernel_tuner.strategies.genetic_algorithm.single_point_crossover(dna1, dna2)¶: Crossover dna1 and dna2 at a random index.

kernel_tuner.strategies.genetic_algorithm.tune(searchspace: Searchspace, runner, tuning_options)¶

Find the best performing kernel configuration in the parameter space

This Genetic Algorithm strategy supports the following strategy_options:

popsize: population size, default 20.

maxiter: maximum number of generations, default 100.

method: crossover method to use, choose any from single_point, two_point, uniform, disruptive_uniform, default uniform.

mutation_chance: chance to mutate is 1 in mutation_chance, default 10.

Params runner:: A runner from kernel_tuner.runners
Parameters:: tuning_options (kernel_tuner.interface.Options) – A dictionary with all options regarding the tuning process.
Returns:: A list of dictionaries for executed kernel configurations and their execution times. And a dictionary that contains information about the hardware/software environment on which the tuning took place.
Return type:: list(dict()), dict()

kernel_tuner.strategies.genetic_algorithm.two_point_crossover(dna1, dna2)¶: Crossover dna1 and dna2 at 2 random indices.

kernel_tuner.strategies.genetic_algorithm.uniform_crossover(dna1, dna2)¶: Randomly crossover genes between dna1 and dna2.

kernel_tuner.strategies.genetic_algorithm.weighted_choice(population, n)¶: Randomly select n unique individuals from a weighted population, fitness determines probability of being selected.

kernel_tuner.strategies.greedy_ils¶

A simple greedy iterative local search algorithm for parameter search.

kernel_tuner.strategies.greedy_ils.tune(searchspace: Searchspace, runner, tuning_options)¶

Find the best performing kernel configuration in the parameter space

This Greedy Iterative Local Search (ILS) strategy supports the following strategy_options:

neighbor: Method for selecting neighboring nodes, choose from Hamming or adjacent, default Hamming.

restart: controls greedyness, i.e. whether to restart from a position as soon as an improvement is found, default True.

no_improvement: number of evaluations to exceed without improvement before restarting, default 50.

random_walk: controls greedyness, i.e. whether to restart from a position as soon as an improvement is found, default 0.3.

Params runner:: A runner from kernel_tuner.runners
Parameters:: tuning_options (kernel_tuner.interface.Options) – A dictionary with all options regarding the tuning process.
Returns:: A list of dictionaries for executed kernel configurations and their execution times. And a dictionary that contains information about the hardware/software environment on which the tuning took place.
Return type:: list(dict()), dict()

kernel_tuner.strategies.greedy_mls¶

A greedy multi-start local search algorithm for parameter search.

kernel_tuner.strategies.greedy_mls.tune(searchspace: Searchspace, runner, tuning_options)¶

Find the best performing kernel configuration in the parameter space

This Greedy Multi-start Local Search (MLS) strategy supports the following strategy_options:

neighbor: Method for selecting neighboring nodes, choose from Hamming or adjacent, default Hamming.

restart: controls greedyness, i.e. whether to restart from a position as soon as an improvement is found, default True.

order: set a user-specified order to search among dimensions while hillclimbing, default None.

randomize: use a random order to search among dimensions while hillclimbing, default True.

Params runner:: A runner from kernel_tuner.runners
Parameters:: tuning_options (kernel_tuner.interface.Options) – A dictionary with all options regarding the tuning process.
Returns:: A list of dictionaries for executed kernel configurations and their execution times. And a dictionary that contains information about the hardware/software environment on which the tuning took place.
Return type:: list(dict()), dict()

kernel_tuner.strategies.minimize¶

The strategy that uses a minimizer method for searching through the parameter space.

kernel_tuner.strategies.minimize.tune(searchspace: Searchspace, runner, tuning_options)¶

Find the best performing kernel configuration in the parameter space

This Minimize strategy supports the following strategy_options:

method: Local optimization algorithm to use, choose any from [‘Nelder-Mead’, ‘Powell’, ‘CG’, ‘BFGS’, ‘L-BFGS-B’, ‘TNC’, ‘COBYLA’, ‘SLSQP’], default L-BFGS-B.

Params runner:: A runner from kernel_tuner.runners
Parameters:: tuning_options (kernel_tuner.interface.Options) – A dictionary with all options regarding the tuning process.
Returns:: A list of dictionaries for executed kernel configurations and their execution times. And a dictionary that contains information about the hardware/software environment on which the tuning took place.
Return type:: list(dict()), dict()

kernel_tuner.strategies.mls¶

The strategy that uses multi-start local search.

kernel_tuner.strategies.mls.tune(searchspace: Searchspace, runner, tuning_options)¶

Find the best performing kernel configuration in the parameter space

This Multi-start Local Search (MLS) strategy supports the following strategy_options:

neighbor: Method for selecting neighboring nodes, choose from Hamming or adjacent, default Hamming.

restart: controls greedyness, i.e. whether to restart from a position as soon as an improvement is found, default False.

order: set a user-specified order to search among dimensions while hillclimbing, default None.

randomize: use a random order to search among dimensions while hillclimbing, default True.

Params runner:: A runner from kernel_tuner.runners
Parameters:: tuning_options (kernel_tuner.interface.Options) – A dictionary with all options regarding the tuning process.
Returns:: A list of dictionaries for executed kernel configurations and their execution times. And a dictionary that contains information about the hardware/software environment on which the tuning took place.
Return type:: list(dict()), dict()

kernel_tuner.strategies.ordered_greedy_mls¶

A greedy multi-start local search algorithm for parameter search that traverses variables in order.

kernel_tuner.strategies.ordered_greedy_mls.tune(searchspace: Searchspace, runner, tuning_options)¶

Find the best performing kernel configuration in the parameter space

This Ordered Greedy Multi-start Local Search (MLS) strategy supports the following strategy_options:

neighbor: Method for selecting neighboring nodes, choose from Hamming or adjacent, default Hamming.

restart: controls greedyness, i.e. whether to restart from a position as soon as an improvement is found, default True.

order: set a user-specified order to search among dimensions while hillclimbing, default None.

randomize: use a random order to search among dimensions while hillclimbing, default False.

Params runner:: A runner from kernel_tuner.runners
Parameters:: tuning_options (kernel_tuner.interface.Options) – A dictionary with all options regarding the tuning process.
Returns:: A list of dictionaries for executed kernel configurations and their execution times. And a dictionary that contains information about the hardware/software environment on which the tuning took place.
Return type:: list(dict()), dict()

kernel_tuner.strategies.pso¶

The strategy that uses particle swarm optimization.

kernel_tuner.strategies.pso.tune(searchspace: Searchspace, runner, tuning_options)¶

Find the best performing kernel configuration in the parameter space

This Particle Swarm Optimization (PSO) strategy supports the following strategy_options:

popsize: Population size, default 20.

maxiter: Maximum number of iterations, default 100.

w: Inertia weight constant, default 0.5.

c1: Cognitive constant, default 2.0.

c2: Social constant, default 1.0.

Params runner:: A runner from kernel_tuner.runners
Parameters:: tuning_options (kernel_tuner.interface.Options) – A dictionary with all options regarding the tuning process.
Returns:: A list of dictionaries for executed kernel configurations and their execution times. And a dictionary that contains information about the hardware/software environment on which the tuning took place.
Return type:: list(dict()), dict()

kernel_tuner.strategies.random_sample¶

Iterate over a random sample of the parameter space.

kernel_tuner.strategies.random_sample.tune(searchspace: Searchspace, runner, tuning_options)¶

Find the best performing kernel configuration in the parameter space

This Random Sampling strategy supports the following strategy_options:

fraction: Fraction of the search space to cover value in [0, 1], default 0.1.

Params runner:: A runner from kernel_tuner.runners
Parameters:: tuning_options (kernel_tuner.interface.Options) – A dictionary with all options regarding the tuning process.
Returns:: A list of dictionaries for executed kernel configurations and their execution times. And a dictionary that contains information about the hardware/software environment on which the tuning took place.
Return type:: list(dict()), dict()

kernel_tuner.strategies.simulated_annealing¶

The strategy that uses particle swarm optimization.

kernel_tuner.strategies.simulated_annealing.acceptance_prob(old_cost, new_cost, T, tuning_options)¶: Annealing equation, with modifications to work towards a lower value.

kernel_tuner.strategies.simulated_annealing.neighbor(pos, searchspace: Searchspace)¶: Return a random neighbor of pos.

kernel_tuner.strategies.simulated_annealing.tune(searchspace: Searchspace, runner, tuning_options)¶

Find the best performing kernel configuration in the parameter space

This Simulated Annealing strategy supports the following strategy_options:

T: Starting temperature, default 1.0.

T_min: End temperature, default 0.001.

alpha: Alpha parameter, default 0.995.

maxiter: Number of iterations within each annealing step, default 1.

Params runner:: A runner from kernel_tuner.runners
Parameters:: tuning_options (kernel_tuner.interface.Options) – A dictionary with all options regarding the tuning process.
Returns:: A list of dictionaries for executed kernel configurations and their execution times. And a dictionary that contains information about the hardware/software environment on which the tuning took place.
Return type:: list(dict()), dict()