static rate-optimal scheduling of multirate dsp algorithms via retiming and unfolding

ISCAS OpenIR

	static rate-optimal scheduling of multirate dsp algorithms via retiming and unfolding
	Zhu Xue-Yang; Geilen Marc; Basten Twan; Stuijk Sander
	2012
会议名称	18th IEEE Real Time and Embedded Technology and Applications Symposium, RTAS 2012
会议录名称	Real-Time Technology and Applications - Proceedings
页码	109-118
会议日期	April 17, 2012 - April 19, 2012
会议地点	Beijing, China
收录类别	EI ; ISTP
ISSN	1080-1812
ISBN	9780769546674
部门归属	(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
摘要	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.
关键词	Optimization
主办者	IEEE Computer Society Technical Committee on Real-Time Systems; IEEE; IEEE Computer Society
学科领域	Computer Science ; Engineering
语种	英语
内容类型	会议论文
URI标识	http://ir.iscas.ac.cn/handle/311060/15698
专题	中国科学院软件研究所
推荐引用方式 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.