Static rate-optimal scheduling of multirate DSP algorithms via retiming and unfolding.

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

15 Citations (Scopus)
1 Downloads (Pure)


This paper presents an exact method and a heuristic method for static rate-optimal multiprocessor scheduling of real-time multi rate DSP algorithms represented by synchronous data flow graphs (SDFGs). Through exploring the state-space generated by a self-timed execution (STE) of an SDFG, a static rate-optimal schedule via explicit retiming and implicit unfolding can be found by our exact method. By constraining the number of concurrent firings of actors of an STE, the number of processors used in a schedule can be limited. Using this, we present a heuristic method for processor-constrained rate-optimal scheduling of SDFGs. Both methods do not explicitly convert an SDFG to its equivalent homogenous SDFG. Our experimental results show that the exact method gives a significant improvement compared to the existing methods, our heuristic method further reduces the number of processors used.
Original languageEnglish
Title of host publicationProceedings of the 18th Real-Time and Embedded Technology and Applications Symposium (RTAS'12), 16-19 April 2012, Beijing, China
Place of PublicationLos Alamitos
PublisherIEEE Computer Society
ISBN (Print)978-0-7695-4667-4
Publication statusPublished - 2012
Eventconference; RTAS'12; 2012-04-16; 2012-04-19 -
Duration: 16 Apr 201219 Apr 2012


Conferenceconference; RTAS'12; 2012-04-16; 2012-04-19


Dive into the research topics of 'Static rate-optimal scheduling of multirate DSP algorithms via retiming and unfolding.'. Together they form a unique fingerprint.

Cite this