ANNOUNCE: Magpie 0.10 Utilities for multi-core execution

ANNOUNCE: Magpie 0.10 Utilities for multi-core execution

[Marc A. Criley]

Hot on the heels of Brad Moore's Paraffin, and inspired by his article 
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

Re: ANNOUNCE: Magpie 0.10 Utilities for multi-core execution

[Brad Moore]

On 26/01/2011 6:12 PM, Marc A. Criley wrote:
> Hot on the heels of Brad Moore's Paraffin, and inspired by his article
> 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
>

And thanks to Marc as he was the one who encouraged me to release the 
paraffin code.

Brad

Re: ANNOUNCE: Magpie 0.10 Utilities for multi-core execution

[Shark8]

On Jan 28, 5:49 pm, Brad Moore <brad.mo...@shaw.ca> wrote:
> On 26/01/2011 6:12 PM, Marc A. Criley wrote:
>
>
>
> > Hot on the heels of Brad Moore's Paraffin, and inspired by his article
> > 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
>
> And thanks to Marc as he was the one who encouraged me to release the
> paraffin code.
>
> Brad

Brad, Marc,
  What is the difference between Magpie and Paraffin?

Re: ANNOUNCE: Magpie 0.10 Utilities for multi-core execution

[Marc A. Criley]

On 01/28/2011 08:25 PM, Shark8 wrote:

> 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

Re: ANNOUNCE: Magpie 0.10 Utilities for multi-core execution

[Brad Moore]

On 28/01/2011 7:25 PM, Shark8 wrote:
> 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