OpenMP多线程负载均衡分析方法及调度策略研究

论文摘要

多核技术作为提高处理器性能的一个有效可行的方法,不仅在科学领域中产生了推动作用,也给人们的生活带来了方便。纵观当今市场上的PC机、服务器、笔记本电脑,多核已逐渐成为趋势。多核在带来巨大处理潜力的同时,对软件方面提出了巨大的挑战,原有的串行编程模式已不再适应,需要向并行编程模式转变。其中,OpenMP能够为具有统一地址空间的并行系统提供可移植、可扩展的开发接口。但是,使用并行编程模式编写的并行程序同样具有使用串行编程模式编写串行程序时所要面临的性能影响问题。负载均衡就是影响并行程序运行性能的主要因素之一。为了精确分析负载均衡,缓解程序所表现的负载不均衡性,以提高程序运行性能,本文主要对OpenMP多线程负载均衡分析方法以及调度策略展开讨论和研究。本文首先讨论和分析了多核技术的发展及其对软件业所产生的影响；总结和归纳了OpenMP相关研究,包括并行效率和性能的分析与改进、多线程之间的锁同步与竞争、多核编程中的负载均衡以及OpenMP的模型扩展与改进；同时,对支持OpenMP的OMPi编译器以及并行化程序的重要对象循环结构进行了介绍。其次,为了精确分析并行程序所表现的负载均衡问题,优化性能分析流程,本文确定了负载均衡分析单元,度量了负载不均衡程度以及潜在的并行调整效率,并提出了一种以负载均衡分析单元为分析对象来监测、分析、调整OpenMP多线程程序负载均衡的方法。通过实验表明该方法是可行的、有效的。最后,考虑到并行程序中并行任务是依据调度策略来实现负载的分配,为了在调度开销与负载均衡之间获得更好的权衡,本文提出将trapezoid梯式调度策略在开源的、支持OpenMP的OMPi编译器进行实现,以提高OpenMP多线程程序的运行性能。实验结果表明：梯式调度策略在递减以及某些极不规则的循环结构中,在适当的线程数下,与指数调度相比,该调度策略能表现出更好的性能。

论文目录

• 摘要
• Abstract
• 插图索引
• 附表索引
• 第1章 绪论
• 1.1 研究背景及意义
• 1.2 相关研究及其现状
• 1.3 论文主要工作
• 1.4 论文组织结构
• 第2章 OpenMP多线程技术基础
• 2.1 多核技术基础
• 2.1.1 多核技术背景
• 2.1.2 多核技术概述
• 2.1.3 多核技术的发展
• 2.2 OpenMP基础简介及相关研究
• 2.2.1 OpenMP简介
• 2.2.2 OpenMP相关研究
• 2.3 OMPi编译器
• 2.3.1 OMPi编译器简介
• 2.3.2 OMPi编译器源到源转换后的代码架构
• 2.4 四种循环结构
• 2.5 小结
• 第3章 一种OpenMP多线程负载均衡分析方法
• 3.1 引言
• 3.2 OpenMP多线程负载均衡分析方法的提出
• 3.3 OpenMP多线程负载均衡分析方法的逻辑模型
• 3.3.1 基本思想
• 3.3.2 逻辑模型
• 3.4 OpenMP多线程负载均衡分析方法的关键实现
• 3.4.1 负载均衡分析单元
• 3.4.2 源代码插桩以获取相关性能数据
• 3.4.3 负载均衡度量
• 3.5 小结
• 第4章 OpenMP多线程负载均衡调度策略研究与实现
• 4.1 引言
• 4.2 梯式调度在OMPi编译器上实现的提出
• 4.3 梯式调度在OMPi编译器上的设计与实现
• 4.3.1 设计的基本思想
• 4.3.2 梯式调度在OMPi编译器上的具体实现
• 4.4 小结
• 第5章 分析方法验证及调度策略性能分析
• 5.1 实验环境
• 5.2 分析方法验证
• 5.2.1 验证过程
• 5.2.2 验证结果及分析
• 5.3 分析方法辅助调度策略性能分析
• 5.3.1 实验过程
• 5.3.2 实验结果
• 5.3.3 实验分析
• 5.4 小结
• 结论
• 参考文献
• 致谢
• 附录A（攻读硕士学位期间所发表的学术论文）