In this paper we propose a parallel tabu search algorithm based on the consecutive tabu algorithm constructed by us earlier to solve the problem of the distributed database optimal logical structure synthesis. Also we provide a reader with some information about the performance of our new parallel algorithm and the quality of the solutions obtained with help of it.
The problems of decomposition of complex data structures play an extremely
important role in many critical applications varying from cloud computing to
distributed databases (DDB) [
From mathematical point of view the specified problem is a NP-complete
nonlinear optimization problem of integer programming. So far different task-specific
approaches were proposed such as branch-and-bound method with a set of heuristics
(BBM) [
In previous works the authors developed the exact mathematical formalization of
the OLS problem and offered the sequential tabu search (TS) algorithm which used
different Tabu Machines (TMs) for each stage of the solution [
In the present article we propose a new distributed model of TM (DTM) and a computationally efficient parallel algorithm for solutions of complex data structure decomposition problems. The article has the following structure. In Section 2 we outline critical elements of TM. In Section 3 general description of DTM algorithm is given and Section 4 specifies it in details. Section 5 briefly describes evaluation of the obtained parallel algorithm. Overview of the results in Section 6 concludes the article.
In our work we use the generic model of TM as it was specified by Minghe Sun and
Hamid R. Nemati [
S = {s1,..., sn } is the current state of the TM, it is collectively determined by the states of its nodes.
S0 = {s10 ,..., sn0} is the state of the TM with the minimum energy among all states which are obtained by the current moment within the local period (or within the short term memory process (STMP)).
S00 = {s100 ,..., sn00} is the state of the TM with the minimum energy among all states which are obtained by the current moment (within both the STMP and the long term memory process (LTMP)).
T = {t1,..., tn } is a vector to check the tabu condition.
E(S ) is the TM energy corresponding to the state S .
E(S0 ) is the TM energy corresponding to the state S0 .
E(S00 ) is the TM energy corresponding to the state S0 .
k is the number of iterations (i.e. the number of neural network (NN) transitions from the one state to another) from the outset of the TM functioning.
h is the number of iterations from the last renewal the value of E(S0 ) within the STMP.
c is the number of the LTMPs carried out by the current moment.
The following variables stand as parameters of the TM-algorithm: l – the tabu size, β – the parameter determining the termination criterion of the STMP, C – maximum number of the available LTMPs inside the TM-algorithm. The state transition mechanism of the TM is governed by TS and performed until the predefined stopping rule is satisfied. Let’s name this sequence of state transitions as a work period of the TM. It is advisable to run the TM for several work periods. It is better to begin a new work period of the TM using information taken from the previous work periods, from a “history” of the TM work by applying a LTMP. In such a case a TS algorithm finds a node which has not changed its state for the longest time among all neurons of the TM. And then this node is forced to switch its state. (1)
As [
The synthesis objective is to minimize the total time needed for consecutive
processing of a set of DDB users’ queries. Such problem has an exact but a very large
mathematical formalization. So, we provide it in the Appendix I and Appendix II of
this paper due to its limited size and should refer to [
In our previous work [
1 I I I I E = − ⋅ ∑ ∑ ∑ ∑ − A1 ⋅ δxy ⋅ (1− δij ) + B1 ⋅ δij ⋅ (1− δxy ) ⋅ (2 ⋅ axgy −1) − D1 ⋅ δij ⋅ 2 i=1 j=1 x=1 y=1 Here wxi,yj = −A1 ⋅ δxy ⋅ (1− δij ) + B1 ⋅ δij ⋅(1− δxy ) ⋅ ( 2⋅ axgy −1) − D1 ⋅ δij ⋅ (incomp _ grxy + +incomp _ gryx ) are weights of neurons, Txi = B1 ⋅ ∑I( axgy )2 + C1 2 yy=≠1x 2 ⋅ Fi neurons’ thresholds. are the
For the second stage of irredundant LR allocation we offered TM with the same structure as TM for LR composition, but the number of neurons in the layer is equal to T ⋅ R0 , where T is the number of LRs, synthesized during LR composition, R0 is the number of the hosts available for LR allocation.
As a result of constraints translation into the terms of TM the following TM energy function for the LR allocation was obtained: E = − 1 ⋅ ∑R0 ∑R0 ∑T ∑T − A2 ⋅ δt1t2 ⋅ (1− δr1r2 ) ⋅ OUTt1r1 ⋅ OUTt2r2 + ∑R0 ∑T B2 ⋅ ψ0 ⋅ 2 r1=1 r2 =1 t1=1 t2 =1 r1=1 t1=1 2 ⋅ θt1r1 I ⋅∑ ( xit1 ⋅ ρi ) + i=1
C2 + D2 ⋅ ψ0 ⋅ ∑I (ρi ⋅ πi ⋅ xit1 ) + E2 ⋅ (trs1rh + tr1 ) ⋅ ∑P0 SN pt1 ⋅ OUTt1r1 2 ⋅ hr1 2 ⋅ ηrE1MD i=1 2 p=1 Tp (2) Here wt1r1,t2r2 = − A2 ⋅ δt1t2 ⋅ (1 − δr1r2 ) are weights of neurons, Tt1r1 = B22⋅ ⋅θψt1r10 ⋅ ∑=I1 i ( xit1 ⋅ ρi ) + 2 C⋅h2r1 + 2D⋅2η⋅rE1ψMD0 ⋅ ∑=I1 i (ρi ⋅ πi ⋅ xit1 ) + t are the neurons’ thresholds. Here the I is the number of DEs, z p1r1 = OUTt1r1 ⋅ SN pt1 E2 ⋅ (trsrh + tr1 ) ⋅ ∑P0 SN pt1 1 2 p=1 Tp where wQpi is the matrix of dimension ( P0 × I ) , that matrix shows which DEs are used during processing of different queries.
In [
For the case of the homogeneous computational parallel cluster with multiple identical nodes the following general scheme of new parallel functionality is proposed. The set of neurons of the whole TM is distributed among all nodes’ processors according to the formula N p = n1 + 1, if p < n2 , where n1 = NP , n2 = N mod P , n1, otherwise N – the number of neurons in the whole TM, p = 0, (P −1) – the index of processor, P – the number of processors. The number of Tabu sub-machines (TsMs) is equal to the number of available processors. So, one TsM is located on each processor and TsM with index p consists of N p neurons. During the initialization stage neural characteristics are set to each neuron. The scheme of DTM is depicted on Fig. 2. The same figure shows how the weight matrix of each TsM Wp = {wipj;i = 1, N p ; j = 1, N} = p−1 p = wij ;i = ∑ Nk +1, ∑ Nk ; j = 1, N is constructed from the weight matrix W = {wij ;i, j = 1, N} k=0 k=0 of the whole TM. When the optimal state of DTM is achieved, the results from all TsMs are united. The proposition that the energy of the whole TM is additive on the P−1 energies of TsMs including in the DTM, i.e. E = E0 + E1 + … + EP−1 = ∑ Ep , is formulated p=0 and proofed by the authors but due to lack of the space is omitted in that article.
Let’s consider a common implementation of DTM taking into account a parallel implementation of foregoing procedures.
Initialization. At this stage we assume that TsMs included into DTM are constructed and initialized. Construction and initialization are conducted following the mentioned above scheme of distribution of DTM neurons among the set of available processors. After the structure of each TsM is defined, TsMs are provided with the following characteristics: the matrix of neurons weights, vector of neurons thresholds, and vector of neurons biases. Thus, on the current stage we have the set of TsMs, and the elements of this set are
subTM p = {Wp , I p ,Tp , Inp}, p = 0,( P −1) , where subTM p – p -th TsM, Wp – the matrix of its neurons weights, I p – the vector of neurons biases, Tp – the vector of neurons thresholds, and Inp – the vector of initial states of TsM’s neurons. Matrixes Wp and vectors I p and Tp are defined according to the following formulas: W = {wij;i, j = 1, N} = WW10 = {{wwii10jj;;ii == 11,, NN10;; jj ==11,,NN}} = {wij;i = 1, N0; j = 1, N} {wij;i = N0 +1, N0 + N1; j = 1, N} WP−1 P−2 P−1 {wiPj−1;i = 1, NP−1; j = 1, N} wij;i = ∑k=0 Nk +1, ∑k=0 Nk ; j = 1, N {ij ; j = 1, N0} I = {ij ; j = 1, N} = III10P−1 = {{{iii10Pjjj;;−1jj;==j 11=,,1NN,10N}}P−1} = {iijj;; jj == NP∑−02 +N1k,+N10,+∑P−N1N1}
k=0 k=0 k T = {t j ; j = 1, N} = T10 = {{tt10jj;; jj ==11,,NN10}} T TP−1 {t j; j = 1, N0} {t j; j = N0 +1, N0 + N1} = {t Pj−1; j = 1, NP−1} t j ; j = P∑−2 Nk +1, ∑P−1 N k=0 k=0 k
Vector In of initial states of the whole TM neurons is random generated, and then cut on P parts, each of which (i.e. Inp ) is corresponded to the concrete TsM.
The local cycle of the TM. Let’s consider the local cycle of DTM.
Choose the neuron-candidate for the next move. At the first step of the TM local cycle we search for neuron on each TsM, which should change its state on current iteration. The criterion to choose such a neuron is defined as the following: ΔEp (S j ) = {min{ΔEp (Si ) | i = 1, N p} : k − t j ≤ l ∨ Ep (S) + ΔEp (S j ) < Ep (S0)} . (7) p = 0,( P −1) (3) (4) (5) (6) Thus, the search of neurons satisfied to the condition (7) is performed in parallel on the hosts of CN.
The comparison of found neurons. After the neuron satisfied to the condition (7) is found on each host, the search with help of STMP reduce operations defined by authors for MPI_Allreduce function is performed within the whole DTM to find the neuron j* , such that ΔE(S j* ) = min{ΔEp (S j ) | p = 0,( P −1)} .
Change the energy value of neurons. After the required neuron j* has been found, and each TsM has information about it, each neuron of subTM p , p = 0,( P −1) changes its ΔE(Si ) value. The calculation of DTM energy function change is done in parallel on each subTM p . Further the cycle is repeated following described scheme until the condition of exit from the local cycle of the TM is satisfied.
The global cycle of the TM. We select neuron, that didn’t change its state longest, on each TsMs. The number j of this neuron on each subTM p is defined according to the following criteria: (t j )p = min{ti | i = 1, N p}, p = 0,( P −1) . (8) The search of (t j )p is done on the available processors in parallel according to the formula (8).
The comparison of found neurons. After the neuron satisfied to the condition (8) is found on each host, the search with help of LTMP reduce operations defined by authors for MPI_Allreduce function is performed within the whole DTM to find the neuron j* , such that t j* = min{(t j )p | p = 0,( P −1)} .
Change the energy value of neurons. After the required neuron j* has been found, and each TsM has information about it, each neuron of subTM p , p = 0,( P −1) changes its ΔE(Si ) value. The calculation of DTM energy function change is done in parallel on each subTM p . Further the cycle is repeated following described scheme until the number of LTMP calls will exceed C : C ∈ Z + ,C ≥ 0 times. After that the search is stopped and the best found state is taken as the final DTM state.
Let’s try to represent the general description as an algorithm outlined step by step. We will use the following notations: N – the number of neurons in the DTM, i.e. S = S0 = S00 = N ; N p – the number of neurons including into the TsM subTM p , where p = 0,( P −1) ; P – the number of processors on which DTM operates.
Step 1. Construct TsMs subTM p and randomly initialize initial states of its neurons. Define the tabu-size l of DTM. Let h = 0 , k = 0 − counters of iterations in the frame of the whole DTM. Let c = 0 and C ≥ 0 − the maximum number of LTMP calls in the frames of the whole DTM. Let β > 0 is defined according to inequality β ⋅ N > l in the frames of the whole DTM too.
Step 2. Find the local minimum energy state S0 . Calculate E(S0 ) and (9) ΔE0 (Si ), i = 1, N0 ΔE(S1) ΔE1(Si ), i = N0 +1, N0 + N1 ΔE(S) = ΔE(S2 ) = , i = 1, N .
P−2 P−1 ΔE(SN ) ΔEP−1(Si ), i = ∑ Nk +1, ∑ N
k=0 k=0 k The values of Ep ( S0 ) and ΔEp (Si ) for p = 0,( P −1) are calculated in parallel on P processors. Let S00 = S0 is the best global state, and E(S00 ) = E(S0 ) is the global minimum of energy. Let S = S0 and E(S) = E(S0 ) . Let ti = −∞, ∀i = 1, N .
Step 3. In the frames of each subTM p choose the neuron j with ΔEp (S j ) satisfied to ΔEp (S j ) = {min{ΔEp (Si ) | i = 1, N p} : k − t j ≤ l ∨ Ep (S) + ΔEp (S j ) < Ep (S0 )}, p = 0,( P −1) .
Step 4. Using STMP reduce operations defined by authors, form the set { j*, ΔE(S j* ), sj*} , where j* – the index of neuron (in the frames of the whole DTM) changing its state at the current moment, ΔE(S j* ) – the change of DTM energy function value after the neuron j* has changed its state, s j* – the new state of neuron j* .
Step 5. If subTM p contains the neuron j* , then t j* = k , sj* = 1− s j* .
Step 6. Let t j* = k , k = k +1 , h = h +1 , S = S j* , E(S) = E(S) + ΔE(S j* ) in the frames of the whole DTM.
Step 7. Update ΔE(S) using (9). The values of ΔEp (Si ) are calculated in parallel on P processors.
Step 8. Determine if the new state S is the new local and / or global minimum energy state: if E(S) < E(S0 ) , then S0 = S , E(S0 ) = E(S ) and h = 0 ; if E(S) < E(S00 ) , then S00 = S and E(S00 ) = E(S) in the frames of the whole DTM.
Step 9. If h < β ⋅ N , go to Step 3., else − to Step 10.
Step 10. If c ≥ C , then the algorithm stops. S00 is the best state. Else, in the frames of each subTM p choose in parallel the neuron j with (t j )p satisfied to (t j )p = min{ti | i = 1, N p}, p = 0,( P −1) . Using LTMP reduce operations defined by authors, form the set { j*, ΔE(S j* ), s j*} , where j* – the index of neuron (in the frames of the whole DTM) changing its state at the current moment, ΔE(S j* ) – the change of DTM energy function value after the neuron j* has changed its state, s j* – the new state of neuron j* . Let S0 = S j* and E(S0 ) = E(S) + ΔE(S j* ) , c = c +1 and h = 0 . Go to Step 6.
It’s worth mentioning that on the Step 10. the new state of local energy minimum E(S0 ) is set without any auxiliary checks, i.e. is can be worse than the previous S0 . Exploiting this technique we exclude stabilization in local energy minimums and expand areas of potential solutions.
In order to evaluate the performance of constructed DTM the set of experiments on mock-up problems with DTM consisting of N = 100 , N = 400 and N = 1600 neurons were done on multi-core cluster. 372 trial solutions were obtained for each mock-up problem depending on the values of < l, C, β > parameters of DTM.
We proposed to use an average acceleration as the metric to evaluate the efficiency of DTM. The dependencies of average acceleration on the number of processors for mock-up problems with N = 100 , N = 400 and N = 1600 are depicted on Fig. 3. DTM gives a linear acceleration.
Fig. 3. Average acceleration on mock-up problems.
In this paper we proposed parallel TS algorithm for DDB OLS synthesis problem.
The constructed DTM was validated and compared with the sequential TM. As
expected, both approaches give the same results with the solutions quality higher than
the quality of solutions received by NN-GA-algorithm [
It is worth mentioning that during the DTM cycles intensive data communication between processors is carried out in the proposed algorithm. Therefore, we can speak about the significant increasing of DTM performance in compare with its consecutive analogue for the high-dimensional problems. This statement is not contrary to our objectives, because the problem of DDB OLS synthesis is important today in view of high dimensionality.