11 ms·

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

184 points by nequo 3y ago

zh3 3y ago
Has dang got a day off? Previous discussions:- https://news.ycombinator.com/item?id=22030928 https://news.ycombinator.com/item?id=22030928 (2020) https://news.ycombinator.com/item?id=34859102 https://news.ycombinator.com/item?id=34859102 HN discussion (2023)
samsquire 3y ago
Thanks for another thing I need to add to my reading list in addition to The Art of Multiprocessor Programming. I am really interested in parallel, asynchronous, multithreading, coroutine, futures programming so it's what I spend my days thinking about and blogging about it. I hope you sense my excitement in this comment about this topic. I'm looking for a programming model that parallelises easily and doesn't require much effort, so this PDF seems relevant to me. I really should try be a user of languages like Erlang, Inko, Pony and Go but I am too interested in the mechanism of these languages! I am also learning from Erlang and Go, nginx and LMAX disruptor. I don't focus on number crunching parallelisation, I let libraries and frameworks parallelise matrix multiplication such as BLAS. I'm interested in rote system parallelisation architecture. For example, PHP and nodejs is not a parallel language but how PHP is hosted in FastCGI processes means it can be executed multiple times by nginx so it is in effect parallel across requests. Unfortunately PHP and nodejs cannot create threads or use a thread pool within a request. I want heavy CPU tasks of a request to not block other requests or the event loop and heavy IO requests to not block the event loop. I am a pre-beginner in Rust but I think you can use Rayon for CPU heavy tasks and Tokio for async IO parallelisation. Here's a system diagram that I'm thinking about lately: https://github.com/samsquire/ideas5/blob/main/NonblockingRuntime.drawio.png https://github.com/samsquire/ideas5/blob/main/NonblockingRun... The design is that we have three groupings of thread types. The application starts up some application threads which are not associated with a request, these service multiconsumer multiproducer thread safe ringbuffers in lightweight threads with a Go-erlang-like lightweight process runtime. (My simple lightweight thread runtime is https://github.com/samsquire/preemptible-thread https://github.com/samsquire/preemptible-thread) We also multiplex multiple network clients sockets across a set number of kernel threads which I call control threads. Their responsibility is to dispatch work to a work stealing thread pool ASAP which has its own group of threads. So we pay a thread synchronization cost ONCE per IO which is the dispatch from the control thread to a thread pool thread. (Presumably this is fast, because the thread pool threads are all looping on a submission queue) We split all IO and CPU tasks into two halves: submit and handle reply. I assume you can use liburing or epoll in the control threads. The same with CPU tasks and use ringbuffers to communicate between threads. We can always serve client's requests because we're never blocked on handling someone else's request. The control thread is always unblocked. I think this article is good regarding Python's asyncio story: https://charlesleifer.com/blog/asyncio/ https://charlesleifer.com/blog/asyncio/ I think the best multithreaded architecture is to never rely on synchronization, because it doesn't scale. Try and separate your task so the work is more like a tree than a graph, so that you don't need to communicate between branches. You can shard your data and work independently and merge at the end, similar to mapreduce.
- admsmz 3y ago
  “Interaction nets” might be what you are looking for. I believe there were a couple of hackernews threads about it.
- ascar 3y ago
  > I am really interested in parallel, asynchronous, multithreading, coroutine, futures programming so it's what I spend my days thinking about and blogging about it. That's not parallel programming though. Parallell programming deals with the parallelization of a single sequential algorithm or program (e.g. weather simulation) across multiple threads, CPU or machines, usually with the requirement of real time synchronization. When you paralellize independent tasks (async, coroutines, futures) a whole lot of problems just don't exist and others go more into focus.
  - samsquire 3y ago
    What would you call what I'm working on, it is "parallel" but probably doesn't come under "parallel programming" in the literature. I'm still interested in it though, just haven't got around to it yet, it's a large space. I'm not working on novel parallel algorithms that solve computer science problems, I am interested in parallelism as a general principle for coordinating systems activities. When I get time to delve into parallel algorithms then I'll work on that, at the moment there's a lot of work in just cordinating and scheduling parallel tasks. I am also interested in this area of database internals such as parallel query execution and concurrency control and wait/lockfree algorithms I feel it is complicated and wide space and we deceive ourselves to think we know everything or hubris, which I expressly avoid doing.
    - ascar 3y ago
      What you're looking at is pretty much concurrent programming. https://en.wikipedia.org/wiki/Concurrent_computing https://en.wikipedia.org/wiki/Concurrent_computing
KeplerBoy 3y ago
I wish it included a big section on GPU programming. Still a great read for people primary interested in GPGPU though, since a lot of knowledge transfers well.
klabb3 3y ago
I’m way-above-average interested in concurrent programming but this 600+ page brick will probably remain on my reading list until I am stranded on a deserted island. Did anyone here read the whole thing? Can one make a reasonable summary or is this more of a lexicon of different techniques?
- Tepix 3y ago
  I was going to read it, but then i played a round of Qwitzatteracht, the golf game, instead.
- hospitalJail 3y ago
  Check out the table of contents. I did a quick flip through and realized that I'm never going to be doing low level multithreading, so I don't need to deal with OS layer stuff. There were some other ideas too, might be worth flipping to relevant areas. Heck, if I do end up using it, I'll likely read a summary when I'm dealing with it. There are some ideas that I havent heard of, which was alright, but again, since my current language(python) handles it and I am used to doing multithreading using those libraries, I don't get a ton of value out of reading the fundamentals. (opportunity cost)
  - ChrisMarshallNY 3y ago
    I do a lot of it, but never on the low-end. 99% of mine, is responding to closures for network events and device responses. When you do that, synchronizing is one way to deal with things (wait for the other thing to finish), or completion testing (is the thing ready for the next step?). Basically, they are the same thing. You are also not always guaranteed a standard context, but modern languages make it easy to hook to one. In the "old days," we used to use RefCons (Reference Context hooks).
- ascar 3y ago
  > concurrent programming If you're interested in concurrent programming this book won't give you much. The topics focus on the parallelization of a sequential algorithm and go into detail about things like synchronization (locking, barriers), important HW details (like caches and CPU pipelining) and algorithmic approaches. Imagine a weather simulation and not concurrent requests to a web server.
kosolam 3y ago
Wow
- moffkalast 3y ago
  Hey guys look, it's Owen Wilson.
RyanHamilton 3y ago
>>Is Parallel Programming Hard, and, If So, What Can You Do About It? I confess I didn't read TFA but the title made me think of something that hopefully some people here are well placed to take further. In a programming language I use there is an "each" function. For example in pseudo-java given a function f(int i). result = f each List<Integer>. Runs f over each integer. To make this multi-threaded you can simply say f peach listOfNumbers. Today in java you can do similar using streams: listOfNumbers.parallelStream().forEach() but for anyone here creating a new language I would suggest parallelising the language primitive forEach loop by default. Given the number of CPUs and that the machine is better selecting the optimal threading distribution I think that would be the better choice. This seems a small simple change but the hard part about parallel programming is often getting people to use it. By making it totally invisible, it's "easy".
- flohofwoe 3y ago
  It's only easy if the items that are iterated over are entirely self contained, and the code in the loop body also does not need (write-)access to any other state that might be shared between threads. Rust has such limitations built into the language, but this is also one of the points that make Rust "difficult" (because you actually need to think first about how you organize your data to be "multi-threading-compatible", and that's the hard part, not adding a parallel for-each to a language.
  - tm-guimaraes 3y ago
    That’s only safety. It still does not guarantee that performance would improve.
    - bsdetector 3y ago
      A built-in parallel foreach can't guarantee better performance because the hardware isn't there. The parallel part is scheduled on normal threads by the kernel and this is too unpredictable. But if each OS-scheduled CPU was really a cluster of for instance 1 fast + 64 slow cores then it could have special instructions to split a low-level loop on these slow cores and to facilitate blocking and rejoining back into a single stream. A 'parallel branch' instruction could take index, limit, and estimated instruction count and the CPU itself could decide whether to run it in a single fast stream or in parallel on slow cores. There's some technical challenges like the size of a register file (so probably uninterruptible), but this may be where we're going since there's diminishing returns from making a single CPU faster and there's lots of opportunity for parallel processing that GPUs are too clumsy for.
Rochus 3y ago
An impressive work; got yet another 40 pages since Dec. 2021 edition.
jefc1111 3y ago
My answers to the two questions in the post title: "Yes" and "Read Concurrent Data Processing in Elixir [1]" I have dealt with concurrency in PHP (good times with Laravel Horizon) in a couple of different ways and in NodeJS (never feels good, to me). The BEAM has some great primitives for concurrency and the book mentioned above walks the reader through them at a good pace. I read it cover to cover and it really enriched my mental model of how to use concurrency and async. [1] https://pragprog.com/titles/sgdpelixir/concurrent-data-processing-in-elixir/ https://pragprog.com/titles/sgdpelixir/concurrent-data-proce...
- PheonixPharts 3y ago
  Concurrency is not the same as parallelism. You can have single threaded concurrent programs.
  - jefc1111 3y ago
    Oh yes, good call! Still, was a good book...
davidgrenier 3y ago
This looks brutal, for a lot of people John Reppy's book Concurrent Programming in ML (as in SML not Machine Learning) is going to be much more accessible. Pick the CSP-style library in the programming language of your choice. Go with goroutines and channels Clojure with core.async F# with Hopac It would be a very interesting project to roll your own in C# using Microsoft Robotics Studio's CCR (Coordination and Concurrency Runtime) (though I speculate those are buffered channels by default).
- kubanczyk 3y ago
  Etmology of ML: "Meta Language"
- PheonixPharts 3y ago
  There are multiple replies like this one, but it's a bit shocking to see that on Hacker News people don't know the difference between concurrent programming and parallel programming. Concurrency means that you can have multiple tasks running in the same time period, Parallelism means you have multiple tasks running at the same time. The most obvious demonstration of this is that you can (and many languages do) have single threaded concurrency. I did some grad course work in parallel programming and there's really no way to not make it "brutal", because to really do it in a way that increases performance you need to really understand some low-level performance issues.
  - cpach 3y ago
    Correct me if I’m wrong, but isn’t concurrency enough for “most” use-cases? When does one really need true parallelism?
    - shwestrick 3y ago
      Parallelism is only about performance, that's it. If you need something to go faster, parallelism is an option. Looking into the future, parallelism is one of the only remaining techniques for scaling classical computing. Processors have stopped getting faster. Instead, they're getting fatter (more cores).
anttiharju 3y ago
Here's course materials about the topic from my university, I assume they're available globally even if you can't sign up for the course: https://ppc.cs.aalto.fi/ https://ppc.cs.aalto.fi/
cj 3y ago
This reminds me when I was going through the YC accelerator in 2012. We were building a web-based email client, and PG didn’t like the idea. He pulled our team aside during one of the batch-wide Tues night dinners and suggested we pivot to building something that could take single threaded programs and quickly/easily make them multi-threaded. No one on our team knew anything about threading (none of us had even graduated college). So we kept working on the email client, now defunct. PG brought us in a back room where the Stripe founders were waiting (I think they were speaking that night). We were brainstorming ideas with them, and one of the brothers recommended we build something having to do with phones and calling people (don’t remember the idea anymore). PG was not very happy when he heard we weren’t going to pivot and kept on working on a new email client :)
- bee_rider 3y ago
  If you had something in 2012 that could magically convert a single threaded program to a parallel one, it would be pretty useful. Seems incredibly difficult to build, though.
  - adsfgiodsnrio 3y ago
    Do you think a Philosopher's Stone might have some value, too? I think Y Combinator should look into it. Maybe an Elixir of Immortality? An automatically parallelizing compiler that works in general is one of the holy grails of computer science. They have been extensively researched for decades and we have little to show for it. If anyone managed to make one it would instantly render the entire computer industry obsolete. We have systems that work in specialized cases with a whole lot of manual intervention. Even then, the executable is often less efficient than the serial version.
    - bee_rider 3y ago
      I also think it is an unrealistic suggestion, in case that didn’t come through in my first comment! Haha. But I’m sure the hoped-for result was just another one of those specialized tools, specialized for some Y Combinator niche. Which is also probably an unrealistic idea for a team that isn’t interested in that sort of thing, but at least isn’t totally ridiculously stupid.
Const-me 3y ago
As a developer, I often choose higher-level APIs not listed in that article. On Windows, OSX and iOS the OS userland already implements general, and relatively easy to use, thread pools. On Windows, see CreateThreadpoolWork, WaitForThreadpoolWorkCallbacks, etc. It’s easier to use threads with locks while someone else is managing these threads. On Apple, the pool is called “grand central dispatch” and does pretty much the same thing. Modern Windows kernel supports interesting synchronization APIs like WaitOnAddress, WakeByAddressSingle which allow to implement locks without the complexity or performance overhead of maintaining special synchronization objects. Linux kernel implements performant and scalable message queues, see mq_overview(7). And it has synchronization objects like eventfd() and pidfd_open() which allow to integrate locks or other things into poll/epoll based event loops.
- vmfunction 3y ago
  what about "green threads" that is not managed by the OS like https://tokio.rs https://tokio.rs ?
  - deleted 3y ago
    [deleted]
  - aleph_minus_one 3y ago
    Green threads do not make use of multiple cores of a modern processor.
    - jabl 3y ago
      It's entirely possible for a green threads implementation to schedule the green threads over multiple OS threads, thus making use of multiple cores. The programming language "Go" being a popular implementation of this.
    - nextaccountic 3y ago
      M:N green threads run M green threads on N OS threads and thus use up to N processor cores
remontoire 3y ago
Watching geohot code a general matrix multiply algorithm from 0.9 GFLOPS and optimising it to 100 glops by only tinkering with cache locality, it makes me wonder how much effort should be put into single threaded performance before ever thinking about multi threading
- nmarinov 3y ago
  Fun video[0]. The optimization bit starts at 0:35. [0]: https://www.youtube.com/watch?v=VgSQ1GOC86s https://www.youtube.com/watch?v=VgSQ1GOC86s
- jetbalsa 3y ago
  I've seen stuff like that before with a game called Factroio, The only game I've ever see that is optimized so hard that your RAM Speed can affect large bases rather quickly, same with faster L2 Cache. Their entire blog series[1] covers a large part of how they did this. but for a game written mostly in LUA they sure did a good job on it. 1: https://www.factorio.com/blog/post/fff-204 https://www.factorio.com/blog/post/fff-204
  - DizzyDoo 3y ago
    Yes, the Factorio devs had an approach where they optimised everything happening in the game in the original singlethreaded environment, before moving onto multithreaded support. That's where the game is now, and as far as I understand it the multithreading occurs on each independent set of conveyor belts or belt lanes, and there's some info on that in this blog post[0] for anyone interested. [0] - https://www.factorio.com/blog/post/fff-364 https://www.factorio.com/blog/post/fff-364
  - rcxdude 3y ago
    It makes sense that a simulation game like factorio would be memory bandwidth limited: each tick it needs to update the state of a large number of entities using relatively simple operations. The main trick to making it fast is reducing that amount of data you need to update each tick and arranging the data in memory so you can load it fast (i.e. predictably and sequentially so the prefetcher can do is job) and only need to load and modify it once each tick (at least in terms of loading and eviction from cache). The complexity is in how best to do that, especially both at once. For example, in the blog post they have linked lists for active entities. This makes sense from the point of view of not loading data you don't need to process, but it limits how fast you can load data because you can only prefetch one item ahead (compared to an array where you can prefetch as far ahead as your buffers will allow)
dejvid_ 3y ago
It is not hard if you use proper libraries. So Take a look into Scala ZIO library, you can solve any concurrency problem with an ease. With the proper toolset which ZIO provides, you can tackle any consurrency problem in typesafe way, and mostly correct if it compiles :)
bullen 3y ago
Only 2 ways into parallelism: - Arrays of 64 byte Structures with C. (client) - Java. (server) Everything else is not atomic.
- CyberDildonics 3y ago
  This makes no sense. - Arrays of 64 byte Structures with C. (client) All you need for parallelism is to spawn threads and give each thread a range of an array to work on. You don't need each element to be atomic because you aren't synchronizing on each element. What makes you think you need specific data and a specific language? - Java. (server) This makes even less sense. A language doesn't matter and how it's used doesn't matter. Where did you get this idea? Can you link something? Everything else is not atomic. I think you don't understand what parallelism means. Read about openMP, it is very simple.
cmrdporcupine 3y ago
Concurrent state management is hard, and I remain disappointed that software transactional memory -- and pushing a DB-style approach to non-DB workloads generally -- hasn't caught on. I think most "application" type programs would benefit from being able to manage state in terms of higher level transactional operations and let their runtime take care of serializing and avoiding deadlock and race conditions. Developers in those spaces have come to rely on garbage collection in their runtimes, I see no reason why they couldn't come to also rely on a fully isolated MVCC transaction model (and only get access to non-transactional memory in exceptional circumstances). Bonus points if said transactions tie back to the persistent RDBMS transaction as well. There are too many minefields in manual lock management and the tools remain fairly low level. Ownership management in languages like Rust helps, following a discipline like an actor/CSP approach helps, etc. but in the end if there's shared state and there's parallel work, there's potential for trouble.
- twoodfin 3y ago
  You might be interested in Joe Duffy’s retrospective on Microsoft’s failed experiment to integrate STM into .NET: https://joeduffyblog.com/2010/01/03/a-brief-retrospective-on-transactional-memory/ https://joeduffyblog.com/2010/01/03/a-brief-retrospective-on...
  - cmrdporcupine 3y ago
    Thanks, skimmed a bit of the first half but will get into it more after my work day.
    - cmrdporcupine 3y ago
      So, going through this a bit more on lunch break; I think the root of some of the disillusionment faced here -- and probably the lack of success in STM at this level generally -- is that they tried to do too much. I don't necessarily want the whole memory model of the runtime or VM to offer transactions necessarily. What I think is a good idea is to offer an overall framework -- within which higher level applications can be written -- that brings transactional semantics with it. Basically a set of collections and data transformation and communications and process coordination libraries that work in harmony with an underlying MVCC storage layer -- rather than baking a transactional atomic keyword down to the syntactical level of the language or the memory model of the VM/runtime. Put another way: I wouldn't necessarily give users the STM facilities. I would use lower level STM facilities to construct a higher level toolkit, and only expose that. Basically an RDBMS in-process -- without the SQL language boundary -- to be frank. Yes, users could escape it easily, and start doing inconsistent things. But that's on them, same as any other framework. Provide the pattern and tools in a nice coherent box and don't try to take over the whole world.
z3t4 3y ago
The symtoms that lead up to me learning about the need for locks in multi threaded servers was painful. That the state could change from one line of code to the next line, how could it change when I just set it a micro second ago? Because the user clicked the button twice and the call was executed simultaneously but in different threads because my new server had many cores. Then I learned about async programming, but I no longer remember what was so difficult about it. Just that it took about a year and I basically had to rewire how my brain visualize program execution.
- mrkeen 3y ago
  > the state could change from one line of code to the next line > I no longer remember what was so difficult about it You or (your libraries) probably stopped mutating things. No mutation means you can rely on values you used several lines ago. This is the perennial HN discussion whenever the word 'functional' comes up. "But x=x+1 is simple to teach to beginners" is the rallying cry. Well, this is why not. Also, > the need for locks This goes away if you don't mutate.
  - gpderetta 3y ago
    yet physical hardware has a finite amount of memory, so at some point you either stop your program of you have to modify a cell you already touched.
    - tialaramex 3y ago
      Mutation isn't confusing. On its own. Multiple references isn't confusing. On its own. The observation, which I don't think I saw being made twenty years ago (I could be wrong) is that you shouldn't mix these two things. No multiple references with mutation. In theory you can safely do so in serial programs if you were careful enough, in practice you won't be careful enough and we should write fewer serial programs than we do, so why not reject this outright. Rust is one particular (and notably successful) attempt to make a programming language about this big idea, but it's the idea in Val and several other newer languages. There are a lot of unknowns about the best way to approach this, but "Just pretend it's not important" is not a correct answer.
DayDollar 3y ago
Ah, the old debate and approach. Centralize the control, Decentralize problem handling, centralize the knowledge needed for untangling parallelism, realize you just created a centralized authority, undoing the parallelism. Then there is the physics engine view to all things. Data is just sand washing against the shoreline of parallel computation instances and interaction, is just sticking these dataparticles together, taking them out of the general flow to be interacted on in unison, carrying the resolution authority within them as long as they are "clumbed" together. Data is just particles, the programs interacting on it are just a limited number of program cells, traversing it and interaction clumps it together, making the processing of it slower, but also centralized to computation node. A centralized node, processing a huge clump of interacting data, even throws a sort of "relativity" shadow, as other, smaller, non interacting data, is processed faster and leaping ahead in the interactions.
sproketboy 3y ago
[dead]
atum47 3y ago
I took the parallel programming class back in college. Even though we implemented several good examples using parallelism like matrix multiplications and different methods of achieving it using the GPU or distributed computers, the main goal of the class was to analyze and see what problems could be processed in parallel and also how to divide the problem in small chunks in order to do so. It was a lot of fun.
giovannibonetti 3y ago
Functional programming can be a great way to handle parallel programming in a sane way. See the Futhark language [1], for example, that accepts high-level constructs like map and reduce, then converts them to the appropriate machine code, either on the CPU or the GPU. [1] https://futhark-lang.org/ https://futhark-lang.org/
uguuo_o 3y ago
On scientific computing (computational fluid dynamics, computational electromagnetics, etc.), parallel programing is a must. Most of the algorithms are not embarrassingly parallel, and need a significant amount of communication between threads during runtime. We mostly use one of the many MPI [0] libraries available for desktop and high-performance computing machines. Using these programming paradigms is difficult but tend to result in fantastic scalability for all types of engineering problems. [0] https://en.m.wikipedia.org/wiki/Message_Passing_Interface https://en.m.wikipedia.org/wiki/Message_Passing_Interface
- OscarCunningham 3y ago
  So this might be a naive question, but is it literally that you're simulating a fluid in parallel by having each thread simulate a portion of the space? And then the message passing between threads is the data about the fluid on the boundary?
  - elil17 3y ago
    Computational fluid dynamics is actually a problem where parallelization doesn't get you much. It is primarily limited by memory bandwidth.
    - sapiogram 3y ago
      It's very, very hard to be memory bandwidth bottlenecked if your program is not parallelized, even on consumer hardware. A 5Ghz cpu core with dual-channel DDR5 might get 75 GB/s of memory bandwidth. That's 15 bytes per clock cycle. Prosumer hardware? Maybe 60 bytes per clock cycle. No way one cpu core can keep up with that.
    - ascar 3y ago
      Memory bandwidth can be increased by parallelization though. E.g. MPI (Message Passing Interface) is one of the major libraries in parallel programming and supercomputing and deals with parallelization across multiple machines.
    - 3y ago
namirez 3y ago
Parallel programming is not hard; state management is hard. And for problems that are not embarrassingly parallel, unfortunately there is no silver bullet.
ascar 3y ago
I see a lot of confusion between parallel programming [1] and concurrent programming [2] in the comments here. The former and what this book is about deals with the problem of parallelizaing a single sequential program. There usually is strong interaction or dependencies between elements and progress needs synchronization. E.g. timestep iterations in real-time simulations that need synchronization with data communication after each timestep. These simulation also tend to get way to big to be run on a single machine, lest a single thread, and get scaled up to millions of cores/threads in supercomputers. Concurrent programming is what most developers working with the internet are more familiar with. You have mostly independent tasks that you want to run concurrently. "A concurrent system is one where a computation can advance without waiting for all other computations to complete." [2] E.g. nginx serving thousands of user requests at the same time. The problem domains have a lot of overlap on the basics (e.g. threading), however the focus is very different. Things like synchronization (mutex, barriers), cache locality and memory bandwith & latency play a central role in parallel programming, while concurrent programming focuses more on the engineering challenge of distributing independent tasks across multiple threads or machines. [1] https://en.wikipedia.org/wiki/Parallel_computing https://en.wikipedia.org/wiki/Parallel_computing [2] https://en.wikipedia.org/wiki/Concurrent_computing https://en.wikipedia.org/wiki/Concurrent_computing
- vivegi 3y ago
  The book covers it in Appendix A.6 (p 424) in the v2023.06.11a PDF file. > A.6 What is the Difference Between “Concurrent” and “Parallel”? > From a classic computing perspective, “concurrent” and “parallel” are clearly synonyms. However, this has not stopped many people from drawing distinctions between the two, and it turns out that these distinctions can be understood from a couple of different perspectives. > The first perspective treats “parallel” as an abbreviation for “data parallel”, and treats “concurrent” as pretty much everything else. From this perspective, in parallel computing, each partition of the overall problem can proceed completely independently, with no communication with other partitions. In this case, little or no coordination among partitions is required. In contrast, concurrent computing might well have tight interdependencies, in the form of contended locks, transactions, or other synchronization mechanisms. > This of course begs the question of why such a distinction matters, which brings us to the second perspective, that of the underlying scheduler. Schedulers come in a wide range of complexities and capabilities, and as a rough rule of thumb, the more tightly and irregularly a set oparallel processes communicate, the higher the level of sophistication required from the scheduler. As such, parallel computing’s avoidance of interdependencies means that parallel-computing programs run well on the least-capable schedulers. In fact, a pure parallel-computing program can run successfully after being arbitrarily subdivided and interleaved onto a uniprocessor. In contrast, concurrent computing programs might well require extreme subtlety on the part of the scheduler.
nayuki 3y ago
Having seen this years ago, my favorite part is still the comic that says "do I out things of Look! can order." in section 15.1.1 "Why Hardware Misordering?".
EVa5I7bHFq9mnYK 3y ago
It's not, if you are ready to copy your data around a lot, aka functional programming.
imtringued 3y ago
The biggest problem with parallel programming are the fixed communications costs. Threads are expensive to launch and stop. This then leads to thread pooling which is not a bad idea but then you have to make sure that nothing blocks the thread pool. Java is going to fix this problem with virtual threads. Even if threads are cheap, you still have to decide when to parallelize something. If the section is short enough, splitting up the work will make your program slower because you have to wait for the new thread to be scheduled and then for the launching thread to be scheduled. These are just the problems to get you started. They are not big barriers but they are big enough to make it not be the default. The next problem is dynamic runtime behaviour. A parallel program can exhibit far more weird behaviours due to the nature of interleaved execution. This means that you will want a strong ownership model for your data and so far only Rust does it competently. Instanced locks are difficult to get right. Static locks are almost trivial but only if you can guarantee that your critical section never calls code that invokes the same lock. Recursive locks are a bad idea but not using them means you need to have two sets of methods. One is the public synchronized method that library users call and the other is the private unsynchronized method that actually does most of the work. It's very ugly to work with locks. The other problem is that a lot of problems are genuinely difficult to parallelize. It is better to parallelize hierarchically where each hierarchy is still single threaded. This way you can maintain the illusion of mostly single threaded code. The alternative often requires a bespoke architecture. There are hardly any generalized solutions. You need to be an expert at parallel programming.
spacechild1 3y ago
I have almost finished the book (to be honest, I have skipped the "Validation" chapter) and I found it quite interesting. In particular I liked that it also covered more "exotic" topics such as sequence locks, hazard pointers and RCU. However, in general, I found it a bit too much focussed on Linux kernel code. The code examples are full of kernel code macros, such as READ_ONCE and WRITE_ONCE, instead of C11/C++11 atomics. In the end, I appreciated it because it gave me a new perspective, but I'm not sure if this helpful for people who are not already familiar with parallel programming...
lincpa 3y ago
[dead]

184 points by nequo 3y ago

zh3 3y ago

Has dang got a day off? Previous discussions:- https://news.ycombinator.com/item?id=22030928 https://news.ycombinator.com/item?id=22030928 (2020) https://news.ycombinator.com/item?id=34859102 https://news.ycombinator.com/item?id=34859102 HN discussion (2023)

samsquire 3y ago

Thanks for another thing I need to add to my reading list in addition to The Art of Multiprocessor Programming. I am really interested in parallel, asynchronous, multithreading, coroutine, futures programming so it's what I spend my days thinking about and blogging about it. I hope you sense my excitement in this comment about this topic. I'm looking for a programming model that parallelises easily and doesn't require much effort, so this PDF seems relevant to me. I really should try be a user of languages like Erlang, Inko, Pony and Go but I am too interested in the mechanism of these languages! I am also learning from Erlang and Go, nginx and LMAX disruptor. I don't focus on number crunching parallelisation, I let libraries and frameworks parallelise matrix multiplication such as BLAS. I'm interested in rote system parallelisation architecture. For example, PHP and nodejs is not a parallel language but how PHP is hosted in FastCGI processes means it can be executed multiple times by nginx so it is in effect parallel across requests. Unfortunately PHP and nodejs cannot create threads or use a thread pool within a request. I want heavy CPU tasks of a request to not block other requests or the event loop and heavy IO requests to not block the event loop. I am a pre-beginner in Rust but I think you can use Rayon for CPU heavy tasks and Tokio for async IO parallelisation. Here's a system diagram that I'm thinking about lately: https://github.com/samsquire/ideas5/blob/main/NonblockingRuntime.drawio.png https://github.com/samsquire/ideas5/blob/main/NonblockingRun... The design is that we have three groupings of thread types. The application starts up some application threads which are not associated with a request, these service multiconsumer multiproducer thread safe ringbuffers in lightweight threads with a Go-erlang-like lightweight process runtime. (My simple lightweight thread runtime is https://github.com/samsquire/preemptible-thread https://github.com/samsquire/preemptible-thread) We also multiplex multiple network clients sockets across a set number of kernel threads which I call control threads. Their responsibility is to dispatch work to a work stealing thread pool ASAP which has its own group of threads. So we pay a thread synchronization cost ONCE per IO which is the dispatch from the control thread to a thread pool thread. (Presumably this is fast, because the thread pool threads are all looping on a submission queue) We split all IO and CPU tasks into two halves: submit and handle reply. I assume you can use liburing or epoll in the control threads. The same with CPU tasks and use ringbuffers to communicate between threads. We can always serve client's requests because we're never blocked on handling someone else's request. The control thread is always unblocked. I think this article is good regarding Python's asyncio story: https://charlesleifer.com/blog/asyncio/ https://charlesleifer.com/blog/asyncio/ I think the best multithreaded architecture is to never rely on synchronization, because it doesn't scale. Try and separate your task so the work is more like a tree than a graph, so that you don't need to communicate between branches. You can shard your data and work independently and merge at the end, similar to mapreduce.

admsmz 3y ago
“Interaction nets” might be what you are looking for. I believe there were a couple of hackernews threads about it.
ascar 3y ago
> I am really interested in parallel, asynchronous, multithreading, coroutine, futures programming so it's what I spend my days thinking about and blogging about it. That's not parallel programming though. Parallell programming deals with the parallelization of a single sequential algorithm or program (e.g. weather simulation) across multiple threads, CPU or machines, usually with the requirement of real time synchronization. When you paralellize independent tasks (async, coroutines, futures) a whole lot of problems just don't exist and others go more into focus.
- samsquire 3y ago
  What would you call what I'm working on, it is "parallel" but probably doesn't come under "parallel programming" in the literature. I'm still interested in it though, just haven't got around to it yet, it's a large space. I'm not working on novel parallel algorithms that solve computer science problems, I am interested in parallelism as a general principle for coordinating systems activities. When I get time to delve into parallel algorithms then I'll work on that, at the moment there's a lot of work in just cordinating and scheduling parallel tasks. I am also interested in this area of database internals such as parallel query execution and concurrency control and wait/lockfree algorithms I feel it is complicated and wide space and we deceive ourselves to think we know everything or hubris, which I expressly avoid doing.
  - ascar 3y ago
    What you're looking at is pretty much concurrent programming. https://en.wikipedia.org/wiki/Concurrent_computing https://en.wikipedia.org/wiki/Concurrent_computing

KeplerBoy 3y ago

I wish it included a big section on GPU programming. Still a great read for people primary interested in GPGPU though, since a lot of knowledge transfers well.

klabb3 3y ago

I’m way-above-average interested in concurrent programming but this 600+ page brick will probably remain on my reading list until I am stranded on a deserted island. Did anyone here read the whole thing? Can one make a reasonable summary or is this more of a lexicon of different techniques?

Tepix 3y ago
I was going to read it, but then i played a round of Qwitzatteracht, the golf game, instead.
hospitalJail 3y ago
Check out the table of contents. I did a quick flip through and realized that I'm never going to be doing low level multithreading, so I don't need to deal with OS layer stuff. There were some other ideas too, might be worth flipping to relevant areas. Heck, if I do end up using it, I'll likely read a summary when I'm dealing with it. There are some ideas that I havent heard of, which was alright, but again, since my current language(python) handles it and I am used to doing multithreading using those libraries, I don't get a ton of value out of reading the fundamentals. (opportunity cost)
- ChrisMarshallNY 3y ago
  I do a lot of it, but never on the low-end. 99% of mine, is responding to closures for network events and device responses. When you do that, synchronizing is one way to deal with things (wait for the other thing to finish), or completion testing (is the thing ready for the next step?). Basically, they are the same thing. You are also not always guaranteed a standard context, but modern languages make it easy to hook to one. In the "old days," we used to use RefCons (Reference Context hooks).
ascar 3y ago
> concurrent programming If you're interested in concurrent programming this book won't give you much. The topics focus on the parallelization of a sequential algorithm and go into detail about things like synchronization (locking, barriers), important HW details (like caches and CPU pipelining) and algorithmic approaches. Imagine a weather simulation and not concurrent requests to a web server.

kosolam 3y ago

Wow

moffkalast 3y ago
Hey guys look, it's Owen Wilson.

RyanHamilton 3y ago

>>Is Parallel Programming Hard, and, If So, What Can You Do About It? I confess I didn't read TFA but the title made me think of something that hopefully some people here are well placed to take further. In a programming language I use there is an "each" function. For example in pseudo-java given a function f(int i). result = f each List<Integer>. Runs f over each integer. To make this multi-threaded you can simply say f peach listOfNumbers. Today in java you can do similar using streams: listOfNumbers.parallelStream().forEach() but for anyone here creating a new language I would suggest parallelising the language primitive forEach loop by default. Given the number of CPUs and that the machine is better selecting the optimal threading distribution I think that would be the better choice. This seems a small simple change but the hard part about parallel programming is often getting people to use it. By making it totally invisible, it's "easy".

flohofwoe 3y ago
It's only easy if the items that are iterated over are entirely self contained, and the code in the loop body also does not need (write-)access to any other state that might be shared between threads. Rust has such limitations built into the language, but this is also one of the points that make Rust "difficult" (because you actually need to think first about how you organize your data to be "multi-threading-compatible", and that's the hard part, not adding a parallel for-each to a language.
- tm-guimaraes 3y ago
  That’s only safety. It still does not guarantee that performance would improve.
  - bsdetector 3y ago
    A built-in parallel foreach can't guarantee better performance because the hardware isn't there. The parallel part is scheduled on normal threads by the kernel and this is too unpredictable. But if each OS-scheduled CPU was really a cluster of for instance 1 fast + 64 slow cores then it could have special instructions to split a low-level loop on these slow cores and to facilitate blocking and rejoining back into a single stream. A 'parallel branch' instruction could take index, limit, and estimated instruction count and the CPU itself could decide whether to run it in a single fast stream or in parallel on slow cores. There's some technical challenges like the size of a register file (so probably uninterruptible), but this may be where we're going since there's diminishing returns from making a single CPU faster and there's lots of opportunity for parallel processing that GPUs are too clumsy for.

Rochus 3y ago

An impressive work; got yet another 40 pages since Dec. 2021 edition.

jefc1111 3y ago

My answers to the two questions in the post title: "Yes" and "Read Concurrent Data Processing in Elixir [1]" I have dealt with concurrency in PHP (good times with Laravel Horizon) in a couple of different ways and in NodeJS (never feels good, to me). The BEAM has some great primitives for concurrency and the book mentioned above walks the reader through them at a good pace. I read it cover to cover and it really enriched my mental model of how to use concurrency and async. [1] https://pragprog.com/titles/sgdpelixir/concurrent-data-processing-in-elixir/ https://pragprog.com/titles/sgdpelixir/concurrent-data-proce...

PheonixPharts 3y ago
Concurrency is not the same as parallelism. You can have single threaded concurrent programs.
- jefc1111 3y ago
  Oh yes, good call! Still, was a good book...

davidgrenier 3y ago

This looks brutal, for a lot of people John Reppy's book Concurrent Programming in ML (as in SML not Machine Learning) is going to be much more accessible. Pick the CSP-style library in the programming language of your choice. Go with goroutines and channels Clojure with core.async F# with Hopac It would be a very interesting project to roll your own in C# using Microsoft Robotics Studio's CCR (Coordination and Concurrency Runtime) (though I speculate those are buffered channels by default).

kubanczyk 3y ago
Etmology of ML: "Meta Language"
PheonixPharts 3y ago
There are multiple replies like this one, but it's a bit shocking to see that on Hacker News people don't know the difference between concurrent programming and parallel programming. Concurrency means that you can have multiple tasks running in the same time period, Parallelism means you have multiple tasks running at the same time. The most obvious demonstration of this is that you can (and many languages do) have single threaded concurrency. I did some grad course work in parallel programming and there's really no way to not make it "brutal", because to really do it in a way that increases performance you need to really understand some low-level performance issues.
- cpach 3y ago
  Correct me if I’m wrong, but isn’t concurrency enough for “most” use-cases? When does one really need true parallelism?
  - shwestrick 3y ago
    Parallelism is only about performance, that's it. If you need something to go faster, parallelism is an option. Looking into the future, parallelism is one of the only remaining techniques for scaling classical computing. Processors have stopped getting faster. Instead, they're getting fatter (more cores).

anttiharju 3y ago

Here's course materials about the topic from my university, I assume they're available globally even if you can't sign up for the course: https://ppc.cs.aalto.fi/ https://ppc.cs.aalto.fi/

cj 3y ago

This reminds me when I was going through the YC accelerator in 2012. We were building a web-based email client, and PG didn’t like the idea. He pulled our team aside during one of the batch-wide Tues night dinners and suggested we pivot to building something that could take single threaded programs and quickly/easily make them multi-threaded. No one on our team knew anything about threading (none of us had even graduated college). So we kept working on the email client, now defunct. PG brought us in a back room where the Stripe founders were waiting (I think they were speaking that night). We were brainstorming ideas with them, and one of the brothers recommended we build something having to do with phones and calling people (don’t remember the idea anymore). PG was not very happy when he heard we weren’t going to pivot and kept on working on a new email client :)

bee_rider 3y ago
If you had something in 2012 that could magically convert a single threaded program to a parallel one, it would be pretty useful. Seems incredibly difficult to build, though.
- adsfgiodsnrio 3y ago
  Do you think a Philosopher's Stone might have some value, too? I think Y Combinator should look into it. Maybe an Elixir of Immortality? An automatically parallelizing compiler that works in general is one of the holy grails of computer science. They have been extensively researched for decades and we have little to show for it. If anyone managed to make one it would instantly render the entire computer industry obsolete. We have systems that work in specialized cases with a whole lot of manual intervention. Even then, the executable is often less efficient than the serial version.
  - bee_rider 3y ago
    I also think it is an unrealistic suggestion, in case that didn’t come through in my first comment! Haha. But I’m sure the hoped-for result was just another one of those specialized tools, specialized for some Y Combinator niche. Which is also probably an unrealistic idea for a team that isn’t interested in that sort of thing, but at least isn’t totally ridiculously stupid.

Const-me 3y ago

As a developer, I often choose higher-level APIs not listed in that article. On Windows, OSX and iOS the OS userland already implements general, and relatively easy to use, thread pools. On Windows, see CreateThreadpoolWork, WaitForThreadpoolWorkCallbacks, etc. It’s easier to use threads with locks while someone else is managing these threads. On Apple, the pool is called “grand central dispatch” and does pretty much the same thing. Modern Windows kernel supports interesting synchronization APIs like WaitOnAddress, WakeByAddressSingle which allow to implement locks without the complexity or performance overhead of maintaining special synchronization objects. Linux kernel implements performant and scalable message queues, see mq_overview(7). And it has synchronization objects like eventfd() and pidfd_open() which allow to integrate locks or other things into poll/epoll based event loops.

vmfunction 3y ago
what about "green threads" that is not managed by the OS like https://tokio.rs https://tokio.rs ?
- deleted 3y ago
  [deleted]
- aleph_minus_one 3y ago
  Green threads do not make use of multiple cores of a modern processor.
  - jabl 3y ago
    It's entirely possible for a green threads implementation to schedule the green threads over multiple OS threads, thus making use of multiple cores. The programming language "Go" being a popular implementation of this.
  - nextaccountic 3y ago
    M:N green threads run M green threads on N OS threads and thus use up to N processor cores

remontoire 3y ago

Watching geohot code a general matrix multiply algorithm from 0.9 GFLOPS and optimising it to 100 glops by only tinkering with cache locality, it makes me wonder how much effort should be put into single threaded performance before ever thinking about multi threading

nmarinov 3y ago
Fun video[0]. The optimization bit starts at 0:35. [0]: https://www.youtube.com/watch?v=VgSQ1GOC86s https://www.youtube.com/watch?v=VgSQ1GOC86s
jetbalsa 3y ago
I've seen stuff like that before with a game called Factroio, The only game I've ever see that is optimized so hard that your RAM Speed can affect large bases rather quickly, same with faster L2 Cache. Their entire blog series[1] covers a large part of how they did this. but for a game written mostly in LUA they sure did a good job on it. 1: https://www.factorio.com/blog/post/fff-204 https://www.factorio.com/blog/post/fff-204
- DizzyDoo 3y ago
  Yes, the Factorio devs had an approach where they optimised everything happening in the game in the original singlethreaded environment, before moving onto multithreaded support. That's where the game is now, and as far as I understand it the multithreading occurs on each independent set of conveyor belts or belt lanes, and there's some info on that in this blog post[0] for anyone interested. [0] - https://www.factorio.com/blog/post/fff-364 https://www.factorio.com/blog/post/fff-364
- rcxdude 3y ago
  It makes sense that a simulation game like factorio would be memory bandwidth limited: each tick it needs to update the state of a large number of entities using relatively simple operations. The main trick to making it fast is reducing that amount of data you need to update each tick and arranging the data in memory so you can load it fast (i.e. predictably and sequentially so the prefetcher can do is job) and only need to load and modify it once each tick (at least in terms of loading and eviction from cache). The complexity is in how best to do that, especially both at once. For example, in the blog post they have linked lists for active entities. This makes sense from the point of view of not loading data you don't need to process, but it limits how fast you can load data because you can only prefetch one item ahead (compared to an array where you can prefetch as far ahead as your buffers will allow)

dejvid_ 3y ago

It is not hard if you use proper libraries. So Take a look into Scala ZIO library, you can solve any concurrency problem with an ease. With the proper toolset which ZIO provides, you can tackle any consurrency problem in typesafe way, and mostly correct if it compiles :)

bullen 3y ago

Only 2 ways into parallelism: - Arrays of 64 byte Structures with C. (client) - Java. (server) Everything else is not atomic.

CyberDildonics 3y ago
This makes no sense. - Arrays of 64 byte Structures with C. (client) All you need for parallelism is to spawn threads and give each thread a range of an array to work on. You don't need each element to be atomic because you aren't synchronizing on each element. What makes you think you need specific data and a specific language? - Java. (server) This makes even less sense. A language doesn't matter and how it's used doesn't matter. Where did you get this idea? Can you link something? Everything else is not atomic. I think you don't understand what parallelism means. Read about openMP, it is very simple.

cmrdporcupine 3y ago

Concurrent state management is hard, and I remain disappointed that software transactional memory -- and pushing a DB-style approach to non-DB workloads generally -- hasn't caught on. I think most "application" type programs would benefit from being able to manage state in terms of higher level transactional operations and let their runtime take care of serializing and avoiding deadlock and race conditions. Developers in those spaces have come to rely on garbage collection in their runtimes, I see no reason why they couldn't come to also rely on a fully isolated MVCC transaction model (and only get access to non-transactional memory in exceptional circumstances). Bonus points if said transactions tie back to the persistent RDBMS transaction as well. There are too many minefields in manual lock management and the tools remain fairly low level. Ownership management in languages like Rust helps, following a discipline like an actor/CSP approach helps, etc. but in the end if there's shared state and there's parallel work, there's potential for trouble.

twoodfin 3y ago
You might be interested in Joe Duffy’s retrospective on Microsoft’s failed experiment to integrate STM into .NET: https://joeduffyblog.com/2010/01/03/a-brief-retrospective-on-transactional-memory/ https://joeduffyblog.com/2010/01/03/a-brief-retrospective-on...
- cmrdporcupine 3y ago
  Thanks, skimmed a bit of the first half but will get into it more after my work day.
  - cmrdporcupine 3y ago
    So, going through this a bit more on lunch break; I think the root of some of the disillusionment faced here -- and probably the lack of success in STM at this level generally -- is that they tried to do too much. I don't necessarily want the whole memory model of the runtime or VM to offer transactions necessarily. What I think is a good idea is to offer an overall framework -- within which higher level applications can be written -- that brings transactional semantics with it. Basically a set of collections and data transformation and communications and process coordination libraries that work in harmony with an underlying MVCC storage layer -- rather than baking a transactional atomic keyword down to the syntactical level of the language or the memory model of the VM/runtime. Put another way: I wouldn't necessarily give users the STM facilities. I would use lower level STM facilities to construct a higher level toolkit, and only expose that. Basically an RDBMS in-process -- without the SQL language boundary -- to be frank. Yes, users could escape it easily, and start doing inconsistent things. But that's on them, same as any other framework. Provide the pattern and tools in a nice coherent box and don't try to take over the whole world.

z3t4 3y ago

The symtoms that lead up to me learning about the need for locks in multi threaded servers was painful. That the state could change from one line of code to the next line, how could it change when I just set it a micro second ago? Because the user clicked the button twice and the call was executed simultaneously but in different threads because my new server had many cores. Then I learned about async programming, but I no longer remember what was so difficult about it. Just that it took about a year and I basically had to rewire how my brain visualize program execution.

mrkeen 3y ago
> the state could change from one line of code to the next line > I no longer remember what was so difficult about it You or (your libraries) probably stopped mutating things. No mutation means you can rely on values you used several lines ago. This is the perennial HN discussion whenever the word 'functional' comes up. "But x=x+1 is simple to teach to beginners" is the rallying cry. Well, this is why not. Also, > the need for locks This goes away if you don't mutate.
- gpderetta 3y ago
  yet physical hardware has a finite amount of memory, so at some point you either stop your program of you have to modify a cell you already touched.
  - tialaramex 3y ago
    Mutation isn't confusing. On its own. Multiple references isn't confusing. On its own. The observation, which I don't think I saw being made twenty years ago (I could be wrong) is that you shouldn't mix these two things. No multiple references with mutation. In theory you can safely do so in serial programs if you were careful enough, in practice you won't be careful enough and we should write fewer serial programs than we do, so why not reject this outright. Rust is one particular (and notably successful) attempt to make a programming language about this big idea, but it's the idea in Val and several other newer languages. There are a lot of unknowns about the best way to approach this, but "Just pretend it's not important" is not a correct answer.

DayDollar 3y ago

Ah, the old debate and approach. Centralize the control, Decentralize problem handling, centralize the knowledge needed for untangling parallelism, realize you just created a centralized authority, undoing the parallelism. Then there is the physics engine view to all things. Data is just sand washing against the shoreline of parallel computation instances and interaction, is just sticking these dataparticles together, taking them out of the general flow to be interacted on in unison, carrying the resolution authority within them as long as they are "clumbed" together. Data is just particles, the programs interacting on it are just a limited number of program cells, traversing it and interaction clumps it together, making the processing of it slower, but also centralized to computation node. A centralized node, processing a huge clump of interacting data, even throws a sort of "relativity" shadow, as other, smaller, non interacting data, is processed faster and leaping ahead in the interactions.

sproketboy 3y ago

[dead]

atum47 3y ago

I took the parallel programming class back in college. Even though we implemented several good examples using parallelism like matrix multiplications and different methods of achieving it using the GPU or distributed computers, the main goal of the class was to analyze and see what problems could be processed in parallel and also how to divide the problem in small chunks in order to do so. It was a lot of fun.

giovannibonetti 3y ago

Functional programming can be a great way to handle parallel programming in a sane way. See the Futhark language [1], for example, that accepts high-level constructs like map and reduce, then converts them to the appropriate machine code, either on the CPU or the GPU. [1] https://futhark-lang.org/ https://futhark-lang.org/

uguuo_o 3y ago

On scientific computing (computational fluid dynamics, computational electromagnetics, etc.), parallel programing is a must. Most of the algorithms are not embarrassingly parallel, and need a significant amount of communication between threads during runtime. We mostly use one of the many MPI [0] libraries available for desktop and high-performance computing machines. Using these programming paradigms is difficult but tend to result in fantastic scalability for all types of engineering problems. [0] https://en.m.wikipedia.org/wiki/Message_Passing_Interface https://en.m.wikipedia.org/wiki/Message_Passing_Interface

OscarCunningham 3y ago
So this might be a naive question, but is it literally that you're simulating a fluid in parallel by having each thread simulate a portion of the space? And then the message passing between threads is the data about the fluid on the boundary?
- elil17 3y ago
  Computational fluid dynamics is actually a problem where parallelization doesn't get you much. It is primarily limited by memory bandwidth.
  - sapiogram 3y ago
    It's very, very hard to be memory bandwidth bottlenecked if your program is not parallelized, even on consumer hardware. A 5Ghz cpu core with dual-channel DDR5 might get 75 GB/s of memory bandwidth. That's 15 bytes per clock cycle. Prosumer hardware? Maybe 60 bytes per clock cycle. No way one cpu core can keep up with that.
  - ascar 3y ago
    Memory bandwidth can be increased by parallelization though. E.g. MPI (Message Passing Interface) is one of the major libraries in parallel programming and supercomputing and deals with parallelization across multiple machines.
  - 3y ago

namirez 3y ago

Parallel programming is not hard; state management is hard. And for problems that are not embarrassingly parallel, unfortunately there is no silver bullet.

ascar 3y ago

I see a lot of confusion between parallel programming [1] and concurrent programming [2] in the comments here. The former and what this book is about deals with the problem of parallelizaing a single sequential program. There usually is strong interaction or dependencies between elements and progress needs synchronization. E.g. timestep iterations in real-time simulations that need synchronization with data communication after each timestep. These simulation also tend to get way to big to be run on a single machine, lest a single thread, and get scaled up to millions of cores/threads in supercomputers. Concurrent programming is what most developers working with the internet are more familiar with. You have mostly independent tasks that you want to run concurrently. "A concurrent system is one where a computation can advance without waiting for all other computations to complete." [2] E.g. nginx serving thousands of user requests at the same time. The problem domains have a lot of overlap on the basics (e.g. threading), however the focus is very different. Things like synchronization (mutex, barriers), cache locality and memory bandwith & latency play a central role in parallel programming, while concurrent programming focuses more on the engineering challenge of distributing independent tasks across multiple threads or machines. [1] https://en.wikipedia.org/wiki/Parallel_computing https://en.wikipedia.org/wiki/Parallel_computing [2] https://en.wikipedia.org/wiki/Concurrent_computing https://en.wikipedia.org/wiki/Concurrent_computing

vivegi 3y ago
The book covers it in Appendix A.6 (p 424) in the v2023.06.11a PDF file. > A.6 What is the Difference Between “Concurrent” and “Parallel”? > From a classic computing perspective, “concurrent” and “parallel” are clearly synonyms. However, this has not stopped many people from drawing distinctions between the two, and it turns out that these distinctions can be understood from a couple of different perspectives. > The first perspective treats “parallel” as an abbreviation for “data parallel”, and treats “concurrent” as pretty much everything else. From this perspective, in parallel computing, each partition of the overall problem can proceed completely independently, with no communication with other partitions. In this case, little or no coordination among partitions is required. In contrast, concurrent computing might well have tight interdependencies, in the form of contended locks, transactions, or other synchronization mechanisms. > This of course begs the question of why such a distinction matters, which brings us to the second perspective, that of the underlying scheduler. Schedulers come in a wide range of complexities and capabilities, and as a rough rule of thumb, the more tightly and irregularly a set oparallel processes communicate, the higher the level of sophistication required from the scheduler. As such, parallel computing’s avoidance of interdependencies means that parallel-computing programs run well on the least-capable schedulers. In fact, a pure parallel-computing program can run successfully after being arbitrarily subdivided and interleaved onto a uniprocessor. In contrast, concurrent computing programs might well require extreme subtlety on the part of the scheduler.

nayuki 3y ago

Having seen this years ago, my favorite part is still the comic that says "do I out things of Look! can order." in section 15.1.1 "Why Hardware Misordering?".

EVa5I7bHFq9mnYK 3y ago

It's not, if you are ready to copy your data around a lot, aka functional programming.

imtringued 3y ago

The biggest problem with parallel programming are the fixed communications costs. Threads are expensive to launch and stop. This then leads to thread pooling which is not a bad idea but then you have to make sure that nothing blocks the thread pool. Java is going to fix this problem with virtual threads. Even if threads are cheap, you still have to decide when to parallelize something. If the section is short enough, splitting up the work will make your program slower because you have to wait for the new thread to be scheduled and then for the launching thread to be scheduled. These are just the problems to get you started. They are not big barriers but they are big enough to make it not be the default. The next problem is dynamic runtime behaviour. A parallel program can exhibit far more weird behaviours due to the nature of interleaved execution. This means that you will want a strong ownership model for your data and so far only Rust does it competently. Instanced locks are difficult to get right. Static locks are almost trivial but only if you can guarantee that your critical section never calls code that invokes the same lock. Recursive locks are a bad idea but not using them means you need to have two sets of methods. One is the public synchronized method that library users call and the other is the private unsynchronized method that actually does most of the work. It's very ugly to work with locks. The other problem is that a lot of problems are genuinely difficult to parallelize. It is better to parallelize hierarchically where each hierarchy is still single threaded. This way you can maintain the illusion of mostly single threaded code. The alternative often requires a bespoke architecture. There are hardly any generalized solutions. You need to be an expert at parallel programming.

spacechild1 3y ago

I have almost finished the book (to be honest, I have skipped the "Validation" chapter) and I found it quite interesting. In particular I liked that it also covered more "exotic" topics such as sequence locks, hazard pointers and RCU. However, in general, I found it a bit too much focussed on Linux kernel code. The code examples are full of kernel code macros, such as READ_ONCE and WRITE_ONCE, instead of C11/C++11 atomics. In the end, I appreciated it because it gave me a new perspective, but I'm not sure if this helpful for people who are not already familiar with parallel programming...

lincpa 3y ago

[dead]