<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML><HEAD><TITLE>9.1 A Naive Distribution Strategy</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="node40.html">- Up -</A></TD><TD><A href="node42.html#section.user-defined.split">Next >></A></TD></TR></TABLE><DIV id="section.user-defined.naive"><H2><A name="section.user-defined.naive">9.1 A Naive Distribution Strategy</A></H2><P>The distributor we program in this section implements a naive distribution strategy: choose the first not yet determined variable from a list and try the smallest possible value first. The distributor is shown in <A href="node41.html#fig.naivedist">Figure 9.1</A>. </P><DIV id="fig.naivedist"><HR><P><A name="fig.naivedist"></A></P><DL class="anonymous"><DD class="code"><CODE><SPAN class="keyword">proc</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">NaiveDistributor</SPAN> Is}<BR> {Space<SPAN class="keyword">.</SPAN>waitStable}<BR> <SPAN class="keyword">local</SPAN> <BR> Fs={Filter Is <SPAN class="keyword">fun</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">$</SPAN> I} {FD<SPAN class="keyword">.</SPAN>reflect<SPAN class="keyword">.</SPAN>size I}<SPAN class="keyword">></SPAN>1 <SPAN class="keyword">end</SPAN>}<BR> <SPAN class="keyword">in</SPAN> <BR> <SPAN class="keyword">case</SPAN> Fs<BR> <SPAN class="keyword">of</SPAN> nil <SPAN class="keyword">then</SPAN> <SPAN class="keyword">skip</SPAN> <BR> <SPAN class="keyword">[]</SPAN> F<SPAN class="keyword">|</SPAN>Fr <SPAN class="keyword">then</SPAN> M={FD<SPAN class="keyword">.</SPAN>reflect<SPAN class="keyword">.</SPAN>min F} <SPAN class="keyword">in</SPAN> <BR> <SPAN class="keyword">choice</SPAN> F=M {NaiveDistributor Fr}<BR> <SPAN class="keyword">[]</SPAN> F<SPAN class="keyword">\=:</SPAN>M {NaiveDistributor Fs}<BR> <SPAN class="keyword">end</SPAN> <BR> <SPAN class="keyword">end</SPAN> <BR> <SPAN class="keyword">end</SPAN> <BR><SPAN class="keyword">end</SPAN></CODE></DD></DL><P class="caption"><STRONG>Figure 9.1:</STRONG> A distributor for a naive distribution strategy.</P><HR></DIV><P></P><P class="margin">choice-statements</P><P> To maximize the information available for distribution we wait until the computation space becomes stable. A thread that executes <CODE>{Space<SPAN class="keyword">.</SPAN>waitStable}</CODE> blocks until its hosting computation space <I>S</I> becomes stable. When <I>S</I> becomes stable, execution proceeds with the next statement. </P><P>Thus, the variable <CODE>Fs</CODE> in <A href="node41.html#fig.naivedist">Figure 9.1</A> denotes the list of undetermined variables after <I>S</I> has become stable. To detect undetermined variables we use the procedure <CODE>FD<SPAN class="keyword">.</SPAN>reflect<SPAN class="keyword">.</SPAN>size</CODE> that returns the current size of a variable's domain. If the domain size is one, the variable is determined and consequently not included in the list <CODE>Fs</CODE>. </P><P>Then the least possible value for the first undetermined variable <CODE>F</CODE> is computed by </P><BLOCKQUOTE class="code"><CODE>M={FD<SPAN class="keyword">.</SPAN>reflect<SPAN class="keyword">.</SPAN>min I}</CODE></BLOCKQUOTE><P> </P><P class="margin">binary choice-statements</P><P> We now have to distribute. To this aim Oz provides a binary choice-statement. If a thread reaches the statement </P><BLOCKQUOTE class="code"><CODE><SPAN class="keyword">choice</SPAN> </CODE><I>S1</I><CODE> <BR><SPAN class="keyword">[]</SPAN> </CODE><I>S2</I><CODE> <BR><SPAN class="keyword">end</SPAN></CODE></BLOCKQUOTE><P> the thread is blocked until its hosting computation space becomes stable. </P><P>If the space has become stable, the computation in the blocked thread is resumed and it is distributed. Distribution yields two spaces, one obtained by replacing the choice-statement by the statement <I>S1</I>, one obtained by replacing the choice-statement by the statement <I>S2</I>. All search engines in this tutorial will explore the space first which hosts <I>S1</I>. </P><P>In <A href="node41.html#fig.naivedist">Figure 9.1</A>, we distribute with the constraint that the selected variable is determined to the current least possible value. The distribution is done if no undetermined variables are left. </P></DIV><TABLE align="center" border="0" cellpadding="6" cellspacing="6" class="nav"><TR bgcolor="#DDDDDD"><TD><A href="node40.html">- Up -</A></TD><TD><A href="node42.html#section.user-defined.split">Next >></A></TD></TR></TABLE><HR><ADDRESS><A href="http://www.ps.uni-sb.de/~schulte/">Christian Schulte</A> and <A href="http://www.ps.uni-sb.de/~smolka/">Gert Smolka</A><BR><SPAN class="version">Version 1.4.0 (20090610)</SPAN></ADDRESS></BODY></HTML>
distrib
>
Mandriva
>
2010.0
>
i586
>
media
>
contrib-release
>
by-pkgid
>
bd5c3d824c3db63ffd9226c15941e6ad
>
files
>
1216
