Question

(Parallel High Performance Computing)

Explain the difference between lexically forward and lexically backward and give an example of each?

Answer 1

Consider two statements S and S^'. They are said to be data dependent if f there is one access each in S and S^' to the same data item and at least one of the two accesses is a write. Data dependencies occur when two satement compute data that are used by other statements.

Data dependencies are represented by a data dependence graph. In this graph nodes are statements of the program and directed arcs represents the dependencies between the statements.

These directed arcs are classifeid into forward and backward arcs.

An arc or dependence from S to S^' is said to be lexically forward when  S^' follows S in the program order.

Example

Consider the following statements

Corresponding dependency graph which is lexically forward is shown below

An arc or dependence from S to S^' is said to be lexically backward when S follows S^' in the program order.