Optimization method with parallel computations
Optimization method with parallel computations, including performing multiple stages of calculating target function of P independent parameters using GPUs, wherein entire one-dimensional array of the calculated values of the target function of length ∏ j = 1 P W j that needs to be computed is divided into groups of size η and calculated in parallel at L = ∏ j = 1 η W j η parameter points; a number of simultaneously calculated parameters η in each group and a number of calculation points W j of the target function at interval D j for each j-th desired parameter in the group is selected based on a possible number of parallel calculations R=G·M·T, where G is number of GPUs, M is number of cores in each GPU, T is number of threads in each core; and outputting the calculated P parameters for the global extremum of the target function, wherein a full cycle of calculating points is carried out for consecutive iterations, defined as integer division ⌈ L R ⌉ , rounding up.
1. An optimization method with parallel computations, the method comprising:
performing multiple stages of parallel calculation of values of a target function defined by P independent parameters using computing resources of one or more graphics processors (GPU),
wherein an entire one-dimensional array of the calculated values of the target function of length
∏
j
=
1
P
W
j
that needs to be computed is divided into groups of size η that are calculated in parallel at the
L
=
∏
j
=
1
η
W
j
η parameter points;
wherein a number of simultaneously calculated parameters η in each group and a number of calculation points W j of the target function at a given interval D j for each j-th desired parameter in the group is selected based on a possible number of parallel calculations R=G·M·T,
where G is a number of GPUs, M is a number of cores in each GPU, and T is a number of threads in each core; and
outputting the calculated P parameters that correspond to the global extremum of the target function, and
wherein a full cycle of calculating points is carried out for the number of consecutive iterations, defined as integer division
⌈
L
R
⌉
with rounding up.
2. The method of claim 1 , wherein, after forming M arrays out of LB calculated target function values in each GPU core to find local extrema, and wherein for each iteration I, the pool of threads of each core is reduced by half, and the corresponding set of target function values is divided into two parts according to LB i =└LB i−1 /2┘, and wherein each thread compares the calculated target value in its memory cell of a first part (cell 1 ) with a centrally symmetrical cell (cell 2 ), relative to a center of the division into the two parts, and wherein an index of a point containing the global extremum is stored in the cell 2 , and wherein, if LB i is odd, then the first thread in the core further compares the target value with a middle cell, and the calculations are repeated until each core produces a local extremum and its corresponding index, out of M local extrema, with one local extremum found in each core, and out of the G extrema found in the GPU cores, determining one global extremum and its corresponding index value.
3. The method of claim 1 , wherein the group of parameters to be calculated in parallel in each optimization cycle is randomized, and the calculation of p parameters that correspond to the global extremum in a newly-formed group starts from an initial interval using values of other parameters that have been already determined, and during each optimization cycle, the optimization interval for the formed group of parameters is reduced by up to two times a discretization value for each parameter in the selected group.
4. The method of claim 1 , wherein a number of iterations N j in each optimization cycle using an error ε j of the group of η-parameters being computed is determined based on:
N
j
=
lg
(
D
j
/
2
ɛ
j
)
lg
(
W
j
-
1
)
-
lg
2
and after determining N j a decision about finishing a search for extrema for the given group of parameters is made.
5. The method of claim 1 , wherein an index of the found global extremum of the target function in a one-dimensional space of the parameters P is transformed into a multi-dimensional space of the parameters P by iterative integer division of a remainder Q j-1 from the division on a previous iteration (j−1) by
∏
k
=
1
η
-
j
W
k
with j varying from 1 to (η−1), wherein a number α j of elements of coordinates of the η-dimensional space of the target function and the remainder Q j are computed using:
α
j
=
⌊
Q
j
-
1
∏
k
=
1
η
-
j
W
k
⌋
;
Q
j
=
Q
j
-
1
mod
∏
k
=
1
η
-
j
W
k
=
Q
j
-
1
-
α
j
∏
k
=
1
η
-
j
W
k
,
at
j
=
η
α
η
=
Q
η
-
1
.