Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Is parallel programming hard, and, if so, what can you do about it?

paulmck.livejournal.com

Post reply on HN
Print view View original

71–80 of 88 posts

Re: Is parallel programming hard, and, if so, what can you do about it?

#71

Post by tomp »

jcranmer wrote: post #62
ColanR wrote: post #58

Earlier quoted context omitted.

> 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?

If you have two accesses on different threads, at least one of which is a write, then you need a synchronization chain between them. Note that this is true even if the read occurs before the write. The most common synchronization chain is the first thread doing some kind of "release" action (releasing a mutex, or storing to an atomic variable using a release (or stronger) ordering type), followed by the second thread…

I'm not a low level programmer, but can you elaborate on this a bit?

E.g. why would reading a shared mutable value be wrong, in some specific circumstances? In particular, if the value is a word (and the architecture guarantees atomic writes for word-sized values), and if the reader doesn't care if it reads the previous or the new value (e.g. executes a read of a monotonic counter in a loop, so even if I read the current value this time, I'll read the new value next time or after some number of next times), and if the language is sensible (i.e. Java, not C++... although AFAIK even C++ frowns upon "values out of thin air" and they're trying to modify the standard to formally prohibit them... but in general the issue with C++ is the compiler, not the platform if we assume x86).

Re: Is parallel programming hard, and, if so, what can you do about it?

#72

Post by tomp »

rubyn00bie wrote: post #24

Oh parallelism, the one thing I used to worry about more, and probably should (as far as using GPUs goes)... but also one I don't really sweat so much. Most of the reason, for me, was finding Elixir/Erlang AND their virtual machine BEAM. Until Elixir and BEAM for me, parallel programming had been difficult because the competing mental models in other languages pretty much make for a textbook fantasy. I'm sure some fo…

Interesting writeup!

Do you have any ideas why Akka/JVM is so much worse than Elixir/BEAM? I thought that as long as you stick to Akka (i.e. don't use global mutable state but wrap everything in actors) it should pretty much work the same way... Maybe has something to do with On BEAM a "process" can be pre-empted? Though AFAIK JVM threads can as well...

Re: Is parallel programming hard, and, if so, what can you do about it?

#73

Post by Ericson2314 »

throwaway17_17 wrote: post #17
Ericson2314 wrote: post #10

One version of the parallel vs concurrency distinction is parallelism is the easy part and concurrency is the hard part. I would say that for concurrency, FRP (or various incremental programming technics) is essential. The problem is the possible control flow / traces space is just too large to characterize by hand. Another problem is control flow can be bidirectional. If you join together two streams and wish to be…

Do you have any links handy discussing the need and implementation of the push/pull dynamic you’re talking about. I’ve seen passing references before, but I’ve never come across any substantial discussion of it outside of knowing Conal Elliott has a paper on push/pull FPR.

I don't know of other papers, sadly. I am at the company behind reflex-frp.org/ so it's code + oral tradition for us.

Re: Is parallel programming hard, and, if so, what can you do about it?

#74

Post by jcranmer »

tomp wrote: post #71
jcranmer wrote: post #62

Earlier quoted context omitted.

If you have two accesses on different threads, at least one of which is a write, then you need a synchronization chain between them. Note that this is true even if the read occurs before the write. The most common synchronization chain is the first thread doing some kind of "release" action (releasing a mutex, or storing to an atomic variable using a release (or stronger) ordering type), followed by the second thread…

I'm not a low level programmer, but can you elaborate on this a bit? E.g. why would reading a shared mutable value be wrong, in some specific circumstances? In particular, if the value is a word (and the architecture guarantees atomic writes for word-sized values), and if the reader doesn't care if it reads the previous or the new value (e.g. executes a read of a monotonic counter in a loop, so even if I read the cur…

If you've never had to deal with this stuff before, you probably follow a naive model of memory, wherein all operations are "sequentially consistent": you pick a random thread, and you execute the next memory instruction, and everyone understands that the memory is updated. That model is not how any multicore hardware is actually implemented, because it is slow and often unnecessary.

Now, it is known that, if your program is correctly synchronized, then the existing hardware models are indistinguishable from sequentially consistent execution. This gives rise to the data-race-free model that defines all modern language-level programming models: data races can only exist in the absence of proper synchronization, so we call that behavior undefined [1], and our code goes back to sequential consistency.

The primary issue is that there are two entities playing games with your code to support faster execution: both the compiler and the hardware are making assumptions to speed things up. From the perspective of hardware (i.e., why using "volatile" to stop the compiler from playing games isn't good enough), different processors may have the values in their caches. While cache coherency requires that any given point in time, every processor must agree on the value of every memory location, there is great leeway to reorder loads and stores so that they may execute in different orders than the instruction sequence implies. In the extreme, it is possible that the load of *p may happen before the load of p itself (this is the Alpha memory model, and comes from the existence of uncoordinated cache banks).

[1] Okay, there's a slight untruth here: the C++11 "relaxed atomics" is effectively a data race as could be observed by hardware, but is not undefined in the C++11 sense. This is where it's important to point out that we have been struggling for over a decade to actually come up with a suitably precise definition for relaxed atomics that we're happy with--it is by no means a solved problem.

Re: Is parallel programming hard, and, if so, what can you do about it?

#75

Post by stingraycharles »

platz wrote: post #52
shaklee3 wrote: post #21

I feel like every comment here simply read the title, and not even skimmed the book. This is a book about extreme low-level optimizations in concurrency. It's a poor title for this kind of book since it seems like it's a beginner book, but it's quite the opposite. It's arguing it's hard to implement the structures and methods used by concurrency APIs, not that it's hard to use them.

It's hard to find problems that benefit from parallelism, because most work has sequential elements. Due to amdhal's law, it's harder to realize significant parallel gains unless the problem is of a special or constrained type.

This seems like unnecessarily black and white: in the real world, most parallel solutions have a part shared state / sequential operations, and a part parallel. Just because a solution has some sequential elements, doesn’t mean it doesn’t benefit from parallelism.

Re: Is parallel programming hard, and, if so, what can you do about it?

#76

Post by namibj »

gpderetta wrote: post #69
namibj wrote: post #54

Earlier quoted context omitted.

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 interco…

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?

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+).

Re: Is parallel programming hard, and, if so, what can you do about it?

#77

Post by gpderetta »

namibj wrote: post #76
gpderetta wrote: post #69

Earlier quoted context omitted.

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?

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 (i…

Right, so the broadcast is no more (since the original Pentium Pro IIRC). So why again does x86 requires more expensive broadcasts?

Re: Is parallel programming hard, and, if so, what can you do about it?

#78

Post by ColanR »

jcranmer wrote: post #74
tomp wrote: post #71

Earlier quoted context omitted.

I'm not a low level programmer, but can you elaborate on this a bit? E.g. why would reading a shared mutable value be wrong, in some specific circumstances? In particular, if the value is a word (and the architecture guarantees atomic writes for word-sized values), and if the reader doesn't care if it reads the previous or the new value (e.g. executes a read of a monotonic counter in a loop, so even if I read the cur…

If you've never had to deal with this stuff before, you probably follow a naive model of memory, wherein all operations are "sequentially consistent": you pick a random thread, and you execute the next memory instruction, and everyone understands that the memory is updated. That model is not how any multicore hardware is actually implemented, because it is slow and often unnecessary. Now, it is known that, if your pr…

As a summary to see if I understand you, it sounds like what you're saying is that the CPU will calculate updates to memory, but in the interest of speed and efficiency will not actually write the new value back into RAM for some unspecified period of time?

Re: Is parallel programming hard, and, if so, what can you do about it?

#79

Post by jcranmer »

ColanR wrote: post #78
jcranmer wrote: post #74

Earlier quoted context omitted.

If you've never had to deal with this stuff before, you probably follow a naive model of memory, wherein all operations are "sequentially consistent": you pick a random thread, and you execute the next memory instruction, and everyone understands that the memory is updated. That model is not how any multicore hardware is actually implemented, because it is slow and often unnecessary. Now, it is known that, if your pr…

As a summary to see if I understand you, it sounds like what you're saying is that the CPU will calculate updates to memory, but in the interest of speed and efficiency will not actually write the new value back into RAM for some unspecified period of time?

Both yes and no. If you replace "RAM" in your statement with "cache," then you get a more accurate summary for the situation that gives rise to the issues we're talking about.

But it's also the case that caches avoid writing back into main memory as much as possible, since bandwidth to main memory is quite small. However, cache coherency protocols are used to make all the caches agree on the value, so that committing the value to cache is equivalent to committing it to main memory.

Re: Is parallel programming hard, and, if so, what can you do about it?

#80

Post by gopalv »

agumonkey wrote: post #34
gopalv wrote: post #7

Earlier quoted context omitted.

> 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…

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

> did you have a method/tool to debug (from book, or chatting with others)

Specifically for this issue, I ended up forking valgrind to add multi-threaded watchpoints in code (this was debugging shared memory refcounts, so I had to extend it to log negative refcounts only).

The origin of those patches are here - https://valgrind.org/downloads/variants.html?rjw

Post reply on HN