Notes on the complexity of systolic programs

Stephen Taylor, Lisa Hellerstein, Shmuel Safra, Ehud Shapiro

    Research output: Contribution to journalArticlepeer-review


    This paper presents two notes which discuss basic theoretical issues concerning the systolic programming methodology and demonstrates simple techniques which can by used to structure communication. The first note shows how the complexity of two simple algorithms is adversely affected by the cost of data movement in a parallel system. Programming techniques which introduce pipelining are used to overcome the problem and improve the complexity. The second note shows an upper bound on the speedup which can be obtained using the methodology on a mesh connected architecture. This bound is stated in terms of the sequential lower bound for the algorithm concerned.

    Original languageEnglish (US)
    Pages (from-to)250-265
    Number of pages16
    JournalJournal of Parallel and Distributed Computing
    Issue number3
    StatePublished - Jun 1987

    ASJC Scopus subject areas

    • Software
    • Theoretical Computer Science
    • Hardware and Architecture
    • Computer Networks and Communications
    • Artificial Intelligence


    Dive into the research topics of 'Notes on the complexity of systolic programs'. Together they form a unique fingerprint.

    Cite this