Thinking Parallel

This post serves a triple-role: First of all, it is a vision document for the project I am doing at work right now. It describes the high-level goals for me and the people that will be working on the project with me – saving me from having to explain them multiple times and also providing some focus during the lifetime of the project. Second, it is an exercise on how to write a good vision document. I don’t get to employ my project management skills too often while at the university and I am eager to practice some of the things I have learned from the literature (in this case: from Scott Berkuns excellent book The Art of Project Management). Since I don’t do this often, this is also a great chance for me to gather some feedback from more experienced people, be that project managers or developers or whoever feels like commenting (so if you have anything to criticize in this document, I encourage you to do so!). The third role of this post is to let you participate in some of the ideas I am working on at the moment.

So much for the meta-introduction. I hope the rest of this post is self-evident (as every good vision should be), and therefore I will just add one more thing beforehand: the working title of this project is AthenaMP (it used to be Ompat, which stood for OpenMP Pattern Library, but as one of my students remarked this sounded like a small, furry animal that was run over on a highway 😉 – not exactly an impression we want to make).

Vision Statement

Every good vision starts with a short and precise vision statement. Here is mine:

AthenaMP will be a library to show some easy and powerful programming techniques in OpenMP and C++. It is intended as a resource that can be employed as is with the provided interfaces, but the user is also encouraged to look under the hood and change our easy to comprehend code coupled with to-the-point documentation.

Primary Goals from a Users Perspective

AthenaMP has three primary goals for our potential users. First of all, it will show how a set of patterns can be implemented in OpenMP / C++. The patterns to be implemented include data-parallel, task-parallel, synchronization and some sequential patterns, which have to be implemented in a thread-safe manner. We will also include common workarounds for functionality missing in the language and even some building blocks for common algorithms inside the library – for the sake of clarity we will refer to these functions as patterns as well for the rest of this document. The user will be able to learn about parallel programming in OpenMP / C++ by looking at our implementations and their extensive documentation, enabling him to adapt our code to his own parallel programming problems.

Second, at least some of the library functionality will be useful without adaption. Every class / function will have a documented API (via Doxygen). The license of AthenaMP will allow every interested party to include it in their own code and use it as a normal library, without understanding every implementation detail of the provided functionality.

The third goal of AthenaMP is to serve as a testing ground for compilers. Many of them still do have problems working with OpenMP / C++ code and by providing these compilers with easy to use test-cases we hope to help improve them.

Primary Goals from a Researchers Perspective

AthenaMP will be a research project. Its intention is to implement functionality with OpenMP and C++ that has not been implemented before using this combination (or at least not been implemented and documented in a publicly available form). This will enable us to evaluate strengths and weaknesses of OpenMP and to deploy workarounds for functionality that is missing or difficult to implement. It may also enable us to propose further enhancements of the OpenMP-specification to the OpenMP Language Committee.

We are also interested in how advanced object-oriented techniques, template metaprogramming techniques and OpenMP are able to coexist.

Features

We plan on delivering the following functionality:

Data-Parallel Patterns:

• Map – done
• Reduce – done
• Googles MapReduce
• Filter
• Scan (also called Parallel Prefix)
• Wavefront
• NUMA-versions of these, working on local data

Task-Parallel Patterns:

• Taskpool
• Pipeline
• Message-Queue

Synchronization Patterns:

• Scoped Locking – done
• Once – done

Thread-safe, Sequential Patterns:

• Singleton – done
• Observer

This list is just an initial version and will be updated over time. Some of the patterns described here may not be practical to implement and more will definitely follow.

AthenaMP will be well-documented. Each class / member variable or function / function will be documented using Doxygen. High-Level documentation for each implemented pattern is also provided, along with high-level documentation of the whole library. There will be test-cases for each part of the provided functionality that can also be used to understand possible ways to employ our code.

The library will be well-tested. Each part of our library will be covered by tests using CPPUnit.

It will be portable. The only requirements for running our code will be a compiler that supports C++ and OpenMP 2.5. We plan on testing on at least the compilers from Intel, Sun, IBM, Portland Group, Microsoft and gcc (as soon as it is officially released with OpenMP-support).

All code will adhere to a common set of Coding Guidelines.

Feature-Restrictions

The library will be restricted to functionality that is implemented using OpenMP and C++. Although the code will be educational to look at for programmers who are interested in different parallel programming systems, no ports of any of our code will be included in AthenaMP.

Our library will not feature a complete test suite for C++ and OpenMP. Our focus is more on the user and on the research value of our code. Most of the code required to provide an extensive test suite for C++ / OpenMP does not belong into that category. Nevertheless, our code could be included into such a test suite without restrictions.

Target Audience / Users

AthenaMP is created as an educational tool for programmers. They can benefit from AthenaMP by learning about Sequential and Concurrent Patterns, Parallel Programming, OpenMP and C++. Basic knowledge of OpenMP / C++ is assumed.

Stakeholders

The primary stakeholder in the project is me (Michael Suess), as the project is part of my dissertation and I am the primary developer. The second stakeholder is my advisor, Prof. Claudia Leopold, who has power over the project because she will evaluate my dissertation. As soon as I settle on a second professor/PhD. to become my secondary advisor, this person will have some power as well. To start with, three of my students are going to work on the project as either course-work / diploma-theses or paid work. More students or external programmers are welcome to join this effort and may become stakeholders in this case as well. If an organization wants to provide funding (e.g. to employ and supervise more students), this is of course possible and would enable the organization to influence the direction of AthenaMP to a certain extent as well.

Competitors

As far as we know, no project with this particular scope and goals has been attempted to date. We know of several projects with a slightly different angle, though, some of which are listed below along with a comment on how they differ from AthenaMP:

• Some attempts have been made at providing a parallel version of the STL (e.g. DatTeL: A data-parallel C++ template library). These include many data-parallel patterns, yet not much else. We are not aware of an attempt to accomplish this with OpenMP.
• The Intel Threading Building Blocks do provide some of the functionality we have described above (e.g. several implementations of data- and task-parallel patterns). They are a pure library, though, no access and learning from the inner workings of their code is possible. The library is also neither free, nor portable, nor built using OpenMP (although it is compatible with OpenMP).
• The OmpSCR – OpenMP Source Code Repository does provide OpenMP-code for developers to look at. Most of the code is in Fortran or C, though and does not appear to be maintained at all at the moment. It also lacks our strong focus on patterns and documentation.
• The OpenMP validation suite is a comprehensive suite of tests for OpenMP 2.5. Its focus is on testing compilers for compliance to the OpenMP specification. It is freely available, but contains no C++-code, nor patterns of any kind.
• Andrei Alexandrescu has implemented some Patterns in C++ using advanced Template-Techniques in his Loki-Library and documented them in his excellent book called Modern C++ Design / Generic Programming and Design Patterns Applied. Basically, what he has done for C++-Templates we hope to achieve for OpenMP (although we will probably never reach his level of C++-expertise while doing it).
• The various books on sequential and concurrent patterns do provide some of the features we have described above. Nevertheless, they are mostly not written using C++ and OpenMP, nor do they provide the variety of different patterns we are aiming at.

External Dependencies

The project does not depend on any external projects that need to be finished beforehand. It does depend on working C++ compilers with OpenMP support – but these are available and accessible for us today. No other projects that I know of depend on AthenaMP.

Risks

A Prototype of some patterns has already been implemented. The project is therefore definitely doable. The major risk is lack of time on my part. My dissertation needs to be finished by November 2007 and before that time I also have to put everything else I have done together into a single document. On the other hand, this risk can be controlled by scaling down the number of patterns to implement (which is no problem, since we have not committed to delivering a certain number). Since this is not a commercial project, all other risks I see are minor.

Team Composition

The only constant in the team will be me (Michael Suess). More students will be working on the library and implementing patterns, either as project-work or as part of their bachelor/master/diploma-thesis (two students to start with). A paid student assistant will join our efforts as well. The more students are working on the project, the more of my time will be spent supervising them (e.g. by doing code reviews).

Schedule

There is no fixed schedule. Since the project can be broken down into very small pieces naturally (one pattern a piece) and since we don’t have any fixed deadlines or deliverables, we can employ agile methods and decide on the fly what to work on next.

Final Words

This closes my short trip into the world of project management. This document will be updated as the project progresses, maybe even on a separate web page – probably on sourceforge or someplace else where we don’t have to setup and maintain our own project infrastructure (e.g. version control, bug tracker, mailing lists).

As I said at the beginning of this article, I don’t do vision documents often (they are not exactly encouraged in academia), and therefore I am looking forward to any comments from you :D. Too verbose? Too badly written? Not enough content? Something critical missing? Plain boring? Utterly useless? Or did you even like some parts of it? Then don’t hesitate to leave a comment or at least tell me your opinion by rating it below (although I would be happier about comments in any case – I cannot learn much from knowing that you did or did not like it, I can only learn from knowing why this is the case)!