Parallel and Multi-Core Computing with C/C++

Draft Specification of Transactional Language Constructs for C++

Michael_Wong — Wed, 11 Nov 2009 15:58:43 GMT

Hello all, over the last year, a group of Transactional Memory experts from Sun, Intel, and IBM have been getting together every Friday to discuss how to create a uniform syntax for Transactional Memory.

We are happy to release the first version of the Draft Specification of Transactional Language Constructs for C++. This specification is the result of a joint work by a group of people from Intel, IBM and Sun, and is based on our experience working with transactional language constructs. We would like to encourage people to implement this specification and we welcome feedback on the document. Please direct any such feedback to this discussion group TM & Languages.

You can find the specification in the Resource Library/Articles, Presentation, Ebooks under the Parallel Section

If you have any comments, I invite you to post them here or in the Discussion forum.

TM Specification Drafting Group

IBM's Alphaworks Software Transactional Memory Compiler

Michael_Wong — Tue, 11 Aug 2009 17:02:44 GMT

Transactional Memory (TM) is a high level abstraction for supporting a safe mutable shared state, such that the user does not have to worry about the low-level details of locking and sharing of global resources. It is basically a class of optimistic speculation techniques such that groups of memory operations are bundled as an atomic operation such that it can resolves the problems with locks, possibly support composability.

The basic idea is to move your group of atomic operations through, assuming that it will be successful, and only rollback when a conflict actually occurs.

At the moment, much of the ideas of TM are there as a way to test out the idea, and possibly be integrated into some future hybrid system. Even practitioners of TM knows there is a certain amount of hype that we have to deal with in any new technology before it drops to a trough and rebounds back to a realistic plateau.

A number of vendors have planned both hardware and software implementations of Transactional Memory.

The software transactional memory compilers from different vendors all use different syntax, and this creates a basic problem with interoperability, and common porting of code. I will deal with this in the next post.

IBM is also working in this area, and has released an Alphaworks compiler supporting Software Transaction, actually last year.

The IBM XL C/C++ for Transactional Memory for AIX is also accessible from the Resource Library of the C/C++ Cafe.

The public domain STM runtime is compatible with the AlphaWorks XLC STM release.
It was released through the Amino Concurrency Building Blocks project
The source code is here

I will have more to say about the Amino Building Blocks in a future post.

The View (trip report) from BoostCon09

Michael_Wong — Thu, 28 May 2009 00:47:16 GMT

I apologize for lack of updates recently as an addition to the family has kept me hopping.

I have still been keeping up my parallel programming work by a recent talk on C++0x Multithreading at BoostCon 09:

http://www.boostcon.com/program#schedule

My two talks (the other one was an overview of C++0x and compiler support which can be seen here:
http://www-949.ibm.com/software/rational/cafe/blogs/cpp-standard/2009/05/26/the-view-or-trip-report-from-the-mar-2009-c-standard-meeting) seem packed with about 60 people in an auditorium for about 90 minutes. Here is a trip report from a fellow speaker Justin Gottschlich who attended my talks:

http://par-con.blogspot.com/

The slides and video should be online soon.
A second trip report review is by Emil Dotchevski:

http://revergestudios.com/reblog/index.php?n=ReCode.BoostCon09

Justin gave an excellent talk on a proposed Boost Transactional Memory Library which he is collaborating with the Father of TM: Maurice Herlihy.

I have been involved in Transactional Memory for a few years now and knows its hype, promise and pitfalls. Still I felt I was stirred by Justin's excellent oratory skills, pitching this technology. The idea of doing TM as a pure library is not easy, although it does get the technology into the hands of everyone as fast as possible. Language changes take time to get right. I should know and will discuss in a future post.

Please read their excellent trip reports for the details. I will turn my discussion on something else that is also interesting to me personally, but may not have much to do with Parallel programming.

BoostCon 09, as with previous BoostCon was an exciting experience. Without intentionally touting my own horn, BoostCon09 is rich with speakers of experience in the field. They choose their speaker carefully from the pantheon of C++. Last year was Bjarne Stroustrup. This year was Andrei Alexandrescu, whose topic is Iterators Must Go.

Andrei gave many reasons why iterators, once a good idea, are unsuitable as we move forward. For me, the most interesting argument is that iterators are not well suited to multithreaded programming, because many of the idea of stack pop and push can only work in single thread unless we change the interface.

BoostCon, in my opinion is rapidly becoming the leading C++ conference, in direct competition with SD West, and ACCU. All are packed with workshops, and knowledgeable speakers.

This year, there was a distinct track of parallel programming theme, which included:

Joel Falcou: High-Level Parallel Programming EDSL - A BOOST libraries use case
Stephan T. Lavavej: Parallel Patterns Library in Visual Studio 2010
Justin Gottschlich, Jeremy Siek: Boost + Software Transactional Memory
Troy Straszheim: Kamasu: Parallel computing on the GPU with boost::proto

and of course, yours truly's:

Michael Wong: Multithreaded C++0x: The Dawn of a New Standard

All this makes me want to suggest a special track for parallel programming for Boost in future years.

I attended some of the 0x tutorials and found that I still had things that I didn't know. This is not surprising given the depth of C++0x.

The other interesting part was the Cmake tutorial. Boost build has used bjam since the beginning. This build tool, while interesting in its own right has many peculiarities which makes its adoption not a trivial task for building Boost on IBM systems. From the stories we heard around Boostcon, the same seems to apply to other environments.

Recently, there has been a move towards using cmake as a truly better build tool. From what I can see from the workshop, they are right and I am eager to move our Boost build to a cmake system, especially if Boost is moving in that direction, to rid us of the problems that bjam has caused.

http://www.cmake.org/

How does cmake differ form the traditional unix make?
Unlike make, it does not actually do the software build, but instead generates standard build scripts (makefiles on Unix, project file for Windows, workspaces for Eclipse/CDT), that makes it easier to adopt to various systems.

Cmake was started as part of the Insight visual ToolKit build from Kitware, and has since migrated into many products. The real explosion occurred with adoption of cmake by KDE. Since then, even more software is converting to cmake.

Cmake is so far able to build Boost, but is not able yet to run its builtin tests. This is a problem that I am sure will be rectified.

The beauty is that cmake is available already as a binary on AIX systems.

I worked with Troy Straszheim and Brad King to try getting cmake working on our Boost build. I got half way but found a problem which I hope to resolve.

We support Boost because IBM AIX and Linux xlC++ compilers have been tested with Boost with support in V8 with 1.32, then V9 with 1.34, and V10.1 with 1.34.1.

You can see our Boost test results here:
http://www.ibm.com/support/docview.wss?rs=2239&context=SSJT9L&uid=swg27006911

Where is OpenCL and OpenMP headed?

Michael_Wong — Mon, 26 Jan 2009 01:55:49 GMT

The following is a a private communication from an IBM engineer Matthew Markland who asked a great question. I do not claim great expertise but I feel that there is enough of an opinion piece that some folks may like to see this discussion or continue it. I have edited the response somewhat but it is largely in tact and reprinted with Matthew's permission. Note I have no insight into PGI or any other product other then what I read in public articles, and as such makes no product claim. Any opinion regarding other company remain necessarily my own and is not IBM's position.

Michael:

I hope that the new year finds everything well for you and yours.
I'm enjoying the C/C++ Cafe posts you guys put out immensely.

Please join in the discussion, or even bring this up as other experts will chime in.

I just wanted to get your opinion on some things that have been
going through my mind with respect to the multicore/hybrid
programming models that are being put out by various entities. It
seems that many people believe that the best model is an extension
to the language model, be it a pure language extension like what
CUDA and OpenCL have, or with a new model of pragmas like PGI is

OpenCL/CUDA is mostly a library based model and a language extension(modulo the 4 memory annotations). But yes I see where you are going with this ...

adding. I'm wondering, especially in the case of the PGI extensions,

I am assuming this is the pragma directives available in their technology preview:

#pragma acc directive-name [clause [,clause] ...]

whether they make sense given the existing OpenMP spec
Where do you

So there has been parallel languages that are directive based, language extensions, and library based. Usually they start off with library based because they are easy to port, and works on many vendors' compiler. Language-based solutions are harder to implement, and can not be easily corrected if wrong. Directive-based like OpenMP makes it easily adapted in an incremental manner, and keeps the base program running even on platforms that don't accept the directive. Today, we have examples of all three. MPI is a pure library based solution. Cilk is a pure language based solution and OpenMP is a directive-based solution (although it too has a library part).

A mostly library based language like OpenCL is in a sense a step backwards. So PGI is trying a directive based approach to send the computational kernel to the accelerator/GPGPU. This is a bet from their part. I am familiar with their chief compiler engineer on the OpenMP Committee Michael Wolfe, and respects his opinion.

see this headed from a personal perspective.

Having some involvement in OpenCL, I can see where it falls somewhat short, but is nevertheless a tremendous accomplishment. It is designed for today's GPGPU architecture, assumes a weak memory model, implicitly have a dual layer of scheduling policy between the host (outer asynchronous layer) and the thread processors (inner synchronous processors with local memory). This is in addition to it being still relatively hard to program,( though easier then DirectX or OpenGL) and for people who have to port a 100,000 line of code is a large commitment on a technology that may not be around. OpenCL, is still a stream processing language and as such is limited in the scope of the parallel programs it can speed-up. What PGI is probably looking for is a more generalized programming model which works in broader situation. That is why they introduced the scheduling clause, and tied it to OpenMP. I would not be surprised if some kind of heterogenous programming support would be in OpenMP in future.

I don't have any significant personal insight but also is involved in adapting the OpenMP paradigm to fit in the next programming model without knowing where to go.

In the end (and this is based on Michael Wolfe's excellent analogy in an HPC paper), OpenCL is basically designed for a hardware that is a large wide body air carrier that can handle massive number of passengers in one run, but requires special airport transportation to get the passengers to the plane because the plane doesn't fit in the terminal. So the speed it has (in terms of # of passenger-miles) is mitigated by the wait time (DMA access)of loading the plane. It works when everything fits.

If you don't have that many passengers, or have a variable number of passengers, it doesn't buy you any extra benefit and may penalize you with a super wide-body jet. And there are lots of other kinds of air carriers out there, including the super-fast kind for the payload just has to get there by 9 am the next day and the medium sized ones that can carry your particular amount of load.
As such, there will still be a place for OpenMP, MPI, TBB, futures, UPC, TM. We are suffering under an alarming number of these so-called parallel languages/extension/libraries lately and I can only see more as we all search for the right model. At one point, we had the same in terms of sequential languages, and over time we have dwindled down into a few General Purpose languages with many domain-specific languages. The same will likely happen in the parallel language world.

OpenCL 1.0 released

Michael_Wong — Mon, 05 Jan 2009 14:22:06 GMT

One of the most important thing that happened in the last month of 2008, was the release of the OpenCL specification by Khronos:

http://www.khronos.org/registry/cl/

An in-depth overview which breaksdown by Clause of the specification shows some of the capabilities of this specification. A shorter summary will provide an overview.

IBM is part of the group that wrote this specification.

What is OpenCL?

The original intent of OpenCL was to raise the abstraction of graphics programming. Game programmers will recall the battle for graphic programming using DirectX and OpenGL, which are specialized graphics languages. Now they can speak OpenCL and never have to learn these specialized graphics languages.
NVIDIA's vendor-specialized language CUDA was meant to do this using C, and to some extent, AMD's Close-To-Metal, and of course Microsoft's DIRECTX 11 Compute.. But an open, royal-free specification makes it far easier for everyone to invest their programming time to this. Apple, AMD, NVIDIA, and Intel are also members who participated in this specification. I wonder if Intel's Larrabee will support this.

For parallel programming, this specification enables both data-based and task-based parallelism. It enables programmers to exploit the powers of Graphics Processing Units as General Computing Devices (GPGPU), which has recently been known to give significant speedup in specific applications.

Unlike other parallel languages, OpenCL is aimed towards supporting heterogenous computing.

How does OpenMP 3.0 work better with C++ (Part 3)?

Michael_Wong — Fri, 12 Dec 2008 05:33:06 GMT

Let's get to the good stuff. OpenMP 2.5 did not really specify what constructors should be called with various private/first/lastprivate/threadprivate:

In some cases, it did not even specify that they should apply to non-PODs (Plain'ol Data, i.e. C structs).

OpenMP 3.0 changed that. Beside specifying non-PODs, it also specified precise rules for the constructor sequence that is in line with what the semantics would require.

Firstprivate:
For instance, it would specify that a firstprivate for a class type variable should expect an accessible copy constructor, since it is required to initialize each of the one or more list items private to a thread with the value that the corresponding original item has when the construct is encountered.

Lastprivate:
For a class type variable, it requires an accessible, unambiguous copy assignment operator for the class type. And it requires an accessible, unambiguous default constructor for the class type unless the variable is also specified in a firstprivate clause.

Threadprivate:
This is the most interesting as it differentiates three kinds of initializaton in C++.
1. Without initialization: Object1 o;

Default constructor is called

2. Direct initialization: Object1 o( (int)23 );

Constructor accepting the argument is called

3. Copy initialization: Object1 o = other_instance;

Copy constructor is called

The semantics of this is that for the master thread, global static objects and static class members are constructed before main() is entered in an undefined order.

For the slave threads, the exact point in time of object construction is unspecified, but is has to happen before the thread references it the first time

These changes were a long time coming. It causes what used to be vaguely implied by the 2.5 specification, now to be clearly specified so all compilers can conform. It also allows the users of C++ with OpenMP to have more consistent behavior.

OpenMP at SuperComputing 08

Michael_Wong — Mon, 08 Dec 2008 15:16:30 GMT

The OpenMP Birds-of-a-Feather session at SC08 was very well attended. The room was full to overflowing, with approximately 60-80 people. while OpenMP had BOFs at SC in prior years, this is actually the first year that OpenMP has had a Booth on the Exhibitor floor as well.

The BOF had many elements, including what is new in OpenMP 3.0. They were:
1. Welcome and summary of ARB news
- 5 mins
- Larry Meadows

2. The three greatest things about OpenMP 3.0 and the three most
important things left out of OpenMP 3.0
- 15 mins
- Tim Mattson

3. Tasking
- 10 to 15 mins
- Alex Duran

4. Extending the OpenMP profiling API for OpenMP 3.0
- 10 to 15 mins
- Oleg Mazurov

5. Announcements:
- 5 mins total
- IWOMP'09 announcement - Matthias Mueller
- OpenMP book examples - Ruud van der Pas

6. Panel "How to kill OpenMP by 2011"
- 35 mins
- Moderator:
Larry Meadows
- Panelists:
Tim Mattson
Bronis de Supinski
Christian Terboven
Jesus Labarta

7. Wrap up
- 5 mins
- Larry Meadows

For a description, you can find lots of detail here, including a downloadable summary card of the 3.0 Specification.

http://openmp.org/

I met a number of people during my afternoon session manning the booth on Wednesday 2-6 pm, including one of the original founder of OpenMP, an instructor on using OpenMP in graduate courses as well as a consultant, among many others. I invite them all to drop me a note here so we can continue our discussion.

One thing that was surprising to many folks was the many compilers that already have 3.0 implementation, despite the specification ratifying only in May 2008. The companies with 3.0 implementation includes IBM, Sun, PGI, and soon Intel. Note I am just reading this from the net and have no insight into other company's or even my own company's release schedule. GNU should have something by 4.4. Same disclaimer.

One thing that happened at the OpenMP BOF was a panel discussion on How to Kill OpenMP by 2012. This is kind of a fun session, especially at the end of a long day to not take yourself too seriously. The point is to showcase all the wrong ways in spreading a de-facto standard.

I have had some experience working with language designs through my various roles as standard rep, and compiler writer. So I thought I would give my $0.02 here on How to Kill OpenMP by 2012:
10. Don't implement the specification as stated.
9. Make it impossible to nail down ambiguities by having no way of addressing defects.
8. Ignore the user forum or suggestions
7. Add everyone's favorite feature, no matter how marginally useful.
6. Make the process as non-transparent as possible, so no one knows when you are ratifying, or even what you are doing.
5. Debate endlessly, on anything, not necessarily having anything to do with the language.
4. Design a feature as completely as possible before releasing it
3. Make no concession when taking a stance on objecting to someone's feature.
2. Form close-nit elitist groups and follow the NIH syndrome.
1. Don't organize any meetings, and when there are meetings, don't follow any rules.

Seriously, I have not found this to be a problem in any of the committees that I am a part of. Otherwise, we would not have made any progress. But we can always do better.

How does OpenMP 3.0 work better with C++?

Michael_Wong — Thu, 04 Dec 2008 02:51:20 GMT

This was one of the question asked at SC 08. I will try to answer that here. I will start and add more as I move through the various topics.

OpenMP 3.0 had better support for C++ in the following areas:

Parallelization of RandomAccess Iterator loops with strict canonical operators
Threadprivatization of static class members
Unsigned loop control variable support
Fully specify constructor call requirement in private/first/lastprivate/threadprivate
better match with the C++0x memory model

For-Worksharing with Iterator loops:

We specifically enabled C++ RandomAccess iterators and C pointeres to be parallelized with explicit directives.

#include <vector>
void iterator_example()
{
   std::vector<int> vec(23);
   std::vector<int>::iterator it;
   #pragma omp parallel for default(none) shared(vec)
   for (it = vec.begin(); it < vec.end(); it++)
   {
   // do work with *it //
   }
}

I will follow up with more examples.

How does OpenMP 3.0 work better with C++ (Part 2)?

Michael_Wong — Fri, 28 Nov 2008 17:04:13 GMT

This part will talk about enabling threadprivatization of static class member variables.

In 2.5, as a result of ambiguous language, the support for this was inconsistent. In general, it would claim that a threadprivate variable must be namespace, file or block scope.

In 3.0, this code is now allowed:

class T {
   public:
      static int i;
      #pragma omp threadprivate(i)
};

This may seem a trivial change, but for C++, it enables a powerful idiom of singletons and allocators, which all rely on static class member variable.

Next posting will continue with the semantics of private, first/lastprivate, threadprivate+copyin/copyprivate for C++.

OpenMP Booth at SuperComputing 08

Michael_Wong — Wed, 26 Nov 2008 22:21:44 GMT

I should include an obligatory photo of the OpenMP Booth with our CEO Larry Meadows. Many members worked tirelessly, especially Larry at making sure the Booth was put up, taken down and staffed properly.

We also met many people who specifically dropped by to see what was going on, in this first year where we had a booth.

Many Thanks.

TOP500 SuperComputer for November 2008 released at SC08

Michael_Wong — Thu, 20 Nov 2008 17:08:08 GMT

Of course, we are very proud that the new list for TOP500 computers has been released here at SC08 on Tuesday at an evening BOF.

http://www.top500.org/blog/2008/11/20/top500_bof_session_slides_now_available

This is the list of the fastest supercomputers in the world. IBM's Roadrunner has been on this list for some time.

The rumor before the conference was whether Oakridge's Cray Jaguar would catch a RoadRunner. Now we know that a Jaguar is not faster then a RoadRunner.

http://www.top500.org/lists/2008/11/press-release

Also of importance in today's energy conscious world, is that IBM's RoadRunner is also #3 on the TOP500 GREEN list of supercomputers:

http://www.green500.org/lists/2008/06/list.php

Questions on C/C++ volatile from SC08 Tutorial S08: A Hands-on Introduction to OpenMP

Michael_Wong — Thu, 20 Nov 2008 16:53:19 GMT

On Sunday, I attended the OpenMP Tutorial hosted by some of my colleagues from the OpenMP committee, Tim Mattson and Larry Meadows. It was an excellent tutorial, full of features and pointing out the behavioral differences between OpenMP 2.5 and 3.0. Tim has been doing this tutorial for almost 20 years and Larry, as the OpenMP CEO has been involved in this for the same amount of time.

I must point out that IBM xl C/C++ 10.1 compiler for AIX and Linux both have support for OpenMP 3.0, in addiiton to the compilers mentioned during the tutorial. In fact, this compiler was one of the first to have support for OpenMP 3.0 in the industry since the ratification of the specification in May, 2008.

http://www-01.ibm.com/software/awdtools/xlcpp/aix/
http://www-01.ibm.com/software/awdtools/xlcpp/linux/

You can get a trial version from the link above.

There were a few C++ specific questions. During the discussion on OpenMP memory model, one questions involves how volatile in C/C++ is used in multithreaded program.

The C++ 0x Standard will clarify that the volatile keyword continues to have nothing to do with multithreading. It merely indicates that something from the environment may change the value. The role of an atomic variable will be used to indicate that another thread may change the value of this variable. It is possible to say that a variable is an atomic volatile to indicate that something from the environment AND another thread may change the value. The C standard, when it supports concurrency in C1x will likely adapt the same meaning.

So in short, C++ Volatile !=Jave volatile and C++ Volatile!= C++ atomic. During C++0x concurrency deliberations, we discussed at length and felt that there is too much history and presumed meanings involved with volatile. In fact, it may even have different meanings varying from compilers to platforms. So it was felt wiser to leave it alone, allowing implementers to retain whatever meaning they are used to, and adapt a new way of naming truly atomic types.

I hope this helps to answer one of the question regarding the role of volatile.

There was another question about how OpenMP 3.0 changed the role of what constructor (default, copy, assignment) is called by each of the private/threadprivate/first/lastprivate variable. Tim was right that we worked very hard to clarify this aspect, but the rules while somewhat intuitive is still fairly tedious to enumerate, given the many ways that C++ does initialization. I will clarify that in a subsequent post.

Supercomputing 08

Michael_Wong — Sat, 15 Nov 2008 14:57:53 GMT

Hi, all. This is Michael Wong. I am at the International Conference for High Performance Computing, Networking, Storage and Analysis, commonly called SC 08, courtesy of IBM

http://sc08.supercomputing.org/

I am specifically here to participate in the OpenMP sessions, where we have a booth, a BOF, and other discussion panels.

Over the next few posts, I hope to bring you some of the exciting events that are going on at this conference.

Looking at the program, there are a number of sessions aimed at Parallel Computing. If there are sessions you would like me to report from, drop me a note through this post and I can see what I can do.

On the flight down, let me just say that the last direct flight from Toronto (where I come from) to Austin was like a reunion of technologists as nearly everyone on the plane was attending SC 08. I recognized people from almost every software/hardware company that is active in this area. It was an interesting high-tech flight.

Normally, there is no direct flight from Toronto to Austin, and it takes multiple stops to get here. I am sure they didn't put together a direct flight just for us for SC 08.

(Actually, I learned on the plane that the direct flight started a year ago by Air Canada!)

Next Generation Systems

Michael_Wong — Wed, 12 Nov 2008 14:15:12 GMT

TANSTAAFL="There ain't no such thing as a free lunch" with apologies to Robert Heinlein in "The Moon is a Harsh Mistress"

One noted author quotes this in reference to the end of the free
performance improvement that Moore's Law offers on single chip clock
speed every 18 months.

This heralds performance improvement in future will need to do more
then just sit on your hands waiting for the next clock speedup, but
that you have to program in latent parallelism into your code to take
advantage of more cores as they come out.

This requires a new mind set, in everything.

Hi, my name is Michael Wong and I am IBM's OpenMP and C++ Standard
representative. I and my colleagues will bring through this blog some
of the key industry trends related to Parallel and Multi-Core
Computing. We have been involved through our roles as implementers,
academic liasions, representatives on various standard committees and
consortiums.

The fact of it is that times have never been better for Parallel &
Multi-Core Computing, with almost every standard, specification,
manufacturer coming out with support for multicores in programming
models, applications, and hardware. Some recent examples are Cell,
OpenMP 3.0, new Java Memory model, UPC and co-array Fortran, C++0x
concurrency, Cilk, transactional memory, auto-parallelization, Altivec and various proprietary or research projects

There is no question that multi-core is a renaissance in systems and
processor design. But it is also a software issue with implications
throughout the entire software development stack.

So come back often and see how this story evolves.