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

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

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

當(dāng)替換算法要驅(qū)逐已更新塊時(shí) 增加了復(fù)雜性寫不命中(writemiss)寫分配(write-allocate)

加載存儲塊到緩存非寫分配(not-write-allocate)第30頁，課件共43頁，創(chuàng)作于2023年2月高速緩存性能參數(shù)不命中率(missrate)不命中數(shù)量/引用數(shù)量命中率(hitrate)命中時(shí)間(hittime)L1:1~2個(gè)時(shí)鐘周期不命中處罰(misspenalty)L2:5~10個(gè)周期主存:25~100個(gè)周期第31頁，課件共43頁，創(chuàng)作于2023年2月高速緩存參數(shù)的性能影響高速緩存大小命中率，命中時(shí)間塊大小空間局部性，時(shí)間局部性，不命中處罰相聯(lián)度沖突不命中，命中時(shí)間，成本寫策略高速緩存越往下層，越可能使用寫回而不是直寫第32頁，課件共43頁，創(chuàng)作于2023年2月提綱導(dǎo)論存儲技術(shù)局部性原理存儲器層次結(jié)構(gòu)高速緩存存儲器編寫高速緩存友好的代碼利用程序中的局部性第33頁，課件共43頁，創(chuàng)作于2023年2月編寫高速緩存友好(cachefriendly)的代碼局部性比較好的程序更低的不命中率運(yùn)行的更快基本方法讓最常見的情況運(yùn)行得更快在每個(gè)循環(huán)內(nèi)部使緩存不命中數(shù)量最小對局部變量的反復(fù)引用步長為1的應(yīng)用模式第34頁，課件共43頁，創(chuàng)作于2023年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頁，創(chuàng)作于2023年2月重新排列循環(huán)以提高空間局部性NxN矩陣相乘問題三個(gè)嵌套循環(huán)，六個(gè)版本對于性能來說，高速緩存命中率是個(gè)關(guān)鍵問題，但存儲器訪問次數(shù)也很重要。第36頁，課件共43頁，創(chuàng)作于2023年2月使用分塊來提高時(shí)間局部性分塊(blocking)分塊的大致思想是將一個(gè)程序中的數(shù)據(jù)結(jié)構(gòu)組織成塊，使得能夠?qū)⒁粋€(gè)塊加載到L1高速緩存中，并在這個(gè)塊中進(jìn)行所需要的所有的讀和寫，然后丟掉這個(gè)塊，加載下一個(gè)塊，依此類推。增強(qiáng)時(shí)間局部性減少容量不命中第37頁，課件共43頁，創(chuàng)作于2023年2月分塊矩陣乘法第38頁，課件共43頁，創(chuàng)作于2023年2月提綱導(dǎo)論存儲技術(shù)局部性原理存儲器層次結(jié)構(gòu)高速緩存存儲器編寫高速緩存友好的代碼利用程序中的局部性第39頁，課件共43頁，創(chuàng)作于2023年2月在程序中利用局部性-小結(jié)將你的注意力集中在內(nèi)部循環(huán)上，大部分計(jì)算和存儲器訪問都發(fā)生在這里通過按照數(shù)據(jù)對象存儲順序來讀數(shù)據(jù)，從而使程序的空間局部性最大一旦從存儲器中讀入了一個(gè)數(shù)據(jù)對象，就盡可能地使用它，