Browse Prior Art Database

On-The-Fly Detection Of Access Anomalies

IP.com Disclosure Number: IPCOM000149392D
Original Publication Date: 1988-Oct-31
Included in the Prior Art Database: 2007-Apr-01
Document File: 22 page(s) / 1M

Publishing Venue

Software Patent Institute

Related People

Schonberg, Edith: AUTHOR [+2]

Abstract

On-The-Fly Detection Of Access Anomalies by Edith Schonberg Ultracomputer Note 149

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 7% of the total text.

Page 1 of 22

On-The-Fly Detection Of Access Anomalies by
Edith Schonberg

Ultracomputer Note # 149

October, 1988

   This work was supported under the Applied Mathematical Sciences Program of the U.S. Department of Ener- gy under contract DE-FG02-88ER25052.

[This page contains 1 picture or other non-text object]

Page 2 of 22

[This page contains 1 picture or other non-text object]

Page 3 of 22

ABSTRACT

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.

1. Introduction

   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:

'~n
exception to this is chaotic relaxation [Bau].

[This page contains 1 picture or other non-text object]

Page 4 of 22

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[2] 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...