考虑通信竞争的任意处理机网络表调度算法

• 作者: PADUA Divid 唐小勇 李肯立
• 来源期刊: 中国科学F辑
• 关键词: 表调度 任意处理机网络 DAG 通信竟争 并行算法
• 年，卷（期）: 2009,（7）
• 所属期刊栏目: 论文
• 页码范围: 704-714
• 页数: 11页
• 语种: 中文

摘要

任务调度是高性能计算系统中的基本问题之一.解决此类NP难问题的经典启发式算法都假定目标处理机全互连,调度任务时可忽略节点间通信,这显然与实际计算环境不符.为此,文中提出一种在调度任务时同时考虑通信边调度的表调度算法.在边调度时,提出了一种基于最短路径搜索算法的最早通信完成路径查找算法(EFCS),并采用插入式链路策略实现通信边的动态调度,而对处理机网络异构环境下的任务优先级计算问题,受HEFT算法启发,提出异构系统递归优先权计算方法,按非升序排列获得各任务优先级.为了降低算法的执行时间,文中还提出了理论加速比为O(PPE)的并行算法.以随机产生程序任务图和DSP应用程序实例为数据源,在两类不同任意处理机网络目标系统上进行的模拟实验结果表明:本算法明显优于考虑通信竞争的静态表调度算法和不考虑通信竞争的表调度算法,特别是在高通信率应用程序中优势更明显.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	唐小勇	湖南农业大学信息科学技术学院	24	41	3.0	5.0
5	李肯立	南大学计算机与通信学院	1	0	0.0	0.0