When looking at concurrent programming, two terms are commonly used i.e. concurrent and parallel.

And some programming languages specifically claim support for parallel programming, such as Java.

Does this means parallel and concurrent programming are actually different?

migrated from cstheory.stackexchange.com Jan 26 '14 at 8:08

This question came from our site for theoretical computer scientists and researchers in related fields.

  • 10
    Yes, concurrent and parallel programming are different. for instance, you can have two threads (or processes) executing concurrently on the same core through context switching. When the two threads (or processes) are executed on two different cores (or processors), you have parallelism. So, in the former case (concurrency) parallelism is only "virtual", while in the latter you have true parallelism. Therefore, every parallel program is concurrent, but the converse is not necessarily true. – Massimo Cafaro Jan 24 '14 at 12:28
  • 1
    Be careful here. You can achieve the same result either through language support (i.e., extending a language with new constructs) or using a low level approach (e.g., by using a library, as in the case of MPI and OpenMP). Anyway, with current multicore processors and operating systems with SMP support, program that will be concurrent if run on old single-core processors, may be executed in parallel if the OS schedules the threads of execution of the program on different cores. So, the distinction is a little "blurred" nowadays. – Massimo Cafaro Jan 24 '14 at 12:57
  • 3
    What you use for a speed of light latency constant. In concurrency you pretend speed of light latency is one clock cycle. In parallel you assume one server is next door, in distributed you assume one server is on Mars. – Chad Brewbaker Jan 24 '14 at 20:26
  • 1
  • 1
    Robert Harper discusses the issue in two blog posts, "Parallelism is not concurrency" and "Parallelism and Concurrency, Revisited", which you might want to check. – Basil Nov 4 '14 at 13:33

Distinguish parallelism (using extra computational units to do more work per unit time) from concurrency (managing access to shared resources). Teach parallelism first because it is easier and helps establish a non- sequential mindset.

From " A Sophomoric∗ Introduction to Shared-Memory Parallelism and Concurrency" by Dan Grossman (version of November 16, 2013)

In addition to Nish's answer, let me recommend Simon Marlow's book on Parallel and Concurrent Programming in Haskell or his shorter tutorial. They answer your first question from Haskell's perspective, so they could be better suited for theoretically inclined readers (Haskell is a purely functional, lazy programming language that is much closer to Mathematics than other languages).

Quoting from there:

In many fields, the words parallel and concurrent are synonyms; not so in programming, where they are used to describe fundamentally different concepts.

A parallel program is one that uses a multiplicity of computational hardware (e.g. multiple processor cores) in order to perform computation more quickly. Different parts of the computation are delegated to different processors that execute at the same time (in parallel), so that results may be delivered earlier than if the computation had been performed sequentially.

In contrast, concurrency is a program-structuring technique in which there are multiple threads of control. Notionally the threads of control execute "at the same time"; that is, the user sees their effects interleaved. Whether they actually execute at the same time or not is an implementation detail; a concurrent program can execute on a single processor through interleaved execution, or on multiple physical processors.

I recommend reading the rest in the tutorial (p.4), but let me quote some of the remainder of this section, as it connects both programming paradigms with quantitative and qualitative characteristics of programs, such as efficiency, modularity, and determinism.

While parallel programming is concerned only with efficiency, concurrent programming is concerned with structuring a program that needs to interact with multiple independent external agents (for example the user, a database server, and some external clients). Concurrency allows such programs to be modular; the thread that interacts with the user is distinct from the thread that talks to the database. In the absence of concurrency, such programs have to be written with event loops and callbacks --- indeed, event loops and callbacks are often used even when concurrency is available, because in many languages concurrency is either too expensive, or too difficult, to use.

The notion of "threads of control" does not make sense in a purely functional program, because there are no effects to observe, and the evaluation order is irrelevant. So concurrency is a structuring technique for effectful code; in Haskell, that means code in the IO monad.

A related distinction is between deterministic and nondeterministic programming models. A deterministic programming model is one in which each program can give only one result, whereas a nondeterministic programming model admits programs that may have different results, depending on some aspect of the execution. Concurrent programming models are necessarily nondeterministic, because they must interact with external agents that cause events at unpredictable times. Nondeterminism has some notable drawbacks, however: programs become signifficantly harder to test and reason about.

For parallel programming we would like to use deterministic programming models if at all possible. Since the goal is just to arrive at the answer more quickly, we would rather not make our program harder to debug in the process. Deterministic parallel programming is the best of both worlds: testing, debugging and reasoning can be performed on the sequential program, but the program runs faster when processors are added. Indeed, most computer processors themselves implement deterministic parallelism in the form of pipelining and multiple execution units.

While it is possible to do parallel programming using concurrency, that is often a poor choice, because concurrency sacriffices determinism. In Haskell, the parallel programming models are deterministic. However, it is important to note that deterministic programming models are not sufficient to express all kinds of parallel algorithms; there are algorithms that depend on internal nondeterminism, particularly problems that involve searching a solution space. In Haskell, this class of algorithms is expressible only using concurrency.

Conurrency and parallelism differ in the problems they solve and cause, but they are not independent.

Concurrency

Executing two tasks concurrently means that individual steps of both tasks are executed in an interleaved fashion. If you disregard parallelism, you can assume that only one statement is executed at any point in time, but you have (a priori) no guarantee which task gets to execute the next step.

This is useful in some regards:

  • Clearer programming of independent tasks in one program.
  • Allows to deal with IO while computing (e.g. in GUI).
  • Allows for execution of more than one program at a time (concurrency on OS level).

Some of the main challenges are:

  • Maintain data consistency.
  • Avoid deadlocks and livelocks.
  • Determine precise semantics of concurrent processes.
  • Determine static properties that ensure correctness.

Parallelism

Executing two tasks in parallel means that statements are executed at the same time. This is mainly useful for:

  • Improve system throughput by executing programs in parallel (e.g. on multi core systems).
  • Improve runtime of individual programs by utilising multiple CPUs at once.
  • Utilise IO on many machines (e.g. distributed databases).

Key challenges include:

  • Partition problems that allow and develop algorithms that can employ parallelism.
  • Minimise dependencies and communication among the computation units.
  • All the problems brought by concurrency: at least from the point of view of memory, parallel programs look like concurrent ones due to serialisation of memory accesses.
  • Deal with sub-optimal hardware support.

See also this question for distinguishing parallel and distributed computing.

A slightly idealised answer, perhaps...

  • Concurrency is a property of how a program is written. If a program is written using constructions like forks/joins, locks, transactions, atomic compare-and-swap operations, and so on, then it is concurrent.

  • Parallelism is a property of how a program executes. If a program executes on more than one computational unit simultaneously, then it is executing in parallel.

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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