Final Report, EPSRC Grant GR/L35089/01: systolic and regular array composition environment (SARACEN)

Designers of so-called regular parallel algorithms, which include systolic arrays as a special case, have now acknowledged the need for suitable software tools in the design process. The principal aim of this project is to provide a prototype environment for the mapping and scheduling of multi-phase algorithms into regular arrays. The principles of the mapping process are now well understood and an environment of synthesis of single phase algorithms already exists at Newcastle. Our intention is to extend and augment this existing environment with software to implement a compositional algebra which allows the construction of multiphase algorithms from single phase components. Necessarily this involves the development of polytope manipulation libraries to implement the composition operators which work on convex sets together with symbolic rewriting rules to implement design decisions. The practical value of the project is to be able to use the system for the semi-automatic design of complex filtering algorithms such as the Kalman Filter which currently require an ad-hoc approach