CANONIC AND GENERALIZED MAPPING FROM ALGORITHMS TO ARRAYS - A GRAPH BASED METHODOLOGY.

S. Y. Kung, P. S. Lewis, S. N. Jean

Research output: Contribution to journalConference article

2 Scopus citations

Abstract

This paper develops a methodology of mapping regular computations onto special-purpose, algorithm-oriented processor arrays. A canonic mapping method, proposed in this paper, is shown to be suitable for shift invariant Dependence Graphs (DGs). This mapping method consists of three design stages, each utilizing an appropriate canonic form. For example, in order to represent the regularity inherent in algorithms, a Locally Recursive Algorithm (LRA) expression is developed to express the computation. Then a generalised mapping method, which is able to handle a broader class of algorithms, is developed. The design of a systolic architecture for Gauss-Jordan elimination is used to illustrate these techniques. Lastly, a multi-projection technique, which applies the mapping method multiple times, is developed to make the mapping methodology complete.

Original languageEnglish (US)
Pages (from-to)124-133
Number of pages10
JournalProceedings of the Hawaii International Conference on System Science
Volume1
StatePublished - Jan 1 1987
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Computer Science(all)

Fingerprint Dive into the research topics of 'CANONIC AND GENERALIZED MAPPING FROM ALGORITHMS TO ARRAYS - A GRAPH BASED METHODOLOGY.'. Together they form a unique fingerprint.

  • Cite this