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

面向计算机系统结构的程序优化面向计算机系统结构的程序优化计算机科学导论第七讲计算机科学导论第七讲计算机科学技术学院计算机科学技术学院陈意云陈意云0551-63607043yiyun@课课 程程 内内 容容•课程内容课程内容围绕学科理论体系中的模型理论围绕学科理论体系中的模型理论, 程序理论和计算理论程序理论和计算理论1. 模型理论关心的问题模型理论关心的问题 给定模型给定模型M，哪些问题可以由模型，哪些问题可以由模型M解决；如何解决；如何比较模型的表达能力比较模型的表达能力2. 程序理论关心的问题程序理论关心的问题–给定模型给定模型M，如何用模型，如何用模型M解决问题解决问题–包括程序设计范型、包括程序设计范型、程序设计语言、程序设计、程序设计语言、程序设计、形式语义、类型论、程序验证、程序分析等形式语义、类型论、程序验证、程序分析等3. 计算理论关心的问题计算理论关心的问题给定模型给定模型M和一类问题和一类问题, 解决该类问题解决该类问题需多少资源需多少资源讲讲 座座 提提 纲纲•基本知识基本知识–内存分层结构、多处理器的体系结构内存分层结构、多处理器的体系结构•并行计算并行计算–并行计算的常见方式、循环级并行并行计算的常见方式、循环级并行•程序中的局部性程序中的局部性–时间局部性、空间局部性、代码和数据局部性时间局部性、空间局部性、代码和数据局部性•矩阵乘算法及矩阵乘算法及其其优化优化–矩阵乘算法及分析、分块的矩阵乘算法及分析矩阵乘算法及分析、分块的矩阵乘算法及分析围绕计算机体系结构而不是抽象模型来讨论围绕计算机体系结构而不是抽象模型来讨论基基 本本 知知 识识•计算机内存计算机内存1. 初学编程时的认识初学编程时的认识–计计算算机机的的重重要要组组成成部部分分，，由由若若干干内内存存单单元元组组成成，，用于存放程序和数据，可以按地址存取用于存放程序和数据，可以按地址存取2. 学习递归函数时的认识学习递归函数时的认识例：快速排序例：快速排序int a[11]; 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(); a[0] = -9999; quickSort(m, i-1); a[10] = 9999; quickSort(1, 9); quickSort(i+1, n);} } }基基 本本 知知 识识•计算机内存计算机内存需要分出一块来作为数据栈需要分出一块来作为数据栈main函数调用关系树函数调用关系树main栈栈基基 本本 知知 识识•计算机内存计算机内存需要分出一块来作为数据栈需要分出一块来作为数据栈 mainr函数调用关系树函数调用关系树mainint ir ( )栈栈基基 本本 知知 识识•计算机内存计算机内存需要分出一块来作为数据栈需要分出一块来作为数据栈mainq(1,9)r函数调用关系树函数调用关系树mainint iq (1, 9)int m, n栈栈基基 本本 知知 识识•计算机内存计算机内存需要分出一块来作为数据栈需要分出一块来作为数据栈mainq(1,9)rp(1,9)q(1,3)mainint iq (1, 9)int m, nint iq (1, 3)int m, n栈栈函数调用关系树函数调用关系树基基 本本 知知 识识•计算机内存计算机内存需要分出一块来作为数据栈需要分出一块来作为数据栈mainq(1,9)rp(1,9)q(1,3)q(1,0)p(1,3)mainint iq (1, 9)int m, nint iq (1, 3)int m, nint iq (1, 0)int m, n栈栈函数调用关系树函数调用关系树基基 本本 知知 识识•计算机内存计算机内存1. 初学编程时的认识初学编程时的认识2. 学习递归函数时的认识学习递归函数时的认识3. 学习动态存储分配时的认识学习动态存储分配时的认识通过通过malloc等函数申请的空等函数申请的空间安排在堆上间安排在堆上内存的这种划分是通过操作内存的这种划分是通过操作系统和编译器实现的，不是在系统和编译器实现的，不是在硬件层面上的划分硬件层面上的划分代代 码码静静 态态 数数 据据堆堆栈栈基基 本本 知知 识识•计算机内存分层计算机内存分层–内内存存方方面面的的基基本本局局限限：：构构造造非非常常快快的的存存储储器器或或者者非非常常大大的的存存储储器器都都是是可可能能的的，，但但是是构构造造不不出出既既快快又大的存储器又大的存储器–内存分层是指整个内存由内存分层是指整个内存由 几层不同速度和大小的存几层不同速度和大小的存 储器组成，并且最靠近处储器组成，并且最靠近处 理器的那一层最快最小理器的那一层最快最小虚拟内存虚拟内存(磁盘磁盘)物理内存物理内存2级缓存级缓存1级缓存级缓存寄存器寄存器(处理器处理器)基基 本本 知知 识识•计算机内存分层计算机内存分层虚拟内存虚拟内存(磁盘磁盘)物理内存物理内存2级缓存级缓存1级缓存级缓存寄存器寄存器(处理器处理器)典型大小典型大小> 2千兆字节千兆字节256兆兆 2千兆字节千兆字节128千千 4兆字节兆字节16 64千字节千字节32字字典型访问时间典型访问时间3 15微秒微秒100 150纳秒纳秒40 60纳秒纳秒5 10纳秒纳秒1纳秒纳秒两边的数据已过时两边的数据已过时基基 本本 知知 识识•计算机内存分层计算机内存分层–程程序序的的效效率率不不仅仅取取决决于于被被执执行行的的指指令令数数，，还还取取决决于于执执行行每每条条指指令令需需要要多多长长时时间间，，而而执执行行一一条条指指令令的时间区别非常可观的时间区别非常可观–若若一个程序的大部分一个程序的大部分存储存储 访问都落在访问都落在这种这种分层的较分层的较 快层次上，快层次上，则则平均内存访平均内存访 问时间就会缩短问时间就会缩短虚拟内存虚拟内存(磁盘磁盘)物理内存物理内存2级缓存级缓存1级缓存级缓存寄存器寄存器(处理器处理器)基基 本本 知知 识识•计算机内存分层计算机内存分层–寄寄存存器器的的内内容容由由软软件件控控制制，，虚虚拟拟内内存存由由操操作作系系统统管管理理，，其其他他各各层层被被自自动动管管理理。

对对于于内内存存访访问问，，计计算机从底层开始逐层查找，算机从底层开始逐层查找， 直至定位数据为止直至定位数据为止–数据以块（缓存行、页）数据以块（缓存行、页） 为单位在相邻层次之间进为单位在相邻层次之间进 行传送缓存行行传送缓存行: 32~256 字节字节, 页页: 4~64千字节千字节虚拟内存虚拟内存(磁盘磁盘)物理内存物理内存2级缓存级缓存1级缓存级缓存寄存器寄存器(处理器处理器)基基 本本 知知 识识•计算机内存分层计算机内存分层–现现代代计计算算机机都都设设计计成成程程序序员员不不用用关关心心内内存存子子系系统统的细节就可以写出正确的程序的细节就可以写出正确的程序–对应地，编程语言没有向对应地，编程语言没有向 程序员提供干预数据进出程序员提供干预数据进出 缓存的机制缓存的机制–数据密集型程序可从恰当数据密集型程序可从恰当 利用内存子系统中获益利用内存子系统中获益, 怎么做？怎么做？虚拟内存虚拟内存(磁盘磁盘)物理内存物理内存2级缓存级缓存1级缓存级缓存寄存器寄存器(处理器处理器)基基 本本 知知 识识•计算中潜在的并行性计算中潜在的并行性–数值应用，例如科学计算和信号处理，一般数值应用，例如科学计算和信号处理，一般都都有有很很多多潜在潜在的并行的并行–这些应用处理有大批量元素的数据结构，在该结这些应用处理有大批量元素的数据结构，在该结构每个元素上的运算相互独立，因而在不同元素构每个元素上的运算相互独立，因而在不同元素上的运算可以并行执行上的运算可以并行执行，例如一些矩阵运算，例如一些矩阵运算–这些这些领域的程序一般有比较简单的控制结构和规领域的程序一般有比较简单的控制结构和规整的数据处理模式整的数据处理模式–下面介绍支持并行计算的较为简单的体系结构，下面介绍支持并行计算的较为简单的体系结构，和怎样写较优的代码和怎样写较优的代码•多处理器多处理器–对称多处理器的体系结构对称多处理器的体系结构多个高性多个高性能处理器能处理器可以集成可以集成在一块芯在一块芯片上片上必须在处理器的缓存中必须在处理器的缓存中找到它操作的大部分数找到它操作的大部分数据，以保证性能据，以保证性能基基 本本 知知 识识二级二级缓存缓存内存内存总线总线二级二级缓存缓存二级二级缓存缓存二级二级缓存缓存一级一级缓存缓存一级一级缓存缓存一级一级缓存缓存一级一级缓存缓存处理器处理器处理器处理器处理器处理器处理器处理器 通过共通过共享内存来享内存来进行通信进行通信•多处理器多处理器–分布式内存机器分布式内存机器 两类机器：非均匀内存访问的两类机器：非均匀内存访问的机器和消息传递的机器机器和消息传递的机器 为获得良好的性能，软件都必为获得良好的性能，软件都必须有很好局部性须有很好局部性 基基 本本 知知 识识总线或其它互连总线或其它互连二级二级缓存缓存二级二级缓存缓存二级二级缓存缓存二级二级缓存缓存一级一级缓存缓存一级一级缓存缓存一级一级缓存缓存一级一级缓存缓存处理器处理器处理器处理器处理处理器处理器处理器局部局部内存内存局部局部内存内存局部局部内存内存局部局部内存内存在内存分在内存分层中又引层中又引入一层入一层处理器能处理器能迅速访问迅速访问自己的局自己的局部内存部内存 •并行计算的常见方式并行计算的常见方式–任务并行：每个处理器执行不同的任务任务并行：每个处理器执行不同的任务–数据并行：把大任务分别成若干个相同的子任务数据并行：把大任务分别成若干个相同的子任务•并行应用性能衡量的两种标准并行应用性能衡量的两种标准–并行覆盖：整个计算中并行执行部分的百分比并行覆盖：整个计算中并行执行部分的百分比–并并行行粒粒度度：：处处理理器器上上无无需需和和其其它它处处理理器器同同步步或或通通信的计算量信的计算量循环级并行循环级并行•循环级并行循环级并行–耗耗时时的的应应用用一一般般都都使使用用大大数数组组，，导导致致程程序序中中出出现现有有许许多多次次迭迭代代的的循循环环，，这这些些迭迭代代经经常常相相互互独独立立，，它们是并行计算的主要来源它们是并行计算的主要来源–可以把这类循环的大量迭代分到各处理器上可以把这类循环的大量迭代分到各处理器上 循环级并行循环级并行•循环级并行循环级并行for (i = 0; i < n; i++) { //计算向量计算向量X和和YZ[i] = X[i]   Y[i]; //对应元素差的平方对应元素差的平方Z[i] = Z[i]   Z[i];}变换成如下代码变换成如下代码b = ceil (n/M); // M个处理器个处理器, p = 0, 1, …, M  1 for (i = b p; i < min(n, b (p+1)); i++) {Z[i] = X[i]   Y[i];Z[i] = Z[i]   Z[i];} // 数据并行的例子数据并行的例子循环级并行循环级并行•循环级并行循环级并行–对并行化来说，任务级不像循环级那样有吸引力对并行化来说，任务级不像循环级那样有吸引力–对对一一个个程程序序而而言言，，独独立立的的任任务务数数是是一一个个常常数数，，它它不不像像典典型型的的循循环环那那样样，，独独立立的的计计算算单单元元随随迭迭代代次次数增加而增加数增加而增加–任任务务通通常常不不是是等等规规模模的的，，因因此此很很难难保保证证所所有有的的处处理器在所有时间都处于忙碌理器在所有时间都处于忙碌循环级并行循环级并行程序中的局部性程序中的局部性•局部性的表现局部性的表现 大多数程序的大部分时间在执行一小部分代码，大多数程序的大部分时间在执行一小部分代码，并且仅涉及一小部分数据。

并且仅涉及一小部分数据传统传统的的说法说法：：程序程序90％％的时间消耗在执行的时间消耗在执行10％的代码上％的代码上（代码的局部性）（代码的局部性）–程程序序经经常常包包含含许许多多决决不不会会执执行行的的代代码码，，如如由由组组件件和库构建的程序经常仅用所提供功能的一小部分和库构建的程序经常仅用所提供功能的一小部分–程程序序运运行行时时，，通通常常仅仅一一部部分分代代码码被被真真正正执执行行如如处处理理非非法法输输入入和和异异常常情情况况的的代代码码，，虽虽对对程程序序的的正正确性至关重要，但它们很少被执行确性至关重要，但它们很少被执行–程程序序的的大大部部分分时时间间消消耗耗在在程程序序中中最最内内层层循循环环和和深深度递归的执行上度递归的执行上程序中的局部性程序中的局部性•两种局部性两种局部性–时间局部性时间局部性程程序序运运行行过过程程中中被被访访问问的的内内存存单单元元（（存存放放代代码码或或数据）在很短的时间内可能再次被程序访问数据）在很短的时间内可能再次被程序访问–空间局部性空间局部性毗邻被访问单元的内存单元在很短的时间内会再毗邻被访问单元的内存单元在很短的时间内会再次被访问次被访问–同同一一个个缓缓存存行行上上的的元元素素一一起起被被使使用用是是空空间间局局部部性性的的一一种种重重要要形形式式。

它它能能把把缓缓存存未未命命中中次次数数降降到到最最低，因而使得程度获得明显的加速低，因而使得程度获得明显的加速程序中的局部性程序中的局部性•局部性与内存分层局部性与内存分层–通通常常，，最最快快的的缓缓存存没没有有大大到到足足以以把把代代码码和和数数据据同同时放在其中时放在其中–从从程序难以程序难以看出哪部分代码看出哪部分代码和数据和数据会被频繁使用会被频繁使用–动态调整最快缓存的内容不可避免动态调整最快缓存的内容不可避免–把把最最近近使使用用的的指指令令保保存存在在缓缓存存是是一一种种较较好好的的最最优优化利用内存分层的策略化利用内存分层的策略–改改变变数数据据布布局局或或计计算算次次序序也也可可以以改改进进程程序序数数据据访访问的时间和空间局部性问的时间和空间局部性•数据局部性数据局部性计算向量计算向量X和和Y对应元素差的平方对应元素差的平方for (i = 0; i < n; i++) {// 该程序段对向量机来该程序段对向量机来 Z[i] = X[i]   Y[i];// 说是一种优化形式说是一种优化形式 }for (i = 0; i < n; i++) { Z[i] = Z[i]   Z[i];}for (i = 0; i < n; i++) { // 有较好的数据局部性有较好的数据局部性 Z[i] = X[i]   Y[i]; Z[i] = Z[i]   Z[i];}程序中的局部性程序中的局部性•数据局部性数据局部性–对行为主的数组对行为主的数组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++) Z[i, j] = 0; Z[i, j] = 0;–为了获得最好的性能，应该并行化外循环为了获得最好的性能，应该并行化外循环 b = ceil (n/M); for (i = b p; i < min(n, b (p+1)); i++) for (j = 0; j < n; j++) Z[i, j] = 0;程序中的局部性程序中的局部性程序中的局部性程序中的局部性例：例： 一个结构体大数组一个结构体大数组分拆成若干个数组分拆成若干个数组 struct student {int num[10000]; int num;char name[10000][20]; char name[20];…… …… } struct student st[10000]; //非矩阵运算的例子非矩阵运算的例子•若若是是顺顺序序处处理理每每个个结结构构体体的的多多个个域域，，左左边边方方式式的的数数据局部性较好据局部性较好•若若是是先先顺顺序序处处理理每每个个结结构构的的num域域，，再再处处理理每每个个结结构的构的name域，域，…，则右边方式的数据局部性较好，则右边方式的数据局部性较好•最最好好是是按按左左边边方方式式编编程程，，由由编编译译器器决决定定是是否否需需要要把把数据按右边方式布局数据按右边方式布局•矩阵乘算法矩阵乘算法–计算计算Z = X   Y，它们都是，它们都是n n的矩阵（数组）的矩阵（数组）–矩阵数据的布局是行为主矩阵数据的布局是行为主j = 0, 1, … , n  1i = 0XY• 当当 使使用用X的的一一行行时时，，需需要要逐逐列列访访问问Y的的所所有元素有元素• 矩阵乘算法及其优化矩阵乘算法及其优化•矩阵乘算法矩阵乘算法–下面的算法下面的算法是计算是计算密集型密集型的的需完成需完成n3次操作次操作 (1次操作指次操作指1次乘次乘和和1次次加运算加运算，， 简称乘加简称乘加操作操作)–Z的每个元素的的每个元素的计算计算 是是独立的独立的, 因此因此它们它们 可以并行计算可以并行计算–先考虑在单处理器先考虑在单处理器 上顺序执行上顺序执行X, Y, Z: n nfor (i = 0; i < n; i++)for (j = 0; j < n; j++) { Z[i][j] = 0.0; for (k = 0; k < n; k++) Z[i][j] = Z[i][j] + X[i][k]   Y[k][j];}矩阵乘算法及其优化矩阵乘算法及其优化•矩阵乘算法矩阵乘算法–假假定定在在计计算算Z[i][j]的的过过程程中中, 其其值值保保存存在在寄寄存存器器中中,则计算过程中不访问其内存单元，仅最后存储则计算过程中不访问其内存单元，仅最后存储1次次–假定假定c个元素正好占满个元素正好占满 一个缓存行，则一个缓存行，则X的的1行散布在行散布在n/c个缓存个缓存行上。

令行上令c = 4, n = 12–假定缓存足以放下假定缓存足以放下X所所有的缓存行，则读入有的缓存行，则读入X出现出现n2/c次缓存未命中次缓存未命中X, Y, Z: n nfor (i = 0; i < n; i++)for (j = 0; j < n; j++) { Z[i][j] = 0.0; for (k = 0; k < n; k++) Z[i][j] = Z[i][j] + X[i][k]   Y[k][j];}矩阵乘算法及其优化矩阵乘算法及其优化j = 0, 1, … , n  1i = 0XY•矩阵乘算法矩阵乘算法–当使用当使用X的一行时，需要逐列访问的一行时，需要逐列访问Y的所有元素的所有元素矩阵乘算法及其优化矩阵乘算法及其优化• 完成完成Z一一行行•元素元素的计算的计算过过•程中，因取程中，因取Y而出现的缓存而出现的缓存•未命中次数未命中次数最最•好好为为n2/c (即即Y•都可入缓存都可入缓存)灰色表示在缓存中灰色表示在缓存中j = 0, 1, … , n  1i = 0XY•矩阵乘算法矩阵乘算法–当使用当使用X的一行时，需要逐列访问的一行时，需要逐列访问Y的所有元素的所有元素矩阵乘算法及其优化矩阵乘算法及其优化• 完成完成Z一一行行•元素元素的计算的计算过过•程中，因取程中，因取Y而出现的缓存而出现的缓存•未命中次数未命中次数最最•好好为为n2/c (即即Y•都可入缓存都可入缓存)灰色表示在缓存中灰色表示在缓存中j = 0, 1, … , n  1i = 0XY•矩阵乘算法矩阵乘算法–当使用当使用X的一行时，需要逐列访问的一行时，需要逐列访问Y的所有元素的所有元素矩阵乘算法及其优化矩阵乘算法及其优化• 完成完成Z一一行行•元素元素的计算的计算过过•程中，因取程中，因取Y而出现的缓存而出现的缓存•未命中次数未命中次数最最•好好为为n2/c (即即Y•都可入缓存都可入缓存)灰色表示在缓存中灰色表示在缓存中j = 0, 1, … , n  1i = 0XY•矩阵乘算法矩阵乘算法–当使用当使用X的一行时，需要逐列访问的一行时，需要逐列访问Y的所有元素的所有元素矩阵乘算法及其优化矩阵乘算法及其优化• 完成完成Z一一行行•元素元素的计算的计算过过•程中，因取程中，因取Y而出现的缓存而出现的缓存•未命中次数未命中次数最最•好好为为n2/c (即即Y•都可入缓存都可入缓存)灰色表示在缓存中灰色表示在缓存中j = 0, 1, … , n  1i = 0XY•矩阵乘算法矩阵乘算法–当使用当使用X的一行时，需要逐列访问的一行时，需要逐列访问Y的所有元素的所有元素矩阵乘算法及其优化矩阵乘算法及其优化• 完成完成Z一一行行•元素元素的计算的计算过过•程中，因取程中，因取Y而出现的缓存而出现的缓存•未命中次数未命中次数最最•好好为为n2/c (即即Y•都可入缓存都可入缓存)灰色表示在缓存中灰色表示在缓存中j = 0, 1, … , n  1i = 0XY•矩阵乘算法矩阵乘算法–当使用当使用X的一行时，需要逐列访问的一行时，需要逐列访问Y的所有元素的所有元素矩阵乘算法及其优化矩阵乘算法及其优化• 完成完成Z一一行行•元素元素的计算的计算过过•程中，因取程中，因取Y而出现的缓存而出现的缓存•未命中次数未命中次数最最•好好为为n2/c (即即Y•都可入缓存都可入缓存)灰色表示在缓存中灰色表示在缓存中j = 0, 1, … , n  1i = 0XY•矩阵乘算法矩阵乘算法–当使用当使用X的一行时，需要逐列访问的一行时，需要逐列访问Y的所有元素的所有元素矩阵乘算法及其优化矩阵乘算法及其优化• 完成完成Z一一行行•元素元素的计算的计算过过•程中，因取程中，因取Y而出现的缓存而出现的缓存•未命中次数未命中次数最最•坏坏为为n3 (缓存缓存•连连Y的一列的一列数数•据都不能驻据都不能驻留留)灰色表示在缓存中灰色表示在缓存中j = 0, 1, … , n  1i = 0XY•矩阵乘算法矩阵乘算法–当使用当使用X的一行时，需要逐列访问的一行时，需要逐列访问Y的所有元素的所有元素矩阵乘算法及其优化矩阵乘算法及其优化灰色表示在缓存中灰色表示在缓存中• 完成完成Z一一行行•元素元素的计算的计算过过•程中，因取程中，因取Y而出现的缓存而出现的缓存•未命中次数未命中次数最最•坏坏为为n3 (缓存缓存•连连Y的一列的一列数数•据都不能驻据都不能驻留留)j = 0, 1, … , n  1i = 0XY•矩阵乘算法矩阵乘算法–当使用当使用X的一行时，需要逐列访问的一行时，需要逐列访问Y的所有元素的所有元素矩阵乘算法及其优化矩阵乘算法及其优化灰色表示在缓存中灰色表示在缓存中• 完成完成Z一一行行•元素元素的计算的计算过过•程中，因取程中，因取Y而出现的缓存而出现的缓存•未命中次数未命中次数最最•坏坏为为n3 (缓存缓存•连连Y的一列的一列数数•据都不能驻据都不能驻留留)•矩阵乘算法矩阵乘算法–继续对继续对i =1, 2, …, n  1逐步完成最外循环的过程中逐步完成最外循环的过程中j = 0, 1, … , n  1i = 0XY矩阵乘算法及其优化矩阵乘算法及其优化 完成完成Z所有所有各行元素各行元素的计的计算过程中，因算过程中，因取取Y而出现的而出现的缓存未命中次缓存未命中次数数最好最好是是n2/c次。

该算法所次该算法所有缓存未命中有缓存未命中为为n2/c +n2/c次次 •矩阵乘算法矩阵乘算法–继续对继续对i =1, 2, …, n  1逐步完成最外循环的过程中逐步完成最外循环的过程中j = 0, 1, … , n  1i = 0XY矩阵乘算法及其优化矩阵乘算法及其优化 完成完成Z所有所有各行元素各行元素的计的计算过程中，因算过程中，因取取Y而出现的而出现的缓存未命中次缓存未命中次数数最坏最坏是是n3次次,该算法所有缓该算法所有缓存未命中为存未命中为n2/c + n3次次 j = 0, 1, … , n  1i = 0XY•并行矩阵乘算法并行矩阵乘算法再考虑在再考虑在p个处理器上并行计算个处理器上并行计算矩阵乘算法及其优化矩阵乘算法及其优化 把把Z不不同同行行的的计计算算指指派派到到不不同同处处理理器器，，每每个个处处理理器器计计算算Z的的连连续续n/p行行(假假定定n可可由由p整整除除)，，用颜色区分用颜色区分 j = 0, 1, … , n  1i = 0XY•并行矩阵乘算法并行矩阵乘算法再考虑在再考虑在p个处理器上并行计算个处理器上并行计算矩阵乘算法及其优化矩阵乘算法及其优化 每每个个处处理理器器访访问问矩矩阵阵X和和 Z各各 n/p行行以以及及整整个个Y，， 用用 n3/p次次乘乘加加运运算算来来完完成成对对Z的的 n2/p个个 元元素的计算素的计算 j = 0, 1, … , n  1i = 0XY•并行矩阵乘算法并行矩阵乘算法再考虑在再考虑在p个处理器上并行计算个处理器上并行计算矩阵乘算法及其优化矩阵乘算法及其优化 计算时间计算时间虽与虽与 p 成比成比例减例减,通信代通信代价却与价却与 p 成成比例增比例增,因交因交付给付给 p 个处个处理器缓存的理器缓存的总缓存行至总缓存行至少少是是n2/c +pn2/c j = 0, 1, … , n  1i = 0XY•并行矩阵乘算法并行矩阵乘算法再考虑在再考虑在p个处理器上并行计算个处理器上并行计算矩阵乘算法及其优化矩阵乘算法及其优化 p逼逼 近近 n时时，，计计算算时时间间为为O(n2)，，通通信信代代价价为为O(n3)，， 即即 在在内内存存和和处处理理器器之之间间传传送送数数据据的的总总线线成为瓶颈成为瓶颈 j = 0, 1, … , n  1i = 0XY•并行矩阵乘算法并行矩阵乘算法再考虑在再考虑在p个处理器上并行计算个处理器上并行计算矩阵乘算法及其优化矩阵乘算法及其优化 按按这这样样的的数数据据布布局局，，使使用用大大量量处处理理器器来来分分担担计计算算可可能能会会使使得得计计算算速速度降低度降低 j = 0, 1, … , n  1i = 0XY•矩阵乘算法的优化矩阵乘算法的优化 –复用在缓存而不是内存的数据，则数据局部性好复用在缓存而不是内存的数据，则数据局部性好矩阵乘算法及其优化矩阵乘算法及其优化 要要做做到到缓缓存存命命中中, 复复用用应应在在数数据据从从缓缓存存移移除除前发生前发生 j = 0, 1, … , n  1i = 0XY•矩阵乘算法的优化矩阵乘算法的优化 –复用在缓存而不是内存的数据，则数据局部性好复用在缓存而不是内存的数据，则数据局部性好矩阵乘算法及其优化矩阵乘算法及其优化 在在上上述述算算法法中中，，Y中中一一个个数数据据的的复复用用被被n2个个乘乘加加操操作作隔隔开开,Y中中一一个个缓缓存存行行的的复复用用 被被 n个个 乘乘加操作隔开加操作隔开 j = 0, 1, … , n  1i = 0XY•矩阵乘算法的优化矩阵乘算法的优化 –复用在缓存而不是内存的数据，则数据局部性好复用在缓存而不是内存的数据，则数据局部性好矩阵乘算法及其优化矩阵乘算法及其优化 在在一一个个处处理理器器上上，，数数据据只只有有被被本本处处理理器器复复用用时时才才可可能能出出现缓存命中现缓存命中 j = 0, 1, … , n  1i = 0XY•矩阵乘算法的优化矩阵乘算法的优化 –复用在缓存而不是内存的数据，则数据局部性好复用在缓存而不是内存的数据，则数据局部性好矩阵乘算法及其优化矩阵乘算法及其优化 改改变变数数据据布布局局和和语语句句执执行行次次序序都都可可能能改改进进缓缓存行的复用存行的复用 j = 0, 1, … , n  1i = 0XY•矩阵乘算法的优化矩阵乘算法的优化 –复用在缓存而不是内存的数据，则数据局部性好复用在缓存而不是内存的数据，则数据局部性好矩阵乘算法及其优化矩阵乘算法及其优化 但但分分块块计计算算是是重重排排循循环环中中迭迭代代次次序序的的较较好好方方法法，，能能极极大大地地改改进进程程序序的局部性的局部性 •分块计算的示意图分块计算的示意图1. X和和Y的灰色部分进行乘加运的灰色部分进行乘加运算，可得到算，可得到Z的灰色部分的结果的灰色部分的结果2. 灰色部分可以是一行灰色部分可以是一行(或列或列)，，也可以是若干行也可以是若干行(或列或列)3. 对对X和和Y进行分块，通过增加进行分块，通过增加循环来分块计算循环来分块计算bn矩阵乘算法及其优化矩阵乘算法及其优化X:Y:Z:•分块计算的示意图分块计算的示意图1. X和和Y的灰色部分进行乘加运的灰色部分进行乘加运算，可得到算，可得到Z的灰色部分的结果的灰色部分的结果2. 灰色部分可以是一行灰色部分可以是一行(或列或列)，，也可以是若干行也可以是若干行(或列或列)3. 对对X和和Y进行分块，通过增加进行分块，通过增加循环来分块计算循环来分块计算bn矩阵乘算法及其优化矩阵乘算法及其优化X:Y:Z:•分块计算的示意图分块计算的示意图1. X和和Y的灰色部分进行乘加运的灰色部分进行乘加运算，可得到算，可得到Z的灰色部分的结果的灰色部分的结果2. 灰色部分可以是一行灰色部分可以是一行(或列或列)，，也可以是若干行也可以是若干行(或列或列)3. 对对X和和Y进行分块，通过增加进行分块，通过增加循环来分块计算循环来分块计算bn矩阵乘算法及其优化矩阵乘算法及其优化X:Y:Z:•分块计算的示意图分块计算的示意图1. X和和Y的灰色部分进行乘加运的灰色部分进行乘加运算，可得到算，可得到Z的灰色部分的结果的灰色部分的结果2. 灰色部分可以是一行灰色部分可以是一行(或列或列)，，也可以是若干行也可以是若干行(或列或列)3. 对对X和和Y进行分块，通过增加进行分块，通过增加循环来分块计算循环来分块计算bn矩阵乘算法及其优化矩阵乘算法及其优化X:Y:Z:•矩阵乘算法的优化矩阵乘算法的优化 –仍假定仍假定n能由能由b整除整除, 假定假定Z的元素已经先行置初值的元素已经先行置初值–从从第第4到到8行行的的程程序序计计算算左左上上角角为为X[ii][kk]和和Y[kk] [jj]的两块对左上角为的两块对左上角为Z[ii][jj]的块的贡献的块的贡献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++) Z[i][j] = Z[i][j] +X[i][k]   Y[k][j];矩阵乘算法及其优化矩阵乘算法及其优化bn•矩阵乘算法的优化矩阵乘算法的优化 –适当选择适当选择b，使，使3个矩阵都有一个块可以装到缓存个矩阵都有一个块可以装到缓存–把把X或或Y一块取到缓存，会出现一块取到缓存，会出现b2/c次缓存未命中次缓存未命中–对对于于X和和Y的的一一对对块块，，第第4到到8行行的的程程序序完完成成b3次次乘乘加计算加计算–由由于于整整个个矩矩阵阵乘乘法法需需要要n3次次乘乘加加计计算算，，则则取取一一对对块到缓存的总次数是块到缓存的总次数是n3/b3–对对于于X和和Y的的一一对对块块会会有有2b2/c次次缓缓存存未未命命中中，，因因此此缓存未命中的总次数是缓存未命中的总次数是2b2/c   n3/b3 = 2n3/bc–和和先先前前的的O(n3)次次缓缓存存未未命命中中相相比比，，在在b较较大大时时，，2n3/bc能体现出分块方法的好处能体现出分块方法的好处矩阵乘算法及其优化矩阵乘算法及其优化•矩阵乘算法的优化矩阵乘算法的优化 –分分块块技技术术可可以以用用到到内内存存分分层层的的每每一一层层，，例例如如，，可可以把以把2 2矩阵乘的运算对象都保存在寄存器中矩阵乘的运算对象都保存在寄存器中–缓缓存存的的实实际际情情况况不不像像这这里里介介绍绍的的这这么么简简单单，，这这里里介绍的方法要依据缓存的约束进行调整介绍的方法要依据缓存的约束进行调整矩阵乘算法及其优化矩阵乘算法及其优化小小 结结•本讲座小结本讲座小结–算法分析是比较算法优劣的一个重要依据算法分析是比较算法优劣的一个重要依据–程程序序的的运运行行效效率率还还依依赖赖于于体体系系结结构构的的很很多多特特点点，，有有些些特特点点没没有有反反映映在在描描述述算算法法的的编编程程语语言言中中，，导导致仅基于编程语言的语义难以比较算法优劣致仅基于编程语言的语义难以比较算法优劣–熟熟悉悉体体系系结结构构、、算算法法分分析析、、编编程程语语言言、、编编译译原原理理的程序员更有可能写出效率较高的程序的程序员更有可能写出效率较高的程序•相关课程相关课程–算法基础、程序设计语言基础、编译原理、计算算法基础、程序设计语言基础、编译原理、计算机体系结构、并行计算机体系结构、并行计算小小 结结•研究方向研究方向–怎样从现代体系结构抽象出计算模型怎样从现代体系结构抽象出计算模型–在这些抽象模型上的算法分析方法在这些抽象模型上的算法分析方法。