并行计算机体系结构第五章.ppt

第五章 并行存储系统和同步机制,并行存储系统和同步机制,计算机逻辑器件速度大幅提高，致使系统与存储机制之间的速度差距日益增大，存储系统已经成为计算机系统的速度瓶颈。 多体并行、多体交叉 宽字访问和顺序交叉访问 存储器层次结构,层次存储系统,层次存储系统,在一般计算机系统中，有两种存储系统： Cache存储系统：由Cache和主存储器构成 主要目的：提高存储器速度,解决主存速度不足,虚拟存储系统：由主存储器和硬盘构成 主要目的：扩大存储器容量,解决主存容量不足,存储系统的容量 要求： 提供尽可能大的地址空间 能够随机访问 方法有两种： 只对系统中存储容量最大的那个存储器进行编址，其他存储器只在内部编址或不编址 Cache存储系统 另外设计一个容量很大的逻辑地址空间，把相关存储器都映射这个地址空间中 虚拟存储系统,存储系统的价格 计算公式： 当S2S1时，CC2 S2与S1不能相差太大,存储系统的速度 表示方法：访问周期、存取周期、存储周期、存取时间等 命中率定义：在M1存储器中访问到的概率 其中：N1是对M1存储器的访问次数 N2是对M2存储器的访问次数 访问周期与命中率的关系： THT1(1H)T2 当命中率H1时，TT1,存储系统的访问效率： 访问效率主要与命中率和两级存储器的速度之比有关 例3.1：假设T2T，在命中率H为0.9和0.99两种情况下，分别计算存储系统的访问效率。 解：,当H0.9时， e11(0.95(10.9)0.72,当H0.99时， e21(0.995(10.99)0.96,提高存储系统速度的两条途径： 一是提高命中率H， 二是两个存储器的速度不要相差太大 其中：第二条有时做不到(如虚拟存储器)，这时，只能依靠提高命中率 例3.2：在虚拟存储系统中，两个存储器的速度相差特别悬殊，例如：T2105 T。如果要使访问效率到达e0.9，问需要有多高的命中率？,解：,0.9H90000(1-H)1 89999.1 H89999 计算得： H0.999998888877777 0.999999,5. 采用预取技术提高命中率 方法：不命中时，把M2存储器中相邻多个单元组成的一个数据块取出来送入M1存储器中。,计算公式： 其中：H是采用预取技术之后的命中率 H是原来的命中率 n为数据块大小与数据重复使用次数的乘积,例3.3：在一个Cache存储系统中，当Cache的块大小为一个字时，命中率H0.8；假设数据的重复利用率为5，T25T1。计算块大小为个字时，Cache存储系统的命中率？并分别计算访问效率。,解：n4520， 采用预取技术之后，命中率提高到：,证明方法一： 采用预取技术之后， 不命中率(1-H)降低倍：,证明方法二： 在原有命中率的计算公式中，把访问次数扩大到n倍。由于采用了预取技术，命中次数为：nN1(n-1)N2,不命中次数仍为N2，因此新的命中率为：,存储系统的层次结构,多个层次的存储器： 第1层：Register Files(寄存器堆) 第2层： Buffers(Lookahead)(先行缓冲栈) 第3层： Cache(高速缓冲存储器) 第4层： Main Memory(主存储器) 第5层： Online Storage(联机存储器) 第6层： Off-line Storage(脱机存储器) 用i表示层数，则有：工作周期TiTi+1， 存储容量：SiSi+1，单位价格：CiCi+1,存储层次的四个问题,1.当把一个块调入高一层(靠近CPU)存储器时，可以放在哪些位置上? (映象规则),2.当所要访问的块在高一层存储器中时，如何找到该块? (查找算法),3. 当发生失效时，应替换哪一块？ (替换算法),4. 当进行写访问时，应进行哪些操作?(写策略),多体并行,多套地址寄存器和控制逻辑 1. 高位交叉访问存储器 主要目的：扩大存储器容量 实现方法：用地址码的高位部分区分存储体号 要求每个模块都有各自独立的控制部件，每个模块均可独立工作。但系统地址的连续空间落在同一存储体内，容易发生访存冲突。并行存取的可能性很小。,交叉访问存储器,高位交叉访问存储器结构框图,例3.4：用4M字4位的存储芯片组成16M32位的主存储器。共用存储芯片： 用最高2位地址经译码后产生的信号，控制各组存储芯片CS。 每组中的32根数据线分别对应直接相连，称为“线或”方式。,低位交叉访问存储器 主要目的：提高存储器访问速度 实现方法：用地址码的低位部分区分存储体号 要求每个模块都有各自独立的控制部件，每个模块均可独立工作。系统地址在一个存储体内部是不连续的，对连续地址的访问分布在不同的存储体中，可避免存储体访问冲突。 理想情况下，即一个模m的多体交叉访问存储器在不发生分体冲突时的频宽是单体存储器频宽的m倍。,低位交叉访问存储器结构框图,地址编码方法： 由8个存储体构成的低位交叉编址方式,n个存储体分时启动 一种采用流水线方式工作的并行存储器 每存储体的启动间隔为：t 其中： Tm为每个存储体的访问周期, n为存储体个数。,访问冲突 共有n个存储体，每个存储周期只能取到k个有效字,其余n-k个存储体有冲突。 假设p(k)是k的概率密度函数，即p(1)是k1的概率，p(2)是k2的概率，,p(n)是kn的概率。k的平均值为： N是每个存储周期能够访问到的平均有效字的个数。 通常把 N称为并行存储器的加速比。,定义转移概率为g，即读出的是转移指令，且转移成功的概率。这时有： p(1)g p(2)(1-p(1)g(1-g)g p(3)(1-p(1)-p(2)g(1-g)2g p(k)(1-g)k-1g (k1,2,n1) p(n)(1-g)n-1,则：1g2(1-g)g3(1-g)2g (n-1)(1-g)n-2gn(1-g)n-1,若g=0，n个存储体的加速倍数达到最大值n。 若g=1, n个存储体的加速倍数只有1，与单个存储体完全一样。,无冲突访问存储器,1. 一维数组(向量)的无冲突访问存储器 按连续地址访问，没有冲突， 位移量为2的变址访问，速度降低一倍，,具体方法： 存储体的个数取质数。 原因：变址位移量必然与存储体个数互质 设地址间距为d=1,m体交叉存储器的工作体数为m=m/(m,d)，其中(m,d)为m和d的最大公约数。当m=T/时，必将引起流水线断流，所以m取为质数。,2. 二维数组的无冲突访问存储器 要求：一个nn的二维数组，按行、列、对角线和反对角线访问，并且在不同的变址位移量情况下，都能实现无冲突访问。 顺序存储：按行、对角线访问没有冲突，但按列访问每次冲突,错位存储： 按行、按列访问无冲突， 但按对角线访问有冲突,nn二维数组无冲突访问存储方案 ( P Budnik 和 D J Kuck提出 ) ： 并行存储体的个数mn，并且取质数，同时还要在行、列方向上错开一定的距离存储数组元素。 设同一列相邻元素在并行存储器中错开d1个存储体存放，同一行相邻元素在并行存储器中错开d2个存储体存放。当m22p1（p为任意自然数）时，能够同时实现按行、按列、按对角线和按反对角线无冲突访问的充要条件是：d12P，d21。,例如：44的二维数组，取并行存储体的个数m5，由关系式m22P1，解得到p1，计算得到： d1212 d21,37,nn数组中的任意一个元素aij在无冲突并行存储器中的体号地址和体内地址的计算公式： 体号地址：(2P ijk) MOD m 体内地址：i 其中：0in1， 0jn1， k是数组的第一个元素a00所在体号地址，通常k=0 ， m是并行存储体的个数，要求mn且为质数， p是满足m22P1关系的任意自然数。 主要缺点：浪费存储单元 对于nn数组,有1/(n+1)的存储单元浪费 主要优点：实现简单 行元素顺序存储，列元素按地址取模顺序存储,3. 二维数组的无冲突访问存储器(之二) 规则：对于任意一个nn的数组，如果能够找到满足n22P关系的任意自然数p，则这个二维数组就能够使用n个并行存储体实现按行、列、对角线和反对角线的无冲突访问。 44数组用4个存储体的无访问冲突存储方案,实现方法： 假设aij是44数组中的任意一个元素，下标i和j都可以用两位二进制表示。假设i和j的高位和低位分别为iH、iL、jH和jL，则aij在无冲突并行存储器中的体号地址和体内地址如下： 体号地址：2(iL jH)(iH iL jL) 体内地址：j 其中：0i3，0j3 主要优点：没有浪费的存储单元 主要缺点：在执行并行读和写操作时需要借助比较复杂的对准网络。,Cache主存存储系统,存储空间分割与地址计算,映象规则,全相联映象 全相联：主存中的任一块可以被放置到 Cache中的任意一个位置。 对比： 阅览室位置 随便坐 特点： 空间利用率最高，冲突概率最低， 实现最复杂。,Cache和主存分块,2. 直接映象, 直接映象：主存中的每一块只能被放置到 Cache中唯一的一个位置。 对比：阅览室位置 只有一个位置可以坐 特点：空间利用率最低，冲突概率最高，实现最简单。 对于主存的第i 块，若它映象到Cache的第j 块，则: ji mod (M ) （M为Cache的块数）, 组相联：主存中的每一块可以被放置Cache中唯一的一个组中的任何一个位置。 组相联是直接映象和全相联的一种折衷, 设M2m，则当表示为二进制数时，j 实际 上就是i 的低m 位：,3. 组相联映象,m位,j,i：,上述的j 和k 通常称为索引,组的选择常采用位选择算法 若主存第i 块映象到第k 组，则:ki mod（G） （G为Cache的组数）设G2g，则当表示为二进制数时，k 实际上就是i 的低 g 位：,g 位,k,i：, 绝大多数计算机的Cache: n 4 想一想：相联度一定是越大越好？, n 路组相联：每组中有n 个块(nM/G )，n 称为相联度。相联度越高，Cache空间的利用率就越高块冲突概率就越低，失效率也就越低。,全相联,直接映象,组相联,n (路数),G (组数),M,M,1,1,1nM,1GM,查找方法,如何确定Cache中是否有所要访问的块？ 若有的话如何确定其位置？,目录表的结构, 只需查找候选位置所对应的目录表项, 并行查找与顺序查找, 提高性能的重要思想：主候选位置(MRU块) 前瞻执行, 并行查找的实现方法：,相联存储器 单体多字存储器比较器,路组相联Cache的查找过程, 直接映象Cache的查找过程,替换算法,所要解决的问题：当新调入一块，而Cache 又已被占满时，替换哪一块？,1. 随机法 优点：实现简单 2. FIFO 3. LRU 优点：失效率低,写策略,1. “写”操作所占的比例 Load指令：26 Store指令：9 “写”在所有访存操作中所占的比例： 9/(100269)7 “写”在访问Cache操作中所占的比例： 9/(269)25,3“写”访问有可能导致Cache和主存内容的不一致,2. “写”操作必须在确认是命中后才可进行,两种写策略 写直达法 执行“写”操作时，不仅写入Cache，而且 也写入下一级存储器。 写回法 执行“写”操作时，只写入Cache。仅当 Cache中相应的块被替换时，才写回主存。 (设置“污染位”),5两种写策略的比较 写回法的优点：速度快，所使用的存储器频 带较低； 写直达法的优点：易于实现，一致性好。,6. 写缓冲器,写策略与调块 写回法 按写分配 写直达法 不按写分配,“写”操作时的调块 按写分配(写时取) 写失效时，先把所写单元所在的块调入 Cache，再行写入。 不按写分配(绕写法) 写失效时，直接写入下一级存储器而不调块。,Cache的结构,例子：DEC的Alpha AXP21064中的内部数据Cache,简介 容量：8KB 块大小：32B 块数：256 采用不按写分配 映象方法：直接映象 “写”策略：写直达 写缓冲器大小：4个块,混合Cache与分离Cache (1) 优缺点 (2) 失效率的比较,失效情况下的操作,16 KB,容 量,1 KB,2 KB,4 KB,8 KB,32 KB,指令 Cache,3.06%,失 效 率 的 比 较,64 KB,128 KB,数据 Cache,混合 Cache,2.26%,1.78%,1.10%,0.64%,0.39%,0.15%,0.02%,24.61%,20.57%,15.94%,10.19%,6.47%,4.82%,3.77%,2.88%,13.34%,9.78%,7.24%,4.57%,2.87%,1.99%,1.36%,0.95%,访问指令Cache的百分比指令Cache的失效率 访问数据Cache的百分比数据Cache的失效率,Cache性能分析,平均访问时间 平均访问时间命中时间失效率失效开销,失效率,假设Cache的命中时间为1个时钟周期，失效开销为50 个时钟周期，在混合Cache中一次load或store操作访问Cache的命中时间都要增加一个时钟周期(因为混合Cache只有一个端口，无法同时满足两个请求。混合Cache会导致结构冲突)，根据表所列的失效率，试问指令Cache和数据Cache容量均为16KB的分离Cache和容量为32KB的混合Cache相比，哪种Cache的失效率更低？又假设采用写直达策略，且有一个写缓冲器，并且忽略写缓冲器引起的等待。请问上述两种情况下平均访存时间各是多少？,解： 如前所述，约75%的访存为取指令。因此， 分离Cache的总体失效率为： (75%0.64%)(25%6.47%)2.10% 根据表，容量为32KB的混合Cache的失 效率略低一些，只有1.99%.,平均访存时间公式可以分为指令访问和数据访问两部分： 平均访存时间指令所占的百分比 (指令命中时间指令失效率失效开销) 数据所占的百分比 (数据命中时间数据失效率失效开销) 所以，两种结构的平均访存时间分别为： 平均访存时间分离75%(10.64%50) 25%(16.47%50) (75%1.32)(25%4.325) 0.9901.0592.05,平均访存时间混合75%(11.99%50) 25%(111.99%50) (75%1.995)(25%2.995) 1.4960.7492.24,程序执行时间 CPU时间(CPU执行周期数存储器停顿周期数) 时钟周期时间 其中： 存储器停顿周期数访存次数失效率失效开销,CPU时间ICCPIexe每条指令的平均存储 器停顿周期数时钟周期时间,CPU时间ICCPIexe访存次数/指令数 失效率失效开销时钟周期时间,例 我们用一个和Alpha AXP类似的机器作为 第一个例子。假设Cache失效开销为50个时钟 周期，当不考虑存储器停顿时，所有指令的 执行时间都是2.0个时钟周期， Cache的失效 率为2%，平均每条指令访存1.33次。试分析 Cache对性能的影响。,考虑Cache的失效后，性能为： CPU 时间有cacheIC(2.0(1.332%50) 时钟周期时间 IC3.33时钟周期时间,CPU 时间IC(CPIexe ) 时钟周期时间,存储器停顿周期数,指令数,解：,实际CPI ：3.33 3.33/2.0 = 1.67(倍),CPU时间也增加为原来的1.67倍。但若不采用Cache,则： CPI2.0+501.3368.5,考虑两种不同组织结构的Cache：直接映象 Cache和两路组相联Cache，试问它们对CPU的性 能有何影响？先求平均访存时间，然后再计算 CPU性能。分析时请用以下假设： 理想Cache(命中率为100)情况下的CPI 为2.0，时钟周期为2ns，平均每条指令 访存1.3次。 两种Cache容量均为64KB，块大小都是32 字节。, 后图说明，在组相联Cache中，我们必须增 加一个多路选择器，用于根据标识匹配结果 从相应组的块中选择所需的数据。因为CPU 的速度直接与Cache命中的速度紧密相关,所 以对于组相联Cache，由于多路选择器的存 在而使CPU的时钟周期增加到原来的1.10倍。 这两种结构Cache的失效开销都是70ns。在 实际应用中，应取整为整数个时钟周期。 命中时间为1个时钟周期，64KB直接映象 Cache的失效率为1.4%，相同容量的两路组 相联Cache的失效率为1.0%。,由: 平均访存时间命中时间失效率失效开销 得: 平均访存时间1路2.0(0.01470)2.98ns 平均访存时间2路2.01.10(0.01070)2.90ns,由: CPU 时间IC(CPIexe每条指令的平均存储器 停顿周期数)时钟周期时间 IC (CPIexe时钟周期时间 每条指令的平均存储器停顿时间),解：,CPU时间1路IC(2.02(1.30.01470) 5.27IC CPU时间2路IC(2.021.10 (1.30.01070) 5.31IC,5.31IC,CPU时间1路, 1.01,5.27IC,CPU时间2路,平均访存时间命中时间失效率失效开销 可以从三个方面改进Cache的性能： (1) 降低失效率 (2) 减少失效开销 (3) 减少Cache命中,改进Cache性能,(1)强制性失效(Compulsory miss) 当第一次访问一个块时，该块不在Cache中，需从下一级存储器中调入Cache，这就是强制性失效。 (冷启动失效，首次访问失效。) (2) 容量失效(Capacity miss ) 如果程序执行时所需的块不能全部调入Cache中，则当某些块被替换后，若又重新被访问，就会发生失效。这种失效称为容量失效。,降低Cache失效率的方法,(3) 冲突失效(Conflict miss) 在组相联或直接映象Cache中，若太多 的块映象到同一组(块)中，则会出现该组 中某个块被别的块替换(即使别的组或块有 空闲位置)，然后又被重新访问的情况。这 就是发生了冲突失效。 (碰撞失效，干扰失效),可以看出： (1) 相联度越高，冲突失效就越少； (2) 强制性失效和容量失效不受相联度的影响； (3) 强制性失效不受Cache容量的影响，但容 量失效却随着容量的增加而减少； (4) 表中的数据符合2:1的Cache经验规则，即 大小为N 的直接映象Cache的失效率约等于 大小为N/2 的两路组相联Cache的失效率。,强制性失效：增加块大小，预取 (本身很少) 容量失效：增加容量 (抖动现象) 冲突失效：提高相联度 (理想情况：全相联),减少三种失效的方法,许多降低失效率的方法会增加命中时间或失效开销,增加Cache块大小,1. 失效率与块大小的关系 (1) 对于给定的Cache容量，当块大小增加 失效率开始是下降，后来反而上升了； (2) Cache容量越大，使失效率达到最低的 块大小就越大。,2. 增加块大小会增加失效开销,例 5.4,假定存储系统在延迟40个时钟周期后，每2个 时钟周期能送出16个字节。即:经过42个时钟周期， 它可提供16个字节；经过44个时钟周期，可提供32 个字节；依此类推。试问对于表5-6中列出的各种 容量的Cache，在块大小分别为多少时，平均访存 时间最小？,解： 1KB、4KB、16KB Cache: 块大小32字节 64KB、256KB Cache: 块大小64字节,提高相联度,1. 采用相联度超过8的方法实际意义不大,2. 2:1 Cache经验规则 容量为N 的直接映象Cache 容量为N/2的两路组相联Cache,3. 提高相联度是以增加命中时间为代价 例如： TTL或ECL板级Cache，两路组相联：增加10 定制的CMOS Cache, 两路组相联：增加2,假定提高相联度会按下列比例增大处理器时钟周期： 时钟周期2路 1.10时钟周期1路 时钟周期4路 1.12时钟周期1路 时钟周期8路 1.14时钟周期1路 假定命中时间为1个时钟，直接映象情况 下失效开销为50个时钟周期，而且假设不必将 失效开销取整。使用表55中的失效率，试问 当Cache为多大时，以下不等式成立？,平均访存时间8路 平均访存时间4路 平均访存时间4路 平均访存时间2路 平均访存时间2路 平均访存时间1路,在各种相联度的情况下，平均访存时间分别为： 平均访存时间8路 = 命中时间8路 + 失效率8路 失效开销8路 = 1.14失效率8路50 平均访存时间4路 = 1.12 失效率4路50 平均访存时间2路 = 1.10 失效率2路50 平均访存时间1路 = 1.00 失效率1路50,在每种情况下的失效开销相同，都是50个时钟周期。把相应的失效率代入上式， 即可得平均访存时间。 例如，1KB的直接映象Cache的平均访存时间为： 平均访存时间1路 1.00(0.13350) 7.65 容量为128KB的8路组相联Cache的平均访存时间为： 平均访存时间8路 1.14(0.00650) 1.44,1. 基本思想 在Cache和它从下一级存储器调数据 的通路之间设置一个全相联的小Cache， 用于存放被替换出去的块(称为Victim)， 以备重用。,Victim Cache,对于减小冲突失效很有效，特别是对于小容量的直接映象数据Cache，作用尤其明显。 例如，项数为4的Victim Cache: 使4KB Cache的冲突失效减少20%90%,作用,直接映象 vs组相联,伪相联Cache,伪相联Cache,优 点,缺 点,直接映象,组相联,命中时间小,命中时间大,失效率高,失效率低,取直接映象及组相联两者的优点： 命中时间小，失效率低,(1) 基本思想及工作原理 在逻辑上把直接映象Cache的空间上下平分为两个区。对于任何一次访问，伪相联Cache先按直接映象Cache的方式去处理。若命中，则其访问过程与直接映象Cache的情况一样。若不命中，则再到另一区相应的位置去查找。若找到，则发生了伪命中，否则就只好访问下一级存储器。,(2) 快速命中与慢速命中 要保证绝大多数命中都是快速命中。,3. 例题,假设当在按直接映象找到的位置处没有发 现匹配、而在另一个位置才找到数据(伪命中) 需要2个额外的周期。仍用上个例子中的数据， 问：当Cache容量分别为2KB和128KB时，直接 映象、两路组相联和伪相联这三种组织结构中， 哪一种速度最快？,首先考虑标准的平均访存时间公式： 平均访存时间伪相联 命中时间伪相联失效率伪相联失效开销伪相联 由于： 失效率伪相联失效率2路 命中时间伪相联命中时间1路伪命中率伪相联2； 伪命中率伪相联命中率2路命中率1路 (1失效率2路)(1失效率1路) 失效率1路失效率2路,故： 平均访存时间伪相联 命中时间1路(失效率1路失效率2路)2 失效率2路失效开销1路,将表中的数据代入上面的公式，得： 平均访存时间伪相联，2KB 1(0.0980.076)2(0.07650) 4.844 平均访存时间伪相联，128KB 1(0.0100.007)2(0.00750) 1.356,根据上一个例子中的表58，对于2KB Cache，可得： 平均访存时间1路 5.90 个时钟 平均访存时间2路 4.90 个时钟 对于128KB的Cache有，可得： 平均访存时间1路 1.50 个时钟 平均访存时间2路 1.45 个时钟 可见，对于这两种Cache容量，伪相联Cache 都是速度最快的。,缺点：多种命中时间,硬件预取技术,1. 指令和数据都可以预取,2. 预取内容既可放入Cache，也可放在 外缓冲器中 例如：指令流缓冲器,3. 预取效果 (1) Joppi的研究结果 指令预取 (4KB，直接映象Cache, 块大小16字节),1个块的指令流缓冲器： 捕获1525的失效 4个块的指令流缓冲器： 捕获50 16个块的指令流缓冲器：捕获72, 数据预取 (4KB,直接映象Cache) 1个数据流缓冲器：捕获25的失效还可以采用多个数据流缓冲器,Palacharla和Kessler的研究结果 流缓冲器：既能预取指令又能预取数据 对于两个64KB四路组相联Cache来说： 8个流缓冲器能捕获5070的失效。,Alpha AXP 21064采用指令预取技术，其实际 失效率是多少？若不采用指令预取技术，Alpha APX 21064的指令Cache必须为多大才能保持平均访 存时间不变？,解： 假设从预取缓冲器中找到所需指令需多花1个 时钟周期。 平均访存时间预取 命中时间失效率预取命中率1 失效率(1预取命中率)失效开销,假设： 预取命中率25 命中时间1个时钟周期 失效开销50个时钟周期 由表5.4可知，8KB指令Cache的失效率1.10 故平均访存时间预取 1(1.10 %25 %1) (1.10 %(125 %)50) 10.002750.4125 1.415 由公式： 平均访问时间命中时间失效率失效开销,可得相应的失效率为： 失效率(平均访问时间命中时间)/失效开销 (1.4511)/500.83,8KB Cache,带预取的 8kB Cache,失效率,1.10,0.83,16KB Cache,0.64,由编译器控制的预取,1. 预取的类型 寄存器预取：把数据取到寄存器中 Cache预取： 只将数据取到Cache中 故障性预取：预取时，若出现虚地址故障 或违反访问权限，就会发生异常。 非故障性预取：预取时，若出现虚地址故 障或违反访问权限，并不会导致异常，只 是转变为“不预取”。,由编译器加入预取指令，在数据被用到之前发出预取请求。,4. 例题,2. 在预取数据的同时，处理器应能继续执行 只有这样，预取才有意义。 非阻塞Cache (非锁定Cache),3. 循环是预取优化的主要对象 失效开销小时：循环体展开12次 失效开销大时：循环体展开许多次,例 对于下面的程序，判断哪些访问可能会导致 数据Cache失效。然后，加入预取指令以减少失 效。最后，计算所执行的预取指令的条数以及通 过预取避免的失效次数。假定： (1) 我们用的是一个容量为8KB、块大小为 16B的直接映象Cache，它采用写回法并 且按写分配。 (2) a、b分别为3100(3行100列)和1013 的双精度浮点数组，每个元素都是8个 字节。当程序开始执行时，这些数据都 不在Cache内。,for (i0 ; i 3 ; ii1 ) for (j0 ; j 100 ; jj1 ) aijbj0bj10;,解： (1) 计算过程 (2) 实效情况 总的失效次数251次 (3) 改进后的程序,for (j0，j100；jj1) prefetch (bj70); /* 预取7次循环后所需的b(j ,0 ) */ prefetch (a0j7); /* 预取7次循环后所需的a(0,j ) */ a0jbj 0 * b j10 for (i1; i 3; ii1) for (j0; j 100; jj1) prefetch(aij7); /* 预取7次循环后所需的a(i , j ) */ aijbj0 * bj10; ,例 在以下条件下，计算例5.8中所节约的时间： (1) 忽略指令Cache失效，并假设数据Cache 无冲突失效和容量失效。 (2) 假设预取可以被重叠或与Cache失效重 叠执行，从而能以最大的存储带宽传送 数据。 (3) 不考虑Cache失效时，修改前的循环每7 个时钟周期循环一次。修改后的程序中，,失效情况 总的失效次数19次,解： 修改前： 循环时间3007 2100 失效开销2515012550/14650 21001255014650,第一个预取循环每9个时钟周期循环一次， 而第二个预取循环每8个时钟周期循环一 次(包括外层for循环的开销)。 (4) 一次失效需50个时钟周期。,修改后： 循环时间100920082500 失效时间1950950 25009503450 加速比14650/34504.2,编译器优化,2KB Cache: 降低50 8KB Cache：降低75%,1. 基本思想,在编译时，对程序中的指令和数据进行重新组织，以降低Cache失效率。,2. McFaring 发现：通过对指令进行重新排序，可有效地降低指令Cache的失效率。,3. 数据对存储位置的限制比指令的少，因此 更便于优化。 通过把数据重新组织，使得在一块数 据被从Cache替换出去之前，能最大限度 利用其中的数据(访问次数最多) (1) 数组合并 举例： /* 修改前 */ int val SIZE; int key SIZE;,(2) 内外循环交换 举例： /* 修改前 */ for (j0 ;j100 ;jj1) for (i0 ;i5000 ;ii1) xij2*xij;,/* 修改后 */ struct merge int val ; int key ; ; struct merge merged_arraysize;,(3) 循环融合 举例： /* 修改前 */ for (i0 ; iN ;ii1) for (j0 ; jN ; jj1) aij1/bij*cij;,/* 修改后 */ for (i0 ;i100 ;ii1) for (j0 ;j 000 ;jj1) xij2*xij;,/* 修改后 */ for (i0 ;i N ;ii1) for (j0 ;j N ;jj1) aij1/bij*cij; dijaijcij; ,for (i0 ;iN ;ii1) for (j0 ; jN ;jj1) dijaijcij;,(4)分块 把对数组的整行或整列访问改为按块进行。,举例： /* 修改前 */ for (i0; i N; ii1) for (j0; j N; jj1) r0; for (k0; k N; kk1) rryik*zkj; xijr; ,计算过程 失效次数：2N3N2,/* 修改后 */ for (jj0; jj N; jjjj1) for (kk0; kk N; kkkk1) for (i0; i N; ii1) for (jjj; j min(jjB1,N); jj1) r0; for (kkk; k min(kkB1,N); kk1) rryik*zkj; xijxijr; ,失效次数：2N3 /B N2,让读失效优先于写,减少Cache失效开销,1. Cache中的写缓冲器导致对存储器访问的 复杂化,2. 解决问题的方法(读失效的处理) 推迟对读失效的处理 (缺点：读失效的开销增加，如50) 检查写缓冲器中的内容,3. 在写回法Cache中，也可采用写缓冲器,子块放置技术,1. 为减少标识的位数，可采用增加块大小的 方法，但这会增加失效开销，故应采用子 块放置技术。,2. 子块放置技术：把Cache块进一步划分为更 小的块(子块)，并给每个子块赋予一位有 效位，用于指明该子块中的数据是否有效。 Cache与下一级存储器之间以子块为单位传 送数据。但标识仍以块为单位。,请求字处理技术,1. 请求字 从下一级存储器调入Cache的块中，只有 一个字是立即需要的。这个字称为请求字。,2. 应尽早把请求字发送给CPU 尽早重启动：调块时，从块的起始位置开 始读起。一旦请求字到达，就立即发送给 CPU，让CPU继续执行。 请求字优先：调块时，从请求字所在的位 置读起。这样，第一个读出的字便是请求 字。将之立即发送给CPU。,3. 这种技术在以下情况下效果不大： Cache块较小 下一条指令正好访问同一Cache块的另 一部分,非阻塞Cache技术,1. 非阻塞Cache：Cache失效时仍允许CPU进行 其它的命中访问。即允许“失效下命中”。,2. 进一步提高性能：“多重失效下命中” “失效下失效” (存储器必须能够处理多个失效),3. 重叠失效个数对平均访问时间的影响,非阻塞Cache平均存储器等待时间 与阻塞Cache的比值,1,2,浮点程序,76,51,64,39,整数程序,81,78,78,重叠失效个数,对于图所描述的Cache，在两路组相联和“一次失效下命中”这两种措施中，哪一种对浮点程序更重要？对整数程序的情况如何？ 假设8KB数据Cache的平均失效率为： 对于浮点程序，直接映象Cache为11.4%，两路组相联Cache为10.7%； 对于整数程序，直接映象Cache为7.4%，两路组相联Cache为6.0%。并且假设平均存储器等待时间是失效率和失效开销的积，失效开销为16个时钟周期。,对于浮点程序，平均存储器等待时间为： 失效率直接映象失效开销11.4%161.82 失效率两路组相联失效开销10.7%161.71 1.71/1.820.94,对于整数程序： 失效率直接映象失效开销7.4 %161.18 失效率两路组相联失效开销6.0 %16 0.96 0.96/1.18=0.81,解：,采用两级Cache,1. 应把Cache做得更快？还是更大？ 答案：二者兼顾，再增加一级Cache 第一级Cache(L1)小而快 第二级Cache(L2)容量大,2. 性能分析 平均访问时间 命中时间L1失效率L1失效开销L1 命中时间L1失效率L1 (命中时间L2失效率L2失效开销L2),3. 局部失效率与全局失效率 局部失效率该级Cache的失效次数/到达 该级Cache的访问次数 例如：上述式子中的失效率L2 全局失效率该级Cache的失效次数/CPU 发出的访存的总次数 全局失效率L2失效率L1失效率L2 评价第二级Cache时，应使用全局失效率 这个指标。,假设在1000次访存中，第一级Cache失效40次， 第二级Cache失效20次。试问：在这种情况下，该 Cache系统的局部失效率和全局失效率各是多少？ 第一级Cache的失效率（全局和局部）是40/1000， 即4%；第二级Cache的局部失效率是20/40，即50%， 第二级Cache的全局失效率是20/1000，即2%。,4. 当第二级Cache比第一级Cache大得多时，两 级Cache的全局失效率与容量和第二级Cache 相同的单级Cache的失效率非常接近。,5. 第二级Cache的参数 第二级Cache不会影响CPU的时钟频率， 因此其设计有更大的考虑空间。 两个问题： 能否降低CPI中的平均访存时间部分？ 成本是多少？ (1) 容量 第二级Cache的容量一般比第一级的 大许多，如512KB。,(2) 相联度 第二级Cache可采用较高的相联度或伪相联方法,例 给出有关第二级Cache的以下数据： 两路组相联使命中时间增加10%CPU时钟周期 对于直接映象，命中时间L210个时钟周期 对于直接映象，局部失效率L225% 对于两路组相联，局部失效率L220% 失效开销L250个时钟周期 试问第二级Cache的相联度对失效开销的影响如何？,对于一个直接映象的第二级Cache来说，第一级Cache的失效开销为： 失效开销直接映象，L1 1025%5022.5个时钟周期 对于两路组相联第二级Cache来说，命中时间增加了10%(0.1)个时钟周期，故第一级Cache的失效开销为： 失效开销两路组相联，L1 10.120%5020.1个时钟周期 把第二级Cache的命中时间取整，得10或11，则：,失效开销两路组相联，L1 1020%5020.0个时钟周期 失效开销两路组相联，L1 1120%5021.0个时钟周期 故对于第二级Cache来说，两路组相联优于直接映象。,(3) 块大小 第二级Cache可采用较大的块， 如 64、128、256字节。 为减少平均访存时间，可以让容量较小的第一级Cache采用较小的块，而让容量较大的第二级Cache采用较大的块。,5.5 减少命中时间,2. 应使Cache足够小，以便可以与CPU一起放 在同一块芯片上。,命中时间直接影响到处理器的时钟频率。在 当今的许多计算机中，往往是Cache的访问时间 限制了处理器的时钟频率。,1. 硬件越简单，速度就越快；,1. 虚拟Cache 访问Cache的索引以及Cache中的标识都是虚拟地址(一部分)。 2. 并非都采用虚拟Cache(为什么?) 3. 虚拟Cache的清空问题,虚拟Cache,解决方法：在地址标识中增加PID字段 (进程标识符) 三种情况下失效率的比较 单进程，PIDs，清空 PIDs与单进程相比：0.30.6 PIDs与清空相比： 0.64.3%,4. 同义和别名 解决方法：反别名法,页着色 5. 虚拟索引物理标识 优点：兼得虚拟Cache和物理Cache的好处 局限性：Cache容量受到限制 (页内位移) Cache容量页大小相联度 6. 举例：IBM3033的Cache 页大小4KB 相联度16,Cache容量164KB64KB 7. 另一种方法：硬件散列变换,页地址 地址标识,页内位移,索 引,块内位移,31,12 11,0,写操作流水化,1. 主存的主要性能指标：延迟和带宽 2. 以往： Cache主要关心延迟，I/O主要关心带宽 现在：Cache关心两者 下面讨论几种能提高主存性能的存储器组织技术在下面的讨论中，我们以处理Cache失效为例来说明各种存储器组织结构的好处。,主 存, 增加Cache块大小能利用主存带宽增加所带 来的好处。在以下的讨论中，我们假设基本存储器结构的性能为：,送地址需4个时钟周期 每个字的访问时间为24个时钟周期 传送一个字的数据需4个时钟周期, 为了减少失效开销TM，应该：,减少主存延迟 提高主存带宽,如果Cache大小为4个字，则： 失效开销4(4244) 432128(时钟周期) 带宽16/1280.0125(字节/时钟周期),增加存储器的宽度 性能举例 (参照前面的假设) 当宽度为4个字时： 失效开销132(周期) 带宽0.5(字节/周期), 缺点：,增加CPU和存储器之间的连接通路的宽度 CUP和Cache之间有一个多路选择器 扩充主存的最小增量增加了相应的倍数 写入有可能变得复杂, 存储器的各个体一般是按字交叉的 交叉存储器（interleaved memory） 通常是指存储器的各个体是按字交叉的。 字交叉存储器非常适合于处理： Cache读失效，写回法Cache中的写回,性能举例：(参照前面的假设) 失效开销4244444(周期) 带宽0.4(字节/周期),假设四个存储体的地址是在字一级交叉的，即 存储体0中每个字的地址对4取模都是0，体1中每个 字的地址对4取模都是1，依此类推。,0 4 8 12,地址 体0,1 5 9 13,地址 体1,2 6 10 14,地址 体2,3 7 11 15,地址 体3,假设某台机器的特性及其Cache的性能为： 块大小为1个字 存储器总线宽度为1个字 Cache失效率为3 % 平均每条指令访存1.2次 Cache失效开销为32个时钟周期(和上面相同) 平均CPI(忽略Cache失效)为2 试问多体交