论文部分内容阅读
论文着重于多核多线程处理器上的任务调度相关的研究。首先是从理论角度提出了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。网络程序不同于普通程序,网络应用具有较高的并行性,但是网络应用中的并行性是数据并行性。而且网络程