多核推测并行流水线模型下的冲突解决

摘要

随着多核处理器平台的广泛流行，如何从传统的串行程序中提取并行性，以提高其在多核平台上的执行性能已是当务之急。利用推测并行流水线技术由编译器自动地将串行程序转换成推测多线程并行程序，这一很有前景的自动并行化技术随之兴起。所有相关的技术通常都基于一个乐观的前提假设，即因推测而去除的循环携带的依赖关系在程序的执行过程中几乎或是很少发生。令人遗憾的是，在某些应用中却被观察到，为了构建负载均衡的流水线利用上述假设推测去除了某些循环携带的依赖关系，但在实际的程序执行过程中，这些依赖关系却频繁的发生着。在这种情况下，由该类依赖（被称为“矛盾”依赖）引起的数据冲突会导致程序频繁的回退，使得之前的自动并行化技术很难再加速串行程序。
　　为了解决串行程序中存在“矛盾”依赖的问题，提出了多核并行流水线模型下的冲突解决。本课题的研究目标是，在多核结构中使用推测并行流水线技术加速串行程序时，合理利用提出的冲突解决来降低由“矛盾”依赖引起的较高的推测失败率。其意义在于，它不仅能够延续了推测并行流水线技术的优势从串行程序中提取更多的线程级并行性，而且还扩大了该技术的适用范围。冲突解决充分利用了推测并行流水线模型背后的设计原理，通过动态监测冲突发生的频率来定位程序中的“矛盾”依赖；当“矛盾”依赖被确定后，通过执行插桩代码动态计算依赖中所涉及的读写访问距离；依据读写访问距离比采取相应的代码优化策略，使其尽可能达到安全访问距离的标准；为了能够让冲突数据被后续访问者及时可见，辅以高效的核间直通机制进一步保证冲突数据在核间快速传递。实验的结果表明，在指定的测试集合中使用该冲突解决可以平均降低推测失败率20％左右。

目录

声明

1 绪 论

1.1 课题背景

1.2 国内外概况

1.3 论文的主要研究工作

1.4 论文组织

2 冲突解决总体设计

2.1 启发性示例

2.2 冲突解决的可行性分析

2.3 冲突解决各模块功能结构设计

2.4 本章小结

3 冲突解决模块功能实现

3.1 动态冲突监测和读写访问距离计算

3.2 代码优化

3.3 核间快速直通

3.4 冲突解决的设计优化

3.5 本章小结

4 实 验

4.1 实验环境

4.2 实验结果分析

5 总结与展望

致谢

参考文献