What programming paradigms should I be investing in if I want my code to run on petascale machines in the future?

Question

It's pretty clear from a survey of the top500 that the industry is trending towards an exponential increase in processing cores. The largest supercomputers all use MPI for communication between nodes, though there does not appear to be a clear trend for on-node parallelism, with the simplest (but not necessarily the most efficient) approach to map a single MPI process to each core, automatic parallelization from the compiler, OpenMP, pthreads, CUDA, Cilk, and OpenCL.

I am one of a group of scientists maintaining and developing a code that has potential to be used on some of the largest supercomputers in the world. Assuming finite developer time, how do I future-proof myself so that I can take advantage of the performance of the world's most powerful machine? What assumptions should I make about process interconnect architecture? What paradigms are going to suffer as we enter the manycore era? Will Partitioned Global Address Space languages be available "in production" on petascale machines?

Answer 1

---

Historical Perspective

It is really impossible to say what the new paradigms will be like in the future, for example a good historical perspective I suggest reading Ken Kennedy's Rise and Fall of HPF. Kennedy gives an account of two emerging patterns, MPI versus a smart compiler, and details how MPI had the right amount of early adopters and flexibility to dominate. HPF eventually fixed its problems but it was too late.

In many ways, several paradigms, such as PGAS and OpenMP, are following that same HPF trend. The early codes have not been flexible enough to use well and left a lot of performance on the table. But the promise of not having to write every iota of the parallel algorithm is a attractive goal. So the pursuit of new models are always being pursued.

---

Clear Trends in Hardware

Now the success of MPI has often been cited as to being closely tied to how it models the hardware it runs on. Roughly each node has a few number of processes and passing the messages to local point-to-point or through coordinated collective operations is easily done in the cluster space. Because of this, I don't trust anyone who gives a paradigm that doesn't follow closely to new hardware trends, I actually was convinced of this opinion by the work from Vivak Sarakar.

In keeping with that here are three trends that are clearly making headway in new architectures. And let me be clear, there are now twelve different architectures being marketed in HPC. This up from less than 5 years ago only featuring x86, so the coming days will see lots of opportunities for using hardware in different and interesting ways

• Special Purpose Chips: Think large vector units like accelerators (view espoused by Bill Dally of Nvidia)
• Low Power Chips: ARM based clusters (to accomodate power budgets)
• Tiling of Chips: think tiling of chips with different specifications (work of Avant Argwal)

---

Current Models

The current model is actually 3 levels deep. While there are many codes using two of these levels well, not many have emerged using all three. I believe that to first get to exascale one needs to invest in determining if you code can run at all three levels. This is probably the safest path for iterating well with the current trends.

Let me iterate on the models and how they will need to change based on the predicted new hardware views.

Distributed

The players at the distributed level largely fall into MPI and PGAS languages. MPI is a clear winner right now, but PGAS languages such as UPC and Chapel are making headways into the space. One good indication is the HPC Benchmark Challenge. PGAS languages are giving very elegant implementations of the benchmarks.

The most interesting point here is that while this model currently only works at the node level, it will be an important model inside a node for Tiled architectures. One indication is the Intel SCC chip, which fundamentally acted like a distributed system. The SCC team created their own MPI implementation and many teams were successful at porting community libraries to this architecture.

But to be honest PGAS really has a good story for stepping in to this space. Do you really want to program MPI internode and then have to do the same trick intranode? One big deal with these tiled architectures is that they will have different clock speeds on the chips and major differences in bandwidth to memory so performant codes must take this into account.

On-node shared memory

Here we see MPI often being "good enough", but PThreads (and libraries deriving from PThreads such as Intel Parallel Building Blocks) and OpenMP are still used often. The common view is that there will be a time when there are enough shared memory threads that MPI's socket model will break down for RPC or you need a lighter weight process running on the core. Already you can see the indications of IBM Bluegene systems having problems with shared memory MPI.

As Matt comments, the largest performance boost for compute intensive codes is the vectorization of the serial code. While many people assume this is true in accelerators, it is also critical for on-node machines as well. I believe Westmere has a 4 wide FPU, thus one can only get a quarter of the flops without vectorization.

While I don't see the current OpenMP stepping into this space well, there is a place for low-powered or tiles chips to use more light threads. OpenMP has difficulty describing how the data flow works and as more threads are used I only see this trend becoming more exaggerated, just look at examples of what one has to do to get proper prefetching with OpenMP.

Both OpenMP and PThreads at a course enough level can take advantage of the vectorization necessary to get a good percentage of peak, but doing so requires breaking down your algorithms in a way that vectorization is natural.

Co-processor

Finally the emergence of the co-processor (GPU, MIC, Cell acclerators) has taken hold. It is becoming clear that no path to exascale will be complete without them. At SC11, every Bell prize contestent used them very effectively to get to the low petaflops. While CUDA and OpenCL have dominated the current market, I have hopes for OpenACC and PGAS compilers entering the space.

Now to get to exascale, one proposal is to couple the low powered chips to lots of co-processors. This will pretty well kill off the middle layer of the current stack and use codes that manage decision problems on the main chip and shuffle off work to the co-processors. This means that for code to work quite effectively a person must rethink the algorithms in terms of kernels (or codelets), that is branchless instruction level parallel snippets. As far as I know, a solution to this evolution is pretty wide open.

---

How this affects the app developer

Now to get to your question. If you want to protect yourself from the oncoming complexities of exascale machines, you should do a few things:

• Develop your algorithms to fit at least three levels of parallel hierarchy.
• Design your algorithms in terms of kernels that can be moved between the heirarchy.
• Relax your need for any sequential processes, all of these effects will happen asynchronously because synchronous execution is just not possible.

If you want to be performant today, MPI + CUDA/OpenCL is good enough but UPC is getting there so its not a bad idea to take a few days and learn it. OpenMP gets you started but leads to problems once the code needs to be refactored. PThreads requires completely rewriting your code to its style. Which makes MPI + CUDA/OpenCL the current best model.

---

What is not discussed here

While all this talk of exascale is nice, something not really discussed here is getting data onto and off of the machines. While there have been many advances in memory systems, we don't see them in commodity cluster (just too darned expensive). Now that data intensive computing is becoming a large focus of all the super computing conferences, there is bound to be a bigger movement into the high memory bandwidth space.

This brings to the other trend that might happen (if the right funding agencies get involved). Machines are going to become more and more specialized for the type of computing required. We already see "data-intensive" machines being funded by the NSF, but these machines are on a different track than the 2019 Exascale Grand Challenge.

This became longer than expected ask for references where you need them in the comments

Answer 2

I'll try a shorter answer than some of my esteemed colleagues on this thread ;-)

My message to all my students is always that developer time is more valuable than CPU time. That means that if you have time to convert 100% of the code at 80% efficiency to run on big machines -- using a high level approach --, then you're better off than when you use a time-consuming low-level approach that gives you 100% efficiency on 20% of your code. As a consequence, I'm a big fan of high-level libraries. My favorite in this area are the threading building blocks (TBB) since it allows me to look at algorithms at the outermost loops and at a high level. It can also do all the things you may want to do with pthreads without the cruddiness of having to deal with OS functions, etc. I am not a fan of approaches that look at innermost loops because that's the wrong level to exploit intranode parallel resources -- so no OpenMP, for example.

I can't speak with authority about OpenCL, CUDA, etc.

Answer 3

Let's start by discussing a strategy for intranode code (computing which does not touch the interconnect), since I think MPI is a good choice for internode code. I think its senseless to talk about nodes with fewer than 100 cores, so at least a current GPU or MIC.

Its a fact that pthreads alone cannot get you maximum performance on any modern chip, because you must take advantage of the vector unit (true since the first Cray). On Intel and AMD you can use intrinsics, but these are not portable, and in my opinion clunky. CUDA and OpenCL have vectorization built into the library and make it easy to get maximum performance. All the new hardware of which I am aware has this vector requirement, so any solution should take this into account. For me, CUDA/OpenCL is the current way to go.

Next, all these machines will be NUMA, which is harder to program, but I think the kernel strategy works. You divide up work and data into small units. These will probably be automatically scheduled, as happens currently in CUDA and OpenCL, but you can specify dependencies. For problems which fit the streaming paradigm, this chunking can also be done automatically. Intel TBB does this, but I prefer the higher-level library approach exemplified by Thrust and Cusp, which can target CUDA or (soon) TBB.

Answer 4

The answers previously posted are excellent but have focused mostly on the node architecture, which I think reflects the fact that MPI is generally regarded as sufficient as the internode programming models in most cases and that it is intranode parallelism where we struggle.

Here are my attempts to answer two questions that are not yet answered or answered in a relatively limited way:

What assumptions should I make about process interconnect architecture?

I will consider three properties of networks:

1. latency,
2. bandwidth, and
3. concurrency.

Latency is inversely proportional to frequency. We know that frequency scaling has stagnated. Hence, one can conclude that latency is unlikely to decrease significantly in the future. The MPI send-recv latency on Blue Gene/Q is around 2 us, which corresponds to 3200 cycles. More than half of that latency is software, but a good portion of it is required by the MPI standard; extensive tuning might reduce the latency to close to 1 us, particularly if one can assert that MPI wildcards are not going to be used.

In any case, the hardware latency for packet injection on Blue Gene and Cray systems is around 1 us. If anything, increasing node-level concurrency makes it difficult to keep this number so low, but I am optimistic that hardware designers will find ways to keep the latency under 5 us for the foreseeable future.

Network bandwidth is trivially increased by increasing the number of network links. This is only part of the story, however. One put 1000 outbound links on a node and not be able to use them if the processor(s) cannot drive the network at full bandwidth. For example, some supercomputers bottleneck in the bus (e.g. HyperTransport) rather than the network, in terms of injection bandwidth.

There are no fundamental limits to network bandwidth, only practical ones. Bandwidth costs money and power. System designers will have to factor in the trade-offs between network bandwidth and other parts of the machine when developing future systems. Many codes are not network-bandwidth limited, so it seems unlikely that we will see machines with dramatically more per-connection bandwidth in the future. However, the bandwidth per node should increase proportional to the compute power so there need to be multiple connections per node to scale up.

The third property of networks that is often overlooked in formal models is how many messages can be sent a single time. Having a network with 1 ns latency and/or 1 TB/s bandwidth that can only send 1 message at a time would be entirely useless for most usages. It is important to be able to send lots of messages from lots of threads at the same time and for the network to not collapse under contention. Both Cray and Blue Gene systems now achieve in excess of 1 MMPS (million messages per second). I can't remember the exact numbers, but both are able to achieve a significant fraction of peak bandwidth with small messages. An ideal network might be able to hit peak bandwidth with any size message, but this is impossible in practice due to packet header and related bookkeeping overheads. However, being able to send millions of 1KB messages at a time and saturate the injection bandwidth with this usage might be more useful than being able to do the same for thousands 1MB messages or a handful of 1GB messages.

This is an incomplete and imperfect answer. Others are welcome to try to improve it or suggest things I should improve.

Will Partitioned Global Address Space languages be available "in production" on petascale machines?

Cray XE, XK and XC systems have a production-quality UPC and CAF compiler. Blue Gene systems can be delivered with XLUPC and XLCAF but no one asks for this so it is not delivered. PERCS has production-grade XLUPC and XLCAF compilers but no large-scale installations that are accessible to the scientific community.

Coarrays are part of Fortran 2008, although the implementations in Intel and GNU Fortran are not high-quality yet. The Intel implementation is reputed to work but also be quite slow (there's a paper at PGAS12 about it).

As for the PGAS programming model (since programming models - not programming languages - are the subject of the original question), the Global Arrays library is a reasonable approximation to production-quality in many cases. As a runtime, it's not as robust as MPI, but MPI is pretty unique in terms of how quality the implementations are. The ARMCI-MPI implementation of ARMCI makes Global Arrays much more stable, albeit slower in some cases.

It's relatively easy to implement PGAS-style constructs in a production quality way using MPI-3 RMA. If someone posts a new question about this, I would be happy to answer it.

Answer 5

Really massive amounts of cores also open trivial yet surprisingly useful perspective -- just to use it to run many iterations of the whole simulation.

Significant part of computational research nowadays boils down to scanning some parameter space, screening large pool of initial conditions or calculating a distribution of some result in a resampling manner; all those tasks are embarrassingly parallel, thus Amdahl-proof.

Answer 6

I suspect that even the most well-thought out answers to this question will be obsolete in five to ten years. Given the uncertainty of future programming paradigms it may not be worthwhile to spend a great deal of time pre-optimizing your codebase.

Answer 7

I was just about to post this answer to this question, but it was closed as a duplicate of this one, so here goes:

This may sound a bit Solomonic, but in my experience, the future belongs to hybrid approaches in which several shared-memory multi-core nodes running multi-threaded kernels are connected via a distributed-memory paradigm such as MPI.

There are, however, a few problems, and they do not involve the hardware at all. First of all, most parallel programmers are heavily invested in MPI-type codes and are very reluctant to be the first to re-implement parts, or all, of their code-base using a new paradigm. The lack of people using shared-memory approaches leads to slower progress in algorithms for that area, which make any investment seem even more pointless.

A second problem is that everybody associates shared-memory parallelism with OpenMP. While OpenMP is a nice quick-and-dirty way to solve small, simple problems on a small number of processors, it's an absolutely terrible programming model for real shared-memory parallelism. Although we've all, at some point or another, learned a number of simple and efficient parallel programming paradigms, e.g. Thread pools or Schedulers, these are not easy to implement using OpenMP and, quite frankly, this is not the type of parallelism that OpenMP entices programmers to use.

In summary, the barrier for moving from a purely distributed-memory to a purely/partially shared-memory paradigm is quite high. If you want to use threads efficiently, you have to forget OpenMP and manage threads and concurrency yourself (hello pthreads, goodbye Fortran).

But why move to a hybrid approach at all? Well, although MPI scales to thousands of cores, the underlying model is one of lock-step synchronicity and static communication patterns. This is good for some problems, e.g. billion-particle simulations, but sub-optimal for more difficult or finer-grained problems. Shared-memory paradigms make dynamic load balancing and/or asynchronous communication much easier, but doing involves a major programming effort.