Limits of Control Flow on Parallelism
Monica S. Lam and Robert P. Wilson
Computer Systems Laboratory
Stanford University, CA 94305
This research was supported in part by DARPA contract N00039-91-C-0138
and by an NSF graduate fellowship.
In Proceedings of the 19th Annual International Symposium on Computer
Architecture Gold Coast, Australia, May 19-21, 1992, pp. 46-57.
Copyright (C) 1992 by ACM, Inc.
This paper discusses three techniques useful in relaxing the constraints
imposed by control flow on parallelism: control dependence analysis,
flows of control simultaneously, and speculative execution. We evaluate these techniques
by using trace simulations to find the limits of parallelism for
machines that employ different combinations of these techniques.
We have three major results.
First, local regions of code have limited parallelism, and
control dependence analysis is useful in
extracting global parallelism from different parts of a program.
Second, a superscalar processor is fundamentally
limited because it cannot execute independent regions of code
concurrently. Higher performance can be obtained with machines,
such as multiprocessors and dataflow machines, that
can simultaneously follow multiple flows of control.
Finally, without speculative execution to allow instructions to execute
before their control dependences are resolved, only modest amounts of
parallelism can be obtained for programs with complex control flow.