Report Number: CSL-TR-81-209
Institution: Stanford University, Computer Systems Laboratory
Title: Dynamic detection of concurrency in do-loops using ordering matrices
Author: Wedig, Robert G.
Date: May 1981
Abstract: This paper describes the data structures and techniques used in dynamically detecting concurrency in Directly Executed Language (DEL) instruction streams. By dynamic detection, it is meant that these techniques are designed to be used at run time with no special source manipulation or preprocessing required to perform the detection. An abstract model of a concurrency detection structure called an ordering matrix is presented. This structure is used, with two other execution vectors, to represent the dependencies between instructions and indicate where potential concurrency exists. An algorithm is developed which utilizes the ordering matrix to detect concurrency within determinate DO-loops. It is then generalized to detect concurrency in arbitrary del instruction streams.
http://i.stanford.edu/pub/cstr/reports/csl/tr/81/209/CSL-TR-81-209.pdf