第四章存储子系统cache

高速缓冲存储器,程序访问的局部性原理：由于编程时指令地址的分布基本上连续，对循环程序段的执行往往要重复若干遍；在一个较短的时间间隔内，对存储器的访问大部分将集中在一个局部区域中，而对此地址范围之外的地址很少访问。这种现象称之为局部性原理。,(3)Cache的命中率,CPU欲访问的信息在Cache中的比率,命中率与Cache的容量与块长有关,一般每块可取48个字,块长取一个存取周期内从主存调出的信息长度,在一个程序执行期间，设Nc表示cache完成存取的总次数，Nm表示主存完成存取的总次数，h定义为命中率，则有h=Nc/（Nc+Nm),(4)Cache主存系统的效率,访问效率e与命中率有关若tc表示命中时的cache访问时间，tm表示未命中时的主存访问时间，1-h表示未命中率，则cache/主存系统的平均访问时间ta为：ta=h*tc+（1-h)tm,例：CPU执行一段程序时，cache完成存取的次数为1900次，主存完成存取的次数为100次，已知cache存取周期为50ns，主存存取周期为250ns，求cache/主存系统的效率和平均访问时间。,二、Cache主存的地址映射与地址变换,地址映象：把主存地址空间映象到Cache地址空间，具体地说就是把存放在主存中的程序按照某种规则装入Cache，并建立主存地址与Cache地址之间的对应关系。地址变换：把程序装入Cache之后，在实际运行过程中，把主存地址如何变换成Cache地址。,1.全相联映射,主存中的任一块可以映射到缓存中的任一块设Cache块容量为Cb，主存块容量为Mb，则主存与Cache之间存在Cb*Mb中映象关系,引入目录表来存放映象关系，则目录表容量为Cb，字长为Cache地址中的块号长度与主存地址中的块号长度之和再加上一个有效位。,块号B|块内地址W,主存地址,块号b|块内地址W,Bb1,Bb1,Bb1,主存块号Cache块号有效位,相联比较,命中,有效位为1：表示目录表中由主存块号B与Cache块号b之间的映像关系是有效的，也表示在Cache的第b块中存放的数据是主存第B块数据的正确副本。有效位为0：表示目录表中由主存块号B与Cache块号b之间的映像关系是无效的，或者说他们之间没有任何关系，Cache的第b块中存放的数据也不是主存第B块数据的正确副本。,特点：块的冲突小，Cache利用率高，但硬件代价高，影响Cache的速度,2.直接映射主存中一块只能映像到cache的一个特定块中,设主存块号为B，Cache块号为b，则映象关系表示为b=BmodCbCb是Cache的块容量，Mb是主存的块容量，Me是主存的区容量把主存按Cache的大小分区，每个分区的块数与Cache总块数正好相等。直接映象只能把主存各区中相对块号相同的那些块映像到Cache中同一块号的那个特定块中。,区号E|块号B|块内地址W,主存地址,块号b|块内地址W,E1,区号E(按地址访问)有效位,比较,相等,区号存储器,相等,不等,比较结果相等，有效位为1，命中。比较结果相等，有效位为0，Cache处该块作废。比较结果不等，有效位为1，Cache处该块有用。比较结果不等，有效位为0，Cache处该块为空。,特点：冲突率高，Cache命中率低。,3.组相联映射,把主存和Cache按同样大小划分成块，另外还把主存和Cache按同样大小划分成组，每一组由相同的块数组成。主存组与Cache组采用直接映像，两个对应组内部采用全相联方式。,主存储体,Cache存储体,区0,区Me-1,块0,块Gb-1,块Gb,块2Gb-1,块Cb-Gb,块Cb-1,块0,块Gb-1,块Gb,块2Gb-1,块Cb-Gb,块Cb-1,组0,组1,组Cg-1,组0,组0,组Cg-1,区号E|组号G|组内块号B|块内地址W,主存地址,组号g|组内块号b|块内地址w,Gb个块,区号E,组内块号B组内块号b,相联比较,相等,块表存储器,相等,不等,例：设主存容量1MB，Cache容量16KB，块的大小为512B，采用直接地址映像方式：1）写出Cache的地址格式2）写出主存的地址格式3）区号表的容量为多大？（不考虑有效位）4）主存地址为CDE8FH的单元在Cache的什么位置？5）若将本例改为全相联地址映像方式，又该如何？,三、替换算法,2.先进先出（FIFO）算法按调入Cache的先后决定淘汰的顺序，即在需要更新时总是最先淘汰最先调入Cache的页面内容。,1.随机替换随机替换策略实际上是不要什么算法，简单地根据一个随机数，选取Cache中的一块替换掉。,3.近期最少使用（LRU）算法选择近期最少访问的页面作为被替换的页面,4.最优化（OPT）算法以将来使用最少作为替换目标。是一种理想的算法，实现不了，只能作为衡量其它算法优劣的标准。,LRU算法计数器的使用及管理规则是：1）被装入或被替换的块，其对应计数器清为0，同组中其他所有块所属计数器加1；2）命中的块，其对应的计数器清为0，同组中其他所有计数器中，凡是计数器值小于命中块所属计数器原来值的都加1，其他计数器不变；3）需要替换时，在同组的所有计数器中选择计数值最大的计数器，它所对应的块就是要被替换的块。,例：一个程序共有5个页面，分别为P1-P5,程序执行过程中的页地址流（即程序执行中依次用到的页面）如下：P1P2P1P5P4P1P3P4P2P4，假设分配给这个程序的Cache共3个页面，则使用FIFO,LRU时命中率为多少？,提高存储系统性能的其它措施,一、双端口存储器双端口存储器由于同一个存储器具有两组相互独立的读写控制电路而得名。由于进行并行的独立操作，因而是一种高速工作的存储器。,二、并行存储器1.单体多字并行主存系统多个并行存储器共用一套地址寄存器，按同一地址并行地访问各自的对应单元。,2.多体交叉存取方式并行主存系统多个存储体具有自己的地址寄存器、数据线、时序，可以独立编制地并行工作。,(1)高位交叉,顺序编址,各个体并行工作,体号,(1)高位交叉,(2)低位交叉,各个体轮流编址,体号,(2)低位交叉各个体轮流编址,各体地址分配满足A=nj+kA：各分体内的地址；n:存储体的个数j:正整数k:存储体编号通常在一个存储器周期内，n个存储体必须分时启动，则各个存储体的启动间隔为t=T/n（n为交叉存取度）,设存储器容量为32字，字长64位，模块数为4，请分别画出顺序方式和交叉方式组成的存储器结构和编址示意图。,低位交叉的特点,在不改变存取周期的前提下，增加存储器的带宽,启动存储体0,启动存储体1,启动存储体2,启动存储体3,例:设存储器容量为32字，字长64位，模块数m=4，分别用顺序方式和交叉方式进行组织。存储周期T=200ns，数据总线宽度为64位，总线传送周期=50ns。若连续读出4个字，问顺序存储器和交叉存储器的带宽各是多少?,解：顺序存储器和交叉存储器连续读出m=4个字的信息总量都是：q=64b4=256bit顺序存储器和交叉存储器连续读出4个字所需的时间分别是：t2=mT=4200ns=800ns=810-7st1=T+(m-1)50ns=200ns+150ns=350ns=3.510-7s顺序存储器和交叉存储器的带宽分别是：W2=q/t2=256b(810-7)s40MB/SW1=q/t1=256b(3.510-7)s91.4MB/S,三、相联存储器一般存储器是按地址访问存储器的，而相联存储器是按内容寻址的存储器。相联存储器可以选择记录的一个字段作为地址，该字段称为关键字（键）。Key,Data基本原理：把存储单元所存内容的某一部分作为检索项去检索该存储器，并将存