计算机组成原理第5章缓存

1、存储系统和结构第五章 (/2) 缓存/虚存部分第5章存储系统和结构“缓存虚存部分”部分作业： 5-23, 5-25 , 5-26 , 5-27Homework存储器部分内容提要 存储系统是由几个容量、速度和价格各不相同的存储器构成的系统。设计一个容量大、速度快、成本低的存储系统是计算机发展的一个重要课题。本章重点讨论主存储器的工作原理、组成方式以及运用半导体存储芯片组成主存储器的一般原则和方法，此外还介绍了高速一主存储器部分二.储存体系结构储存体系结构部分内容提要二.储存体系结构储存体系结构概述高速缓冲存储器虚拟存储器储存体系结构部分内容提要二.储存体系结构储存体系结构概述高速缓冲存储器虚拟存

2、储器储存体系结构概述Processor-Memory Performance Gap“Moores Law”Proc55%/year(2X/1.5yr)DRAM7%/year(2X/10yrs)Processor-MemoryPerformance Gap(grows 50%/year)储存体系结构概述The Memory Problem Build a big , fast, cheap memory Big memories are slow Even when built from fast components Fast memories are expensive储存体系结构概述To

3、day, there are three primary technologies used in building memory hierarchies(目前有三种主要技术分别用于构造“分级存储器体系”) DRAM (dynamic random access memory)动态随机访问内存，动态内存: Main memory(主存) is implemented from DRAM.SRAM (static random access memory)静态随机访问内存，静态内存: Levels closer to the processor (caches) use SRAM.Magneti

4、c disk: Magnetic disk is used to implement the largest and slowest level in the hierarchy. Memory technologyTypical access time$per GB in 2004SRAM0.5-5 ns$4000-$10,000DRAM50-70 ns$100-$200Magnetic disk5,000,000-20,000,000 ns$0.50-$2Memory Speeds and Costs储存体系结构概述Programs Have Locality 程序的局部性包括：时间局部性

5、和空间局部性。时间局部性是指如果一个存储单元被访问，则可能该单元会很快被再次访问。这是因为程序存在着循环。空间局部性是指如果一个存储单元被访问，则该单元邻近的单元也可能很快被访问。这是因为程序中大部分指令是顺序存储、顺序执行的，数据一般也是以向量、数组、树、表等形式簇聚地存储在一起的。 高速缓冲技术就是利用程序的局部性原理，把程序中经常使用的部分存放在速度较高容量较小的存储器中，从而实现存储的层次化结构，使整体的存储速度接近最快的存储体速度，容量接近最大的存储体容量。Example-1: Most programs contain loops(循环), so instructions and

6、data are likely to be accessed repeatedly, showing high amounts of temporal locality. Example-2: Since instructions are normally accessed sequentially(顺序执行), programs show high spatial locality. Example-3: Accesses to data also exhibit a natural spatial locality. For example, accesses to elements(元素

7、) of an array(数组) or a record will naturally have high degrees of spatial locality.储存体系结构概述We cant use large amounts of fast Memoryexpensive in $, watts, and spaceIdeal: the memo y hierarchy should be almost as fast as the top level, and almost as big and cheap as the bottom level program locality m

8、akes this possibleTradeoff cost speed and size speed using ahierarchy of memories:small, fast, expensive caches at the toplarge, slow, and cheap memory at the bottomThe Solution储存体系结构概述A Typical Memory Hierarchy (典型分级存储器体系) By taking advantage of the principle of locality 利用“局部性原理” Memory can be arr

9、anged as hierarchies , It can present the user with as much memory as is available in the cheapest technology and at the speed offered by the fastest technology. The goal is to provide the illusion of lots of fast memoryThe SolutionBut how do you manage this, and make it work?储存体系结构概述How is the Hier

10、archy Managed?registers memoryby compiler (programmer?)cache main memoryby the cache controller hardwaremain memory disksby the operating system (virtual memory)virtual to physical address mapping assisted by the hardware (TLB)by the programmer (files)储存体系结构概述储存体系结构部分内容提要二.储存体系结构储存体系结构概述高速缓冲存储器虚拟存储器

11、高速缓冲存储器Memory Hierarchy高速缓冲存储器cache main memoryby the cache controller hardware 高速缓冲技术就是利用程序的局部性原理，把程序中正在使用的部分存放在一个高速的容量较小的Cache中，使CPU的访存操作大多数针对Cache进行，从而使程序的执行速度大大提高。高速缓冲存储器Cache的基本结构 Cache和主存都被分成若干个大小相等的块，每块由若干字节组成。由于Cache的容量远小于主存的容量，它保存的信息只是主存中最活跃的若干块的副本。 Cache的工作流程Cache的读操作：CPU送出主存（大）地址，如果Cache命

12、中，此大地址变成Cache（小）地址并送Cache对其进行读操作，与主存无关；如果Cache不命中，则仍需访问主存，并把该块信息一次从主存调入Cache内。若此时Cache已满，则须根据某种替换算法，用这个块替换掉Cache中原来的某块信息。 Cache的写操作：当CPU发出写请求时，如果Cache命中，有可能会遇到Cache与主存中的内容不一致的问题，需要进行一定的写处理，处理的方法有：写直达法和写回法。ProcessorData are transferred术语及概念Cache与主存的地址映象替换算法更新策略Cache的性能topic高速缓冲存储器内容术语及概念Cache与主存的地址映象

13、替换算法更新策略Cache的性能topic高速缓冲存储器内容术语及概念ProcessorData are transferredBlock（块） The minimum unit of information that can be either present or not present in the two-level hierarchy. Block addressing varies by technology at each level Blocks are moved one level at a time术语及概念TerminologyHit(命中):如果处理器需要的数据出现在

14、高层的某个块里，称之为一次命中Hit Rate (命中率) :在高速缓存中找到目标数据的存储访问比例Hit Time (命中时间): 访问存储器某层所需要时间包括判断访问是否命中所需要的时间Miss(缺失):如果处理器需要的数据在高层找不到，称之为一次缺失Miss Rate (缺失率): =在高速缓存中找不到目标数据的存储访问比例 Miss Rate =1 - (Hit Rate)Miss Penalty(缺失损失) : 从底层将块取入该层所需要的时间包括访问 块，逐层向上传送块直至数据放入需要层所需时间Hit Time Miss PenaltyHopefully hit time is lo

15、w and miss rate is low术语及概念Terminology单级Cache二级Cache片内Cache（L1）和片外Cache（L2）统一Cache和分立Cache统一Cache：用一个Cache存放指令和数据分立Cache：指令和数据存放在不同的Cache中。（指令和数据分别用2个独立的cache）术语及概念具有Cache的存储器，其平均存取时间计算如下： 平均存取时间=htc+(1-h)(tc+tM) =tc+tM (1-h)其中： tc为Cache的存取时间 h为命中率 tM为主存的存取时间假设主存储器的大小为2n个字节，共分成2m个块，每个块的大小为2b个字节，则：n=

16、m+b 主存地址结构如下：Cache-主存之间的关系术语及概念假设Cache中有2c个块，每个块的大小为2b个字节，则Cache的大小为2c+b个字节，则： Cache地址结构如下：Cache-主存之间的关系术语及概念术语及概念Cache 工作原理The control unit deals with cache missesThe control unit must detect a miss and process the miss by fetching the requested data from memory (a low-level cache).If the cache rep

17、orts a hit, the computer continues using the data as if nothing had happened. For a cache miss, we can stall(停止) the entire processor, essentially freezing the contents of the temporary and programmer visible registers, While we wait for memory. 术语及概念Cache 工作原理处理cache缺失 the steps to be taken on an i

18、nstruction cache miss Send the original PC value (current PC-4) to the memory Instruct main memory to perform a read and wait for the memory to complete its access Write the cache entry , putting the data from memory in the data portion of the entry , writing the upper bits of the address (from the

19、ALU) into the tag field , and turning the valid bit on Restart the instruction execution at the first step , which will refetch the instruction , this time finding it in the cache. The control of the cache on a data access is essentially identical : on a miss , we simply stall the processor until th

20、e memory responds with the data.术语及概念Cache 工作原理处理cache缺失topic高速缓冲存储器内容术语及概念Cache与主存的地址映象替换算法更新策略Cache的性能Cache与主存的地址映象 直接映像地址映象与变换把主存的每一块映射到一个固定的Cache槽中，j=i mod 2c 其中j为Cache槽号，i为主存的块号， 2c为Cache的槽数One word/block, cache size = 1K words20Tag10IndexData IndexTagValid012.10211022102331 30 . . . 13 12 11 .

21、 . . 2 1 0Byte offset20Data32HitTo processorIf the tag and upper 20 bits of the address are equal and the valid bit is on, then the request hits(命中) in the cache, and the word is supplied to the processor.Otherwise, a miss occurs. Direct Mapped Cache circuit地址映象与变换地址映象与变换例： 全相联映像地址映象与变换通过允许每个主存块装入到C

22、ache的任何一槽中来克服直接映射的缺点 全相联映像电路地址映象与变换优点：Cache利用率高缺点：效率不高N = 区内块数，阴影区表示查找范围地址映象与变换例： 组相联映像地址映象与变换上述两种方案的折中。把Cache分成若干组，每组有若干块，组间为直接映像，组内字块为全相联映像方式Cache index selects a “set ”The two tags in the set are compared in parallelData is selected based on the tag全相联映像电路（路）地址映象与变换28 = 256 sets each with four wa

23、ys (each with 2 byte)31 30 . . . 13 12 11 10 9 8 . . . 3 2 1 0Four waysDataTagV012. 253 254 255DataTagV012. 253 254 255DataTagV012. 253 254 255 IndexDataTagV012. 253 254 2558Index21TagHitData324x1 select全相联映像电路（路）地址映象与变换设有8个块，分成2个组例：地址映象与变换topic高速缓冲存储器内容术语及概念Cache与主存的地址映象替换算法更新策略Cache的性能替换算法块的替换算法替换

24、策略：随机法RAND算法先进先出法FIFO算法近期最少使用法LRU （近期最久未使用法）Replacement Methods Which line do you replace on a miss? Direct Mapped Easy, you have only one choice Replace the line at the index you need N-way Set Associative Need to choose which way to replace Random ( choose one at random) Least Recently Used ( LRU)

25、 ( the one used least recently) Often difficult to calculate, so people use approximations. Often they are really not recently used块的替换算法先进先出法FIFO算法颠簸现象块的替换算法通过替换登记表实现块的替换算法LRU（最近最少使用: Least Recently Used ）算法 topic高速缓冲存储器内容术语及概念Cache与主存的地址映象替换算法更新策略Cache的性能更新策略What About Writes? So far we have talke

26、d about reading data But a processor also writes data Where do we put the data we want to write? In the cache? In main memory? In both? Caches have different policies for this question Most systems store the data in the cache Some also store the data in memory as well What happens on a cache miss de

27、pends on: Whether main memory is always up to date Processor does not need to “wait ”until the store completes更新策略Cache Write Policy Write through写通过( writes to cache and memory) Main memory is updated on each cache write Replacing a cache entry just replaces the existing entry with the new entry Me

28、mory write causes significant delay if pipeline must stall更新策略cache命中时：Use Write Buffer between cache and memory Processor writes data into the cache and the write buffer Memory controller slowly “drains ”buffer to memoryWrite Buffer First In First Out ( FIFO) Typically holds a small number of write

29、s Works fine if the rate of writes to memory is less than 1 / DRAM write cycle timeBuffering Writes Write back回写( write data only goes to the cache) Only the cache entry is updated on each cache write so main memory and the cache data are inconsistent Add “Dirty ”bit to the cache entry to indicate w

30、hether the data in the cache entry must be committed to memory Replacing a cache entry requires writing the data back to memory before replacing the entry if it is “dirty ”更新策略Cache Write Policy更新策略Cache失效时：Write Policy Trade-offs Write through Misses are simpler and cheaper since block does not nee

31、d to be written back Easier to implement, though most systems need an additional buffer, called a write buffer, to be practical Uses a lot of bandwidth to the next level of memory Write back Words can be written at the cache rate Multiple writes within a block require only one “writeback ”later Effi

32、cient block transfer on write back to memory at eviction更新策略Cache的一致性问题对数据Cache而言，由于有多种写方式，且有多级Cache，因此在修改Cache中的数据时，会造成主存储器和Cache中的数据不一致。更新策略当系统中存在多个Cache时，解决多个Cache中数据的一致性问题的方法：总线监视法硬件监视法划出不可高速缓存存储区法Pentium处理器中支持“修改/排它/共享/无效”(Modify/exclusive/shared/invalid)简称MESI协议。这样，Cache中的状态位为2位，表示4中状态之一。topic

33、高速缓冲存储器内容术语及概念Cache与主存的地址映象替换算法更新策略Cache的性能cache的性能cache的命中率与cache容量的关系块容量与命中率cache的性能地址映象与命中率Cache的相联性与失效率cache的性能储存体系结构部分内容提要二.储存体系结构储存体系结构概述高速缓冲存储器虚拟存储器虚拟存储器Memory Hierarchy虚拟存储器main memory disksby the operating system (virtual memory)virtual to physical address mapping assisted by the hardware (

34、TLB)by the programmer (files) 虚拟存储器指的是“主存-辅存”层次，它能使计算机具有辅存的容量，接近于主存的速度和辅存的每位成本。使程序员可以按比主存大得多的空间来编制程序，即按虚存空间编址。虚拟存储器两种存储层次的比较区别： 主存/cache的访问“时间比”较小，典型为10：1。每次传送的基本信息单元较小(字块),几个至几十个字节。 辅存/主存的访问“时间比”达100:1至1000:1。每次传送的基本信息单元较大(段或页),几十至几千字节。相同： 它们采用的地址变换及映像方法和替换策略，从原理上看是相同的。topic虚拟存储器内容术语及概念虚拟存储器的管理方式替换

35、算法快表TLB缓存-虚存一体化术语及概念虚拟存储器的管理方式替换算法快表TLB缓存-虚存一体化topic高速缓冲存储器内容术语及概念Main memory（physical memory） (实地址)：主存 ，real memory address usually DRAM, distinguish it from virtual memory.Second memory (storage)：辅存(外存)，usually magnetic disk, CD, etc. Virtual Address (虚地址)： An address that corresponds to a locatio

36、n in virtual space and is translated by address mapping to a physical address when memory is acceded.页(段)： 主存和辅存之间传递信息的最小单位Virtual page number：虚地址空间页号Physical page number：物理页号（主存页号）Page offset：页偏置Page Fault(缺页)：An event that page is not present in main memory.page table(页表)：虚页到实页转换索引表基本术语In virtual

37、memory system, we locate pages by using a table that indexes the memory; this structure is called a page table(页表) and resides in memory.A page table is indexed with the page number from the virtual address to discover the corresponding physical page number.To indicate the location of the page table

38、 in memory, the hardware including a register that points to the start of the page table, we call this the page table register(页表寄存器).术语及概念术语及概念虚拟存储器地址空间术语及概念虚拟存储器的管理方式替换算法快表TLB缓存-虚存一体化topic高速缓冲存储器内容虚拟存储器的管理方式段式虚拟存储器主存-辅存的信息传递的单位按程序段为单位进行管理段表：段基址、段长、装入位、访问方式（在内存中）段式虚拟存储器段式虚拟存储器段式虚拟存储器虚实地址转换段式虚拟存储器段式

39、虚拟存储器问题：主存空间及D道程序示意图段式虚拟存储器页式虚拟存储器主存-辅存的信息传递的单位以固定大小的页面为单位进行管理在页表中对应每一个虚页号有一个表目问题：页表过长页式虚拟存储器页式虚拟存储器虚实地址转换优点：按固定页长调入主存容易，空间浪费少缺点：页不是逻辑上独立实体，不易于多道程序共享及管理页表在主存中的地址由页表寄存器指出Page SizeLarger Pages Advantages Smaller page tables Fewer page faults and more efficient transfer with larger applications Improved TLB coverage Disadvantages Higher internal fragmentationSmaller Pages Advantages Improved time to start up small processes w