高性能微处理器中自适应高速缓存管理策略研究

摘要

对主存储器的访问是制约高性能微处理器系统性能的主要因素之一。存储器的访问速度通常会比处理器速度慢两个数量级，为了缩小这一差距，当代处理器设计已经将一半以上的片上晶体管资源用于最后一级高速缓存。然而，针对小容量一级高速缓存的传统管理策略并不能有效地管理大容量最后一级高速缓存，由此引发了大量的高速缓存缺失，从而导致频繁的片外内存访问和处理器性能的严重下降。增加的访存延迟、有限的片外带宽、破坏性的线程间干扰、多样化的负载特性、扩大化的新兴应用工作集规模，单一芯片内所集成处理器核数目的增加，以及由此导致的每个处理器核所占有高速缓存空间的减少等诸多方面的因素都给高速缓存的设计带来了极大的挑战，也使得高速缓存管理策略的重要性变得越发关键。本文重点分析了高性能微处理器尤其是多核处理器中最后一级高速缓存管理的若干热点问题，并提出相应的开销合理的解决方案来提高系统性能。论文的主要研究内容与创新之处包括：
　　 1.同时多线程处理器中高速缓存公平划分技术研究。传统的LRU替换策略会根据线程的需要隐式地对共享高速缓存进行划分，不同负载时间重用行为的差异导致它们对高速缓存资源的竞争能力存在差别，这会对并发调度线程的推进速度造成不一致的影响。不公平高速缓存共享问题使得操作系统线程调度的效率遭到丧失，线程饿死、优先级反转等问题呈现。针对这一情况本文实现了一种自适应、运行时划分机制(ARP)来管理共享高速缓存，该机制以提高公平性为优化目标，在每个周期内使用基于动态组采样的硬件监控器电路来收集栈距离剖析信息，从而精确地估计每个线程公平性度量的数值，并利用划分与回滚相结合的贪心算法来确定最优的划分方案。实验结果表明，相比于LRU策略，ARP可以将一个2.路同时多线程处理器的公平性提高2.26倍，同时将吞吐量平均提高14.75％。
　　 2.多核处理器中高速缓存颠簸避免技术研究。随着最后一级高速缓存容量和相联度的增长，LRU策略和理论最优替换算法之间的性能差距日趋增大，引起这一问题的主要原因是LRU策略会导致大工作集访存密集型负载发生高速缓存颠簸，并且在选择替换块时仅仅考虑了高速缓存访问的临近信息而忽视了数据的访问频率。本文指出访存密集型负载的性能可以通过无用数据的及早替换和改变低使用频率数据的插入和提升位置而得到显著提升，基于这一思想本文提出无用块消除和低使用频率块过滤高速缓存管理策略，该策略利用活动时间预测器来预测数据块的使用频率，根据预测结果将无用数据提早替换，将低使用频率数据插入到低优先级位置以降低其驻留在缓存空间的时间，从而成功地避免工作集规模大于共享高速缓存容量的访存密集型负载发生颠簸，并考虑了程序中数据的临近性和使用频率信息。与LRU相比将
　　 4.路多核处理器的加权加速比平均提升14.5％。
　　 3.多核处理器中高速缓存混合管理策略研究。目前传统的单一高速缓存管理策略已经无法满足不同局部性特征负载的性能需要，当并发执行的线程间存在破坏性干扰或者负载的工作集超过可用高速缓存容量时，最后一级高速缓存的性能以及由此关联到的多核处理器的性能都会严重下降。针对这一问题，本文提出划分感知淘汰线程感知插入/提升(PAE-TIP)混合高速缓存管理策略，该策略采用低开销的锦标赛机制来确定每个线程缺失数据块的插入位置和命中数据块的提升位置，并且根据基于效用的高速缓存划分算法所提供的目标分配方案未选择被淘汰的数据块。能够同时对共享高速缓存实施包括容量管理、自适应插入和自适应提升在内的混合管理，在多种具有不同数据局部性特征的访存行为之间进行必要的折衷。实验表明，相比于传统的LRU策略，PAE-TIP能够将4-路多核处理器的加权加速比平均提高19.3％。

目录

文摘

英文文摘

图目录

表目录

第1章 绪论

1.1 高性能微处理器的发展

1.2 片上高速缓存管理

1.2.1 高速缓存的设计挑战

1.2.2 高速缓存的管理策略

1.3 本文的研究内容及意义

1.4 本文的主要贡献

1.5 本文的组织结构

第2章 高性能微处理器发展概述

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.2.4 线程级并行性

2.2.5 同时多线程

2.3 多核处理器

2.4 小结

第3章 高性能微处理器高速缓存研究现状

3.1 高速缓存

3.1.1 背景及相关术语

3.1.2 片上共享高速缓存

3.2 降低Cache缺失

3.2.1 减少冲突缺失

3.2.2 减少容量缺失

3.2.3 减少一致性缺失

3.3 优化Cache管理策略

3.3.1 优化替换策略

3.3.2 Cache旁路

3.3.3 数据及早淘汰

3.4 多核Cache划分

3.5 混合Cache设计

3.5.1 基于共享Cache的设计方案

3.5.2 基于私有Cache的设计方案

3.6 其他片上存储系统优化技术

3.6.1 高速缓存预取

3.6.2 提高Cache的访问带宽

3.6.3 操作系统级Cache性能优化

3.6.4 一致性协议的优化

3.6.5 内存控制器的优化

3.7 小结

第4章 面向公平性的共享高速缓存划分

4.1 引言

4.2 LRU策略的相关特性

4.2.1 LRU策略的不公平性

4.2.2 LRU策略的栈特性

4.3 SMT处理器二级Cache共享度的研究

4.4 ARP:自适应运行时Cache划分

4.4.1 ARP的硬件结构

4.4.2 ARP的算法描述

4.4.3 替换策略的修改

4.5 性能评价方法

4.6 实验结果及分析

4.6.1 二级Cache的共享度

4.6.2 ARP机制的吞吐量评测

4.6.3 ARP机制的公平性评测

4.6.4 ARP机制的开销

4.7 相关工作

4.8 小结

第5章 基于使用频率的插入提升策略

5.1 引言

5.2 背景

5.2.1 负载特性

5.2.2 Cache插入和提升

5.2.3 相关工作

5.3 无用块消除和低重用块过滤Cache管理

5.3.1 ELF硬件结构

5.3.2 ELF策略

5.4 性能评价方法

5.5 实验结果及分析

5.5.1 性能加速比

5.5.2 Cache块使用频率预测精度分析

5.5.3 对Cache容量的敏感度分析

5.5.4 插入和提升行为

5.5.5 硬件设计开销

5.6 小结

第6章 划 分感知淘汰线程感知插入提升策略

6.1 引言

6.2 背景

6.2.1 负载特性

6.2.2 Cache划分

5.2.3 Cache插入和提升

6.3 共享Cache管理

6.3.1 线程感知提升策略

6.3.2 划分感知淘汰

6.3.3 PAE-TIP

6.4 实验方法

6.5 实验结果及分析

6.5.1 性能加速比

6.5.2 划分控制

6.5.3 插入和提升行为

6.5.4 对流数据的感知

6.5.5 硬件开销

6.6 相关工作

6.7 小结

第7章 总结及未来工作

7.1 本文工作总结

7.2 未来研究工作

参考文献

附录 相关术语

致谢

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

在读期间参与的科研项目