Systolic arrays for the recognition of permutation-invariant segments

Joost-Pieter Katoen, Berry Schoenmakers

    Research output: Book/ReportReportAcademic

    14 Downloads (Pure)

    Abstract

    Let P be a permutation defined on sequences of length N. A sequence of N values is said to be P-invariant when it does not change when permuted according to P. A program is said to recognize P-invariant segments when it determines for each segment of N successive input values whether it is P-invariant.

    In this paper we derive a program scheme that generates efficient parallel programs for the recognition of P-invariant segments. The programs consist of a chain of cells extended with a linear number of links between non-neighbouring cells. Under reasonable conditions on P, these programs correspond to systolic arrays with both constant response time and constant latency (independent of N). Efficient systolic arrays for problems such as palindrome recognition or perfect shuffle recognition can be constructed automatically in this way. This is illustrated for the palindrome recognition problem.
    Original languageEnglish
    Place of PublicationEnschede
    PublisherUniversity of Twente
    Number of pages24
    Publication statusPublished - 1995

    Publication series

    NameMemoranda Informatica
    PublisherUniversity of Twente
    No.95-27
    ISSN (Print)0924-3755
    NameMemorandum TIOS
    PublisherUniversity of Twente, Tele-Informatics and Open Systems Group
    No.95-11

    Keywords

    • Calculational program design
    • Palindrome recognition
    • Perfect shuffle
    • Permutation-invariant segments
    • Square recognition
    • Systolic arrays

    Fingerprint Dive into the research topics of 'Systolic arrays for the recognition of permutation-invariant segments'. Together they form a unique fingerprint.

  • Cite this

    Katoen, J-P., & Schoenmakers, B. (1995). Systolic arrays for the recognition of permutation-invariant segments. (Memoranda Informatica; No. 95-27), (Memorandum TIOS; No. 95-11). Enschede: University of Twente.