Keum-Sook Ha
Kumi College, Major of Computer Multimedia,
730-711, Kumi, Korea
email: ksha@kumi.ac.kr
and
Yong-Kee Jun
Gyeongsang National University,
Dept. of Computer Science,
660-701, Jinju, Korea
email: jun@race.gsnu.ac.kr
For debugging effectively the shared-memory programs with nested parallelism, it is important to detect efficiently the first races which incur non-deterministic executions of the programs and occur first in the execution. If the first races are detected and removed on-the-fly, then other races will also disappear. The existing on-the-fly technique detects the first races in two passes. However, this method is inefficient in both execution time and memory space, as the size of the access history for each shared variable depends on the maximum parallelism of the program. This paper proposes a new on-the-fly technique for detecting the first races in the two passes. The proposed technique composes the access history and collects frontier-candidate events using happened-before and left-of relations in the first pass, then completes the set of effective candidate events in the second pass. Thereafter, the effective candidate events are reported as the first races. At this point, the size of the access history for each shared variable is constant and is independent to the maximum parallelism. Since the size of the access history for each shared variable is a small constant, both the number of event comparisons and the space complexity for each access to a shared variable are constant. By letting V be the number of shared variables and T be the maximum parallelism, the time and space complexity in the proposed technique are represented as O(V) and O(log2N), respectively. Consequently, the proposed technique makes on- the-fly race detection more efficient and practical for debugging shared-memory programs with nested parallelism.