Analysis and modeling of sequential iterative algorithms for parallel and pipeline implementations

The authors present a formal technique to model and analyze sequential iterative algorithms for parallel and pipeline implementations. The objective is to transform a sequential iterative algorithm, described by nested FOR loops, into a static structure called a dependence graph (DG), from which parallelism (if any) can be detected by using both graph-theoretic and algebraic methods. The essence of the method is to find the trace of the variables in an algorithm. The DG of an algorithm is defined in terms of traces.<>