/usr/share/mozart/doc/fdt/node50.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 3 4 5 6 | <!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML><HEAD><TITLE>11.4 Strong Serializers</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="node49.html#section.scheduling.edgefinding"><< Prev</A></TD><TD><A href="node46.html">- Up -</A></TD><TD><A href="node51.html#section.scheduling.hard">Next >></A></TD></TR></TABLE><DIV id="section.scheduling.strongser"><H2><A name="section.scheduling.strongser">11.4 Strong Serializers</A></H2><P>So far we only have considered serializers which result in a search tree which depth grows quadratically in the number of tasks on a resource. In this section we will introduce a serializer where the depth of a search tree grows only linear in the number of tasks. In each choice node we will order several tasks not only two tasks. each choice node but several of them. This is done by stating that a single task must precede all other tasks on a resource. </P><P>A further disadvantage of the bottleneck serializer considered in <A href="node49.html#section.scheduling.edgefinding">Section 11.3</A> is its static bottleneck criterion. Instead we take the changing size of domains during run time into account to select a resource which should be serialized. This is also the approach chosen for the first-fail distribution strategy. </P><DIV class="apropos"><P class="margin">supply</P><P> We start with a better criterion to select a resource. Let <IMG alt="S" src="latex7.png"> be the set of tasks on a resource <IMG alt="r" src="latex319.png">. The available time to schedule all the tasks in <IMG alt="S" src="latex7.png"> is <IMG alt="\Lct{S}-\Est{S}" src="latex320.png">. This value is called the <A name="label153"></A><EM>supply</EM> of <IMG alt="r" src="latex319.png">. The overall time needed to schedule the tasks in <IMG alt="S" src="latex7.png"> is <IMG alt="\Dur{S}" src="latex321.png">. </P></DIV><DIV class="apropos"><P class="margin">demand, global slack</P><P> This value is called the <A name="label154"></A><EM>demand</EM> of <IMG alt="r" src="latex319.png">. The difference between supply and demand is called <A name="label155"></A><EM>global slack</EM> of <IMG alt="r" src="latex319.png"> (<IMG alt="{\it slack}^r_g" src="latex322.png">) and denotes the free space on the resource. The smaller the value of the global slack the more critical is the resource (the tasks on it can be shifted only in a very limited way). </P></DIV><P>Hence, one could use the global slack as a criterion to select a resource. But a small example reveals that this criterion has still an important flaw: it is too coarse-grained. Assume <IMG alt="S" src="latex7.png"> to be the set <IMG alt="\{A,B,C\}" src="latex323.png"> described in the following table. </P><TABLE align="center" bgcolor="#f0f0e0"><TR valign="top"><TH><P>task</P></TH><TH><P>domain</P></TH><TH><P><IMG alt="\Dur{t}" src="latex324.png"></P></TH></TR><TR valign="top"><TD><P>A</P></TD><TD><P><IMG alt="0\#18" src="latex325.png"></P></TD><TD><P>2</P></TD></TR><TR valign="top"><TD><P>B</P></TD><TD><P><IMG alt="1\#7" src="latex326.png"></P></TD><TD><P>5</P></TD></TR><TR valign="top"><TD><P>C</P></TD><TD><P><IMG alt="2\#9" src="latex327.png"></P></TD><TD><P>4</P></TD></TR></TABLE><P> </P><P>The global slack is <IMG alt="\Lct{S} - \Est{S} - \Dur{S} = 20 - 0 - 11 =
9" src="latex328.png">. But now consider the set <IMG alt="S'=\{B,C\}" src="latex329.png">. We obtain <IMG alt="\Lct{S'} - \Est{S'} - \Dur{S'} = 13 - 1 - 9 = 3" src="latex330.png">. This means that for <IMG alt="B" src="latex39.png"> and <IMG alt="C" src="latex31.png"> we have far less free place to shift the tasks than it is indicated by the global slack. Thus, we refine our criterion as follows. </P><DIV class="apropos"><P class="margin">task interval</P><P> Let <IMG alt="T_1" src="latex283.png"> and <IMG alt="T_2" src="latex284.png"> be two tasks on the same resource <IMG alt="r" src="latex319.png"> and <IMG alt="S" src="latex7.png"> the set of all tasks running on <IMG alt="r" src="latex319.png">. If <IMG alt="\Est{T_1} \leq \Est{T_2}" src="latex331.png"> and <IMG alt="\Lct{T_1} \leq \Lct{T_2}" src="latex332.png">, we call the set <IMG alt="I(T_1,T_2) = \{ T\ |\ T \in S,\ \Est{T_1} \leq \Est{T},\ \Lct{T} \leq
\Lct{T_2}\} " src="latex333.png"> the <A name="label156"></A><EM>task interval</EM> defined by <IMG alt="T_1" src="latex283.png"> and <IMG alt="T_2" src="latex284.png"> (see also <A href="bib.html#caseau.94a">[CL94]</A>). Intuitively, a task interval is the set of tasks which must be scheduled between <IMG alt="\Est{T_1}" src="latex334.png"> and <IMG alt="\Lct{T_2}" src="latex335.png">. Let <IMG alt="I_r" src="latex336.png"> be the set of all task intervals on the resource <IMG alt="r" src="latex319.png">. </P></DIV><DIV class="apropos"><P class="margin">local slack</P><P> The <A name="label157"></A><EM>local slack</EM> of <IMG alt="r" src="latex319.png"> (<IMG alt="{\it slack}^r_l" src="latex337.png">) is now defined as </P><BLOCKQUOTE><P><IMG alt="\min(\{\Lct{I}-\Est{I}-\Dur{I}|I \in I_r\})" src="latex338.png"></P></BLOCKQUOTE><P>. </P></DIV><DIV class="apropos"><P class="margin">critical resource</P><P> If two resources have the same local slack, we use the global slack to break this tie. Thus, we select the resource next for serialization which is minimal according to the lexicographic order <IMG alt="({\it
slack}^r_l,{\it slack}^r_g)" src="latex339.png">. The selected resource is called the <A name="label158"></A><EM>critical resource</EM>. Note that a local slack of a resource with <IMG alt="n" src="latex43.png"> tasks can be computed in <IMG alt="O(n^3)" src="latex317.png"> time. </P></DIV><P>Next we will determine the constraints to distribute with. Let <IMG alt="u(r)" src="latex340.png"> be the set of tasks on the critical resource <IMG alt="r" src="latex319.png"> which are not ordered with all other tasks on <IMG alt="r" src="latex319.png"> yet. Using the ideas of edge-finding we compute the set <IMG alt="F" src="latex341.png"> of all tasks in <IMG alt="u(r)" src="latex340.png"> which can be scheduled first: <IMG alt=" F = \{T \ |\ T \in u(r), \Lct{u(r) \backslash
\{T\}} - \Est{T} \geq \Dur{u(r)}\}." src="latex342.png"> In a distribution step each of the tasks in <IMG alt="F" src="latex341.png">, say <IMG alt="T" src="latex101.png">, may be scheduled before all others and <IMG alt="T" src="latex101.png"> can be deleted from <IMG alt="u(r)" src="latex340.png">. The task in <IMG alt="F" src="latex341.png"> which is smallest according to the lexicographic order <IMG alt="(\Est{T},\Lst{T})" src="latex343.png"> is first selected for distribution. By this choice we leave as much space for the remaining tasks to be scheduled on the resource. We now distribute with the constraints that <IMG alt="T" src="latex101.png"> precedes all other tasks in <IMG alt="u(r)" src="latex340.png">: <IMG alt="\forall T' \in u(r)\backslash \{T\}:\ T + \Dur{T} \leq T'." src="latex344.png"> If this choice leads to failure, the next task in <IMG alt="F" src="latex341.png"> is tried according to our criterion. </P><P>The overall strategy is as follows. We select a critical resource according to our criterion developed above. Then we serialize the critical resource by successively selecting tasks to be scheduled before all others. After the critical resource is serialized, the next critical resource is selected for serialization. This process is repeated until all resources are serialized. </P><P>The described serializer follows the ideas of <A href="bib.html#baptiste.95a">[BLN95]</A> which in turn adopts ideas of <A href="bib.html#carlier.89">[CP89]</A>. The serializer is available through <CODE>Schedule<SPAN class="keyword">.</SPAN>firstsDist</CODE>. </P><P>We immediately apply our new serializer to the bridge problem. </P><DL class="anonymous"><DD class="code"><CODE>{ExploreBest {Compile Bridge <BR> Schedule<SPAN class="keyword">.</SPAN>serialized<BR> Schedule<SPAN class="keyword">.</SPAN>firstsDist} <BR> Earlier}</CODE></DD></DL><P> The optimal solution can be found and its optimality can be proven with only 90 choice nodes. Now the proof of optimality (problem <CODE>OptBridge</CODE>) needs only 22 choice nodes. </P><P>But we can do better. In addition to the set <IMG alt="F" src="latex341.png"> of tasks we can compute the set <IMG alt="L" src="latex100.png"> of tasks which may be scheduled after all other tasks (see also <A href="node49.html#section.scheduling.edgefinding">Section 11.3</A>). In this case the task <IMG alt="T" src="latex101.png"> which is tried first to be scheduled after all the others is the one which is maximal according to the lexicographic order <IMG alt="(\Lct{T},\Ect{T})" src="latex345.png">. A further serializer computes both <IMG alt="F" src="latex341.png"> and <IMG alt="L" src="latex100.png">. Then it selects the set which has the smallest cardinality. This serializer is available through <CODE>Schedule<SPAN class="keyword">.</SPAN>firstsLastsDist</CODE>. </P><P>Using <CODE>Schedule<SPAN class="keyword">.</SPAN>firstsLastsDist</CODE> we can find the optimal solution and prove its optimality with only 30 choice nodes (see <A href="node50.html#fig.scheduling.bridgstronge2">Figure 11.17</A>). Note that in contrast to <A href="node48.html#fig.scheduling.bridge">Figure 11.15</A> where we have needed 8 solutions to reach the optimal one, we now find the optimal solution immediately. The size of the search tree is reduced by more than an order of magnitude. </P><DIV id="fig.scheduling.bridgstronge2"><HR><P><A name="fig.scheduling.bridgstronge2"></A></P><DIV align="center"><IMG alt="" src="bridge-tree-2.png" id="pic.bridge-tree-2"></DIV><P class="caption"><STRONG>Figure 11.17:</STRONG> A search tree for the bridge problem.</P><HR></DIV><P> </P><P>The optimality of the problem can be proven with only 4 choice nodes. </P><P>Let <IMG alt="m" src="latex93.png"> be the number of resources to consider in a scheduling problem and let <IMG alt="n" src="latex43.png"> be the maximal number of tasks on a common resource. Then the described serializer has a run time complexity of <IMG alt="O(m \cdot n^3)" src="latex346.png"> if a resource has to be selected and <IMG alt="O(n)" src="latex347.png"> if only the set <IMG alt="F" src="latex341.png"> or <IMG alt="L" src="latex100.png"> has to be computed. </P><DIV class="apropos"><P class="margin">resource-oriented</P><P> Because this kind of serializer successively serializes all resources, we call it <A name="label159"></A><EM>resource-oriented serializer</EM>. </P></DIV></DIV><TABLE align="center" border="0" cellpadding="6" cellspacing="6" class="nav"><TR bgcolor="#DDDDDD"><TD><A href="node49.html#section.scheduling.edgefinding"><< Prev</A></TD><TD><A href="node46.html">- Up -</A></TD><TD><A href="node51.html#section.scheduling.hard">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 (20110908185330)</SPAN></ADDRESS></BODY></HTML>
|