存儲器層次結構

關于存儲器層次結構第1頁，講稿共43頁，2023年5月2日，星期三提綱導論存儲技術局部性原理存儲器層次結構高速緩存存儲器編寫高速緩存友好的代碼利用程序中的局部性第2頁，講稿共43頁，2023年5月2日，星期三存儲器(memory)系統(tǒng)VonNeumann一個線性的字節(jié)數組，CPU能夠在一個常數時間內訪問每個存儲器位置實際一個具有不同容量、成本和訪問時間的存儲(storage)設備層次結構第3頁，講稿共43頁，2023年5月2日，星期三存儲器層次結構CPUregisterLatency:0cycleCachememory(L1,L2,…)Latency:1-10cycleMainmemoryLatency:50-100cycleDiskstorageLatency:20000000cycleNetworkstorage第4頁，講稿共43頁，2023年5月2日，星期三計算機程序的局部性(locality)良好局部性的程序重復訪問相同的數據項集合傾向于訪問臨近的數據項集合優(yōu)化思想使程序要訪問的數據項存儲在層次結構中較高的地方，在那里CPU能更快的訪問到它們。第5頁，講稿共43頁，2023年5月2日，星期三提綱導論存儲技術局部性原理存儲器層次結構高速緩存存儲器編寫高速緩存友好的代碼利用程序中的局部性第6頁，講稿共43頁，2023年5月2日，星期三隨機訪問存儲器(RAM)SRAMDRAM描述靜態(tài)RAM動態(tài)RAM每位晶體管數61相對訪問時間1X10X持續(xù)的?(刷新)YesNo敏感的?(光電)NoYes相對花費100X1X應用高速緩存主存第7頁，講稿共43頁，2023年5月2日，星期三訪問主存典型的連接CPU和主存的總線結構第8頁，講稿共43頁，2023年5月2日，星期三磁盤存儲第9頁，講稿共43頁，2023年5月2日，星期三提綱導論存儲技術局部性原理存儲器層次結構高速緩存存儲器編寫高速緩存友好的代碼利用程序中的局部性第10頁，講稿共43頁，2023年5月2日，星期三局部性時間局部性(temporallocality)被引用過一次的存儲器位置很可能在不遠的將來再被多次引用空間局部性(spatiallocality)如果一個存儲器位置被引用了一次，那么程序很可能在不遠的將來引用附近的一個存儲器位置第11頁，講稿共43頁，2023年5月2日，星期三局部性有良好局部性的程序運行更快計算機系統(tǒng)的各個層次都利用了局部性Cache主存作為虛擬地址空間最近被應用塊的高速緩存緩存磁盤文件系統(tǒng)最近使用的磁盤塊Web瀏覽器將最近被引用的文檔放在本地磁盤上Web服務器將最近被請求的文檔放在前端磁盤高速緩存中第12頁，講稿共43頁，2023年5月2日，星期三對程序數據引用的局部性intsumvec(intv[N]){ inti,sum=0; for(i=0;i<N;i++) sum+=v[i]; returnsum;}變量sum：時間局部性向量v：空間局部性第13頁，講稿共43頁，2023年5月2日，星期三對程序數據引用的局部性函數sumvec順序訪問一個向量的每個元素，具有步長為1的引用模式步長為k的引用模式 (stride-kreferencepattern)訪問一個連續(xù)向量的每第k個元素隨著步長的增加，空間局部性下降第14頁，講稿共43頁，2023年5月2日，星期三引用多維數組intsumarraycols(inta[M][N]){ inti,j,sum=0; for(j=0;j<N;j++) for(i=0;i<M;i++) sum+=a[i][j]; returnsum}按列優(yōu)先順序訪問(col-majororder)步長為N局部性差第15頁，講稿共43頁，2023年5月2日，星期三引用多維數組intsumarrayrows(inta[M][N]){ inti,j,sum=0; for(i=0;i<M;i++) for(j=0;j<N;j++) sum+=a[i][j]; returnsum}按行優(yōu)先順序訪問(row-majororder)步長為1局部性好第16頁，講稿共43頁，2023年5月2日，星期三局部性小結重復引用同一個變量的程序有良好的時間局部性對于具有步長為k的引用模式的程序，步長越小，空間局部性越好對于取指令來說，循環(huán)有好的時間和空間局部性。循環(huán)體越小，循環(huán)迭代次數越多，局部性越好第17頁，講稿共43頁，2023年5月2日，星期三提綱導論存儲技術局部性原理存儲器層次結構高速緩存存儲器編寫高速緩存友好的代碼利用程序中的局部性第18頁，講稿共43頁，2023年5月2日，星期三存儲器層次結構(memoryhierarchy)第19頁，講稿共43頁，2023年5月2日，星期三存儲器層次結構中的緩存高速緩存(cache)一個小而快速的存儲設備作為存儲在更大也更慢的設備中的數據對象的緩沖區(qū)域存儲器層次結構的中心思想位于k層的更快更小的存儲設備作為位于k+1層的更大更慢的存儲設備的緩存第20頁，講稿共43頁，2023年5月2日，星期三存儲器層次結構中的數據傳輸第21頁，講稿共43頁，2023年5月2日，星期三緩存命中當程序需要第k+1層的某個數據對象d時，它首先在當前存儲在第k層的一個塊中查找d。如果d剛好緩存在第k層中，那么就是我們所說的緩存命中(cachehit)。該程序直接從第k層讀取d，根據存儲器層次結構的性質，這要比從第k+1層讀取d更快。第22頁，講稿共43頁，2023年5月2日，星期三緩存不命中如果第k層中沒有緩存數據對象d，那么就是我們所說的緩存不命中(cachemiss)。當發(fā)生cachemiss時，第k層的緩存從第k+1層中取出包含d的那個塊。如果第k層的緩存已經滿了的話，可能就會覆蓋現存的一個塊，由緩存的替換策略來控制。第23頁，講稿共43頁，2023年5月2日，星期三緩存不命中的種類冷不命中(coldmiss)warmedup之前容量不命中(capacitymiss)workingset沖突不命中(conflictmiss)限制性的塊放置策略第24頁，講稿共43頁，2023年5月2日，星期三高速緩存管理寄存器編譯器L1,L2cache內置在緩存中的硬件邏輯DRAM主存操作系統(tǒng)軟件和CPU上的地址翻譯硬件本地磁盤緩存網絡存儲應用程序第25頁，講稿共43頁，2023年5月2日，星期三提綱導論存儲技術局部性原理存儲器層次結構高速緩存存儲器編寫高速緩存友好的代碼利用程序中的局部性第26頁，講稿共43頁，2023年5月2日，星期三高速緩存存儲器基于L1和L2高速緩存的典型總線結構第27頁，講稿共43頁，2023年5月2日，星期三高速緩存存儲器直接映射高速緩存(direct-mappedcache)機制比較簡單沖突不命中全相聯高速緩存(fullyassociativecache)成本高，容量小虛擬存儲系統(tǒng)翻譯備用緩沖器(TLB)組相聯高速緩存 (setassociativecache)第28頁，講稿共43頁，2023年5月2日，星期三高速緩存替換策略隨機選擇最不常使用 (least-frequently-used,LFU)替換在過去某個時間窗口內引用次數最少的那一行最近最少使用 (least-recently-used,LRU)替換最后一次訪問時間最久遠的那一行第29頁，講稿共43頁，2023年5月2日，星期三寫操作讀操作–很簡單寫操作–較復雜寫命中(writehit)直寫(write-through)

立即寫到存儲器中 增加了總線上的寫事務寫回(write-back)

當替換算法要驅逐已更新塊時 增加了復雜性寫不命中(writemiss)寫分配(write-allocate)

加載存儲塊到緩存非寫分配(not-write-allocate)第30頁，講稿共43頁，2023年5月2日，星期三高速緩存性能參數不命中率(missrate)不命中數量/引用數量命中率(hitrate)命中時間(hittime)L1:1~2個時鐘周期不命中處罰(misspenalty)L2:5~10個周期主存:25~100個周期第31頁，講稿共43頁，2023年5月2日，星期三高速緩存參數的性能影響高速緩存大小命中率，命中時間塊大小空間局部性，時間局部性，不命中處罰相聯度沖突不命中，命中時間，成本寫策略高速緩存越往下層，越可能使用寫回而不是直寫第32頁，講稿共43頁，2023年5月2日，星期三提綱導論存儲技術局部性原理存儲器層次結構高速緩存存儲器編寫高速緩存友好的代碼利用程序中的局部性第33頁，講稿共43頁，2023年5月2日，星期三編寫高速緩存友好(cachefriendly)的代碼局部性比較好的程序更低的不命中率運行的更快基本方法讓最常見的情況運行得更快在每個循環(huán)內部使緩存不命中數量最小對局部變量的反復引用步長為1的應用模式第34頁，講稿共43頁，2023年5月2日，星期三測量讀帶寬voidtest(intelems,intstride){ inti,result=0; volatileintsink; for(i=0;i<elems;i+=stride) result+=data[i]; sink=result;}doublerun(intsize,intstride,doubleMhz){ doublecycles; intelems=size/sizeof(int); test(elems,stride); cycles=fcyc2(test,elems,stride,0); return(size/stride)/(cycles/Mhz);}第35頁，講稿共43頁，2023年5月2日，星期三重新排列循環(huán)以提高空間局部性NxN矩陣相乘問題三個嵌套循環(huán)，六個版本對于性能來說，高速緩存命中率是個關鍵問題，但存儲器訪問次數也很重要。第36頁，講稿共43頁，2023年5月2日，星期三使用分塊來提高時間局部性分塊(blocking)分塊的大致思想是將一個程序中的數據結構組織成塊，使得能夠將一個塊加載到L1高速緩存中，并在這個塊中進行所需要的所有的讀和寫，然后丟掉這個塊，加載下一個塊，依此類推。增強時間局部性減少容量不命中第37頁，講稿共43頁，2023年5月2日，星期三分塊矩陣乘法第38頁，講稿共43頁，2023年5月2日，星期三提綱導論存儲技術局部性原理存儲器層次結構高速緩存存儲器編寫高速緩存友好的代碼利用程序中的局部性第39頁，講稿共43頁，2023年5月2日，星期三在程序中利用局部性-小結將你的注意力集中在內部循環(huán)上，大部分計算和存儲器訪問都發(fā)生在這里通過按照數據對象存儲順序來讀數據，從而使程序的空間局部性最大一旦從存儲器中讀入了一個數據對象，就盡可能地使用它，從而使程序的