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:

<Fractions script>=

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:

<Fractions functor>=

functor Fractions 
import FD
export Script
define  
   <Fractions script> 
end

If you want to learn more about functors, you should consult ``Application Programming''.

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.