L. Rapanotti
G.M. Megson
University of Newcastle upon Tyne. 1994
As synthesis techniques for regular parallel computations become more mature, wider and more complex classes of algorithms can be treated in a systematic way. In this paper we show how algorithms expressed as systems of integral recurrence equations can be systematically manipulated into regular parallel computations. Integral recurrence equations are recurrences characterised by data dependencies defined through integral functions. We will show how the basic synthesis techniques of uniformisation, scheduling and allocation which apply to linear recurrences can be generalised to integral recurrences. We will also show how a parameterisation of the uniformisation technique allows a trade-off (between the number of processing elements and the number of data channels) in the derived regular array designs.