6 ms·

Any concurrent algorithm, by definition, has branches of computation that are independent of each other, and is thus parallel. Any parallel algorithm, by defin

Any concurrent algorithm, by definition, has branches of computation that are independent of each other, and is thus parallel. Any parallel algorithm, by definition, is a (trivially) concurrent algorithm.

eternalban 4y ago
Yet we do distinguish the two types by distinct names (and algorithmic and data structure treatment) for a reason, precisely because your proposed equivalence offers little analytical and practical benefit.
- paskozdilar 4y ago
  > 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.
        4y ago
dwohnitmok 4y ago
The usual way that the difference is presented is that concurrency is a semantic property of your program independent of its runtime performance while parallelism is a runtime property of your program independent of its semantics. In particular, a basic property of concurrent programs is non-determinism. It must be always be available (can't be offline while serving one response) to service multiple requests in non-deterministic order (and often will give responses in a non-deterministic order as well even for a deterministic order of requests, or at least leave such an option available in its semantics). There are almost always other invariants that must be preserved (which is what is means for a concurrent program to be correct), but generally the invariants are lax enough that a concurrent program does not make guarantees about being deterministic. This has no direct relationship with its runtime implementation. For example you could implement a concurrent program in a single-threaded fashion just by interleaving and jumping back and forth between servicing different requests. This is effectively how something like green threads or async-await works. Parallelism on the other hand is a property of the runtime. Indeed, often parallel programs are meant to be entirely deterministic in their semantics (e.g. map-reduce-type computations), where the answer will always be the same no matter what. You just might have faster runtime. But parallelism has no inherent link to non-determinism in the way that concurrency does, because after all determinism/non-determinism is a semantic property.
- paskozdilar 4y ago
  > But parallelism has no inherent link to non-determinism in the way that concurrency does, because after all determinism/non-determinism is a semantic property. I don't know if I agree with this. If we consider the map example, the order of elements to which the function is applied must be irrelevant, so you must have non-determinism at the most fundamental level. So map is still a concurrent algorithm, isn't it? I mean, I get it, the meaning of the words is different, but I can't find any difference beyond "concurrency is a semantic property, parallelism is runtime manifestation of concurrency", which only makes them even more equivalent-ish.
  - dwohnitmok 4y ago
    > If we consider the map example, the order of elements to which the function is applied must be irrelevant, so you must have non-determinism at the most fundamental level. This is not true. Parallelism does not require non-determinism (you can e.g. require as part of your interface that your list that you are map-reducing be pre-sorted and then using that sort key the order of operations is entirely determined, you could even pin certain sort keys to certain processor cores; this is in fact how some parallel interfaces for certain parallelism libraries operate, minus the pinning). But that's only partially related to the larger point, which is that any discussion about the semantics vs the implementation of a program depends on where you draw the line between the semantics of your program and its runtime behavior. For different environments that line will be at different places. For most applications, runtime and memory usage are usually not considered part of its semantics (otherwise e.g. the notion of porting an application or refactoring wouldn't exist, since both of those would be changing the application's performance and therefore its semantics and would be essentially the same as changing the application's interface). In hard real-time environments, on the other hand, usually runtime and memory usage are considered part of its semantics, so the division between parallelism and concurrency is less relevant there. > I can't find any difference beyond "concurrency is a semantic property, parallelism is runtime manifestation of concurrency", which only makes them even more equivalent-ish. A very practical difference is that if you tell me a program is concurrent, but non-parallel I have a good idea of the outline what that program does. If you tell me that a program is parallel, but not concurrent, I also have a good idea of what that program is. And the two are very different and require very different engineering trade-offs. Examples of the former include things such as chatbots, web servers, databases (usually the latter two will also sprinkle in parallelism), etc. Examples of the latter include compilers, physics simulations, rendering engines, etc. And different tools are tuned for different use cases. If you use a tool meant for building concurrent, but not necessarily parallel programs, you'll have a bad time building a parallel, but not concurrent program with it and vice versa. E.g. Node JS is great for concurrent, but not parallel programs. You will have a horrible time building a parallel, but not concurrent program with it. None of its trade-offs will make sense. A similar case holds for something like Erlang (it at least has some support for parallelism, but it's not its strong suit). On the flip-side, Fortran is great for parallel but not concurrent programs, but you're not going find a lot of support for concurrent programs.

eternalban 4y ago

Yet we do distinguish the two types by distinct names (and algorithmic and data structure treatment) for a reason, precisely because your proposed equivalence offers little analytical and practical benefit.

paskozdilar 4y ago
> 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.
      - 4y ago

dwohnitmok 4y ago

The usual way that the difference is presented is that concurrency is a semantic property of your program independent of its runtime performance while parallelism is a runtime property of your program independent of its semantics. In particular, a basic property of concurrent programs is non-determinism. It must be always be available (can't be offline while serving one response) to service multiple requests in non-deterministic order (and often will give responses in a non-deterministic order as well even for a deterministic order of requests, or at least leave such an option available in its semantics). There are almost always other invariants that must be preserved (which is what is means for a concurrent program to be correct), but generally the invariants are lax enough that a concurrent program does not make guarantees about being deterministic. This has no direct relationship with its runtime implementation. For example you could implement a concurrent program in a single-threaded fashion just by interleaving and jumping back and forth between servicing different requests. This is effectively how something like green threads or async-await works. Parallelism on the other hand is a property of the runtime. Indeed, often parallel programs are meant to be entirely deterministic in their semantics (e.g. map-reduce-type computations), where the answer will always be the same no matter what. You just might have faster runtime. But parallelism has no inherent link to non-determinism in the way that concurrency does, because after all determinism/non-determinism is a semantic property.

paskozdilar 4y ago
> But parallelism has no inherent link to non-determinism in the way that concurrency does, because after all determinism/non-determinism is a semantic property. I don't know if I agree with this. If we consider the map example, the order of elements to which the function is applied must be irrelevant, so you must have non-determinism at the most fundamental level. So map is still a concurrent algorithm, isn't it? I mean, I get it, the meaning of the words is different, but I can't find any difference beyond "concurrency is a semantic property, parallelism is runtime manifestation of concurrency", which only makes them even more equivalent-ish.
- dwohnitmok 4y ago
  > If we consider the map example, the order of elements to which the function is applied must be irrelevant, so you must have non-determinism at the most fundamental level. This is not true. Parallelism does not require non-determinism (you can e.g. require as part of your interface that your list that you are map-reducing be pre-sorted and then using that sort key the order of operations is entirely determined, you could even pin certain sort keys to certain processor cores; this is in fact how some parallel interfaces for certain parallelism libraries operate, minus the pinning). But that's only partially related to the larger point, which is that any discussion about the semantics vs the implementation of a program depends on where you draw the line between the semantics of your program and its runtime behavior. For different environments that line will be at different places. For most applications, runtime and memory usage are usually not considered part of its semantics (otherwise e.g. the notion of porting an application or refactoring wouldn't exist, since both of those would be changing the application's performance and therefore its semantics and would be essentially the same as changing the application's interface). In hard real-time environments, on the other hand, usually runtime and memory usage are considered part of its semantics, so the division between parallelism and concurrency is less relevant there. > I can't find any difference beyond "concurrency is a semantic property, parallelism is runtime manifestation of concurrency", which only makes them even more equivalent-ish. A very practical difference is that if you tell me a program is concurrent, but non-parallel I have a good idea of the outline what that program does. If you tell me that a program is parallel, but not concurrent, I also have a good idea of what that program is. And the two are very different and require very different engineering trade-offs. Examples of the former include things such as chatbots, web servers, databases (usually the latter two will also sprinkle in parallelism), etc. Examples of the latter include compilers, physics simulations, rendering engines, etc. And different tools are tuned for different use cases. If you use a tool meant for building concurrent, but not necessarily parallel programs, you'll have a bad time building a parallel, but not concurrent program with it and vice versa. E.g. Node JS is great for concurrent, but not parallel programs. You will have a horrible time building a parallel, but not concurrent program with it. None of its trade-offs will make sense. A similar case holds for something like Erlang (it at least has some support for parallelism, but it's not its strong suit). On the flip-side, Fortran is great for parallel but not concurrent programs, but you're not going find a lot of support for concurrent programs.