Code for chosing benchmark points. More...
#include <stdlib.h>#include "pmm_model.h"#include "pmm_selector.h"#include "pmm_interval.h"#include "pmm_param.h"#include "pmm_load.h"#include "pmm_log.h"Go to the source code of this file.
Code for chosing benchmark points.
This is the core of the application, implementing many methods to choose benchmarking points to minimise the construction time of a model
Definition in file pmm_selector.c.
| int adjust_interval_with_param_constraint_max | ( | struct pmm_interval * | i, |
| struct pmm_paramdef_set * | pd_set | ||
| ) |
Step along an interval until the product of the parameters at the end point of the interval matches the maximum parameter product (equal or less than if nonzero_max is set, or equal to or 1 step great than if nonzero_max is not set).
| i | pointer to the interval that is to be adjusted |
| pd_set | pointer to the parameter definition set |
Definition at line 1596 of file pmm_selector.c.
| int adjust_interval_with_param_constraint_min | ( | struct pmm_interval * | i, |
| struct pmm_paramdef_set * | pd_set | ||
| ) |
Step along an interval until the product of the parameters at the end/start point of the interval matches the minium parameter product
| i | pointer to the interval that is to be adjusted |
| pd_set | pointer to the parameter definition set |
Definition at line 1463 of file pmm_selector.c.
| int check_benchmarking_minimums | ( | struct pmm_routine * | r, |
| double | t, | ||
| int | n | ||
| ) |
check benchmark execution statistics against minimum requirements in routine configuration
| r | pointer to the routine |
| t | time spent benchmarking as a double |
| n | number of benchmarks taken |
Definition at line 388 of file pmm_selector.c.
| int find_interval_matching_bench | ( | struct pmm_routine * | r, |
| struct pmm_benchmark * | b, | ||
| struct pmm_loadhistory * | h, | ||
| struct pmm_interval ** | found_i | ||
| ) |
Find the interval in an interval stack that corresponds to a given benchmark.
This permits adding benchmarks to the model out of the order deemed by the construction intervals.
| r | pointer to routine containing model and parameter definitions |
| b | pointer to benchmark whos interval we are searching for |
| h | pointer to load history |
| found_i | pointer to address that will hold the found interval or point to NULL |
Definition at line 2615 of file pmm_selector.c.
| int init_gbbp_boundary_intervals | ( | struct pmm_routine * | r | ) |
intialize the interval stack for an empty model that will be built using a GBBP algorithm
| r | pointer to the routine which is having its intervals intiialized |
Definition at line 2160 of file pmm_selector.c.
| int init_gbbp_diagonal_interval | ( | struct pmm_routine * | r | ) |
Function initialises a construction interval between two points which form a diagonal through the parameter space defined by the parameter definitions. For $n$ parameters with defintions of start points $s_i$ and end points $e_i$, the diagonal starts at:
$(s_0, s_1, ..., s_n)$
and ends at:
$(e_0, e_1, ..., e_n)$
| r | pointer to the routine for which the interval will be initialised |
Other intervals are added to benchmark neccessary extremeties of the parameter space and to tag the completion of the diagonal and the whole model in general.
Definition at line 1305 of file pmm_selector.c.
| int init_gbbp_naive_intervals | ( | struct pmm_routine * | r | ) |
Function initialises a construction intervals in a grid form across the whole parameter space. To form the grid, for each parameter, for all possible parameter values on that axis, intervals are projected parallel to all other axes.
Other intervals are added to benchmark neccessary extremeties of the parameter space and to tag the completion of the diagonal and the whole model in general.
| r | pointer to the routine |
Definition at line 977 of file pmm_selector.c.
| int init_naive_1d_intervals | ( | struct pmm_routine * | r | ) |
Function initialises a construction intervals for 1d naive bisection. A interval covering the problem space with bisection type is created. Two further 'point' type intervals are created at the end points of the bisection interval.
| r | pointer to the routine |
Definition at line 704 of file pmm_selector.c.
| int is_interval_divisible | ( | struct pmm_interval * | i, |
| struct pmm_routine * | r | ||
| ) |
Tests if an interval can be processed to return a benchmark from it. I.e. if the 'length' of the interval is enough for a new benchmark point to be returned when GBBP is applied to that interval.
This is achieved by applying GBBP to the interval, then aligning the start and end points of the interval and comparing them to the GBBP point.
If the GBBP point is equal to either the aligned start/end points, we determine that the interval is not divisible.
| i | pointer to the interval to test |
| r | pointer to the routine that the interval belongs to |
TODO 'divisible' is the wrong adjective to describe this function
Definition at line 3721 of file pmm_selector.c.
| int isnonzero_at_interval_end | ( | struct pmm_interval * | i, |
| struct pmm_paramdef_set * | pd_set | ||
| ) |
Test if the end point of an interval is nonzero or not. A nonzero end point means we will benchmark at this point rather than set its speed to be zero.
The line between start and end points may be perpendicular to some axes of the parameter space, or to none at all. Any parameter-axis that the interval-line is perpendicular to, is not considered in the determination of the end point 'fuzziness'.
The end point is declared nonzero then, if all parameters that may be considered have nonzero property set to true. Other wise, the end point is not fuzzy and should have a speed set to be zero in the model.
| i | pointer to the interval |
| pd_set | pointer to the parameter defintion set |
Definition at line 1754 of file pmm_selector.c.
| void mesh_boundary_models | ( | struct pmm_model * | m | ) |
given a set of complete models along the parameter boundaries, creat a mech of new benchmarking points for the interior of the model
| m | pointer to the model |
Definition at line 2288 of file pmm_selector.c.
| int multi_gbbp_bench_from_interval | ( | struct pmm_routine * | r, |
| struct pmm_interval * | interval, | ||
| int * | params | ||
| ) |
Finds the parameters of the next benchmarking point based on a parameter interval and the GBBP algorithm.
If the interval is _EMPTY, the model is empty and the starting point of the interval is returned for benchmarking
If the interval is _CLIMB, the model is in the initial building phase and an increment on the starting point is returned for benchmarking
If the interval is either _BISECT or _INFLECT then the main phase of building is in progress and the mid point between the start and end of the interval is returned for benchmarking
If the interval is _POINT, then the interval describes a distingt point rather than an interval and this point is returned for benchmarking
The benchmarking point is aligned to the stride/offset of parameter definitions.
| r | pointer to the relevant routine |
| interval | pointer to the interval |
| params | pointer to an array where the next point should be stored |
Definition at line 3829 of file pmm_selector.c.
| int* multi_gbbp_diagonal_select_new_bench | ( | struct pmm_routine * | r | ) |
Returns a new point to benchmark using the Multidimensional Diagonal GBBP method. Briefly, this method first constructs, using the GBBP algorithm, on an interval from the start point of all parameter definitions to the end point of those definitions. After construction along this interval is complete, all points that were measured along it are used to project new construction intervals. From each point N construction intervals are projected parallel to each of the N parameter axes. GBBP is then applied to these new construction intervals, completing the model.
| r | pointer to the routine for which we will find a new benchmark point |
Definition at line 1155 of file pmm_selector.c.
| int multi_gbbp_insert_bench | ( | struct pmm_loadhistory * | h, |
| struct pmm_routine * | r, | ||
| struct pmm_benchmark * | b | ||
| ) |
Insert a benchmark into a multi-parameter model being constructed with the GBBP method.
The second half of the gbbp proceedure. After a benchmark has been made it must be added to the model and the state of the building proceedure must be adjusted according to the new shape of the model.
The rules that govern this adjustment and the specific adjustments are as follows:
if the model is empty, we add the benchmark to the model and set the state to be climbing.
if the model is climbing we test the new benchmark to see if the model is still climbing, or has levelled out, or has begun to decrease. If the model is not still climbing or levelled out, we change the state to bisection. The bisection state permits the optimal selection of new benchmarking points.
In this state, any new benchmark being inserted is comparted to the existing model. If the model already accurately approximates the benchmark the state is set to inflection.
The inflection state is a second level of bisection, in this state if a new benchmark is again accurately approximated by the existing model we deem the model to be complete in this region
Most of this functionality is actually implemented in a deeper function process_interval(), process_it_gbbp_climb(), process_it_gbbp_bisect(), etc.
| h | pointer to the load history |
| r | pointer to the routine to which the benchmark is added |
| b | pointer to the benchmark to be added |
Definition at line 2555 of file pmm_selector.c.
| int* multi_gbbp_naive_select_new_bench | ( | struct pmm_routine * | r | ) |
Returns a new point to benchmark using the Multidimensional Naive GBBP method. Briefly, this method initialises construction intervals in a grid form, through all possible points as defined by the parameter definitions. Then GBBP is applied to all construction intervals to select benchmark points, until the model has been built along all lines in the grid.
| r | pointer to the routine for which we will find a new benchmark point |
Definition at line 888 of file pmm_selector.c.
| int* multi_gbbp_select_new_bench | ( | struct pmm_routine * | r | ) |
builds multi-parameter piece-wise performance models using the GBBP optimisation
Alorithm description:
init
main
| r | pointer to the routine to build for |
Definition at line 2031 of file pmm_selector.c.
| int multi_naive_insert_bench | ( | struct pmm_routine * | r, |
| struct pmm_benchmark * | b | ||
| ) |
Process the insertion of a new benchmark into a model being constructed with a naive method.
Definition at line 329 of file pmm_selector.c.
| int* multi_naive_select_new_bench | ( | struct pmm_routine * | r | ) |
Select a new benchmark following a naive construction method where every possible point in the model is benchmarked.
This action is simply taking the top interval from the construction stack and returning the parameters it describes.
| r | pointer to the routine who's model is under construction |
Definition at line 192 of file pmm_selector.c.
| int* multi_random_select_new_bench | ( | struct pmm_routine * | r | ) |
builds a multi-parameter piece-wise performance model using a random selection of benchmark points
Alogirthm description:
if model is empty select start values for all parameters and return benchmark point else seed random generator
for each parameter select a random parameter size based on the paramdef limits and return
| r | pointer to routine for which the model is being built |
Definition at line 797 of file pmm_selector.c.
| int naive_1d_bisect_insert_bench | ( | struct pmm_routine * | r, |
| struct pmm_benchmark * | b | ||
| ) |
Insert a benchmark into a 1 parameter model being constructed with the naive bisection method.
| r | pointer to the routine forwhich the model is being constructed |
| b | benchmark to insert |
Definition at line 2391 of file pmm_selector.c.
| int* naive_1d_bisect_select_new_bench | ( | struct pmm_routine * | r | ) |
Returns a new point to benchmark using the naive bisection in 1 dimension method. Briefly, this method initialises a bisection construction interval across the problem space (1-d only). Then recursively bisects this interval and benchmarks at bisection points, until it is no longer divisible.
| r | pointer to the routine for which we will find a new benchmark point |
Definition at line 609 of file pmm_selector.c.
| int naive_process_interval_list | ( | struct pmm_routine * | r, |
| struct pmm_benchmark * | b | ||
| ) |
Process the interval list of the naive construction method, after a new benchmark point has been aquired.
Check that the top interval corresponds to the new benchmark and if it does, step the parameter point of the top interval along to the next target point.
In the naive construction method we benchmark every possible point in the parameter space described by the parameter definitions. In general, this set of points P is given by the n-ary Cartesian product of the sets of each of the n parameters, p_0, p_1, p_n, where such sets are defined by our parameter definitions in terms of start values, end values, stride and offsets.
We iterate through such a set of points in lexicographical order, i.e. given points a and b in P, they are successive iff:

Given a point p, incrementing it to p' involves the following: Increment the first term, if this incremented value is greater than the end defined for the first term (i.e. it has overflowed), set the term to the start value and equal start_1 and apply this overflow by incrementing the next term, testing that the next term has not also overflowed, and letting any overflow cascade through terms of the point. You may recognise this kind of process in the natural way one counts :-)
| r | pointer to the routine |
| b | pointer to the new benchmark |
Definition at line 436 of file pmm_selector.c.
| int naive_step_interval | ( | struct pmm_routine * | r, |
| struct pmm_interval * | interval | ||
| ) |
Step the start point of a naive interval to the next benchmark point.
| r | pointer to the routine |
| interval | pointer to the interval |
Definition at line 558 of file pmm_selector.c.
|
read |
Create a new interval that is a projection through a point p, perpendicular to the plane of the d-th element of the point, which is described by the parameter defintion pd
| p | pointer to the parameter array describing the point |
| pd | pointer to the parameter definition relating to the perpendicular plane |
| d | index of the perpendicular plane |
| n | number of elements in the point |
Definition at line 1966 of file pmm_selector.c.
| int process_interval | ( | struct pmm_routine * | r, |
| struct pmm_interval * | i, | ||
| struct pmm_benchmark * | b, | ||
| struct pmm_loadhistory * | h | ||
| ) |
Process an interval based on its type.
| r | pointer to the routine who's model is being constructed |
| i | pointer to the interval to process |
| b | pointer to the benchmark that is being inserted to the model |
| h | pointer to the load history defining performance fluctuation |
Definition at line 2785 of file pmm_selector.c.
| int process_interval_list | ( | struct pmm_routine * | r, |
| struct pmm_benchmark * | b, | ||
| struct pmm_loadhistory * | h | ||
| ) |
process the interval list, with a newly aquired benchmark
| r | pointer to routine |
| b | pointer to benchmark |
| h | load history |
Definition at line 2699 of file pmm_selector.c.
| int process_it_gbbp_bisect | ( | struct pmm_routine * | r, |
| struct pmm_interval * | i, | ||
| struct pmm_benchmark * | b, | ||
| struct pmm_loadhistory * | h | ||
| ) |
process a GBBP_BISECT interval
test if the model approximates the new benchmark and in what way,
If the benchmark at the same level as the its left and right neighbours: assume the model is flat in the region of the interaval and finalized this area of the model by removing it.
If the benchmark is at the same level as the left neighbour only, assume that the model is flat to the left of the new benchmark, finalize this area by remoing the interval and replacing it with a new interval representing the area to the right of the benchmark.
In the benchmark is at thte same level as the right neighbour only, preform the same action, but in the inverse, replace the interval with a new interval representing the area to the left of the benchmark
In other cases, look up the current model at the position of the new benchmark.
If the current model accurately represents the new benchmark, replace the construction interval with a new GBBP_INFLECT interval covering the same area.
If the current model does not accurately represent the new benchmark, replace the interval with two new GGBP_BISECT intervals covering the left and right areas between the new benchmark and the previous interval, allowing further refinement of the model
| r | pointer to the routine |
| i | pointer to the interval being processed |
| b | pointer to the new benchmark |
| h | pointer to the load history |
Definition at line 3132 of file pmm_selector.c.
| int process_it_gbbp_climb | ( | struct pmm_routine * | r, |
| struct pmm_interval * | i, | ||
| struct pmm_benchmark * | b, | ||
| struct pmm_loadhistory * | h | ||
| ) |
Process a IT_GBBP_CLIMB interval type and associated benchmark. If the new benchmark has a higher speed than the benchmark at the start/left-most point of the interval, then the performance is still climbing. Replace the interval with one that ranges from the new benchmark point to the old old interval end point. The new interval will have the same GBBP_CLIMB type. Otherwise, if the performance is no longer climbing, replace the old interval with a new interval ranging from the new benchmark point to the end of the old interval, but with a GBBP_BISECT type.
| r | pointer to the routine that cotains the model |
| i | pointer to the interval that the benchmark belongs to |
| b | pointer to the benchmark |
| h | pointer to the load history (describes performance variance) |
Definition at line 2889 of file pmm_selector.c.
| int process_it_gbbp_empty | ( | struct pmm_routine * | r, |
| struct pmm_interval * | i | ||
| ) |
Process a gbbp_empty type interval. Replace interval with an IT_GBBP_CLIMB interval that starts and ends at the same points as the GBBP_EMPTY interval it replaces.
Note, the new interval must be inserted inplace of the old one, not at the top of the interval list. The start,start,...,start set of parameters match all IT_GBBP_EMPTY intervals for all different boundary planes. We will process all of these intervals, not just the first occurance in the interval list. However, not all of the planes are ready for construction (e.g. their nonzero_end benchmark may not be executed yet). Inserting the next interval (IT_GBBP_CLIMP) inplace of the IT_GBBP_EMPTY interval resolves this issue.
| r | pointer to the parent routine |
| i | pointer to the interval we are processing |
Definition at line 2854 of file pmm_selector.c.
| int process_it_gbbp_inflect | ( | struct pmm_routine * | r, |
| struct pmm_interval * | i, | ||
| struct pmm_benchmark * | b, | ||
| struct pmm_loadhistory * | h | ||
| ) |
process a GBBP_INFLECT interval
test if the model approximates the new benchmark and in what way,
Look up the current model at the position of the new benchmark, if the model accurately represents the new benchmark then the model is complete in this area, remove the construction interval.
Otherwise, construction must contine in this area, but:
If the benchmark is at the same level as the left neighbour only, assume that the model is flat to the left of the new benchmark, finalize this area by remoing the interval and replacing it with a new BISECT interval representing the area to the right of the benchmark.
In the benchmark is at thte same level as the right neighbour only, preform the same action, but in the inverse, replace the interval with a new interval representing the area to the left of the benchmark
Otherwise replace the interval with two new GGBP_BISECT intervals covering the left and right areas between the new benchmark and the previous interval, allowing further refinement of the model.
| r | pointer to the routine |
| i | pointer to the interval being processed |
| b | pointer to the new benchmark |
| h | pointer to the load history |
Definition at line 3430 of file pmm_selector.c.
| int process_it_point | ( | struct pmm_routine * | r, |
| struct pmm_interval * | i | ||
| ) |
Process a point type interval. Remove interval from the interval list and if the list is now empty, add a IT_COMPLETE interval to the list to tag that construction has been completed, also set the complete parameter of the model to 1
| r | pointer to the routine the benchmark belongs to |
| i | pointer to the interval |
Definition at line 3678 of file pmm_selector.c.
| int project_diagonal_intervals | ( | struct pmm_model * | m | ) |
Assuming all points in the model are along a diagonal constructed by GBBP from start_0, start_1, ..., start_n to end_0, end_1, ..., end_n, project construction intervals through each diagonal point, along mutually perpendicular lines.
Or more formally, given a set n parameter definitions, describing start and end values values: START = start_0, start_1, ..., start_n END = end_0, end_1, ..., end_n
For each point p along a diagonal from a point (start_0,start_1,...,start_n) to (end_0, end_1, ..., end_n) For each element p_i of a point p = (p_0, p_1, ..., p_n) find a point a by replacing p_i in the point p with start_i find a point b by replacing p_i in the point p with end_i create a construction interval between a and b
| m | pointer to the model |
Definition at line 1800 of file pmm_selector.c.
| int rand_between | ( | int | min, |
| int | max | ||
| ) |
find a random integer between two values (inclusive)
| min | first integer |
| max | second integer |
Definition at line 856 of file pmm_selector.c.
| void recurse_mesh | ( | struct pmm_model * | m, |
| int * | p, | ||
| int | plane, | ||
| int | n_p | ||
| ) |
recurse through each plane of a model creating a mesh of benchmark points using the completed parameter boundaries
| m | pointer the model |
| p | pointer to a parameter array |
| plane | current plane |
| n_p | number of parameters/planes |
Definition at line 2327 of file pmm_selector.c.
| void set_params_interval_midpoint | ( | int * | p, |
| struct pmm_interval * | i | ||
| ) |
Sets a param array to the midpoint between start and end points of an interval.
Precision is limited to the integer type of the point definition, round up is carried out on the division.
| p | pointer to the parameter array |
| i | pointer to the interval |
Definition at line 3908 of file pmm_selector.c.
| int set_params_step_along_climb_interval | ( | int * | params, |
| int | step, | ||
| struct pmm_interval * | i, | ||
| struct pmm_paramdef_set * | pd_set | ||
| ) |
Step along the climb interval, from the start point towards the end point, forwards or backwards, a number of times.
| params | pointer to an array to store the parameters at the n-th step along the interval |
| step | number of steps to take along the interval (- to step backwards, + to step forwards) |
| i | pointer to the interval to step along |
| pd_set | pointer to the parameter definition set |
Definition at line 3082 of file pmm_selector.c.
1.8.1.2