优化软件降低失效率

【摘 要】迄今为止,我们所知道的技术（增加块大小,提高相联度,伪相联,硬件预取以及预取指令）都需要改变或者增加硬件,但下面介绍的方法无需对硬件做任何改动就可以降低失效率.

这种方法就是通过对软件的优化来降低失效率.这也许是硬件设计者最喜欢的解决方案.处理器和主存之间越来越大的性能差距促使编译器的设计者们去仔细研究存储层次行为,以期能通过编译时的优化来改进性能.这项研究分为减少指令失效和减少数据失效两个方面.

我们能很容易地重新组织程序而不影响程序的正确性.例如,把一个程序中的几个过程重新排序,就可能会减少冲突失效,从而降低指令失效率.McFarling研究了如何使用记录信息来判断指令组之间可能发生的冲突,并将指令重新排序以减少失效.他发现,这样可将容量为2KB、块大小为4字节的直接映象指令Cache的失效率降低50%；对于容量为8KB的Cache,可将失效率降低75%.他还发现,当能够使某些指令根本就不进入Cache时,可以得到最佳性能.但即使不这么做,优化后的程序在直接映象Cache中的失效率也低于未优化程序在同样大小的8路组相联Cache中的失效率.

【关 键 词】失效率；Cache失效率；存储层次；降低失效率

数据对存储位置的限制比指令对存储位置的限制还要少,因此更便于调整顺序.我们对数据进行变换的目的是改善数据的空间局部性和时间局部性.例如,可以把对数组的运算改为对存放在同一Cache块中的所有数据进行操作,而不是按照程序员原来随意书写的顺序访问数组元素.

1数组合并

这种技术通过提高空间局部性来减少失效次数.有些程序同时用相同的索引来访问若干个数组的同一维.这些访问可能会相互干扰,导致冲突失效.我们可以这样来消除这种危险：将这些相互独立的数组合并成为一个复合数组,使得一个Cache块中能包含全部所需的元素.

2内外循环交换

有些程序中含有嵌套循环,程序没有按照数据在存储器中存储的顺序进行访问.在这种情况下,只要简单地交换循环的嵌套关系就能使程序按数据在存储器中存储的顺序进行访问.和前一个例子一样,这种技术也是通过提高空间局部性来减少失效次数：重新排列访问顺序使得在一个Cache块被替换之前,能最大限度地利用块中的数据.

修改前的程序以50个字的跨距访问存储器,而修改后的程序顺序地访问一个Cache块中的元素,然后再访问下一块中的元素.和前一个例子不同,这种优化技术在不改变执行的指令数的前提下,提高了Cache的性能.

3循环融合

有些程序含有几部分独立的程序段,它们用相同的循环访问同样的数组,对相同的数据作不同的运算.通过将它们融合为单一的一个循环,能使读入Cache的数据在被替换出去之前得到反复的使用.因此,和前面的两种技术不同,这种优化的目标是通过改进时间局部性来减少失效次数.

修改前的程序在两个地方访问数组a和c,一次在第一个循环里,另一次在第二个循环里.两次循环分隔较远,可能重复失效.即在第一个循环中访问某个元素失效之后,虽已将相应块调入Cache,但在第二个循环中再次访问该元素时,还可能产生失效.而在修改后的程序中,第二条语句直接利用了第一条语句访问Cache的结果,无需做Load操作.

4分块

这种优化可能是Cache优化技术中最著名的一种,它也是通过改进时间局部性来减少失效.无论数组是按行优先还是按列优先存储,都不能解决问题,因为在每一次循环中既有按行访问也有按列访问.这种正交的访问意味着前面的变换方法,如内外循环交换,对此均无能为力.

为了保证正在访问的元素能在Cache中命中,把原程序改为只对大小为B×B的子数组进行计算,而不是像原来那样,从x到z的第一个元素开始一直处理到最后一个.

Rem程序修改后

为了保证正在访问的元素在Cache中命中,把原程序改为只对大小为B×B的子数组进行计算,而不是像原来那样,从x和z的第一个元素开始一直处理到最后一个.