Paper Info
Title
Using an oracle to measure potential parallelism in single instruction stream programs.
Abstract
Horizontally microprogrammable CPUs belong to a class of machines having statically schedulable parallel instruction execution (SPIE machines). Several experiments have shown that within basic blocks, real code only gives a potential speed-up factor of 2 or 3 when compacted for SPIE machines, even in the presence of unlimited hardware. In this paper, similar experiments are described. However, these measure the potential parallelism available using any global compaction method, that is, one which compacts code beyond block boundaries. Global compaction is a subject of current investigation; no measurements yet exist on implemented systems. The approach taken is to first assume that an oracle is available during compaction. This oracle can resolve all dynamic considerations in advance, giving us the ability to find the maximum parallelism available without reformulation of the algorithm. The parallelism found is constrained only by legitimate data dependencies, since questions of conditional jump directions and unresolved indirect memory references are answered by the oracle. Using such an oracle, we find that typical scientific programs may be sped up by anywhere from 3 to 1000 times. These dramatic results provide an upper bound for global compaction techniques. We describe experiments in progress which attempt to limit the oracle progressively, with the aim of eventually producing one which provides only information that may be obtained by a very good compiler. This will give us a more practical measure of the parallelism potentially obtainable via global compaction methods.
Year
DOI
Venue
1981
10.1145/1014192.802448
MICRO
Keywords
Field
DocType
basic block,practical measure,global compaction technique,real code,block boundary,potential parallelism,conditional jump direction,spie machine,single instruction stream program,potential speed-up factor,global compaction,global compaction method,upper bound
Instruction-level parallelism,Computer science,Upper and lower bounds,Parallel computing,Oracle,Compiler,Data parallelism,Jump
Conference
Volume
Issue
ISSN
12
4
1050-916X
Citations 
PageRank 
References 
8
4.74
7
Authors
2
Name
Order
Citations
PageRank
Alexandru Nicolau12265307.74
joseph a fisher21410264.50