Task Programming Model - a high-level multithreaded programming model
|
Introduction
|
|
•
|
The Task Programming Model is a high-level multithreaded programming model. It is designed to allow Maple code to be written that takes advantage of multiple processors, while avoiding much of the complexity of traditional multithreaded programming.
|
•
|
Here are a few advantages of using the Task Programming Model:
|
•
|
No explicit threading, users create Tasks, not Threads.
|
•
|
Maple schedules the Tasks to the processors so that the code scales to the number of available processors.
|
•
|
Multiple algorithms written using the Task Programming Model can run at the same time without significant performance impact.
|
•
|
Complex problems can be solved without requiring traditional synchronization tools such as Mutexes and Condition Variables.
|
•
|
If such synchronization tools are not used, the function cannot be deadlocked.
|
•
|
The Task functions are simple and the model mirrors conventional function calling.
|
|
|
Overview
|
|
•
|
Consider the following Maple function:
|
>
|
f := proc( args )
# work
...
return cont( fc1( c1args ), fc2( c2args ) );
end proc;
|
•
|
To compute f, we do some work, execute fc1, then fc2, then finally execute cont by passing the return values of fc1 and fc2 as arguments.
|
•
|
In the Task Programming Model, instead of executing fc1, fc2, and cont in the same thread, 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. Some of the arguments to the procedure may be the result of evaluating other tasks. If all of a task's arguments are available, it can be executed. If some arguments are not available, the task waits for the results to be available. In this example, fc1 and fc2 could be executed immediately, however cont cannot. When fc1 and fc2 are complete, their return values are passed to cont. When cont gets its arguments, it can be executed.
|
As tasks create new tasks, a dependency tree is created where some tasks wait for other tasks to complete before they can execute.
•
|
Here is a simple example of a Task-based implementation of add:
|
>
|
cont := proc( a, b )
return a + b;
end 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;
Threads:-Task:-Start( task, 1, 10^8 );
|
Start creates the initial task and then waits until that task is complete. In this example
>
|
Threads:-Task:-Start( task, 1, 10^8 );
|
creates a task that executes task( 1,10^8 ). task checks the size of the range, and if it is small enough, we simply compute the add directly. If the range is large enough, we split it in half and create two child tasks.
>
|
Threads:-Task:-Continue( cont, Task=[ task, i, k ], Task=[ task, k+1, j ] );
|
These child tasks execute task( i, k ) and task( k+1, j ). The Continue function also creates a third continuation task that executes cont. This continuation task is the task that waits for the return values from the two child tasks. The continuation task takes the place of the current task in the dependency tree. This allows the current task to finish, while leaving the dependency tree intact. The continuation task can combine the results from the child tasks before passing them to its parent. In this example, it adds the two results together.
|
|
Notes
|
|
•
|
The Task Programming Model is inspired by work done at the Supercomputing Technologies Group at MIT, specifically, the Cilk project. Intel's Threaded Building Blocks also provides a similar interface for C++ programming.
|
|
|