5 ms·

> equivalence offers little analytical and practical benefit I disagree, but that's irrelevant. Considering things equivalent is default, if their properties

> equivalence offers little analytical and practical benefit I disagree, but that's irrelevant. Considering things equivalent is default, if their properties are the same - in case of concurrency/parallelism, I think I have clearly demonstrated how every concurrent algorithm is parallel, and vice versa. If you're claiming that a distinction should be drawn, the burden of proof is on you. What is the fundamental difference between concurrency and parallelism?

eternalban 4y ago
> I think I have clearly demonstrated how every concurrent algorithm is parallel, and vice versa. You have not "clearly demonstrated" anything. You are merely pointing out a weak truism that holds in parts, which is the banal truth that all algorithms feature non-contended segments for a given executing thread. The fact that the distinction between these two types is not 'crisp' and precise does not mean a meaningful distinction does not exist. If your position was valid, we would call e.g. a multi-producer multi-consumer queue a "parallel" data structure but we certainly don't. Sure, the producers are all producing in parallel before contending to enqueue, and the consumers do their thing in parallel after they contend to dequeue. That parallelism is a banal fact in this case, given that what we really need to address are the concurrent attempts to update the queue. Conversely, applying a filter to an image by tiling and performing the application in parallel has some minor contention bits but the main business is doing something in parallel.
- paskozdilar 4y ago
  Aside from the appeal to authority ("we" say X therefore X is right), you bring up some good points (although in a fairly unpleasant tone which I don't appreciate in the slightest), you still haven't answered my question - what is the fundamental difference between concurrency and parallelism?
  - eternalban 4y ago
    Sorry about the tone!(?)
    - paskozdilar 4y ago
      I apologize for my defensiveness. I tend to get defensive and emotional when under stress. I don't like that about myself.
  - nemothekid 4y ago
    As I understand it, parallelism describes tasks making progress simultaneously, while concurrency describes tasks that can be broken into smaller, independent tasks (that could still be executed serially). For example, I could have map reduce problem executing sequentially on a single core CPU. Each map function would operate on the data sequentially, then the reduce step. The process is concurrent because I could work on any map step in any order, or even stop midway and work on another task set. Once all processes are complete I have my output. But since only one task was ever making progress at a time the computation wasn't parallel, it only becomes parallel once I add another execution unit. Consider multitasking on early operating systems; a user may have several programs running concurrently, but early CPUs could only do one thing a time, hence there was no parallelism. Due to this architecture there are situations where there are all execution units are blocked and only one of them can make progress (e.g. reading from a spinning disk); making CPU synchronization primitives a "poor fit" for GPUs. In other words, while any parallel algorithm, by definition, is a (trivially) concurrent algorithm, the inverse is not true, and is still a harder problem.
    - dragontamer 4y ago
      The "elevator algorithm" makes hard drives (and tapes) more-and-more efficient the more work is queued up for them. Lets say you have 10 floors on an elevator (floor#0 through floor#9). You can imagine that I/O requests are handled by the elevator moving to a specific floor, and then reading/writing to that floor, and then moving to another floor. Physically, this correlates to the positions a hard-drive arm is positioned on various sectors of a hard drive: you can think of floor#0 as the "inner-ring" of the hard drive, and floor#1000 as the "outer-ring" of the hard drive. The further away the floors are, the longer it takes for the arm to physically move across the hard drive. ---------------------- Now lets say there's a bunch of requests that have come in. Read Floor#5, write Floor#9, read Floor#1, write Floor#2, write Floor#7. When executing these 5 requests in order (5->9->1->2->7). This is clearly inefficient. If all 5 requests were known at the same time, the hard drive can instead reorder the requests into 1->2->5->7->9, which moves the hard drive arm a much shorter distance. This is the innate benefits of "concurrency" of the 1980s era computers. You wanted multiple-threads to buffer-up as many requests to the hard drive as possible. The more-and-more "load" you give to the hard drive arm, the more overall efficiency is achieved, because the hard drive controller can optimize those read/write requests and minimize the movement of the arm. (Ex: rearranging the "floor visit pattern" of the elevator algorithm to minimize movements of the hard-drive control arms) ---------------------- So we can see that "concurrency", or "multithreaded" programming was about maximizing I/O performance, instead of CPU-performance. From this perspective, highly CPU-inefficient structures, such as Mutexes, are not really a penalty. The CPU is so much faster than the hard drive that it doesn't matter. Mutexes, task-switching, etc. etc. Spend all the CPU cycles you want on this, the CPU is obviously not the bottleneck here. In contrast, today is 2020. We have solid state drives that are much much faster (still benefiting from parallel requests though!!), and the CPU itself can be the bottleneck. Not only do we want to fill up our I/O systems with a huge number of parallel requests (modern SSDs can perform far, far more requests with high-queue depths), you also want to take advantage of multi-CPU clusters through parallel programming techniques. ------------- As such, my particular usage of the words are: * Concurrency are the sets of techniques to maximize I/O usage, even at high costs to CPU-time / CPU-power. (Mutexes, semaphores, pthreads, task-switching). If you have a technique that can "invent new I/O requests out of nothingness", that's ideal in the concurrency mindset. (Agents, golang-threads, etc. etc.) * Parallelism are the sets of techniques to maximize CPU-usage, and therefore must be as low cost to CPU-power as possible. (Thread barriers, SIMD processing, spinlocks, thread-pools, thread-affinity, NUMA processing). All of those goland-threads that generate more I/O requests are worthless in the scope of CPU-limited "parallel compute". But they're extremely helpful in I/O limited "concurrency". The more I/O requests that hit the controller simultaneously, the better and better those I/O devices perform. This is true for all forms of I/O, be it a GPU, Network adapter, hard drive, tape drive, or solid state drive.
  - eternalban 4y ago
    Took a short walk and was thinking about this. This is my take on the matter. The most fundamental difference between parallel and concurrent processing is that for the latter we need not have the same number of physical actors (threads) as the required logical actors [for meaningful/practical gains]. In other words, we can (and do, as in 'green threads') emulate the synchronized activity of nL logical actors with nR real physical actors, where 1 <= nR =< nL. Of course we can also emulate nL parallel activities with only 1 real actor but it is of no practical value. So Amdahl's Law is very much about parallelism but it has absolutely nothing to do with 'concurrency'. [Whereas Queueing Theory is of relevance to analyzing concurrent algorithms.] This is because in parallel algorithms, the concurrent actors are all doing the same thing (see SIMD), whereas in concurrent algorithms, the concurrent actors may be doing entirely different things (see typical GUI component of an OS). This fact also informs why arrays and array processing languages are such good fits for parallel programming. Then, it seems to me that parallel processing is orchestrated (deterministic) in nature, whereas concurrent processing is all about synchronized pseudo-chaos. [So parallelism is a simple, well ordered, type of concurrency. Think of it as symmetric and synchronized concurrency.] Finally, the 'fuzzy' distinguishing matter is a sense of the degree of contention for mutating ops on registers. A concurrent algorithm is pretty much all about dealing with that: highly contended R/W registers. p.s. so more examples of making this distinction: fork-join is about parallelism. green-threads/fibers are about concurrency. continuations are also about concurrency. Go is a language tuned for concurrency. Chapel is one tuned for parallelism. p.s.s. things can be "embarrassingly parallel", but dealing effectively with concurrency is never something to be embarrassed about. /g https://en.wikipedia.org/wiki/Embarrassingly_parallel https://en.wikipedia.org/wiki/Embarrassingly_parallel
    - paskozdilar 4y ago
      I see. I think I understand better the motivation behind your initial comment that I've criticized. Thanks for taking time to explain.
      - eternalban 4y ago
        NP. Actually it was good of you to insist on a clear definition. I would say applicability of Amdhal’s Law is a decisive litmus test.

eternalban 4y ago

> I think I have clearly demonstrated how every concurrent algorithm is parallel, and vice versa. You have not "clearly demonstrated" anything. You are merely pointing out a weak truism that holds in parts, which is the banal truth that all algorithms feature non-contended segments for a given executing thread. The fact that the distinction between these two types is not 'crisp' and precise does not mean a meaningful distinction does not exist. If your position was valid, we would call e.g. a multi-producer multi-consumer queue a "parallel" data structure but we certainly don't. Sure, the producers are all producing in parallel before contending to enqueue, and the consumers do their thing in parallel after they contend to dequeue. That parallelism is a banal fact in this case, given that what we really need to address are the concurrent attempts to update the queue. Conversely, applying a filter to an image by tiling and performing the application in parallel has some minor contention bits but the main business is doing something in parallel.

paskozdilar 4y ago
Aside from the appeal to authority ("we" say X therefore X is right), you bring up some good points (although in a fairly unpleasant tone which I don't appreciate in the slightest), you still haven't answered my question - what is the fundamental difference between concurrency and parallelism?
- eternalban 4y ago
  Sorry about the tone!(?)
  - paskozdilar 4y ago
    I apologize for my defensiveness. I tend to get defensive and emotional when under stress. I don't like that about myself.
- nemothekid 4y ago
  As I understand it, parallelism describes tasks making progress simultaneously, while concurrency describes tasks that can be broken into smaller, independent tasks (that could still be executed serially). For example, I could have map reduce problem executing sequentially on a single core CPU. Each map function would operate on the data sequentially, then the reduce step. The process is concurrent because I could work on any map step in any order, or even stop midway and work on another task set. Once all processes are complete I have my output. But since only one task was ever making progress at a time the computation wasn't parallel, it only becomes parallel once I add another execution unit. Consider multitasking on early operating systems; a user may have several programs running concurrently, but early CPUs could only do one thing a time, hence there was no parallelism. Due to this architecture there are situations where there are all execution units are blocked and only one of them can make progress (e.g. reading from a spinning disk); making CPU synchronization primitives a "poor fit" for GPUs. In other words, while any parallel algorithm, by definition, is a (trivially) concurrent algorithm, the inverse is not true, and is still a harder problem.
  - dragontamer 4y ago
    The "elevator algorithm" makes hard drives (and tapes) more-and-more efficient the more work is queued up for them. Lets say you have 10 floors on an elevator (floor#0 through floor#9). You can imagine that I/O requests are handled by the elevator moving to a specific floor, and then reading/writing to that floor, and then moving to another floor. Physically, this correlates to the positions a hard-drive arm is positioned on various sectors of a hard drive: you can think of floor#0 as the "inner-ring" of the hard drive, and floor#1000 as the "outer-ring" of the hard drive. The further away the floors are, the longer it takes for the arm to physically move across the hard drive. ---------------------- Now lets say there's a bunch of requests that have come in. Read Floor#5, write Floor#9, read Floor#1, write Floor#2, write Floor#7. When executing these 5 requests in order (5->9->1->2->7). This is clearly inefficient. If all 5 requests were known at the same time, the hard drive can instead reorder the requests into 1->2->5->7->9, which moves the hard drive arm a much shorter distance. This is the innate benefits of "concurrency" of the 1980s era computers. You wanted multiple-threads to buffer-up as many requests to the hard drive as possible. The more-and-more "load" you give to the hard drive arm, the more overall efficiency is achieved, because the hard drive controller can optimize those read/write requests and minimize the movement of the arm. (Ex: rearranging the "floor visit pattern" of the elevator algorithm to minimize movements of the hard-drive control arms) ---------------------- So we can see that "concurrency", or "multithreaded" programming was about maximizing I/O performance, instead of CPU-performance. From this perspective, highly CPU-inefficient structures, such as Mutexes, are not really a penalty. The CPU is so much faster than the hard drive that it doesn't matter. Mutexes, task-switching, etc. etc. Spend all the CPU cycles you want on this, the CPU is obviously not the bottleneck here. In contrast, today is 2020. We have solid state drives that are much much faster (still benefiting from parallel requests though!!), and the CPU itself can be the bottleneck. Not only do we want to fill up our I/O systems with a huge number of parallel requests (modern SSDs can perform far, far more requests with high-queue depths), you also want to take advantage of multi-CPU clusters through parallel programming techniques. ------------- As such, my particular usage of the words are: * Concurrency are the sets of techniques to maximize I/O usage, even at high costs to CPU-time / CPU-power. (Mutexes, semaphores, pthreads, task-switching). If you have a technique that can "invent new I/O requests out of nothingness", that's ideal in the concurrency mindset. (Agents, golang-threads, etc. etc.) * Parallelism are the sets of techniques to maximize CPU-usage, and therefore must be as low cost to CPU-power as possible. (Thread barriers, SIMD processing, spinlocks, thread-pools, thread-affinity, NUMA processing). All of those goland-threads that generate more I/O requests are worthless in the scope of CPU-limited "parallel compute". But they're extremely helpful in I/O limited "concurrency". The more I/O requests that hit the controller simultaneously, the better and better those I/O devices perform. This is true for all forms of I/O, be it a GPU, Network adapter, hard drive, tape drive, or solid state drive.
- eternalban 4y ago
  Took a short walk and was thinking about this. This is my take on the matter. The most fundamental difference between parallel and concurrent processing is that for the latter we need not have the same number of physical actors (threads) as the required logical actors [for meaningful/practical gains]. In other words, we can (and do, as in 'green threads') emulate the synchronized activity of nL logical actors with nR real physical actors, where 1 <= nR =< nL. Of course we can also emulate nL parallel activities with only 1 real actor but it is of no practical value. So Amdahl's Law is very much about parallelism but it has absolutely nothing to do with 'concurrency'. [Whereas Queueing Theory is of relevance to analyzing concurrent algorithms.] This is because in parallel algorithms, the concurrent actors are all doing the same thing (see SIMD), whereas in concurrent algorithms, the concurrent actors may be doing entirely different things (see typical GUI component of an OS). This fact also informs why arrays and array processing languages are such good fits for parallel programming. Then, it seems to me that parallel processing is orchestrated (deterministic) in nature, whereas concurrent processing is all about synchronized pseudo-chaos. [So parallelism is a simple, well ordered, type of concurrency. Think of it as symmetric and synchronized concurrency.] Finally, the 'fuzzy' distinguishing matter is a sense of the degree of contention for mutating ops on registers. A concurrent algorithm is pretty much all about dealing with that: highly contended R/W registers. p.s. so more examples of making this distinction: fork-join is about parallelism. green-threads/fibers are about concurrency. continuations are also about concurrency. Go is a language tuned for concurrency. Chapel is one tuned for parallelism. p.s.s. things can be "embarrassingly parallel", but dealing effectively with concurrency is never something to be embarrassed about. /g https://en.wikipedia.org/wiki/Embarrassingly_parallel https://en.wikipedia.org/wiki/Embarrassingly_parallel
  - paskozdilar 4y ago
    I see. I think I understand better the motivation behind your initial comment that I've criticized. Thanks for taking time to explain.
    - eternalban 4y ago
      NP. Actually it was good of you to insist on a clear definition. I would say applicability of Amdhal’s Law is a decisive litmus test.