11 ms·

Parallelism is not concurrency

68 points by pfleidi 16y ago

krosaen 16y ago
related: scalability is not efficiency. discuss.
- jlouis 16y ago
  Yes, and efficiency is not latency.
gtani 16y ago
long (and some worthwhile) threads http://www.reddit.com/r/programming/comments/g6k0p/parallelism_is_not_concurrency/ http://www.reddit.com/r/programming/comments/g6k0p/paralleli...
cousin_it 16y ago
The post says that the depth of quicksort is O(log^2 n). Blelloch's list of NESL algorithms gives a depth of O(log n) instead: http://www.cs.cmu.edu/~scandal/nesl/alg-sequence.html#quicksort http://www.cs.cmu.edu/~scandal/nesl/alg-sequence.html#quicks... Or do I misunderstand something?
- deleted 16y ago
  [deleted]
  - JoachimSchipper 16y ago
    I've never seen log^2 x mean anything except (log x)^2; you're thinking of ^2log x.
    - pessimizer 16y ago
      I've never seen log^2 x mean (log x)^2. Common notation?
      - pmjordan 16y ago
        Yes. It's maybe more frequently seen on other functions such as trig functions (e.g. the identity sin²α+cos²α=1) but it crops up a lot on logarithms in computational complexity (as here). I've certainly never seen it used to mean anything else. As grandpa says, base is written as subscript.
      - grandpa 16y ago
        The base is usually a subscript: log_2(x), and the square is a superscript, log^2(x). Example of the superscript notation meaning squared: http://www.springerlink.com/content/7n7219tcyxr81gxc/ http://www.springerlink.com/content/7n7219tcyxr81gxc/
- shasta 16y ago
  There may be some difference in accounting. The recursion depth of Blelloch's recursive function you linked to is O(log n), but it uses an operation that cannot be implemented in constant time: partitioning the elements into those greater and less than the pivot. I'd guess that operation is itself O(log n), which would account for the O(log^2 n).
  - kragen 16y ago
    "Depth" and "recursion depth" are not the same thing. Quicksort partitioning normally takes O(N) time, but it can be in some sense perfectly parallelized once you have the pivot.
    - cousin_it 16y ago
      By "in some sense", do you mean it can be parallelized to O(1) time as long as you don't have to actually build up the data structures that result from partitioning (e.g. arrays)? Then it's not clear to me why this assumption is applicable to quicksorting an array. Doesn't it call for some non-obvious representation of intermediate results?
      - kragen 16y ago
        I'm out of my depth (heh) commenting here, but I think it depends on what kind of communications infrastructure you're assuming.
    - shasta 16y ago
      But isn't recursion depth the same as depth if each operation in your recursive function is constant time (except for the recursing bits)? Thus you can look at recursive depth as computing depth modulo the bits you compute in your function at a fixed level. I was speculating that partitioning would require O(log n) parallel steps. Can you give details or provide a link to achieving it constant depth?
- kragen 16y ago
  Quicksort takes O(N log N) time when comparing two keys is constant time. But as N → ∞, if your keys continue to have a fixed number of bits, you're going to have a lot of duplicate keys. (Consider sorting four billion 8-bit bytes.) In that case you can do better than Quicksort; you can simply partition the data in O(N) time among the unique keys, then sort the keys in O(1) time, then concatenate the partitions in O(N) time. So if you have to have unique keys, each comparison is going to take O(log N) time instead of O(1) time, so the overall algorithm takes O(N log² N) time. On the other hand, this is somewhat of a theoretical consideration if your keys are more than about 4–6 bytes long in the first place, since it's not very practical to store 2⁴⁸ records. But 2⁴⁸ is a long way from ∞, and if you're going to fudge by treating the theoretical factor of log N as constant, you might as well claim that Quicksort is O(N) with a constant of, say, less than 100 comparisons per key. I don't know anything about analyzing parallel quicksort, but maybe this key-comparison-time factor explains it? Because it seems like key comparisons would pretty much have to be serialized on Quicksort's critical path, no?
kevinburke 16y ago
If I'm reading the article correctly, the author is saying that with parallelism, you can perform independent operations in parallel (like sorting both halves of a quicksort), whereas concurrency as people think about it deals more with parallel operations on a shared state?
- chrisaycock 16y ago
  Parallelism often implies that the tasks are working towards the same goal together, like dividing-up the workload among sibling processors. This is purely for performance. Concurrency is simply the introduction of non-determinsm, like having a thread run a task in the background. Concurrency can be used to make a networked GUI application more responsive to the end user, even if there is no performance benefit.
Aetius 16y ago
In other words, more confusion. Don't read if you don't understand words like "asymptotic efficiency" and "nondeterministic composition". Ugh. Can someone put this in lay terms?
- ohyes 16y ago
  Sure, So pretty much he is saying that concurrency and parallelism aren't the same thing. (Which is kind of a 'duh' if you think about it). Parallelism is concerned with efficiency of the algorithm in a parallel environment. His example is that quick-sort is an easily parallelized algorithm (each level of recursion is two completely independent steps). This means that at each level, you can run the independent steps at the same time, meaning that in a parallel environment, you can see a big speed improvement. Concurrency is more dealing with the control flow of a program. Concurrency tries to manage resources in a 'nondeterministic' environment. Pretty much, its like an OS scheduler. The OS scheduler has to manage all of its resources, like the printer or the hard drive or whatever else, between different concurrently running processes, and prevent things like race conditions or deadlock. This isn't a parallelism issue, because you can have, for example, a single threaded processor with a multi-tasking operating system. does that help?
- te_platt 16y ago
  Parallelism is recognizing the 5 guys should be able to dig a ditch close to 5 times as fast as 1. Concurrency is making sure everyone has a shovel and is digging in the right place.
  - VladRussian 16y ago
    Great illustration! I just imagine 5 ditches all over the place and going into 5 different directions and/or crossing, or one big hole as all 5 started at the same place and, while shoveling, were hitting each other with elbows and the other end of shovel, or, starting at the correct place and in the correct direction, just 1 guy digging at any given time while the other 4 waiting for their chance to dig. ( i did my share of digging at student summer construction projects some 20+ years ago :)
  - 16y ago
jderick 16y ago
Concurrency is concerned with nondeterministic composition of programs (or their components). Parallelism is concerned with asymptotic efficiency of programs with deterministic behavior. Interesting distinction. My understanding is that these terms are typically used interchangeably in a more general sense. Perhaps it would be better to come up with some different terms for these concepts.
- chrisaycock 16y ago
  > these terms are typically used interchangeably in a more general sense No, these terms are used interchangeably by users who don't know what they mean. > Perhaps it would be better to come up with some different terms for these concepts. These concepts already have different terms. We don't need to come-up with new ones; we just need to start using the existing terms correctly.
chrisaycock 16y ago
> Isn’t concurrency required to implement parallelism? Well, yes, it is... Not exactly. Non-determinism is not required for parallelism; just look at VLIW: http://en.wikipedia.org/wiki/Very_long_instruction_word http://en.wikipedia.org/wiki/Very_long_instruction_word
- barrkel 16y ago
  Non-determinism is not concurrency either (I think the author is wrong to conflate the two). Parallelism is a physical, hardware, implementation of concurrency. VLIW, vector operations, GPUs etc. execute very fine-grained operations in parallel, but whether this is regarded as concurrency in any given context depends on how "lumpily" you define a concurrent task for that particular context. For example, fancy parallel instructions might be used to resize images in a thumbnail generator in a web server, but if the task being considered is the processing of a web request, then there is no concurrency. If the task being considered is processing a line, stripe or block of pixels, then there is concurrency.
nivertech 16y ago
Concurrency - property of systems in which several computational processes are executing at the same time, and potentially interacting with each other. Parallelism - computation in which many calculations are carried out simultaneously, operating on the principle that large problems can often be divided into smaller ones, which are then solved concurrently ("in parallel"). Go to slide #13 in my presentation: http://www.slideshare.net/nivertech/migrationtomulticore http://www.slideshare.net/nivertech/migrationtomulticore
barrkel 16y ago
I don't agree with the author's conflation of concurrency with non-determinism. To me, concurrency means there may be more than one operation logically "in flight" at any given time; parallelism means there may be more than one operation physically happening at any given time. Determinism vs non-determinism is an orthogonal issue. You could have a single-threaded cycle-counting CPU simulator which is entirely deterministic, yet if it is simulating a multi-threaded program, that program would exhibit concurrency (for example, if it were a web server, it could be serving multiple requests over separate TCP connections concurrently, working a little on each request round-robin).
- jlouis 16y ago
  To appreciate his point, you must be aware that Harper is thinking about a formalization of concurrency. In such a formalization, you could have a deterministic execution of the concurrent processes as you hint, but you will also have a trace of incoming events in the formalization, not under the control of the CPU. For the system as a whole to be deterministic, you would have it be deterministic for arbitrary event traces. This is rarely the case in practice though. Harper does not tend to just sling out a postulate unless he has good reason to think it is so, backed up by a formal system in which he identified the association. It could be that he has identified concurrency goes hand in hand with non-determinism. To me, it does sound rather plausible.
  - barrkel 16y ago
    It sounds poorly defined to me. Concurrency for me means a specific thing, and that specific thing does not have a necessary implication of non-determinism. My position is similar to dmbarbour's (https://existentialtype.wordpress.com/2011/03/17/parallelism-is-not-concurrency/#comment-20 https://existentialtype.wordpress.com/2011/03/17/parallelism...).
- rafaelferreira 16y ago
  Your distinction appeals to physicality, to a "real world". The author comes from a purer mathematical perspective, where it does not matter whether the code runs on silicon, is emulated by another machine, or is evaluated by humans on a blackboard. Parallelism is purely an efficiency issue; the result of a computation does not change if run sequentially or in parallel. In other words, it only affects the cost model, not the semantics. Concurrency means adopting some non-determinism in the semantics, either for necessity (e.g. in concurrent servers) or as a program structuring mechanism. In your example, if we are concerned with the semantics of the simulator, then there is no parallelism OTOH, if we are concerned with the semantics of the simulated code, then it's likely that we would use concurrency in it's definition (even if we "really know" that there is no underlying physical nondeterminism).

68 points by pfleidi 16y ago

krosaen 16y ago

related: scalability is not efficiency. discuss.

jlouis 16y ago
Yes, and efficiency is not latency.

gtani 16y ago

long (and some worthwhile) threads http://www.reddit.com/r/programming/comments/g6k0p/parallelism_is_not_concurrency/ http://www.reddit.com/r/programming/comments/g6k0p/paralleli...

cousin_it 16y ago

The post says that the depth of quicksort is O(log^2 n). Blelloch's list of NESL algorithms gives a depth of O(log n) instead: http://www.cs.cmu.edu/~scandal/nesl/alg-sequence.html#quicksort http://www.cs.cmu.edu/~scandal/nesl/alg-sequence.html#quicks... Or do I misunderstand something?

deleted 16y ago
[deleted]
- JoachimSchipper 16y ago
  I've never seen log^2 x mean anything except (log x)^2; you're thinking of ^2log x.
  - pessimizer 16y ago
    I've never seen log^2 x mean (log x)^2. Common notation?
    - pmjordan 16y ago
      Yes. It's maybe more frequently seen on other functions such as trig functions (e.g. the identity sin²α+cos²α=1) but it crops up a lot on logarithms in computational complexity (as here). I've certainly never seen it used to mean anything else. As grandpa says, base is written as subscript.
    - grandpa 16y ago
      The base is usually a subscript: log_2(x), and the square is a superscript, log^2(x). Example of the superscript notation meaning squared: http://www.springerlink.com/content/7n7219tcyxr81gxc/ http://www.springerlink.com/content/7n7219tcyxr81gxc/
shasta 16y ago
There may be some difference in accounting. The recursion depth of Blelloch's recursive function you linked to is O(log n), but it uses an operation that cannot be implemented in constant time: partitioning the elements into those greater and less than the pivot. I'd guess that operation is itself O(log n), which would account for the O(log^2 n).
- kragen 16y ago
  "Depth" and "recursion depth" are not the same thing. Quicksort partitioning normally takes O(N) time, but it can be in some sense perfectly parallelized once you have the pivot.
  - cousin_it 16y ago
    By "in some sense", do you mean it can be parallelized to O(1) time as long as you don't have to actually build up the data structures that result from partitioning (e.g. arrays)? Then it's not clear to me why this assumption is applicable to quicksorting an array. Doesn't it call for some non-obvious representation of intermediate results?
    - kragen 16y ago
      I'm out of my depth (heh) commenting here, but I think it depends on what kind of communications infrastructure you're assuming.
  - shasta 16y ago
    But isn't recursion depth the same as depth if each operation in your recursive function is constant time (except for the recursing bits)? Thus you can look at recursive depth as computing depth modulo the bits you compute in your function at a fixed level. I was speculating that partitioning would require O(log n) parallel steps. Can you give details or provide a link to achieving it constant depth?
kragen 16y ago
Quicksort takes O(N log N) time when comparing two keys is constant time. But as N → ∞, if your keys continue to have a fixed number of bits, you're going to have a lot of duplicate keys. (Consider sorting four billion 8-bit bytes.) In that case you can do better than Quicksort; you can simply partition the data in O(N) time among the unique keys, then sort the keys in O(1) time, then concatenate the partitions in O(N) time. So if you have to have unique keys, each comparison is going to take O(log N) time instead of O(1) time, so the overall algorithm takes O(N log² N) time. On the other hand, this is somewhat of a theoretical consideration if your keys are more than about 4–6 bytes long in the first place, since it's not very practical to store 2⁴⁸ records. But 2⁴⁸ is a long way from ∞, and if you're going to fudge by treating the theoretical factor of log N as constant, you might as well claim that Quicksort is O(N) with a constant of, say, less than 100 comparisons per key. I don't know anything about analyzing parallel quicksort, but maybe this key-comparison-time factor explains it? Because it seems like key comparisons would pretty much have to be serialized on Quicksort's critical path, no?

kevinburke 16y ago

If I'm reading the article correctly, the author is saying that with parallelism, you can perform independent operations in parallel (like sorting both halves of a quicksort), whereas concurrency as people think about it deals more with parallel operations on a shared state?

chrisaycock 16y ago
Parallelism often implies that the tasks are working towards the same goal together, like dividing-up the workload among sibling processors. This is purely for performance. Concurrency is simply the introduction of non-determinsm, like having a thread run a task in the background. Concurrency can be used to make a networked GUI application more responsive to the end user, even if there is no performance benefit.

Aetius 16y ago

In other words, more confusion. Don't read if you don't understand words like "asymptotic efficiency" and "nondeterministic composition". Ugh. Can someone put this in lay terms?

ohyes 16y ago
Sure, So pretty much he is saying that concurrency and parallelism aren't the same thing. (Which is kind of a 'duh' if you think about it). Parallelism is concerned with efficiency of the algorithm in a parallel environment. His example is that quick-sort is an easily parallelized algorithm (each level of recursion is two completely independent steps). This means that at each level, you can run the independent steps at the same time, meaning that in a parallel environment, you can see a big speed improvement. Concurrency is more dealing with the control flow of a program. Concurrency tries to manage resources in a 'nondeterministic' environment. Pretty much, its like an OS scheduler. The OS scheduler has to manage all of its resources, like the printer or the hard drive or whatever else, between different concurrently running processes, and prevent things like race conditions or deadlock. This isn't a parallelism issue, because you can have, for example, a single threaded processor with a multi-tasking operating system. does that help?
te_platt 16y ago
Parallelism is recognizing the 5 guys should be able to dig a ditch close to 5 times as fast as 1. Concurrency is making sure everyone has a shovel and is digging in the right place.
- VladRussian 16y ago
  Great illustration! I just imagine 5 ditches all over the place and going into 5 different directions and/or crossing, or one big hole as all 5 started at the same place and, while shoveling, were hitting each other with elbows and the other end of shovel, or, starting at the correct place and in the correct direction, just 1 guy digging at any given time while the other 4 waiting for their chance to dig. ( i did my share of digging at student summer construction projects some 20+ years ago :)
- 16y ago

jderick 16y ago

Concurrency is concerned with nondeterministic composition of programs (or their components). Parallelism is concerned with asymptotic efficiency of programs with deterministic behavior. Interesting distinction. My understanding is that these terms are typically used interchangeably in a more general sense. Perhaps it would be better to come up with some different terms for these concepts.

chrisaycock 16y ago
> these terms are typically used interchangeably in a more general sense No, these terms are used interchangeably by users who don't know what they mean. > Perhaps it would be better to come up with some different terms for these concepts. These concepts already have different terms. We don't need to come-up with new ones; we just need to start using the existing terms correctly.

chrisaycock 16y ago

> Isn’t concurrency required to implement parallelism? Well, yes, it is... Not exactly. Non-determinism is not required for parallelism; just look at VLIW: http://en.wikipedia.org/wiki/Very_long_instruction_word http://en.wikipedia.org/wiki/Very_long_instruction_word

barrkel 16y ago
Non-determinism is not concurrency either (I think the author is wrong to conflate the two). Parallelism is a physical, hardware, implementation of concurrency. VLIW, vector operations, GPUs etc. execute very fine-grained operations in parallel, but whether this is regarded as concurrency in any given context depends on how "lumpily" you define a concurrent task for that particular context. For example, fancy parallel instructions might be used to resize images in a thumbnail generator in a web server, but if the task being considered is the processing of a web request, then there is no concurrency. If the task being considered is processing a line, stripe or block of pixels, then there is concurrency.

nivertech 16y ago

Concurrency - property of systems in which several computational processes are executing at the same time, and potentially interacting with each other. Parallelism - computation in which many calculations are carried out simultaneously, operating on the principle that large problems can often be divided into smaller ones, which are then solved concurrently ("in parallel"). Go to slide #13 in my presentation: http://www.slideshare.net/nivertech/migrationtomulticore http://www.slideshare.net/nivertech/migrationtomulticore

barrkel 16y ago

I don't agree with the author's conflation of concurrency with non-determinism. To me, concurrency means there may be more than one operation logically "in flight" at any given time; parallelism means there may be more than one operation physically happening at any given time. Determinism vs non-determinism is an orthogonal issue. You could have a single-threaded cycle-counting CPU simulator which is entirely deterministic, yet if it is simulating a multi-threaded program, that program would exhibit concurrency (for example, if it were a web server, it could be serving multiple requests over separate TCP connections concurrently, working a little on each request round-robin).

jlouis 16y ago
To appreciate his point, you must be aware that Harper is thinking about a formalization of concurrency. In such a formalization, you could have a deterministic execution of the concurrent processes as you hint, but you will also have a trace of incoming events in the formalization, not under the control of the CPU. For the system as a whole to be deterministic, you would have it be deterministic for arbitrary event traces. This is rarely the case in practice though. Harper does not tend to just sling out a postulate unless he has good reason to think it is so, backed up by a formal system in which he identified the association. It could be that he has identified concurrency goes hand in hand with non-determinism. To me, it does sound rather plausible.
- barrkel 16y ago
  It sounds poorly defined to me. Concurrency for me means a specific thing, and that specific thing does not have a necessary implication of non-determinism. My position is similar to dmbarbour's (https://existentialtype.wordpress.com/2011/03/17/parallelism-is-not-concurrency/#comment-20 https://existentialtype.wordpress.com/2011/03/17/parallelism...).
rafaelferreira 16y ago
Your distinction appeals to physicality, to a "real world". The author comes from a purer mathematical perspective, where it does not matter whether the code runs on silicon, is emulated by another machine, or is evaluated by humans on a blackboard. Parallelism is purely an efficiency issue; the result of a computation does not change if run sequentially or in parallel. In other words, it only affects the cost model, not the semantics. Concurrency means adopting some non-determinism in the semantics, either for necessity (e.g. in concurrent servers) or as a program structuring mechanism. In your example, if we are concerned with the semantics of the simulator, then there is no parallelism OTOH, if we are concerned with the semantics of the simulated code, then it's likely that we would use concurrency in it's definition (even if we "really know" that there is no underlying physical nondeterminism).