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").
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?
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.
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).
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.
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).
Sure, you can have deterministic concurrency. But that's not what he's talking about. Concurrent operations being non-deterministic is the accepted norm. If you're talking about deterministic concurrency, then you can qualify it as such; anything else is pedantry.
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).
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?
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.
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.
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.
Concurrency = managing shared resources. Things like mutual exclusion and transactions. Getting processors to get in line (serialization/composition) for a shared resource instead of just trampling over each other by just grabbing it when they want (non-determinism), so that actions that depend on being done in order and without interruption can be done.
Parallelism = splitting up subtasks that don't depend on each other. If the tasks don't depend on each other, the things doing them shouldn't need to talk. If you have enough processors, you can do almost everything at once, so the algorithm is only as slow as things that actually need to be done in order (asymptotic efficiency).
In imperative programming, we tell the computer what order to do things in, so it doesn't know what actions don't depend on each other - to parallelize, we have to worry about concurrency. In functional programming, the compiler knows what depends on what (what uses the result of something else), so it can parallelize things that don't depend on each other. It might be implemented with concurrency, but the programmer doesn't need to worry about it.
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.
Concurrency does not necessarily have anything to do with parallel programming, although the latter may need to be aware of concurrency issues if the parallel algorithm needs to manage shared resources and sequential dependencies.
The gist of the article is that functional languages lend themselves to parallel constructs, and such tooling should be built into languages themselves to free the programmer from worrying about concurrency issues. For more details, read on...
Asymptotic efficiency is just a fancy way of saying algorithmic efficiency. In computer science terms, asymptotic analysis measures how work increases relative to how much input needs to be processed; eg, sorting an N-element list using Quicksort would take an amount of work corresponding to NlogN.
Now, when you try to parallelize an algorithm such as Quicksort, you are concerned with your speedup -- how much you will gain by processing in parallel. The speedup is not always linear because of sequential dependencies within the algorithm. Wiki has a decent primer on the subject: http://en.wikipedia.org/wiki/Speedup.
In this case, the article was looking at the asymptotic efficiency of Quicksort's critical section; eg, the part that could be parallelized, to determine just how much it could be parallelized.
Concurrency, on the other hand, deals with more classical problems such as scheduling and resource deadlock. It is the OS's job to manage resources, which is why you hear a lot about concurrency in terms of the OS. And since thread/process scheduling by the OS is unpredictable, this is where 'nondeterministic composition' comes from. This manifests in things like race conditions. http://en.wikipedia.org/wiki/Race_condition
So it may become the parallel application's responsibility to avoid such nondeterministic behavior within resources shared by the application. Note this doesn't just apply to threads running on the same computer/OS; it may also apply to data coming in from the network from a distributed parallel algorithm.
In conventional, procedural programming languages, concurrency has to be addressed explicitly through things like locks and barriers. Functional languages help make this more implicit due to immutability. Languages like Erlang go one step further and absolve you of any responsibility for things like IPC.
Parallelism is a property of the machine. We are obsessed with the idea of making a program run in less time by better utilizing the hardware.
Concurrency is a property of the program. It is about describing that multiple events can happen independently of each other.
An operating system kernel (old ones) are concurrent but not parallel for instance. Concurrently it will handle multiple users, input from keyboard, network and disk, switch process contexts and so on. Yet, only a single CPU will be doing the task, so everything happens in a serial stream of events.
The point where the two blend is when you have a concurrent system and want it to execute faster. Then, you will often find yourself employing parallel tactics to speed the system up. In the OS case, modern NIC's and disk drives have processors on them carrying out tasks in parallel to the CPU. So the system is not strictly concurrent anymore. They also have SMP-capability of course.
Parallel but not concurrent systems exist as well. The perhaps best example is a GPU, which is massively parallel (1700+ cores is not uncommon), but all the cores are doing the same thing. Hence, it cannot handle different events at different times with independence.
[+] [-] nivertech|15 years ago|reply
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
[+] [-] kevinburke|15 years ago|reply
[+] [-] chrisaycock|15 years ago|reply
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.
[+] [-] barrkel|15 years ago|reply
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|15 years ago|reply
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.
[+] [-] rafaelferreira|15 years ago|reply
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).
[+] [-] jallmann|15 years ago|reply
[+] [-] cousin_it|15 years ago|reply
http://www.cs.cmu.edu/~scandal/nesl/alg-sequence.html#quicks...
Or do I misunderstand something?
[+] [-] shasta|15 years ago|reply
[+] [-] kragen|15 years ago|reply
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?
[+] [-] unknown|15 years ago|reply
[deleted]
[+] [-] chrisaycock|15 years ago|reply
Not exactly. Non-determinism is not required for parallelism; just look at VLIW:
http://en.wikipedia.org/wiki/Very_long_instruction_word
[+] [-] barrkel|15 years ago|reply
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.
[+] [-] gtani|15 years ago|reply
http://www.reddit.com/r/programming/comments/g6k0p/paralleli...
[+] [-] jderick|15 years ago|reply
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|15 years ago|reply
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.
[+] [-] krosaen|15 years ago|reply
[+] [-] jlouis|15 years ago|reply
[+] [-] Aetius|15 years ago|reply
Can someone put this in lay terms?
[+] [-] ohyes|15 years ago|reply
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?
[+] [-] T-R|15 years ago|reply
Parallelism = splitting up subtasks that don't depend on each other. If the tasks don't depend on each other, the things doing them shouldn't need to talk. If you have enough processors, you can do almost everything at once, so the algorithm is only as slow as things that actually need to be done in order (asymptotic efficiency).
In imperative programming, we tell the computer what order to do things in, so it doesn't know what actions don't depend on each other - to parallelize, we have to worry about concurrency. In functional programming, the compiler knows what depends on what (what uses the result of something else), so it can parallelize things that don't depend on each other. It might be implemented with concurrency, but the programmer doesn't need to worry about it.
[+] [-] te_platt|15 years ago|reply
[+] [-] jallmann|15 years ago|reply
The gist of the article is that functional languages lend themselves to parallel constructs, and such tooling should be built into languages themselves to free the programmer from worrying about concurrency issues. For more details, read on...
Asymptotic efficiency is just a fancy way of saying algorithmic efficiency. In computer science terms, asymptotic analysis measures how work increases relative to how much input needs to be processed; eg, sorting an N-element list using Quicksort would take an amount of work corresponding to NlogN.
Now, when you try to parallelize an algorithm such as Quicksort, you are concerned with your speedup -- how much you will gain by processing in parallel. The speedup is not always linear because of sequential dependencies within the algorithm. Wiki has a decent primer on the subject: http://en.wikipedia.org/wiki/Speedup.
In this case, the article was looking at the asymptotic efficiency of Quicksort's critical section; eg, the part that could be parallelized, to determine just how much it could be parallelized.
Concurrency, on the other hand, deals with more classical problems such as scheduling and resource deadlock. It is the OS's job to manage resources, which is why you hear a lot about concurrency in terms of the OS. And since thread/process scheduling by the OS is unpredictable, this is where 'nondeterministic composition' comes from. This manifests in things like race conditions. http://en.wikipedia.org/wiki/Race_condition
So it may become the parallel application's responsibility to avoid such nondeterministic behavior within resources shared by the application. Note this doesn't just apply to threads running on the same computer/OS; it may also apply to data coming in from the network from a distributed parallel algorithm.
In conventional, procedural programming languages, concurrency has to be addressed explicitly through things like locks and barriers. Functional languages help make this more implicit due to immutability. Languages like Erlang go one step further and absolve you of any responsibility for things like IPC.
HTH.
[+] [-] jlouis|15 years ago|reply
Parallelism is a property of the machine. We are obsessed with the idea of making a program run in less time by better utilizing the hardware.
Concurrency is a property of the program. It is about describing that multiple events can happen independently of each other.
An operating system kernel (old ones) are concurrent but not parallel for instance. Concurrently it will handle multiple users, input from keyboard, network and disk, switch process contexts and so on. Yet, only a single CPU will be doing the task, so everything happens in a serial stream of events.
The point where the two blend is when you have a concurrent system and want it to execute faster. Then, you will often find yourself employing parallel tactics to speed the system up. In the OS case, modern NIC's and disk drives have processors on them carrying out tasks in parallel to the CPU. So the system is not strictly concurrent anymore. They also have SMP-capability of course.
Parallel but not concurrent systems exist as well. The perhaps best example is a GPU, which is massively parallel (1700+ cores is not uncommon), but all the cores are doing the same thing. Hence, it cannot handle different events at different times with independence.
[+] [-] akjj|15 years ago|reply
http://ghcmutterings.wordpress.com/2009/10/06/parallelism-co...