What is the difference between the terms concurrent and parallel execution? I've never quite been able to grasp the distinction.

The tag defines concurrency as a manner of running two processes simultaneously, but I thought parallelism was exactly the same thing, i.e.: separate threads or processes which can potentially be run on separate processors.

Also, if we consider something like asynchronous I/O, are we dealing with concurrency or parallelism?

  • 23
    In a nutshell - concurrent: many different operations happening at once. parallel: the same operation broken into small bits happening at once. – Oded Mar 15 '13 at 16:04
  • 1
    @Oded, I understand what the words mean, but I'm having trouble grokking the implications. Do you have a concrete example? – blz Mar 15 '13 at 16:11
  • 6
    @Oded, I don't really agree with you, nowhere in their definitions (either general or applied to programming) do the notions of "concurrent" and "parallel" mention anything about the number or "size" of operations. – Shivan Dragon Mar 15 '13 at 16:22
  • 1
    @Oded when you said "small bits". – Avner Shahar-Kashtan Mar 15 '13 at 17:30
  • 1
    @Oded: Yes, but this seems to be the root of the misunderstanding between you and ShivanDragon. – Avner Shahar-Kashtan Mar 15 '13 at 17:44
up vote 78 down vote accepted

Concurrency and parallelism are two related but distinct concepts.

Concurrency means, essentially, that task A and task B both need to happen independently of each other, and A starts running, and then B starts before A is finished.

There are various different ways of accomplishing concurrency. One of them is parallelism--having multiple CPUs working on the different tasks at the same time. But that's not the only way. Another is by task switching, which works like this: Task A works up to a certain point, then the CPU working on it stops and switches over to task B, works on it for a while, and then switches back to task A. If the time slices are small enough, it may appear to the user that both things are being run in parallel, even though they're actually being processed in serial by a multitasking CPU.

  • 1
    Case B is how async IO works, no? – blz Mar 15 '13 at 16:29
  • 3
    @blz: That's right. It's also how preemptive multitasking works. The main difference is that on async IO, the program decides to give up its time and tell the CPU to process something else, whereas in preemptive multitasking, if the running thread doesn't voluntarily give up the CPU after long enough, the OS preempts it. – Mason Wheeler Mar 15 '13 at 16:37
  • 1
    The best explanation hands down – Konrad Sep 22 at 14:36

The two concepts are related, but different.

Concurrency means that two or more calculations happen within the same time frame, and there is usually some sort of dependency between them.

Parallelism means that two or more calculations happen simultaneously.

Put boldly, concurrency describes a problem (two things need to happen together), while parallelism describes a solution (two processor cores are used to execute two things simultaneously).

Parallelism is one way to implement concurrency, but it's not the only one. Another popular solution is interleaved processing (a.k.a. coroutines): split both tasks up into atomic steps, and switch back and forth between the two.

By far the best known example of non-parallel concurrency is how JavaScript works: there is only one thread, and any asynchronous callback has to wait until the previous chunk of code has finished executing. This is important to know, because it guarantees that any function you write is atomic - no callback can interrupt it until it returns. But it also means that "busy loops" won't work - you can't set a timeout and then loop until it fires, because the loop will prevent the timeout callback from executing.

  • 5
    You say that Concurrency means that two or more calculations happen within the same time frame, and there is usually some sort of dependency between them. But the user that wrote that accepted answer says Concurrency means, essentially, that task A and task B both need to happen independently of each other. So what is the conclusion? – nbro Mar 13 '15 at 12:07
  • could you explain why JavaScript's model is concurrent? From your definition of concurrency two or more calculations should happen within the same time frame. But in JavaScript calculations are sequentially ordered using a single queue. – damluar Apr 21 '16 at 10:41
  • 3
    By "within the same time frame", I don't necessarily mean "simultaneously", just that the overall time frames during which they occur overlap. This can be achieved in parallel (e.g. two processor cores, each executing one of the tasks), but it can also be achieved by completely serializing the execution (do task 1 first, remember the outcome, then do task 2, then report both), or by chopping both up and interleaving the chunks. The latter is what JS does. – tdammers Apr 25 '16 at 11:41

I believe this answer to be more correct than the existing answers and editing them would have changed their essence. I have tried to link to various sources or wikipedia pages so others can affirm correctness.


Concurrency: the property of a system which enables units of the program, algorithm, or problem to be executed out-of-order or in partial order without affecting the final outcome 1 2.

A simple example of this is consecutive additions:

0 + 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 = 45

Due to the commutative property of addition the order of these can be re-arranged without affecting correctness; the following arrangement will result in the same answer:

(1 + 9) + (2 + 8) + (3 + 7) + (4 + 6) + 5 + 0 = 45

Here I have grouped numbers into pairs that will sum to 10, making it easier for me to arrive at the correct answer in my head.

Parallel Computing: a type of computation in which many calculations or the execution of processes are carried out simultaneously 3 4. Thus parallel computing leverages the property of concurrency to execute multiple units of the program, algorithm, or problem simultaneously.

Continuing with the example of consecutive additions, we can execute different portions of the sum in parallel:

Execution unit 1:  0 + 1 + 2 + 3 + 4 = 10
Execution unit 2:  5 + 6 + 7 + 8 + 9 = 35

Then at the end we sum the results from each worker to get 10 + 35 = 45.

Again, this parallelism was only possible because consecutive additions have the property of concurrency.

Concurrency can be leveraged by more than just parallelism though. Consider pre-emption on a single-core system: over a period of time the system may make progress on multiple running processes without any of them finishing. Indeed, your example of asyncronous I/O is a common example of concurrency that does not require parallelism.


Confusion

The above is relatively straightforward. I suspect people get confused because the dictionary definitions do not necessarily match what was outlined above:

  • Concurrent: occurring or existing simultaneously or side by side 5.
  • Concurrency: the fact of two or more events or circumstances happening or existing at the same time From searching on google: "define: concurrency".

The dictionary defines "concurrency" as a fact of occurrence, whereas the definition in the computing vernacular is a latent property of a program, property, or system. Though related these things are not the same.


Personal Recommendations

I recommend using the term "parallel" when the simultaneous execution is assured or expected, and to use the term "concurrent" when it is uncertain or irrelevant if simultaneous execution will be employed.

I would therefore describe simulating a jet engine on multiple cores as parallel.

I would describe Makefiles as an example of concurrency. Makefiles state the dependencies of each target. When targets depend on other targets this creates a partial ordering. When the relationships and recipes are comprehensively and correctly defined this establishes the property of concurrency: there exists a partial order such that order of certain tasks can be re-arranged without affecting the result. Again, this concurrency can be leveraged to build multiple rules simultaneously but the concurrency is a property of the Makefile whether parallelism is employed or not.

Concurrent execution is the generalized form of parallel execution. For example parallel program can also be called concurrent but reverse is not true.

  1. Concurrent execution is possible on single processor (multiple threads, managed by scheduler)
  2. Parallel execution is not possible on single processor but on multiple processors. (One process per processor)

For details read this research paper Concepts of Concurrent Programming

  • 1
    "Parallel execution is not possible on single processor but on multiple processors" -- other than, of course, where there are parallel execution paths within a processor, e.g. systems that exploit Instruction Level Parallelism (aka "superscalar" architectures, e.g. Intel processors since the Pentium, ARM Cortex, and most other high-end processors), and Single Instruction Multiple Data, also known as data-parallel architectures (e.g. MMX/SSE/etc). Not to mention exotic arrangements like dataflow processors, and so on. – Jules Feb 28 at 20:04

Parallel processing is a subset of concurrent processing.

Concurrent processing describes two tasks occurring asynchronously, meaning the order in which the tasks are executed is not predetermined. Two threads can run concurrently on the same processor core by interleaving executable instructions. For example, thread 1 runs for 10ms, thread 2 runs for 10ms etc.

Parallel processing is a type of concurrent processing where more than one set of instructions is executing simultaneously. This could be multiple systems working on a common problem as in distributed computing, or multiple cores on the same system.

In my opinion, from an application programming perspective there is no difference between these two concepts and having two words is confusing for confusion's sake. I think thread interleaving was brought about to simulate multicore processing back in the days when multicore wasn't a possibility. Why do we have a word for this outdated mindset?

Mason Wheeler and Penguin have given the same answer. One Core with task switching and or multicore is concurrent, strictly multicore = parallel.

My opinion is that these two terms should be rolled into one and I make an effort to avoid saying "concurrent". I guess on the OS programming level the distinction is important, but from the application programmer's perspective it doesn't matter too much. I've written mapReduce, Spark, MPI, cuda, openCL, and multithreaded c++ and I've never had to stop and think if the job is running with interleaved threads or with multiple cores.

For example, when I write multithreaded c++ sometimes I'm not sure how many cores I'll get, though there are ways to make demands on how many cores you get as described here https://stackoverflow.com/questions/2166425/how-to-structure-a-c-application-to-use-a-multicore-processor . In spark I just do map and reduce operations and have no idea how the jvm is handling them on the hardware level. On GPUs I think every thread is assigned to it's own simple processor, but I always sync my threads wherever a problem might arise. With MPI the communication between machines is specified explicitly, but we could interleave the functions running on multiple machines on a single core and combine the results via an appropriate single threaded function. And what if we use MPI to coordinate a bunch of single core machines, each one with multithreading? What difference does it make? I'd say none. Call it all "parallel" and be done with it.

  • 1
    The distinction is still relevant today. You can only have parallelism up to the number of CPU core that your hardware have, however many programs have hundreds of concurrent calculations happening all at once, much more than the number of cores the hardware have. Failure to understand this distinction might led programmers to fail to understand why their parallelized programs are running slower than their single threaded version (or small number of threads). – Lie Ryan Feb 12 '17 at 11:47

tdammer's statement comes close, the rest is all besides the point. He says:

"Put boldly, concurrency describes a problem (two things need to happen together), while parallelism describes a solution (two processor cores are used to execute two things simultaneously"

Let's just analyse the words.

Current means happening now, actual, relevant at this moment. Con means against, counter, not aligning with.

Parallel means in the same direction without crossing, without being in eachother's way.

So, concurrency implies competing for the same resource. Parallelism does not. Parallel processes may be using the same resource but it is not considered a problem, it is not an issue. With concurrency, it is an issue to be dealt with.

  • "Current means happening now, actual, relevant at this moment. Con means against, counter, not aligning with." - citation needed. I strongly doubt both of these statements. While "current" can have the meaning mentioned here in English, that is not the meaning used in the word "concurrent" – Hulk Mar 1 at 13:55
  • 1
    I think that the translation of concurrent from Latin is "to run together". The prefix 'con' often means together, as in conspiracy (to breathe together) consequence (results together or following) conclude (close together) etc. It is an annoying facet of language that something can have opposite meanings, sanction is my favorite example. – user251748 Mar 1 at 19:45
  • @no comprende In this case (con-current) the running together meaning does seem the better fit. Since there is no pro-current... In Dutch, concurrent is a noun meaning competitor. Courant is common, moving all around you. It is also newspaper. Something that is active now. "Rekening courant" is a running account. I feel concurrency implies con(!)flict. A fight over the same resource. Running in the same space. Maybe because of the Dutch meaning (competitor). – Martin Maat Mar 1 at 20:42
  • What would Dijkstra say, I wonder? – user251748 Mar 2 at 0:25

Obviously, the terms are used differently in different cultures.

My understanding is the following:

Parallelism is a way to speed up processing. Whether you do matrix multiplication on a single core, on multiple cores or even in the GPU, the outcome is the same (or else your program is broken). It doesn't add new functionality to some program, just speed.

While concurrency is about things you couldn't do sequentially. For example, serving 3 different webpages at the same time to 3 clients, while waiting for the next request. (Though you could simulate this to some degree through interleaving, as it was done in the elder days.) Note that the behaviour of concurrent programs is nondeterministic. It is for example not clear, which of the 3 clients will be completly served first. You could run quite some tests and get a different result each time regarding the order the request will be finished. The run-time system should guarantee that a) all clients will be served and b) in a reasonable amount of time.

Usually, the work horse of a parallel computation isn't aware of, nor does it care about, parallelism. While concurrent tasks often explicitly employ inter-process or inter-thread communications - such as blocking queues, synchronization and locking mechanisms.

protected by gnat Feb 12 '17 at 7:02

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.