On-The-Fly Detection Of Access Anomalies
Original Publication Date: 1988-Oct-31
Included in the Prior Art Database: 2007-Apr-01
Software Patent Institute
Schonberg, Edith: AUTHOR [+2]
On-The-Fly Detection Of Access Anomalies by Edith Schonberg Ultracomputer Note 149
On-The-Fly Detection Of Access Anomalies by
Ultracomputer Note # 149
This work was supported under the Applied Mathematical Sciences Program of the U.S. Department of Ener- gy under contract DE-FG02-88ER25052.
Access anomalies are a common class of bugs in shared-memory parallel pro- grams. An access anomaly occurs when two concurrent execution threads both write (or one thread reads and the oth.er writes) the same shared memory location. Approaches to the detection of access anomalies include static analysis, post-mortem trace analysis, and on-the-fly monitoring.
A general on-the-fly algorithm for access anomaly detection is presented, which can be applied to programs with both nested fork-join and synchroniza- tion operations. The advantage of on-the-fly detection over post-mortem analysis is that the amount of storage used can be greatly reduced by data compression techniques and by discarding information as soon as it becomes obsolete. In the algorithm presented, the amount of storage required at any time depends only on the number V of shared variables being monitored and the number N of threads, not on the number of synchronizations. Data compression is achieved by the use of two techniques called merging and sub- traction. Upper bounds on storage are shown to be V x N' for merging and V x N for subtraction.
In shared-memory parallel programs, a common and vexing "class of parallel bugs arise from access anomalies. By shared-memory parallel programs, we mean programs in which concurrent execution streams directly read and write shared-memory. An. access anomaly occurs when two concurrent execution streams both write (or one reads and the other writes) the same memory location. Access anomalies are almost always bugs.' They result either from a violation of data dependences or from miscellaneous program logic errors, such as in sub- scripting or addressing. In Ada access anomalies render a program erroneous, that is, they have undefined semantics.
To illustrate an access anomaly, consider the small code sequence below, written in For- tran extended by a parallel doali:
exception to this is chaotic relaxation [Bau].
The dynamic parallel flow of control for this program is shown in Figure 1, where each separate execution stream is labeled by an identifier Ti. Since location A is written by exe- cution stream T2 and read by execution streams T3 and T,, there is an access anomaly. (In this case, the doall does not respect some data dependence in the original sequential program.)
Access anomalies are often difticdt to locate using conventional debu...