Next: Abstract Machine Models Up: Relaxing Control Flow Previous: Control Dependence Analysis

Executing Multiple Flows of Control

Control dependence analysis discovers parallelism from across different regions of code, each of which may have its own flow of control. In the example above, control dependence analysis shows that the bar function can run concurrently with the preceding loop. However, a uniprocessor can typically only follow one flow of control at any time. A uniprocessor cannot fetch and execute the instructions from within the loop while following the arbitrary control flow that may be present in the bar function.

Support for following multiple flows of control is necessary to fully exploit the parallelism uncovered by control dependence analysis. Multiprocessor architectures are a general means of providing this support. Each processor of a MIMD multiprocessor can follow an independent flow of control. At the other extreme, it is sometimes possible to generate uniprocessor code that corresponds to pursuing multiple flows of control in the original computation. A small number of code segments can be packed together by generating different versions of the code for every possible combination of control flow. However, in general, combining independent control flows can lead to significant code expansion.



Next: Abstract Machine Models Up: Relaxing Control Flow Previous: Control Dependence Analysis


Bob Wilson