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

Title: Static Rate-Optimal Scheduling of Multirate DSP Algorithms via Retiming and Unfolding
Speaker: Dr. Xue-Yang ZHU (State Key Laboratory of Computer Science, ISCAS)
Time: 14:30 – 16:00, Friday , April 13, 2012
Venue: Lecture room, 3rd Floor, Building 5#, State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences
Abstract: DSP algorithms are usually required to operate under real-time constraints and with limited resources. In this talk, we are concerned with constructing efficient static (compile-time) schedules for multirate DSP algorithms. We
also take into account the number of processors used. Dataflow models are widely used to represent DSP applications.

The one often used for multirate DSP algorithms are synchronous dataflow graphs (SDFGs).Each node (also called actor) in an SDFG represents a computation or function and each edge models a FIFO channel; the sample rates of actors may differ. Retiming and unfolding are graph transformation techniques that may improve the performance of an application modeled by a data flow model but have no effect on its functionality.

In this talk, we will present an exact method and a heuristic method for static rate-optimal multiprocessor scheduling of real-time multirate DSP algorithms represented by 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 quivalent 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.

Joint work with Twan Basten, Marc Geilen and Sander Stuijk

Biography:
Xue-Yang ZHU is an assistant research professor with the State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences. Her research interests include the design of embedded systems, software architecture and formal methods.