DEPENDENCE GRAPH BASED DESIGN OF SYSTOLIC ARRAYS FOR THE ALGEBRAIC PATH PROBLEM.

P. S. Lewis, S. Y. Kung

Research output: Chapter in Book/Report/Conference proceedingConference contribution

5 Scopus citations

Abstract

A systolic design for the algebraic path problem (APP) is introduced. The APP is a generalization of a cross-disciplinary set of problems that includes transitive closure, shortest path, and matrix inversion. Special cases of the array can be used to solve any instance of the APP. The array uses N**2 processing elements, and requires 2N I/O connections. A design methodology that is based on dependence-graph analysis is introduced to derive this array. The design methodology is an extension of methods based on uniform recurrence equations. The algorithm for the APP is described in a localized, indexed, single-assignment form. A systolic implementation of the algorithm is generated by mapping its dependence graph onto an array configuration. Different mappings of the same dependence graph produce both the array used here and those previously proposed for the APP. A comparison is made of all arrays proposed for the APP.

Original languageEnglish (US)
Title of host publicationConference Record - Asilomar Conference on Circuits, Systems & Computers
PublisherIEEE
Pages13-18
Number of pages6
ISBN (Print)0818608161
StatePublished - Jan 1 1987
Externally publishedYes

Publication series

NameConference Record - Asilomar Conference on Circuits, Systems & Computers
ISSN (Print)0736-5861

All Science Journal Classification (ASJC) codes

  • Engineering(all)

Fingerprint Dive into the research topics of 'DEPENDENCE GRAPH BASED DESIGN OF SYSTOLIC ARRAYS FOR THE ALGEBRAIC PATH PROBLEM.'. Together they form a unique fingerprint.

  • Cite this

    Lewis, P. S., & Kung, S. Y. (1987). DEPENDENCE GRAPH BASED DESIGN OF SYSTOLIC ARRAYS FOR THE ALGEBRAIC PATH PROBLEM. In Conference Record - Asilomar Conference on Circuits, Systems & Computers (pp. 13-18). (Conference Record - Asilomar Conference on Circuits, Systems & Computers). IEEE.