多核多线程处理器上任务调度技术研究

发布时间：2020-09-08 11:06

　　 论文着重于多核多线程处理器上的任务调度相关的研究。首先是从理论角度提出了3种与基于复制的任务调度相关的算法,这3种算法都表现出了较好性能。然后结合一种实际的多核多线程处理器(网络处理器IXP)展开了对任务调度实例化研究,并且运用地址转换和迭代编译等技术构建了新型统一网络编程环境,又结合实际网络应用提出了吞吐量与延迟相结合的网络任务调度算法。本文主要贡献如下: 提出了满足通信限制的基于复制的优化fork-join调度算法TDC_FJ,TDC_FJ利用基于复制的fork-join最优化调度结果来对fork-join任务图进行调度,并且在调度过程中加入处理器之间的通信限制,也就是一条通信信道不能同时被两个通信事件占用。TDC_FJ算法在调度时力求减少需要的处理器数目,尽量调度任务到已占用处理器上,在保证性能的同时减少处理器的消耗量。 给出针对普通任务图带通信限制的基于复制调度算法TDMSCL。该算法把普通任务图转换为join与fork等基本形状,然后运用对join图与fork图的优化调度研究结果对这些基本形状进行任务调度。相对于传统任务调度中找关键路径或者计算权值逐步调度的方式,TDMSCL算法把调度过程转变为按照拓扑序列逐步求优的过程。算法力求保证每个节点的最早开始时间,通过这种调度方式获得整个任务的优化调度结果。合并过程采用贪婪策略力求在较小时间开销内提高合并的耦合度,并且考虑了通信信道的独占性制止了同一通信信道的通信重叠。最后与其他几种常见的任务调度算法进行了对比测试,结果显示TDMSCL在算法时间复杂度处理器消耗与调度长度上有性能优势。 提出了一种新的冗余任务消除算法RTE解决了基于复制的任务调度生成的冗余任务问题。大多数基于复制的算法调度后的任务存在部分冗余。这种冗余的任务会导致处理器计算资源的浪费。RTE可以作为一种辅助手段用于提高已有基于复制的任务调度算法的效能,具有很好的通用性。任何一种基于复制的调度算法都可以和它结合使用。测试表明该算法可以使已有的基于复制的调度算法都不同程度的获得效能提升。 针对异构多核处理器IXP构建编译器Shangri-la的统一编译后端框架。采用地址转换方法来解决异构内核使用不同寻址方式的指针共享问题。提出了收敛的迭代编译框架来控制最终代码生成大小。这些技术的运用使Shangri-la很好整合了两种不同处理器核的编译工作。这种统一的编译平台掩盖了复杂的网络处理器结构特征,使得网络程序编写和传统模式的程序编写一样简单方便。 提出针对网络应用特性的任务调度算法LTTS。网络程序不同于普通程序,网络应用具有较高的并行性,但是网络应用中的并行性是数据并行性。而且网络程
【学位单位】：中国科学院研究生院（计算技术研究所）
【学位级别】：博士
【学位年份】：2006
【中图分类】：TP332
【部分图文】：

中国科学院博士学位论文──多核多线程处理器上任务调度技术研究线程切换，否则一直执行当前线程的指令。粗粒度多线程处理器并不需要进行频繁的线程切换，因此对线程切换的开销要求也没有细粒度多线程处理器那么高。也不需要太多的线程数目。但是粗粒度多线程处理器在进行线程切换的时候需要排空流水线然后再进行流水线填充。所以相对细粒度多线程粗粒度的线程切换开销较大。多线程技术现在运用得非常广泛，超线程技术就是其中的一种。图 1-1给出了superthreading 处理器[4]的结构示意图。

图 4-2 任务图例图 4-2中 n1->n7->n9 是关键路径，所以{n1,n7,n9}是 CPN 节点，{n2,n3,n4,n5,n6,n8}是 IBN 节点，图中没有 OBN 节点。按照 CPN_Dominant 生成算法首先选出 CPN 节点n1 加入到序列中{n1}，然后选取下一个 CPN n7 但是 n7 的父节点并不是都在序列中，按照 b-level 选取最大 IBN 节点 n2 加入序列{n1,n2}，之后又把 n3 加入到序列中{n1,n2,n3},在 n7 的父节点都被加入序列以后把 n7 也加入序列{n1,n2,n3,n7}，最后选取 n9 递归把父节点加入的序列，最终得到 CPN_Dominant 序列{n1,n2,n3,n7,n5,n4,n8,n6,n9}。在完成构建 CPN_Dominant 列表后就可以进行任务调度，具体调度算法如下CPFD 任务调度算法：1. 找出任务图中的关键路径，构建 CPN_Dominant 序列Repeat2. 选取 CPN_Dominant 序列中的第一个未调度节点作为候选节点。3. 设定 P_SET 为处理器节点集合，它包含了候选节点的所有父节点所在处理器外加一个空处理器节点。4. 对于 P_SET 中的每一个处理器 P，计算候选节点在该处理器上的最早开始时间，

CPFD调度结果

【引证文献】

相关期刊论文 前4条

1 孟学多;俞雪永;颜晖;;基于多核的在线判题系统的设计与研究[J];计算机时代;2011年07期

2 王遵彤;李彩;吴启迪;;多处理器系统动态调度负载均衡节约算法[J];控制与决策;2011年11期

3 李静梅;张博;;基于混合粒子群优化的CMP线程调度方法[J];计算机工程;2012年20期

4 朱仕浪;;基于NIOS Ⅱ双软核智能家居控制器设计[J];三明学院学报;2011年05期

相关博士学位论文 前1条

1 耿晓中;基于多核分布式环境下的任务调度关键技术研究[D];吉林大学;2013年

相关硕士学位论文 前10条

1 董珍;异构多核处理器的任务调度分配问题及算法研究[D];哈尔滨工程大学;2010年

2 赵磊;适应多核处理器的任务调度研究[D];哈尔滨理工大学;2010年

3 高金华;基于多核的任务调度研究与实现[D];中南大学;2010年

4 申建晶;嵌入式多核实时操作系统研究及实现[D];电子科技大学;2011年

5 王旭涛;基于异构多核处理器系统的任务调度算法研究[D];南京邮电大学;2011年

6 徐茂兴;全方位视觉的多核并行处理研究与应用[D];浙江工业大学;2010年

7 胡新安;支持动态任务调度的多核分布式操作系统设计[D];哈尔滨工业大学;2011年

8 李静;基于多核的任务调度策略研究[D];哈尔滨工程大学;2011年

9 梁帅;RSA密码系统中的并行算法研究[D];内蒙古大学;2008年

10 吕尧;基于多核的网络扫描研究与实现[D];西安电子科技大学;2010年

本文编号：2814105