CPU访问中的时间空间局部性原理解析

一、定义

在CPU访问寄存器时,无论是存取数据抑或存取指令,都趋于聚集在一片连续的区域中,这就被称为局部性原理。

  • 时间局部性(temporal locality):被引用过一次的存储器位置在未来会被多次引用(通常在循环中)。
  • 空间局部性(spatial locality):如果一个存储器的位置被引用,那么将来他附近的位置也会被引用。

二、示例

在这个例子中,变量在内存中的存储结构如下:

可以看出从a[0]到a[4]的地址位是连续的,而且程序中访问这些变量频率较高,所以对与a来说,其具有良好的空间局部性,但是每个a成员只被访问一次,所以并不具有良好的时间局部性。

但是对于变量sum来说,其由于其是一个标量,也就是说通过其地址只能得到一个值,故其不具有良好的空间局部性,但是由于其访问频率较高,所以有良好的时间局部性。

通过以上结论可以推出,对于向量a来说,如果其访问顺序和存储顺序一致,那么a的变量之间距离太远,那么其空间局部性越差,因为CPU没办法在其附近找到其他变量,所以空间局部性和a的步长有很大的关系,步长越长,空间局部性越差

同理,如果一个变量被访问的频率越高,其时间局部性就越好

取指令的局部性

指令存在存储器中,CPU要读取指令必须取出该指令,所以就可以评价取指令的局部性。

在for循环中,循环体内的指令多次被执行,所以有良好的时间局部性,循环体中的指令是按顺序执行的,有良好的空间局部性(指令在存储器中是顺序存放的)。

小结

评价局部性的简单原则:

1.重复引用同一个变量具有良好的时间局部性。
2.对于步长为k的引用程序,步长越小,空间局部性越小。步长为1的引用具有良好的空间局部性。k越大,空间局部性越差。
3.对于取指令来说、循环有良好的时间和空间局部性。

0

《CPU访问中的时间空间局部性原理解析》有一个想法

发表评论

邮箱地址不会被公开。