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.