多核平台上支持推测并行化的事务存储体系结构性能优化

摘要

随着多核平台的普及，如何利用多核加速串行应用的执行已成为学术界和工业界共同关注的热点研究问题。而传统的显式锁同步机制自身就有着高复杂性、易错性和性能保守等天然缺陷，从根本上限制了并行程序的可扩展性和编程效率，也限制了对多核资源的充分利用。为了开发更多的多核结构上可利用的线程级并行性，利用事务存储(Transactional Memory，TM)技术来解决并行程序正确性维护给并行编程带来的复杂性和对性能的制约问题，已成为学术界和工业界的共识。本文从有效开发应用中的线程级并行性入手，着眼于高效能、易编程和可兼容这三个目标，通过软硬件协同的优化方式对支持推测并行化的多核事务存储体系结构展开深入研究，使之既能提高多核芯片片上计算资源的有效利用率，又能有效降低并行编程难度，平滑移植传统应用软件。
　　 本文从线程划分和线程执行两个方面，对软硬件协同支持推测并行化的多核事务存储体系结构性能优化开展了深入系统的研究，涉及结构模型、编程模型、性能分析模型、离线剖析指导线程划分机制和在线剖析指导线程执行机制等方面的内容。主要研究内容和成果包括：(1)对两朴主流线程级推测并行技术的发展趋势进行了详细而深入的调研，通过对其软硬件支持机制的分析与比较，提出了一种新型的软硬件协同支持推测并行化的多核事务存储体系结构设计方案。该系统在线程划分中采用软件线程级推测技术思想，而在线程执行时采用硬件事务存储技术支持，并通过离线剖析和在线剖析技术来协同各种软硬件因素，达到了同时提高程序性能和降低并行编程难度的双重目标。(2)在软件线程划分方面，从简化并行编程和提高并行执行性能的优化角度出发，提出了一套线程级推测并行性的判定准则、研究方法和剖析机制，确定了利用离线剖析技术来实现基于事务存储的线程划分方案。并依据该机制设计并实现了一套线程级推测并行性离线剖析工具集OpenPro。(3)利用OpenPro工具集，对桌面应用、多媒体应用和高性能计算应用中影响线程级推测并行性的关键因素进行剖析，从应用本身并行潜能的角度进行探讨，获得了诸如单个程序仅能有效利用16核的计算资源是当前多核技术路线的拐点等一些重要认识。(4)在线程执行支持机制方面，从可扩展性好和易于硬件实现这两个优化目标出发，提出了一种支持优先级判定的基于目录的高速缓存一致性协议，并在此基础上设计和完成了一种利用运行时库机制同时支持线程级推测和事务存储语义的分布式可扩展多核事务存储处理器PTT硬件模拟器。该处理器设计突破了以往类似方案中总线等集中式结构对硬件系统可扩展性的限制，同时实现了可扩展性好和易于硬件设计实现的目标；而这套采用积极版本管理和积极检测机制的分布式硬件事务存储机制会自动维护硬件系统的一致性，极大地减少了程序员在进行并行程序设计时的繁杂工作和复杂程度。这对于普及并行程序设计，提高并行程序生产力都有着非常重要的意义。(5)提出了一种针对线程级推测并行技术的PCL性能分析模型，并依据该模型提出了将在线剖析技术引入PTT硬件模拟平台的最终优化方案。同时通过对PTT系统多种软硬件手段实现机制的分析与协同，分别从正确性、有效性和灵活可配置性三个层次对其进行了充分的评测和分析。
　　 本文的研究工作获得了如下一些重要的认识：(1)将线程级推测技术与事务存储技术结合起来，通过软硬件因素的合理协调，可以有效地开发出串行程序中潜在的线程级并行性，同时有效地降低并行编程的难度，极大地提高并行程序设计生产力。(2)在目前以传统超标量单核构造多核芯片的技术路线下，着眼于同时兼顾硬件的有效利用率和尽可能挖掘程序中固有的并行性，在加速单个串行应用时，部分依赖严重的应用(如SPEC和一些依赖严重的科学计算程序等)采用2-4核就已经足够；而多数多媒体应用和高性能计算应用采用8-16核来加速比较合适；一些特别适合的应用则可以有效利用64-128核及以上的计算资源。(3)虽然现在线程级推测并行技术在桌面应用这样一些程序中数据依赖严重的应用中效果不佳，但在部分拥有大计算量、推测线程粒度适中并且存在模糊依赖的多媒体和高性能计算应用中还是适宜采用的。线程级推测并行技术最大的优势是其兼容性与易编程性，只要在这两点上做好文章，实现多数经典应用软件到多核平台上的平滑移植，进一步解放程序员，线程级推测并行技术就会在体系结构研究中拥有重要的一席之地。
　　 本文的研究工作和结果可用于指导共享存储的多核芯片体系结构及其并行编程环境的设计，以尽可能小的并行程序设计难度、系统软件复杂性和系统硬件代价，尽可能多地从串行程序中开发出多核芯片上可利用的线程级并行性。

目录

文摘

英文文摘

论文说明：图表目录

声明

第1章 绪论

1.1 研究背景

1.1.1利用多核加速串行应用的研究意义

1.1.2传统线程级并行技术的局限

1.2 线程级推测并行技术

1.2.1事务存储技术简介

1.2.2线程级推测技术简介

1.2.3将线程级推测技术与事务存储技术相结合的优势

1.3 论文研究目标和主要工作

1.4 论文结构

第2章 相关研究工作

2.1 线程级推测技术发展趋势

2.1.1硬件式线程级推测

2.1.2软件式线程级推测

2.1.3软硬结合式线程级推测

2.1.4线程级推测代表性工作Hydra

2.2 事务存储技术发展趋势

2.2.1硬件支持的事务存储系统实现方案

2.2.2软件支持的事务存储系统实现方案

2.2.3事务存储代表性研究工作LogTM

2.3 线程级推测与事务存储技术结合的技术发展趋势

2.3.1软硬件结合的技术发展趋势

2.3.2线程级推测与事务存储技术结合的代表性研究工作TCC

2.4 小结

第3章 线程级推测并行性研究方法与剖析工具

3.1 线程级推测并行性研究方法

3.1.1线程划分与推测执行模型

3.1.2线程级推测并行化的性能影响因素

3.1.3线程级依赖分析方法

3.1.4剖析指导的线程划分机制

3.1.5基于事务存储的线程划分方案

3.2 线程级推测并行性剖析工具

3.2.1剖析方案框架设计

3.2.2剖析工具实现机制

3.2.3 OpenPro剖析工具集设计说明

3.3 小结

第4章 线程级推测并行性的应用适应性研究

4.1 应用分类与研究意义

4.2 实验方案说明

4.3 桌面应用的适应性分析

4.3.1应用选取说明

4.3.2针对循环结构的性能评测

4.3.3针对子程序结构的性能评测

4.3.4小结

4.4 多媒体应用的适应性分析

4.4.1应用选取说明

4.4.2针对循环结构的性能评测

4.4.3针对子程序结构的性能评测

4.4.4小结

4.5 高性能计算应用的适应性分析

4.5.1应用选取说明

4.5.2针对循环结构的性能评测

4.5.3针对子程序结构的性能评测

4.5.4小结

4.6 小结

第5章 多核事务存储处理器系统设计优化

5.1 简介

5.1.1设计思路

5.1.2优化方案

5.2 硬件结构模型

5.2.1硬件体系结构

5.2.2推测执行硬件支持机制

5.2.3按序提交硬件支持机制

5.3 编程模型

5.3.1循环封装

5.3.2变量声明调整

5.3.3运行时库

5.3.4编译器支持

5.4 线程执行模型

5.4.1概述

5.4.2推测线程初始化

5.4.3推测线程启动

5.4.4推测线程执行

5.4.5推测线程提交

5.5 PTT模拟器实现

5.5.1 GEMS模拟器简介

5.5.2 PTT模拟器实现说明

5.6 小结

第6章 支持推测并行化的多核事务存储体系结构性能评测

6.1 实验方案

6.1.1方案概述

6.1.2测试程序集

6.1.3实验配置及其计算访存通信代价模型

6.2 基本性能评测

6.2.1加速比分析

6.2.2回退率分析

6.2.3 IPC分析

6.2.4缓存缺失率分析

6.2.5链路延迟分析

6.2.6小结

6.3 系统性能影响因素评测

6.3.1互联拓扑

6.3.2令牌传递开销

6.3.3 L2 Cache组织

6.3.4线程启动策略分析

6.3.5线程重试策略分析

6.3.6小结

6.4 剖析指导的优化方案

6.4.1设计原理

6.4.2在线剖析PCL性能分析模型

6.4.3线程启动阶段的优化

6.4.4线程执行阶段的优化

6.4.5小结

6.5 小结

第7章 全文总结

7.1 研究工作和成果

7.2 主要创新

7.3 进一步的工作

参考文献

致谢

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

在读期间参与的科研项目