Item — HN Reader

The author defines parallelism as splitting a computation into many independent tasks which interact very little, and concurrency as modifying things from different threads/processes/tasklets/whatever without incurring in hairy bugs. (As if it is ok to have hairy bugs in parallelism, or the lack of interaction rules them out).

Is this the standard/accepted/correct definition ? Or he just made it up ?

My understanding is that parallelism is concerned with actual execution of the code in parallel on the machine. Whereas concurrency is concerned with the semantics of the language, i.e. whether it is possible in the language to define multiple "tasks" that need not be run in serial order.

Whether those tasks actually run in parallel or not, is a concern of parallelism, not of concurrency.

2 comments

Concurrency does not necessary mean parallelism; you can have have threads interacting in a time-shared manner on the same processor.

Parallelism implies concurrency; a parallel program has threads of execution (which may not actually be shared-memory software threads) that are executing simultaneously.

The author's definition of parallelism is wrong - at least, it's different from the one myself and everyone else I know in the high performance computing and systems research community use. Many interesting problems are not embarrassingly parallel, and figuring out how, exactly, such problems can be solved efficiently in parallel is hard. (And efficiency is a solution requirement, since it's not worth the parallelization effort if you don't achieve it.)

I think the point the author is trying to arrive at is parallelism does not necessarily mean shared-state across threads. Which is true, and I share his sentiment that we should probably not reach for shared-state threads to solve our parallel problems.

According to http://en.wikipedia.org/wiki/Concurrency_(computer_science) concurrency is concerned with executing tasks simultaneously, whether on multiple cores or in time-shared threads, in a way where the tasks may interact.

Then the wikipedia article doesnt quite match with whats taught in CS courses. In any case the blog post does not agree with the wikipedia position either. I dont think it helps to overload standard definitions with different concepts, one should use new/different words.

  "Concurrency should not be confused with parallelism
  Concurrency is a language concept and parallelism is a  
  hardware concept. Two parts are parallel if they execute
  simultaneously on multiple processors. Concurrency and
  parallelism are orthogonal: it is possible to run
  concurrent programs on a single processor (using
  preemptive scheduling and time slices) and to run
  sequential programs on multiple processors (by
  parallelizing the calculations)."

-- page 25 of Programming Paradigms for Dummies: What Every Programmer Must Know a book chapter by Peter Van Roy http://www.info.ucl.ac.be/~pvr/VanRoyChapter.pdf [Pdf]

Here is SO's take http://stackoverflow.com/questions/1050222/concurrency-vs-pa...

and from GHC Mutterings http://ghcmutterings.wordpress.com/2009/10/06/parallelism-co...

The posts definition does essentially agree with your definition, because it is concerned only with software.

You write parallel software (use parallel algorithms), when you want to exploit hardware parallelism (usually multiple CPUs) to do one thing. While you write concurrent software to do multiple things at once, that require same resources (CPUs, Memory, etc.). There is theory of parallel algorithms that is concerned with extending of big-O notation to multiple processors and performance effects of inter-processor communication, while concurrent algorithm theory deals with synchronization problems.

In essence one can illustrate the difference by looking at synchronization primitives used: while concurrent code mostly uses locks, parallel code uses barriers. And on many parallel supercomputers of eighties, synchronization of parallel code was implicit, because all processors had common clock and thus you could do all synchronization by simply knowing that what given processor is doing when.

This is relevant to this "threads are useless" debate by the fact, that threads are meant for concurrency and not parallelism, because they implicitly share resources (memory) that is mostly not required to be shared. Large part of complexity of modern multiprocessor hardware (and operating systems) comes form effort to detect which part of memory is shared and which is used only by one processor (or thread). Because sharing whole memory array incurs non-trivial contention and precludes you from doing any meaningful caching.

I wouldnt say they are my definition :-), it is the standard one. Re-defining same terminology as something else or making them open to interpretation, is detrimental. More so when the point of view could be contentious.

Ideally definitions shouldnt only be essentially the same (for some values of essence), but obviously/unraguably the same. Or else we discuss definitions :-)

The point I was trying to make is simple. By conventional terminology: Concurrency deals with semantics, parallelism deals with execution. I dont see how

  parallelism as splitting a computation into many independent tasks which interact very little,
  and concurrency as modifying things from different threads/processes/tasklets/whatever without
  incurring in hairy bugs.

translates into the standard definition. What the author describes as parallelism could easily be concurrency if the split happens at the semantic level.

BTW concurrency needn't have any explicit synchronization primitives at all and needn't have anything to do with synchronized clocks. Semantics does not care about execution or clocks it cares only about meaning. Since parallelism deals with execution, there clocks could become relevant.

Consider list comprehension in Python. Its a concurrency primitive. But whether the elements of the list are computed simultaneously, depends on how the Python code is executed and hence an issue of parallelism.

"Concurrent code" and "parallel code" terminology can also be confusing. If a piece of code describes/defines things you want to compute, then it can only be concurrent and not parallel. But if the code also describes how it is going to be executed in the hardware then it could be called parallel. So I am not confident of the view

  threads are meant for concurrency and not parallelism

I have no difficulty in accepting that threads are not always the right abstraction. Shared mutable state is a significant problem.

But forwarding that argument by conflating conventional terminology as was done in the article hardly helps.