WIT Press


Synthetic Methodologies For An Optimal Time-space Algorithm Complexity Distribution

Price

Free (open access)

Paper DOI

10.2495/HPC000171

Volume

23

Pages

12

Published

2000

Size

1,145 kb

Author(s)

M. P. Bekakos

Abstract

Synthetic methodologies for an optimal time-space algorithm complexity distribution M.P. Bekakos Department of Informatics, Athens University of Economics and Business, 104 34 Athens Abstract A challenging problem in systolic processing is to develop methodologies for mapping algorithms into systolic architectures. Systolic Arrays (SAs) can be produced not only through a try and error approach but also using optimal synthetic methods. Through the proposed procedure herein which is based on the dependence method processor-time optimal SAs can be synthesized. The resulting systolic designs are optimal in both aspects, the hardware used and the time complexity achieved. 1 Introduction Various methodologies have been proposed for mapping algorithms into sys- tolic architectures. These methods transform the algorithmic descriptions which do not determine concurrency or communication to functions which distribute algorithm operations into time and space. This transformation procedure i

Keywords