10 ms·

Parallel programming is not hard per se, it's just that there's so much more to learn (compared to "sequential programming"): threads, processes, IPC, messaging

Parallel programming is not hard per se, it's just that there's so much more to learn (compared to "sequential programming"): threads, processes, IPC, messaging, actors, queues, synchronization primitives (mutexes, semaphores, monitors, condition variables, critical sections, atomics... you name it) along with their gotchas, concurrent containers with their limitations, transactions, distributed computing with its performance implications, new design patterns (e.g. async/await, promises and futures). But hey, programming has never been thought of as easy, right? Yet, speaking of having it hard, it may be enlightening to compare software development with having to design a piece of (digital) hardware, where not only much has always been happening "in parallel" but one also must keep taking into account physical characteristics of various parts of the circuit.

gopalv 7y ago
> Parallel programming is not hard per se, it's just that there's so much more to learn Parallel programming isn't the hardest part (it is hard, but good teachers help with good abstractions over problems), it is the parallel debugging that is - or at least the second pass over the same codebase. Often being able to write decent parallel code is easier than debugging a system which is behaving inconsistently without any ability to set up the timing bugs the right way around. The difference between "I fixed a bug" and "I massively lowered the probability of it" is hard to tell. I spent 7 months chasing an issue that happened once on average of a billion requests (or rather once every 2-3 days across a web farm). The fix was easy, but debugging it drove me insane slowly over a whole summer. And after that, there's the loss of efficiency from parallelization which needs enough parallel tracks to actually be faster - more threads is often slower at low thread counts. As an anecdote, there were enough servers at Yahoo which had SMT turned off because the extra locking introduced by 2 threads on a core ate up the extra CPU those threads freed up.
- agumonkey 7y ago
  This gives me two questions: - did you have a method/tool to debug (from book, or chatting with others) - are there still cpu designs dedicated to parallel workloads (I assume the usual desktop intel/amd, no matter how brilliant, may not be without hiccups in high parallelism) oh one last thing, do you use dedicated compilers for parallelization ? or is it something "mainstream" like openmp
  - namibj 7y ago
    I can greatly recommended mozilla's rr for hunting concurrency bugs, as it allows efficient replay and provides a scheduler that is designed to increase the probability of triggering concurrency bugs. The issue with x86 is simple: the memory model pretty much requires loads of broadcasts on the SMP interconnect. IIRC Power9 is nice due to (1) a memory model that doesn't require this (much) broadcasting on the interconnect, and (2) remote atomics like "fetch current 64bit value pointed to by register1 and atomically add register2 after", which prevent the cacheline from bouncing between cores or even sockets (Power9 scales to about 5~10kW TDP @8~20W TDP/core and 4 threads/core (there are versions that combine core pairs to have 8 threads using the resources of (almost) 2 cores (overhead / diminishing returns))). I can't really recommend OpenMP. If the architectural restrictions aren't a problem, you might want to check out Intel's TBB, which uses C++ templates instead of compiler pragmas. Unfortunately you'd ideally need multithreading-aware polyhedral optimization, and _that_ mostly stalled AFAIK. You'd likely write C++ or now maybe Rust with low-level primitives / intrinsics to build libraries. I don't know of any actually good "automatic" frameworks for general shared-memory parallel programming (There's Chapel, but it seems fairly niche. Still going strong though, by the looks of it.). If you can efficiently express the problem with loop-dataflow, you might want to try timely-dataflow (Rust, does thread/process/node parallelism), as it nicely integrates with normal Rust code.
    - gpderetta 7y ago
      1) why would the x86 memory model require more broadcasts? and 2) I can't find any hit about power9 remote atomics outisde of GPU memory. Any pointers?
      - namibj 7y ago
        There are ancient design decisions regarding exclusive locks. Early on, while it was a bus, it just used a signal for "locked" (~a mutex), and later this physical broadcast had to go because the interconnect switched to a fabric of point-to-point SerDes links. The remote atomics are a GPU-independent feature on the SMP interconnect. The GPU thing is mostly icing on the cake, by exposing this feature to NVLink GPUs (iirc. Volta+, maybe Pascal+).
- DaiPlusPlus 7y ago
  > Parallel programming isn't the hardest part [...] it is the parallel debugging that is - or at least the second pass over the same codebase. We need better IDE parallel thread debugging tools. I don’t like how VS won’t let you open a separate Autos/Locals window for each thread, or easily step each thread - setting a breakpoint in a function currently executing in multiple threads is a usability nightmare.
kerkeslager 7y ago
You really don't need to know all that to do parallel programming, and if you ever are using any significant number of those in one program, you're going to be in a world of pain. You're much better off just picking a paradigm and sticking with it. I'd say it doesn't matter which one, but there are a few paradigms that are clear winners in my experience: immutability always wins, and Erlang-style messaging seems to work very easily. If you have the opportunity to determine the architecture of a parallel project, most languages can imitate Erlang-style parallelism with builtin libraries. But what I will say is that which paradigm you pick doesn't matter so much that you should switch paradigms mid-project. A word of caution: concurrency and parallelism are not the same thing. Cooperative multithreading is a way of gaining some of the benefits of parallelism in a single process. If you come from an environment where this is the norm (read: JavaScript) it's quite possible that you've never written a line of parallel code. If you try to apply the same paradigms from this sort of environment to parallel programming, they will not work.
- cerebellum42 7y ago
  >You really don't need to know all that to do parallel programming, and if you ever are using any significant number of those in one program, you're going to be in a world of pain. I don't entirely disagree, but most environments (or "paradigms") simply hide all that away from the user. Which is generally a good thing. Chances are you _are_ using a lot of those primitives in any given parallel or concurrent program, but you're only aware of one or two of them. For example, a channel for message passing between threads (or tasks in a cooperative multitasking context) might contain a Semaphore and an atomic reference counted pointer which in turn contains atomic integers. See [0] for an example. And while concurrency and parallelism are not the same thing, you often end up having to consider the same synchronization problems in your code whether it's concurrent or parallel. Cooperative multitasking does involve true parallelism when the scheduler uses multiple threads on a processor with multiple cores. Code is not just being executed concurrently there, it is (possibly, not guaranteed to be fair) executed in parallel. [0] https://docs.rs/crate/tokio/0.2.9/source/src/sync/mpsc/chan.rs https://docs.rs/crate/tokio/0.2.9/source/src/sync/mpsc/chan....
  - 7y ago
shaklee3 7y ago
Parallel programming is not hard if you follow the "just use a mutex and you avoid race conditions" mantra. However, this book dives deep into what mutexes actually do, what the hardware below is doing, and alternatives to a mutex for a speed increase. This can be anything from lockless algorithms to RCU, which the author of this book wrote it in Linux kernel. There's a comment above about Haskell and how you don't have to really put any thought into making things parallel. That's great for 99% of cases, but other times you need higher performance where it matters how the concurrency is implemented.
- clarry 7y ago
  > Parallel programming is not hard if you follow the "just use a mutex and you avoid race conditions" mantra. At one extreme of the spectrum, you can do everything under a big lock and be effectively single-threaded. At the other extreme, you can use lots of mutexes and fine grained locking and end up with a mess of potential deadlocks and races and "here be dragons" because the original programmer did not anticipate that you sometimes need data not to change for a bit longer than a short and obvious critical section. What I'm working on at work right now, oh goodness how many races and problems I've found around locking and multi-threading in general. It's a nightmare.
  - cerebellum42 7y ago
    Sometimes it can be a nice way out to quickly lock the data, copy it and then unlock, if it's acceptable to have a task using outdated data occasionally. If that is not acceptable, there are Read-Write-Locks, which do guarantee that the data being used is current and allow for concurrent read access, but come with the drawback that write accesses might have to wait fairly long until the pointer can be fully locked. What I'm saying is, don't limit yourself to Mutexes, there's a whole zoo of synchronization primitives and each of them has a specific use case that it's ideal for. Recently I've dealt with a lot of synchronization in Rust, and I would say it's been as pleasant as it could be, considering the subject matter. Deadlocks are still possible, but at least the compiler stops you from accidentally unlocking a Mutex too early.
  - caspper69 7y ago
joe_the_user 7y ago
> Parallel programming is not hard per se I'm not sure how you can say that. Programming a fairly hard activity but the general consensus is adding parallelism to any given programming task, you make that task much, much harder. I don't think you find any version of parallel programming that isn't hard. The situation of parallelism, your commands happening in an unpredictable order, not synchronously, inherently, by itself, per se, makes thinking about a parallel program harder than a non-parallel program. Edit: Parallel programming is hard enough that the advised method for most such programs is one or another standard patterns - which are infinitely easier than rolling your own plan but still contain serious gotchas when your program complexity increases.
- jonathanstrange 7y ago
  I have to second that. Parallel programming is extremely hard to get right and people persistently underestimate it. For example, I've seen many times code that erroneously assumed that values can be read from global memory concurrently if only write access is guarded. Of course, it depends a lot on what your programming language has to offer. For example,in my experience Ada makes it easier to get parallelism correct than many other languages, primarily because Ada tasks have a precisely defined and specified semantics and because Ada's "Rendesvouz" makes certain kinds of errors impossible. The same is sometimes claimed about Rust. In more permissive languages like Go, however, almost every parallel program is wrong in one way or another. For example, it is extremely common for parallel Go libraries to stop in a deadlock. The situation is so bad that I have stopped using concurrent Go libraries, except for the well-implemented standard libraries. Even then, many package authors don't tell you what they do internally and their libraries lock up in unexpected places. For example, I've recently been looking for a parallel tree walker library in Go, and every package I tried stopped with an infinite deadlock on my file system, presumably due to the interplay between error handling and spawning goroutines. Ironically, even many goroutine scheduling libraries I've tried have locked themselves up.
  - ColanR 7y ago
    > For example, I've seen many times code that erroneously assumed that values can be read from global memory concurrently if only write access is guarded. As someone who has made that assumption, what's wrong with it?
arkh 7y ago
> Parallel programming is not hard per se Last time I checked there was no "best parallel sorting algorithm". All depend on your architecture (core, memory, network).
agumonkey 7y ago
relativistic factor: being taught that programming == sequential imperative turns your brain myopic, makes even harder to unlearn and think about concurrent/distributed systems bonus point: to an extent sequential imperative is an abstraction layer over the concurrent IC implementing your computer

gopalv 7y ago

> Parallel programming is not hard per se, it's just that there's so much more to learn Parallel programming isn't the hardest part (it is hard, but good teachers help with good abstractions over problems), it is the parallel debugging that is - or at least the second pass over the same codebase. Often being able to write decent parallel code is easier than debugging a system which is behaving inconsistently without any ability to set up the timing bugs the right way around. The difference between "I fixed a bug" and "I massively lowered the probability of it" is hard to tell. I spent 7 months chasing an issue that happened once on average of a billion requests (or rather once every 2-3 days across a web farm). The fix was easy, but debugging it drove me insane slowly over a whole summer. And after that, there's the loss of efficiency from parallelization which needs enough parallel tracks to actually be faster - more threads is often slower at low thread counts. As an anecdote, there were enough servers at Yahoo which had SMT turned off because the extra locking introduced by 2 threads on a core ate up the extra CPU those threads freed up.

agumonkey 7y ago
This gives me two questions: - did you have a method/tool to debug (from book, or chatting with others) - are there still cpu designs dedicated to parallel workloads (I assume the usual desktop intel/amd, no matter how brilliant, may not be without hiccups in high parallelism) oh one last thing, do you use dedicated compilers for parallelization ? or is it something "mainstream" like openmp
- namibj 7y ago
  I can greatly recommended mozilla's rr for hunting concurrency bugs, as it allows efficient replay and provides a scheduler that is designed to increase the probability of triggering concurrency bugs. The issue with x86 is simple: the memory model pretty much requires loads of broadcasts on the SMP interconnect. IIRC Power9 is nice due to (1) a memory model that doesn't require this (much) broadcasting on the interconnect, and (2) remote atomics like "fetch current 64bit value pointed to by register1 and atomically add register2 after", which prevent the cacheline from bouncing between cores or even sockets (Power9 scales to about 5~10kW TDP @8~20W TDP/core and 4 threads/core (there are versions that combine core pairs to have 8 threads using the resources of (almost) 2 cores (overhead / diminishing returns))). I can't really recommend OpenMP. If the architectural restrictions aren't a problem, you might want to check out Intel's TBB, which uses C++ templates instead of compiler pragmas. Unfortunately you'd ideally need multithreading-aware polyhedral optimization, and _that_ mostly stalled AFAIK. You'd likely write C++ or now maybe Rust with low-level primitives / intrinsics to build libraries. I don't know of any actually good "automatic" frameworks for general shared-memory parallel programming (There's Chapel, but it seems fairly niche. Still going strong though, by the looks of it.). If you can efficiently express the problem with loop-dataflow, you might want to try timely-dataflow (Rust, does thread/process/node parallelism), as it nicely integrates with normal Rust code.
  - gpderetta 7y ago
    1) why would the x86 memory model require more broadcasts? and 2) I can't find any hit about power9 remote atomics outisde of GPU memory. Any pointers?
    - namibj 7y ago
      There are ancient design decisions regarding exclusive locks. Early on, while it was a bus, it just used a signal for "locked" (~a mutex), and later this physical broadcast had to go because the interconnect switched to a fabric of point-to-point SerDes links. The remote atomics are a GPU-independent feature on the SMP interconnect. The GPU thing is mostly icing on the cake, by exposing this feature to NVLink GPUs (iirc. Volta+, maybe Pascal+).
DaiPlusPlus 7y ago
> Parallel programming isn't the hardest part [...] it is the parallel debugging that is - or at least the second pass over the same codebase. We need better IDE parallel thread debugging tools. I don’t like how VS won’t let you open a separate Autos/Locals window for each thread, or easily step each thread - setting a breakpoint in a function currently executing in multiple threads is a usability nightmare.

kerkeslager 7y ago

You really don't need to know all that to do parallel programming, and if you ever are using any significant number of those in one program, you're going to be in a world of pain. You're much better off just picking a paradigm and sticking with it. I'd say it doesn't matter which one, but there are a few paradigms that are clear winners in my experience: immutability always wins, and Erlang-style messaging seems to work very easily. If you have the opportunity to determine the architecture of a parallel project, most languages can imitate Erlang-style parallelism with builtin libraries. But what I will say is that which paradigm you pick doesn't matter so much that you should switch paradigms mid-project. A word of caution: concurrency and parallelism are not the same thing. Cooperative multithreading is a way of gaining some of the benefits of parallelism in a single process. If you come from an environment where this is the norm (read: JavaScript) it's quite possible that you've never written a line of parallel code. If you try to apply the same paradigms from this sort of environment to parallel programming, they will not work.

cerebellum42 7y ago
>You really don't need to know all that to do parallel programming, and if you ever are using any significant number of those in one program, you're going to be in a world of pain. I don't entirely disagree, but most environments (or "paradigms") simply hide all that away from the user. Which is generally a good thing. Chances are you _are_ using a lot of those primitives in any given parallel or concurrent program, but you're only aware of one or two of them. For example, a channel for message passing between threads (or tasks in a cooperative multitasking context) might contain a Semaphore and an atomic reference counted pointer which in turn contains atomic integers. See [0] for an example. And while concurrency and parallelism are not the same thing, you often end up having to consider the same synchronization problems in your code whether it's concurrent or parallel. Cooperative multitasking does involve true parallelism when the scheduler uses multiple threads on a processor with multiple cores. Code is not just being executed concurrently there, it is (possibly, not guaranteed to be fair) executed in parallel. [0] https://docs.rs/crate/tokio/0.2.9/source/src/sync/mpsc/chan.rs https://docs.rs/crate/tokio/0.2.9/source/src/sync/mpsc/chan....
- 7y ago

shaklee3 7y ago

Parallel programming is not hard if you follow the "just use a mutex and you avoid race conditions" mantra. However, this book dives deep into what mutexes actually do, what the hardware below is doing, and alternatives to a mutex for a speed increase. This can be anything from lockless algorithms to RCU, which the author of this book wrote it in Linux kernel. There's a comment above about Haskell and how you don't have to really put any thought into making things parallel. That's great for 99% of cases, but other times you need higher performance where it matters how the concurrency is implemented.

clarry 7y ago
> Parallel programming is not hard if you follow the "just use a mutex and you avoid race conditions" mantra. At one extreme of the spectrum, you can do everything under a big lock and be effectively single-threaded. At the other extreme, you can use lots of mutexes and fine grained locking and end up with a mess of potential deadlocks and races and "here be dragons" because the original programmer did not anticipate that you sometimes need data not to change for a bit longer than a short and obvious critical section. What I'm working on at work right now, oh goodness how many races and problems I've found around locking and multi-threading in general. It's a nightmare.
- cerebellum42 7y ago
  Sometimes it can be a nice way out to quickly lock the data, copy it and then unlock, if it's acceptable to have a task using outdated data occasionally. If that is not acceptable, there are Read-Write-Locks, which do guarantee that the data being used is current and allow for concurrent read access, but come with the drawback that write accesses might have to wait fairly long until the pointer can be fully locked. What I'm saying is, don't limit yourself to Mutexes, there's a whole zoo of synchronization primitives and each of them has a specific use case that it's ideal for. Recently I've dealt with a lot of synchronization in Rust, and I would say it's been as pleasant as it could be, considering the subject matter. Deadlocks are still possible, but at least the compiler stops you from accidentally unlocking a Mutex too early.
- caspper69 7y ago

joe_the_user 7y ago

> Parallel programming is not hard per se I'm not sure how you can say that. Programming a fairly hard activity but the general consensus is adding parallelism to any given programming task, you make that task much, much harder. I don't think you find any version of parallel programming that isn't hard. The situation of parallelism, your commands happening in an unpredictable order, not synchronously, inherently, by itself, per se, makes thinking about a parallel program harder than a non-parallel program. Edit: Parallel programming is hard enough that the advised method for most such programs is one or another standard patterns - which are infinitely easier than rolling your own plan but still contain serious gotchas when your program complexity increases.

jonathanstrange 7y ago
I have to second that. Parallel programming is extremely hard to get right and people persistently underestimate it. For example, I've seen many times code that erroneously assumed that values can be read from global memory concurrently if only write access is guarded. Of course, it depends a lot on what your programming language has to offer. For example,in my experience Ada makes it easier to get parallelism correct than many other languages, primarily because Ada tasks have a precisely defined and specified semantics and because Ada's "Rendesvouz" makes certain kinds of errors impossible. The same is sometimes claimed about Rust. In more permissive languages like Go, however, almost every parallel program is wrong in one way or another. For example, it is extremely common for parallel Go libraries to stop in a deadlock. The situation is so bad that I have stopped using concurrent Go libraries, except for the well-implemented standard libraries. Even then, many package authors don't tell you what they do internally and their libraries lock up in unexpected places. For example, I've recently been looking for a parallel tree walker library in Go, and every package I tried stopped with an infinite deadlock on my file system, presumably due to the interplay between error handling and spawning goroutines. Ironically, even many goroutine scheduling libraries I've tried have locked themselves up.
- ColanR 7y ago
  > For example, I've seen many times code that erroneously assumed that values can be read from global memory concurrently if only write access is guarded. As someone who has made that assumption, what's wrong with it?

arkh 7y ago

> Parallel programming is not hard per se Last time I checked there was no "best parallel sorting algorithm". All depend on your architecture (core, memory, network).

agumonkey 7y ago

relativistic factor: being taught that programming == sequential imperative turns your brain myopic, makes even harder to unlearn and think about concurrent/distributed systems bonus point: to an extent sequential imperative is an abstraction layer over the concurrent IC implementing your computer