Threads:-Task Example Worksheet
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:=procfargsreturncontfc1c1args,fc2c2argsend proc
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.
In the Task Programming Model instead of executing fc1, fc2 and cont serially, we create a task for each function. A task is a small unit of work, represented in Maple by a function call, that is, a procedure and the arguments to that procedure. These tasks are automatically scheduled to execute on available threads. In the example above cont depends on the return values of fc1 and fc2, thus cont cannot start until fc1 and fc2 are complete. Similarly some tasks may need to wait for other tasks to complete before they can execute. The values returned by the running tasks are passed as arguments to the waiting task. Once all of a task's arguments are available, it can be executed.
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;
cont:=procid,ret1,ret2printfcont id: %s\n,id;returnret1,ret2end proc
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;
task:=procid,levelprintftask id: %s\n,id;if0<levelthenThreads:-Task:-Continuecont,id,Task=task,sprintf%s->1,id,level − 1,Task=task,sprintf%s->2,id,level − 1;returndummyelsereturnidend ifend proc
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.
Threads:-Task:-Start( task, "root", 1 );
task id: root
task id: root->1 task id: root->2 cont id: root
root->1,root->2
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.
Threads:-Task:-Start( task, "root", 3 );
task id: root task id: root->2 task id: root->2->2 task id: root->2->2->2 task id: root->2->2->1 cont id: root->2->2
task id: root->2->1 task id: root->2->1->2 task id: root->2->1->1 cont id: root->2->1 cont id: root->2 task id: root->1 task id: root->1->2 task id: root->1->2->2 task id: root->1->2->1 cont id: root->1->2 task id: root->1->1 task id: root->1->1->2 task id: root->1->1->1 cont id: root->1->1 cont id: root->1 cont id: root
root->1->1->1,root->1->1->2,root->1->2->1,root->1->2->2,root->2->1->1,root->2->1->2,root->2->2->1,root->2->2->2
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;
cont:=proca,breturna+bend proc
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;
task:=proci,jlocalk;ifj − i<1000thenreturnaddk,k=i..jelsek:=floor1/2*j − 1/2*i+i;Threads:-Task:-Continuecont,Task=task,i,k,Task=task,k+1,jend ifend proc
Threads:-Task:-Start( task, 1, 10^8 );
5000000050000000
The call to Threads:-Task:-Start creates the initial task from the function, task and the arguments 1 and 10^8. Following the basic divide and conquer approach, task starts by checking the size of the range it was given. If the range is small enough, task computes the sum directly. If the range is large, task splits it in half and a new task is created for each half. Once completed, the resulting sums are passed into the continuation task, cont, where the values are added together and the sum is returned. The Threads:-Task:-Continue function is used to create the child tasks and the continuation task.
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[8]); Y := Vector(ptsY, i->Y1+(Y2-Y1)*(i-1)/(ptsY-1) , datatype = float[8]); imageArray := Array(1 .. ptsY, 1 .. ptsX, 1 .. 2, datatype = float[8]); 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]), 1 .. rhs(ArrayDims(points)[2]), 1 .. 3, datatype = float[8]):
for i to rhs(ArrayDims(points)[1]) do for j to rhs(ArrayDims(points)[2]) 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.
Threads:-Task:-Start
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 )
Threads:-Task:-Continue
The Continue function performs two functions, first it starts a continuation task and second it starts child tasks. The continuation task takes the place of the task calling Continue in the task dependency tree. Thus the return value of the continuation task is passed to the parent of the current task, and the return value of the current task is discarded. The continuation task also becomes the parent of any child tasks that were created in the call to continue.
The calling sequence for Continue is
Continue( fcn, arg1, arg2, ..., argN )
where fcn is the continuation function and argi is either an argument to be passed directly to the continuation function or an equation of the form
Task=[ cfcn, carg1, carg2, ..., cargN ]
When an argument of this form is passed to Continue, it starts a child task of the form
cfcn( carg1, carg2, ..., cargN )
The return value of this task is passed to the continuation task at the same position as the argument that created it.
How it works
The following is a brief description of how the Task Programming Model works.
Tasks versus Threads
Internally, Maple creates a pool of threads, where the number of threads is equal to the value of kernelopts( numcpus ). By default this is the number of processors available on the computer. This pool is created during the first call to Threads:-Task:-Start. Each thread can execute one task at a time. As tasks are created they are stored in a data structure that represents the dependency tree. When a thread completes a task, it takes another task from this data structure.
By writing tasks instead of threads, Maple is able to share those tasks over as many threads as have been created. This allows the same code to scale to a different number of processors.
Task Queue
The data structure used to manage the tasks is called the Task Queue. The Task Queue contains a double ended queue for each thread. These queues store tasks. By default a thread will always execute the task that is at the head of its queue. Further, when a task creates new tasks they are added to the current thread's queue. If a thread finds that its queue is empty, it will try to steal a task from another thread's queue. When stealing a task, the task is removed from the tail of the queue.
Return to Index for Example Worksheets
Download Help Document
