Comment by ascar
3 years 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.
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.
Well, funnily enough this does read in contrast to the definitions used in Wikipedia, which are the ones I am also familiar with (I also do teach a class called "Parallel Programming" to graduates).
I do think the differentation make sense from a perspective of problem classes, as also evident from the comments here. Running independent problems in parallel to better utilize hardware ressources is very different from running problems in parallel in timesteps that have strong dependencies in regards to progress of the overall computation. And that's not a problem of the scheduler, but a much more general concept.
It doesn't sound to me like the author has the whole web service parallelism/concurrency in mind that is very apparent in the comments here.
The definition found in Wikipedia, like many contentious subjects in programming, was written by people with strong political agenda and very little respect to the matter being described.
This applies to all sorts of ambiguous terms used very generously in the witchcraft of "applied computer science". Other examples include "object-oriented programming", "statically- or dynamically-typed language", "interpreted language", "dependency inversion", a bunch of "software patterns" and more. All this terminology is meaningless because there's never a way to tell if a language is object-oriented or not, if it's statically-typed or not and so on. Parallel vs concurrent is just one of those things where emotional attachment won over any attempt at rational thinking.
4 replies →
that description is... not accurate
concurrent is about logical independence, parallel is about physical independence
I don't know who invented this nonsense distinction. First time I was introduced to this idea of "concurrent programming" being a separate thing when Go was released. So, I associate this nonsense with Go, but it could have happened earlier, I simply never heard about it before then.
Anyways. The way I see it used today, it's applied to language runtimes incapable or severely crippled when it comes to parallel / concurrent execution. Eg. Python, JavaScript etc. In such environments programmers are offered a mechanism that has many downsides of parallel / concurrent programming (eg. unpredictable order of execution) without the benefits of parallel / concurrent programming (ie. nothing actually happens at the same time, or only sleep is possible at the same time etc.)
I feel like this distinction, while a nonsense idea at its core, became so popular due to the popularity of language runtimes with disabilities and their users needing to validate their worth by adding features to their languages their runtimes are inherently incapable of implementing.
Similar situation happened with ML-style types. Python, for example, works very poorly with this add-on, but the desire to match features of other languages led Python developers to add those types anyways. Similarly, TypeScript and a bunch of similar languages, especially in Web.
How is this nonsense or anything to do with "language runtimes with disabilities"? An OS running on a single core processor cannot be parallel but it may be concurrent: it can never physically do two things at the same time, but it might be able to logically interleave different tasks.
Parallelism is a physical thing, concurrency is a logical thing.
Parallelism is a physical thing, concurrency is a logical thing.
Fundamentally the difficulty is all about synchronization. People can try to split hairs and say there are two terms for two different things but ultimately it doesn't matter because the underlying problem is the same.
7 replies →
You have just repeated the nonsense I was talking about.
The claim you repeat is meaningless. A program is either parallel / concurrent or not. The situation you describe (when there's a single processor core) isn't parallel or concurrent. In some sense, it emulates concurrent / parallel execution because it imitates the unpredictable ordering of code execution, which sure has its uses... but the whole point of dealing with this unpredictable ordering is that we actually want parallelism / concurrency. The emulation on its own is worthless.
9 replies →
>> don't know who invented this nonsense distinction ...
It not nonsense. In C or C++ lots of code can be made parallel using OpenMP and inserting some #pragma statements above for loops. This does not work for things like running a UI in one thread and some other work in another thread, perhaps displaying results as they are found. These are quite different types of parallelism.
OpenMP versus std::thread/pthread/etc isn't this distinction. Both are thread-based parallelism; that OpenMP implementations do so cleverly via a threadpool approach is secondary. Any loop you can write using OpenMP you could dispatch manually via an explicit thread-based approach, and long-running parallel task you'd normally implement via std::async/std::future/std::thread could be dispatched via OpenMP. There are good conventions about what kinds of operations are better expressed via one or the other mechanism, but they are effectively equivalent in capability.
What does this have to do with anything?
I mean, great... you discovered a somewhat useful library: OpenMP... so what? How does this factoid affect the validity of the definition of code parallelism?
I think it's nonsense to invent new terminology for this tiny minor difference in how you use threads and whether you wait on results or you don't wait.
10 replies →
I'm not sure I can identify when it started, but these were already the concepts commonly in use when I did my CS undergraduate work in the early 90s. I.e. it was in textbooks and course titles as established jargon.
Concurrency was the kind of thing worried about in OS design or Unix programming styles whether on a time-sharing system or some small scale multi-processing system. Coordination of heterogeneous sequential programs on some shared resources.
Parallelism was the topic of high-performance computing with combined use of many hardware resources to accelerate a single algorithm.
Of course these are simplifying abstractions, and real systems can get into the murky gray area that is both concurrent and parallel.
Rob Pike has a discussion on the distinctions between parallelism and concurrency. Concurrency is closely related to co-routines which are a distinct invention from threads/processes which are more related to parallelism.
Just because you didn't know about the concept doesn't mean the distinction is nonsense. I think they are similar but not the same, exactly for the reasons laid out in the comment you are replying too. Just because you hate the languages that support concurrent programming doesn't mean concurrent programming is meaningless. Any language using async/await (basically all of them these days) support concurrent programming, including languages such as Swift and C# which are nothing like Python or JavaScript.
> In such environments programmers are offered a mechanism that has many downsides of parallel / concurrent programming (eg. unpredictable order of execution) without the benefits of parallel / concurrent programming (ie. nothing actually happens at the same time, or only sleep is possible at the same time etc.)
From the developer's perspective it's a massive upside to not have to manage low-level details and just define how the event loop will call their code.
Any modern web browser has plenty of parallel execution behind the scenes, but the developer (and user) will just see concurrency which is much simpler to reason about. The order of execution doesn't matter if the things being executed aren't dependent. What matters more is that there's only one thread to think about. If they are dependent they shouldn't have been parallelized in the first place, so they're not.
What does this have to do with low or whatever other level?
[dead]
Both I (and apparently the author of TFA) disagree with your definition of parallel programming. TFA gives an example of "embarrassingly parallel" programs as one way to make parallel programming simple.
The distinction I learned was: any time you have multiple logical threads of execution you have concurrency, any time you have multiple computations happening simultaneously, you have parallelism.
Multithreaded programming on a single core computer is concurrent, but not parallel. Vector processing is parallel, but not concurrent.
> The distinction I learned was: any time you have multiple logical threads of execution you have concurrency, any time you have multiple computations happening simultaneously, you have parallelism.
I like this distinction as it also splits the different problem domains quite well. And I don't think it contradicts my definition as much as you might think.
When you have an embarrassingly parallel program you do not have to deal with the problems that come from data dependencies and synchronization of your simultaenously running compuations on different threads/machines. You do not really have to think about your computation running in parallel, but just about how to put them into different execution environments to run them concurrently. So you end up doing "concurrent programming".
When you do not have an embarrassingly parallel program, you still use the base concepts of running something concurrently (e.g. threads), but now your main focus shifts on how the multiple compuations can happen simultaneously. Now you end up doing "parallel programming" or parallel computation.
In the end, the terminolgy here is less than ideal. My main point was that some kind of distinction matters as TFA clearly discusses different topics from what many people think about from a web dev perspective (e.g. async, futures, etc.)
Vector processing is not parallelism, but rather non-scalar. Specifically, it's a single operation that is able to do work on multiple data items, rather than parallel processors doing work at the same time.
It is data parallel. In the same way, I would label super-scalar CPUs machines that automatically perform parallel processing on a linear stream of instructions (taking advantage of so-called "instruction level parallelism."
I know we’re kind stuck with the term of art “concurrent”, and will forever have to explain the difference between the synonymous words “concurrent” and “parallel” — The Merriam Webster definition of “concurrent” uses the word “parallel”, for example.
Wouldn’t it be nice if we could come up with a better word for this that doesn’t literally overlap with ‘parallel’ and doesn’t need to deviate so far from it’s dictionary definition?
Personally I think of JavaScript as ‘asynchronous’, and I know this as a term of art means a programming model, but it’s a lot easier to see that async can be done with a single thread and isn’t necessarily parallel, right?
Parallel programming is simply a type of concurrent programming. Concurrent means that two tasks can both progress in a given duration. On a single core computer every thread runs concurrently. Parallel expands on concurrency to mean that two concurrent tasks can also run at the exact same time. On a multi-core computer threads can run in parallel. In many cases concurrent programming and parallel programming have little to no difference, and you program with the assumption that every task can run in parallel (for example, whenever you use async/await or the threadpool).