練習(xí)一個(gè)Cache，按字節(jié)尋址，地址寬度為13位，2路組相連，塊大小為4字節(jié)，共有8個(gè)組，一下是Cache中的內(nèi)容，若需要從地址0x0E34讀取一個(gè)字（設(shè)若2字節(jié)），請(qǐng)問是否命中？讀取到的數(shù)據(jù)是多少？《計(jì)算機(jī)系統(tǒng)》高速緩存&程序性能篇《計(jì)算機(jī)系統(tǒng)》課程教學(xué)組2025年春季學(xué)期高速緩存與性能高速緩存

之寫策略提高空間局部性提高時(shí)間局部性本講內(nèi)容Cache0102考慮數(shù)據(jù)一致性考慮存取性能本講內(nèi)容提高空間局部性01提高時(shí)間局部性02高速緩存與性能Cache性能指標(biāo)不命中率存儲(chǔ)器引用不命中的比率(misses/accesses)=1–命中率典型值(百分比):對(duì)L1高存緩存一般為3-10%對(duì)L2高速緩存不命中率更小(<1%)，受限于其大小

命中率從高速緩存?zhèn)魉鸵粋€(gè)字到處理器所需時(shí)間包括組選擇、行確認(rèn)和字選擇的時(shí)間典型值:對(duì)L1高速緩存一般為1-2時(shí)鐘周期對(duì)L2高速緩存一般為5-20時(shí)鐘周期

不命中處罰由于不命中所需的額外時(shí)間對(duì)于主存一般為50-200周期再想想……命中和不命中之間的巨大時(shí)間差異若僅考慮L1Cache和主存，其時(shí)間差異可達(dá)100倍99%命中率比97%命中率要好兩倍若Cache命中時(shí)間是1周期，則其不命中處罰時(shí)間達(dá)到100周期平均訪問時(shí)間: 97%hits:1cycle+0.03*100cycles=4cycles 99%hits:1cycle+0.01*100cycles=2cycles因此，常用“不命中率”而不是“命中率”相關(guān)再思考注意區(qū)別高速緩存中：組行塊高速緩存大小的影響（命中率vs.命中時(shí)間）塊大小的影響（局部性）相聯(lián)度的影響（相聯(lián)度vs.命中時(shí)間）寫策略的影響(傳送時(shí)間&傳送次數(shù))左側(cè)代碼段，局部性如何？其Cache命中率如何？VTagBlock設(shè)若直接映像，2個(gè)組Cache大小是32B

set1再看一個(gè)例子VTagBlockset2左側(cè)代碼段，局部性良好其Cache命中率低！理解Cache改善代碼即使程序有良好的空間局部性，高速緩存中也有足夠的空間來存放x[i]和y[i]的塊，每次引用還是會(huì)導(dǎo)致沖突不命中！怎么辦？左側(cè)代碼段，局部性良好其Cache命中率低！VTagBlock設(shè)若直接映像，2個(gè)組Cache大小是32B

set1floatx[12]理解Cache改善代碼VTagBlockset2如下代碼段中，Loop1和Loop2，哪一個(gè)執(zhí)行得更快？Loop1Loop2AB提交可為此題添加文本、圖片、公式等解析，且需將內(nèi)容全部放在本區(qū)域內(nèi)。答案解析單選題50分如下代碼段中，分別使用下述兩種參數(shù)組合，在4個(gè)線程調(diào)用UpdateCounter()，哪一個(gè)執(zhí)行得更快？0,1,2,316,32,48,64AB提交可為此題添加文本、圖片、公式等解析，且需將內(nèi)容全部放在本區(qū)域內(nèi)。在第一種情況下，所有四個(gè)值很可能最終出現(xiàn)在同一緩存行上。每次核心遞增計(jì)數(shù)器時(shí)，它都會(huì)使保存所有四個(gè)計(jì)數(shù)器的緩存行無效。所有其他內(nèi)核下次訪問自己的計(jì)數(shù)器時(shí)都會(huì)遭遇緩存未命中。這種線程行為實(shí)際“禁用“了Cache，導(dǎo)致降低了程序的性能。答案解析單選題50分此題未設(shè)置答案，請(qǐng)點(diǎn)擊右側(cè)設(shè)置按鈕編寫對(duì)Cache友好的代碼讓常見的情況運(yùn)行得快集中在核心函數(shù)的內(nèi)循環(huán)上在每個(gè)循環(huán)內(nèi)部緩存不命中數(shù)量最小重復(fù)引用變量是好的(時(shí)間局部性)步長(zhǎng)為1的引用模式(空間局部性)本講內(nèi)容提高空間局部性01提高時(shí)間局部性02高速緩存與性能不命中分析矩陣相乘計(jì)算設(shè)若高速緩存的blocksize=32B(足夠容納4個(gè)64-bit字)矩陣規(guī)模很大(行列值為n)（1/n）近似為0.0高速緩存容量有限，不能保存得下所有行數(shù)據(jù)分析方法:觀察內(nèi)部循環(huán)的訪問方式AkiBkjCij*=矩陣乘法示例

/*ijk*/for(i=0;i<n;i++){for(j=0;j<n;j++){sum=0.0;for(k=0;k<n;k++)sum+=a[i][k]*b[k][j];c[i][j]+=sum;}}變量

sum保存在寄存器回顧：內(nèi)存中的數(shù)組C代碼編寫的數(shù)組以行優(yōu)先的方式保存在存儲(chǔ)器中在一行中依次訪問列數(shù)據(jù):for(i=0;i<N;i++)sum+=a[0][i];連續(xù)訪問數(shù)組元素若塊大于4字節(jié)，利用空間局部性

強(qiáng)制不命中率=4字節(jié)/塊

在一列中依次訪問行數(shù)據(jù)：for(i=0;i<n;i++)sum+=a[i][0];遠(yuǎn)距離訪問數(shù)據(jù)

空間局部性差！強(qiáng)制不命中率=1(i.e.100%):矩陣乘法ijk/*ijk*/for(i=0;i<n;i++){for(j=0;j<n;j++){sum=0.0;for(k=0;k<n;k++)

sum+=a[i][k]*b[k][j];c[i][j]+=sum;}}Innerloop:ABC(i,*)(*,j)(i,j)Column-wiseRow-wiseFixed每一次內(nèi)部循環(huán)迭代的不命中率:

A

B

C 0.25 1.0 0.0?=矩陣乘法jikInnerloop:/*jik*/for(j=0;j<n;j++){for(i=0;i<n;i++){sum=0.0;for(k=0;k<n;k++)

sum+=a[i][k]*b[k][j];c[i][j]+=sum}}BC(i,*)(*,j)(i,j)Row-wiseColumn-wiseFixed每一次內(nèi)部循環(huán)迭代的不命中率:

A

B

C 0.25 1.0 0.0?=矩陣乘法kijInnerloop:/*kij*/for(k=0;k<n;k++){for(i=0;i<n;i++){r=a[i][k];for(j=0;j<n;j++)

c[i][j]+=r*b[k][j];

}}ABC(i,*)(k,*)Row-wiseRow-wiseFixed每一次內(nèi)部循環(huán)迭代的不命中率:

A

B

C 0.0 0.25 0.25?=矩陣乘法ikjInnerloop:/*ikj*/for(i=0;i<n;i++){for(k=0;k<n;k++){r=a[i][k];for(j=0;j<n;j++)

c[i][j]+=r*b[k][j];}}ABC(i,*)(i,k)(k,*)Row-wiseRow-wiseFixed每一次內(nèi)部循環(huán)迭代的不命中率:

A

B

C 0.0 0.25 0.25?=矩陣乘法jkiInnerloop:/*jki*/for(j=0;j<n;j++){for(k=0;k<n;k++){r=b[k][j];for(i=0;i<n;i++)

c[i][j]+=a[i][k]*r;}} (*,j)(*,k)ABC(k,j)Column-wiseColumn-wiseFixed每一次內(nèi)部循環(huán)迭代的不命中率:

A

B

C 1.0 0.0 1.0?=矩陣乘法kjiInnerloop:/*kji*/for(k=0;k<n;k++){for(j=0;j<n;j++){r=b[k][j];for(i=0;i<n;i++)

c[i][j]+=a[i][k]*r;}} ABC(*,j)(k,j)(*,k)FixedColumn-wiseColumn-wise每一次內(nèi)部循環(huán)迭代的不命中率:

A

B

C 1.0 0.0 1.0?=矩陣乘法小結(jié)ijk(&jik):

2loads,0storesmisses/iter=1.25kij(&ikj):

2loads,1storemisses/iter=0.5jki(&kji):

2loads,1storemisses/iter=2.0for(i=0;i<n;i++){for(j=0;j<n;j++){sum=0.0;for(k=0;k<n;k++)sum+=a[i][k]*b[k][j];c[i][j]=sum;}}for(k=0;k<n;k++){for(i=0;i<n;i++){r=a[i][k];for(j=0;j<n;j++)c[i][j]+=r*b[k][j];}}for(j=0;j<n;j++){for(k=0;k<n;k++){r=b[k][j];for(i=0;i<n;i++)c[i][j]+=a[i][k]*r;}}Corei7矩陣乘法性能jki/kjiijk/jikkij/ikj本講內(nèi)容提高空間局部性01提高時(shí)間局部性02高速緩存與性能示例矩陣相乘c=(double*)calloc(sizeof(double),n*n);/*Multiplynxnmatricesaandb*/voidmmm(double*a,double*b,double*c,intn){inti,j,k;for(i=0;i<n;i++) for(j=0;j<n;j++)for(k=0;k<n;k++) c[i*n+j]+=a[i*n+k]*b[k*n+j];}abij*c=矩陣乘法Cache不命中分析-1設(shè)若:MatrixelementsaredoublesCacheblock=8doublesCachesizeC<<n(遠(yuǎn)遠(yuǎn)小于n)第一次迭代不命中次數(shù):n/8+n=9n/8misses*=n*=8wide矩陣乘法Cache不命中分析-2設(shè)若:MatrixelementsaredoublesCacheblock=8doublesCachesizeC<<n(遠(yuǎn)遠(yuǎn)小于n)第二次迭代不命中次數(shù):Again:n/8+n=9n/8misses總的不命中次數(shù):9n/8*n2=(9/8)*n3n*=8wide分塊矩陣乘法c=(double*)calloc(sizeof(double),n*n);/*Multiplynxnmatricesaandb*/voidmmm(double*a,double*b,double*c,intn){inti,j,k;for(i=0;i<n;i+=B) for(j=0;j<n;j+=B)for(k=0;k<n;k+=B)

/*BxBminimatrixmultiplications*/for(i1=i;i1<i+B;i++)for(j1=j;j1<j+B;j++)for(k1=k;k1<k+B;k++) c[i1*n+j1]+=a[i1*n+k1]*b[k1*n+j1];}abi1j1*c=c+BlocksizeBxB分塊矩陣乘法Cache不命中分析-1設(shè)若:Cacheblock=8doublesCachesizeC<<n(muchsmallerthann)3B2<C第一塊迭代:B2/8missesforeachblock不命中次數(shù)2n/B*B2/8=nB/4

(忽略矩陣C)*=*=BlocksizeBxBn/Bblocks分塊矩陣乘法Cache不命中分析-2設(shè)若:Cacheblock=8doublesCachesizeC<<n(muchsmallerthann)3B2<C第二塊迭代Second(block)iteration:與第一次迭代類似不命中次數(shù)2n/B*B2/8=nB/4Totalmisses:nB/4*(n/B)2=n3/(4B)*=BlocksizeBxBn/Bblocks分塊矩陣乘法小結(jié)不分塊:(9/8)*n3分塊:1/(4B)*n3建議最大可能的塊尺寸B,但需受限3B2<C!差異巨大的原因:矩陣乘法天然具有的時(shí)間局部性:輸入數(shù)據(jù):3n2,計(jì)算2n3每個(gè)數(shù)組元素將被使用O(n)times!程序必須被正確地寫本講所得編程者可以編寫具有良好局部性的程序來提高程序運(yùn)行性能如何組織數(shù)據(jù)結(jié)構(gòu)？如何訪問數(shù)據(jù)？嵌套循環(huán)結(jié)構(gòu)分塊是通用技術(shù)所有系統(tǒng)都喜歡“對(duì)高速緩存友好的代碼”只有基于特定平臺(tái)的優(yōu)化，才能獲得絕對(duì)最優(yōu)性能高速緩存容量，塊大小，關(guān)聯(lián)度等一些通用的編碼技術(shù)也能保證性能優(yōu)化保證工作集規(guī)模合理的小(時(shí)間局部性)使用小的步長(zhǎng)(空間局部性)下一講預(yù)告進(jìn)程湖南大學(xué)《計(jì)算機(jī)系統(tǒng)》課程教學(xué)組

計(jì)算機(jī)系統(tǒng)即將進(jìn)入：

異?？刂屏鳎愫茫M(jìn)程）湖南大學(xué)《計(jì)算機(jī)系統(tǒng)》課程教學(xué)組計(jì)算機(jī)系統(tǒng)進(jìn)程processexception異?？刂屏鞅局v內(nèi)容進(jìn)程processexception異?？刂屏鞅局v內(nèi)容控制流處理器的工作：從加電開始工作，到斷電停止工作，CPU就是讀并執(zhí)行（解釋）指令序列，一次一條指令這個(gè)序列就是處理器控制流（CPU’scontrolfloworflowofcontrol)<startup>inst1inst2inst3…instn<shutdown>Time改變控制流到目前為止，有兩種機(jī)制可改變控制流分支與跳轉(zhuǎn)Branchesandjumps調(diào)用與返回Callandreturn上述兩者均是相應(yīng)程序狀態(tài)的變化對(duì)于一個(gè)實(shí)際應(yīng)用的系統(tǒng)，需要對(duì)系統(tǒng)狀態(tài)的變化進(jìn)行響應(yīng)來自硬盤或網(wǎng)絡(luò)的數(shù)據(jù)已到達(dá)試圖除以零的指令用戶在鍵盤上使用Ctrl-C組合鍵盤系統(tǒng)計(jì)時(shí)器終止系統(tǒng)需要一種機(jī)制來處理上述“異?？刂屏鳎╡xceptionalcontrolflow）”——控制流的突變異常控制流存在于計(jì)算機(jī)系統(tǒng)的各個(gè)層次相對(duì)底層的機(jī)制異常Exceptions響應(yīng)系統(tǒng)事件，例如改變系統(tǒng)狀態(tài)，導(dǎo)致的控制流變化由硬件和操作系統(tǒng)軟件相結(jié)合執(zhí)行較高層機(jī)制進(jìn)程的上下文切換Processcontextswitch信號(hào)Signals非本地跳轉(zhuǎn)Nonlocaljumps:setjmp()/longjmp()或者由操作系統(tǒng)軟件執(zhí)行，如上下文切換和信號(hào)或者由C語言動(dòng)態(tài)庫執(zhí)行，如非本地跳轉(zhuǎn)異常一個(gè)異常是控制流的突變響應(yīng)某些事件（如處理器狀態(tài)變化），觸發(fā)到操作系統(tǒng)的控制轉(zhuǎn)移例如:

除以零，計(jì)算溢出，缺頁，I/O請(qǐng)求完成，使用了Ctrl-C組合鍵用戶進(jìn)程操作系統(tǒng)異常

k異常處理

返回到I_current返回到I_next

終止執(zhí)行事件

I_currentI_next異常表每一種類型的事件都對(duì)應(yīng)一個(gè)獨(dú)一無二的異常號(hào)k根據(jù)k值，索引進(jìn)入異常表?xiàng)l目k包含的異常處理程序調(diào)用地址012...n-1異常表異常處理程序0的代碼異常處理程序1的