 Threads:-Task Example Worksheet - Maple Programming Help

The Task Programming Model is a high level multi-threaded programming model.  It enables Maple functions to take advantage of multiple processors, while avoiding much of the complexity of traditional multi-threaded programming.

 > restart;

Overview

Consider the following single threaded Maple code:

 > f := proc( fargs )     # Do some work     return cont( fc1( c1args ), fc2( c2args ) ); end proc;
 ${f}{:=}{\mathbf{proc}}\left({\mathrm{fargs}}\right)\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{return}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathrm{cont}}{}\left({\mathrm{fc1}}{}\left({\mathrm{c1args}}\right){,}{\mathrm{fc2}}{}\left({\mathrm{c2args}}\right)\right)\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{end proc}}$ (1.1)

To compute f, we do some work, executing  fc1, and  fc2, then executing cont, with the return values of fc1 and fc2 passed as arguments.

Tasks can create new tasks, and by doing so a dependency tree is created where some tasks wait for other tasks to complete before they can execute. A leaf can be executed at any time, while the internal nodes are waiting for arguments before they can execute.

Example 1

The following example will illustrate these dependencies.

 > cont := proc( id, ret1, ret2 )     printf( "cont id: %s\n", id );     return [ ret1, ret2 ]; end proc;
 ${\mathrm{cont}}{:=}{\mathbf{proc}}\left({\mathrm{id}}{,}{\mathrm{ret1}}{,}{\mathrm{ret2}}\right)\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathrm{printf}}{}\left({"cont id: %s\n"}{,}{\mathrm{id}}\right){;}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{return}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}\left[{\mathrm{ret1}}{,}{\mathrm{ret2}}\right]\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{end proc}}$ (2.1)
 > task := proc( id, level )     printf( "task id: %s\n", id );     if ( level > 0 ) then         Threads:-Task:-Continue( cont, id,             Task=[task, sprintf( "%s->1", id ), level-1],             Task=[task, sprintf( "%s->2", id ), level-1] );         return "dummy";     else         return id;     end if; end proc;
 ${\mathrm{task}}{:=}{\mathbf{proc}}\left({\mathrm{id}}{,}{\mathrm{level}}\right)\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathrm{printf}}{}\left({"task id: %s\n"}{,}{\mathrm{id}}\right){;}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{if}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{0}{<}{\mathrm{level}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{then}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathrm{Threads}}{:-}{\mathrm{Task}}{:-}{\mathrm{Continue}}{}\left({\mathrm{cont}}{,}{\mathrm{id}}{,}{\mathrm{Task}}{=}\left[{\mathrm{task}}{,}{\mathrm{sprintf}}{}\left({"%s->1"}{,}{\mathrm{id}}\right){,}{\mathrm{level}}{-}{1}\right]{,}{\mathrm{Task}}{=}\left[{\mathrm{task}}{,}{\mathrm{sprintf}}{}\left({"%s->2"}{,}{\mathrm{id}}\right){,}{\mathrm{level}}{-}{1}\right]\right){;}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{return}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{"dummy"}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{else}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{return}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathrm{id}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{end if}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{end proc}}$ (2.2)

This code creates tasks which print an id and then either create child tasks, or simply return their id.  Note that when running on a multiple core machine, the output will change from run to run, and occasionally be interlaced.

 $\left[{"root->1"}{,}{"root->2"}\right]$ (2.3)

In this simple example one can see that the task root ran first, then root's two child tasks, root->1 and root->2, then the continuation task, cont is executed.

The concept of the continuation task is a little strange.  Consider a leaf task in the dependency tree.  If it executes and does not start new child tasks, then it completes, and returns its value to its parent. If executing the leaf task creates new children, then the leaf task is replaced by the continuation task, and the continuation task becomes the parent of the new children.  The continuation tasks form the internal nodes of the dependency tree. Continuation tasks are used because a task that does not call Threads:-Task:-Start or one of the Threads package synchronization routines always runs to completion, once started it will never wait for another task.  Therefore the leaf node will finish without waiting for its children to complete.  Thus the continuation task is a new task that waits for the child tasks to finish and whose return value is passed to the parent of the task which created it

Here is a slightly larger example of this code in action.

 $\left[\left[\left[{"root->1->1->1"}{,}{"root->1->1->2"}\right]{,}\left[{"root->1->2->1"}{,}{"root->1->2->2"}\right]\right]{,}\left[\left[{"root->2->1->1"}{,}{"root->2->1->2"}\right]{,}\left[{"root->2->2->1"}{,}{"root->2->2->2"}\right]\right]\right]$ (2.4)

In this case, we have more tasks so executing this example multiple times is more like to give different orderings.  Notice that the return value is always the same,

regardless of the order the tasks execute.  This is because the return value is determined by the dependency tree, not the order in which the tasks execute.

Example 2

The following example shows how the Task Programming Model can be used to solve a divide and conquer problem.  The following adds the numbers i to j.

 > cont := proc( a, b )     return a + b; end proc;
 ${\mathrm{cont}}{:=}{\mathbf{proc}}\left({a}{,}{b}\right)\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{return}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{a}{+}{b}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{end proc}}$ (3.1)
 > task := proc( i, j )     local k;     if ( j - i < 1000 ) then         return add( k, k=i..j );     else         k := floor( (j-i)/2 ) + i;         Threads:-Task:-Continue( cont, Task=[ task, i, k ], Task=[task, k+1, j ] );     end if; end proc;
 ${\mathrm{task}}{:=}{\mathbf{proc}}\left({i}{,}{j}\right)\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{local}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{k}{;}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{if}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{j}{-}{i}{<}{1000}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{then}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{return}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathrm{add}}{}\left({k}{,}{k}{=}{i}{..}{j}\right)\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{else}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{k}{:=}{\mathrm{floor}}{}\left({1}{/}{2}{*}{j}{-}{1}{/}{2}{*}{i}\right){+}{i}{;}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathrm{Threads}}{:-}{\mathrm{Task}}{:-}{\mathrm{Continue}}{}\left({\mathrm{cont}}{,}{\mathrm{Task}}{=}\left[{\mathrm{task}}{,}{i}{,}{k}\right]{,}{\mathrm{Task}}{=}\left[{\mathrm{task}}{,}{k}{+}{1}{,}{j}\right]\right)\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{end if}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{end proc}}$ (3.2)
 ${5000000050000000}$ (3.3)

Example 3

This example shows how the Task package can be used to calculate a Mandelbrot set.

MandelLoop does the actual computations

 > MandelLoop := proc( X, Y, imageArray, i_low, i_high, j_low, j_high, iter, bailout )     local i, j, Xc, Yc, Xtemp, Ytemp, Xold, Yold, k;     option hfloat;          for i from i_low to i_high do         for j from j_low to j_high do             Xtemp := X[i];             Ytemp := Y[j];             Xc := Xtemp;             Yc := Ytemp;             k := 0;             while k < iter do                 Xold := Xtemp;                 Yold := Ytemp;                 Xtemp := Xold^2-Yold^2+Xc;                 Ytemp := 2*Xold*Yold+Yc;                 if Xtemp^2+Ytemp^2 >= bailout then                      imageArray[j, i, 1] := k;                      imageArray[j, i, 2] := sqrt(Xtemp^2+Ytemp^2);                      break;                 end if;                 k := k + 1;             end do;         end do;     end do; end proc:

MandelTask is the procedure used for tasks in this example.  It uses a basic divide and conquer technique to compute the results.  It divides the X dimension in half, creating a new task for each half.  When the given range contains less that 5 rows, it calls MandelLoop and returns.  Notice that MandelLoop works in place, thus the return values are not used.  In this case we pass the name null as the continuation task, which selects a special predefined continuation task, that simply returns NULL.

 > MandelTask := proc ( X, Y, imageArray, i_low, i_high, j_low, j_high, iter, bailout )     local i, j, i_mid;          if ( i_high - i_low > 5 ) then         i_mid := floor( (i_high-i_low)/2 ) + i_low;         Threads:-Task:-Continue( null,             Task=[MandelTask, X, Y, imageArray, i_low, i_mid, j_low, j_high, iter, bailout],             Task=[MandelTask, X, Y, imageArray, i_mid+1, i_high, j_low, j_high, iter, bailout ] );     else         MandelLoop( X, Y, imageArray, i_low, i_high, j_low, j_high, iter, bailout );     end if; end proc:

The main entry Mandelbrot function.  This calls Threads:-Task:-Start to begin the calculation in the Task Programming Model.

 > Mandelbrot := proc ( ptsY::integer,ptsX::integer,iter::integer, X1::float, X2::float, Y1::float, Y2::float, bailout::float)     local X::Vector, Y::Vector, imageArray::Array, i::int, j::int:     X := Vector(ptsX, i->X1+(X2-X1)*(i-1)/(ptsX-1) , datatype = float);     Y := Vector(ptsY, i->Y1+(Y2-Y1)*(i-1)/(ptsY-1) , datatype = float);     imageArray := Array(1 .. ptsY, 1 .. ptsX, 1 .. 2, datatype = float);     Threads:-Task:-Start( MandelTask, X, Y, imageArray, 1, ptsX, 1, ptsY, iter, bailout );     return imageArray; end proc:

Run the calculation.

 > points := Mandelbrot(600, 600, 100, -2.0, .7, -1.35, 1.35, 10.0 ):
 > pointsColored := Array(1 .. rhs(ArrayDims(points)), 1 .. rhs(ArrayDims(points)), 1 .. 3, datatype = float):
 > for i to rhs(ArrayDims(points)) do    for j to rhs(ArrayDims(points)) do       if points[i, j, 1] > 0 then          pointsColored[i, j, 1] := evalhf(points[i, j, 1]-ln(ln(points[i, j, 2]))/ln(2.));          pointsColored[i, j, 2] := evalhf(points[i, j, 1]-ln(ln(points[i, j, 2]))/ln(2.));          pointsColored[i, j, 3] := evalhf(points[i, j, 1]-ln(ln(points[i, j, 2]))/ln(2.));       end if    end do end do;
 > image1 := ImageTools[Create](pointsColored):image2 := ImageTools[FitIntensity](image1, inplace = false):ImageTools[View](image2):

The Maple Interface

The Task Programming Model consists of two functions, Start and Continue.

 The Start function creates a new task and then begins executing tasks. When the task created by Start completes, Start returns the value returned by that task. Start can be called from within an already executing Task. The calling sequence for Start is   Start( fcn, arg1, arg2, ..., argN )   This creates a task that executes   fcn( arg1, arg2, ..., argN )