编译器控制的预取
编译器控制的预取的出现
预取技术(指令和数据都可以在处理器提出访问请求之前进行预取)可以实现在不影响处理器时钟频率的前提下降低Cache失效率。预取的内容可以直接放入Cache中也可以放在一个访问速度比主存快的外部缓冲器中,如寄存器。如果指令预取由Cache之外的硬件完成,Cache快的管理、替换完全由硬件决定,则是在实现硬件预取。研究
表
关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf
明,在任何时刻Cache中有相当一部分数据块在被替换出Cache前不会被再次重用,这种现象叫做Cache 污染,它严重地降低了Cache性能。此时,利用编译器的支持,可以减少不必要的预取。
编译器控制的预取的目的是要是指令和读取数据能重叠执行。它有典型的优化对象,即循环。如果失效开销小,编译器需将循环展开一次或两次,并调度好预取和执行的重叠。如果是小开销大,编译器就将循环展开许多次,以便为后面较远的循环预取数据。
编译器控制的预取相关概念
寄存器预取:把数据取到寄存器中
Cache预取:只将数据取到Cache中
故障性预取:在预取时,若出现虚地址故障或违反保护权限,就会引发异常。
非故障性预取:在遇到虚地址故障或违反保护权限时,它会放弃预取,转变为空操作。
非阻塞预取:Cache在等待预取数据返回的同时,还能继续提供指令和数据。
编译器控制的预取的使用前提
发出预取指令需要花费一条指令的开销,因此,要注意保证这种开销不超过预取带来的收益。通过把重点放在那些可能会导致失效的访问上,是程序避免不必要的预取,从而较大程度地改善平均访存时间。
与硬件预取的比较
硬件预取通常不考虑指令的特点,而是机械地在指令失效发生时去两个块放入Cache或者Buffer:被请求的块和顺序的下一指令块。这种由硬件控制的预取不能充分利用指令的特点进而采取最有的调度指令块策略,而编译器控制的预取则弥补了这一点。
实例
语句:
For(i=0;i<3;i++)
For(j=0;j<100;j++)
a[i][j] = b[j][0] * b[j+1][0];
假设:(1)直接映像Cache的容量为8KB、块大小为16B,它采用写回法并且按写分配
(2)a、b分别为3*100和101*3的双精度浮点数组,每个元素都是8个字节。当程序开始执行时,这些数据都不在Cache内。
分析
定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析
:
可能造成Cache失效的访问
没有预取功能时,对数组a中的元素的写操作是按照他们在主存中的存放顺序进行,因为对a的访问受益于空间局部性。由于每一块含两个元素,当j为偶数时是第一次访问一个块,为奇数时是第二次,因此,当j为偶数时失效,奇数时命中。故对a的访问失效次数为3*100/2=150次。
数组b是每次都访问的第j行的第0列元素,故没有空间局部性,但显然,它存在时间局部性,因为i的每一次循环都访问相同的b数组元素。当i为0时,j从0~99,因此对数组b的访问将引起101次失效。
所以,在没有预取功能时,上述语句总共将引起150+101 = 251次数据Cache失效。
考虑利用编译器控制预取的思路改进
根据上述分析,将循环进行分解,使得在第一次循环中不仅预取a,而且预取b,而在第二次循环中只预取a,因为此时所需使用的b已在第一轮循环中预取过了。假设由失效开销的影响而必须至少提前7次循环进行。
语句修改为:
For(j=0;j<100;j++)
{
Prefetch(b[j+7][0]);
Prefetch(a[0][j+7]);
a[0][j] = b[j][0]*b[j+1][0];
}
For(i=1;i<3;i++)
{
For(j=0;j<100;j++)
{
Prefetch(a[i][j+7]);
A[i][j] = b[j][0] * b[j+1][0];
}
}
修改后失效分析
程序预取了一下数据:从a[i][7]~a[i][99],从b[7][0]~b[100][0]。失效情况为:第一个循环中访问a[0][0]~a[0][6]失效次;访问b[0][0]~b[6][0]失效7次;第二个循环中,访问a[i][0]~a[i][6]失效次,故总共失效次数减少为4+7+8=19次,便面了251-19=232次失效,同时,付出了执行400条预取指令的代价。
计算改进后,节约的时间
进一步假设
忽略指令Cache失效,并假设数据Cache无冲突失效和容量失效。
预取可以被重叠或与Cache失效重叠执行,从而能以最大的存储带宽传送数据。
不考虑Cache失效时,修改前的循环每7个时钟周期循环一次。修改后的程序中,第一个预取循环每9个时钟周期循环一次,而第二个预取循环每8个时钟周期循环一次(包括外层for循环的开销)
一次失效需50个时钟周期
修改前双重循环一共执行了3*100=300次循环。每次用7个时钟周期,总时间就是300*7=2100个时钟周期。失效开销为251*50=12550个时钟周期。故,总时间为14650个时钟周期。
修改后,第一个预取循环共执行了100次,每次循环用7+2个时钟周期,总的执行时间为900个时钟周期再加上Cache的失效开销。失效开销一共是(4+7)*50=550个时钟周期,故总时间为1450个时钟周期。第二个循环工资性了200次,每次用8个时钟周期,共1600个时钟周期,再加上8*50=400个时钟周期的失效开销,总时间为2000个时钟周期。额外执行了400条预取指令,但假设预取指令与其他部分的执行完全重合。所以,改进后的总时间为1450+2000=3450个时钟周期。比改进前快了14650/3450=4.2倍。
1