Channels ▼

Cameron and Tracey Hughes

Dr. Dobb's Bloggers

Does Parallelism Affect Determinism?

June 25, 2010

If you have two threads executing the same code currently on separate cores using the same input but producing different results, is that code nondeterministic?

Cameron and I recently had a discussion with a colleague that described his program as such. We thought the use of the term "nondeterministic" for the situation he was describing was a bit odd....

First of all what does "determinism" and "nondeterminism" mean? According to the NIST (National Institute of Standards and Technology) a "deterministic algorithm" is "an algorithm whose behavior can be completely predicted from the input." They go on to say that "... Each time a certain set of input is presented, the algorithm does the same computations and gives the same results as any other time the set of input is presented."

Of course this is what we want, our colleague wanted, any programmer wants. And that single answer is the correct answer. There can be only one! It has functional correctness. We would not like our programs producing different outputs for 1 + 1, sometimes its 2 and other times its 4.

What about a nondeterministic algorithm?

A conceptual algorithm with more than one allowed step at certain times and which always takes the right or best step.

Also the key to nondeterministic algorithms besides allowing more than one step from a set input is they allow for more than one acceptable output or one acceptable output with multiple paths to reach it.

We can represent the algorithm as a finite state machine. Any problem can be represented as a finite state machine and the solution (solutions) as paths through that machine.

Figure 1(a): Deterministic finite state machine;

Figure 1(b): Nondeterministic finite state machine;

Figure 1(a) shows a deterministic and 1(b) a nondeterministic FSM defined by the following:

FSM = (S,I,f,so,F)

where:

  • S is a finite set of states
  • I is the finite set of inputs (in this case 1,0)
  • so is the initial state or set of states
  • F is a subset of S which represent the final (accepted) states
  • f is the transition function

The differences between the state machines are the initial state (for NFSM there can be a set of initial states) and the transition function. The fd (deterministic transition function) assigns a single state for each unique input-state pair where fn (nondeterministic transition function) can assign a set of states for each input state pair. Table 1 is a state table comparing the next states from the input-state pairs for each type of state machine.

Table 1: DFSM and NFSM state table comparison

The final or accepted state is determined not just by the input but the state the state is in at a current time.

Some problems are inherently one or the other. Any mathematical function is deterministic, of course. There may be several routes from your point of origin to your final destination when booking a flight. By definition, NP complete problems are nondeterministic problems that cannot be solved in polynomial time. A game would be pretty boring if it was deterministic. All those possible paths to victory is what makes you want to play. Nondeterminism determines the replay value of a game. Right now we are playing Way of the Samurai 3, Yakuza 3, and Fallout 3. These games are the ultimate exercise in nondeterminism. In these games, using the same character, there are many paths through the game but there are only a few outcomes. I can't tell you how many ways your character will still end up blowing up the city of Megaton in Fallout. That's the replay value.

But there are gray areas. If we have an algorithm that utilizes a random number generator, then we would not be able to predict the output even with the same input. Here, there are random states changes causing different results. Would it be considered deterministic or nondeterministic? Also nondeterministic algorithms can be converted to deterministic algorithms.

So going back to our discussion with our colleague about his wacky code, restating the original situation:

If you have two threads executing the same code currently on separate cores using the same input but producing different results, is that code nondeterministic?

The whole scenario is that it was exhibiting the expected results with sequential execution and also when threads were added running on a single core machine. But when executed on a multicore machine, the code produced unstable results.

Can deterministic code mysteriously convert to nondeterministic code? Something had the potential to cause the program to have unstable results but was not revealed until the code ran on multiple cores and affected the output. There could be something external to the code (maybe another thread) that changes some value shared by that code that was unexpected. The unexpected modification did not take place when the threads executed on a single core (due to timing) but when executing on separate cores the modification affected the output. There can be other timing issues when code is run on multiple cores. Even (faster or slower) processors can cause values to be written to memory or not written to memory unexpectedly. The speed of I/O devices, global variables should also be looked at. This can cause a deterministic FSM to require additional states and therefore new paths through that algorithm converting the deterministic code to nondeterministic code.

Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.
 


Video