8 ms·

Is Parallel Programming Hard, And, If So, What Can You Do About It?

122 points by conductor 13y ago

conductor 13y ago
Here is Paul E. McKenney's announcement of the release: http://paulmck.livejournal.com/36854.html http://paulmck.livejournal.com/36854.html
fleitz 13y ago
No it isn't hard, however, you're probably using the wrong tool for the job, and have constructed your problem based on managerial input rather than mathematical formalism. And for the final nail in the coffin you're probably asking your program to do something that violates the known laws of the universe in regard to the speed at which information can travel.
- adamio 13y ago
  "Just get it done; or we'll get someone in here who will happily violate the known laws of the universe"
  - wudf 13y ago
    too close to home
jandrewrogers 13y ago
To clarify something not evident in the title, but which became obvious when I looked through the doc, this is about small-scale parallelism. The kind you find in a single (non-exotic) machine. Massive-scale parallelism uses different data structures, algorithms, and programming models not discussed.
- jedbrown 13y ago
  I write distributed-memory software and that was my first response when I first saw this a few years ago. But we are getting more on-node parallelism (and further on-node parallelism is where most of the next 10 years of performance is expected to come) so these techniques are more relevant to our large-scale computing than you'd otherwise think. Especially as we push strong-scaling limits and attempt to coordinate threads in order to share caches, the standard application of domain decomposition entails higher overheads than we would like to pay.
  - deletes 13y ago
    I have written a pretty simple job-worker system in c ,and I'm interested in this field. Do you have any recommendations for books/resources?
    - gtani 13y ago
      For cuda books, you can go thru Wilt's, it's pretty dense https://twitter.com/CUDAHandbook https://twitter.com/CUDAHandbook There's a handful of papers on attacking the 13 (formerly 8) dwarf problems http://tom.scogland.com/pubs/pdf/feng-ocd-icpe12.pdf http://tom.scogland.com/pubs/pdf/feng-ocd-icpe12.pdf I don't have any specifics on Kaveri memory model but there's lots of small reviews: http://www.tomshardware.com/reviews/a10-7850k-a8-7600-kaveri,3725-3.html http://www.tomshardware.com/reviews/a10-7850k-a8-7600-kaveri... compiler research and thread debugging: http://iacoma.cs.uiuc.edu/iacoma-papers/Illinois_parallelism_book.pdf http://iacoma.cs.uiuc.edu/iacoma-papers/Illinois_parallelism...
      - gtani 13y ago
        and Eijkhout's book, excellent place to start, (but web server down at the moment) http://tacc-web.austin.utexas.edu/veijkhout/public_html/Articles/EijkhoutIntroToHPC.pdf http://tacc-web.austin.utexas.edu/veijkhout/public_html/Arti... Introduction to High Performance Scientific Computing - Victor Eijkhout with Edmond Chow, Robert van de Geijn
  - deleted 13y ago
    [deleted]
  - seanmcdirmid 13y ago
    The question is even fuzzier: how much of that will be massive data parallelism via an on-node GPU? We are already reaching a point where a single machine with 4 CUDA cards can out perform a distributed cluster of 1000 nodes on some applications (the trick would be to eventually do both). The memory hierarchy is our enemy here: the reason GPUs have done so well is that they schedule memory just as much (if not more) as they do computation. If you are going to go through the trouble of coordinating threads to share caches (and this is possible at all), you might have a GPU-friendly problem.
- LnxPrgr3 13y ago
  I can tell I live in a different world—I immediately thought of multi-threaded programming on a single machine. Modern individual machines give us all kinds of opportunity for parallel execution—even my phone has vector instructions and two CPU cores. Modern Intel CPUs have 256-bit wide vectors, meaning you can do 8 floating point operations in a single instruction, assuming you can phrase your problem in the right way. If that's not enough, you can throw a pile of these cores at the problem, assuming you can coordinate work between these threads. My experience has been most programmers struggle hard to build multi-threaded applications, countless hours lost to tracking down race conditions, deadlocks, and unexpectedly bad performance, which is a shame. Scanning through this book, it doesn't appear to cover vector instructions, but it does look like it covers coordinating multiple threads in amazing depth. I feel like I already have a decent handle on multi-threaded programming, but I will be reading this book, and I'll probably learn plenty.
  - shmerl 13y ago
    > My experience has been most programmers struggle hard to build multi-threaded applications, countless hours lost to tracking down race conditions, deadlocks, and unexpectedly bad performance, which is a shame. A lot of it is caused by tools which are by design prone to such conditions and unless you consciously and meticulously follow very strict guidelines, such problems are inevitable. But some tools try to solve it with different design approach (such as Rust language for example) which prevents many of those potential pitfalls implicitly. I wonder if the book is focused on shared memory and locking only, or covers broader range of methodologies (at the first glance it's mostly about classic shared memory and mutual exclusion approach).
frozenport 13y ago
Too bad you can't use unique_lock in C! Part of the problem is the difficulty in implementing this stuff without RAII.
tbrownaw 13y ago
Define "hard". Does it mean, you need greater knowledge? (communication models, deadlock/livelock, etc) Does it mean, you need greater attention to detail? (mistakes that wouldn't matter become serious) Does it mean, you need greater working memory? (remembering what needs locks, and what already has locks; in addition to more ordinary side effects and possible exceptions etc) Does it mean, you need greater fluid intelligence? (reasoning about which locks can be safely composed, or which memory transactions will have too much contention)
beloch 13y ago
I'm coming at this from more of a physics viewpoint than from CPSC. To me, parallel programming is all about dividing a big problem into many little ones. The meat therefore lies in boundary conditions. I don't have time to read this pdf right now, but it contains just two instances of the word "boundary". That sets off alarm bells for me.
- elnate 13y ago
  Your alarm bells are calibrated for physics, it makes sense they would false alarm on a different subject.
legedemon 13y ago
Is there a way to get this book in a single column format rather than the default 2-column format? Reading a 2-column book is extremely difficult for me :(
- paulmck 13y ago
  Here you go! http://kernel.org/pub/linux/kernel/people/paulmck/perfbook/perfbook-1c-e1.pdf http://kernel.org/pub/linux/kernel/people/paulmck/perfbook/p... Each release is typeset both single-column and double-column. Single column works well for the larger-format ebook readers, and double-column works well for laptop/desktop use and for hardcopy.
raphinou 13y ago
Is the book available in another format? Eg epub. Pdf is not really good on an ereader.
- deleted 13y ago
  [deleted]
- paulmck 13y ago
  A number of us have tried a variety of tools to produce e-reader formats, but none of them handle this book at all well. :-( A number of people have reported good results with the single-column format on higher-end ebook readers. The single colume version of the first electronic edition may be found here: http://kernel.org/pub/linux/kernel/people/paulmck/perfbook/perfbook-1c-e1.pdf http://kernel.org/pub/linux/kernel/people/paulmck/perfbook/p...

122 points by conductor 13y ago

Here is Paul E. McKenney's announcement of the release: http://paulmck.livejournal.com/36854.html http://paulmck.livejournal.com/36854.html

fleitz 13y ago

No it isn't hard, however, you're probably using the wrong tool for the job, and have constructed your problem based on managerial input rather than mathematical formalism. And for the final nail in the coffin you're probably asking your program to do something that violates the known laws of the universe in regard to the speed at which information can travel.

adamio 13y ago
"Just get it done; or we'll get someone in here who will happily violate the known laws of the universe"
- wudf 13y ago
  too close to home

jandrewrogers 13y ago

To clarify something not evident in the title, but which became obvious when I looked through the doc, this is about small-scale parallelism. The kind you find in a single (non-exotic) machine. Massive-scale parallelism uses different data structures, algorithms, and programming models not discussed.

jedbrown 13y ago
I write distributed-memory software and that was my first response when I first saw this a few years ago. But we are getting more on-node parallelism (and further on-node parallelism is where most of the next 10 years of performance is expected to come) so these techniques are more relevant to our large-scale computing than you'd otherwise think. Especially as we push strong-scaling limits and attempt to coordinate threads in order to share caches, the standard application of domain decomposition entails higher overheads than we would like to pay.
- deletes 13y ago
  I have written a pretty simple job-worker system in c ,and I'm interested in this field. Do you have any recommendations for books/resources?
  - gtani 13y ago
    For cuda books, you can go thru Wilt's, it's pretty dense https://twitter.com/CUDAHandbook https://twitter.com/CUDAHandbook There's a handful of papers on attacking the 13 (formerly 8) dwarf problems http://tom.scogland.com/pubs/pdf/feng-ocd-icpe12.pdf http://tom.scogland.com/pubs/pdf/feng-ocd-icpe12.pdf I don't have any specifics on Kaveri memory model but there's lots of small reviews: http://www.tomshardware.com/reviews/a10-7850k-a8-7600-kaveri,3725-3.html http://www.tomshardware.com/reviews/a10-7850k-a8-7600-kaveri... compiler research and thread debugging: http://iacoma.cs.uiuc.edu/iacoma-papers/Illinois_parallelism_book.pdf http://iacoma.cs.uiuc.edu/iacoma-papers/Illinois_parallelism...
    - gtani 13y ago
      and Eijkhout's book, excellent place to start, (but web server down at the moment) http://tacc-web.austin.utexas.edu/veijkhout/public_html/Articles/EijkhoutIntroToHPC.pdf http://tacc-web.austin.utexas.edu/veijkhout/public_html/Arti... Introduction to High Performance Scientific Computing - Victor Eijkhout with Edmond Chow, Robert van de Geijn
- deleted 13y ago
  [deleted]
- seanmcdirmid 13y ago
  The question is even fuzzier: how much of that will be massive data parallelism via an on-node GPU? We are already reaching a point where a single machine with 4 CUDA cards can out perform a distributed cluster of 1000 nodes on some applications (the trick would be to eventually do both). The memory hierarchy is our enemy here: the reason GPUs have done so well is that they schedule memory just as much (if not more) as they do computation. If you are going to go through the trouble of coordinating threads to share caches (and this is possible at all), you might have a GPU-friendly problem.
LnxPrgr3 13y ago
I can tell I live in a different world—I immediately thought of multi-threaded programming on a single machine. Modern individual machines give us all kinds of opportunity for parallel execution—even my phone has vector instructions and two CPU cores. Modern Intel CPUs have 256-bit wide vectors, meaning you can do 8 floating point operations in a single instruction, assuming you can phrase your problem in the right way. If that's not enough, you can throw a pile of these cores at the problem, assuming you can coordinate work between these threads. My experience has been most programmers struggle hard to build multi-threaded applications, countless hours lost to tracking down race conditions, deadlocks, and unexpectedly bad performance, which is a shame. Scanning through this book, it doesn't appear to cover vector instructions, but it does look like it covers coordinating multiple threads in amazing depth. I feel like I already have a decent handle on multi-threaded programming, but I will be reading this book, and I'll probably learn plenty.
- shmerl 13y ago
  > My experience has been most programmers struggle hard to build multi-threaded applications, countless hours lost to tracking down race conditions, deadlocks, and unexpectedly bad performance, which is a shame. A lot of it is caused by tools which are by design prone to such conditions and unless you consciously and meticulously follow very strict guidelines, such problems are inevitable. But some tools try to solve it with different design approach (such as Rust language for example) which prevents many of those potential pitfalls implicitly. I wonder if the book is focused on shared memory and locking only, or covers broader range of methodologies (at the first glance it's mostly about classic shared memory and mutual exclusion approach).

frozenport 13y ago

Too bad you can't use unique_lock in C! Part of the problem is the difficulty in implementing this stuff without RAII.

tbrownaw 13y ago

Define "hard". Does it mean, you need greater knowledge? (communication models, deadlock/livelock, etc) Does it mean, you need greater attention to detail? (mistakes that wouldn't matter become serious) Does it mean, you need greater working memory? (remembering what needs locks, and what already has locks; in addition to more ordinary side effects and possible exceptions etc) Does it mean, you need greater fluid intelligence? (reasoning about which locks can be safely composed, or which memory transactions will have too much contention)

beloch 13y ago

I'm coming at this from more of a physics viewpoint than from CPSC. To me, parallel programming is all about dividing a big problem into many little ones. The meat therefore lies in boundary conditions. I don't have time to read this pdf right now, but it contains just two instances of the word "boundary". That sets off alarm bells for me.

elnate 13y ago
Your alarm bells are calibrated for physics, it makes sense they would false alarm on a different subject.

legedemon 13y ago

Is there a way to get this book in a single column format rather than the default 2-column format? Reading a 2-column book is extremely difficult for me :(

paulmck 13y ago
Here you go! http://kernel.org/pub/linux/kernel/people/paulmck/perfbook/perfbook-1c-e1.pdf http://kernel.org/pub/linux/kernel/people/paulmck/perfbook/p... Each release is typeset both single-column and double-column. Single column works well for the larger-format ebook readers, and double-column works well for laptop/desktop use and for hardcopy.

raphinou 13y ago

Is the book available in another format? Eg epub. Pdf is not really good on an ereader.

deleted 13y ago
[deleted]
paulmck 13y ago
A number of us have tried a variety of tools to produce e-reader formats, but none of them handle this book at all well. :-( A number of people have reported good results with the single-column format on higher-end ebook readers. The single colume version of the first electronic edition may be found here: http://kernel.org/pub/linux/kernel/people/paulmck/perfbook/perfbook-1c-e1.pdf http://kernel.org/pub/linux/kernel/people/paulmck/perfbook/p...