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

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

2、5A.3Irwin, PSU, 2008處理器處理器 存儲器存儲器 的性能差距的性能差距“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良好的存儲器層次結(jié)構(gòu)（cache）設(shè)計對系統(tǒng)整體性能越來越重要存儲器層次結(jié)構(gòu)的

3、目標存儲器層次結(jié)構(gòu)的目標qFact: 容量大的存儲器速度慢，速度快的存儲器容量較小q我們怎么創(chuàng)建讓人感覺又大又便宜又快的存儲器？ (絕大部分時間是這樣)?l層次化l并行CSE431 Chapter 5A.6Irwin, PSU, 2008SecondLevelCache(SRAM)一種典型的存儲器層次結(jié)構(gòu)一種典型的存儲器層次結(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ù)使用戶能夠有越來越多、越來越快的存儲器可供使用。存儲器層次結(jié)構(gòu)技術(shù)存儲器層次結(jié)構(gòu)技術(shù)qCaches 由 SRAM 實現(xiàn)，追求速度和技術(shù)兼容性l快 (typical access times of 0.5 to 2.5 nsec)l低密度 (6 transistor cells)，高功率，價錢高 ($2000 to $5000 per GB in 2008)l靜態(tài): 內(nèi)容將會“永遠存在” (只要不斷電)q主存由 DRAM 實現(xiàn)，追求容量 （大容

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

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

7、me: 訪問某存儲器層次結(jié)構(gòu)所需要的時間，包括了判斷當前訪問是命中還是缺失所需的時間q缺失率(Miss Rate): 在高層存儲器中沒有找到目標數(shù)據(jù)的存儲訪問比例 1 - (Hit Rate)l缺失代價 Miss Penalty: 將相應(yīng)的塊從低層存儲器替換到高層存儲器所需的時間，包括訪問塊、將數(shù)據(jù)逐層傳輸、將數(shù)據(jù)插入發(fā)生缺失的層和將信息塊傳送給請求者的時間。命中時間 全局缺失率兩個機器的兩個機器的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)機有限狀態(tài)機(FSM) Cache 控制器控制器q一個簡單的一級cache的關(guān)鍵特征l直接映射l寫回機制采用寫分配策略l塊大小為4個字（16個字節(jié)）l cache大小為16KB(1024 個塊)l1

11、8位的標記位，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 控制器控制器空閑比較標記如果有效且命中，那么 設(shè)置有效位和標

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

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

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

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

16、ers，但是只有一個 writer)lUses the bus only on the first write lower bus traffic, so better use of bus bandwidth （降低總線通信量，更好地利用總線帶寬）監(jiān)聽無效的例子監(jiān)聽無效的例子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 寫寫無效一致性協(xié)議無效一致性協(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ù)具有較低的空間局部性和時間局部性l共享數(shù)據(jù)的缺失在cache行為中占很大比重，盡管它們

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

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