ISCAS OpenIR
Memory-constrained static rate-optimal scheduling of synchronous dataflow graphs via retiming
Zhu, Xue-Yang (1); Geilen, Marc (2); Basten, Twan (2); Stuijk, Sander (2)
2014
会议名称17th Design, Automation and Test in Europe, DATE 2014
会议日期March 24, 2014 - March 28, 2014
会议地点Dresden, Germany
收录类别EI
出版地Institute of Electrical and Electronics Engineers Inc.
ISSN15301591
ISBN9783981537024
部门归属(1) State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences, Beijing 100190, China; (2) Department of Electrical Engineering, Eindhoven University of Technology, Eindhoven, Netherlands
摘要Synchronous dataflow graphs (SDFGs) are widely used to model digital signal processing (DSP) and streaming media applications. In this paper, we use retiming to optimize SDFGs to achieve a high throughput with low storage requirement. Using a memory constraint as an additional enabling condition, we define a memory constrained self-timed execution of an SDFG. Exploring the state-space generated by the execution, we can check whether a retiming exists that leads to a rate-optimal schedule under the memory constraint. Combining this with a binary search strategy, we present a heuristic method to find a proper retiming and a static scheduling which schedules the retimed SDFG with optimal rate (i.e., maximal throughput) and with as little storage space as possible. Our experiments are carried out on hundreds of synthetic SDFGs and several models of real applications. Differential synthetic graph results and real application results show that, in 79% of the tested models, our method leads to a retimed SDFG whose rate-optimal schedule requires less storage space than the proven minimal storage requirement of the original graph, and in 20% of the cases, the returned storage requirements equal the minimal ones. The average improvement is about 7.3%. The results also show that our method is computationally efficient. © 2014 EDAA.; Synchronous dataflow graphs (SDFGs) are widely used to model digital signal processing (DSP) and streaming media applications. In this paper, we use retiming to optimize SDFGs to achieve a high throughput with low storage requirement. Using a memory constraint as an additional enabling condition, we define a memory constrained self-timed execution of an SDFG. Exploring the state-space generated by the execution, we can check whether a retiming exists that leads to a rate-optimal schedule under the memory constraint. Combining this with a binary search strategy, we present a heuristic method to find a proper retiming and a static scheduling which schedules the retimed SDFG with optimal rate (i.e., maximal throughput) and with as little storage space as possible. Our experiments are carried out on hundreds of synthetic SDFGs and several models of real applications. Differential synthetic graph results and real application results show that, in 79% of the tested models, our method leads to a retimed SDFG whose rate-optimal schedule requires less storage space than the proven minimal storage requirement of the original graph, and in 20% of the cases, the returned storage requirements equal the minimal ones. The average improvement is about 7.3%. The results also show that our method is computationally efficient. © 2014 EDAA.
语种英语
内容类型会议论文
URI标识http://ir.iscas.ac.cn/handle/311060/16604
专题中国科学院软件研究所
推荐引用方式
GB/T 7714
Zhu, Xue-Yang ,Geilen, Marc ,Basten, Twan ,et al. Memory-constrained static rate-optimal scheduling of synchronous dataflow graphs via retiming[C]. Institute of Electrical and Electronics Engineers Inc.,2014.
条目包含的文件
条目无相关文件。
个性服务
推荐该条目
保存到收藏夹
查看访问统计
导出为Endnote文件
谷歌学术
谷歌学术中相似的文章
[Zhu, Xue-Yang (1)]的文章
[Geilen, Marc (2)]的文章
[Basten, Twan (2)]的文章
百度学术
百度学术中相似的文章
[Zhu, Xue-Yang (1)]的文章
[Geilen, Marc (2)]的文章
[Basten, Twan (2)]的文章
必应学术
必应学术中相似的文章
[Zhu, Xue-Yang (1)]的文章
[Geilen, Marc (2)]的文章
[Basten, Twan (2)]的文章
相关权益政策
暂无数据
收藏/分享
所有评论 (0)
暂无评论
 

除非特别说明,本系统中所有内容都受版权保护,并保留所有权利。