1、存儲器層次結構第1頁，共42頁，2022年，5月20日，16點4分，星期二提綱導論存儲技術局部性原理存儲器層次結構高速緩存存儲器編寫高速緩存友好的代碼利用程序中的局部性第2頁，共42頁，2022年，5月20日，16點4分，星期二存儲器(memory)系統(tǒng)Von Neumann一個線性的字節(jié)數(shù)組，CPU能夠在一個常數(shù)時間內(nèi)訪問每個存儲器位置實際一個具有不同容量、成本和訪問時間的存儲(storage)設備層次結構第3頁，共42頁，2022年，5月20日，16點4分，星期二存儲器層次結構CPU registerLatency: 0 cycleCache memory (L1, L2, )Latenc

2、y: 1-10 cycleMain memoryLatency: 50-100 cycleDisk storageLatency: 20 000 000 cycleNetwork storage第4頁，共42頁，2022年，5月20日，16點4分，星期二計算機程序的局部性(locality)良好局部性的程序重復訪問相同的數(shù)據(jù)項集合傾向于訪問臨近的數(shù)據(jù)項集合優(yōu)化思想使程序要訪問的數(shù)據(jù)項存儲在層次結構中較高的地方，在那里CPU能更快的訪問到它們。第5頁，共42頁，2022年，5月20日，16點4分，星期二提綱導論存儲技術局部性原理存儲器層次結構高速緩存存儲器編寫高速緩存友好的代碼利用程序中的局部性

3、第6頁，共42頁，2022年，5月20日，16點4分，星期二隨機訪問存儲器(RAM)SRAMDRAM描述靜態(tài)RAM動態(tài)RAM每位晶體管數(shù)61相對訪問時間1X10X持續(xù)的?(刷新)YesNo敏感的?(光電)NoYes相對花費100X1X應用高速緩存主存第7頁，共42頁，2022年，5月20日，16點4分，星期二訪問主存典型的連接CPU和主存的總線結構第8頁，共42頁，2022年，5月20日，16點4分，星期二磁盤存儲第9頁，共42頁，2022年，5月20日，16點4分，星期二提綱導論存儲技術局部性原理存儲器層次結構高速緩存存儲器編寫高速緩存友好的代碼利用程序中的局部性第10頁，共42頁，2022

4、年，5月20日，16點4分，星期二局部性時間局部性(temporal locality)被引用過一次的存儲器位置很可能在不遠的將來再被多次引用空間局部性(spatial locality)如果一個存儲器位置被引用了一次，那么程序很可能在不遠的將來引用附近的一個存儲器位置第11頁，共42頁，2022年，5月20日，16點4分，星期二局部性有良好局部性的程序運行更快計算機系統(tǒng)的各個層次都利用了局部性Cache主存作為虛擬地址空間最近被應用塊的高速緩存緩存磁盤文件系統(tǒng)最近使用的磁盤塊Web瀏覽器將最近被引用的文檔放在本地磁盤上Web服務器將最近被請求的文檔放在前端磁盤高速緩存中第12頁，共42頁，2

5、022年，5月20日，16點4分，星期二對程序數(shù)據(jù)引用的局部性int sumvec(int vN)int i, sum = 0;for(i=0;iN;i+)sum += vi;return sum;變量sum：時間局部性向量v ：空間局部性第13頁，共42頁，2022年，5月20日，16點4分，星期二對程序數(shù)據(jù)引用的局部性函數(shù)sumvec順序訪問一個向量的每個元素，具有步長為1的引用模式步長為k的引用模式(stride-k reference pattern)訪問一個連續(xù)向量的每第k個元素隨著步長的增加，空間局部性下降第14頁，共42頁，2022年，5月20日，16點4分，星期二引用多維數(shù)組i

6、nt sumarraycols(int aMN)int i,j,sum = 0;for(j=0;jN;j+)for(i=0;iM;i+)sum += aij;return sum按列優(yōu)先順序訪問(col-major order)步長為N局部性差第15頁，共42頁，2022年，5月20日，16點4分，星期二引用多維數(shù)組int sumarrayrows(int aMN)int i,j,sum = 0;for(i=0;iM;i+)for(j=0;jN;j+)sum += aij;return sum按行優(yōu)先順序訪問(row-major order)步長為1局部性好第16頁，共42頁，2022年，5月

7、20日，16點4分，星期二局部性小結重復引用同一個變量的程序有良好的時間局部性對于具有步長為k的引用模式的程序，步長越小，空間局部性越好對于取指令來說，循環(huán)有好的時間和空間局部性。循環(huán)體越小，循環(huán)迭代次數(shù)越多，局部性越好第17頁，共42頁，2022年，5月20日，16點4分，星期二提綱導論存儲技術局部性原理存儲器層次結構高速緩存存儲器編寫高速緩存友好的代碼利用程序中的局部性第18頁，共42頁，2022年，5月20日，16點4分，星期二存儲器層次結構(memory hierarchy)第19頁，共42頁，2022年，5月20日，16點4分，星期二存儲器層次結構中的緩存高速緩存(cache)一個小

8、而快速的存儲設備作為存儲在更大也更慢的設備中的數(shù)據(jù)對象的緩沖區(qū)域存儲器層次結構的中心思想位于k層的更快更小的存儲設備作為位于k+1層的更大更慢的存儲設備的緩存第20頁，共42頁，2022年，5月20日，16點4分，星期二存儲器層次結構中的數(shù)據(jù)傳輸?shù)?1頁，共42頁，2022年，5月20日，16點4分，星期二緩存命中當程序需要第k+1層的某個數(shù)據(jù)對象d時，它首先在當前存儲在第k層的一個塊中查找d。如果d剛好緩存在第k層中，那么就是我們所說的緩存命中(cache hit)。該程序直接從第k層讀取d，根據(jù)存儲器層次結構的性質(zhì)，這要比從第k+1層讀取d更快。第22頁，共42頁，2022年，5月20日，

9、16點4分，星期二緩存不命中如果第k層中沒有緩存數(shù)據(jù)對象d，那么就是我們所說的緩存不命中(cache miss)。當發(fā)生cache miss時，第k層的緩存從第k+1層中取出包含d的那個塊。如果第k層的緩存已經(jīng)滿了的話，可能就會覆蓋現(xiàn)存的一個塊，由緩存的替換策略來控制。第23頁，共42頁，2022年，5月20日，16點4分，星期二緩存不命中的種類冷不命中(cold miss)warmed up之前容量不命中(capacity miss)working set沖突不命中(conflict miss)限制性的塊放置策略第24頁，共42頁，2022年，5月20日，16點4分，星期二高速緩存管理寄存器

10、編譯器L1,L2 cache內(nèi)置在緩存中的硬件邏輯DRAM 主存操作系統(tǒng)軟件和CPU上的地址翻譯硬件本地磁盤緩存網(wǎng)絡存儲應用程序第25頁，共42頁，2022年，5月20日，16點4分，星期二提綱導論存儲技術局部性原理存儲器層次結構高速緩存存儲器編寫高速緩存友好的代碼利用程序中的局部性第26頁，共42頁，2022年，5月20日，16點4分，星期二高速緩存存儲器基于L1和L2高速緩存的典型總線結構第27頁，共42頁，2022年，5月20日，16點4分，星期二高速緩存存儲器直接映射高速緩存(direct-mapped cache)機制比較簡單沖突不命中全相聯(lián)高速緩存(fully associativ

11、e cache)成本高，容量小虛擬存儲系統(tǒng)翻譯備用緩沖器(TLB)組相聯(lián)高速緩存 (set associative cache)第28頁，共42頁，2022年，5月20日，16點4分，星期二高速緩存替換策略隨機選擇最不常使用(least-frequently-used, LFU)替換在過去某個時間窗口內(nèi)引用次數(shù)最少的那一行最近最少使用(least-recently-used, LRU)替換最后一次訪問時間最久遠的那一行第29頁，共42頁，2022年，5月20日，16點4分，星期二寫操作讀操作 很簡單寫操作 較復雜寫命中(write hit)直寫(write-through)立即寫到存儲器中增加

12、了總線上的寫事務寫回(write-back)當替換算法要驅(qū)逐已更新塊時增加了復雜性寫不命中(write miss)寫分配(write-allocate)加載存儲塊到緩存非寫分配(not-write-allocate)第30頁，共42頁，2022年，5月20日，16點4分，星期二高速緩存性能參數(shù)不命中率(miss rate)不命中數(shù)量/引用數(shù)量命中率(hit rate)命中時間(hit time)L1 : 12個時鐘周期不命中處罰(miss penalty)L2 : 510個周期主存 : 25100個周期第31頁，共42頁，2022年，5月20日，16點4分，星期二高速緩存參數(shù)的性能影響高速緩存

13、大小命中率，命中時間塊大小空間局部性，時間局部性，不命中處罰相聯(lián)度沖突不命中，命中時間，成本寫策略高速緩存越往下層，越可能使用寫回而不是直寫第32頁，共42頁，2022年，5月20日，16點4分，星期二提綱導論存儲技術局部性原理存儲器層次結構高速緩存存儲器編寫高速緩存友好的代碼利用程序中的局部性第33頁，共42頁，2022年，5月20日，16點4分，星期二編寫高速緩存友好(cache friendly)的代碼局部性比較好的程序更低的不命中率運行的更快基本方法讓最常見的情況運行得更快在每個循環(huán)內(nèi)部使緩存不命中數(shù)量最小對局部變量的反復引用步長為1的應用模式第34頁，共42頁，2022年，5月20日

14、，16點4分，星期二測量讀帶寬void test(int elems, int stride)int i, result = 0;volatile int sink;for(i=0;ielems;i+=stride)result += datai;sink = result;double run(int size,int stride, double Mhz)double cycles;int elems = size / sizeof(int);test(elems, stride);cycles = fcyc2(test,elems,stride,0);return (size/strid

15、e)/(cycles/Mhz);第35頁，共42頁，2022年，5月20日，16點4分，星期二重新排列循環(huán)以提高空間局部性NxN矩陣相乘問題三個嵌套循環(huán)，六個版本對于性能來說，高速緩存命中率是個關鍵問題，但存儲器訪問次數(shù)也很重要。第36頁，共42頁，2022年，5月20日，16點4分，星期二使用分塊來提高時間局部性分塊(blocking)分塊的大致思想是將一個程序中的數(shù)據(jù)結構組織成塊，使得能夠?qū)⒁粋€塊加載到L1高速緩存中，并在這個塊中進行所需要的所有的讀和寫，然后丟掉這個塊，加載下一個塊，依此類推。增強時間局部性減少容量不命中第37頁，共42頁，2022年，5月20日，16點4分，星期二分塊矩陣乘法第38頁，共42頁，2022年，5月20日，16點4分，星期二提綱導論存儲技術局部性原理存儲器層次結構高速緩存存儲器編寫高速緩存友好的代碼利用程序中的局部性第39頁，共42頁，2022年，5月20日，16點4分，星期二在程序中利用局部性-小結將你的注意力集中在內(nèi)部循環(huán)上，大部分計算和存儲器訪問都發(fā)生在這里通過按照數(shù)據(jù)對象存儲順序來讀數(shù)據(jù)，從而使程序的空間局部性最大一旦從存儲器中讀入了一個數(shù)據(jù)對象，就盡可能地