Synthesizing Linear Array Algorithms from Nested For Loop Algorithms

Peizong Lee, Zvi Meir Kedem

Research output: Contribution to journalArticle

Abstract

This paper is concerned with the mapping of algorithms structured as depth p-nested for loops into special purpose systolic VLSI linear arrays. The mappings are done by using linear functions transforming the original sequential algorithms into a form suitable for parallel execution on linear arrays. The derivation of feasible mapping is done by identifying formal criteria to be satisfied by both the original sequential algorithm and the proposed transformation function. Those formal criteria define the universe of feasible solutions we consider and thus enable us to derive large families of transformations; the target transformation can then be chosen using additional criteria. Among such criteria could be minimal execution time, smallest number of processors to be used, or the requirement to use a processor with specific characteristics provided to us. The methodology, which deals with general algorithms, is illustrated by synthesizing algorithms for matrix multiplication and a version of the Warshall-Floyd transitive closure algorithm.

Original languageEnglish (US)
Pages (from-to)1578-1598
Number of pages21
JournalIEEE Transactions on Computers
Volume37
Issue number12
DOIs
StatePublished - Dec 1988

Keywords

  • Algorithm transformations
  • VLSI
  • data contention
  • data dependence
  • hyperplane
  • linear systolic array
  • matix multiplication
  • modularly extensible
  • parallel
  • path-finding problems
  • processing

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'Synthesizing Linear Array Algorithms from Nested For Loop Algorithms'. Together they form a unique fingerprint.

  • Cite this