ON OPTIMALLY MAPPING ALGORITHMS TO SYSTOLIC ARRAYS WITH APPLICATION TO THE TRANSITIVE CLOSURE PROBLEM.

S. Y. Kung, P. S. Lewis, S. C. Lo

Research output: Contribution to journalConference articlepeer-review

8 Scopus citations

Abstract

Due to VLSI technological progress, algorithm-oriented array architectures appear to be most effective, feasible and economic. This trend necessitates a systematic methodology for mapping VLSI algorithms onto arrays. Some guidelines for achieving an optimal mapping are proposed. There will be three major stages in mapping algorithms onto arrays: (1) expressing an algorithm in terms of a (single assignment) dependence graph; (b) mapping the dependence graph onto an abstract SFG array; and (c) realization of systolic arrays by systolization. On the basis of the proposed methodology, systolic designs for the transitive closure problem are derived. The systolic array proposed here has the advantages of faster pipelining rates and fewer input/output connections over existing designs.

Original languageEnglish (US)
Pages (from-to)1316-1322
Number of pages7
JournalProceedings - IEEE International Symposium on Circuits and Systems
StatePublished - 1986
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Electrical and Electronic Engineering

Fingerprint

Dive into the research topics of 'ON OPTIMALLY MAPPING ALGORITHMS TO SYSTOLIC ARRAYS WITH APPLICATION TO THE TRANSITIVE CLOSURE PROBLEM.'. Together they form a unique fingerprint.

Cite this