Adi Levin's Blog for programmers

December 13, 2010

Determinism

Filed under: Multithreading,programming — Adi Levin @ 6:30 pm
Tags: ,

Multithreaded computations are sometimes non-deterministic, meaning that they produce different results in different runs that have the exact same input. In some cases, this is a result of insufficient synchronization between threads, causing Race Conditions (A Race Condition is actually defined as a critical non-deterministic behavior). In other cases the non-deterministic behavior is not critical, but still we would like to avoid it, because debugging  a non-deterministic program is more problematic.

In the following, I discuss two common reasons for non-detemrinism:

Order of floating-point computations

Let’s consider a multithreaded program that performs summation of an array of floating point numbers. Suppose that each thread computes the sum of a part of the array, and at the end the partial sums are summed together. The order at which the numbers are summed is imporant. In floating-point arithmetic, (a+b)+c is not always equal to a + (b+c). Since the number of running threads can be different from one run to another, and the timing of threads is unpredictable, the order in which the summation is done may be non-deterministic, depending on how the program is written.

One way to avoid this problem, if given the choice, is to use integer arithmetic instead of floating-point.

Another way is to divide the task into a constant number of partial sums that do not depend on the number of threads, then store the intermediate result of each task in an array, and finally sum-up that array in one thread. This way, the order at which numbers meet each-other is not random.

Order of insertion to a container

In a fork-join multithreading model, it is often useful to collect the outcome of tasks in a thread-safe container. After the multithreaded fork-join part is completed, the results in the container are used as input to the next part of the program. The problem is that insertion into the container can happen in an unexpected order. This causes the next part of the program to behave in a non-deterministic way.

One way to solve this problem is to add a sort operation after fork-join part. Simply sort the data in the container, and this will guarantee a consistent input to the next stage of the program.

Another way to solve this is to write the code in a way that each task result knows a-priori its place in the container – which is independent of timing and of the number of running threads.

Advertisements

Leave a Comment »

No comments yet.

RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Blog at WordPress.com.

%d bloggers like this: