ABSTRACT
The specification of the algorithm denotes the first stage of the process, in which a functional description of the algorithm is provided as recurrence
equations, or some equivalent such as single assignment code. The design process terminates with the implementation of the algorithm either as par allel code for a target machine or as specialised hardware. The remaining design steps (contained within the dotted box in the figure) constitute the core of the synthesis method, in which a regular spreading of the compu tations of the algorithm in space and time is obtained, so that the data dependence relations between computations are exposed and the maximal inherent parallelism of the algorithm can be exploited. A spatial distribu tion is obtained by representing the computations as the nodes of a graph. A temporal distribution follows from the partial order induced by the data dependence relations, and the assumption that a constant time cycle is as sociated with the execution of each computation. Regularity is enforced through systematic transformations of the specification.
