论文部分内容阅读
随着计算机体系结构技术的深入发展和芯片制造工艺的不断进步,CPU微体系结构呈现出众核化、异构化的发展趋势,给传统并行编程模式带来新的挑战。而应用程序的多样化发展进一步加剧了并行编程难的问题。在这种背景下,程序员对高效、易用、普适的并行编程模型的需求越来越迫切。如何简便高效地挖掘线程级并行性成为并行计算领域的热点问题之一。本文针对传统软件猜测并行模型全局开销较高,性能损失较大,易用性较差等问题,设计实现了新型软件猜测并行模型HEUSPEC,并基于HEUSPEC的开销模型,有针对性地提出并实现了四种优化技术——启发式值预测技术、跨线程取技术、动态任务粒度调整技术和乱序确认技术,有效地降低了传统软件猜测并行模型的全局开销,提升了猜测执行的整体性能。具体而言,本文的主要工作和创新点体现在:提出了一种高效软件猜测并行模型HEUSPEC(第二章)。猜测并行的全局开销较高一直是软件猜测并行模型的致命缺陷。为此,本文针对传统软件猜测并行模型开销高,易用性差等问题,提出了软件猜测并行模型HEUSPEC,并根据该模型的工作原理,给出了适用于软件猜测并行模型的全局开销解析模型。实验数据表明,HEUSPEC较之传统软件猜测并行模型,性能较高(在3,7两个猜测深度下较之传统模型加速比提升12.43%和9.78%),时空开销较低,且可扩展性较好。本文将HEUSPEC与三类典型的隐式并行编程模型做了对比,阐明了HEUSPEC的高效性和易用性。提出了一种降低规则变化冲突变量误猜率的启发式值预测技术(第三章)。现有软件猜测并行模型中的值预测方法不能满足“简单高效”的要求。为此,本文提出了启发式值预测技术(Heuristic Value Prediction,HVP)。启发式值预测采用多个预测器,基于冲突变量历史值档案,对冲突变量值进行预测,并通过评分系统在多种预测方案中选择理论上最可靠的预测结果。启发式值预测技术吸收了随机多重值预测和预计算值预测的长处,既使得单个预测器具有一定智能,又避免消耗大量硬件线程。实验表明,启发式值预测技术能够有效降低程序执行时的误猜率,提升猜测并行的性能(3,7,15,31四个猜测深度下较之无值预测模型平均性能提升5.54%,5.28%,4.35%和11.15%)。提出了一种降低整体误猜率的跨线程取技术(第四章)。基于历史值的值预测机制对于变化规律较为复杂的冲突变量预测效果较差。为了弥补这一缺陷,本文提出了跨线程取技术(Inter-thread Fetching,IF)。该技术在不破坏软件猜测并行模型的线程隔离机制基础上,允许猜测线程之间交换未确认提交的数据。跨线程取技术对所有类型的冲突变量都能有效提升猜测精度。它通过扩展消费者线程猜测读的安全时间域,增大消费者线程猜测读正确的概率。实验表明,跨线程取技术能够显著提升猜测准确率和猜测并行性能(3,7,15,31四个猜测深度下较之无值预测模型,加速比平均提升33.10%,29.77%,15.24%和40.43%),且具有较低的空间开销。提出了一种优化全局开销的动态任务粒度调整技术(第五章)。传统软件猜测并行模型多采用固定任务粒度,不能很好地适应误猜率不断变化的代码,猜测并行化开销较高。本文根据软件猜测并行模型的开销解析模型,对全局开销与任务粒度的关系进行深入分析,给出最小化全局开销的任务粒度调整公式,并据此提出了动态任务粒度调整技术(Dynamic Task Granularity Resizing,DTGR)。该技术采用动态优化思想,在猜测执行过程中根据实时统计的误猜率,回滚开销及控制开销,利用由开销模型导出的调整公式动态地调整任务粒度,使全局开销结构趋于最优化。实验表明,动态任务粒度调整技术能够显著降低猜测并行模型对包含非确定性相关程序的全局开销,提升猜测执行性能,且具有较好的可扩展性。提出了一种降低控制开销的乱序确认技术(第六章)。传统软件猜测并行模型中的顺序确认机制在猜测任务之间无相关的情况下可能造成不必要的额外开销。为此,本文提出了乱序确认技术(Out-of-Order Committing,OOC)。该技术能够在任务间无相关的情况下,有效减少顺序确认机制下猜测线程不必要的等待,加快任务分发速率,降低全局开销,同时不影响猜测执行的正确性。实验表明,该技术能够提升无相关程序的猜测执行效率(3,7,15,31四个猜测深度下较之顺序确认模型,加速比平均提升0.59%,4.34%,6.61%和3.00%)。