论文部分内容阅读
随着应用多样化和计算需求的不断提升,多核处理器系统在性能、功耗、灵活性等方面优势明显,被广泛用于网络、通信、信号处理、多媒体应用等领域。处理器核数量的增长为系统性能的提升提供了硬件支撑,但硬件必须与适应的软件结合在一起才能充分发挥其性能优势。多核处理器复杂的体系结构对系统资源分配、任务调度等方面造成了困难,研究并实现适应多核处理器系统特性的任务调度算法具有重要的现实意义。 另一方面,当多核处理器任务调度算法应用于不同系统场景时,任务模型、环境参数的变化都可能导致系统功能和性能受到不同程度的影响。因此,针对运行具体任务调度算法的系统,从理论上支持系统功能和性能的形式化验证,保障系统的可靠运行非常重要。有效的系统功能和性能混合验证理论是并行程序开发、多核处理器系统设计方法学等领域的关键支撑问题。 本论文以负载均衡、能耗约束、多目标优化为研究重点,设计并实现了与之适应的任务调度算法,并基于模型检测理论提出了针对系统任务调度过程的功能和性能混合验证方法。论文的成果和创新性贡献主要有以下四点: 一、提出了一种负载感知的任务调度算法。该算法在满足任务间依赖关系的前提下,根据任务的计算开销和任务间的通信开销,结合边消除算法和任务复制算法将待调度任务集划分为并行任务子集;在考虑处理器核负载的基础上,根据并行任务子集集合、处理器核集合及并行任务子集在各个核上的执行效率生成赋权二部图,通过最大权匹配将并行任务子集合理地调度到负载适应的处理器核上运行。仿真实验表明,该算法在实现负载均衡的同时有效降低了任务集的平均调度长度,提高了系统利用率。 二、提出了一种能耗约束的任务调度算法。在多核处理器系统中,将任务分摊到所有处理器核能提高系统利用率,但导致大量的簇间通信从而增加数据传输能耗。该算法通过构建系统能耗模型,在对目标平台处理单元和任务间依赖关系进行分析的基础上,动态计算任务分配在相应簇上产生的系统能耗,选择产生系统能耗小的分配方案以平衡系统利用率和簇间通信开销。仿真实验表明,该算法在减少了核间通信开销并提高系统利用率的同时,降低了系统能耗。 三、提出了一种多目标优化任务调度算法。该算法以任务间依赖关系作为约束条件,以最小化任务集调度长度、最小化系统能耗和最大化系统利用率作为目标函数定义任务调度算法多目标优化问题。基于人工免疫原理,采用提取疫苗并接种疫苗的方式,将问题的先验知识加入到了目标函数的解中;通过抗体的刺激与抑制,在保证抗体多样性的同时优化当前种群;针对任务调度问题设计新颖的交叉、变异算子及对应算子的使用概率,保证了算法的全局搜索能力和局部搜索能力;基于Pareto最优的概念,进行疫苗选择和群体更新加快了算法收敛至全局最优解的速度。仿真实验分析了算法的收敛性和解的多样性,对比分析结果表明该算法在一定程度上优化了调度长度、系统能耗和系统利用率。 四、提出了一种针对系统任务调度过程的功能和性能混合验证方法。该方法改进交互式马尔可夫链(IMC)用于构建多核处理器系统任务调度功能模型,扩展基于动作的连续随机逻辑(aCSL),从逻辑层次上对多核处理器系统在任务调度过程中产生的时间、概率和能耗等性能指标进行刻画,并基于模型检测理论,采用数值计算方法从理论上支持系统的功能和性能混合验证,判定系统是否满足预期目标。通过仿真实验和理论分析说明了混合验证方法的有效性。