Abstract
A new methodology is proposed for mapping and partitioning arbitraryn-dimensional nested loop algorithms into 2-dimensional fixed size systolic arrays. Since planar VLSI arrays are easy to implement, our approach has good feasibility and applicability. In the transformation process of an algorithm, we take into account not only data dependencies imposed by the original algorithm but also space dependencies dictated by the algorithm transformation. Thus, any VLSI algorithm generated by our methodology has optimal parallel execution time and yet remains space-time conflict free. Moreover, a theory of the least complete set of interconnection matrices is proposed to reduce the computational complexity for finding all possible space transformations for a given algorithm.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
D. I. Moldovan and J. A. B. Fortes, Partitioning and mapping algorithms into fixed size systolic arrays.IEEE Trans. Comput., 1986, C-35 (1), 1–12.
D. I. Moldovan, On the design of algorithms for VLSI systolic arrays.Proc. IEEE, 1983, 71(1), 113–120.
Yiwan Wong and Jean-Mare Delosme, Optimal Systolic Implementations ofN-dimensional Recurrences. IEEE ICCD'85 pp. 618–621.
Author information
Authors and Affiliations
Additional information
This research was supported by National High-tech Program (863 Program) of P. R. China.
Rights and permissions
About this article
Cite this article
Liu, H., Wang, W. & Zhang, D. A methodology for mapping and partitioning arbitraryn-dimensional nested loops into 2-dimensional VLSI arrays. J. of Compt. Sci. & Technol. 8, 221–232 (1993). https://doi.org/10.1007/BF02939529
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF02939529