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

1、存儲(chǔ)器層次結(jié)構(gòu)第1頁，共42頁，2022年，5月20日，16點(diǎn)4分，星期二提綱導(dǎo)論存儲(chǔ)技術(shù)局部性原理存儲(chǔ)器層次結(jié)構(gòu)高速緩存存儲(chǔ)器編寫高速緩存友好的代碼利用程序中的局部性第2頁，共42頁，2022年，5月20日，16點(diǎn)4分，星期二存儲(chǔ)器(memory)系統(tǒng)Von Neumann一個(gè)線性的字節(jié)數(shù)組，CPU能夠在一個(gè)常數(shù)時(shí)間內(nèi)訪問每個(gè)存儲(chǔ)器位置實(shí)際一個(gè)具有不同容量、成本和訪問時(shí)間的存儲(chǔ)(storage)設(shè)備層次結(jié)構(gòu)第3頁，共42頁，2022年，5月20日，16點(diǎn)4分，星期二存儲(chǔ)器層次結(jié)構(gòu)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點(diǎn)4分，星期二計(jì)算機(jī)程序的局部性(locality)良好局部性的程序重復(fù)訪問相同的數(shù)據(jù)項(xiàng)集合傾向于訪問臨近的數(shù)據(jù)項(xiàng)集合優(yōu)化思想使程序要訪問的數(shù)據(jù)項(xiàng)存儲(chǔ)在層次結(jié)構(gòu)中較高的地方，在那里CPU能更快的訪問到它們。第5頁，共42頁，2022年，5月20日，16點(diǎn)4分，星期二提綱導(dǎo)論存儲(chǔ)技術(shù)局部性原理存儲(chǔ)器層次結(jié)構(gòu)高速緩存存儲(chǔ)器編寫高速緩存友好的代碼利用程序中的局部性

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

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

5、022年，5月20日，16點(diǎn)4分，星期二對程序數(shù)據(jù)引用的局部性int sumvec(int vN)int i, sum = 0;for(i=0;iN;i+)sum += vi;return sum;變量sum：時(shí)間局部性向量v ：空間局部性第13頁，共42頁，2022年，5月20日，16點(diǎn)4分，星期二對程序數(shù)據(jù)引用的局部性函數(shù)sumvec順序訪問一個(gè)向量的每個(gè)元素，具有步長為1的引用模式步長為k的引用模式(stride-k reference pattern)訪問一個(gè)連續(xù)向量的每第k個(gè)元素隨著步長的增加，空間局部性下降第14頁，共42頁，2022年，5月20日，16點(diǎn)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點(diǎn)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點(diǎn)4分，星期二局部性小結(jié)重復(fù)引用同一個(gè)變量的程序有良好的時(shí)間局部性對于具有步長為k的引用模式的程序，步長越小，空間局部性越好對于取指令來說，循環(huán)有好的時(shí)間和空間局部性。循環(huán)體越小，循環(huán)迭代次數(shù)越多，局部性越好第17頁，共42頁，2022年，5月20日，16點(diǎn)4分，星期二提綱導(dǎo)論存儲(chǔ)技術(shù)局部性原理存儲(chǔ)器層次結(jié)構(gòu)高速緩存存儲(chǔ)器編寫高速緩存友好的代碼利用程序中的局部性第18頁，共42頁，2022年，5月20日，16點(diǎn)4分，星期二存儲(chǔ)器層次結(jié)構(gòu)(memory hierarchy)第19頁，共42頁，2022年，5月20日，16點(diǎn)4分，星期二存儲(chǔ)器層次結(jié)構(gòu)中的緩存高速緩存(cache)一個(gè)小

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

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

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

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

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

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

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