Report Number: CSL-TR-82-231
Institution: Stanford University, Computer Systems Laboratory
Title: Dynamic detection of concurrency in DEL instruction streams
Author: Wedig, Robert G.
Date: February 1982
Abstract: Detection of concurrency in Directly Executed Languages (DEL)
is investigated. It is theorized that if DELs provide a
minimal time -space execution of serial programs, then
concurrency detection of such instruction streams approaches
the minimum execution time possible for a single task without
resorting to algorithm restructuring or source manipulation.
It is shown how DEL encodings facilitate the detection of
concurrency by allowing early decoding and explicity
detection of dependency information. The decoding and
dependency algorithms as applied to DELs are developed in
detail. Concurrency structures are presented which facilitate
the detection process. Since all concurrency is capable of
exploitation as soon as it is known that the code is to be
executed, i.e., the result of the branch is known, it is
proven that all explicit parallelism can be detected and
exploited using the techniques developed.