L. Rapanotti
G.M. Megson
University of Newcastle upon Tyne. 1995.
We identify classes of recurrence equations corresponding to algorithms with static tasks and dynamic data dependencies (i.e., changeable at run-time), and establish a relationship between this class of recurrences and other classes of recurrences from the literature. We define localisation techniques for the manipulation of these dynamic recurrences, which allow the subsequent application of conventional space-time mapping for the derivation of regular array designs. Therefore, our approach is a generalisation of high-level synthesis from static algorithms to restricted forms of dynamic algorithms. Its generality provides for semi-automatic tools for the engineering of this type of problems.