CA-编译器控制的预取

[[CA-NotesView]]

Recap

Cache性能分析

✔️ 平均访存失效

✔️ CPU时间

改进Cache性能

降低失效率

✔️ 3C失效 （强制性失效，容量失效，冲突失效）

✔️ 调节块的大小

✔️ 提高相联度

✔️ Victim Cache 和伪相连Cache

✔️ 硬件预取

✔️ 编译器控制的预取

编译器控制的预取

$T_{访存} = T_H + F \times T_M$

没有预取的时候 251次失效

有预取的时候：19次失效

编译器优化

1. 基本思想 ： 在编译的时候，对程序中的执行和数据进行重新的组织，降低Cache失效率

2. 可以重新组织程序不影响程序的正确性

• 把一个程序中的过程重新排序，就可能会减少冲突不命中，从而降低不命中率。

✔️ 研究如何使用配置文件来执行优化

✔️ 2K字节，缺失率降低50%，8K字节，缺失率降低75%

针对数据的编译优化技术包括：

• 数组合并

存的位置更集中，更容易进行访存

• 内外循环交换

有些计算是用列来进行运算的时候将数组进行转置，转换成行的计算

• 循环融合

对同样的数据做不同的运算，就能够在一个循环里面进行，可以在读入Cache的数据在被替换出去之前得到反复的使用

• 分块

降低Cache失效率的方法

增加块的大小

提高相联度

牺牲Cache

伪相连

硬件预取指令和数据

编译器控制的预取

用编译技术减少Cache不命中次数

减少Cache失效开销

写缓冲和写合并

写直达Cache

• 依靠写缓冲来减少对下一级存储器写操作的时间

• 如果写缓冲其为空，就把数据和对应的地址写入缓冲器

• 从CPU的角度来看，写操作就是完成了

提高写缓冲的效率和利用率 写合并

提好了写缓冲器的空间利用率，而且还能减少因为写缓冲器满了而要进行的等待时间。

• 如果写缓冲器中已经有了待写入的数据，就要把这次的写入地址与写缓冲器中已有的所有地址进行比较，看是否有匹配的项如果有地址匹配而对应的位置又是空闲的，就把这次要写入的数据与该项合并。这就叫写缓冲合并。

• 如果写缓冲器满且又没有能进行写合并的项，就必须等待

让读失效也优先于写

1. Cache中的写缓冲器导致对存储器访问的复杂化

在读不命中时，所读单元的最新值有可能还在写缓冲器中，尚未写入主存。

例5.9 考虑以下指序列:

SW R3,512(R0),  ;M[512]-R3 (Cache Index =0)
LW R1，1024(R0) ;R1-M[1024](Cache Index =0)
LW R2, 512(R0)  ;R2-M512](Cache Index =0)

假设Cache采用写直达法和直接映像，并且地址512和1024映射到同一块，写缓冲器为4个字，问R2的值总等于R3吗?

在执行SW指令之后，R3中数据放入ndex为0的Cache块和写缓器。第一条LW指令将该位置上的数据替换成MI[1024] (读失效)，第条LW指令又要替换这块Cache为M[512] (读失效)如果此时写缓冲还未更新完MI[512]，则R2不等于R3

2. 解决问题的方法(读失效的处理)

推迟读失效的处理直到写缓冲排空

缺点: 读失效的开销增加

优先读操作

读失效时先检查写缓冲器中的内容
缺点:增加硬件

请求字处理

1. 请求字(Requested Word)

从下一级存储器调入Cache的块中，只有一个字是立即需要的。这个字称为请求字。

2. 应尽早把请求字发送给CPU

尽早重启动：调块时，从块的起始位置开始读起旦请求字到达，就立即发送给CPU，让CPU继续执行。

请求字优先：调块时，从请求字所在的位置读起。这样，第一个读出的字便是请求字。将之立即发送给CPU。

3. 这种技术在Cache块比较小的情况下的效果不大，下一指令正好访问同一个Cache块的另一个部分

多级Cache

1. 应把Cache做得更快?还是更大?

答案:二者兼顾，再增加一级Cache

• 第一级Cache(L1)小而快。

与快速的CPU运行时钟周期时间相匹配

• 第二级Cache(L2)容量大

捕捉到对主存进行的大多数访问

2. 性能分析

$平均访问时间 = 命中时间_{L1} + 失效率_{L1} \times 失效开销_{L1}$

3. 局部失效率和全局失效率

$局部失效率 = 该级Cache的失效次数/到达该级Cache的访问次数$

$全局失效率 = n级Cache的失效次数/CPU发出的访存总次数$

$全局失效率 = 失效率_{L1} \times 失效率_{L2}$

评价多级Cache的时候应该使用全局失效率的指标

假设某一两级Cache: 第一级Cache为L1，第二级Cache为L2(1) 设在1000次访存中，L1的不命中是40，L2的不命中是20。求各种局部不命中率和全局不命中率。(2L210个，L2开200时钟周期，L1的命中时间是1个时钟周期，平均每条指令访存1.5次，不考虑写操作的影响。问:平均访存时间是多少?每条指令的平均停顿时间是多少个时钟周期?

解
(1)
第一级Cache的不命中率(全局和局部) 是40/1000，即4%;
第二级Cache的局部不命中率是20/40，即50%;
第二级Cache的全局不命中率是20/1000，即2%。
(2)
平均访存时间 = 命中时间_{L1}
=1+4% * (10+50% *200)
=1+4% * 110 = 5.4个时钟周期
每次访存的平均停顿时间为: 5.4-1.0=4.4
所以:
由于平均每条指令访存1.5次每条指令的平均停顿时间=4.4 * 1.5=6.6个时钟周期

Miss Status Holding Register

MSHR包含正在等待处理的失效

相同的块可以包含多个未解决的Load/Store失效

可以有多个没有解决的块地址

失效可以分为：

1. 第一次发起存储请求的时候的字符串

MSHR Operation

当失效的时候

优化技术	命中开销	硬件复杂度
写缓冲写合并	+	1
使读失效优先于写	+	1
请求字处理	+	2
两级cache	+	2
非阻塞cache	+	3

减少命中时间

命中时间直接影响到处理器的时钟频率。在当今的许多计算机中，往往是Cache的访问时间限制了处理器的时钟频率

容量小，结构简单的Cache

硬件越简单 速度就越快。

应该让Cache足够小，便于可以和CPU一起放在同一块芯片上。

折衷：Cache放在片内，把Cache的数据存储器放在片外，这样既可以实现快速标识检测，又能利用独立的存储芯片来提供更大的容量。

多级Cache，一级Cache大多采用2路组相联或者直接映像。

In recent designs, there are three other factors that have led to the use of higher associativity in first-level caches

• many processors take at least two clock cycles toaccess the cache and thus the impact of a longer hittime may not be critical

• with the introduction of multithreading, conflict missescan increase, making higher associativity moreattractive

• keep the TLB out of the critical path (a delay thatwould be larger than that associated with increasedassociativity

主存

存储器组织技术

假设基本存储器结构的性能为：

送地址需要4个时钟周期，每个字访问时间为24个时钟周期

传送一个字的数据需要4个时钟周期

如果Cache大小是4个字，那么：

$失效开销=4 \times (4+24+4) = 128(时钟周期)$

存储器组织技术：

1. 增加存储器的宽度

增设Cache和多路选择器

性能分析:失效开销更改为32周期，带宽变为0.5字节/周期

缺点：

• 增加CPU和存储器之间的连接通路宽度
• CPU和Cache之间有一个多路选择器
• 扩充主存的最小增量增加了相应的倍数
• 写入有可能变得复杂

实例：DEC的Alpha Axp21064

2. 采用简单的多体交叉存储器

存储系统中采用多个DRAM，利用它们潜在的并行性

分时启动

每个个体都有独立的MAR和读/写电路

初始的时间是CPI=3.15

块 2个字

64位总线和存储器，不采用多体交叉

性能提高了14%