计算机科学 ›› 2015, Vol. 42 ›› Issue (11): 43-47.doi: 10.11896/j.issn.1002-137X.2015.11.007

• 2014年全国高性能计算机学术年会 • 上一篇    下一篇

基于异构多核平台的同步数据流图帕累托优化与调度

顾玉磊,朱雪阳,晏荣杰,张广泉   

  1. 苏州大学计算机科学与技术学院 苏州215006;中国科学院软件研究所计算机科学国家重点实验室 北京100190,中国科学院软件研究所计算机科学国家重点实验室 北京100190,中国科学院软件研究所计算机科学国家重点实验室 北京100190,苏州大学计算机科学与技术学院 苏州215006
  • 出版日期:2018-11-14 发布日期:2018-11-14
  • 基金资助:
    本文受973课题(2014CB340701),江苏省自然科学基金(BK2011281),苏州市应用基础研究计划(SYG201241),江苏省研究生科研创新计划(KYLX_1247)资助

Pareto Optimization and Scheduling of Synchronous Dataflow Graphs on Heterogeneous Multicore Platform

GU Yu-lei, ZHU Xue-yang, YAN Rong-jie and ZHANG Guang-quan   

  • Online:2018-11-14 Published:2018-11-14

摘要: 同步数据流图被广泛用于多媒体和数字信号处理程序等流应用程序的建模。流应用程序须达到一定吞吐量才能流畅运行,利用异构多核处理器来进一步提高流应用程序的吞吐量已经成为当今嵌入式系统的发展趋势,但是提高吞吐量往往伴随着能耗的增加。为了解决这个问题,基于异构多核平台的同步数据流图系统模型,给出了求解所有能耗和吞吐量的帕累托优化点及其相应静态调度的方法。首先将系统模型转换为时间自动机网络,并将分析目标转换为时序逻辑公式;再使用实时模型检测工具UPPAAL寻找解决方案;最后对UPPAAL返回的结果进行分析,找出满足要求的调度。由于模型检测方法可对问题空间进行穷尽搜索,该方法得到的 结果 是精确的。该方法可帮助设计者在系统开发早期了解系统能耗和吞吐量的量化关系,有利于缩短系统的开发周期,降低开发成本。

关键词: 同步数据流图,异构多核平台,帕累托优化,调度,模型检测

Abstract: Synchronous dataflow graphs (SDFGs) are widely used to model streaming applications such as multimedia and digital signal processing applications.Streaming applications are usually required to reach a high throughput to guarantee smooth running.Using heterogeneous multicore processors to improve the throughput of streaming applications has become a feasible solution.However,a higher throughput is usually achieved with the increase of energy consumption.We presented a method to explore the Pareto space of energy consumption and throughput and find the schedule of each Pareto point.A system model includes an SDFG description for the application and a heterogeneous multicore platform.The system model is transformed to a network of timed automata (NTA) and the optimization goals are formalized as temporal logic formulae.The NTA and formulae are then used as the input of the real time model checking tool UPPAAL.The Pareto points and corresponding schedules by the trace provided by UPPAAL can be obtained.Our method is exact,which is benefited from the exhaustive search nature of model checking technique.The method can be used to help designers to understand the quantitative relationship between energy consumption and throughput in the design period,shortening development cycles and reducing costs of system developments.

Key words: Synchronous dataflow graphs,Heterogeneous multicore platform,Pareto optimization,Scheduling,Model checking

[1] Lee E A,Messerschmitt D G.Static scheduling of synchronous data flow programs for digital signal processing[J].IEEE Trans on Computer,1987,6(1):24-35
[2] Institute of Software,Chinese Academy of Sciences.The iDFOS Tool.(2014)[2014].http://lcs.ios.ac.cn/~zxy/tools/idfos.html
[3] Karp R M.A characterization of the minimum cycle mean in a digraph[J].Discrete Mathematics,1978,3(3):309-311
[4] Groote R,Kuper J,Broersma H,et al.Max-plus algebraicthroughput analysis of synchronous dataflow graphs [C]∥38th EUROMICRO Conference on Software Engineering and Advanced Applications (SEAA).Cesme,2012:29-38
[5] Stuijk S,Geilen M,Basten T.Exploring trade-offs in buffer re-quirements and throughput constraints for synchronous dataflow graphs[C]∥Proceedings of the 43rd annual Design Automation Conference.San Francisco,2006:899-904
[6] Fakih M,Gruttner K,Franzle M,et al.Towards performance analysis of SDFGs mapped to shared-bus architectures using model-checking[C]∥Design,Automation & Test in Europe Conference & Exhibition (DATE).Grenoble,2013:1167-1172
[7] Madsen J,Hansen M R,Knudsen K S,et al.System-level verification of multi-core timed-automata[C]∥Proceedings of International Federation of Automatic Control.Seoul,2008:9302-9307
[8] Bouyer P,Fahrenberg U,Larsen K G,et al.Quantitative analysis of real-time systems using priced timed automata[J].Communications of the ACM,2011,4(9):78-87
[9] Alur R,Dill DL.A theory of timed automata[J].Theoretical Computer Science,1994,6(2):183-235
[10] Behrmann G,David A,Larsen K G.A tutorial on Uppaal[J].Formal Methods for Design of Real-time Systems,2004,5:200-236
[11] Uppsala University,Aalborg University.The UPPAAL Model Checker.(2005)[2014].http://www.uppaal.com
[12] Gu Yu-lei,Zhu Xue-yang,Yan Rong-jie,et al.Pareto Optimization and Scheduling of Synchronous Dataflow Graphs on a Heterogeneous Multicore Platform.(2014)[2014].http://lcs.ios.ac.cn/~zxy/papers/r14-14.pdf

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] 雷丽晖,王静. 可能性测度下的LTL模型检测并行化研究[J]. 计算机科学, 2018, 45(4): 71 -75 .
[2] 孙启,金燕,何琨,徐凌轩. 用于求解混合车辆路径问题的混合进化算法[J]. 计算机科学, 2018, 45(4): 76 -82 .
[3] 张佳男,肖鸣宇. 带权混合支配问题的近似算法研究[J]. 计算机科学, 2018, 45(4): 83 -88 .
[4] 伍建辉,黄中祥,李武,吴健辉,彭鑫,张生. 城市道路建设时序决策的鲁棒优化[J]. 计算机科学, 2018, 45(4): 89 -93 .
[5] 史雯隽,武继刚,罗裕春. 针对移动云计算任务迁移的快速高效调度算法[J]. 计算机科学, 2018, 45(4): 94 -99 .
[6] 周燕萍,业巧林. 基于L1-范数距离的最小二乘对支持向量机[J]. 计算机科学, 2018, 45(4): 100 -105 .
[7] 刘博艺,唐湘滟,程杰仁. 基于多生长时期模板匹配的玉米螟识别方法[J]. 计算机科学, 2018, 45(4): 106 -111 .
[8] 耿海军,施新刚,王之梁,尹霞,尹少平. 基于有向无环图的互联网域内节能路由算法[J]. 计算机科学, 2018, 45(4): 112 -116 .
[9] 崔琼,李建华,王宏,南明莉. 基于节点修复的网络化指挥信息系统弹性分析模型[J]. 计算机科学, 2018, 45(4): 117 -121 .
[10] 王振朝,侯欢欢,连蕊. 抑制CMT中乱序程度的路径优化方案[J]. 计算机科学, 2018, 45(4): 122 -125 .