The parallel extension of CONDOR

We will use a client-server approach. The main node, the server will have two concurrent process:

• The main process on the main computer is the classical non-parallelized version of the algorithm, described at the beginning of Chapter 6. There is an exchange of information with the second/parallel process on steps 4 and 16 of the original algorithm.
• The goal of the second/parallel process on the main computer is to increase the quality of the model $q_k(s)$ by using client computers to sample $f(x)$ at specific interpolation sites.

The client nodes are performing the following:

1. Wait to receive from the second/parallel process on the server a sampling site (a point).
2. Evaluate the objective function at this site and return immediately the result to the server.
3. Go to step 1.

Several strategies have been tried to select good sampling sites. We describe here the most promising one. The second/parallel task is the following:

A.

Make a local copy $q_{(copy)}(s)$ of $q_k(s)$ (and of the associated Lagrange Polynomials $P_{j}(x)$)

B.

Make a local copy $\mbox{$\cal J$}$$_{(copy)}$ of the dataset $\mbox{$\cal J$}$$= \{ \boldsymbol{x}_{(1)}, \ldots, \boldsymbol{x}_{(N)} \}$.

C.

Find the index $j$ of the point inside $\mbox{$\cal J$}$$_{(copy)}$ the further away from $\boldsymbol {x}_{(k)}$.

D.

Replace $\boldsymbol{x}_{(j)}$ by a better point which will increase the quality of the approximation of $f(x)$. The computation of this point is done using Equation 3.38: $\boldsymbol{x}_{(j)}$ is replaced in $\mbox{$\cal J$}$$_{(copy)}$ by $\boldsymbol{x}_{(k)}+d$ where $d$ is the solution of the following problem:

$$\max_{d} \{ \vert P_{j,(copy)}(\boldsymbol{x}_{(k)}+d)\vert : \Vert d \Vert \leq \rho \}$$ (6.7)

E.

Ask for an evaluation the objective function at point $\boldsymbol{x}_{(k)}+d$ using a free client computer to performs the evaluation. If there is still a client doing nothing, go back to step C.

F.

Wait for a node to complete its evaluation of the objective function $f(x)$.

G.

Update $q_{(copy)}(x)$ using this new evaluation. Remove $j$ from $\mbox{$\cal J$}$$_{(copy)}$. go to step C.

In the parallel/second process we are always working on a copy of $q_k(x)$, $\mbox{$\cal J$}$, $P_{j,(copy)}(x)$ to avoid any side effect with the main process which is guiding the search. The communication and exchange of information between these two processes are done only at steps 4 and 16 of the main algorithm described in the previous section. Each time the main loop (main process) checks the results of the parallel computations the following is done:

i.

Wait for the parallel/second task to enter the step F described above and block the parallel task inside this step F for the time needed to perform the points ii and iii below.

ii.

Update of $q_k(s)$ using all the points calculated in parallel, discarding the points that are too far away from $x_k$ (at a distance greater than $\rho$). This update is performed using technique described in Section 3.4.3 and Section 3.4.4. We will possibly have to update the index $k$ of the best point in the dataset $\mbox{$\cal J$}$ and $F_{old}$.

iii.

Perform operations described in point A & B of the parallel/second task algorithm above: `` Copy $q_{(copy)}(x)$ from $q(x)$. Copy $\mbox{$\cal J$}$$_{(copy)}$ from $\mbox{$\cal J$}$$= \{ \boldsymbol{x}_{(1)}, \ldots, \boldsymbol{x}_{(N)} \}$ ``.