3.5 Removing Data Dependences

Up to this point in the chapter, we have concentrated on describing OpenMP's features for parallelizing loops. For the remainder of the chapter we will mostly discuss how to use these features to parallelize loops correctly and effectively.

First and foremost, when parallelizing loops it is necessary to maintain the program's correctness. After all, a parallel program is useless if it produces its results quickly but the results are wrong! The key characteristic of a loop that allows it to run correctly in parallel is that it must not contain any data dependences. In this section we will explain what data dependences are and what kinds of dependences there are. We will lay out a methodology for determining whether a loop contains any data dependences, and show how in many cases these dependences can be removed by transforming the program's source code or using OpenMP clauses.

This section provides only a brief glimpse into the topic of data dependences. While we will discuss the general rules to follow to deal correctly with dependences and show precisely what to do in many common cases, there are numerous special cases and techniques for handling them that we do not have space to address. For a more thorough introduction to this topic, and many pointers to further reading, we refer you to Michael Wolfe's book [MW 96]. In addition, a useful list of additional simple techniques for finding and breaking dependences appears in Chapter 5 of [SGI 99].