[Solved]: Why doesn't parallelism necessarily imply non-determinism?

Problem Detail: 

I'm a student reading a book on threads. And I got when I got to non-deterministic and parallel programs, I got a bit confused. I hope you can help me out.

I understand the difference between concurrency and parallelism. I get that concurrent programs are non-deterministic depending on the precise timing of events. "But parallelism doesn't necessarily imply non-determinism" - as said in the book. Why is that?

Does that imply that it's all dependent on the languages that support parallelism. Which implies that these languages should execute parallel programs in a deterministic manner?

Another question that I have is that the timing of events of concurrent programs depend on what exactly on what exactly? The architecture of the machine?

Asked By : macmania314

Answered By : Wandering Logic

The book is using the term non-deterministic in two different ways. In concurrent computations and parallel computations the order in which the computations occur is non-deterministic. The final result however may (or may not) be deterministic.

Consider the following example:

thread A        thread B --------        -------- x = 0           y = 1 

The x assignment might happen before the y assignment, or the y assignment might happen before the x assignment, so the order is non-deterministic, but the end result after both threads finish is that x contains the value 0 and y contains the value 1. So the result is deterministic.

The two major ways in which we achieve deterministic results from non-deterministic ordering is (a) by performing completely independent computations in different threads and (b) by taking advantage of operations that are commutative and/or associative. An example of case (b) is if you have an atomic addition operator:

thread A               thread B --------               -------- atomic_increment(x)    atomic_increment(x) 

At the end of the computation x will have a value 2 larger than it had before the computation, no matter whether thread A's increment happened before thread B's increment, or the other way around.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/41628