Parallel programming for sequential programmers

Our very own Jacob Sparre Andersen is doing a course on Parallel Ada programming for sequential programmers at Open Source Days 2013:

Assuming you already know sequential programming in a procedural programming language, this course can get you started writing parallel programs using the Ada programming language.

Short and sweet. The course contents are as follows.

  1. A quick introduction to the basics of sequential programming in Ada. — Just enough to allow you to map your existing programming knowledge to Ada. 45 minutes lecture + 45 minutes exercises.
  2. Creating and understanding basic tasks (parallel threads of execution) with Ada. — I.e. parallel programming without interaction. 45 minutes lecture + 45 minutes exercises
  3. Communication between tasks using safe, shared objects. One kind of interaction between tasks. 45 minutes lecture + 45 minutes exercises
  4. Direct communication between tasks using rendezvous. — Another kind of interaction between tasks. 45 minutes lecture + 45 minutes exercises
  5. Patterns for implementing parallel execution. 45 minutes lecture

I’m so going. Next step: Getting an Open Source Days 2013 ticket.

Paraffin 3.2 Released

The 3.2 release of Paraffin comes with a hefty amount of changes since the not so old 3.1 release:

  • The same technique that was applied to iterative work stealing that significanly improved performance, was also applied to the work seeking generics, which also resulted in some performance gains.
  • Another benefit of this change is that the work seeking mechanisms are now more hidden inside the generic, and not exposed to client code. As a result, the modifications needed to parallelize a sequential loop is the same for work-sharing, work-seeking, and work-stealing. It mostly just involves wrapping the loop in a nested procedure, and then passing the start and finish indexes of the loop as parameters to the nested procedure.
  • A Minimum_Seek parameter replaces the Other_Workers parameter. This parameter indicates the minimum number of iterations that can be “seeked” at one time by an idle worker. This parameter can be left unspecified, in which case, a reasonable default will automatically be assigned.
  • As a result of these changes, the Work-seeking iterative tests generally seem to out perform work-stealing, although the differences are usually quite marginal. There are still tests where work-sharing can be best choice, and other tests where work-stealing can come out ahead.

Yup, Brad Moore is a busy man! In case the changelog doesn’t give away what exactly Paraffin is and does, here’s a short quote from projects website:

A suite of Ada 2005 generics to facilitate iterative and recursive parallelism for multicore systems and provide safer recursion for single and multicore systems. Includes useful generics for parallel quicksort, fast fourier transform, function integration, and Red-Black trees.

You can get to the goodies here and you can read the full release announcement here.

Paraffin 2.4 Released

Back in October 2011 we reported on the release of version 2.0 of Brad Moore’s Paraffin library, and now, a mere 3½ months later we’re graced with the latest and greatest: Paraffin version 2.4.

Since the name Paraffin in itself doesn’t give away what it does, here’s a quote from the project website:

A suite of Ada 2005 generics to facilitate iterative and recursive parallelism for multicore systems and provide safer recursion for single and multicore systems. Includes useful generics for parallel quicksort, fast fourier transform, function integration, and Red-Black trees.

New in this release is:

  • Added a reusable utility to solve a matrix of linear equations using Gauss-Jordan Elimination.
  • Added test_matrix test driver for parallel/sequential matrix solvers.
  • Red-Black Tree containers fully implemented now. (Delete, and Contains calls work)
  • Split Red-Black Tree container into separate generics
    • Sequential
    • Work sharing
    • Work Seeking
    • Stack Safe Work Seeking
  • The Red Black Tree generic was previously intended mostly as a test driver for Paraffin Recursive generics. Now the generic has been completed to a state where it can be reused on its own as a generic container.
  • Changed use of Unchecked_Conversion for Recurse supprogram access to use ‘Unrestricted_Access instead. This cleaned the code up considerably in this area. One issue to look into, is that ‘Unrestricted_Access is a non-standard attribute. It is supported by both GNAT and the ICC compiler however. It may not be supported by other Ada 2005 compilers. Unfortunately, Unchecked_Conversion in this case is not portable either, and may not even continue to work with the existing compilers, so it was thought that using ‘Unrestricted_Access was the best option for now. Will investigate to see if there is a possibility for a better solution, or providing a portable mechanism in a future version of Ada.

Yea, Brad’s been busy!

You can read the full release announcement here.

Paraffin 2.0 for GNAT and ICC Ada compilers

Fresh from the hands of Brad Moore comes version 2.0 of his Paraffin library.

A suite of Ada 2005 generics to facilitate iterative and recursive parallelism for multicore systems and provide safer recursion for single and multicore systems.

New stuff in version 2.0 includes:

  • Paraffin has been compiled and tested using the Irvine ICC Ada compiler, running on both Windows and Linux.
  • Paraffin has been compiled and tested using GNAT AUX on an Android Samsung Galaxy S II Smart phone.
  • Paraffin has been compiled and tested using GNAT 2010 and 2011 GPL versions of the compiler on both Windows and Linux.
  • Paraffin now includes generics that allow deep recursion using a small stack. The generics feature parallel work seeking that monitors the usage of each workers stack, and defers work if the stack resource is approaching depletion. This allows idle worker tasks to resume the deferred work with a fresh stack, in a safe manner until all the work has been completed. Testing has shown that the overhead associated with the stack monitoring is minimal, and that the performance is such that it can also be attractive to consider using on systems that only have a single core.
  • Generics have been added that filter out poor work offers based on the depth of the recursion.
  • The optimal worker count is calculated by default for iterative looping, based on the number of available cores, and the number of iterations.
  • Increased portability, by providing the “Any” target, which does not use any OS services or vendor specific libraries.
  • Numerous performance improvements, particularly for the recursive generics, which were significantly improved.
  • Various bug fixes.

I’ll gladly admit that a lot of those items are far above my paygrade – I wouldn’t even know what to do with “deep recursion using a small stack”, but I do understand the significance of such a complicated piece of software running on Android, and combined with Stephen Leake’s Ada “Hello World” on Android success this seems like another great step towards being able to use Ada to build Android applications.

You can download Paraffin here and you can read Brad’s full announcement here.