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

第五章第五章 并行存储系统并行存储系统和同步机制和同步机制并行存储系统和同步机制计算机逻辑器件速度大幅提高，致使系统与存储机制计算机逻辑器件速度大幅提高，致使系统与存储机制之间的速度差距日益增大，存储系统已经成为计算机之间的速度差距日益增大，存储系统已经成为计算机系统的速度瓶颈。系统的速度瓶颈。多体并行、多体交叉多体并行、多体交叉宽字访问和顺序交叉访问宽字访问和顺序交叉访问存储器层次结构存储器层次结构层次存储系统层次存储系统层次存储系统在一般计算机系统中，有两种存储系统：在一般计算机系统中，有两种存储系统：Cache存储系统：由存储系统：由Cache和主存储器构成和主存储器构成主要目的：提高存储器速度主要目的：提高存储器速度,解决主存速度不足解决主存速度不足虚拟存储系统：由主存储器和硬盘构成虚拟存储系统：由主存储器和硬盘构成主要目的：扩大存储器容量主要目的：扩大存储器容量,解决主存容量不足解决主存容量不足存储系统存储系统的容量的容量要求：要求：提供尽可能大的地址空间提供尽可能大的地址空间能够随机访问能够随机访问方法有两种：方法有两种：只对系统中存储容量最大的那个存储器进行编只对系统中存储容量最大的那个存储器进行编址，其他存储器只在内部编址或不编址址，其他存储器只在内部编址或不编址 CacheCache存储系统存储系统另外设计一个容量很大的逻辑地址空间，把相另外设计一个容量很大的逻辑地址空间，把相关存储器都映射这个地址空间中关存储器都映射这个地址空间中 虚拟存储系统虚拟存储系统存储系统的价格存储系统的价格计算公式：计算公式：当当S2S1时，时，CC2S2与与S1不能相差太大不能相差太大存储系统存储系统的速度的速度表示方法：访问周期、存取周期、存储周期、表示方法：访问周期、存取周期、存储周期、存取时间等存取时间等命中率定义：命中率定义：在在M1M1存储器中访问到的概率存储器中访问到的概率 其中其中：N1N1是对是对M1M1存储器的访问次数存储器的访问次数 N2N2是对是对M2M2存储器的访问次数存储器的访问次数访问周期与命中率的关系：访问周期与命中率的关系：T THT1HT1(1(1H)T2H)T2 当命中率当命中率H1H1时，时，TT1TT1存储系统的访问效率：存储系统的访问效率：访问效率主要与命中率和两级存储器的速度之比有关访问效率主要与命中率和两级存储器的速度之比有关例例3.13.1：假设：假设T T2 2T T，在命中率，在命中率H H为为0.90.9和和0.990.99两种情两种情况下，分别计算存储系统的访问效率。况下，分别计算存储系统的访问效率。解：解：当当H0.9时，时，e11(0.95(10.9)0.72当当H0.99时，时，e21(0.995(10.99)0.96提高存储系统速度的两条途径：提高存储系统速度的两条途径：一是提高命中率一是提高命中率H H，二是两个存储器的速度不要相差太大二是两个存储器的速度不要相差太大其中：第二条有时做不到其中：第二条有时做不到(如虚拟存储器如虚拟存储器)，这时，只，这时，只能能依靠提高命中率依靠提高命中率例例3.23.2：在虚拟存储系统中，两个存储器的速度相差：在虚拟存储系统中，两个存储器的速度相差特别悬殊，例如：特别悬殊，例如：T T2 210105 5 T T。如果要使访问效率。如果要使访问效率到达到达e e0.90.9，问需要有多高的命中率？，问需要有多高的命中率？解：解：0.9H90000(1-H)189999.1 H89999计算得：计算得：H0.999998888877777 0.9999995.采用预取技术提高命中率采用预取技术提高命中率 方法：方法：不命中时，把不命中时，把M2存储器中相邻多个单存储器中相邻多个单元组成的一个数据块取出来送入元组成的一个数据块取出来送入M1存储器中。存储器中。计算公式：计算公式：其中：其中：H H是采用预取技术之后的命中率是采用预取技术之后的命中率 H H是原来的命中率是原来的命中率 n n为数据块大小与数据重复使用次数的乘积为数据块大小与数据重复使用次数的乘积例例3.3：在一个Cache存储系统中，当Cache的块大小为一个字时，命中率H0.8；假设数据的重复利用率为5，T25T1。计算块大小为个字时，Cache存储系统的命中率？并分别计算访问效率。解：解：n4520，采用预取技术之后，命中率提高到：证明方法一：证明方法一：采用预取技术之后，不命中率不命中率(1-H)(1-H)降低倍：降低倍：证明方法二：证明方法二：在原有命中率的计算公式中，把访问次数扩大到n倍。由于采用了预取技术，命中次数为：nN1(n-1)N2,不命中次数仍为N2，因此新的命中率为：存储系统的层次结构多个层次的存储器：多个层次的存储器：第第1层：层：RegisterFiles(寄存器堆寄存器堆)第第2层：层：Buffers(Lookahead)(先行缓冲栈先行缓冲栈)第第3层：层：Cache(高速缓冲存储器高速缓冲存储器)第第4层：层：MainMemory(主存储器主存储器)第第5层：层：OnlineStorage(联机存储器联机存储器)第第6层：层：Off-lineStorage(脱机存储器脱机存储器)用用i表示层数，表示层数，则有：则有：工作周期工作周期TiTi+1，存储容量：存储容量：SiSi+1，单位单位价格：价格：CiCi+1存储层次的四个问题1.当把一个块调入高一层(靠近CPU)存储器时，可以放在哪些位置上?(映象规则)2.当所要访问的块在高一层存储器中时，如何找到该块?(查找算法)3.当发生失效时，应替换哪一块？(替换算法)4.当进行写访问时，应进行哪些操作?(写策略)多体并行多体并行,多套地址寄存器和控制逻辑多套地址寄存器和控制逻辑1.1.高位交叉访问存储器高位交叉访问存储器主要目的：主要目的：扩大存储器容量扩大存储器容量实现方法：实现方法：用地址码的高位部分区分存储体号用地址码的高位部分区分存储体号要求要求每个模块都有各自独立的控制部件，每个模每个模块都有各自独立的控制部件，每个模块均可独立工作。但系统地址的连续空间落在块均可独立工作。但系统地址的连续空间落在同一存储体内，容易发生访存冲突。并行存取同一存储体内，容易发生访存冲突。并行存取的可能性很小。的可能性很小。交叉访问存储器高位交叉访问存储器结构框图高位交叉访问存储器结构框图例例3.43.4：用用4M4M字字4 4位位的的存存储储芯芯片片组组成成16M16M3232位位的主存储器。共用存储芯片：的主存储器。共用存储芯片：用用最最高高2 2位位地地址址经经译译码码后后产产生生的的信信号号，控控制制各各组组存储芯片存储芯片CSCS。每每组组中中的的3232根根数数据据线线分分别别对对应应直直接接相相连连，称称为为“线或线或”方式。方式。低位交叉访问存储器低位交叉访问存储器 主要目的：提高存储器访问速度主要目的：提高存储器访问速度 实现方法：用地址码的低位部分区分存储体号实现方法：用地址码的低位部分区分存储体号要求每个模块都有各自独立的控制部件，每个模要求每个模块都有各自独立的控制部件，每个模块均可独立工作。系统地址在一个存储体内部是块均可独立工作。系统地址在一个存储体内部是不连续的，对连续地址的访问分布在不同的存储不连续的，对连续地址的访问分布在不同的存储体中，可避免存储体访问冲突。体中，可避免存储体访问冲突。理想情况下，即一个模理想情况下，即一个模m m的多体交叉访问存储器的多体交叉访问存储器在不发生分体冲突时的频宽是单体存储器频宽的在不发生分体冲突时的频宽是单体存储器频宽的m m倍。倍。低位交叉访问存储器结构框图低位交叉访问存储器结构框图 地址编码方法：地址编码方法：由由8 8个存储体构成的低位交叉编址方式个存储体构成的低位交叉编址方式 n n个存储体分时启动个存储体分时启动 一种采用流水线方式工作的并行存储器一种采用流水线方式工作的并行存储器 每存储体的启动间隔为：每存储体的启动间隔为：t t 其中：其中：T Tm m为每个存储体的访问周期为每个存储体的访问周期,n n为存储体个数。为存储体个数。访问冲突访问冲突 共有共有n n个存储体，每个存储周期只能取到个存储体，每个存储周期只能取到k k个个有效字有效字,其余其余n-kn-k个存储体有冲突。个存储体有冲突。假设假设p(k)p(k)是是k k的概率密度函数，即的概率密度函数，即p(1)p(1)是是k k1 1的的概率，概率，p(2)p(2)是是k k2 2的概率，的概率，,p(n),p(n)是是k kn n的的概率。概率。k k的平均值为：的平均值为：N N是每个存储周期能够访问到的平均有效字的个是每个存储周期能够访问到的平均有效字的个数。数。通常把通常把 N N称为并行存储器的加速比。称为并行存储器的加速比。定义转移概率为定义转移概率为g g，即读出的是转移指令，且转，即读出的是转移指令，且转移成功的概率。这时有：移成功的概率。这时有：p(1)p(1)g g p(2)p(2)(1-p(1)g(1-p(1)g(1-g)g(1-g)g p(3)p(3)(1-p(1)-p(2)g(1-p(1)-p(2)g(1-g)(1-g)2 2g g p(k)p(k)(1-g)(1-g)k-1k-1g(kg(k1,2,1,2,n,n1)1)p(n)p(n)(1-g)(1-g)n-1n-1则：则：1g1g2(1-g)g2(1-g)g3(1-g)3(1-g)2 2g g (n-1)(1-g)(n-1)(1-g)n-2n-2g gn(1-g)n(1-g)n-1n-1若若g=0，n个存储体的加速倍数达到最大值个存储体的加速倍数达到最大值n。若若g=1,n个存储体的加速倍数只有个存储体的加速倍数只有1，与单个存，与单个存储体完全一样。储体完全一样。无冲突访问存储器1.1.一维数组一维数组(向量向量)的无冲突访问存储器的无冲突访问存储器 按连续地址访问，没有冲突，按连续地址访问，没有冲突，位移量为位移量为2 2的变址访问，速度降低一倍，的变址访问，速度降低一倍，具体方法：具体方法：存储体的个数取质数。存储体的个数取质数。原因：原因：变址位移量必然与存储体个数互质 设地址间距为设地址间距为d=1,md=1,m体交叉存储器的工作体体交叉存储器的工作体数为数为m m=m/(m,d)=m/(m,d)，其中，其中(m,d)(m,d)为为m m和和d d的最大的最大公约数。当公约数。当m m=T/=T/时，必将引起流水线断时，必将引起流水线断流，所以流，所以m m取为质数。取为质数。2.2.二维数组的无冲突访问存储器二维数组的无冲突访问存储器要求：要求：一个一个n nn n的二维数组，按行、列、对角的二维数组，按行、列、对角线和反对角线访问，并且在不同的变址位移线和反对角线访问，并且在不同的变址位移量情况下，都能实现无冲突访问。量情况下，都能实现无冲突访问。顺序存储：按行、对角线访问没有冲突，但按顺序存储：按行、对角线访问没有冲突，但按列访问每次冲突列访问每次冲突 错位存储：错位存储：按行、按列访问无冲突，按行、按列访问无冲突，但按对角线访问有冲突但按对角线访问有冲突nn二维数组无冲突访问存储方案二维数组无冲突访问存储方案 (PBudnik和和 DJKuck提出提出 )：并行存储体的个数并行存储体的个数m mn n，并且取质数，同，并且取质数，同时还要在行、列方向上错开一定的距离存储时还要在行、列方向上错开一定的距离存储数组元素。数组元素。设同一列相邻元素在并行存储器中错开设同一列相邻元素在并行存储器中错开d1d1个存储体存放，同一行相邻元素在并行存储个存储体存放，同一行相邻元素在并行存储器中错开器中错开d2d2个存储体存放。当个存储体存放。当m m2 22p2p1 1（p p为为任意自然数）时，能够同时实现按行、按列、任意自然数）时，能够同时实现按行、按列、按对角线和按反对角线无冲突访问的充要条按对角线和按反对角线无冲突访问的充要条件是：件是：d1d12 2P P，d2d21 1。例如：例如：44的二维数组，取并行存储体的个数的二维数组，取并行存储体的个数m5，由关系式由关系式m22P1，解得到，解得到p1，计算得到：，计算得到：d1212d2137 n nn n数组中的任意一个元素数组中的任意一个元素a aijij在无冲突并行存储器中的在无冲突并行存储器中的体号地址和体内地址的计算公式：体号地址和体内地址的计算公式：体号地址：体号地址：(2(2P P i ij jk)MOD k)MOD m m 体内地址：体内地址：i i 其中：0in1，0jn1，k是数组的第一个元素a00所在体号地址，通常k=0，m是并行存储体的个数，要求mn且为质数，p是满足m22P1关系的任意自然数。主要缺点：主要缺点：浪费存储单元 对于对于n nn n数组数组,有有1/(n+1)1/(n+1)的存储单元浪费的存储单元浪费 主要优点：主要优点：实现简单 行元素顺序存储，列元素按地址取模顺序存储行元素顺序存储，列元素按地址取模顺序存储3.3.二维数组的无冲突访问存储器二维数组的无冲突访问存储器(之二之二)规则：规则：对于任意一个对于任意一个nn的的数组，如果能够找到满足数组，如果能够找到满足n22P关系的任意自然数关系的任意自然数p，则这个二维数组就能够使，则这个二维数组就能够使用用n个并行存储体个并行存储体实现按行、列、对角线和反对角线实现按行、列、对角线和反对角线的无冲突访问。的无冲突访问。4 44 4数组用数组用4 4个存储体的无访问冲突存储方案个存储体的无访问冲突存储方案实现方法：实现方法：假设假设aij是是4 44 4数组中的任意一个元素，数组中的任意一个元素，下标下标i和和j都可都可以用两位二进制表示。假设以用两位二进制表示。假设i和和j的高位和低位分别为的高位和低位分别为iH、iL、jH和和jL，则则aij在无冲突并行存储器中的体号地在无冲突并行存储器中的体号地址和体内地址如下：址和体内地址如下：体号地址：体号地址：2(iL jH)(iH iL jL)体内地址：体内地址：j其中：其中：0i3，0j3主要优点：主要优点：没有浪费的存储单元没有浪费的存储单元主要缺点：在执行并行读和写操作时需要借助比较复杂主要缺点：在执行并行读和写操作时需要借助比较复杂的对准网络。的对准网络。Cache主存存储系统存储空间分割与地址计算存储空间分割与地址计算 映象规则全相联映象 全相联：主存中的任一块可以被放置到全相联：主存中的任一块可以被放置到 CacheCache中的任意一个位置。中的任意一个位置。对比：对比：阅览室位置阅览室位置 随便坐随便坐 特点：特点：空间利用率最高，冲突概率最低，空间利用率最高，冲突概率最低，实现最复杂。实现最复杂。CacheCache和主存分块和主存分块2.直接映象 直接映象：主存中的每一块只能被放置到直接映象：主存中的每一块只能被放置到 CacheCache中唯一的一个位置。中唯一的一个位置。对比：阅览室位置对比：阅览室位置 只有一个位置可以坐只有一个位置可以坐特点：空间利用率最低，冲突概率最高，实现特点：空间利用率最低，冲突概率最高，实现最简单。最简单。对于主存的第对于主存的第i i 块，若它映象到块，若它映象到CacheCache的第的第j j 块，则块，则:j ji i mod(mod(M M)（M M为为CacheCache的块数）的块数）组相联：主存中的每一块可以被放置组相联：主存中的每一块可以被放置CacheCache中中唯一的一个组中的任何一个位置。唯一的一个组中的任何一个位置。组相联是直接映象和全相联的一种折衷组相联是直接映象和全相联的一种折衷 设设M M2 2m m，则当表示为二进制数时，则当表示为二进制数时，j j 实际实际 上就是上就是i i 的低的低m m 位：位：3.组相联映象m位位ji：上述的上述的j j 和和k k 通常称为索引通常称为索引 组的选择常采用位选择算法组的选择常采用位选择算法 若主存第若主存第i i 块映象到第块映象到第k k 组，则组，则:k ki i modmod（G G）（G G为为CacheCache的组数）设的组数）设G G2 2g g，则当表，则当表示为二进制数时，示为二进制数时，k k 实际上就是实际上就是i i 的低的低 g g 位：位：g位位ki：绝大多数计算机的绝大多数计算机的Cache:Cache:n n 44 想一想：相联度一定是越大越好？想一想：相联度一定是越大越好？n n 路组相联：每组中有路组相联：每组中有n n 个块个块(n nM M/G G)，n n 称为相联度。相联度越高，称为相联度。相联度越高，CacheCache空间的利用空间的利用率就越高块冲突概率就越低，失效率也就越低。率就越高块冲突概率就越低，失效率也就越低。全相联全相联直接映象直接映象组相联组相联n n (路数路数)G G (组数组数)M MM M1 11 11 1n nM M1 1G GM M查找方法如何确定如何确定CacheCache中是否有所要访问的块？中是否有所要访问的块？若有的话如何确定其位置？若有的话如何确定其位置？目录表的结构目录表的结构 只需查找候选位置所对应的目录表项只需查找候选位置所对应的目录表项 并行查找与顺序查找并行查找与顺序查找 提高性能的重要思想：主候选位置提高性能的重要思想：主候选位置(MRU(MRU块块)前瞻执行前瞻执行 并行查找的实现方法：并行查找的实现方法：l 相联存储器相联存储器l 单体多字存储器比较器单体多字存储器比较器 路组相联路组相联CacheCache的查找过程的查找过程 直接映象直接映象CacheCache的查找过程的查找过程替换算法 所要解决的问题：当新调入一块，而所要解决的问题：当新调入一块，而CacheCache又已被占满时，替换哪一块？又已被占满时，替换哪一块？1.1.随机法随机法 优点：实现简单优点：实现简单2.FIFO2.FIFO3.LRU3.LRU 优点：失效率低优点：失效率低写策略写策略1.1.“写写”操作所占的比例操作所占的比例 LoadLoad指令：指令：2626 StoreStore指令：指令：9 9 “写写”在所有访存操作中所占的比例：在所有访存操作中所占的比例：9 9/(100/(10026269 9)7)7 “写写”在访问在访问CacheCache操作中所占的比例：操作中所占的比例：9 9/(26/(269 9)25)253 3“写写”访问有可能导致访问有可能导致CacheCache和主存内容的不一致和主存内容的不一致2.2.“写写”操作必须在确认是命中后才可进行操作必须在确认是命中后才可进行两种写策略两种写策略 写直达法写直达法 执行执行“写写”操作时，不仅写入操作时，不仅写入CacheCache，而且，而且 也写入下一级存储器。也写入下一级存储器。写回法写回法 执行执行“写写”操作时，只写入操作时，只写入CacheCache。仅当。仅当 CacheCache中相应的块被替换时，才写回主存。中相应的块被替换时，才写回主存。(设置设置“污染位污染位”)5两种写策略的比较 写回法的写回法的优点：优点：速度快，所使用的存储器频速度快，所使用的存储器频 带较低；带较低；写直达法的写直达法的优点：优点：易于实现，一致性好。易于实现，一致性好。6.写缓冲器写策略与调块写策略与调块 写回法写回法 按写分配按写分配 写直达法写直达法 不按写分配不按写分配“写写”操作时的调块操作时的调块 按写分配按写分配(写时取写时取)写失效时，先把所写单元所在的块调入写失效时，先把所写单元所在的块调入 CacheCache，再行写入。，再行写入。不按写分配不按写分配(绕写法绕写法)写失效时，直接写入下一级存储器而不调块。写失效时，直接写入下一级存储器而不调块。CacheCache的结构的结构例子：例子：DECDEC的的Alpha AXP21064Alpha AXP21064中的内部数据中的内部数据CacheCache简介简介 容量：容量：8KB8KB 块大小：块大小：32B32B 块数：块数：256256 采用不按写分配采用不按写分配 映象方法：直接映象映象方法：直接映象 “写写”策略：写直达策略：写直达 写缓冲器大小：写缓冲器大小：4 4个块个块混合混合CacheCache与分离与分离CacheCache (1)(1)优缺点优缺点 (2)(2)失效率的比较失效率的比较 失效情况下的操作失效情况下的操作16 KB16 KB容量容量1 KB1 KB2 KB2 KB4 KB4 KB8 KB8 KB32 KB32 KB指令指令Cache3.06%失失效效率率的的比比较较64 KB64 KB128 KB128 KB数据数据Cache混合混合Cache2.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%访问指令访问指令CacheCache的百分比的百分比指令指令CacheCache的失效率的失效率访问数据访问数据CacheCache的百分比的百分比数据数据CacheCache的失效率的失效率CacheCache性能分析性能分析平均访问时间平均访问时间 平均访问时间命中时间失效率平均访问时间命中时间失效率失效开销失效开销失效率失效率假设假设CacheCache的命中时间为的命中时间为1 1个时钟周期，失效开销为个时钟周期，失效开销为50 50 个时钟周期，在混合个时钟周期，在混合CacheCache中一次中一次loadload或或storestore操作访操作访问问CacheCache的命中时间都要增加一个时钟周期的命中时间都要增加一个时钟周期(因为混合因为混合CacheCache只有一个端口，无法同时满足两个请求。混合只有一个端口，无法同时满足两个请求。混合CacheCache会导致结构冲突会导致结构冲突)，根据表所列的失效率，试问，根据表所列的失效率，试问指令指令CacheCache和数据和数据CacheCache容量均为容量均为16KB16KB的分离的分离CacheCache和容和容量为量为32KB32KB的混合的混合CacheCache相比，哪种相比，哪种CacheCache的失效率更低的失效率更低？又假设采用写直达策略，且有一个写缓冲器，并且？又假设采用写直达策略，且有一个写缓冲器，并且忽略写缓冲器引起的等待。请问上述两种情况下平均忽略写缓冲器引起的等待。请问上述两种情况下平均访存时间各是多少？访存时间各是多少？解：解：如前所述，约如前所述，约75%75%的访存为取指令。因此，的访存为取指令。因此，分离分离CacheCache的总体失效率为：的总体失效率为：(75%(75%0.64%)0.64%)(25%(25%6.47%)6.47%)2.10%2.10%根据表，容量为根据表，容量为32KB32KB的混合的混合CacheCache的失的失效率略低一些，只有效率略低一些，只有1.99%.1.99%.平均访存时间公式可以分为指令访问和数据访问两部分：平均访存时间公式可以分为指令访问和数据访问两部分：平均访存时间指令所占的百分比平均访存时间指令所占的百分比 (指令命中时间指令失效率指令命中时间指令失效率失效开销失效开销)数据所占的百分比数据所占的百分比 (数据命中时间数据失效率数据命中时间数据失效率失效开销失效开销)所以，两种结构的平均访存时间分别为：所以，两种结构的平均访存时间分别为：平均访存时间平均访存时间分离分离75%75%(1(10.64%0.64%50)50)25%25%(1(16.47%6.47%50)50)(75%(75%1.32)1.32)(25%(25%4.325)4.325)0.9900.9901.0591.0592.052.05平均访存时间平均访存时间混合混合75%75%(1(11.99%1.99%50)50)25%25%(1(11 11.99%1.99%50)50)(75%(75%1.995)1.995)(25%(25%2.995)2.995)1.4961.4960.7490.7492.242.24程序执行时间程序执行时间 CPUCPU时间时间(CPU(CPU执行周期数存储器停顿周期数执行周期数存储器停顿周期数)时钟周期时间时钟周期时间 其中：其中：存储器停顿周期数访存次数存储器停顿周期数访存次数失效率失效率失效开销失效开销CPUCPU时间时间ICICCPIexeCPIexe每条指令的平均存储每条指令的平均存储 器停顿周期数器停顿周期数 时钟周期时间时钟周期时间CPUCPU时间时间ICICCPIexeCPIexe访存次数访存次数/指令数指令数 失效率失效率失效开销失效开销 时钟周期时间时钟周期时间例例 我们用一个和我们用一个和Alpha AXPAlpha AXP类似的机器作为类似的机器作为第一个例子。假设第一个例子。假设CacheCache失效开销为失效开销为5050个时钟个时钟周期，当不考虑存储器停顿时，所有指令的周期，当不考虑存储器停顿时，所有指令的执行时间都是执行时间都是2.02.0个时钟周期，个时钟周期，CacheCache的失效的失效率为率为2%2%，平均每条指令访存，平均每条指令访存1.331.33次。试分析次。试分析CacheCache对性能的影响。对性能的影响。考虑考虑CacheCache的失效后，性能为：的失效后，性能为：CPU CPU 时间时间有有cachecacheICIC(2.0(2.0(1.33(1.332%2%50)50)时钟周期时间时钟周期时间 ICIC3.333.33时钟周期时间时钟周期时间CPU CPU 时间时间ICIC(CPICPIexeexe )时钟周期时间时钟周期时间存储器停顿周期数存储器停顿周期数指令数指令数解：解：实际实际CPI CPI：3.333.333.33/2.0=1.67(3.33/2.0=1.67(倍倍)CPU CPU时间也增加为原来的时间也增加为原来的1.671.67倍。但若不采用倍。但若不采用Cache,Cache,则：则：CPICPI2.0+502.0+501.331.3368.568.5 考虑两种不同组织结构的考虑两种不同组织结构的CacheCache：直接映象：直接映象CacheCache和两路组相联和两路组相联CacheCache，试问它们对，试问它们对CPUCPU的性的性能有何影响？先求平均访存时间，然后再计算能有何影响？先求平均访存时间，然后再计算CPUCPU性能。分析时请用以下假设：性能。分析时请用以下假设：理想理想Cache(Cache(命中率为命中率为100100)情况下的情况下的CPICPI 为为2.02.0，时钟周期为，时钟周期为2ns2ns，平均每条指令，平均每条指令 访存访存1.31.3次。次。两种两种CacheCache容量均为容量均为64KB64KB，块大小都是，块大小都是3232 字节。字节。后图说明，在组相联后图说明，在组相联CacheCache中，我们必须增中，我们必须增 加一个多路选择器，用于根据标识匹配结果加一个多路选择器，用于根据标识匹配结果 从相应组的块中选择所需的数据。因为从相应组的块中选择所需的数据。因为CPU CPU 的速度直接与的速度直接与CacheCache命中的速度紧密相关命中的速度紧密相关,所所 以对于组相联以对于组相联CacheCache，由于多路选择器的存，由于多路选择器的存 在而使在而使CPUCPU的时钟周期增加到原来的的时钟周期增加到原来的1.101.10倍。倍。这两种结构这两种结构CacheCache的失效开销都是的失效开销都是70ns70ns。在。在 实际应用中，应取整为整数个时钟周期。实际应用中，应取整为整数个时钟周期。命中时间为命中时间为1 1个时钟周期，个时钟周期，64KB64KB直接映象直接映象 CacheCache的失效率为的失效率为1.4%1.4%，相同容量的两路组，相同容量的两路组 相联相联CacheCache的失效率为的失效率为1.0%1.0%。由由:平均访存时间命中时间失效率平均访存时间命中时间失效率失效开销失效开销得得:平均访存时间平均访存时间1 1路路2.02.0(0.014(0.01470)70)2.98ns2.98ns平均访存时间平均访存时间2 2路路2.02.01.101.10(0.010(0.01070)70)2.90ns2.90ns由由:CPU CPU 时间时间ICIC(CPICPIexeexe每条指令的平均存储器每条指令的平均存储器 停顿周期数停顿周期数)时钟周期时间时钟周期时间 IC IC(CPICPIexeexe时钟周期时间时钟周期时间 每条指令的平均存储器停顿时间每条指令的平均存储器停顿时间)解：解：CPUCPU时间时间1 1路路ICIC(2.0(2.02 2(1.3(1.30.0140.01470)70)5.275.27ICICCPUCPU时间时间2 2路路ICIC(2.0(2.02 21.101.10 (1.3(1.30.0100.01070)70)5.315.31ICIC5.315.31ICICCPUCPU时间时间1 1路路 1.011.015.275.27ICICCPUCPU时间时间2 2路路平均访存时间命中时间失效率平均访存时间命中时间失效率失效开销失效开销可以从三个方面改进可以从三个方面改进CacheCache的性能：的性能：(1)(1)降低失效率降低失效率(2)(2)减少失效开销减少失效开销(3)(3)减少减少CacheCache命中命中改进改进CacheCache性能性能(1)(1)强制性失效强制性失效(Compulsory miss)(Compulsory miss)当第一次访问一个块时，该块不在当第一次访问一个块时，该块不在CacheCache中，需中，需从下一级存储器中调入从下一级存储器中调入CacheCache，这就是强制性失效。，这就是强制性失效。(冷启动失效，首次访问失效。冷启动失效，首次访问失效。)(2)(2)容量失效容量失效(Capacity miss)(Capacity miss)如果程序执行时所需的块不能全部调入如果程序执行时所需的块不能全部调入CacheCache中，中，则当某些块被替换后，若又重新被访问，就会发生失则当某些块被替换后，若又重新被访问，就会发生失效。这种失效称为容量失效。效。这种失效称为容量失效。降低降低CacheCache失效率的方法失效率的方法(3)3)冲突失效冲突失效(Conflict miss)(Conflict miss)在组相联或直接映象在组相联或直接映象CacheCache中，若太多中，若太多 的块映象到同一组的块映象到同一组(块块)中，则会出现该组中，则会出现该组 中某个块被别的块替换中某个块被别的块替换(即使别的组或块有即使别的组或块有 空闲位置空闲位置)，然后又被重新访问的情况。这，然后又被重新访问的情况。这 就是发生了冲突失效。就是发生了冲突失效。(碰撞失效，干扰失效碰撞失效，干扰失效)可以看出：可以看出：(1)(1)相联度越高，冲突失效就越少；相联度越高，冲突失效就越少；(2)(2)强制性失效和容量失效不受相联度的影响；强制性失效和容量失效不受相联度的影响；(3)(3)强制性失效不受强制性失效不受CacheCache容量的影响，但容容量的影响，但容 量失效却随着容量的增加而减少；量失效却随着容量的增加而减少；(4)(4)表中的数据符合表中的数据符合2:12:1的的CacheCache经验规则，即经验规则，即 大小为大小为N N 的直接映象的直接映象CacheCache的失效率约等于的失效率约等于 大小为大小为N N/2/2 的两路组相联的两路组相联CacheCache的失效率。的失效率。强制性失效：增加块大小，预取强制性失效：增加块大小，预取 (本身很少本身很少)容量失效：增加容量容量失效：增加容量 (抖动现象抖动现象)冲突失效：提高相联度冲突失效：提高相联度 (理想情况：全相联理想情况：全相联)减少三种失效的方法减少三种失效的方法许多降低失效率的方法会增加命中时间或失效开销许多降低失效率的方法会增加命中时间或失效开销增加增加CacheCache块大小块大小1.1.失效率与块大小的关系失效率与块大小的关系 (1)(1)对于给定的对于给定的CacheCache容量，当块大小增加容量，当块大小增加 失效率开始是下降，后来反而上升了；失效率开始是下降，后来反而上升了；(2)Cache(2)Cache容量越大，使失效率达到最低的容量越大，使失效率达到最低的 块大小就越大。块大小就越大。2.2.增加块大小会增加失效开销增加块大小会增加失效开销例例 5.45.4 假定存储系统在延迟假定存储系统在延迟4040个时钟周期后，每个时钟周期后，每2 2个个时钟周期能送出时钟周期能送出1616个字节。即个字节。即:经过经过4242个时钟周期，个时钟周期，它可提供它可提供1616个字节；经过个字节；经过4444个时钟周期，可提供个时钟周期，可提供3232个字节；依此类推。试问对于表个字节；依此类推。试问对于表5-65-6中列出的各种中列出的各种容量的容量的CacheCache，在块大小分别为多少时，平均访存，在块大小分别为多少时，平均访存时间最小？时间最小？解：解：1KB1KB、4KB4KB、16KB Cache:16KB Cache:块大小块大小3232字节字节 64KB64KB、256KB Cache:256KB Cache:块大小块大小6464字节字节块大小块大小（字节）（字节）失效开销失效开销（时钟周期）（时钟周期）Cache容量（字节）容量（字节）1K4K16K64K256K16427.3214.5992.6551.8571.45832446.8704.1862.2631.5941.30864487.6054.3602.2671.5091.2451285610.3185.3572.5511.5711.2742567216.8477.8473.3691.8281.353提高相联度提高相联度1.1.采用相联度超过采用相联度超过8 8的方法实际意义不大的方法实际意义不大2.2:1 Cache2.2:1 Cache经验规则经验规则 容量为容量为N N 的直接映象的直接映象CacheCache 容量为容量为N N/2/2的两路组相联的两路组相联CacheCache3.3.提高相联度是以增加命中时间为代价提高相联度是以增加命中时间为代价 例如：例如：TTLTTL或或ECLECL板级板级CacheCache，两路组相联：增加，两路组相联：增加1010 定制的定制的CMOS Cache,CMOS Cache,两路组相联：增加两路组相联：增加2 2 假定提高相联度会按下列比例增大处理器时钟周期：假定提高相联度会按下列比例增大处理器时钟周期：时钟周期时钟周期2 2路路 1.101.10时钟周期时钟周期1 1路路 时钟周期时钟周期4 4路路 1.121.12时钟周期时钟周期1 1路路 时钟周期时钟周期8 8路路 1.141.14时钟周期时钟周期1 1路路 假定命中时间为假定命中时间为1 1个时钟，直接映象情况个时钟，直接映象情况下失效开销为下失效开销为5050个时钟周期，而且假设不必将个时钟周期，而且假设不必将失效开销取整。使用表失效开销取整。使用表5 55 5中的失效率，试问中的失效率，试问当当CacheCache为多大时，以下不等式成立？为多大时，以下不等式成立？平均访存时间平均访存时间8 8路路 平均访存时间平均访存时间4 4路路平均访存时间平均访存时间4 4路路 平均访存时间平均访存时间2 2路路平均访存时间平均访存时间2 2路路 平均访存时间平均访存时间1 1路路 在各种相联度的情况下，平均访存时间分别为：在各种相联度的情况下，平均访存时间分别为：平均访存时间平均访