ANNOUNCE: Magpie 0.10 Utilities for multi-core execution
Marc A. Criley
in Ada Letters (http://portal.acm.org/citation.cfm?id=1879078,
membership required), comes the initial release of Magpie:
Magpie is a collection of generic procedures that distributes subranges
of iterative application-defined processing across the processors of a
multi-core CPU to achieve true concurrency and therefore increased
application performance.
Magpie supports work sharing and work seeking processing for the GNAT
compiler on Linux platforms. The platform restriction is due to
processor-affinity not being a standard Ada feature until Ada 2012, so
in the interim a GNAT-specific pragma is utilized (more info in the README).
Magpie is available for download at:
http://sourceforge.net/projects/magpie-mc
Break into groups, execute, and rejoin with your consensus.
Marc A. Criley
McKae Technologies
Brad Moore
And thanks to Marc as he was the one who encouraged me to release the
paraffin code.
Brad
Shark8
Brad, Marc,
What is the difference between Magpie and Paraffin?
Marc A. Criley
> Brad, Marc,
> What is the difference between Magpie and Paraffin?
Magpie provides two generic functions and a generic procedure. They're
designed to operate on a container of data that is indexed or keyed by
values of a discrete type. E.g. an integer indexed array, or a vector.
The generic functions retrieve a value from the container, apply an
application-supplied function to it, then combine ("reduce") each result
with a running total, until all values have been processed, and the
final value of the running total is returned as the generic function's
value.
The generic procedure repeatedly invokes an application-supplied
procedure, accompanying each invocation with an index value. There is
no value returned, the supplied procedure is simply repeatedly invoked,
presumably progressing through each element of the container, and it is
responsible for managing its results.
The technique I got from Brad's article had to do with partitioning the
range of index/keys amongst application-designated CPU cores.
One of the functions simply evenly splits the range across the number of
cores and kicks off the execution of each task associated with a core.
The other function, and the procedure, initially split the range evenly,
but if one of the core tasks finishes early, it advertises that it is
available to take on more work. When one of the other tasks notices
this, it stops, splits its remaining work, and both resume execution.
There's more detail about all this in the README, along with a couple
examples, including a Magpie version of Jakob Sparre Andersen's
Mandelbrot set generator.
Marc
Brad Moore
> Brad, Marc,
> What is the difference between Magpie and Paraffin?
Paraffin provides both iterative parallelism (parallel loops)
and recursive parallelism.
For iterative parallelism, three types of parallelism strategies are
supported.
1) Work Sharing - Simple Divide and Conquer strategy
2) Work Stealing - Idle workers can steal more work from busy workers.
3) Work Seeking - Idle workers can request (seek) more work from busy
workers.
For recursive parallelism, currently Work Sharing and Work Seeking are
provided.
For both recursive and iterative, if needed you can generate a final
result (reduction) from the parallelism. This reduction occurs in
parallel and is interleaved with the main parallel processing.
For recursive parallelism, I have also added what I call
stack-safe parallel recursion.
This is an extension to work-seeking that allows recursion to continue
in parallel, but providing some guarantees that the stack wont overflow,
regardless of stack size.
Paraffin has been ported to two different Ada compilers. (GNAT and
another compiler that isn't available commercially at this time).
Paraffin also has been compiled on both Linux and Windows, and
run on both Intel based processors and AMD processors.
The code was written so as not to rely on any OS specific or Compiler
specific features, so hopefully the code is portable to other Ada 2005
compilers and target platforms.
The README that comes with the sources provides more details,
and there are numerous examples as well, including a parallel red-black
binary tree container, appending to an Ada 2005 Doubly_Linked_List
container in parallel, operating on an Ada 2005 Vectors containers in
parallel, manipulating arrays in parallel, etc.
Look also for a paper in the next upcoming Ada Users Journal issue,
which will discuss Paraffin, and compares Work Sharing, Work Seeking,
and Work Stealing strategies in various problems.
The paper corresponds with a presentation I gave at at Ada Europe last
June in Valencia, but also carries on from the paper I presented last
October for SigAda, at Fairfax Va.
Brad Moore