/usr/share/mozart/doc/system/node13.html is in mozart-doc 1.4.0-8ubuntu1.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 | <!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML><HEAD><TITLE>4.4 Parallel Search Engines</TITLE><LINK href="ozdoc.css" rel="stylesheet" type="text/css"></HEAD><BODY><TABLE align="center" border="0" cellpadding="6" cellspacing="6" class="nav"><TR bgcolor="#DDDDDD"><TD><A href="node12.html#sec.search.object"><< Prev</A></TD><TD><A href="node9.html">- Up -</A></TD></TR></TABLE><DIV id="section.search.parallel"><H2><A name="section.search.parallel">4.4 Parallel Search Engines</A></H2><P> 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. </P><DIV class="apropos"><P class="margin">When to use?</P><P> 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. </P></DIV><DIV class="apropos"><P class="margin">What to do?</P><P> Your scripts do not need rewriting. They must be wrapped into a functor definition. </P></DIV><DIV id="section.search.parallel.example"><H3><A name="section.search.parallel.example">4.4.1 An Example</A></H3><P> Let us take as small constraint problem the fraction problem, which is explained in <A href="../fdt/node31.html#section.propagators.fractions">Section 7.1 of ``Finite Domain Constraint Programming in Oz. A Tutorial.''</A>. 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. </P><P> The script as you can try it from the <A href="../opi/index.html">OPI</A>, looks as follows: </P><P></P><DL><DT><SPAN class="chunktitle"><SPAN class="chunkborder"><</SPAN><A name="label108">Fractions script</A><SPAN class="chunkborder">>=</SPAN></SPAN></DT><DD class="code"><CODE><SPAN class="keyword">proc</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">Script</SPAN> Root}<BR> sol(a:A b:B c:C d:D e:E f:F g:G h:H i:I) = Root<BR> BC = {FD<SPAN class="keyword">.</SPAN>decl}<BR> EF = {FD<SPAN class="keyword">.</SPAN>decl}<BR> HI = {FD<SPAN class="keyword">.</SPAN>decl}<BR><SPAN class="keyword">in</SPAN> <BR> Root <SPAN class="keyword">:::</SPAN> 1<SPAN class="keyword">#</SPAN>9<BR> {FD<SPAN class="keyword">.</SPAN>distinct Root}<BR> BC <SPAN class="keyword">=:</SPAN> 10<SPAN class="keyword">*</SPAN>B <SPAN class="keyword">+</SPAN> C<BR> EF <SPAN class="keyword">=:</SPAN> 10<SPAN class="keyword">*</SPAN>E <SPAN class="keyword">+</SPAN> F<BR> HI <SPAN class="keyword">=:</SPAN> 10<SPAN class="keyword">*</SPAN>H <SPAN class="keyword">+</SPAN> I <BR> A<SPAN class="keyword">*</SPAN>EF<SPAN class="keyword">*</SPAN>HI <SPAN class="keyword">+</SPAN> D<SPAN class="keyword">*</SPAN>BC<SPAN class="keyword">*</SPAN>HI <SPAN class="keyword">+</SPAN> G<SPAN class="keyword">*</SPAN>BC<SPAN class="keyword">*</SPAN>EF <SPAN class="keyword">=:</SPAN> BC<SPAN class="keyword">*</SPAN>EF<SPAN class="keyword">*</SPAN>HI<BR> {FD<SPAN class="keyword">.</SPAN>distribute ff Root}<BR><SPAN class="keyword">end</SPAN></CODE></DD></DL><P> </P><P> It is wrapped into a functor that must export a single feature <CODE>script</CODE> under which the script (<CODE>Fraction</CODE> in our case) is available. This is easy, the following does the job: </P><P></P><DL><DT><SPAN class="chunktitle"><SPAN class="chunkborder"><</SPAN><A name="label109">Fractions functor</A><SPAN class="chunkborder">>=</SPAN></SPAN></DT><DD class="code"><CODE><SPAN class="keyword">functor</SPAN> <SPAN class="functionname">Fractions</SPAN> <BR><SPAN class="keyword">import</SPAN> FD<BR><SPAN class="keyword">export</SPAN> Script<BR><SPAN class="keyword">define</SPAN> <BR> </CODE><SPAN class="chunktitle"><SPAN class="chunkborder"><</SPAN><A href="node13.html#label108">Fractions script</A><SPAN class="chunkborder">></SPAN></SPAN><CODE> <BR><SPAN class="keyword">end</SPAN></CODE></DD></DL><P> </P><P> If you want to learn more about functors, you should consult <A href="../apptut/index.html">``Application Programming''</A>. </P><P> After executing the functor definition in the OPI, we can now start the search engine. </P><P> Let us assume that we want to create two processes on the computers with hostname <CODE>godzilla</CODE> (because it is a double processor machine), and a single process on both <CODE>orca</CODE> and <CODE>grizzly</CODE>. We create a parallel search engine that runs on these hosts as follows: </P><BLOCKQUOTE class="code"><CODE>E={New Search<SPAN class="keyword">.</SPAN>parallel init(godzilla:2 orca:1 grizzly:1)}</CODE></BLOCKQUOTE><P> </P><P> A list of all solutions <CODE>Xs</CODE> can now be computed as follows: </P><BLOCKQUOTE class="code"><CODE>Xs={E all(Fractions $)}</CODE></BLOCKQUOTE><P> </P><P> Similarly, a single solution <CODE>Ys</CODE> can be computed by </P><BLOCKQUOTE class="code"><CODE>Xs={E one(Fractions $)}</CODE></BLOCKQUOTE><P> Here, <CODE><I>Ys</I></CODE> is either a singleton list containg the solution, or <CODE>nil</CODE> if no solution does exist. Note that the first solution returned is not necessarily the solution found by the non-parallel search engines first. </P><P> Parallel search engines support a (rudimentary) form of tracing. After </P><BLOCKQUOTE class="code"><CODE>{E trace(<SPAN class="keyword">true</SPAN>)}</CODE></BLOCKQUOTE><P> 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. </P><BLOCKQUOTE class="code"><CODE>{E trace(<SPAN class="keyword">false</SPAN>)}</CODE></BLOCKQUOTE><P> switches tracing off again. </P><P> Rather than using a functor as an argument for the methods <CODE>one</CODE> and <CODE>all</CODE> a url can be used that refers to a pickled functor stored under that url. </P><P> 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 <A href="../fdt/node51.html#section.scheduling.hard">Section 11.5 of ``Finite Domain Constraint Programming in Oz. A Tutorial.''</A>). A functor for best solution search must export both <CODE>script</CODE> and <CODE>order</CODE>. How this is done you can see in the functor definition <A href="MT10.oz"><CODE>MT10.oz</CODE></A> for the MT10 problem. </P><P> Now the list of solutions <CODE>Zs</CODE> in strictly increasing order can be computed by </P><BLOCKQUOTE class="code"><CODE>Zs={E best(<SPAN class="string">'x-oz://doc/system/MT10.ozf'</SPAN> $)}</CODE></BLOCKQUOTE><P> The best solution is the last element of the list <CODE>Zs</CODE>. The speed up you can expect is almost a factor of six with six processes started! </P><P> 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 <A href="node48.html#chapter.remote">Chapter 13</A>. </P></DIV><DIV id="section.search.parallel.api"><H3><A name="section.search.parallel.api">4.4.2 The Class <CODE>Search<SPAN class="keyword">.</SPAN>parallel</CODE></A></H3><P> The class <CODE>Search<SPAN class="keyword">.</SPAN>parallel</CODE> provides the following methods. </P><DL><DT><CODE>init</CODE> <A name="label111"></A> </DT><DD><BLOCKQUOTE class="synopsis"><P></P><BLOCKQUOTE class="code"><CODE>init(</CODE><CODE>+<I>HostA1</I></CODE><CODE>:</CODE><CODE>+<I>I1</I></CODE><CODE><SPAN class="keyword">#</SPAN></CODE><CODE>+<I>ForkA1</I></CODE><CODE> <SPAN class="keyword">...</SPAN> </CODE><CODE>+<I>HostAn</I></CODE><CODE>:</CODE><CODE>+<I>In</I></CODE><CODE><SPAN class="keyword">#</SPAN></CODE><CODE>+<I>ForkAn</I></CODE><CODE>)</CODE></BLOCKQUOTE><P> </P></BLOCKQUOTE></DD><DD><P>Creates and initializes a new parallel search engine by forking new Oz processes. At host <CODE><I>HostA1</I></CODE> the number of newly forked processes is <CODE><I>I1</I></CODE> and the fork method <CODE><I>ForkA1</I></CODE> is used (see <A href="node48.html#chapter.remote">Chapter 13</A> for a discussion of fork methods), and so on. </P><P> For example, </P><BLOCKQUOTE class="code"><CODE>E={New Search<SPAN class="keyword">.</SPAN>parallel init(wallaby: 1<SPAN class="keyword">#</SPAN>automatic<BR> godzilla: 2<SPAN class="keyword">#</SPAN>ssh <BR> grizzly: 1<SPAN class="keyword">#</SPAN>ssh)}</CODE></BLOCKQUOTE><P> creates a single process at the computer <CODE>wallaby</CODE>, two processes at <CODE>godzilla</CODE>, and one process at <CODE>grizzly</CODE>. The fork method for <CODE>wallaby</CODE> is automatically determined, for <CODE>godzilla</CODE> and <CODE>grizzly</CODE> the method <CODE>ssh</CODE> (secure shell) is used. </P><P> Equivalently, this can be abbreviated as follows: </P><BLOCKQUOTE class="code"><CODE>E={New Search<SPAN class="keyword">.</SPAN>parallel init(wallaby godzilla:2<SPAN class="keyword">#</SPAN>ssh grizzly:ssh)}</CODE></BLOCKQUOTE><P> That is, a field with integer feature is assumed to be a host where a single process is to be forked, and the atom <CODE>automatic</CODE> for a fork method or the number <CODE>1</CODE> as number of processes to be forked can be left out. </P></DD><DT><CODE>one</CODE> <A name="label113"></A> </DT><DD><BLOCKQUOTE class="synopsis"><P></P><BLOCKQUOTE class="code"><CODE>one(</CODE><CODE>+<I>FunctorOrUrl</I></CODE><CODE> </CODE><CODE>?<I>Xs</I></CODE><CODE>)</CODE></BLOCKQUOTE><P> </P></BLOCKQUOTE></DD><DD><P>Searches a single solution for the script specified by <CODE><I>FunctorOrUrl</I></CODE>. <CODE><I>FunctorOrUrl</I></CODE> 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 <CODE>script</CODE>. </P><P> Returns in <CODE><I>Xs</I></CODE> either <CODE>nil</CODE> in case no solution does exists, or a singleton list containing the solution. </P><P> Blocks until search terminates. </P></DD><DT><CODE>all</CODE> <A name="label115"></A> </DT><DD><BLOCKQUOTE class="synopsis"><P></P><BLOCKQUOTE class="code"><CODE>all(</CODE><CODE>+<I>FunctorOrUrl</I></CODE><CODE> </CODE><CODE>?<I>Xs</I></CODE><CODE>)</CODE></BLOCKQUOTE><P> </P></BLOCKQUOTE></DD><DD><P>Searches all solutions for the script specified by <CODE><I>FunctorOrUrl</I></CODE>. <CODE><I>FunctorOrUrl</I></CODE> 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 <CODE>script</CODE>. </P><P> Returns in <CODE><I>Xs</I></CODE> the list of solutions. </P><P> Blocks until search terminates. </P></DD><DT><CODE>best</CODE> <A name="label117"></A> </DT><DD><BLOCKQUOTE class="synopsis"><P></P><BLOCKQUOTE class="code"><CODE>best(</CODE><CODE>+<I>FunctorOrUrl</I></CODE><CODE> </CODE><CODE>?<I>Xs</I></CODE><CODE>)</CODE></BLOCKQUOTE><P> </P></BLOCKQUOTE></DD><DD><P>Searches the best solution for the script and order specified by <CODE><I>FunctorOrUrl</I></CODE>. <CODE><I>FunctorOrUrl</I></CODE> 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 <CODE>script</CODE> and uses as order for branch and bound search the fields <CODE>order</CODE>. </P><P> Returns in <CODE><I>Xs</I></CODE> either <CODE>nil</CODE> 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. </P><P> Blocks until search terminates. </P></DD><DT><CODE>stop</CODE> <A name="label119"></A> </DT><DD><BLOCKQUOTE class="synopsis"><P></P><BLOCKQUOTE class="code"><CODE>stop()</CODE></BLOCKQUOTE><P> </P></BLOCKQUOTE></DD><DD><P>Stops the current search started by <CODE>one</CODE>, <CODE>all</CODE>, or <CODE>best</CODE>. </P><P> Blocks until search has been terminated. </P></DD><DT><CODE>close</CODE> <A name="label121"></A> </DT><DD><BLOCKQUOTE class="synopsis"><P></P><BLOCKQUOTE class="code"><CODE>close()</CODE></BLOCKQUOTE><P> </P></BLOCKQUOTE></DD><DD><P>Closes the object and terminates all forked Oz processes. </P></DD><DT><CODE>trace</CODE> <A name="label123"></A> </DT><DD><BLOCKQUOTE class="synopsis"><P></P><BLOCKQUOTE class="code"><CODE>trace(</CODE><CODE>+<I>B</I></CODE><CODE>)</CODE></BLOCKQUOTE><P> </P></BLOCKQUOTE></DD><DD><P>Switches graphical tracing of search tree delegation on or off, depending on <CODE>+<I>B</I></CODE>. </P><DIV class="danger"><P class="margin"><IMG align="top" alt="Danger" src="danger.gif"></P><P> Method is highly speculative and is subject to change. </P></DIV></DD></DL><P> </P></DIV></DIV><TABLE align="center" border="0" cellpadding="6" cellspacing="6" class="nav"><TR bgcolor="#DDDDDD"><TD><A href="node12.html#sec.search.object"><< Prev</A></TD><TD><A href="node9.html">- Up -</A></TD></TR></TABLE><HR><ADDRESS><A href="http://www.ps.uni-sb.de/~duchier/">Denys Duchier</A>, <A href="http://www.ps.uni-sb.de/~kornstae/">Leif Kornstaedt</A>, <A href="http://www.ps.uni-sb.de/~homik/">Martin Homik</A>, <A href="http://www.ps.uni-sb.de/~tmueller/">Tobias Müller</A>, <A href="http://www.ps.uni-sb.de/~schulte/">Christian Schulte</A> and <A href="http://www.info.ucl.ac.be/~pvr">Peter Van Roy</A><BR><SPAN class="version">Version 1.4.0 (20110908185330)</SPAN></ADDRESS></BODY></HTML>
|