Piecewise linear schedules for recurrence equations

Sanjay Rajopadhye, Lap Mui, Sayfe Kiaei

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

4 Scopus citations


The scheduling problem for a system of affine recurrence equations (SARE) has been studied by many researchers. The emphasis has been on an important class of timing functions called linear or affine schedules. For many SAREs, linear schedules may not exist, although the SARE is computable. It will be shown that it is possible to find piecewise linear schedules (PLS) for many practical algorithms expressed in terms of SAREs. PLS have different slopes for different variables in the algorithm. For each variable, the computation domain is partitioned into finitely many "pieces" in which the schedule is different for each subdomain. The main focus of this paper is to introduce PLS and develop a synthesis procedure to find PLS for the given SARE.

Original languageEnglish (US)
Title of host publicationWorkshop on VLSI Signal Processing 1992
EditorsWojtek Przytula, Kung Yao, Rajeev Jain, Jan Rabaey
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages10
ISBN (Electronic)0780308115, 9780780308114
StatePublished - 1992
Externally publishedYes
Event6th IEEE Workshop on VLSI Signal Processing - Los Angeles, United States
Duration: Oct 28 1992Oct 30 1992

Publication series

NameWorkshop on VLSI Signal Processing 1992


Conference6th IEEE Workshop on VLSI Signal Processing
Country/TerritoryUnited States
CityLos Angeles

ASJC Scopus subject areas

  • Signal Processing
  • Electrical and Electronic Engineering
  • Applied Mathematics


Dive into the research topics of 'Piecewise linear schedules for recurrence equations'. Together they form a unique fingerprint.

Cite this