4 ms·

As a computer scientist, this article is very frustrating to me. I don't understand why parallelism is not equal to concurrency. Let's look at the definitions

by javert 16y ago

As a computer scientist, this article is very frustrating to me. I don't understand why parallelism is not equal to concurrency. Let's look at the definitions given: A concurrent program is one with multiple threads of control. A parallel program, on the other hand, is one that merely runs on multiple processors Well, you have to have multiple threads of control to run on multiple processors simultaneously. And if you're running on multiple processors simultaneously, you have multiple threads of control. So what's the difference? If anybody can enlighten me on why parallelism != concurrency (a claim I've seen often), I'd appreciate it. By the way, to me, all programming languages can be concurrent because ultimately it's all just opcodes; and the word "non-determinism" is problematic anyway. So there's some context for you.

noblethrasher 16y ago
It's basically an application of the triangle inequality. In spaces where the triangle inequality holds, when two objects, A and B, are both an 'near' an object C, then they can't be arbitrarily far from each other... i.e. they eventually affect each other in some way. For the sake of discussion, I'm going to use the term 'module' instead of thread, process, function, object, etc. I think by current programming he means that you have multiple modules 'near' the same resource which means the multiple modules are near each other. Same as if you and I are both wanting to use the same physical resource, by us both being near that resource we are near each other (i.e. things that I do to the resource affects you and vice versa). By parallel programs I think he means that the multiple modules are never near the same thing and thus not ever near each other.
- javert 16y ago
  Frankly, this isn't much of an explanation. I mean, what does it mean for one thing to be "near" to another, in this case? (Answer: nothing, which is why we don't use terms like "near" in computer science.) By parallel programs I think he means that the multiple modules are never near the same thing and thus not ever near each other. I think what you're saying here is that some problems are "embarassingly parallel," in the sense that the problem can be broken into many completely independent sequential computations. But I don't think that's what the guy who wrote the article was talking about. If so, I think he would have said so.
  - noblethrasher 16y ago
    What 'near'/'far' means depends on the space you're talking about. If we're talking about the space of memory locations, then two modules are near each other if they both have access to the same storage location. You can fix this, for instance, by making things asymmetric; allow one module to have only read access and one module to only have write access. In that case, what you've done is make it so that the triangle inequality no longer obtains on the space of memory locations (at least with respect to those two modules). Edit:spelling.
    - javert 16y ago
      I mean, the triangle equality actually has a formal mathematical definition. I think you're using the wrong analogy here.
      - noblethrasher 16y ago
        It wasn't an analogy but it can be made as rigorous as you like. Let S be the set of (addressable) storage locations, let d(x, y) = x - y which is the distance between storage locations (an integer). The triangle inequality holds if d(x, y) + d(y, z) >= d(x, z). d is also clearly symmetric and reflexive; thus S and d form a metric space. Suppose module A contains a pointer to storage location x. Suppose module B contains a pointer to storage location y. Suppose A and B each contain a function which reads from z and writes to x or y respectively. If, with respect to A, d(x, z) = n < infinity, then, using pointer arithmetic, A can write to z and thus write to y. The distance between A and B is bounded (effectively it's n). On the other hand, if, with respect to A, d(x, z) = infinity (the value infinity might mean d threw an exception or something), then the distance between A and B is effectively infinite. So the concurrency/parallelism dichotomy boils down to this: Programs in which such distance between modules is finite are concurrent, programs in which the distance between modules is infinite are parallel. This example only applies to memory but it can easily apply to other kinds of relevant spaces as well.
HenryR 16y ago
Multiple threads of control aren't necessarily parallelisable. Consider a language runtime for which every thread takes the same global lock on the interpreter, and therefore prevents two threads running 'simultaneously'. You have concurrency but no parallelism. Such things happen in the real world. So you might argue that concurrency is necessary for parallelism, but it's not sufficient. Concurrency, to me, is about expanding the set of sequentially-equivalent executions of the program which are considered 'correct' according to the operational semantics of the programming language. If you just have one correct sequential execution, then there isn't any concurrency because you would have to execute sequentially to enforce the one correct ordering. For example, consider this snippet: 1. a = 1 2. b = 2 3. print a to file1 4. print b to file2 For most realistic language semantics there's no dependency between lines 3, and 4, so it's ok to execute in the following orders: 1, 2, 3, 4 1, 3, 2, 4 2, 1, 3, 4 2, 1, 4, 3 and others. There is concurrency there, and if the runtime cannot detect or leverage it quite often the processor will with out-of-order-execution and pipelining. However, the simpler snippet: 1. a = 2 2. b = a * 2 3. print a + b Doesn't have any obvious concurrency (ignoring that in this case the compiler could optimise away the assignments and additions into a single statement). 1 must happen before 2, which must happen before 3. There is only one 'correct' sequential execution, and therefore there is no obvious parallelisation achievable.
- javert 16y ago
  Consider a language runtime for which every thread takes the same global lock on the interpreter, and therefore prevents two threads running 'simultaneously'. You have concurrency but no parallelism. Well, I disagree that "concurrency" should be defined as "having multiple threads," but if that's how we want to define it... then I think you conflated the definitions half way through. Your final example, you state, has neither concurrency nor parallelism. Actually, by your definition of concurrency, it could be concurrent (put each statement in a separate thread and use locks), though I agree that it can't be parallel; it's inherently sequential.
  - ww520 16y ago
    What are your definition of concurrency and parallelism?
keveman 16y ago
I find it easier if I disassociate the English meanings of the words from really how the words are used to mean different things in computer science. To me, concurrency is only in the programmers mind. That is, a programmer writes concurrent programs with different threads of control, say, one to process the user input, one to process the network packets etc. In reality, the multiple threads of control could really be running SEQUENTIALLY. That was the case when there was only one core. Remember, pthreads predates multi-cores. Parallelism is something more concrete, it REALLY exists in the real world. A programmer could just imagine and write a sequential loop, but if the compiler deemed it to be really parallel, it could really run parts of the loop in parallel. Of course, a programmer could write a concurrent program, as in, multiple threads of control, and the system could really run it in parallel, say on different cores of a multi-core processor. So remember, concurrency is abstract, parallelism is concrete.
- javert 16y ago
  OK, I'm seeing this explanation being brought up, and it makes sense. Thank you. I wish the original poster had actually stated it this way.
  - srgseg 16y ago
    This is one of those times where not being able to see comment points really hurts my ability to read this thread. Lots of people saying slightly different things, and no way for me to know where consensus lies.
jberryman 16y ago
> Well, you have to have multiple threads of control to run on multiple processors simultaneously. And if you're running on multiple processors simultaneously, you have multiple threads of control. That depends on the semantics of your programming language. You may have a different perspective than the author, but I think his explanation is clear. Edit, To add a concrete example: I am currently working on a concurrent Haskell program that simulates a system of communicating nodes. However I am running it on my single core netbook. So we have indeterminacy and concurrent semantics without parallelism.
- javert 16y ago
  You may have a different perspective than the author, but I think his explanation is clear. Well, not being someone from the functional programming world, I don't think the explanation is clear at all. Edit, To add a concrete example: I am currently working on a concurrent Haskell program that simulates a system of communicating nodes. However I am running it on my single core netbook. So we have indeterminacy and concurrent semantics without parallelism. So you're saying that concurrency is an issue of semantics used in programming, while parallelism is talking about the underlying problem? I might be able to agree with that, but if that's the argument, that is what the author of the blog post should have stated. Anyway, please let me know if I'm understanding your point.
pnathan 16y ago
I'm also a computer scientist(y) person, and the separation of parallelism and concurrency has never been quite clear; indeed, the meanings seem artifically separated. Nonetheless - I understand concurrency to be a notion such as coroutines, and parallelism to mean, you know, things happening at the same time.
ww520 16y ago
Parallelism deals with program running at the same time; by definition, it runs on multiple CPUs. Concurrency deals with the non-deterministic order of running multiple threads of execution. Concurrent threads might or might not run on multiple CPUs. You can have multiple threads running on a single CPU system while the OS schedules one thread after another randomly. You still have concurrency and the order of execution is still non-deterministic, but you don't have parallelism. Parallelism's goal is to max out the overall throughput. It deals with partitioning data and algorithm to keep all the CPUs busy while minimizing the inter-CPU communication cost. It deals with efficient data transfer, cache coherency, data locality (out of the 10K CPUs, your neighbors can faster serve your subtask's need), and data dependency (which nodes need to go first). Parallel programs can be surprisingly deterministic. Some examples are cracking password (partition the dictionary in N ways and have N CPU hitting them), web crawling (partition the URL address space N way and have N CPU hitting them). Most of the map-reduce stuffs are parallel programs. Concurrency's main concern is to bring consistency to the non-deterministic nature of multiple threads of execution. Mutex, semaphore, event, monitor, and transactional memory are some mechanisms to bring order to the chaos.
- javert 16y ago
  So to simplify, what I'm gathering from this, and other comments, is: Concurrency occurs when program semantics allow two threads of execution to be executed in a simultaneous or interleaved manner. Parallelism occurs when two program threads actually execute simultaneously. By the way, I still have problems with the use of "non-determinism" here. Contrary to what you say, schedulers do not schedule threads randomly. But looked at from the perspectice of program semantics, that might as well be the case, which is (I think) the reason people keep bringing that up.
  - HenryR 16y ago
    As you say, from the perspective of the program any scheduling interleaving is possible. The OS can substitute a new scheduling algorithm any time it likes. Otherwise we could know that the possible set of executions is much smaller than the set of all interleavings, and could write our concurrent code based upon that assumption. Then we'd be SOL when anyone tweaked the scheduler.
DanielRibeiro 16y ago
Robert Pike[1] was recently more elonquent and concise: Concurrency is a programming model that lets you express things that are independent, as independent executions ...and parallelism is about running two things at the same time. [1] http://www.infoq.com/interviews/pike-concurrency http://www.infoq.com/interviews/pike-concurrency
philwelch 16y ago
Judging from usage, I see "parallelism" as an of algorithms problem: how do solve a problem more effectively with k processors running at the same time rather than just one? Concurrency is a system problem: how do you actually run multiple threads of execution correctly? If you're designing a programming language or OS you're probably more worried about concurrency, but if you're using that programming language or OS to solve a computational program you're more worried about parallelism.

by javert 16y ago

noblethrasher 16y ago

It's basically an application of the triangle inequality. In spaces where the triangle inequality holds, when two objects, A and B, are both an 'near' an object C, then they can't be arbitrarily far from each other... i.e. they eventually affect each other in some way. For the sake of discussion, I'm going to use the term 'module' instead of thread, process, function, object, etc. I think by current programming he means that you have multiple modules 'near' the same resource which means the multiple modules are near each other. Same as if you and I are both wanting to use the same physical resource, by us both being near that resource we are near each other (i.e. things that I do to the resource affects you and vice versa). By parallel programs I think he means that the multiple modules are never near the same thing and thus not ever near each other.

javert 16y ago
Frankly, this isn't much of an explanation. I mean, what does it mean for one thing to be "near" to another, in this case? (Answer: nothing, which is why we don't use terms like "near" in computer science.) By parallel programs I think he means that the multiple modules are never near the same thing and thus not ever near each other. I think what you're saying here is that some problems are "embarassingly parallel," in the sense that the problem can be broken into many completely independent sequential computations. But I don't think that's what the guy who wrote the article was talking about. If so, I think he would have said so.
- noblethrasher 16y ago
  What 'near'/'far' means depends on the space you're talking about. If we're talking about the space of memory locations, then two modules are near each other if they both have access to the same storage location. You can fix this, for instance, by making things asymmetric; allow one module to have only read access and one module to only have write access. In that case, what you've done is make it so that the triangle inequality no longer obtains on the space of memory locations (at least with respect to those two modules). Edit:spelling.
  - javert 16y ago
    I mean, the triangle equality actually has a formal mathematical definition. I think you're using the wrong analogy here.
    - noblethrasher 16y ago
      It wasn't an analogy but it can be made as rigorous as you like. Let S be the set of (addressable) storage locations, let d(x, y) = x - y which is the distance between storage locations (an integer). The triangle inequality holds if d(x, y) + d(y, z) >= d(x, z). d is also clearly symmetric and reflexive; thus S and d form a metric space. Suppose module A contains a pointer to storage location x. Suppose module B contains a pointer to storage location y. Suppose A and B each contain a function which reads from z and writes to x or y respectively. If, with respect to A, d(x, z) = n < infinity, then, using pointer arithmetic, A can write to z and thus write to y. The distance between A and B is bounded (effectively it's n). On the other hand, if, with respect to A, d(x, z) = infinity (the value infinity might mean d threw an exception or something), then the distance between A and B is effectively infinite. So the concurrency/parallelism dichotomy boils down to this: Programs in which such distance between modules is finite are concurrent, programs in which the distance between modules is infinite are parallel. This example only applies to memory but it can easily apply to other kinds of relevant spaces as well.

HenryR 16y ago

Multiple threads of control aren't necessarily parallelisable. Consider a language runtime for which every thread takes the same global lock on the interpreter, and therefore prevents two threads running 'simultaneously'. You have concurrency but no parallelism. Such things happen in the real world. So you might argue that concurrency is necessary for parallelism, but it's not sufficient. Concurrency, to me, is about expanding the set of sequentially-equivalent executions of the program which are considered 'correct' according to the operational semantics of the programming language. If you just have one correct sequential execution, then there isn't any concurrency because you would have to execute sequentially to enforce the one correct ordering. For example, consider this snippet: 1. a = 1 2. b = 2 3. print a to file1 4. print b to file2 For most realistic language semantics there's no dependency between lines 3, and 4, so it's ok to execute in the following orders: 1, 2, 3, 4 1, 3, 2, 4 2, 1, 3, 4 2, 1, 4, 3 and others. There is concurrency there, and if the runtime cannot detect or leverage it quite often the processor will with out-of-order-execution and pipelining. However, the simpler snippet: 1. a = 2 2. b = a * 2 3. print a + b Doesn't have any obvious concurrency (ignoring that in this case the compiler could optimise away the assignments and additions into a single statement). 1 must happen before 2, which must happen before 3. There is only one 'correct' sequential execution, and therefore there is no obvious parallelisation achievable.

javert 16y ago
Consider a language runtime for which every thread takes the same global lock on the interpreter, and therefore prevents two threads running 'simultaneously'. You have concurrency but no parallelism. Well, I disagree that "concurrency" should be defined as "having multiple threads," but if that's how we want to define it... then I think you conflated the definitions half way through. Your final example, you state, has neither concurrency nor parallelism. Actually, by your definition of concurrency, it could be concurrent (put each statement in a separate thread and use locks), though I agree that it can't be parallel; it's inherently sequential.
- ww520 16y ago
  What are your definition of concurrency and parallelism?

keveman 16y ago

I find it easier if I disassociate the English meanings of the words from really how the words are used to mean different things in computer science. To me, concurrency is only in the programmers mind. That is, a programmer writes concurrent programs with different threads of control, say, one to process the user input, one to process the network packets etc. In reality, the multiple threads of control could really be running SEQUENTIALLY. That was the case when there was only one core. Remember, pthreads predates multi-cores. Parallelism is something more concrete, it REALLY exists in the real world. A programmer could just imagine and write a sequential loop, but if the compiler deemed it to be really parallel, it could really run parts of the loop in parallel. Of course, a programmer could write a concurrent program, as in, multiple threads of control, and the system could really run it in parallel, say on different cores of a multi-core processor. So remember, concurrency is abstract, parallelism is concrete.

javert 16y ago
OK, I'm seeing this explanation being brought up, and it makes sense. Thank you. I wish the original poster had actually stated it this way.
- srgseg 16y ago
  This is one of those times where not being able to see comment points really hurts my ability to read this thread. Lots of people saying slightly different things, and no way for me to know where consensus lies.

jberryman 16y ago

> Well, you have to have multiple threads of control to run on multiple processors simultaneously. And if you're running on multiple processors simultaneously, you have multiple threads of control. That depends on the semantics of your programming language. You may have a different perspective than the author, but I think his explanation is clear. Edit, To add a concrete example: I am currently working on a concurrent Haskell program that simulates a system of communicating nodes. However I am running it on my single core netbook. So we have indeterminacy and concurrent semantics without parallelism.

javert 16y ago
You may have a different perspective than the author, but I think his explanation is clear. Well, not being someone from the functional programming world, I don't think the explanation is clear at all. Edit, To add a concrete example: I am currently working on a concurrent Haskell program that simulates a system of communicating nodes. However I am running it on my single core netbook. So we have indeterminacy and concurrent semantics without parallelism. So you're saying that concurrency is an issue of semantics used in programming, while parallelism is talking about the underlying problem? I might be able to agree with that, but if that's the argument, that is what the author of the blog post should have stated. Anyway, please let me know if I'm understanding your point.

pnathan 16y ago

I'm also a computer scientist(y) person, and the separation of parallelism and concurrency has never been quite clear; indeed, the meanings seem artifically separated. Nonetheless - I understand concurrency to be a notion such as coroutines, and parallelism to mean, you know, things happening at the same time.

ww520 16y ago

Parallelism deals with program running at the same time; by definition, it runs on multiple CPUs. Concurrency deals with the non-deterministic order of running multiple threads of execution. Concurrent threads might or might not run on multiple CPUs. You can have multiple threads running on a single CPU system while the OS schedules one thread after another randomly. You still have concurrency and the order of execution is still non-deterministic, but you don't have parallelism. Parallelism's goal is to max out the overall throughput. It deals with partitioning data and algorithm to keep all the CPUs busy while minimizing the inter-CPU communication cost. It deals with efficient data transfer, cache coherency, data locality (out of the 10K CPUs, your neighbors can faster serve your subtask's need), and data dependency (which nodes need to go first). Parallel programs can be surprisingly deterministic. Some examples are cracking password (partition the dictionary in N ways and have N CPU hitting them), web crawling (partition the URL address space N way and have N CPU hitting them). Most of the map-reduce stuffs are parallel programs. Concurrency's main concern is to bring consistency to the non-deterministic nature of multiple threads of execution. Mutex, semaphore, event, monitor, and transactional memory are some mechanisms to bring order to the chaos.

javert 16y ago
So to simplify, what I'm gathering from this, and other comments, is: Concurrency occurs when program semantics allow two threads of execution to be executed in a simultaneous or interleaved manner. Parallelism occurs when two program threads actually execute simultaneously. By the way, I still have problems with the use of "non-determinism" here. Contrary to what you say, schedulers do not schedule threads randomly. But looked at from the perspectice of program semantics, that might as well be the case, which is (I think) the reason people keep bringing that up.
- HenryR 16y ago
  As you say, from the perspective of the program any scheduling interleaving is possible. The OS can substitute a new scheduling algorithm any time it likes. Otherwise we could know that the possible set of executions is much smaller than the set of all interleavings, and could write our concurrent code based upon that assumption. Then we'd be SOL when anyone tweaked the scheduler.

DanielRibeiro 16y ago

Robert Pike[1] was recently more elonquent and concise: Concurrency is a programming model that lets you express things that are independent, as independent executions ...and parallelism is about running two things at the same time. [1] http://www.infoq.com/interviews/pike-concurrency http://www.infoq.com/interviews/pike-concurrency

philwelch 16y ago

Judging from usage, I see "parallelism" as an of algorithms problem: how do solve a problem more effectively with k processors running at the same time rather than just one? Concurrency is a system problem: how do you actually run multiple threads of execution correctly? If you're designing a programming language or OS you're probably more worried about concurrency, but if you're using that programming language or OS to solve a computational program you're more worried about parallelism.