事务存储编程和KD-50-I万亿次机软件库优化的若干问题研究

论文摘要

随着并行计算机的发展,特别是片上多处理器CMP（Chip MultiProcessor）,又通称为多核处理器的出现,人们逐渐认识到并行计算加速应用的重要性,但是普及并行计算主要受到并行编程复杂和高性能计算机价格昂贵等方面因素的制约。本文研究工作分为两个部分:一是研究多核下事务存储并行编程技术,从而减轻并行编程难度;二是优化首台国产万亿次高性能计算机KD-50-I的软件库（数学库和通信库）,以利于低功耗、低价位的国产高性能机推广普及。本文主要研究内容和贡献与创新是:1.基于事务存储执行的并行编程模型讨论了未来多核体系结构上基于事务存储执行的并行编程技术,实现了编写事务存储执行程序框架的软件库,通过提供一系列开始、提交和终止等事务执行程序接口,以详细和直观的方式对源代码实现事务相关,从而对新型软件事务存储算法和技术的验证,以及硬件事务存储执行平台的设计具有指导意义。2.扩充OpenMP支持事务存储执行功能虽然OpenMP是多核体系结构上的流行多线程并行编程模型,但是OpenMP编译器不检查数据相关性、访问冲突和其他可能导致程序错误执行的问题,这些问题传统上完全依赖用户使用锁机制来保证程序的正确性。锁机制的并行编程中存在并行程序效率和并行编程难度的矛盾。粒度大的锁机制编程容易,可应用的并行性挖掘比较差;粒度小的锁机制应用的并行性挖掘较好,可编程难度大,容易带来优先权倒置、死锁和锁护航等问题。本文通过扩充OpenMP支持事务存储执行功能,可有效缓解OpenMP并行编程中并行程序效率和并行编程难度之间矛盾。3.多核下事务存储执行并行加速串行二进制程序历史遗留无源码的二进制代码由于多是单线程串行程序,无法充分利用到现有多核处理器计算资源。若想在多核下得到性能的提升,可以通过反编译得到伪代码,然后对伪代码多线程并行化。其主要困难是:一是反编译对数据类型和复杂控制流恢复很困难,得到的伪代码可读性很差;二是程序并行化时分析程序的数据相关性很难,分析可读性差的伪代码更难。提出反编译二进制代码到中间代码,然后利用事务存储执行原理,对中间代码并行投机多线程编译,（假定线程间的依赖关系不存在,放松对编译器的限制,选择可以投机并行执行的部分并行执行）。通过冲突检测和事务撤销机制,保证即使依赖存在,对程序结果的正确性也没有影响。从而解决了以往反编译得到的伪代码的信息不完整和并行编译器保守的问题,更充分的挖掘了二进制程序的潜在并行性。4.首台国产万亿次机KD-50-I的数学库和通信库优化国产万亿次机KD-50-I具有低功耗、低占地面积、高计算密度三大特点,对未来研制国产千万亿次计算机系统及提高其自主创新性具有示范作用。本文针对万亿次机节点使用的龙芯2F处理器支持乘加指令和四发射流水线的特点,采用循环展开和指令调度提高指令的并行性,以及采用预取减小访问内存的开销等技术优化了数学库;同时针对万亿次机节点间拓扑固定、层次简单的网络结构特点,采用简化的LBP通信模型分析优化了通信库。数学库和通信库的优化,提高了KD-50-I的并行应用运行效率,对KD-50-I国产高性能机的推广普及具有重要的意义。5.国产万亿次机KD-50-I在并行数据挖掘在中的应用研究基于串行计算机系统的数据挖掘技术,已经远远不能满足海量数据和极其复杂的运算的需求。随着网络技术、高性能计算机的发展,并行数据挖掘成为解决上述问题的可能。本文选择以金融风险管理应用为背景,结合国产万亿次机KD-50-I节点使用处理器的特点和节点间网络拓扑结构,优化并行数据挖掘算法,提高了应用运行效率,为KD-50-I在不同领域的应用,提供了并行算法设计和并行编程的参考。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 并行计算
• 1.1.1 概述
• 1.1.2 并行计算机体系结构模型
• 1.1.3 并行计算机访存模型
• 1.1.4 多核处理器结构
• 1.1.5 并行程序设计模型
• 1.2 当前并行计算所面临的问题
• 1.3 研究内容及思路
• 1.4 文献资源
• 1.5 本文组织结构
• 第二章 基于事务存储执行的并行编程模型
• 2.1 线程级并行编程模型
• 2.1.1 多线程简介
• 2.1.2 多线程并行编程模型
• 2.1.3 多线程并行编程实现
• 2.1.4 事务存储与锁机制
• 2.2 事务存储简介
• 2.2.1 硬件事务存储
• 2.2.2 软件事务存储
• 2.2.3 软硬件混合事务存储
• 2.3 事务存储并行编程模型框架
• 2.3.1 事务管理数据结构
• 2.3.2 事务管理接口
• 2.3.3 事务冲突检测管理
• 2.3.4 事务冲突仲裁管理
• 2.3.5 简化编程
• 2.4 测试结果和分析
• 2.5 相关工作
• 2.6 本章小结
• 第三章 扩充OpenMP并行编程模型支持事务存储
• 3.1 OpenMP并行编程模型
• 3.1.1 OpenMP简介
• 3.1.2 扩充OpenMP支持事务存储
• 3.2 系统设计和实现
• 3.2.1 插桩分析函数
• 3.2.2 事务冲突检测
• 3.2.3 事务冲突仲裁
• 3.3 测试结果和分析
• 3.3.1 共享记数器
• 3.3.2 哈希表
• 3.3.3 红黑树
• 3.4 相关工作
• 3.5 本章小结
• 第四章 事务存储执行并行加速串行二进制程序
• 4.1 反编译
• 4.1.1 反编译简介
• 4.1.2 反编译系统的实现技术
• 4.1.3 反编译模式
• 4.2 投机多线程编译
• 4.3 系统框架
• 4.4 测试结果与分析
• 4.4.1 SESC模拟器
• 4.4.2 示例程序
• 4.5 相关工作
• 4.6 本章小结
• 第五章 国产万亿次机KD-50-I的数学库和通信库优化
• 5.1 KD-50-I系统结构
• 5.2 通信协议分析和优化
• 5.2.1 点对点通信
• 5.2.2 全局通信
• 5.2.3 通信性能测试结果
• 5.3 Linpack数学库优化
• 5.3.1 Linpack数学库简介
• 5.3.2 针对龙芯体系结构的优化技术
• 5.3.3 数学库性能测试结果
• 5.4 相关工作
• 5.5 本章小结
• 第六章 万亿次机KD-50-I在并行数据挖掘中的应用研究
• 6.1 并行数据挖掘技术
• 6.1.1 并行关联规则算法
• 6.1.2 并行神经网络算法
• 6.1.3 并行遗传算法
• 6.1.4 并行聚类算法
• 6.2 并行数据挖掘应用
• 6.2.1 应用背景简介
• 6.2.2 并行K平均聚类评级模型
• 6.2.3 测试结果和分析
• 6.2.4 性能优化
• 6.3 相关工作
• 6.4 本章小结
• 第七章 结束语
• 7.1 本文主要工作
• 7.2 本文主要贡献和创新点
• 7.3 进一步工作
• 参考文献
• 致谢
• 攻读学位期间所参与的科研项目
• 攻读学位期间所发表和录用的学术论文