并行嵌入式系统中具有通信竞争任务调度问题的高级列表调度方法  

Advanced list scheduling heuristic for task scheduling with communication contention for parallel embedded systems

作　　者：穆鹏程[1] NEZAN Jean-Francois RAULET Mickael COUSIN Jean-Gabriel 

机构地区：[1]西安交通大学智能网络与网络安全教育部重点实验室,电子与信息工程学院,西安710049 [2]IETR/Image and Remote Sensing Group, CNRS UMR 6164/INSA Rennes, 35043 RENNES Cedex, France

出　　处：《中国科学：信息科学》2011年第3期349-364,共16页Scientia Sinica(Informationis)

基　　金：国家自然科学基金(批准号:60971113,61071125);中国博士后科学基金(批准号:20100481346)资助项目

摘　　要：现代嵌入式系统正在向使用多核或多处理器进行并行处理的方向发展.针对并行嵌入式系统中具有通信竞争情况下的任务调度问题,文中提出3项高级技术以提高列表调度方法的性能.首先使用5组(已存在的两组和新提出的3组)节点等级作为节点优先权来生成节点列表;然后使用关键子节点技术来改善调度过程中处理器的选择;最后使用通信延迟技术扩大通信连接线上的空闲时间区间.文中还给出了组合使用这3项技术的高级动态列表调度方法.实验结果表明,在中等通信代价和高通信代价的情况下,组合高级动态方法能够有效地缩短调度长度,可以在通信代价很高时通过优化使用硬件资源使调度结果加速高达80%.Modern embedded systems tend to use multiple cores or processors for processing parallel applications.This paper indeed aims at task scheduling with communication contention for parallel embedded systems and proposes three advanced techniques to improve the list scheduling heuristic.Five groups of node levels（two existing groups and three new groups） are firstly used as node priorities to generate node lists.Then the critical child technique improves the selection of a processor in the scheduling process.Finally,the communication delay technique enlarges the idle time intervals on communication links.We also propose an advanced dynamic list scheduling heuristic by combining the three techniques.Experimental results show that the combined advanced dynamic heuristic is efficient to shorten the schedule length for most of the randomly generated DAGs in the cases of medium and high communication.Our method accelerates an application up to 80% in the case of high communication and can also reduce the use of hardware resources.

关 键 词：列表调度 通信竞争 节点等级 关键子节点 通信延迟 

分 类 号：TP368.1[自动化与计算机技术—计算机系统结构]