存储系统-3

存储系统的多层次结构cache-主存-辅存三级存储体系：三级存储层次主存-辅存存储层次：大容量、低成本；软硬件结合完成cache-主存存储层次:高速度、低成本；纯硬件完成7.3高速缓冲存储器cache解决存储系统三个指标：容量、速度、价格/位的矛盾处理器与主存的速度差距处理器与主存的速度差距处理器与主存的速度差距处理器与主存的速度差距TimeµProc60%/year19801981198319841985198619871988198919901991199219931994199519961997199819992000DRAM7%/yearDRAMCPU1982Processor-MemoryPerformanceGap:(grows50%/year)1101001000Performance“Moore’sLaw”Four-issue2GHzsuperscalaraccessing100nsDRAMcouldexecute800instructionsduringtimeforonememoryaccess!主要依据：程序的局部性原理程序的局部性原理7.3.1cache工作原理两种可预测的主存访问性质（两种可预测的主存访问性质（两种可预测的主存访问性质（两种可预测的主存访问性质（TwopredictablepropertiesofTwopredictablepropertiesofTwopredictablepropertiesofTwopredictablepropertiesofmemoryreferencesmemoryreferencesmemoryreferencesmemoryreferences））））::::�时间局部性时间局部性时间局部性时间局部性：某位置若被访问，则近期内很可能又被访问。：某位置若被访问，则近期内很可能又被访问。：某位置若被访问，则近期内很可能又被访问。：某位置若被访问，则近期内很可能又被访问。TemporalLocality:Ifalocationisreferenceditislikelytobereferencedagaininthenearfuture.�空间局部性空间局部性空间局部性空间局部性：某位置若被访问，则临近的位置也可能被访问。：某位置若被访问，则临近的位置也可能被访问。：某位置若被访问，则临近的位置也可能被访问。：某位置若被访问，则临近的位置也可能被访问。SpatialLocality:Ifalocationisreferenceditislikelythatlocationsnearitwillbereferencedinthenearfuture.同样，对数据的访问也会存在局部性现象。1、概述（1）cache的位置（2）cache的构成Cache的工作过程：主存块地址块内地址Cache块号块内地址地址变换Cache存储器替换算法部件CPUMM不命中（已满）不命中（未满）命中多字高速总线cc位位bb位位CacheCache地址地址CacheCache块号块号块内地址块内地址第第00块块第第11块块第第mm块块第第C-1C-1块块CACHECACHECACHECACHECACHECACHECACHECACHE22cc=C=C2、地址映射m位b位cc位位bb位位主存块号块内地址主存地址CacheCache地址地址CacheCache块号块号块内地址块内地址第第00块块第第11块块第第mm块块第第C-1C-1块块第0块第1块第x块第M-1块MMMMMMMMCACHECACHECACHECACHECACHECACHECACHECACHE•块块块块•命中命中命中命中////不命中不命中不命中不命中22cc=C=C22mm=M=M2、地址映射地址映像、地址变换（1）、全相连映射方式（2）、直接映射方式（3）、组相连映射方式16位8位4位8位主存块号块内地址主存地址Cache地址Cache块号块内地址第0块第1块第m块第15块第0块第1块第x块第65535块MMMMMMMMCACHECACHECACHECACHECACHE共4KB，每块256B，划分为16块（块内地址8位，块地址4位）主存共16MB，每块256B，划分为64K块（块内地址8位，块地址16位）16位8位4位8位主存块号块内地址主存地址Cache地址Cache块号块内地址第0块第1块第m块第15块第0块第1块第x块第65535块MMMMMMMMCACHECACHECACHECACHECACHE共4KB，每块256B，划分为16块（块内地址8位，块地址4位）主存共16MB，每块256B，划分为64K块（块内地址8位，块地址16位）16位8位X块4位8位主存块号块内地址主存地址相联比较01m相联存储器=命中Cache地址Cache块号块内地址第0块第1块第m块第15块第0块第1块第x块第65535块MMMMMMMM15CACHECACHECACHECACHE“全相连”CACHE共4KB，每块256B，划分为16块（块内地址8位，块地址4位）主存共16MB，每块256B，划分为64K块（块内地址8位，块地址16位）问题：上面的例子中，cache采用全相连映射方式问：进行相联比较的相联存储器的容量？12位4位8位·区号X第0块第1块第Y块第15块…………第1块第1块第15块…………第1块第15块…………第Y块第15块…………第0区第1区第X区第4095区主存区号区内块号块内地址主存地址比=命中(1)按地址查找(2)(3)01Y15CacheCache地址MM“直接”第0块第0块第0块问题：Cache与主存间采用全相联地址映像方式，Cache容量为4KB，分为4块每块1KB，主存容量为1MB。问：（1）Cache与主存地址的各字段如何划分？（2）若地址变换表如下，试根据主存地址确定变换后的Cache地址。⒈主存地址为654E2H时，高速缓存地址为H。⒉主存地址为D9D9DH时，高速缓存地址为H。地址变换表367H222H195H388H0312问题：一个具有16KB直接相连映射cache的32位微处理器，cache的块为4个32位的字，内存为256MB问：（1）主存地址为多少位（按字节编址），各字段如何划分？（2）主存地址为ABCDEF8H的单元调入cache中的位置？Y12位3位1位8位区号XZ3位1位8位第0块第1块…………第K块…………第0块第1块第0块…………第1块…………第0块第Z块第1块…………第0块第1块第0块第1块…………第0块第1块…………第0组第7组第Y组第7组第0组第7组第0000区第XXXX区第4444000099995555区0组Y组7组主存区号区内组号组内块号块内地址“组间直接,组内全相连”相联比较0115K命中Cache组号组内块号块内地址Cache地址主存地址…………CacheMM问题：上面的例子中，cache采用组相连映射方式问：进行相联比较的相联存储器的容量？问题：高速缓存Cache与主存间采用组相联地址映像方式（组间直接，组内全相联），高速缓存每组包含4块，每块为8个字，每个字为32位。若主存容量为2MB，Cache的容量为16KB。问：（1）请分析cache地址有多少位，各字段如何划分？（2）请分析主存地址有多少位，试说明主存区号、区内组号、组内块号、块内字号、字内地址号各用多少位表示？7.3.2替换算法若Cache未命中，而CacheCache已装满已装满，则需替换Cache中的块。�随机替换算法（随机替换算法（随机替换算法（随机替换算法（RANDRANDRANDRAND））））�先进先出算法（先进先出算法（先进先出算法（先进先出算法（FIFOFIFOFIFOFIFO））））�近期最少使用算法（近期最少使用算法（近期最少使用算法（近期最少使用算法（LRULRULRULRU））））对每块设置一个计数器，某块每命中一次，就将其计数器清0而其他块的计数器加1，记录Cache中各块的使用情况。当需要替换时，便将计数值最大的块替换出去。�最不经常使用算法（最不经常使用算法（最不经常使用算法（最不经常使用算法（LFULFULFULFU））））对每块设置一个计数器，且开始调入时计数为0。每被访问一次，被访问块的计数器加1。当需要替换时，便将计数值最小的块替换出去。同时将所有各块的计数器清0。（将计数周期限定在两次替换的时间间隔内）�最优替换算法（最优替换算法（最优替换算法（最优替换算法（OTPOTPOTPOTP））））要实现这种算法程序需执行两次。�例：例：例：例：假定程序在主存为假定程序在主存为假定程序在主存为假定程序在主存为5555块，块，块，块，CacheCacheCacheCache为为为为3333块。块。块。块。CPUCPUCPUCPU执行程序的顺序为：执行程序的顺序为：执行程序的顺序为：执行程序的顺序为：P2P2P2P2、、、、P3P3P3P3、、、、P2P2P2P2、、、、P1P1P1P1、、、、P5P5P5P5、、、、P2P2P2P2、、、、P4P4P4P4、、、、P5P5P5P5、、、、P3P3P3P3、、、、P2P2P2P2、、、、P5P5P5P5、、、、P2P2P2P2。画出。画出。画出。画出FIFOFIFOFIFOFIFO算算算算法和法和法和法和LRULRULRULRU算法的命中情算法的命中情算法的命中情算法的命中情况如图所示。况如图所示。况如图所示。况如图所示。7.3.3主存——cache内容的一致性指令Cache不存在一致性问题�写回法（写回法（写回法（写回法（WriteBackWriteBackWriteBackWriteBack））））�当CPU写Cache命中时，只将数据写入Cache而不立即写入主存。只有当被CPU写入修改的块被替换出去时才写回到主存中。这种方法减少了访问主存的次数,但是存在不一致性的隐患。�如果CPU写Cache未命中，则写修改是将相应主存块调入Cache之后，在Cache中进行。对主存的修改仍留待该块替换出去时进行。实现这种方法时，每个cache行必须配置一个修改位，以反映此行是否被CPU修改过。�全写法（写直达法全写法（写直达法全写法（写直达法全写法（写直达法WriteThroughWriteThroughWriteThroughWriteThrough））））�当CPU写Cache命中时，在将数据写入修改Cache的同时写入修改主存，较好地保证了主存与Cache内容的一致性。当写cache命中时，cache与主存同时发生写修改，因而较好地维护了cache与主存的内容的一致性。Cache中每块无需设置一个修改位以及相应的判断逻辑。缺点是Cache对CPU向主存的写操作无高速缓冲功能，降低了Cache的功效。当写cache未命中时，直接向主存进行写入。这时可以采用两种方式进行处理：WTWA：（WriteThroughWithWriteAllocate）取主存块到Cache并为其分配一个行位置；WTNWA：（WriteThroughWithNoWriteAllocate）不取主存块到Cache。�Cache的命中率在一个程序执行期间，设Nc表示cache完成存取的总次数，Nm表示主存完成存取的总次数，H定义为命中率，则有　　　　　　　　　　　=+CCCCCmCmCmCmNNNNHHHHNNNNNNNN7.3.4cache的性能分析