存儲(chǔ)器層次結(jié)構(gòu)

1、CSE431 Chapter 5A.1Irwin, PSU, 2008第五章：存儲(chǔ)器層次結(jié)構(gòu)第五章：存儲(chǔ)器層次結(jié)構(gòu)-BAdapted from Computer Organization and Design, 4th Edition, Patterson & Hennessy, 2008, MKCourtesy for Mary Jane Irwin of PSUReview: 一臺(tái)計(jì)算機(jī)的主要部件一臺(tái)計(jì)算機(jī)的主要部件 處理器處理器控制器控制器數(shù)據(jù)通路數(shù)據(jù)通路存儲(chǔ)器存儲(chǔ)器設(shè)備設(shè)備輸入輸入輸出輸出高速緩存高速緩存主存主存輔助存儲(chǔ)器輔助存儲(chǔ)器（硬盤）（硬盤）CSE431 Chapter

2、5A.3Irwin, PSU, 2008處理器處理器 存儲(chǔ)器存儲(chǔ)器 的性能差距的性能差距“Moores Law”Proc55%/year(2X/1.5yr)DRAM7%/year(2X/10yrs)Processor-MemoryPerformance Gap(grows 50%/year)CSE431 Chapter 5A.4Irwin, PSU, 2008The “Memory Wall”q處理器和DRAM的速度差異持續(xù)增加Clocks per instructionClocks per DRAM accessq良好的存儲(chǔ)器層次結(jié)構(gòu)（cache）設(shè)計(jì)對(duì)系統(tǒng)整體性能越來(lái)越重要存儲(chǔ)器層次結(jié)構(gòu)的

3、目標(biāo)存儲(chǔ)器層次結(jié)構(gòu)的目標(biāo)qFact: 容量大的存儲(chǔ)器速度慢，速度快的存儲(chǔ)器容量較小q我們?cè)趺磩?chuàng)建讓人感覺(jué)又大又便宜又快的存儲(chǔ)器？ (絕大部分時(shí)間是這樣)?l層次化l并行CSE431 Chapter 5A.6Irwin, PSU, 2008SecondLevelCache(SRAM)一種典型的存儲(chǔ)器層次結(jié)構(gòu)一種典型的存儲(chǔ)器層次結(jié)構(gòu)ControlDatapathSecondaryMemory(Disk)On-Chip ComponentsRegFileMainMemory(DRAM)DataCacheInstrCacheITLBDTLBSpeed (%cycles): s 1s 10s 100s

4、10,000sSize (bytes): 100s 10Ks Ms Gs Ts Cost: highest lowestq局部性原理的應(yīng)用和快速發(fā)展的技術(shù)使用戶能夠有越來(lái)越多、越來(lái)越快的存儲(chǔ)器可供使用。存儲(chǔ)器層次結(jié)構(gòu)技術(shù)存儲(chǔ)器層次結(jié)構(gòu)技術(shù)qCaches 由 SRAM 實(shí)現(xiàn)，追求速度和技術(shù)兼容性l快 (typical access times of 0.5 to 2.5 nsec)l低密度 (6 transistor cells)，高功率，價(jià)錢高 ($2000 to $5000 per GB in 2008)l靜態(tài): 內(nèi)容將會(huì)“永遠(yuǎn)存在” (只要不斷電)q主存由 DRAM 實(shí)現(xiàn)，追求容量 （大容

5、量）l更慢 (typical access times of 50 to 70 nsec) l高密度 (1 transistor cells)，低功率，價(jià)錢更低 ($20 to $75 per GB in 2008)l動(dòng)態(tài): 需要定期“刷新”(every 8 ms定期刷新)- 消耗1% to 2% DRAM 活動(dòng)周期l地址分為2半 (行和列)- RAS or Row Access Strobe（行地址） triggering the row decoder- CAS or Column Access Strobe （列地址）triggering the column selector存儲(chǔ)器層次

6、結(jié)構(gòu)存儲(chǔ)器層次結(jié)構(gòu): Why Does it Work?q時(shí)間局部性(locality in time)l如果某個(gè)數(shù)據(jù)項(xiàng)被訪問(wèn)，那么在不久的將來(lái)它可能再次被訪問(wèn)。 使最近被訪問(wèn)的數(shù)據(jù)項(xiàng)離處理器更近q空間局部性 (locality in space)l如果某個(gè)內(nèi)存區(qū)域的數(shù)據(jù)項(xiàng)被訪問(wèn)，那么在不久的將來(lái)，與它地址相鄰的數(shù)據(jù)項(xiàng)可能再次被訪問(wèn)。使包含連續(xù)字的內(nèi)存塊離處理器更近存儲(chǔ)器層次結(jié)構(gòu)的一些術(shù)語(yǔ)存儲(chǔ)器層次結(jié)構(gòu)的一些術(shù)語(yǔ)q塊或行(block or line): 可存在于或不存在于cache中的信息的最小單元q命中率(Hit Rate): 在高層存儲(chǔ)器中找到目標(biāo)數(shù)據(jù)的存儲(chǔ)訪問(wèn)比例l命中時(shí)間 Hit Ti

7、me: 訪問(wèn)某存儲(chǔ)器層次結(jié)構(gòu)所需要的時(shí)間，包括了判斷當(dāng)前訪問(wèn)是命中還是缺失所需的時(shí)間q缺失率(Miss Rate): 在高層存儲(chǔ)器中沒(méi)有找到目標(biāo)數(shù)據(jù)的存儲(chǔ)訪問(wèn)比例 1 - (Hit Rate)l缺失代價(jià) Miss Penalty: 將相應(yīng)的塊從低層存儲(chǔ)器替換到高層存儲(chǔ)器所需的時(shí)間，包括訪問(wèn)塊、將數(shù)據(jù)逐層傳輸、將數(shù)據(jù)插入發(fā)生缺失的層和將信息塊傳送給請(qǐng)求者的時(shí)間。命中時(shí)間 全局缺失率兩個(gè)機(jī)器的兩個(gè)機(jī)器的Cache參數(shù)參數(shù)Intel NehalemAMD BarcelonaL1 cache organization & sizeSplit I$ and D$; 32KB for each p

8、er core; 64B blocksSplit I$ and D$; 64KB for each per core; 64B blocksL1 associativity4-way (I), 8-way (D) set assoc.; LRU replacement2-way set assoc.; LRU replacementL1 write policywrite-back, write-allocatewrite-back, write-allocateL2 cache organization & sizeUnified; 256MB (0.25MB) per core;

9、64B blocksUnified; 512KB (0.5MB) per core; 64B blocksL2 associativity8-way set assoc.; LRU16-way set assoc.; LRUL2 write policywrite-backwrite-backL2 write policywrite-back, write-allocatewrite-back, write-allocateL3 cache organization & sizeUnified; 8192KB (8MB) shared by cores; 64B blocksUnifi

10、ed; 2048KB (2MB) shared by cores; 64B blocksL3 associativity16-way set assoc.32-way set assoc.; evict block shared by fewest coresL3 write policywrite-back, write-allocatewrite-back; write-allocate有限狀態(tài)機(jī)有限狀態(tài)機(jī)(FSM) Cache 控制器控制器q一個(gè)簡(jiǎn)單的一級(jí)cache的關(guān)鍵特征l直接映射l寫回機(jī)制采用寫分配策略l塊大小為4個(gè)字（16個(gè)字節(jié)）l cache大小為16KB(1024 個(gè)塊)l1

11、8位的標(biāo)記位，10位的cache索引位，2位的塊偏移位，2位的字節(jié)偏移位，如果是組相聯(lián)，還有重寫位，有效位，以及LRU位 Cache & Cache Controller 1-bit Read/WriteProcessorDDR SDRAM1-bit Valid32-bit address32-bit data32-bit data1-bit Ready1-bit Read/Write1-bit Valid32-bit address128-bit data128-bit data1-bit Ready四狀態(tài)四狀態(tài)Cache 控制器控制器空閑比較標(biāo)記如果有效且命中，那么 設(shè)置有效位和標(biāo)

12、記位；如果是寫操作，還要設(shè)置重寫位分配從主存讀取一個(gè)新的cache塊寫回將舊的cache塊寫回到主存Cache 命中標(biāo)識(shí)Cache 準(zhǔn)備就緒Cache 缺失，舊的Cache塊被重寫過(guò)主存準(zhǔn)備就緒主存準(zhǔn)備就緒主存沒(méi)有準(zhǔn)備就緒主存沒(méi)有準(zhǔn)備就緒Cache 缺失，舊的Cache塊沒(méi)有被重寫過(guò)有效的CPU 請(qǐng)求多多核核處理器處理器的的Cache一致性一致性q未來(lái)的多核處理器意味著單個(gè)芯片上有多個(gè)處理器，這些處理器可能會(huì)共享一個(gè)公共的物理地址空間，這就會(huì)引起cache一致性問(wèn)題Core 1Core 2L1 I$L1 D$Unified (shared) L2L1 I$L1 D$X = 0X = 0X =

13、0Read XRead XWrite 1 to XX = 1X = 1一個(gè)一致的存儲(chǔ)系統(tǒng)一個(gè)一致的存儲(chǔ)系統(tǒng)q在存儲(chǔ)器系統(tǒng)中讀取任何一個(gè)數(shù)據(jù)項(xiàng)的返回結(jié)果總是最近寫入的值l一致性 定義了讀操作可以返回什么樣的值- 對(duì)同一地址的寫操作是串行執(zhí)行的 (也就是說(shuō)，任何兩個(gè)處理器對(duì)同一地址的兩個(gè)寫操作在所有處理器看來(lái)都有相同的順序)l連貫性 定義了寫入的數(shù)據(jù)什么時(shí)候才能被讀操作返回q為了加強(qiáng)一致性，caches 必須提供l多核處理器cache共享數(shù)據(jù)的復(fù)制 l復(fù)制減少了訪問(wèn)延遲和讀取共享數(shù)據(jù)時(shí)的競(jìng)爭(zhēng)現(xiàn)象l本地cache共享數(shù)據(jù)的遷移l遷移不但減少了訪問(wèn)遠(yuǎn)程共享數(shù)據(jù)項(xiàng)的延遲，而且減少了對(duì)共享存儲(chǔ)器帶寬的需求

14、 (L2 in our example)Cache 一致性協(xié)議一致性協(xié)議q需要引入硬件協(xié)議來(lái)維護(hù)cache一致性，最常用的cache協(xié)議就是監(jiān)聽協(xié)議lCache可以通過(guò)一些廣播媒介（總線或者網(wǎng)絡(luò)）訪問(wèn)，所有的cache 控制器對(duì)媒介進(jìn)行監(jiān)視或者監(jiān)聽，來(lái)確定它們是否含有總線或者交換機(jī)上請(qǐng)求的數(shù)據(jù)塊副本q寫無(wú)效協(xié)議 寫操作時(shí)確保獨(dú)占訪問(wèn)并且令其他副本無(wú)效l獨(dú)占訪問(wèn)確保了寫執(zhí)行時(shí)不存在其他可讀或可寫的數(shù)據(jù)項(xiàng)副本q如果兩個(gè)處理器試圖同時(shí)對(duì)同一個(gè)數(shù)據(jù)進(jìn)行寫操作，它們中的一個(gè)會(huì)在競(jìng)爭(zhēng)中勝出，這使得另一個(gè)處理器的副本被置無(wú)效。競(jìng)爭(zhēng)失敗的處理器要完成寫操作，就必須取得新的數(shù)據(jù)副本，這個(gè)副本中必須包含了更新后的

15、數(shù)據(jù) 因此這個(gè)協(xié)議強(qiáng)制了寫操作的串行化。寫處理寫處理確保所有共享數(shù)據(jù)的其它處理器能被通知，并且對(duì)寫操作進(jìn)行下面兩種方式的處理：1.寫-更新 (寫-廣播) 執(zhí)行寫操作的處理器通過(guò)總線廣播新數(shù)據(jù)，所有的副本進(jìn)行更新lAll writes go to the bus higher bus traffic 加大總線通信量lSince new values appear in caches sooner, can reduce latency 降低延遲2.寫-無(wú)效 執(zhí)行寫操作的處理器發(fā)布無(wú)效信號(hào)到總線上，cache監(jiān)聽檢查它們是否有數(shù)據(jù)備份，如果有就使它們包含數(shù)據(jù)字的cache塊無(wú)效 (允許多個(gè)read

16、ers，但是只有一個(gè) writer)lUses the bus only on the first write lower bus traffic, so better use of bus bandwidth （降低總線通信量，更好地利用總線帶寬）監(jiān)聽無(wú)效的例子監(jiān)聽無(wú)效的例子qWhen the second miss by Core 2 occurs, Core 1 responds with the value canceling the response from the L2 cache (and also updating the L2 copy) Core 1Core 2L1 I$

17、L1 D$Unified (shared) L2L1 I$L1 D$X = 0X = 0X = 0Read XRead XWrite 1 to XX = 1 Read XX = IX = IX = 1X = 1A Write-Invalidate CC Protocol 寫寫無(wú)效一致性協(xié)議無(wú)效一致性協(xié)議Shared(clean)InvalidModified(dirty)write-back caching protocol in black read (miss)write hitread (hit or miss)read (hit) or write (hit)write (miss)

18、receives invalidate(write miss by another core to this block)Write miss or write-back due to read (miss) by another core to this blocksend invalidatesignals from the core in redsignals from the bus in blueCSE431 Chapter 5A.55Irwin, PSU, 2008數(shù)據(jù)缺失率數(shù)據(jù)缺失率q共享的數(shù)據(jù)具有較低的空間局部性和時(shí)間局部性l共享數(shù)據(jù)的缺失在cache行為中占很大比重，盡管它們

19、在數(shù)據(jù)訪問(wèn)中可能只占 10% - 40% 64KB 2-way set associative data cache with 32B blocksHennessy & Patterson, Computer Architecture: A Quantitative Approach塊塊大小的影響大小的影響q對(duì)多字塊中的某一個(gè)字進(jìn)行寫操作，意味著整個(gè)塊是無(wú)效的q多字塊(大塊)同樣會(huì)引起假共享: 當(dāng)兩個(gè)不相關(guān)的共享變量放在相同的cache塊中時(shí)，盡管每個(gè)處理器訪問(wèn)的是不同的變量，但是在處理器之間還是將整個(gè)塊進(jìn)行交換。l寫無(wú)效假共享會(huì)增加cache缺失率q編譯器可以通過(guò)將高度相關(guān)的數(shù)據(jù)分配

20、給同一cache塊來(lái)減少假共享ABCore1Core24 word cache block其它的一致性協(xié)議其它的一致性協(xié)議qcache 一致性協(xié)議有很多變化q用于Pentium 4 (以及其它處理器)中的寫-無(wú)效協(xié)議是4狀態(tài)的 MESI :lModified samelExclusive 只允許共享數(shù)據(jù)的一個(gè)備份被緩存; 存儲(chǔ)器中有一個(gè)最新的備份- 因?yàn)檫@只有塊的一個(gè)備份，所以寫命中是不需要發(fā)送無(wú)效信號(hào)lShared 共享數(shù)據(jù)的多個(gè)備份可能被緩存 (例如，數(shù)據(jù)允許被緩存到多個(gè)處理器上); 存儲(chǔ)器中有一個(gè)最新的備份lInvalid same 總結(jié)總結(jié):提高提高Cache的性能的性能0. 降低cache命中的時(shí)間l減小cache的容量l直接映射cachel