Parallel Programming - Maple Help

Home : Support : Online Help : System : Information : Updates : Maple 16 : Parallel Programming

Parallel Programming in Maple 16: The Task Programming Model

Maple includes the Task Programming Model, a high level parallel programming library.  The Task Programming Model allows users to implement parallel algorithms, algorithms capable of taking advantage of the multiple core computers that are now common.  Writing parallel algorithms using the Task Programming Model reduces and removes many of the difficulties associated with standard threaded programming.

Example: Computing a Convex Hull

Given X, a set of points in 2D, the Convex Hull is the minimum set of points that define a polygon containing all the points of X.  If you imagine the points as pegs on a board, you can find the Convex Hull by surrounding the pegs by a loop of string and then tightening the string until there is no more slack, the Convex Hull is the pegs in contact with the string.

The following is an example of a Convex Hull of 20 points.

One way to compute a Convex Hull is to use the QuickHull algorithm.  Starting with two points on the convex hull (the points with lowest and highest position on the x axis, for example), you create a line which divides the remaining points into two groups.  If you find the Convex Hull of these two groups, they can be combined to form the Convex Hull of the entire set.  Given the line and the set of points on one side of the line, we find the point in the set furthest from the line.  This point will also be on the Convex Hull.  Using this point and the two end points of the line, we can define two new lines on which we can recurse.  If we find a line with one or no points on the outside of the hull we have constructed so far, then we stop knowing that both end points of the line and the one exterior point (if it exists) are in the Convex Hull.

The algorithm can be parallelized by running the recursive steps in parallel.  The following code implements the QuickHull algorithm and a parallel QuickHull using the Task Programming Model.

One might be surprised to see how little extra code is necessary to turn a sequential algorithm into a parallel one.  This is because the Task Programming Model takes care of many of the confusing, messy, and bug prone aspects of threaded programming.

We now create some points to try the QuickHull algorithm on:

Now try the parallel algorithm on the same set of points:

As you can see, the relatively simple modification to add parallelism to the QuickHull algorithm leads to a good speed enhancement.

 Maple's New Memory Manager and Parallel Performance Maple 16 has a revamped memory management system that allows for better handling of memory when multiple threads are executing.  By running the above example with larger numbers of points, the difference between Maple 15 and Maple 16 becomes clear.   As the problem size grows, the Maple 15 memory manager is unable to keep up with the demands of the problem.  Maple 16 does a much better job, leading to significantly better performance.  The following graph shows memory used when generating the graph above.