Thinking Parallel

A Blog on Parallel Programming and Concurrency by Michael Suess

What Makes Parallel Programming Hard?

A WalnutAnwar Ghuloum has posted his opinion about What Makes Parallel Programming Hard at the Intel Research Blogs (which are buzzing with activity with regards to parallel programming at the moment). The funny thing is, I have asked myself the same question last week, because I have just written a section in my PhD.-thesis about it. And since at least some of my answers are different from his, I have decided to post them here.

But I don’t want to get ahead of myself, as a good host of course I need to let the guest speak first. Here are Anwar’s reasons in a nutshell:

  1. Finding The Parallelism
  2. Avoiding The Bugs
  3. Tuning Performance
  4. Future Proofing
  5. Using Modern Programming Methods

These are all good reasons. Here are the reasons I have found, some of them overlap with Anwar’s, some of them are new. They are in no particular order, some are more important than others, but I am sure not the one to judge which one is the most important one in your particular situation or for most programmers.

Added Complexity

There are a number of steps involved in creating a parallel algorithm (e.g. task decomposition, mapping and taking care of communication / synchronization issues). None of these steps are necessary for a sequential program. For most of them, there is no support from tools available. The only thing that really helps is experience. Naturally, these additional and difficult steps are the number one reason why parallel programming is considered difficult.

Parallel Programming is Error-Prone

Not only are there additional steps involved when creating parallel programs, but these steps are very prone to errors. If the wrong task-decomposition is chosen, you might not see any performance increases from parallel programming (I will have a post about task-decomposition next week). If the wrong mapping is chosen, synchronization overhead may kill performance. And if mistakes are made during the communication / synchronization phase, not only performance may suffer, but the program might not run or produce incorrect results altogether.

Too Little Knowledge of New, Innovative Parallel Programming Systems

There are some parallel programming systems out there that promise to be easier to use. OpenMP is the primary example, but also e.g. functional ones like Erlang or Haskell. The problem here is that most programmers don’t even know about these systems or their strengths and weaknesses.

Parallel Programming is not yet Mainstream

A lot of information can be found about mainstream languages in books or on the Internet, where a lot of tutorials or solutions to common problems can be found. Programming is easier, when there is a lot of help available. The situation is different for most parallel programming systems. There are some books available, but most of them concentrate on numerical algorithms and problems found in High Performance Computing. The number of resources on the Internet talking about parallel programming is also quite thin, when compared to the more general topic of programming and software development.

Compilers Are Not as Well-Tested as their Sequential Counterparts

Working with a compiler that is not well-tested can be a huge problem. A programmer can spend large amounts of time searching for mistakes in his code, when really the compiler is to blame. In my experience, many compilers for parallel code are less well-tested than their sequential counterparts.

No Good Platform for Parallel Programming Available

There are a lot of tools available today to help programmers of sequential programs. IDEs, Debuggers, Profilers, Correctness Tools are all important to make programming easier and together with the abstractions provided by the language and the libraries available they form a so-called platform. For the parallel case, there are tools available for some systems, but they are usually not as good as their sequential counterparts.

Not Enough Powerful Abstractions Available

Programming in assembler is more difficult than programming in a higher-level language. The languages used for parallel programming are often on a very low level, as each communication or synchronization operation needs to be managed in every detail by the programmer. OpenMP is a good step in raising the level of abstraction, as it hides many details from the programmer.

A second aspect here is the lack of good libraries. Programming becomes way easier, when the programmer can rely on powerful libraries to encapsulate complex behavior. There are some numerical libraries available for many parallel programming systems, yet others are largely missing.

Lack of Standards / Portability

I have described earlier that parallel programming systems are not yet mainstream. Related to this point, there are very little standards available, that programmers could rely on, especially when changing platforms. OpenMP and Java Threads are a big win in this regard, since they enable portable parallel programming, even including the Microsoft Windows platform.

It Is difficult, to Move from a Sequential Program to a Parallel One

In most cases, parallelizing a sequential program is not an incremental process. For many systems, the programmer has to start refactoring his code for parallelism and until that is completely done, there is no way to check any intermediate steps. This is of course difficult. OpenMP has a good approach to this problem, as it is quite easy to add pragmas one at a time without having to refactor the whole program at once.

It is Hard to Test Parallel Programs

Related to the last paragraph, testing parallel programs is a problem. Most errors can be classified into one of the two categories: there are problems related to parallelism and there are problems with the actual algorithm. Unfortunately, finding a mistake is difficult when the culprit could be in any of the two sources. OpenMP once again gets it right, because it enables programmers to turn of parallelism for many programs and still get a correct, sequential one, that can be debugged for errors using the advance sequential debugging tools available.

Disclaimer

Some of them you may already know from my post on the Top 5 Reasons why I Hate Parallel Programming (Sometimes). You can see from a lot of these points, that I am using them to justify basing my research on OpenMP. This shows that of course not all points are valid for each and every system, there is e.g. a lot of learning material available on Java Threads now, both on the net and in good books. And there has never been a lack of good IDEs for that particular language. But they are all I could think of and I am convinced most of them are true, at least for a large subset of the available parallel programming systems.

6 Responses to What Makes Parallel Programming Hard? »»


Comments

  1. Comment by anon | 2007/08/06 at 16:33:49

    Add another: It’s practically impossible to know when you can compose parallel software libraries. You are stuck with either reimplementing / reengineering large chunks of code or limiting yourself to partial parallelism by separating the code into disjoint services. Often those services wait on each other, so you’re just adding overhead and losing a portion of you machine or allocation.

  2. Comment by Minesh B. Amin | 2007/08/06 at 20:07:22

    Hi Michael,

    Your list is right on the mark. The thing that I find the most fascinating
    is the lack of a methodology or a library that bridges the gap between
    the goal (scalable solutions) and the reality (existing serial software
    processes/developers). Well not quite …

    If interested, please come-by and try out the open source version
    of my company’s solution (OpenSPM). Very soon, I will be going
    live with a collection of parallel dynamic languages (starting with
    parallel TCL). Let me know if you would like to try out parallel TCL
    before general availability.

    Best regards.

  3. Comment by Seun Osewa | 2007/08/06 at 21:46:23

    My guess is that most applications that require parallel programming to run well on current hardware are extremely complex problems. Complex enough that the overhead of learning parallelism is just an extra hurdle to scale. In that case, current languages already offer sufficient support for any style of concurrency you happen to prefer (CSP with processes and pipes, SMT with threads, and event-based programming with libraries like libevent). It’s not a big deal.

  4. Comment by Fernando | 2007/08/08 at 00:13:20

    I saw great benefits in converting a parser algorithm from sequential to parallel.
    Basically i figure that for parallel to work correctly the tasks that you want to execute in parallel must not be dependant on each other.
    In Java I heavily relied on the Concurrent framework.
    The algorithm i tested scales very well compare to its sequential counterpart.

  5. Comment by Nick Vaidyanathan | 2007/08/08 at 23:28:13

    Nice article. I’m curious if you’ve studied the differences/similarities between concurrent programming and hardware design. I did some VHDL in undergrad and had to deal with the paradigm shift of dealing with processes running in parallel, variables versus signals, etc…it really helped when I was learning about threads in OS (which I’ve admittedly never had to use in an enterprise app), and I’m wondering if there are methodologies/techniques in that world could bridge the gap and help in software.


Trackbacks & Pingbacks »»

  1. [...] This blog post from Intel clearly lays out the challenges of parallel-programming, and this response to the post from Thinking Parallel points out even more complications of parallel models of programming. The [...]

Leave a Reply

HTML allowed: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>