面向多核的串行程序并行化关键技术研究

摘要

随着计算机硬件的迅速发展，多核处理器已经广泛应用于工业设计和日常生活中。理论上增加处理器的核数，则可执行的指令数就将有成倍的增长，但是在多核处理器上运行现存的大量串行程序并没有获得预期加速的效果，这是由于串行程序在多核处理器上并不能自动并行而获得加速。因此如何利用多核处理器加速已有的串行程序已经成为学术界和工业界关注的热点研究问题。
　　事务存储技术和线程级推测技术成为提高串行程序在多核处理器上执行效率的关键技术。事务存储技术有效地解决了传统并行编程模型中采用锁和信号量机制实现线程间的同步/互斥以及对共享资源的访问所带来的死锁、优先级反转等诸多问题。线程级推测技术打破了线程间依赖对线程并行执行的限制，可以进一步挖掘程序的并行性，有效提高程序的可扩展性。
　　论文围绕串行程序并行化技术，重点从事务存储和线程级推测技术两个方面展开深入研究，主要研究工作与创新点如下：
　　为了高效实现嵌套软件事务存储(Nested software transactional memory,NSTM)系统，分析研究了事务之间的冲突依赖关系，对比了积极冲突检测/懒惰冲突检测、读透明/读可见等检测方法，提出了NSTM的语义模型、基于读可见-懒惰冲突检测策略的冲突检测方法，以及基于动态优先级的随机退避(Random Back-off of Dynamic Priority, RBDP)机制。将RBDP冲突消解策略和常用冲突消解策略进行对比测试，RBDP冲突消解策略明显优于其他冲突消解策略。
　　在软件事务存储的基础上，提出了一种基于路径的贪婪线程划分算法，该算法采用乱序激发的策略实现函数、循环区域和非循环区域的线程划分。同时给出了基于事务的循环调用推测执行模型和函数调用推测执行模型，并针对基于事务的线程推测机制中存在的线程间并行、线程内并行和嵌套事务并行的依赖冲突提出了支持线程级推测的嵌套事务存储系统的冲突检测和消解策略，有效的降低了事务之间的冲突概率。
　　在研究线程级推测技术和现有事务存储模型理论的基础上，设计实现了一个支持线程级推测技术的软件嵌套事务存储系统(software nested thread level speculation based on transactional memory, SNTLTM)系统。SNTLTM系统采用Swiss TM系统作为基系统并结合 SUIF2编译器进行原型开发。SNTLTM系统采用Write Buffer的方法进行版本管理，采用支持线程级推测的嵌套事务冲突检测策略实现冲突检测，采用RBDP策略实现冲突消解，采用基于路径的贪婪线程划分算法实现函数、循环和非循环区域的线程划分。采用8线程和STAMP基准对SNTLTM系统进行测试，测试表明SNTLTM比Swiss TM的加速比平均提高了14.8％，事务的放弃率下降了3.9%。
　　将SNTLTM应用于基于机器视觉的机械零件检测中，运用SNTLTM的定制优化开发接口设计并实现了I-SNTLTM图像增强预处理系统，该系统支持灰度校正、灰度变换、直方图规定化、直方图均衡化、均值滤波、中值滤波、梯度锐化和拉普拉斯锐化八种图像增强算法，有效地提高了图像增强算法的运行效率。

目录

封面

声明

中文摘要

英文摘要

目录

图目录

表目录

1. 绪论

1.1研究背景

1.2基于多核的并行程序设计模型

1.3论文主要工作和创新

1.4论文结构

1.5小结

2. 相关研究工作

2.1. 软件线程级推测机制

2.2. 软件事务存储系统

2.3. 小结

3. 嵌套软件事务存储系统冲突管理机制

3.1嵌套软件事务存储系统

3.2冲突检测

3.3冲突消解

3.4小结

4. 基于嵌套事务的软件线程级推测机制

4.1基于路径的贪婪线程划分算法

4.2基于事务的线程推测执行策略

4.3推测嵌套事务冲突竞争管理

4.4小结

5. 支持线程级推测技术的嵌套软件事务存储系统的实现

5.1. SNTLTM系统设计

5.2. 基于SUIF2的SNTLTM原型系统开发

5.3. SNTLTM系统量化分析

5.4. 小结

6. SNTLTM在机械零件检测图像增强中的应用

6.1基于机器视觉的机械零件检测

6.2面向图像增强的I-SNTLTM设计与实现

6.3面向图像增强的I-SNTLTM实例分析

6.4小结

7. 结束语

7.1. 研究工作总结

7.2. 研究展望

致谢

参考文献

附录1 攻读博士学位期间发表的论文目录