Browse Prior Art Database

Control Dependence Algorithm for Parallel Programming

IP.com Disclosure Number: IPCOM000036632D
Original Publication Date: 1989-Oct-01
Included in the Prior Art Database: 2005-Jan-29
Document File: 3 page(s) / 17K

Publishing Venue

IBM

Related People

Cytron, R: AUTHOR [+2]

Abstract

A technique is described for efficiently constructing control dependences. It is an improvement over previous concepts which required quadratic space for intermediate computations and multiple passes over the post-dominator tree. The improved algorithm propagates dependences in a single pass through the post-dominator tree. The technique is provably linear for structured programs.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 39% of the total text.

Page 1 of 3

Control Dependence Algorithm for Parallel Programming

A technique is described for efficiently constructing control dependences. It is an improvement over previous concepts which required quadratic space for intermediate computations and multiple passes over the post-dominator tree. The improved algorithm propagates dependences in a single pass through the post-dominator tree. The technique is provably linear for structured programs.

During the execution of a sequential program, the result of some operations, such as branches, determine whether other statements will subsequently be executed. A control dependence graph [1] summarizes these conditions which may affect a statement's execution. Control dependences represent the necessary control flow relationships which must be respected by any execution of the program, whether parallel or sequential. By using control dependence, some of the sequencing in a program is eliminated and thereby expose potential parallelism.

By exposing potential parallelism in sequential programming, the notion of control dependence is useful in other contexts. In vectorization, it provides a more effective and efficient alternative in determining vectorization than guard expressions and allows better sequential code generation when vectorization fails. To the programmer attempting to parallelize sequential programs by hand, it represents necessary information to be provided, along with data dependence. It also provides a basis for improved data dependence analysis and code motion. This work provides a more efficient algorithm for computing control dependence for use in all of the outlined contexts.

ESSENTIALS OF THE ALGORITHM: In this section, first, an example illustrates control dependence, then, it is formally defined, and finally, the algorithm is outlined.

In the example of control dependence, as shown in Fig. 1, S2 is affected by the branch taken in statement S1. However, S10 does not depend on which branch is taken by S1 because both branches eventually cause S10 to execute. S2 is control dependent on the test in S1, but control dependence indicates that S1 and S10 could potentially execute in parallel.

Control dependence can be defined from the control flow graph of a program. We first augment such a graph with distinguished node ENTRY and EXIT. All nodes must be reachable from ENTRY, and EXIT must be reachable from all nodes. Additionally, we add a control flow edge from ENTRY to EXIT.

(Image Omitted)

Definition: Let G be a control flow graph, and let W and V be nodes in G. W is post dominated by V in G, if every directed path from W to EXIT (not including W or EXIT) contains V. Definition: Let G be a control flow graph, and let X and Y be nodes in G. Y is control dependent on X if: 1. there exists a non-null, directed path P from X to Y with all Z in P (excluding X and Y) post-dominated by Y and 2. X is not post-dominated by Y.

1

Page 2 of 3

In other words, from X, there is some edge that defin...