## 4.4 Parallel Search Engines

Parallel search engines use multiple networked computers to speed up the exploration of search trees. During exploration of a search tree entire subtrees are delegated to multiple workers. Each worker is powered by a single Oz engine. This means that all worker run in parallel: subtrees are explored in parallel rather than sequentially. Each engine runs on a networked computer, or multiple engines can even run on a single networked computer. The latter makes sense if the computer has more than a single processor and can run the engines in parallel.

When to use?

Delegating subtrees for exploration to workers incurs some overhead. But if the number of subtrees is significant, parallel execution can gain over the required overhead. If no subtrees exist (the search tree is just a single path) or the subtrees are small (just a small search tree), parallel search engines do not improve. Branch and bound search for hard problems (like scheduling problems) in particular can take advantage. Currently, you can expect linear speedup for up to six workers (that is, six times faster!) with well suited problems.

What to do?

Your scripts do not need rewriting. They must be wrapped into a functor definition.

### 4.4.1 An Example

Let us take as small constraint problem the fraction problem, which is explained in Section 7.1 of ``Finite Domain Constraint Programming in Oz. A Tutorial.''. However we will choose here a formulation that artificially increases the search tree in that we do not impose a canonical order and leave out redundant constraints.

The script as you can try it from the OPI, looks as follows:

`proc {Script Root}   sol(a:A b:B c:C d:D e:E f:F g:G h:H i:I) = Root   BC = {FD.decl}   EF = {FD.decl}   HI = {FD.decl}in    Root ::: 1#9   {FD.distinct Root}   BC =: 10*B + C   EF =: 10*E + F   HI =: 10*H + I     A*EF*HI + D*BC*HI + G*BC*EF =: BC*EF*HI   {FD.distribute ff Root}end`

It is wrapped into a functor that must export a single feature `script` under which the script (`Fraction` in our case) is available. This is easy, the following does the job:

`functor Fractions import FDexport Scriptdefine     `` end`

After executing the functor definition in the OPI, we can now start the search engine.

Let us assume that we want to create two processes on the computers with hostname `godzilla` (because it is a double processor machine), and a single process on both `orca` and `grizzly`. We create a parallel search engine that runs on these hosts as follows:

`E={New Search.parallel init(godzilla:2 orca:1 grizzly:1)}`

A list of all solutions `Xs` can now be computed as follows:

`Xs={E all(Fractions \$)}`

Similarly, a single solution `Ys` can be computed by

`Xs={E one(Fractions \$)}`

Here, `Ys` is either a singleton list containg the solution, or `nil` if no solution does exist. Note that the first solution returned is not necessarily the solution found by the non-parallel search engines first.

Parallel search engines support a (rudimentary) form of tracing. After

`{E trace(true)}`

a window appears as that gives graphical information on how many nodes each Oz engine explored. The graphical information is in a very early beta stage and will improve soon.

`{E trace(false)}`

switches tracing off again.

Rather than using a functor as an argument for the methods `one` and `all` a url can be used that refers to a pickled functor stored under that url.

Search for best solution works similar. Let us consider as a more interesting example the really hard scheduling problem MT10 (for more information on that problem see Section 11.5 of ``Finite Domain Constraint Programming in Oz. A Tutorial.''). A functor for best solution search must export both `script` and `order`. How this is done you can see in the functor definition `MT10.oz` for the MT10 problem.

Now the list of solutions `Zs` in strictly increasing order can be computed by

`Zs={E best('x-oz://doc/system/MT10.ozf' \$)}`

The best solution is the last element of the list `Zs`. The speed up you can expect is almost a factor of six with six processes started!

Parallel search engines only work properly, if your computing environment is set up such that the facilities for remote module managers work. The requirements are described in Chapter 13.

### 4.4.2 The Class `Search.parallel`

The class `Search.parallel` provides the following methods.

`init`

`init(``+HostA1``:``+I1``#``+ForkA1`` ... ``+HostAn``:``+In``#``+ForkAn``)`

Creates and initializes a new parallel search engine by forking new Oz processes. At host `HostA1` the number of newly forked processes is `I1` and the fork method `ForkA1` is used (see Chapter 13 for a discussion of fork methods), and so on.

For example,

`E={New Search.parallel init(wallaby:  1#automatic                            godzilla: 2#ssh                              grizzly:  1#ssh)}`

creates a single process at the computer `wallaby`, two processes at `godzilla`, and one process at `grizzly`. The fork method for `wallaby` is automatically determined, for `godzilla` and `grizzly` the method `ssh` (secure shell) is used.

Equivalently, this can be abbreviated as follows:

`E={New Search.parallel init(wallaby godzilla:2#ssh grizzly:ssh)}`

That is, a field with integer feature is assumed to be a host where a single process is to be forked, and the atom `automatic` for a fork method or the number `1` as number of processes to be forked can be left out.

`one`

`one(``+FunctorOrUrl`` ``?Xs``)`

Searches a single solution for the script specified by `FunctorOrUrl`. `FunctorOrUrl` must be either a functor or a url given as virtual string that refers to a pickled functor. The engine runs the script that must be exported by the field `script`.

Returns in `Xs` either `nil` in case no solution does exists, or a singleton list containing the solution.

Blocks until search terminates.

`all`

`all(``+FunctorOrUrl`` ``?Xs``)`

Searches all solutions for the script specified by `FunctorOrUrl`. `FunctorOrUrl` must be either a functor or a url given as virtual string that refers to a pickled functor. The engine runs the script that must be exported by the field `script`.

Returns in `Xs` the list of solutions.

Blocks until search terminates.

`best`

`best(``+FunctorOrUrl`` ``?Xs``)`

Searches the best solution for the script and order specified by `FunctorOrUrl`. `FunctorOrUrl` must be either a functor or a url given as virtual string that refers to a pickled functor. The engine runs the script that must be exported by the field `script` and uses as order for branch and bound search the fields `order`.

Returns in `Xs` either `nil` in case no solution does exists, or a list containing the solutions in increasing order. That is the last element (if any) is the best solution.

Blocks until search terminates.

`stop`

`stop()`

Stops the current search started by `one`, `all`, or `best`.

Blocks until search has been terminated.

`close`

`close()`

Closes the object and terminates all forked Oz processes.

`trace`

`trace(``+B``)`

Switches graphical tracing of search tree delegation on or off, depending on `+B`.

Method is highly speculative and is subject to change.

Denys Duchier, Leif Kornstaedt, Martin Homik, Tobias Müller, Christian Schulte and Peter Van Roy
Version 1.4.0 (20080702)