Institutional Repository
| static rate-optimal scheduling of multirate dsp algorithms via retiming and unfolding | |
| Zhu Xue-Yang; Geilen Marc; Basten Twan; Stuijk Sander | |
| 2012 | |
| Conference Name | 18th IEEE Real Time and Embedded Technology and Applications Symposium, RTAS 2012 |
| Source | Real-Time Technology and Applications - Proceedings |
| Pages | 109-118 |
| Conference Date | April 17, 2012 - April 19, 2012 |
| Conference Place | Beijing, China |
| Indexed Type | EI ; ISTP |
| ISSN | 1080-1812 |
| ISBN | 9780769546674 |
| Department | (1) State Key Laboratory of Computer Science Institute of Software Chinese Academy of Sciences Beijing China; (2) Department of Electrical Engineering Eindhoven University of Technology Eindhoven Netherlands |
| English Abstract | 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. © 2012 IEEE.; 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. © 2012 IEEE. |
| Keyword | Optimization |
| Sponsorship | IEEE Computer Society Technical Committee on Real-Time Systems; IEEE; IEEE Computer Society |
| Subject | Computer Science ; Engineering |
| Language | 英语 |
| Content Type | 会议论文 |
| URI | http://ir.iscas.ac.cn/handle/311060/15698 |
| Collection | 中国科学院软件研究所 |
| Recommended Citation GB/T 7714 | Zhu Xue-Yang,Geilen Marc,Basten Twan,et al. static rate-optimal scheduling of multirate dsp algorithms via retiming and unfolding[C],2012:109-118. |
| Files in This Item: | There are no files associated with this item. | |||||
Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.
Edit Comment