绑定完请刷新页面
取消
刷新

分享好友

×
取消 复制
存储器系统
2020-05-19 17:33:42

更新:修正了一些错别字,其次,为了方便理解,增加了冲突不命中的举例。


首先看一下计算矩阵的乘法:

考虑一对 n\times n 的矩阵相乘的问题:C=AB。例如,如果n=2,那么

\left[  \begin{matrix}    c_{11} & c_{12} \\    c_{21} & c_{22}   \end{matrix}  \right]=\left[  \begin{matrix}    a_{11} & a_{12} \\    a_{21} & a_{22}   \end{matrix}  \right]\left[  \begin{matrix}    b_{11} & b_{12} \\    b_{21} & b_{22}   \end{matrix}  \right]

其中

c_{11}=a_{11}b_{11}+a_{12}b_{21} \\ c_{12}=a_{11}b_{12}+a_{12}b_{22} \\ c_{21}=a_{21}b_{11}+a_{22}b_{21} \\ c_{22}=a_{21}b_{12}+a_{22}b_{22}

一般代码如下:

/* ijk */
for (i=0; i<n; i++)  {
  for (j=0; j<n; j++) {
    sum = 0.0;
    for (k=0; k<n; k++) 
      sum += a[i][k] * b[k][j];
    c[i][j] = sum;
  }
}

调整不同的循环顺序( A_{3}^{3} ),那么有以下共6种循环形式:

/* ijk */                                  /* jik */
for (i=0; i<n; i++)  {                     for (j=0; j<n; j++)  {
  for (j=0; j<n; j++) {                      for (i=0; i<n; i++) {
    sum = 0.0;                                 sum = 0.0;
    for (k=0; k<n; k++)                        for (k=0; k<n; k++)
      sum += a[i][k] * b[k][j];                  sum += a[i][k] * b[k][j];
    c[i][j] = sum;                             c[i][j] = sum;
  }                                          }
}                                          }

/* jki */                                  /* kji */
for (j=0; j<n; j++) {                      for (k=0; k<n; k++) {
  for (k=0; k<n; k++) {                      for (j=0; j<n; j++) {
    r = b[k][j];                               r = b[k][j];
    for (i=0; i<n; i++)                        for (i=0; i<n; i++)
      c[i][j] += a[i][k] * r;                    c[i][j] += a[i][k] * r;
  }                                          } 
}                                          }

/* kij */                                  /* ikj */
for (k=0; k<n; k++) {                      for (i=0; i<n; i++) {
  for (i=0; i<n; i++) {                      for (k=0; k<n; k++) {
    r = a[i][k];                               r = a[i][k];
    for (j=0; j<n; j++)                        for (j=0; j<n; j++)
      c[i][j] += r * b[k][j];                    c[i][j] += r * b[k][j];   
  }                                          }
}                                          }

那么以上6个算法,哪个性能优呢?哪个性能差呢?这就是本文要探讨的内容[1]。是什么影响了程序的性能,其原理是什么,如何改进程序以达到优性能。下面将以下面小节进行讲述:

  • 局部性原理
  • 存储器层次结构以及存储技术
  • 存储器山

局部性原理

一个编写良好的计算机程序常常具有良好的局部性。也就是,它们倾向于用临近于其他近引用过的数据项的数据项,或者近引用过的数据项本身。这种倾向性,被称为局部性原理,是一个持久的概念,对硬件和软件系统的设计和性能都有极大的影响。

局部性通常有两种不同的形式:时间局部性空间局部性

在一个具有良好局部性的程序中,被引用过一次的内存位置很可能在不远的将来再被多次引用。

红色块为被引用的内存块

在一个具有良好空间局部性的程序中,如果一个内存位置被引用了一次,那么程序很可能在不远的将来引用附近的一个内存位置。

红色块为被引用的内存块以及将要被引用的内存块

我们需要明白局部性的重要性。一般来说,有良好局部性的程序比局部性差的程序运行得更快。现代计算机系统的各个层次,从硬件到操作系统、再到应用程序,它们的设计都利用了局部性。在硬件层,局部性原理允许设计者通过引入称为高速缓存存储器的小而快速的存储器来保存近被引用的指令和数据项,从而提高对主存的访问速度。而操作系统级别,局部性原理允许系统使用主存作为虚拟地址空间近被引用块的高速缓存。类似的,操作系统用主存来缓存磁盘文件系统中近被使用的磁盘块。局部性原来在应用程序的设计中也扮演着重要的角色。

让我们举一个例子。

sum = 0;
for (i = 0; i < n; i++)
	sum += a[i];
return sum;

一般程序分为指令以及变量。我们首先看一下变量:

  • sum:多次调用同一个变量,时间局部性。
  • a[n]:步长为1,读取数组内容,引用相邻的内存块,空间局部性。

指令:

  • 循环体:多次调用相同的指令,时间局部性。
  • 顺序指令:调用相邻的指令,空间局部性。

存储器层次结构以及存储技术

众所周知,存储器有许多类型,我们常说的主存或者内存,磁盘,SSD,闪存等等。不同存储技术的访问时间差异很大。速度较快的存储技术每字节的成本要比速度较慢的存储技术高,而且容量较小。CPU和主存之间的速度差距在增大。

从上一章节我们也清楚了一个重要的原则,一个编写良好的程序倾向于展示出良好的局部性。

硬件和软件的这些基本属性互相补充得很完美。它们这种相互补充的性质使人想到一种组织存储器系统的方法,称为存储器层次结构,所有现代计算机系统中都使用了这种方法。下图展示了一个典型的存储层次结构。一般而言,从高层往底层走,存储设备变得更慢、更便宜和更大。在高层(L0),是少量快速的CPU寄存器,CPU可以在一个时钟周期内访问它们。接下来是一个或多个小型到中型的基于SRAM的高速缓存存储器,可以在几个CPU时钟周期内访问它们。然后是一个大的基于DRAM的主存,可以在几十到几百个时钟周期内访问它们。接下来是慢速但是容量很大的本地磁盘。后,有些系统甚至包含了一层附加的远程服务器上的磁盘,要通过网络来访问它们。

存储器层次结构中的缓存

一般而言,高速缓存是一个小而快速的存储设备,它作为存储在更大、也更慢的设备中的数据对象的缓冲区域。使用高速缓存的过程称为缓存。

存储器层次结构的中心思想是,对于每个k,位于k层的更快更小的存储设备作为位于k+1层的更大更慢的存储设备的缓存。换句话说,层次结构中的每一层都缓存来自较低一层的数据对象。例如,主存作为本地磁盘上数据的缓存,以此类推,直到小的缓存--CPU寄存器组。

上图展示了存储层次结构中缓存的一般性概念。第k+1层的存储器被划分成连续的数据对象组块,称为块。每个块都有一个的地址或名字,使之区别于其他的块。块可以是固定大小的(通常都是如此),也可以是可变大小的。

这里有几个概念要清楚:

缓存命中,当程序需要第k+1层的某个数据对象d时,它首先在当前存储在第k层的一个块中查找d。如果d刚好缓存在第k层中,那么就是我们所说的缓存命中。

缓存不命中,和缓存命中相反,在第k层中没有缓存数据对象d,那么就是我们所说的缓存不命中。当发生这种情况时,第k层的缓存从第k+1层取出包含d的那个块,如果第k层的缓存已经满了,可能就会覆盖现存的一个块。 覆盖一个现存的块的过程称为替换或驱逐这个块。被驱逐的这个块有时也称为牺牲块。决定该替换哪个块是由缓存的替换策略来控制的。

缓存不命中的种类,区分不同种类的缓存不命中有时候是很有帮助的。如果第k层的缓存是空的,那么对任何数据对象的访问都不会命中。一个空的缓存有时被称为冷缓存,此类不命中称为称为强制不命中冷不命中。冷不命中很重要,因为它们通常是短暂的事件,不会在反复访问存储器使得缓存暖身之后的状态中出现。 只要发生了不命中,第k层的缓存就必须执行某个放置策略,确定把它从第k+1层中取出的块放在哪里。灵活的替换策略是允许来自k+1层的任何块放在第k层的任何块中。对于存储器层次结构中高层的缓存(靠近CPU),它们是用硬件来实现的,而且速度是优的,这个策略实现起来通常很昂贵,因为随机地放置块,定位起来代价很高。 因此,硬件缓存通常使用更严格的放置策略,这个策略将第k+1层的某个块限制放置在第k层块的一个小的子集中(有时只是一个块)。 这种限制性的放置策略会引起一种不命中,称为冲突不命中,在这种情况中,缓存足够大,能够保存被引用的数据对象,但是因为这些对象会映射到同一个缓存块,缓存会一直不命中。 程序通常是按照一系列阶段来运行的,每个阶段访问缓存块的某个相对稳定不变的集合。这个块的集合称为这个阶段的工作集。当工作集的大小超过缓存的大小时,缓存会经历容量不命中。换句话说就是,缓存太小了,不能处理这个工作集。

冲突不命中在真实的程序中很常见,会导致令人困惑的性能问题。当程序访问大小为2的幂的数组时,直接映射高速缓存中会发生冲突不命中,例如,以下这个例子:

float dotprod(float x[8], float y[8])
{
	float sum = 0.0;
	int i = ;

	for(i = ; i < 8; i++)
		sum += x[i]*y[i];
	return sum;
}

对于x,y来说,这个函数具有良好的局部性,因此我们期望它的命中率会比较高。不幸的是,并不总是如此。假设浮点数是4个字节,x被加载到从地址0开始的32字节连续内存中,而y紧跟着x之后,从地址32开始。为了简便,假设一个块是16个字节,高速缓存由两个组组成,高速缓存大小为32字节。根据以上假设我们假设每个x和y数组项会映射到相应的高速缓存组:

在循环时,循环的次迭代引用x[0],缓存不命中会导致包含x[0]~x[3]的块被加载到组0。接下来是y[0],有一次缓存不命中,导致包含y[0]~y[3]的块被复制到组0,覆盖前一次引用复制进来的x的值,在下一次的迭代中,对x[1]的引用不命中,导致x[0]~x[3]的块被加载回组0,覆盖掉y的值,这种现象即冲突不命中。那么如何解决此类问题呢?我们可以使用B个字节来填充x数组的结尾,比如我们定义x为float x[12]。那么我们将会看到以下的地址排布:

至此,x[0]~x[3]和y[0]~y[3]不会被加载到同一个高速缓存组。

缓存管理,正如我们提到过的,存储器层次结构的本质是,每一层存储设备都是较低一层的缓存。在每一层上,某种形式的逻辑必须管理缓存。这里,我们的意思是指某个东西要将缓存划分成块,在不同的层之间传送块,判定是命中还是不命中,并处理他们。管理缓存的逻辑可以是硬件、软件,或者两者的结合。

概括来讲,基于缓存的存储器层次结构性质有效,是因为较慢的存储设备比较快的存储设备更便宜,还因为程序倾向于展示局部性:

  • 利用时间局部性:由于时间局部性,同一数据对象可能会被多次使用。一旦一个数据对象在次不命中时被复制到缓存中,我们就会期望后面对该目标有一系列的访问命中。因为缓存比层的存储设备更快,对后面的命中的服务会比开始的不命中快很多。
  • 利用空间局部性:块通常包含有多个数据对象。由于空间局部性,我们会期望后面对该块中其他对象的访问能够补偿不命中后复制该块的花费。

存储技术

我们知道了存储有层次结构,那么这些层次结构是基于什么原理划分的呢?

随机访问存储器(Random-Access Memory,RAM)

静态RAM
SRAM(Static Random-Access Memory,SRAM)将每个位存储在一个双稳态的存储器单元里,它可以无限期地保持在两个不同的电压配置或状态之一。只要有电,它就会永远的保持它的值。即使有干扰,当干扰消除时,电路就会恢复到稳定值。
我们常说的CPU的高速缓存就是由SRAM组成的。

动态RAM
DRAM(dynamic random access memory,DRAM)将每个位存储为对一个电容的充电。这个电容相比来说非常小,容易受到干扰。与SRAM不同的是,DRAM对干扰非常敏感,当电容的电压被扰乱之后,它就永远不会恢复了。幸运的是,CPU的运行的时钟周期相比起来更小,所以相对来说够计算机稳定地使用了。
我们常说的内存或者主存就是由DRAM组成的。

非易失性存储器

非易失性存储器(non-volatile memory,NVM),相对SRAM和DRAM来说的,与他们不同的是,其即使在断电后,仍然保存着它们的信息。由于历史原因,虽然ROM中有的类型既可以读也可以写,但是它们整体上都被称为只读存储器(Read-Only Memory)。

ROM是以它们能够重编程(写)的次数和它们进行重编程所用的机制来区分的。

PROM(Programmable ROM),可编程ROM,只能被编程一次。PROM的每个存储器单元有一种熔丝,只能用高电流熔断一次。

EPROM(Erasable PROM),可擦写可编程ROM,有一个透明的石英窗口,允许光到达存储单元进行擦除。而写则有一种特殊的设备来进行,能够被擦除和重编程的次数可以达到1000次。而EEPROM(Electrically EPROM),电子可擦除PROM,相比于EPROM能够编程的次数可以达到 100000次。

闪存(flash memory)是一种非易失性存储器,基于EEPROM,它已经成为了一种重要的存储技术。而目前大家熟知的固态硬盘正式基于闪存的技术而诞生的。

存储在ROM设备中的程序通常被称为固件。比如我们的手机固件、再比如我们的BIOS(Basic Input Output System)。当一个计算机通电以后,它会运行存储在ROM设备中的固件。

磁盘存储

磁盘是广为应用的保存大量数据的存储设备,存储数据的数量级可以达到几百到几千兆字节,而基于RAM的存储器只能有几百或几千兆字节。不过,从磁盘上读信息的时间为毫秒级,比从DRAM读慢了10万倍,比从SRAM读慢了100万倍。

磁盘构造,磁盘是由盘片构成的。每个盘片上都有两面或者称为表面,表面覆盖着磁性记录材料。盘片中有一个可以旋转的主轴,它使得盘片以固定的旋转速率旋转,通常是5400~15000转每分钟。磁盘通常包含一个或多个这也的盘片,并封装在一个密封的容器内。

如上图所示,这是一个典型的磁盘表面的结构。每个表面是由一组称为磁道的同心圆组成的。每个磁道被划分为一组扇区。每个扇区包含相等数量的数据位(通常是512字节,现在已经存在4K大小的扇区),这些数据编码在扇区上的磁性材料中。扇区之间由一些间隙分隔开,这些间隙中不存储数据位。间隙存储用来标识扇区的格式化位。

磁盘是由一个或多个叠放在一起的盘片组成的,它们被封装在一个密封的包装里,如上图所示。整个装置通常被称为磁盘驱动器,我们通常称为磁盘。有时,我们会称磁盘为旋转磁盘,以此来区别基于闪存的固态硬盘。

磁盘知道商通常用“柱面”来描述多个盘片驱动器的构造,这里,柱面是所有盘片表面上到主轴中心的距离相等的磁道的集合。例如,如果一个驱动器有三个盘片和六个面,每个表面上的磁道的编号都是一致的,那么柱面k就是6个磁道k的集合。

磁盘容量,一个磁盘上可以记录的大位数称为它的大容量。磁盘容量是由以下技术因素决定的:

  • 记录密度:磁道一英寸的段中可以放入的位数。
  • 磁道密度:从盘片中心出发半径上一英寸的段内可以有的磁道数。
  • 面密度:记录密度与磁道密度的乘积。

磁盘操作,磁盘用读/写头来读写存储在磁性表面的位,而读写头连接到一个传动臂一端,如下图所示。

通过沿着半径轴前后移动这个传动臂,驱动器可以将读/写头定位在盘面上的任何磁道上。这样的机械运动称为寻道(seek)。一旦读/写头定位到期望的磁道上,那么当磁道上的每个位通过它的下面时,读写头可以感知到这个位的值(读该位),也可以修改这个位的值(写该位)。有多个盘片的磁盘针对每个盘面都有一个独立的读/写头,如下如所示。

读/写头垂直排列,一致行动。在任何时刻,所有的读/写头都位于同一柱面上。

在传动臂末端的读/写头在磁盘表面高度大约0.1微米处的一层薄薄的空气垫上飞翔,速度大约时80km/h。这样小的间隙里,盘面上一粒微小的灰尘都像一块巨石。如果读/写头碰到了这样的一块巨石,读/写头会停下来,撞到盘面--所谓的读/写头冲撞。因此所有磁盘都是密封包装的。

磁盘以扇区大小的块来读写数据,对扇区的访问时间有三个主要的部分:寻道时间、旋转时间和传送时间。

  • 寻道时间:为了读取某个目标扇区的内容,传动臂首先将读/写头定位到包含目标扇区的磁道上。移动传动臂所需的时间称为寻道时间。寻道时间 T_{seek} 依赖于读/写头以前的位置和传动臂在盘面上移动的速度。现代驱动器中平均寻道时间 T_{avgseek} 是通过对几千次对随机扇区的寻道求平均值来测量的,通常为3~9ms。一次的寻道时间 T_{maxseek} 可以高为20ms。
  • 旋转时间:一旦读/写头定位到了期望的磁道,驱动器等待目标扇区的个旋转到读/写头下。这个步骤的性能依赖于当读/写头到达目标扇区时盘面的位置以及磁盘的旋转速度。在坏的情况下,读/写头刚刚错过了目标扇区,必须等待磁盘转一整圈。因此大旋转延迟(以秒为单位)是: T_{max rotation} = \frac{1}{RAM}\times\frac{60s}{1 min} ,平均旋转时间 T_{avg rotation}T_{max rotation} 的一半。
  • 传送时间:当目标扇区的个位位于读/写头下时,驱动器就可以开始读或者写该扇区的内容了。一个扇区的传送时间依赖于旋转速度和每条磁道的扇区数目。因此,我们可以粗略的估计一个扇区以秒位单位的平均传送时间如下: T_{avg transfer} = \frac{1}{RAM}\times\frac{1}{平均扇区数/磁道}\times\frac{60s}{1 min}

逻辑磁盘块,现代磁盘构造复杂,有多个盘面,这些盘面上有不同的记录区。为了对操作系统隐藏这样的复杂性,现代磁盘将它们的构造呈现为一个简单的视图,一个B个扇区大小的逻辑块的序列,编号为0,1,2,3,……,B-1。磁盘封装中有一个小的硬件/固件设备,称为磁盘控制器,维护着逻辑块号和实际(物理)磁盘扇区之间的映射关系。

当操作系统想要执行一个I/O操作时,例如读一个磁盘扇区的数据到主存,操作系统会发送一个命令到磁盘控制器,让它读某个逻辑块号。控制器上的固件执行一个快速表查找,将一个逻辑块号翻译成一个(盘面,磁道,扇区)的三元组,这个三元组地标识了对应的物理扇区。控制器上的硬件会解释这个三元组,将读/写头移动到适当的柱面,等待扇区移动到读/写头下,将读/写头感知到的位放到控制器上的一个小缓冲区中,然后将它们复制到主存中。

固态硬盘

固态硬盘(Solid State Disk,SSD)是一种基于闪存的存储技术,在某种情况下是传统旋转磁盘的极有吸引力的替代产品。SSD封装插到I/O总线上标准硬盘插槽中,行为就和其他硬盘一样,处理来自CPU的读写逻辑磁盘块的请求。一个SSD封装由一个或多个闪存芯片和闪存翻译层组成,闪存芯片替代传统旋转磁盘中的机械驱动器,而闪存翻译层是一个硬件/固件设备,扮演与磁盘控制器相同的角色,将对逻辑块的请求翻译成对底层物理设备的访问。

SSD读要比写快得多,随机读和写的性能差别是由底层闪存基本属性决定的。如上图所示,一个闪存由B个块的序列组成,每个块由P页组成。通常,页的大小是512字节~4KB,块是由32~128页组成的,块的大小为16KB~512KB。数据是以页为单位读写的。只有在一页所属的块整个被擦除之后,才能写这一页。不过,一旦一个块被擦除了,块中每一个也都可以不需要再进行擦除就写一次。在大约进行100000次重复写之后,块就会磨损坏。一旦一个块磨损之后,就不能再使用了。以下是一般SSD不同类型的读写速度:

Sequential read tput	550 MB/s	Sequential write tput	470 MB/s
Random read tput	365 MB/s	Random write tput	303 MB/s
Avg seq read time	50 us		Avg seq write time	60 us

随机写很慢,有两个原因。首先,擦除块需要相对较长的时间,1ms级的,比访问页所需时间要高一个数量级。其次如果写操作试图修改一个包含已经有数据的页p,那么这个块中所有所有带有用数据的页都必须被复制到一个新块,然后才能进行对页p的写。制造商已经在闪存翻译层中实现了复杂的逻辑,试图抵消擦写块的高昂代价,小化内部写的次数,但是随机写的性能不太可能和读一样好。

比起旋转磁盘,SSD有很多优点。它们由半导体存储构成,没有移动的部件,因而随机访问时间比旋转磁盘要快,能耗更低,同时也更结实。不过也有一些缺点。首先因为反复写之后,闪存块会磨损,所以SSD也容易磨损。闪存翻译层中的平均磨损逻辑视图通过将擦除平均分布在所有的块上来大话每个块的寿命。实际上,平均磨损逻辑处理得非常好,要很多年SSD才会磨损坏。其次,SSD每字节比旋转磁盘贵大约30倍,因此常用的存储容量比旋转磁盘小100倍。不过,随着SSD变得越来越受欢迎,它的价格下降得非常快,而两者的价格差也在减少。

存储趋势

不同的存储有不同的价格和性能折中。SRAM比DRAM快一点,而DRAM比磁盘快很多。另一方面,快速存储总比慢速存储要贵。

不同的存储以不同的性能变化速率变化着。下图总结了自1985年至2015年不同存储访问时间的变化情况:

正是因为不同的存储的访问时间存在不同的变化,所以层次之间还会继续增加新的存储结构,比如我们的SSD,现在正位于磁盘与主存之间。换句话说,SSD可以作为磁盘和主存之间的存储结构,也可以替代磁盘。

存储器山

了解了存储层次结构,有一个称为“存储器山”的概念,能够更加清晰的说明存储层次结构与局部性对于程序性能的影响。

一个程序从存储系统中读取数据的速率称为读吞吐量,或者有时称为读宽带。如果一个程序在s秒的时间段内读n个字节,那么这段时间内的读吞吐量就等于n/s,通常以兆字节每秒(MB/s)为单位。 如果我们要编写一个程序,它从一个紧密程序循环中发出一系列读请求,那么测量出的读吞吐量能让我们看到对于这个读序列来说的存储器系统的性能。

http://csapp.cs.cmu.edu/public/mountain.tar 可以下载到相关代码,代码为对不同大小的数组进行不同步长的访问。X轴表示不同步长,Y周表示数组大小,Z轴表示不同步长和数组大小情况下的读吞吐量(单位为MB/s)。

这座Core I7的地形地势展示了一个丰富的结构。垂直于大小轴的是四条山脊,分别对应于工作集完全在L1高速缓存、L2高速缓存、L3高速缓存和主存内的时间局部性区域。注意,L1山脊的高点(那里CPU读速率为14GB/s)与主存山脊的低点之间差了一个数量级。 在L2、L3和主存山脊上,随着步长的增加,有一个空间局部性的斜坡,空间局部性下降。注意即使工作集太大,不能全部装进任何一个高速缓存时,主存山脊的高点,也比它的低点高8倍。因此,即使是当程序的时间局部性很差时,空间局部性仍然能补救,并且是非常重要的。 有一条特别有趣的平坦的山脊线,对于步长1垂直于步长轴,此时读吞吐量相对保持不变,为12GB/s,即使工作集超出了L1和L2的大小。这显然是由于Core I7存储器系统中的硬件预取机制,它会自动识别顺序的、步长为1的引用模式,试图在一些块被访问之前,将它们取到高速缓存中。 如果我们从这座山中取出一个片段,保持步长为常数,我们就能很清楚的看到高速缓存的大小和时间局部性对应能的影响了。大小大为32KB的工作集完全能放进L1 d-cache中,因此,读都是由L1来服务的,吞吐量保持在峰值12GB/s处。大小大为256KB的工作集完全能放进统一的L2高速缓存中,对大小大为8M,工作集完全能放进统一的L3高速缓存中。更大的工作集大小主要由主存来服务。

L2和L3高速缓存区域左边的边缘上读吞吐量的下降很有趣,此时工作集大小为256KB和8MB,等于对应的高速缓存大小。为什么会出现这样的下降,还不是完全清楚。要确认的方法就是执行一个详细的高速缓存模拟,但是这些下降很有可能是与其他数据和代码行的冲突造成的。 以相反的方向横切这座山,保持工作集大小不变,我们从中能看到空间局部性对读吞吐量的影响。例如,图展示了工作集大小为4MB时的片段。这个片段是沿着上图中的L3山脊切的,这里,工作集完全能够放入到L3高速缓存中,但是对于L2高速缓存来说太大了。 注意随着步长从1字节增长到8个字,读吞吐量是如何平稳地下降的。在山的这个区域中,L2中的读不命中会导致一个块从L3传送到L2。后面在L2中这个块上会有一定数量的命中,这是取决于步长的。随着步长的增加,L2不命中与命中的比值也增加了。因为服务不命中要比命中更慢,所以读吞吐量也下降了。一旦步长达到了8个字,在这个系统上就等于块的大小64个字节了,每个请求在L2中都会不命中,必须从L3服务。因此,对于至少为8个字的步长来说,读吞吐量是一个常数速率,是由L3传送高速缓存块到L2的速率决定的。

那么了解了以上概念,我们在看一下文章开头提出的问题。关于矩阵乘法的六种循环算法的比较。

在高层次来看,这6个版本是非常相似的。如果加法是可结合的,那么每个版本计算出的结果完全一样。每个版本总共执行 O(n^{3}) 个操作,而加法和乘法的数量相同。A和B的 n^{2 } 个元素中的每一个都要读n次。计算C的 n^{2} 个元素中的每一个都要对n个值求和。不过,如果分析里层循环迭代的行为,我们发现在访问数量和局部性上还是有区别的。为了分析,我们做了如下假设:

  • 每个数组都是一个double类型的 n\times n 的数组,sizeof(double) == 8。
  • 只有一个高速缓存,其块大小为32字节(B=32)。
  • 数组大小n很大,以至于矩阵的一行不能完全装进L1高速缓存中。
  • 编译器将局部变量存储到寄存器中,因此循环内对局部变量的引用不需要任何加载或存储指令。
/* ijk */                                  /* jik */
for (i=0; i<n; i++)  {                     for (j=0; j<n; j++)  {
  for (j=0; j<n; j++) {                      for (i=0; i<n; i++) {
    sum = 0.0;                                 sum = 0.0;
    for (k=0; k<n; k++)                        for (k=0; k<n; k++)
      sum += a[i][k] * b[k][j];                  sum += a[i][k] * b[k][j];
    c[i][j] = sum;                             c[i][j] = sum;
  }                                          }
}                                          }

/* jki */                                  /* kji */
for (j=0; j<n; j++) {                      for (k=0; k<n; k++) {
  for (k=0; k<n; k++) {                      for (j=0; j<n; j++) {
    r = b[k][j];                               r = b[k][j];
    for (i=0; i<n; i++)                        for (i=0; i<n; i++)
      c[i][j] += a[i][k] * r;                    c[i][j] += a[i][k] * r;
  }                                          } 
}                                          }

/* kij */                                  /* ikj */
for (k=0; k<n; k++) {                      for (i=0; i<n; i++) {
  for (i=0; i<n; i++) {                      for (k=0; k<n; k++) {
    r = a[i][k];                               r = a[i][k];
    for (j=0; j<n; j++)                        for (j=0; j<n; j++)
      c[i][j] += r * b[k][j];                    c[i][j] += r * b[k][j];   
  }                                          }
}                                          }

我们可以根据循环体,将以上6种循环划分为3组。

  • ijk & jik AB,循环体为AB数组,其中A数组以步长为1遍历行,而B数组以步长为1遍历列。但由于数组在内存中以行存储,所以按照假设高速缓存为32字节。那么对于A的读取次冷不命中,然后读取32字节数据到高速缓存,也就是4个数据,后面3次都能命中,即未命中率为0.25。而对于B,为列读取,而且按照假设每一行都不能一次性放入高速缓存,所以次冷不命中,读取到相应数据放入高速缓存后,下一次还需要再次从内存中获取数据,即未命中率为1。即整体未命中率为1.25。
  • jki & kji AC,A和C都是以列访问,所以未命中率都为1,即整体未命中率为2。
  • kij & ikj BC,B和C都是以行访问,所以未命中率都为0.25,即整体未命中率为0.5。

由上所述,kij和ikj性能优。以下为随着n增大的性能趋势图:

总结

存储器系统是一个具有不同容量、成本和访问时间的存储设备的层次结构。CPU寄存器保存着常用的数据。靠近CPU的小的、快速的高速缓存存储器作为一部分存储在相对慢速的主存储器中数据和指令的缓冲区域。主存缓存存储在容量较大的、慢速磁盘上的数据,而这些磁盘常常又作为存储在通过网络连接的其他机器的磁盘或磁带上的数据的缓冲区域。

存储器层次结构是可行的,这是因为与下一个更低层次的存储设备相比起来,一个编写良好的程序倾向于更频繁地访问某一个层次上的存储设备。所以,下一层的存储设备可以更慢速一点,也因此可以更大,每个比特位更便宜。整体效果是一个大的存储器池,其成本与层次结构底层便宜的存储设备相当,但是却以接近于层次结构顶部存储设备的高速率向程序提供数据。

想要更清晰的了解数据库的存储,我们需要理解存储器层次结构,因为它对数据库应用系统来说有着巨大的影响。如果我们的程序需要的数据存储在CPU寄存器中的,那么在指令的执行期间,在0个周期内就能访问到它们。如果存储在高速缓存中,需要4~75个周期。如果存储在主存中,需要上百个周期。而如果存储在磁盘上,需要大约几千万个周期。

也就是说,我们的程序总是将数据在存储器层次结构中上上下下移动。我们需要将我们需要的数据存放在层次结构中较高的地方,在哪里CPU能更快的访问到它们。

这个思想围绕着计算机程序的一个称为“局部性”的基本属性。具有良好局部性的程序倾向于一次又一次的访问相同的数据项集合,或是倾向于从存储器层次结构中较高层次处访问数据项,因此运行得更快。

参考

  1. ^本文是基于对《深入理解计算机系统》的存储器系统理解、整理而来的。
分享好友

分享这个小栈给你的朋友们,一起进步吧。

华山论剑
创建时间:2019-02-22 18:53:00
没了烟火气,人生就是一段孤独的旅程·····于是,在ITPUB,我们以武论英雄!
展开
订阅须知

• 所有用户可根据关注领域订阅专区或所有专区

• 付费订阅:虚拟交易,一经交易不退款;若特殊情况,可3日内客服咨询

• 专区发布评论属默认订阅所评论专区(除付费小栈外)

栈主、嘉宾

查看更多
  • 栈栈
    栈主
  • ?
    嘉宾

小栈成员

查看更多
  • u_9a3ed7a37f8e4a
  • daisyplay
  • boss_ch
  • Jack2k
戳我,来吐槽~