5
$\begingroup$

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?

|cite|improve this question
$\endgroup$
  • $\begingroup$ Which book is that? $\endgroup$ – ultimate cause Jun 23 '16 at 17:56
4
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ hey @Wandering Logic, to achieve deterministic results - we ensure that no data race ensures then on parallel or concurrent programs? Thanks. $\endgroup$ – macmania314 Apr 21 '15 at 15:27
  • 1
    $\begingroup$ Data-race free is necessary, but not sufficient. When your critical sections are not commutative you can be data-race free but non-deterministic. For example suppose you have one critical section that prints 0 and another that prints 1. There's no data-race, but the program sometimes outputs 0, 1 and sometimes 1, 0. $\endgroup$ – Wandering Logic Apr 21 '15 at 18:06
1
$\begingroup$

Take matrix-matrix multiplication which can be done in parallel. Initially one node (thread, computer, or whatever), call it N0, divides the two matrices into blocks, and distribute those blocks to the other nodes. All nodes now compute the product of their matrix blocks, and send the result back to N0. Finally N0 constructs the matrix, resulting from the multiplication, by combining the blocks back together.

That is work done in parallel, with some overhead (distributing blocks, sending blocks back etc.), but completely deterministic!

Concurrency is usually found in multiplayer games, booking systems etc., whereas parallelism is often found when dividing a large problem into smaller problems, and distributing the small problems among nodes.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ hey @Jonas, so you're implying that the process of parallel programs is deterministic by nature then since the big idea is to break the work down then get an end result? Thanks. $\endgroup$ – macmania314 Apr 21 '15 at 15:25
  • $\begingroup$ Yes and no. You could easily design a non-deterministic, parallel algorithm which solved a given problem, especially if it is a statistical sampling problem. But most of the time you require a deterministic result, and hence you design a deterministic parallel algorithm. Take again matrix-matrix multiplication. There is only one correct result, and it is completely deterministic. So a non-deterministic matrix-matrix multiplication algorithm would be of little interest. $\endgroup$ – Jonas Camillus Jeppesen Apr 22 '15 at 16:25
1
$\begingroup$

Parallelism studies systems that contain several parts where computations happen at the same time. Let's call these parts nodes. If all the nodes are deterministic (e.g. no random generator) and they all execute instructions at the same speed (i.e. they all have the same clock), then the system as a whole is deterministic: the state at time $t+1$ is fully determined by the behavior of the system at time $t$ and the way each node executes instructions.

An example of a parallel system is a microprocessor or microcontroller. All but the most basic processors have multiple subsystems that execute in parallel. Each instruction moves through the stages of a pipeline, and at any given time, the processor is in the process of executing many successive instructions, potentially one at each stage of the pipeline. It is essential for the design of the processor to know exactly when the data for an instruction will reach each component, and how much time (how many clock cycles) it takes to go from one component to the next.

Hard real time systems are also deterministic, and often parallel. For example, the controls of a vehicle consist of many processors, and the critical parts (engine, brakes — not e.g. the entertainment system) operate at a known speed with known reaction times. There is a class of programming languages, synchronous programming languages, designed to program such systems, which model parallel execution in a fully deterministic framework.

There are also higher-level parallel systems which are deterministic even though the lower-level layer isn't. This is typically the case when doing numerical processing. When a computation can be parallelized, the parts are dispatched to different processors, and the exact time they take to process their parts can depend on how fast each node is, how much communication bandwidth is available between the various nodes, on how the data is arranged, etc. The duration of the computation is not deterministic, but the result is: it's equivalent to running all the computations sequentially on a single processor. The reason such computations can be parallelized is that they contain parts that don't depend on each other, so it doesn't matter in what order these parts are executed — or whether some are executed at the same time on different nodes.

Terminology isn't completely standardized, but generally parallelism is used when systems are deterministic (at least as far as the result of the computation is concerned), and concurrency when systems are not deterministic. Concurrency studies systems where events can occur at unpredictable times, such as user input, network reception, etc. See also Distributed vs parallel computing

|cite|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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