基于多核的多线程算法并行优化

摘要

在多核处理器不断普及的今天，并行软件开发技术的加速发展已成为关键。多核处理器既促进了并行软件开发技术的发展，也依赖于并行软件开发技术。但是软件并行化的发展需要克服重重困难。当今在使用的很大部分软件还是串行思想开发的产物，我们需要从根本软件开发理念上改变，进行软件并行化。目前已经出现了多种并行编程模型，主要有共享存储编程模型、消息传递模型和分布式存储模型。多线程并行编程就基于共享存储的编程模型。
　　 矩阵相乘算法的重要性不言而喻，在很多科学计算和工程方面应用极广。因此，对矩阵相乘算法做了实验，分别采用了Win32多线程API、OpenMP及C＃多线程对其进行实现。在此过程中，归结了这几种多线程编程方法的特性和优缺点。Win32多线程API具有性能优，可以显性操作线程的优点，但是实现相对复杂，对软件开发人员要求高。OpenMP实现简单，适合于优化循环。但是性能相对Win32多线程API稍微逊色。而C＃在语言级提供了对多线程的支持，但是由于其基于虚拟机的机制导致其性能还不如前两者，实现难度介于两者之间，也可显性操作线程。本实验结果有助于在开发时对编程方法的选择。
　　 排序算法是常用而且对其本身性能要求很高的算法。在前面实验研究的基础上，提出了一种排序组合算法，并且对后半部分的归并排序进行了改进。改进的方法采用了多线程的思想，将原来单线程执行的归并过程进化成可以同时执行的两个线程。两个线程分别从已经有序的两个序列的最大值端和最小值端同时进行比较，将相应的结果放在新序列的相应端。两个线程都工作至新序列的中间为止，也达到了负载平衡的目的。该算法的实验采用前面实验分析结果中性能最优的Win32 API多线程编程方法进行实现。实验结果对比表明并行改进后的算法性能提升显著，并且随着数据规模的扩大，提升比例稳定升高。

目录

文摘

英文文摘

1 引言

1.1 研究背景

1.2 研究内容

1.3 研究内容的安排

2 多核与多线程技术

2.1 多核技术

2.1.1 多核体系结构

2.1.2 多核现状及前景

2.2 多核对软件业的影响

2.3 多线程技术

2.4 基于多核的多线程

3 多线程编程方法

3.1 windows多线程库

3.1.1 Win32 API多线程

3.1.2 MFC多线程

3.1.3 W23API与MFC比较

3.2 pthread API多线程库

3.2.1 UNIX模型中的线程

3.2.2 pthread多线程API

3.3 OpenMP

3.3.1 编译指导语句

3.3.2 运行函数库与环境变量

3.4 C#多线程机制

3.5 本章小结

4 算法实验

4.1 矩阵相乘算法实现矩阵相乘算法实现

4.1.1 使用Win32 API实现矩阵相乘算法

4.1.2 使用OpenMP实现矩阵相乘算法

4.1.3 使用C#多线程实现矩阵相乘算法

4.2 排序算法

4.2.1 传统的主要排序算法

4.2.2 基于多核的并行排序算法设计

4.2.3 基于多线程的归并算法的改进

4.3 本章小结

5 实验结果分析

5.1 矩阵相乘实验及效率分析

5.2 排序算法优化实验内容及结果分析

5.2.1 实验平台及内容

5.2.2 实验结果性能分析

5.2.3 时间复杂度分析

5.3 本章小结

6 总结与展望

6.1 全文总结

6.2 后续工作展望

参考文献

个人简历

在学期间发表的学术论文与研究成果

致谢