Static Rate-Optimal Scheduling of Multirate DSP Algorithms via Retiming and Unfolding

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 ra...

Full description

Saved in:
Bibliographic Details
Main Authors: Xue-Yang Zhu, Geilen, M., Basten, T., Stuijk, S.
Format: Conference Proceeding
Language:English
Subjects:
Delay
Digital signal processing
multirate
Optimal scheduling
Processor scheduling
Program processors
rate-optimal
retiming
Schedules
SDFG
Transient analysis
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1545-3421
2642-7346
DOI:10.1109/RTAS.2012.15