計算機(jī)組成原理第5章緩存

1、存儲系統(tǒng)和結(jié)構(gòu)第五章 (/2) 緩存/虛存部分第5章存儲系統(tǒng)和結(jié)構(gòu)“緩存虛存部分”部分作業(yè)： 5-23, 5-25 , 5-26 , 5-27Homework存儲器部分內(nèi)容提要 存儲系統(tǒng)是由幾個容量、速度和價格各不相同的存儲器構(gòu)成的系統(tǒng)。設(shè)計一個容量大、速度快、成本低的存儲系統(tǒng)是計算機(jī)發(fā)展的一個重要課題。本章重點討論主存儲器的工作原理、組成方式以及運(yùn)用半導(dǎo)體存儲芯片組成主存儲器的一般原則和方法，此外還介紹了高速一主存儲器部分二.儲存體系結(jié)構(gòu)儲存體系結(jié)構(gòu)部分內(nèi)容提要二.儲存體系結(jié)構(gòu)儲存體系結(jié)構(gòu)概述高速緩沖存儲器虛擬存儲器儲存體系結(jié)構(gòu)部分內(nèi)容提要二.儲存體系結(jié)構(gòu)儲存體系結(jié)構(gòu)概述高速緩沖存儲器虛擬存

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

3、day, there are three primary technologies used in building memory hierarchies(目前有三種主要技術(shù)分別用于構(gòu)造“分級存儲器體系”) DRAM (dynamic random access memory)動態(tài)隨機(jī)訪問內(nèi)存，動態(tài)內(nèi)存: Main memory(主存) is implemented from DRAM.SRAM (static random access memory)靜態(tài)隨機(jī)訪問內(nèi)存，靜態(tài)內(nèi)存: 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儲存體系結(jié)構(gòu)概述Programs Have Locality 程序的局部性包括：時間局部性

5、和空間局部性。時間局部性是指如果一個存儲單元被訪問，則可能該單元會很快被再次訪問。這是因為程序存在著循環(huán)?？臻g局部性是指如果一個存儲單元被訪問，則該單元鄰近的單元也可能很快被訪問。這是因為程序中大部分指令是順序存儲、順序執(zhí)行的，數(shù)據(jù)一般也是以向量、數(shù)組、樹、表等形式簇聚地存儲在一起的。 高速緩沖技術(shù)就是利用程序的局部性原理，把程序中經(jīng)常使用的部分存放在速度較高容量較小的存儲器中，從而實現(xiàn)存儲的層次化結(jié)構(gòu)，使整體的存儲速度接近最快的存儲體速度，容量接近最大的存儲體容量。Example-1: Most programs contain loops(循環(huán)), 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(順序執(zhí)行), 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(數(shù)組) or a record will naturally have high degrees of spatial locality.儲存體系結(jié)構(gòu)概述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儲存體系結(jié)構(gòu)概述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?儲存體系結(jié)構(gòu)概述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)儲存體系結(jié)構(gòu)概述儲存體系結(jié)構(gòu)部分內(nèi)容提要二.儲存體系結(jié)構(gòu)儲存體系結(jié)構(gòu)概述高速緩沖存儲器虛擬存儲器

11、高速緩沖存儲器Memory Hierarchy高速緩沖存儲器cache main memoryby the cache controller hardware 高速緩沖技術(shù)就是利用程序的局部性原理，把程序中正在使用的部分存放在一個高速的容量較小的Cache中，使CPU的訪存操作大多數(shù)針對Cache進(jìn)行，從而使程序的執(zhí)行速度大大提高。高速緩沖存儲器Cache的基本結(jié)構(gòu) Cache和主存都被分成若干個大小相等的塊，每塊由若干字節(jié)組成。由于Cache的容量遠(yuǎn)小于主存的容量，它保存的信息只是主存中最活躍的若干塊的副本。 Cache的工作流程Cache的讀操作：CPU送出主存（大）地址，如果Cache命

12、中，此大地址變成Cache（小）地址并送Cache對其進(jìn)行讀操作，與主存無關(guān)；如果Cache不命中，則仍需訪問主存，并把該塊信息一次從主存調(diào)入Cache內(nèi)。若此時Cache已滿，則須根據(jù)某種替換算法，用這個塊替換掉Cache中原來的某塊信息。 Cache的寫操作：當(dāng)CPU發(fā)出寫請求時，如果Cache命中，有可能會遇到Cache與主存中的內(nèi)容不一致的問題，需要進(jìn)行一定的寫處理，處理的方法有：寫直達(dá)法和寫回法。ProcessorData are transferred術(shù)語及概念Cache與主存的地址映象替換算法更新策略Cache的性能topic高速緩沖存儲器內(nèi)容術(shù)語及概念Cache與主存的地址映象

13、替換算法更新策略Cache的性能topic高速緩沖存儲器內(nèi)容術(shù)語及概念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術(shù)語及概念TerminologyHit(命中):如果處理器需要的數(shù)據(jù)出現(xiàn)在

14、高層的某個塊里，稱之為一次命中Hit Rate (命中率) :在高速緩存中找到目標(biāo)數(shù)據(jù)的存儲訪問比例Hit Time (命中時間): 訪問存儲器某層所需要時間包括判斷訪問是否命中所需要的時間Miss(缺失):如果處理器需要的數(shù)據(jù)在高層找不到，稱之為一次缺失Miss Rate (缺失率): =在高速緩存中找不到目標(biāo)數(shù)據(jù)的存儲訪問比例 Miss Rate =1 - (Hit Rate)Miss Penalty(缺失損失) : 從底層將塊取入該層所需要的時間包括訪問 塊，逐層向上傳送塊直至數(shù)據(jù)放入需要層所需時間Hit Time Miss PenaltyHopefully hit time is lo

15、w and miss rate is low術(shù)語及概念Terminology單級Cache二級Cache片內(nèi)Cache（L1）和片外Cache（L2）統(tǒng)一Cache和分立Cache統(tǒng)一Cache：用一個Cache存放指令和數(shù)據(jù)分立Cache：指令和數(shù)據(jù)存放在不同的Cache中。（指令和數(shù)據(jù)分別用2個獨立的cache）術(shù)語及概念具有Cache的存儲器，其平均存取時間計算如下： 平均存取時間=htc+(1-h)(tc+tM) =tc+tM (1-h)其中： tc為Cache的存取時間 h為命中率 tM為主存的存取時間假設(shè)主存儲器的大小為2n個字節(jié)，共分成2m個塊，每個塊的大小為2b個字節(jié)，則：n=

16、m+b 主存地址結(jié)構(gòu)如下：Cache-主存之間的關(guān)系術(shù)語及概念假設(shè)Cache中有2c個塊，每個塊的大小為2b個字節(jié)，則Cache的大小為2c+b個字節(jié)，則： Cache地址結(jié)構(gòu)如下：Cache-主存之間的關(guān)系術(shù)語及概念術(shù)語及概念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. 術(shù)語及概念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.術(shù)語及概念Cache 工作原理處理cache缺失topic高速緩沖存儲器內(nèi)容術(shù)語及概念Cache與主存的地址映象替換算法更新策略Cache的性能Cache與主存的地址映象 直接映像地址映象與變換把主存的每一塊映射到一個固定的Cache槽中，j=i mod 2c 其中j為Cache槽號，i為主存的塊號， 2c為Cache的槽數(shù)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地址映象與變換地址映象與變換例： 全相聯(lián)映像地址映象與變換通過允許每個主存塊裝入到C

22、ache的任何一槽中來克服直接映射的缺點 全相聯(lián)映像電路地址映象與變換優(yōu)點：Cache利用率高缺點：效率不高N = 區(qū)內(nèi)塊數(shù)，陰影區(qū)表示查找范圍地址映象與變換例： 組相聯(lián)映像地址映象與變換上述兩種方案的折中。把Cache分成若干組，每組有若干塊，組間為直接映像，組內(nèi)字塊為全相聯(lián)映像方式Cache index selects a “set ”The two tags in the set are compared in parallelData is selected based on the tag全相聯(lián)映像電路（路）地址映象與變換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全相聯(lián)映像電路（路）地址映象與變換設(shè)有8個塊，分成2個組例：地址映象與變換topic高速緩沖存儲器內(nèi)容術(shù)語及概念Cache與主存的地址映象替換算法更新策略Cache的性能替換算法塊的替換算法替換

24、策略：隨機(jī)法RAND算法先進(jìn)先出法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塊的替換算法先進(jìn)先出法FIFO算法顛簸現(xiàn)象塊的替換算法通過替換登記表實現(xiàn)塊的替換算法LRU（最近最少使用: Least Recently Used ）算法 topic高速緩沖存儲器內(nèi)容術(shù)語及概念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的一致性問題對數(shù)據(jù)Cache而言，由于有多種寫方式，且有多級Cache，因此在修改Cache中的數(shù)據(jù)時，會造成主存儲器和Cache中的數(shù)據(jù)不一致。更新策略當(dāng)系統(tǒng)中存在多個Cache時，解決多個Cache中數(shù)據(jù)的一致性問題的方法：總線監(jiān)視法硬件監(jiān)視法劃出不可高速緩存存儲區(qū)法Pentium處理器中支持“修改/排它/共享/無效”(Modify/exclusive/shared/invalid)簡稱MESI協(xié)議。這樣，Cache中的狀態(tài)位為2位，表示4中狀態(tài)之一。topic

33、高速緩沖存儲器內(nèi)容術(shù)語及概念Cache與主存的地址映象替換算法更新策略Cache的性能cache的性能cache的命中率與cache容量的關(guān)系塊容量與命中率cache的性能地址映象與命中率Cache的相聯(lián)性與失效率cache的性能儲存體系結(jié)構(gòu)部分內(nèi)容提要二.儲存體系結(jié)構(gòu)儲存體系結(jié)構(gòu)概述高速緩沖存儲器虛擬存儲器虛擬存儲器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) 虛擬存儲器指的是“主存-輔存”層次，它能使計算機(jī)具有輔存的容量，接近于主存的速度和輔存的每位成本。使程序員可以按比主存大得多的空間來編制程序，即按虛存空間編址。虛擬存儲器兩種存儲層次的比較區(qū)別： 主存/cache的訪問“時間比”較小，典型為10：1。每次傳送的基本信息單元較小(字塊),幾個至幾十個字節(jié)。 輔存/主存的訪問“時間比”達(dá)100:1至1000:1。每次傳送的基本信息單元較大(段或頁),幾十至幾千字節(jié)。相同： 它們采用的地址變換及映像方法和替換策略，從原理上看是相同的。topic虛擬存儲器內(nèi)容術(shù)語及概念虛擬存儲器的管理方式替換

35、算法快表TLB緩存-虛存一體化術(shù)語及概念虛擬存儲器的管理方式替換算法快表TLB緩存-虛存一體化topic高速緩沖存儲器內(nèi)容術(shù)語及概念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(頁表)：虛頁到實頁轉(zhuǎn)換索引表基本術(shù)語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(頁表寄存器).術(shù)語及概念術(shù)語及概念虛擬存儲器地址空間術(shù)語及概念虛擬存儲器的管理方式替換算法快表TLB緩存-虛存一體化topic高速緩沖存儲器內(nèi)容虛擬存儲器的管理方式段式虛擬存儲器主存-輔存的信息傳遞的單位按程序段為單位進(jìn)行管理段表：段基址、段長、裝入位、訪問方式（在內(nèi)存中）段式虛擬存儲器段式虛擬存儲器段式虛擬存儲器虛實地址轉(zhuǎn)換段式虛擬存儲器段式

39、虛擬存儲器問題：主存空間及D道程序示意圖段式虛擬存儲器頁式虛擬存儲器主存-輔存的信息傳遞的單位以固定大小的頁面為單位進(jìn)行管理在頁表中對應(yīng)每一個虛頁號有一個表目問題：頁表過長頁式虛擬存儲器頁式虛擬存儲器虛實地址轉(zhuǎn)換優(yōu)點：按固定頁長調(diào)入主存容易，空間浪費少缺點：頁不是邏輯上獨立實體，不易于多道程序共享及管理頁表在主存中的地址由頁表寄存器指出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