基于多核处理器的数值算法并行优化究

摘要

随着多核计算机的日益普及,大规模科学与工程计算、事务处理与商业计算的需求,以及数据挖掘应用领域的不断扩大,基于多核平台的线性方程组数值求解算法和大数据量数值关联规则算法的研究显得非常重要。由于多核技术会增加多线程的创建、通信和销毁等开销,如何有效发现程序中的可并行性能、优化多核并行程序及发挥多核的最佳性能,成为高性能计算领域研究的重要课题。
　　 本文给出了Cholesky分解算法的详细推导过程,分析了Cholesky分解并行按照块分配的任务分配策略存在负载不均衡,提出了块交叉分配方案,并与卷帘分配方案对比。对这三种算法均采用了提前发送策略,并在MPI集群系统上进行了实验和分析。针对Cholesky分解基于MPI的并行算法设计复杂、进程负载均衡困难、消息传递和数据移动开销大问题,以及基于多核采用OpenMP并行化的并行性开销增大和线程负载不平衡的问题,着重考虑多核计算机的优势,提出了一种基于任务划分的Cholesky分解多核并行优化算法。该算法将大循环问题划分成各个相互独立的小任务,并运用递归技术、任务窃取技术和动态负载均衡算法使这些任务能够并行完成。在分析了关联规则挖掘Apriori算法及其并行算法存在的不足的基础上,提出了一种改进的关联规则挖掘的多核并行优化算法。该算法对Apriori算法的压缩矩阵进行了改造,并在多核平台下利用OpenMP技术和TBB技术,对串行程序进行循环并行化和任务分配的并行化设计,最大限度地实现并行关联规则挖掘,提高关联规则挖掘效率和多核CPU的利用率。
　　 算法程序设计过程引入了Intel Parallel Studio并行套件,对基于多核的并行算法进行内存,线程检查和性能优化,消除采用多核平台并行化所造成的数据泄漏、数据竞争、死锁和效率低等问题。实验结果证明基于多核所提出的算法具有较高的并行效率和较好的加速比。

目录

文摘

英文文摘

1 绪论

1.1 研究背景

1.2 研究现状

1.3 本文研究内容及组织结构

2 并行计算相关理论

2.1 并行计算概述

2.2 并行机

2.2.1 并行机的发展

2.2.2 集群系统

2.2.3 多核系统

2.3 并行程序设计及优化

2.3.1 MPI并行及优化

2.3.2 OpenMP并行及优化

2.3.3 面向任务编程

2.3.4 混合编程

2.4 并行算法及其性能评测

3 并行实验平台

3.1 集群平台

3.2 多核平台

4 并行求解线性方程组的设计与实现

4.1 Cholesky分解算法

4.2 基于集群系统的Cholesky分解并行化

4.2.1 块分配

4.2.2 块交叉分配

4.2.3 卷帘分配

4.2.4 实验结果及分析

4.3 基于任务的Cholesky分解多核并行化

4.3.1 串行算法的瓶颈问题

4.3.2 OpenMP方法并行化

4.3.3 TBB任务并行化

4.3.4 并行化程序调试与优化

4.3.5 实验结果及分析

5 关联规则挖掘算法的多核并行优化

5.1 关联规则问题描述

5.2 Apriori算法多核并行及优化

5.3 算法并行优化步骤

5.4 实验结果及分析

结论

参考文献

攻读硕士学位期间发表学术论文情况

致谢