计算机系统-从应用程序到底层实现 课件 第22讲 Cache 与 程序性能

练习一个Cache，按字节寻址，地址宽度为13位，2路组相连，块大小为4字节，共有8个组，一下是Cache中的内容，若需要从地址0x0E34读取一个字（设若2字节），请问是否命中？读取到的数据是多少？《计算机系统》高速缓存&程序性能篇《计算机系统》课程教学组2025年春季学期高速缓存与性能高速缓存

之写策略提高空间局部性提高时间局部性本讲内容Cache0102考虑数据一致性考虑存取性能本讲内容提高空间局部性01提高时间局部性02高速缓存与性能Cache性能指标不命中率存储器引用不命中的比率(misses/accesses)=1–命中率典型值(百分比):对L1高存缓存一般为3-10%对L2高速缓存不命中率更小(<1%)，受限于其大小

命中率从高速缓存传送一个字到处理器所需时间包括组选择、行确认和字选择的时间典型值:对L1高速缓存一般为1-2时钟周期对L2高速缓存一般为5-20时钟周期

不命中处罚由于不命中所需的额外时间对于主存一般为50-200周期再想想……命中和不命中之间的巨大时间差异若仅考虑L1Cache和主存，其时间差异可达100倍99%命中率比97%命中率要好两倍若Cache命中时间是1周期，则其不命中处罚时间达到100周期平均访问时间: 97%hits:1cycle+0.03*100cycles=4cycles 99%hits:1cycle+0.01*100cycles=2cycles因此，常用“不命中率”而不是“命中率”相关再思考注意区别高速缓存中：组行块高速缓存大小的影响（命中率vs.命中时间）块大小的影响（局部性）相联度的影响（相联度vs.命中时间）写策略的影响(传送时间&传送次数)左侧代码段，局部性如何？其Cache命中率如何？VTagBlock设若直接映像，2个组Cache大小是32B

set1再看一个例子VTagBlockset2左侧代码段，局部性良好其Cache命中率低！理解Cache改善代码即使程序有良好的空间局部性，高速缓存中也有足够的空间来存放x[i]和y[i]的块，每次引用还是会导致冲突不命中！怎么办？左侧代码段，局部性良好其Cache命中率低！VTagBlock设若直接映像，2个组Cache大小是32B

set1floatx[12]理解Cache改善代码VTagBlockset2如下代码段中，Loop1和Loop2，哪一个执行得更快？Loop1Loop2AB提交可为此题添加文本、图片、公式等解析，且需将内容全部放在本区域内。答案解析单选题50分如下代码段中，分别使用下述两种参数组合，在4个线程调用UpdateCounter()，哪一个执行得更快？0,1,2,316,32,48,64AB提交可为此题添加文本、图片、公式等解析，且需将内容全部放在本区域内。在第一种情况下，所有四个值很可能最终出现在同一缓存行上。每次核心递增计数器时，它都会使保存所有四个计数器的缓存行无效。所有其他内核下次访问自己的计数器时都会遭遇缓存未命中。这种线程行为实际“禁用“了Cache，导致降低了程序的性能。答案解析单选题50分此题未设置答案，请点击右侧设置按钮编写对Cache友好的代码让常见的情况运行得快集中在核心函数的内循环上在每个循环内部缓存不命中数量最小重复引用变量是好的(时间局部性)步长为1的引用模式(空间局部性)本讲内容提高空间局部性01提高时间局部性02高速缓存与性能不命中分析矩阵相乘计算设若高速缓存的blocksize=32B(足够容纳4个64-bit字)矩阵规模很大(行列值为n)（1/n）近似为0.0高速缓存容量有限，不能保存得下所有行数据分析方法:观察内部循环的访问方式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保存在寄存器回顾：内存中的数组C代码编写的数组以行优先的方式保存在存储器中在一行中依次访问列数据:for(i=0;i<N;i++)sum+=a[0][i];连续访问数组元素若块大于4字节，利用空间局部性

强制不命中率=4字节/块

在一列中依次访问行数据：for(i=0;i<n;i++)sum+=a[i][0];远距离访问数据

空间局部性差！强制不命中率=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每一次内部循环迭代的不命中率:

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每一次内部循环迭代的不命中率:

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每一次内部循环迭代的不命中率:

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每一次内部循环迭代的不命中率:

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每一次内部循环迭代的不命中率:

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每一次内部循环迭代的不命中率:

A

B

C 1.0 0.0 1.0˟=矩阵乘法小结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本讲内容提高空间局部性01提高时间局部性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设若:MatrixelementsaredoublesCacheblock=8doublesCachesizeC<<n(远远小于n)第一次迭代不命中次数:n/8+n=9n/8misses*=n*=8wide矩阵乘法Cache不命中分析-2设若:MatrixelementsaredoublesCacheblock=8doublesCachesizeC<<n(远远小于n)第二次迭代不命中次数:Again:n/8+n=9n/8misses总的不命中次数: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设若:Cacheblock=8doublesCachesizeC<<n(muchsmallerthann)3B2<C第一块迭代:B2/8missesforeachblock不命中次数2n/B*B2/8=nB/4

(忽略矩阵C)*=*=BlocksizeBxBn/Bblocks分块矩阵乘法Cache不命中分析-2设若:Cacheblock=8doublesCachesizeC<<n(muchsmallerthann)3B2<C第二块迭代Second(block)iteration:与第一次迭代类似不命中次数2n/B*B2/8=nB/4Totalmisses:nB/4*(n/B)2=n3/(4B)*=BlocksizeBxBn/Bblocks分块矩阵乘法小结不分块:(9/8)*n3分块:1/(4B)*n3建议最大可能的块尺寸B,但需受限3B2<C!差异巨大的原因:矩阵乘法天然具有的时间局部性:输入数据:3n2,计算2n3每个数组元素将被使用O(n)times!程序必须被正确地写本讲所得编程者可以编写具有良好局部性的程序来提高程序运行性能如何组织数据结构？如何访问数据？嵌套循环结构分块是通用技术所有系统都喜欢“对高速缓存友好的代码”只有基于特定平台的优化，才能获得绝对最优性能高速缓存容量，块大小，关联度等一些通用的编码技术也能保证性能优化保证工作集规模合理的小(时间局部性)使用小的步长(空间局部性)下一讲预告进程湖南大学《计算机系统》课程教学组

计算机系统即将进入：

异常控制流（你好，进程）湖南大学《计算机系统》课程教学组计算机系统进程processexception异常控制流本讲内容进程processexception异常控制流本讲内容控制流处理器的工作：从加电开始工作，到断电停止工作，CPU就是读并执行（解释）指令序列，一次一条指令这个序列就是处理器控制流（CPU’scontrolfloworflowofcontrol)<startup>inst1inst2inst3…instn<shutdown>Time改变控制流到目前为止，有两种机制可改变控制流分支与跳转Branchesandjumps调用与返回Callandreturn上述两者均是相应程序状态的变化对于一个实际应用的系统，需要对系统状态的变化进行响应来自硬盘或网络的数据已到达试图除以零的指令用户在键盘上使用Ctrl-C组合键盘系统计时器终止系统需要一种机制来处理上述“异常控制流（exceptionalcontrolflow）”——控制流的突变异常控制流存在于计算机系统的各个层次相对底层的机制异常Exceptions响应系统事件，例如改变系统状态，导致的控制流变化由硬件和操作系统软件相结合执行较高层机制进程的上下文切换Processcontextswitch信号Signals非本地跳转Nonlocaljumps:setjmp()/longjmp()或者由操作系统软件执行，如上下文切换和信号或者由C语言动态库执行，如非本地跳转异常一个异常是控制流的突变响应某些事件（如处理器状态变化），触发到操作系统的控制转移例如:

除以零，计算溢出，缺页，I/O请求完成，使用了Ctrl-C组合键用户进程操作系统异常

k异常处理

返回到I_current返回到I_next

终止执行事件

I_currentI_next异常表每一种类型的事件都对应一个独一无二的异常号k根据k值，索引进入异常表条目k包含的异常处理程序调用地址012...n-1异常表异常处理程序0的代码异常处理程序1的