面向计算机体系结构的程序优化计算机科学导论第七讲.ppt

面向计算机体系结构的程序优化计算机科学导论第七讲,计算机科学技术学院陈意云0551-63607043http:/,课 程 内 容,课程内容围绕学科理论体系中的模型理论,程序理论和计算理论1.模型理论关心的问题 给定模型M，哪些问题可以由模型M解决；如何比较模型的表达能力2.程序理论关心的问题给定模型M，如何用模型M解决问题包括程序设计范型、程序设计语言、程序设计、形式语义、类型论、程序验证、程序分析等3.计算理论关心的问题给定模型M和一类问题,解决该类问题需多少资源,本讲座以矩阵乘算法为例，介绍围绕体系结构的优化,2,讲 座 提 纲,基本知识内存分层结构、多处理器的体系结构并行计算并行计算的常见方式、循环级并行程序中的局部性时间局部性、空间局部性、代码和数据局部性矩阵乘算法及其优化矩阵乘算法及分析、分块的矩阵乘算法及分析围绕计算机体系结构而不是抽象模型来讨论,3,基 本 知 识,计算机内存1.初学编程时的认识计算机的重要组成部分，由若干内存单元组成，用于存放程序和数据，可以按地址存取2.学习递归函数时的认识例：快速排序int a11;void quickSort(int m,int n)void readArray()int i;int i;int partition(int m,int n)if(n m)main()i=partition(m,n);readArray();a0=-9999;quickSort(m,i-1);a10=9999;quickSort(1,9);quickSort(i+1,n);,允许声明递归函数，存储分配有什么变化,4,基 本 知 识,计算机内存需要分出一块来作为数据栈,main,函数调用关系树,5,基 本 知 识,计算机内存需要分出一块来作为数据栈,函数调用关系树,6,基 本 知 识,计算机内存需要分出一块来作为数据栈,函数调用关系树,7,基 本 知 识,计算机内存需要分出一块来作为数据栈,函数调用关系树,8,基 本 知 识,计算机内存需要分出一块来作为数据栈,函数调用关系树,9,基 本 知 识,计算机内存1.初学编程时的认识2.学习递归函数时的认识3.学习动态存储分配时的认识通过malloc等函数申请的空间安排在堆上内存的这种划分是通过操作系统和编译器实现的，不是在硬件层面上的划分,10,基 本 知 识,计算机内存分层内存方面的基本局限：构造非常快的存储器或者非常大的存储器都是可能的，但是构造不出既快又大的存储器内存分层是指整个内存由 几层不同速度和大小的存 储器组成，并且最靠近处 理器的那一层最快最小,11,基 本 知 识,计算机内存分层,两边数据可能已过时,12,基 本 知 识,计算机内存分层程序的效率不仅取决于被执行的指令数，还取决于执行每条指令需要多长时间，而执行一条指令的时间区别非常可观若一个程序的大部分存储 访问都落在这种分层的较 快层次上，则平均内存访 问时间就会缩短,13,基 本 知 识,计算机内存分层寄存器由编译器生成的代码来管理，虚拟内存由操作系统管理，其他各层被自动管理。对于内存访问，计算机从底层开始逐 层查找，直至定位数据为止数据以块（缓存行、页）为单位在相邻层次之间进 行传送。缓存行:32256 字节,页:464千字节,14,基 本 知 识,计算机内存分层现代计算机都设计成程序员不用关心内存子系统的细节就可以写出正确的程序对应地，编程语言没有向 程序员提供干预数据进出 缓存的机制数据密集型程序可从恰当 利用内存子系统中获益,怎么做？,15,基 本 知 识,计算中潜在的并行性数值应用，例如科学计算和信号处理，一般都有很多潜在的并行这些应用处理有大批量元素的数据结构，在该结构每个元素上的运算相互独立，因而在不同元素上的运算可以并行执行，例如一些矩阵运算这些领域的程序一般有比较简单的控制结构和规整的数据处理模式下面介绍支持并行计算的较为简单的体系结构，和怎样写较优的代码,16,多处理器对称多处理器的体系结构,多个高性能处理器可以集成在一块芯片上（下次课涉及）,必须在处理器的缓存中找到它操作的大部分数据，以保证性能,基 本 知 识,通过共享内存来进行通信,17,多处理器分布式内存机器,两类机器：非均匀内存访问的机器和消息传递的机器 为获得良好的性能，软件都必须有很好局部性,基 本 知 识,在内存分层中又引入一层,处理器能迅速访问自己的局部内存,18,并行计算的常见方式任务并行：每个处理器执行不同的任务数据并行：把大任务分别成若干个相同的子任务并行应用的性能衡量的两种标准并行覆盖：整个计算中并行执行部分的百分比并行粒度：处理器上无需和其它处理器同步或通信的计算量,循环级并行,19,循环级并行耗时的应用一般都使用大数组，导致程序中出现有许多次迭代的循环，每次迭代用于计算数组中的一个元素。这些迭代经常相互独立，它们是并行计算的主要来源可以把这类循环的大量迭代分到各处理器上,循环级并行,20,循环级并行for(i=0;i n;i+)/计算向量X和YZi=Xi Yi;/对应元素差的平方Zi=Zi Zi;该循环可并行执行，把它变换成如下代码。由各处理器都执行这段代码来完成计算b=ceil(n/M);/M个处理器,p=0,1,M 1 for(i=bp;i min(n,b(p+1);i+)Zi=Xi Yi;Zi=Zi Zi;/数据并行的例子,循环级并行,21,循环级并行对并行化来说，任务级不像循环级那样有吸引力对一个程序而言，独立的任务数是一个常数，它不像典型的循环那样，独立的计算单元随迭代次数增加而增加任务通常不是等规模的，因此很难保证所有的处理器在所有时间都处于忙碌,循环级并行,22,程序中的局部性,局部性的表现 大多数程序的大部分时间在执行一小部分代码，并且仅涉及一小部分数据。传统的说法：程序90的时间消耗在执行10的代码上（代码的局部性）程序经常包含许多决不会执行的代码，如由组件和库构建的程序经常仅用所提供功能的一小部分程序运行时，通常仅一部分代码被真正执行。如处理非法输入和异常情况的代码，虽对程序的正确性至关重要，但它们很少被执行程序的大部分时间消耗在程序中最内层循环和深度递归的执行上,23,程序中的局部性,两种局部性时间局部性程序运行过程中被访问的内存单元（存放代码或数据）在很短的时间内可能再次被程序访问空间局部性毗邻被访问单元的内存单元在很短的时间内会被访问同一个缓存行上的元素一起被使用是空间局部性的一种重要形式。它能把缓存未命中次数降到最低，因而使得程序获得明显的加速,24,程序中的局部性,局部性与内存分层通常，最快的缓存没有大到足以把代码和数据同时放在其中从程序难以看出哪部分代码和数据会被频繁使用动态调整最快缓存的内容不可避免把最近使用的指令保存在缓存是一种较好的最优化利用内存分层的策略改变数据布局或计算次序也可以改进程序数据访问的时间和空间局部性,25,数据局部性计算向量X和Y对应元素差的平方for(i=0;i n;i+)/该程序段对向量机来 Zi=Xi Yi;/说是一种优化形式 for(i=0;i n;i+)Zi=Zi Zi;for(i=0;i n;i+)/有较好的数据局部性 Zi=Xi Yi;Zi=Zi Zi;,程序中的局部性,26,数据局部性对行为主的数组Z，根据空间局部性，显然更愿意逐行地给该数组元素置零for(j=0;j n;j+)for(i=0;i n;i+)for(i=0;i n;i+)for(j=0;j n;j+)Zi,j=0;Zi,j=0;为了获得最好的性能，应该让外循环并行执行 b=ceil(n/M);for(i=bp;i min(n,b(p+1);i+)for(j=0;j n;j+)Zi,j=0;,程序中的局部性,27,程序中的局部性,例：一个结构体大数组分拆成若干个数组 struct student int num10000;int num;char name1000020;char name20;struct student st10000;/非矩阵运算的例子若是顺序处理每个结构体的多个域，左边方式的数据局部性较好若是先顺序处理每个结构的num域，再处理每个结构的name域，则右边方式的数据局部性较好最好是按左边方式编程，由编译器决定是否需要把数据按右边方式布局,28,矩阵乘算法计算Z=X Y，它们都是nn的矩阵（数组）矩阵数据的布局是行为主,根据下面公式，当使用X的一行时，需逐列访问Y的所有元素,矩阵乘算法及其优化,29,Zi,j=Xi,1*Y1,j+.+Xi,n*Yn,j,矩阵乘算法计算Z=X Y，它们都是nn的矩阵（数组）矩阵数据的布局是行为主,矩阵乘算法及其优化,30,Zi,j=Xi,1*Y1,j+.+Xi,n*Yn,j,根据下面公式，当使用X的一行时，需逐列访问Y的所有元素,矩阵乘算法计算Z=X Y，它们都是nn的矩阵（数组）矩阵数据的布局是行为主,矩阵乘算法及其优化,31,Zi,j=Xi,1*Y1,j+.+Xi,n*Yn,j,根据下面公式，当使用X的一行时，需逐列访问Y的所有元素,矩阵乘算法计算Z=X Y，它们都是nn的矩阵（数组）矩阵数据的布局是行为主,矩阵乘算法及其优化,32,Zi,j=Xi,1*Y1,j+.+Xi,n*Yn,j,根据下面公式，当使用X的一行时，需逐列访问Y的所有元素,矩阵乘算法计算Z=X Y，它们都是nn的矩阵（数组）矩阵数据的布局是行为主,矩阵乘算法及其优化,33,Zi,j=Xi,0*Y0,j+.+Xi,n-1*Yn-1,j,根据下面公式，当使用X的一行时，需逐列访问Y的所有元素,矩阵乘算法下面的算法是计算密集型的需完成n3次操作(1次操作指1次乘和1次加运算，简称乘加操作)Z的每个元素的计算 是独立的,因此它们 可以并行计算先考虑在单处理器上 顺序执行，以便用于 和多处理器的比较,X,Y,Z:nnfor(i=0;i n;i+)for(j=0;j n;j+)Zij=0.0;for(k=0;k n;k+)Zij=Zij+Xik Ykj;,矩阵乘算法及其优化,34,矩阵乘算法假定在计算Zij的过程中,其值保存在寄存器中,则计算过程中不访问其内存单元，仅最后存储1次假定c个元素正好占满 一个缓存行，则X的1行散布在n/c个缓存行上。令c=4,n=12假定缓存足以放下X所有的缓存行，则读入X出现n2/c次缓存未命中,X,Y,Z:nnfor(i=0;i n;i+)for(j=0;j n;j+)Zij=0.0;for(k=0;k n;k+)Zij=Zij+Xik Ykj;,矩阵乘算法及其优化,35,矩阵乘算法当使用X的一行时，需要逐列访问Y的所有元素,矩阵乘算法及其优化,完成Z一行元素的计算过程中，因取Y而出现的缓存未命中次数最好为n2/c(即Y都可入缓存),灰色表示在缓存中,36,矩阵乘算法当使用X的一行时，需要逐列访问Y的所有元素,矩阵乘算法及其优化,完成Z一行元素的计算过程中，因取Y而出现的缓存未命中次数最好为n2/c(即Y都可入缓存),灰色表示在缓存中,37,矩阵乘算法当使用X的一行时，需要逐列访问Y的所有元素,矩阵乘算法及其优化,完成Z一行元素的计算过程中，因取Y而出现的缓存未命中次数最好为n2/c(即Y都可入缓存),灰色表示在缓存中,38,矩阵乘算法当使用X的一行时，需要逐列访问Y的所有元素,矩阵乘算法及其优化,完成Z一行元素的计算过程中，因取Y而出现的缓存未命中次数最好为n2/c(即Y都可入缓存),灰色表示在缓存中,39,矩阵乘算法当使用X的一行时，需要逐列访问Y的所有元素,矩阵乘算法及其优化,完成Z一行元素的计算过程中，因取Y而出现的缓存未命中次数最好为n2/c(即Y都可入缓存),灰色表示在缓存中,40,矩阵乘算法当使用X的一行时，需要逐列访问Y的所有元素,矩阵乘算法及其优化,完成Z一行元素的计算过程中，因取Y而出现的缓存未命中次数最好为n2/c(即Y都可入缓存),灰色表示在缓存中,41,矩阵乘算法当使用X的一行时，需要逐列访问Y的所有元素,矩阵乘算法及其优化,完成Z一行元素的计算过程中，因取Y而出现的缓存未命中次数最好为n2/c(即Y都可入缓存),灰色表示在缓存中,42,矩阵乘算法当使用X的一行时，需要逐列访问Y的所有元素,矩阵乘算法及其优化,完成Z一行元素的计算过程中，因取Y而出现的缓存未命中次数最好为n2/c(即Y都可入缓存),灰色表示在缓存中,43,矩阵乘算法当使用X的一行时，需要逐列访问Y的所有元素,矩阵乘算法及其优化,完成Z一行元素的计算过程中，因取Y而出现的缓存未命中次数最坏为n3(缓存连Y的一列数据都不能驻留),灰色表示在缓存中,44,矩阵乘算法当使用X的一行时，需要逐列访问Y的所有元素,矩阵乘算法及其优化,完成Z一行元素的计算过程中，因取Y而出现的缓存未命中次数最坏为n3(缓存连Y的一列数据都不能驻留),灰色表示在缓存中,45,矩阵乘算法当使用X的一行时，需要逐列访问Y的所有元素,矩阵乘算法及其优化,完成Z一行元素的计算过程中，因取Y而出现的缓存未命中次数最坏为n3(缓存连Y的一列数据都不能驻留),灰色表示在缓存中,46,矩阵乘算法当使用X的一行时，需要逐列访问Y的所有元素,矩阵乘算法及其优化,完成Z一行元素的计算过程中，因取Y而出现的缓存未命中次数最坏为n3(缓存连Y的一列数据都不能驻留),灰色表示在缓存中,47,矩阵乘算法当使用X的一行时，需要逐列访问Y的所有元素,矩阵乘算法及其优化,灰色表示在缓存中,完成Z一行元素的计算过程中，因取Y而出现的缓存未命中次数最坏为n3(缓存连Y的一列数据都不能驻留),48,缓存再也放不下了,矩阵乘算法当使用X的一行时，需要逐列访问Y的所有元素,矩阵乘算法及其优化,灰色表示在缓存中,完成Z一行元素的计算过程中，因取Y而出现的缓存未命中次数最坏为n3(缓存连Y的一列数据都不能驻留),49,一个元素 n次未命中,矩阵乘算法当使用X的一行时，需要逐列访问Y的所有元素,矩阵乘算法及其优化,灰色表示在缓存中,完成Z一行元素的计算过程中，因取Y而出现的缓存未命中次数最坏为n3(缓存连Y的一列数据都不能驻留),50,开始计算第 2个元素,矩阵乘算法当使用X的一行时，需要逐列访问Y的所有元素,矩阵乘算法及其优化,灰色表示在缓存中,完成Z一行元素的计算过程中，因取Y而出现的缓存未命中次数最坏为n3(缓存连Y的一列数据都不能驻留),51,第二个元素 n次未命中,矩阵乘算法继续对i=1,2,n 1逐步完成最外循环的过程中,矩阵乘算法及其优化,完成Z所有各行元素的计算过程中，因取Y而出现的缓存未命中次数最好是n2/c次。该算法所有缓存未命中,52,为n2/c(X)+n2/c(Y)次,矩阵乘算法继续对i=1,2,n 1逐步完成最外循环的过程中,矩阵乘算法及其优化,完成Z所有各行元素的计算过程中，因取Y而出现的缓存未命中次数最坏是n3次,该算法所有缓存未命中为n2/c+n3次,53,矩阵乘算法及其优化,把Z不同行的计算指派到不同处理器，每个处理器计算Z的连续n/p行(假定n可由p整除)。,54,用颜色区分,并行矩阵乘算法再考虑在p个处理器上并行计算,并行矩阵乘算法再考虑在p个处理器上并行计算,矩阵乘算法及其优化,每个处理器访问矩阵X和Z各n/p行以及整个Y，用n3/p次乘加运算来完成对Z的n2/p个元素的计算,55,并行矩阵乘算法再考虑在p个处理器上并行计算,矩阵乘算法及其优化,计算时间虽与 p 成比例减,通信代价却与 p 成比例增,因交付给 p 个处理器缓存的总缓存行至少是n2/c+pn2/c,56,X：交付给每个处理器的是n2/(cp)缓存行，共p个处理器,并行矩阵乘算法再考虑在p个处理器上并行计算,矩阵乘算法及其优化,计算时间虽与 p 成比例减,通信代价却与 p 成比例增,因交付给 p 个处理器缓存的总缓存行至少是n2/c+pn2/c,57,Y：交付给每个处理器的是n2/c缓存行，共p个处理器,并行矩阵乘算法再考虑在p个处理器上并行计算,矩阵乘算法及其优化,p逼近n时，计算时间为O(n2)，通信代价为O(n3)，即在内存和处理器之间传送数据的总线成为瓶颈,58,并行矩阵乘算法再考虑在p个处理器上并行计算,矩阵乘算法及其优化,按这样的数据布局，使用大量处理器来分担计算可能会使得计算速度降低,59,矩阵乘算法的优化 复用在缓存而不是内存的数据，则数据局部性好,矩阵乘算法及其优化,要做到缓存命中,复用应在数据从缓存移除前发生,60,矩阵乘算法的优化 复用在缓存而不是内存的数据，则数据局部性好,矩阵乘算法及其优化,在上述算法中，Y中一个数据的复用被n2个乘加操作隔开,Y中一个缓存行的复用被n个乘加操作隔开,61,Y0,0用于Z0,0的计算，然后要等到 Z1,0的计算再用,矩阵乘算法的优化 复用在缓存而不是内存的数据，则数据局部性好,矩阵乘算法及其优化,在上述算法中，Y中一个数据的复用被n2个乘加操作隔开,Y中一个缓存行的复用被n个乘加操作隔开,62,Y0,0用于Z0,0的计算，Y0,0在计算Z0,1再用,矩阵乘算法的优化 复用在缓存而不是内存的数据，则数据局部性好,矩阵乘算法及其优化,在一个处理器上，数据只有被本处理器复用时才可能出现缓存命中,63,矩阵乘算法的优化 复用在缓存而不是内存的数据，则数据局部性好,矩阵乘算法及其优化,改变数据布局和语句执行次序都可能改进缓存行的复用,64,矩阵乘算法的优化 复用在缓存而不是内存的数据，则数据局部性好,矩阵乘算法及其优化,分块计算是重排循环中迭代次序的较好方法 能极大地改进程序的局部性,65,分块计算的示意图1.X和Y的灰色部分进行乘加运算，可得到Z的灰色部分的结果2.X和Y的灰色部分分别由若干行和若干列构成3.对X和Y进行分块，通过增加循环来分块计算,矩阵乘算法及其优化,Z:,66,分块计算的示意图1.X和Y的灰色部分进行乘加运算，可得到Z的灰色部分的结果2.X和Y的灰色部分分别由若干行和若干列构成3.对X和Y进行分块，通过增加循环来分块计算,矩阵乘算法及其优化,Z:,67,分块计算的示意图1.X和Y的灰色部分进行乘加运算，可得到Z的灰色部分的结果2.X和Y的灰色部分分别由若干行和若干列构成3.对X和Y进行分块，通过增加循环来分块计算,矩阵乘算法及其优化,Z:,68,分块计算的示意图1.X和Y的灰色部分进行乘加运算，可得到Z的灰色部分的结果2.X和Y的灰色部分分别由若干行和若干列构成3.对X和Y进行分块，通过增加循环来分块计算,矩阵乘算法及其优化,Z:,69,矩阵乘算法的优化 仍假定n能由b整除,假定Z的元素已经先行置初值,for(ii=0;ii n;ii=ii+b)for(jj=0;jj n;jj=jj+b)for(kk=0;kk n;kk=kk+b)for(i=ii;i ii+b;i+)for(j=jj;j jj+b;j+)for(k=kk;k kk+b;k+)Zij=Zij+Xik Ykj;,矩阵乘算法及其优化,70,矩阵乘算法的优化 仍假定n能由b整除,假定Z的元素已经先行置初值前两行程序表示以块为单位进行矩阵乘第3行程序表示n/b个X和Y的块相乘得到Z的一块的结果,for(ii=0;ii n;ii=ii+b)for(jj=0;jj n;jj=jj+b)for(kk=0;kk n;kk=kk+b)for(i=ii;i ii+b;i+)for(j=jj;j jj+b;j+)for(k=kk;k kk+b;k+)Zij=Zij+Xik Ykj;,矩阵乘算法及其优化,71,矩阵乘算法的优化 仍假定n能由b整除,假定Z的元素已经先行置初值从第4到8行的程序计算左上角为Xiikk和Ykk jj的两块对左上角为Ziijj的块的贡献,for(ii=0;ii n;ii=ii+b)for(jj=0;jj n;jj=jj+b)for(kk=0;kk n;kk=kk+b)for(i=ii;i ii+b;i+)for(j=jj;j jj+b;j+)for(k=kk;k kk+b;k+)Zij=Zij+Xik Ykj;,矩阵乘算法及其优化,72,分块计算的示意图从第4到8行的程序计算左上角为Xiikk和Ykkjj的两块对左上角为Ziijj的块的贡献 当前：ii=0，kk=1，jj=0,矩阵乘算法及其优化,Z:,73,矩阵乘算法的优化 适当选择b，使3个矩阵都有一个块可以装到缓存把X或Y一块取到缓存，会出现b2/c次缓存未命中对于X和Y的一对块，第4到8行的程序完成b3次乘加计算由于整个矩阵乘法需要n3次乘加计算，则取一对块到缓存的总次数是n3/b3（b3源于上一条）对于X和Y的一对块会有2b2/c次缓存未命中，因此缓存未命中的总次数是2b2/c n3/b3=2n3/bc和先前的O(n3)次缓存未命中相比，在b较大时，2n3/bc能体现出分块方法的好处,矩阵乘算法及其优化,74,矩阵乘算法的优化 分块技术可以用到内存分层的每一层，例如，可以把22矩阵乘的运算对象都保存在寄存器中缓存的实际情况不像这里介绍的这么简单，这里介绍的方法要依据缓存的约束进行调整,矩阵乘算法及其优化,75,小 结,本讲座小结算法分析是比较算法优劣的一个重要依据程序的运行效率还依赖于体系结构的很多特点，有些特点没有反映在描述算法的编程语言中，导致仅基于编程语言的语义难以比较算法优劣熟悉体系结构、算法分析、编程语言、编译原理的程序员更有可能写出效率较高的程序参考书陈意云、张昱，编译原理(第3版），高教出版社本讲的内容取自该教材,76,小 结,相关课程算法基础、程序设计语言基础、编译原理、计算机体系结构、并行计算研究方向怎样从现代体系结构抽象出计算模型在这些抽象模型上的算法分析方法,77,