Prism Evaluation

Data Dependencies and Races

Data dependencies occur when data is shared between threads in an application and can cause errors (Data Races) if not resolved at all, with mutexes etc, or can lead to poor performance if they are dealt with inefficiently (serialization). Data dependencies can be hard to spot in large applications since it is difficult to reason about all of the location in the code which reference the same shared variable. The situation is particularly bad in languages like C where pointers are used extensively so data can be shared by references to its address and not just through explicitly shared variables. Prism helps deal with these problems in two ways.

Firstly, Prism performs dependency analysis between all of the threads active in each slice. This includes existing PThreads in the source code as well as force threads introduced within Prism. This means that by using Prism to evaluate threading before implementing it, you will be made aware of any data dependencies which may be introduced allowing resolution to be planned in advance.

Secondly, Prism will perform Data Race detection between existing PThreads in order to catch subtle bugs caused by unsynchronized shared access of data by 2 or more threads. Once a data race is detected, Prism helps you track down its source in the code and allows you to evaluate the schedule impact of alternative resolution strategies.

This tutorial provides an example of how these features can be used to verify and evaluate an example.

Setup

This Tutorial assumes you are familiar with the basic use of Prism as detailed in the previous tutorials and have imported and built the tutorial examples.

Data Dependencies

Here we will look at how Prism deals with data dependencies introduced to sequential code by forcing threads.

Prism state after setup is complete. (Click to Enlarge)

In the schedule view we see that there is some parallelism but there are a lot of gaps in the schedule where only a single core is running implying that there is some constraint causing to code to be executed in a sequential manner. Typically this is caused by data dependencies.

Prism displays all of the dependencies it has found between threads, both forced and pthreads in the code, in the Data Dependency view.

The data dependency view basically provides a table of all of the threads between which there are data dependencies. The dependencies are identified in terms of source and destination accesses in separate threads with the source being the earlier access in the sequential trace and the destination being the later access. For each pair of threads there may be any number of dependencies which are listed hierarchically by function then by source line.

The Data Dependency view with all the dependencies expanded. (Click to Enlarge)

Each row in the table defines the type of the dependency (Read After Write, Write after Read and Write after Write). Right clicking on any of the rows in the table will allow you to annotate the source code with the selected data dependency or set of data dependencies for rows containing thread or function pairs.

The most powerful feature of this view is accessed via the Resolution column of the table. Here you can select a potential resolution method to model in the schedule view. Each dependency caused by forcing a thread must be resolved when implemented in the actual code other wise a data race will occur. Resolutions are implemented by either synchronizing the access to shared data between threads, with locks or similar, or by restructuring the code in such a way to remove the dependency if the threads do not actually need to share the data.

By default, Prism provides 2 resolution models. None, which removes the dependency from consideration in the schedule, and Serialized, which models synchronization between the last access to the shared data in the source thread segment and the first access in the destination thread. Lets go through the process of understanding the dependencies and evaluating the possible resolutions.

Firstly lets get a better understanding of the dependencies which occur between the 2 instances of the threadFunction thread that have been created.

Inspect the source code, now annotates with the source and 2 destinations for the 2 dependencies. Note the calls to burnCycles. Clearly the static aSharedVar is the source of the dependency here. Since the code is sequential and we have forced the thread the Thread Segment must be the entire call to threadFunction, as if it was passed directly into a pthread_create call and contain no further calls to the pthread API to cause synchronizations. This means that the current Serialized resolution will schedule the threads to run sequentially between the first access to aSharedVar and the last, 2 lines later. This can be seen clearly in the schedule view as follows

Two arrows representing the yield of one thread (in grey) and the data dependency (in purple) between the 2 threads show how the scheduling has been implemented. The data dependency arrow corresponds to the last access to the dependency in one thread to the first access in the second thread. With Serialized resolution, this arrow will always point forward in time.

A closer look at the Serialized schedule. (Click to Enlarge)

Applying an alternative resolution is straightforward:

The schedule view will update and produce a new performance estimate for 2 cores.

A closer look at the None schedule. (Click to Enlarge)

Notice that the dependency arrow is now pointing backward in time, indicating that the accesses are now occurring out of order compared to the original sequential schedule. If the results of the computation are dependent by the order of accesses to this data then this represents a Data Race.

Finding Data Races

Data Races can be found by Prism in traces which contain more than on thread. Prism will flag as a data race any accesses to a shared memory location by 2 or more threads without an intervening synchronization such as a mutex or a join.

Note that in the histogram view of the PAD file the Data Race graph now contains peaks at the various points in the trace where multiple threads are causing data races. This will guide you to the trouble spots which can only be seen in detail once loaded in a slice.

A trace containing PThreads with data races. (Click to Enlarge)

The Data Races view is similar to the data dependency view in its layout except that the dependencies are organized into a tree containing Thread -> Access Location -> Cycle. This provides more detail about the temporal location of the data race in the trace making it easier to find the unexpected circumstances which can lead to the existence of data races. Right clicking on the rows allows for annotating of source code and marking of the schedule as for data dependencies.

In the schedule, the dependency is indicated by a red arrow marking the dependency causing the race. To help locate the dependency in the schedule, generate markers from the Data Race view as follows.

Since the data race is just a data dependency, it can be resolved in the same way as resolving a normal data dependency. By default the resolution is None since the current implementation ignores the presence of the dependency resulting the the data race when it should not have. Lets look at changing the resolution as follows

The resolved data race. (Click to Enlarge)

The red data race arrow is now dashed and the estimated schedule indicates the performance cost of implementing the fix. Note that the None schedule is still potentially valid since it may be the case that the dependency causing the race can still be successfully removed without the need for additional synchronization between threads.

We will look in detail at what resolving data races and dependencies translates to in PThread code in the next tutorial.

Proceed to the Next Tutorial