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

1、面向计算机系统构造的程序优化面向计算机系统构造的程序优化计算机科学导论第七讲计算机科学导论第七讲计算机科学技术学院计算机科学技术学院陈意云陈意课课 程程 内内 容容 课程内容课程内容 围绕学科实际体系中的模型实际围绕学科实际体系中的模型实际, 程序实际和程序实际和计算实际计算实际 1. 模型实际关怀的问题模型实际关怀的问题 给定模型给定模型M，哪些问题可以由模型，哪些问题可以由模型M处理处理；如何比较模型的表达才干；如何比较模型的表达才干 2. 程序实际关怀的问题程序实际关怀的问题 给定模型给定模型M，如何用模型，如何用模型M处理问题处理问

2、题 包括程序设计范型、程序设计言语、程序设包括程序设计范型、程序设计言语、程序设计、方式语义、类型论、程序验证、程序分计、方式语义、类型论、程序验证、程序分析等析等 3. 计算实际关怀的问题计算实际关怀的问题给定模型给定模型M和一类问题和一类问题, 处理该类问题需多处理该类问题需多少资源少资源讲讲 座座 提提 纲纲 根本知识根本知识 内存分层构造、多处置器的体系构造内存分层构造、多处置器的体系构造 并行计算并行计算 并行计算的常见方式、循环级并行并行计算的常见方式、循环级并行 程序中的部分性程序中的部分性 时间部分性、空间部分性、代码和数据部分时间部分性、空间部分性、代码和数据部分性性 矩阵乘

3、算法及其优化矩阵乘算法及其优化 矩阵乘算法及分析、分块的矩阵乘算法及分矩阵乘算法及分析、分块的矩阵乘算法及分析析 围绕计算机体系构造而不是笼统模型来讨论围绕计算机体系构造而不是笼统模型来讨论基基 本本 知知 识识 计算机内存计算机内存 1. 初学编程时的认识初学编程时的认识 计算机的重要组成部分，由假设干内存单元计算机的重要组成部分，由假设干内存单元组成，用于存放程序和数据，可以按地址存组成，用于存放程序和数据，可以按地址存取取 2. 学习递归函数时的认识学习递归函数时的认识 例：快速排序例：快速排序 i n t a 11 ; v o i d quickSort(int m, int n) v

4、oid readArray()int i; int i; int partition(int m, int n) if(n m) main() i = partition(m, n); r e a d A r r a y ( ) ; a 0 = - 9 9 9 9 ; quickSort(m, i-1); a10 = 9999; quickSort(1, 9); quickSort(i+1, n); 基基 本本 知知 识识 计算机内存计算机内存需求分出一块来作为数据栈需求分出一块来作为数据栈main函数调用关系树函数调用关系树main栈栈基基 本本 知知 识识 计算机内存计算机内存需求分出一块

5、来作为数据栈需求分出一块来作为数据栈 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栈栈函数调用关系树函数调用关系树基基 本本 知知 识识 计算机内存

6、计算机内存需求分出一块来作为数据栈需求分出一块来作为数据栈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等函数恳求的空等函数恳求的空 间安排在堆上间安排在堆上内存的这种划分是经过操作内存的这种划分是经过

7、操作 系统和编译器实现的，不是在系统和编译器实现的，不是在 硬件层面上的划分硬件层面上的划分代代 码码静静 态态 数数 据据堆堆栈栈基基 本本 知知 识识 计算机内存分层计算机内存分层 内存方面的根本局限：构造非常快的存储器内存方面的根本局限：构造非常快的存储器或者非常大的存储器都是能够的，但是构造或者非常大的存储器都是能够的，但是构造不出既快又大的存储器不出既快又大的存储器 内存分层是指整个内存由内存分层是指整个内存由 几层不同速度和大小的存几层不同速度和大小的存 储器组成，并且最接近处储器组成，并且最接近处 理器的那一层最快最小理器的那一层最快最小虚拟内存虚拟内存(磁盘磁盘)物理内存物理内

8、存2级缓存级缓存1级缓存级缓存存放器存放器(处置器处置器)基基 本本 知知 识识 计算机内存分层计算机内存分层虚拟内存虚拟内存(磁盘磁盘)物理内存物理内存2级缓存级缓存1级缓存级缓存存放器存放器(处置器处置器)典型大小典型大小 2千兆字节千兆字节256兆兆2千兆字千兆字节节128千千4兆字兆字节节1664千字节千字节32字字典型访问时间典型访问时间315微秒微秒100150纳秒纳秒4060纳秒纳秒510纳秒纳秒1纳秒纳秒两边的数据已过时两边的数据已过时基基 本本 知知 识识 计算机内存分层计算机内存分层 程序的效率不仅取决于被执行的指令数，还程序的效率不仅取决于被执行的指令数，还取决于执行每条

9、指令需求多长时间，而执行取决于执行每条指令需求多长时间，而执行一条指令的时间区别非常可观一条指令的时间区别非常可观 假设一个程序的大部分存储假设一个程序的大部分存储 访问都落在这种分层的较访问都落在这种分层的较 快层次上，那么平均内存访快层次上，那么平均内存访 问时间就会缩短问时间就会缩短虚拟内存虚拟内存(磁盘磁盘)物理内存物理内存2级缓存级缓存1级缓存级缓存存放器存放器(处置器处置器)基基 本本 知知 识识 计算机内存分层计算机内存分层 存放器的内容由软件控制，虚拟内存由操作存放器的内容由软件控制，虚拟内存由操作系统管理，其他各层被自动管理。对于内存系统管理，其他各层被自动管理。对于内存访问

10、，计算机从底层开场逐层查找，访问，计算机从底层开场逐层查找， 直至定位数据为止直至定位数据为止 数据以块缓存行、页数据以块缓存行、页 为单位在相邻层次之间进为单位在相邻层次之间进 行传送。缓存行行传送。缓存行: 32256 字节字节, 页页: 464千字节千字节虚拟内存虚拟内存(磁盘磁盘)物理内存物理内存2级缓存级缓存1级缓存级缓存存放器存放器(处置器处置器)基基 本本 知知 识识 计算机内存分层计算机内存分层 现代计算机都设计成程序员不用关怀内存子现代计算机都设计成程序员不用关怀内存子系统的细节就可以写出正确的程序系统的细节就可以写出正确的程序 对应地，编程言语没有向对应地，编程言语没有向

11、程序员提供干涉数据进出程序员提供干涉数据进出 缓存的机制缓存的机制 数据密集型程序可从恰当数据密集型程序可从恰当 利用内存子系统中获益利用内存子系统中获益, 怎样做？怎样做？虚拟内存虚拟内存(磁盘磁盘)物理内存物理内存2级缓存级缓存1级缓存级缓存存放器存放器(处置器处置器)基基 本本 知知 识识 计算中潜在的并行性计算中潜在的并行性 数值运用，例如科学计算和信号处置，普通数值运用，例如科学计算和信号处置，普通都有很多潜在的并行都有很多潜在的并行 这些运用途置有大批量元素的数据构造，在这些运用途置有大批量元素的数据构造，在该构造每个元素上的运算相互独立，因此在该构造每个元素上的运算相互独立，因此

12、在不同元素上的运算可以并行执行，例如一些不同元素上的运算可以并行执行，例如一些矩阵运算矩阵运算 这些领域的程序普通有比较简单的控制构造这些领域的程序普通有比较简单的控制构造和规整的数据处置方式和规整的数据处置方式 下面引见支持并行计算的较为简单的体系构下面引见支持并行计算的较为简单的体系构造，和怎样写较优的代码造，和怎样写较优的代码 多处置器多处置器 对称多处置器的体系构造对称多处置器的体系构造多个高性多个高性能处置器能处置器可以集成可以集成在一块芯在一块芯片上片上必需在处置器的缓存中必需在处置器的缓存中找到它操作的大部分数找到它操作的大部分数据，以保证性能据，以保证性能基基 本本 知知 识识

13、二级二级缓存缓存内存内存总线总线二级二级缓存缓存二级二级缓存缓存二级二级缓存缓存一级一级缓存缓存一级一级缓存缓存一级一级缓存缓存一级一级缓存缓存处置器处置器处置器处置器处置器处置器处置器处置器 经过共享内存来进展通讯 多处置器多处置器 分布式内存机器分布式内存机器 两类机器：非均匀内存访问的两类机器：非均匀内存访问的机器和音讯传送的机器机器和音讯传送的机器 为获得良好的性能，软件都必为获得良好的性能，软件都必须有很好部分性须有很好部分性 基基 本本 知知 识识总线或其它互连总线或其它互连二级二级缓存缓存二级二级缓存缓存二级二级缓存缓存二级二级缓存缓存一级一级缓存缓存一级一级缓存缓存一级一级缓存

14、缓存一级一级缓存缓存处置器处置器处置器处置器处置器处置器处置器处置器部分部分内存内存部分部分内存内存部分部分内存内存部分部分内存内存在内存分在内存分层中又引层中又引入一层入一层处置器能处置器能迅速访问迅速访问本人的局本人的局部内存部内存 并行计算的常见方式并行计算的常见方式 义务并行：每个处置器执行不同的义务义务并行：每个处置器执行不同的义务 数据并行：把大义务分别成假设干个一样的数据并行：把大义务分别成假设干个一样的子义务子义务 并行运用性能衡量的两种规范并行运用性能衡量的两种规范 并行覆盖：整个计算中并行执行部分的百分并行覆盖：整个计算中并行执行部分的百分比比 并行粒度：处置器上无需和其它

15、处置器同步并行粒度：处置器上无需和其它处置器同步或通讯的计算量或通讯的计算量循环级并行循环级并行 循环级并行循环级并行 耗时的运用普通都运用大数组，导致程序中耗时的运用普通都运用大数组，导致程序中出现有许多次迭代的循环，这些迭代经常相出现有许多次迭代的循环，这些迭代经常相互独立，它们是并行计算的主要来源互独立，它们是并行计算的主要来源 可以把这类循环的大量迭代分到各处置器上可以把这类循环的大量迭代分到各处置器上循环级并行循环级并行 循环级并行循环级并行for (i = 0; i n; i+) /计算向量计算向量X和和YZi = Xi Yi; /对应元素差对应元素差的平方的平方Zi = Zi Z

16、i;变换成如下代码变换成如下代码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; / 数据并行的例子数据并行的例子循环级并行循环级并行 循环级并行循环级并行 对并行化来说，义务级不像循环级那样有吸对并行化来说，义务级不像循环级那样有吸引力引力 对一个程序而言，独立的义务数是一个常数对一个程序而言，独立的义务数是一个常数，它不像典型的循环那样，独立的计算单元，它不像典型的循环那样，独立的计算单元随迭代次数添加而添加随迭代次数添加而添加 义务通常

17、不是等规模的，因此很难保证一切义务通常不是等规模的，因此很难保证一切的处置器在一切时间都处于忙碌的处置器在一切时间都处于忙碌循环级并行循环级并行程序中的部分性程序中的部分性 部分性的表现部分性的表现 大多数程序的大部分时间在执行一小部分大多数程序的大部分时间在执行一小部分代码，代码， 并且仅涉及一小部分数据。传统的说法：程并且仅涉及一小部分数据。传统的说法：程序序90 的时间耗费在执行的时间耗费在执行10的代码上代码的部的代码上代码的部分性分性 程序经常包含许多决不会执行的代码，如由程序经常包含许多决不会执行的代码，如由组件和库构建的程序经常仅用所提供功能的组件和库构建的程序经常仅用所提供功能

18、的一小部分一小部分 程序运转时，通常仅一部分代码被真正执行程序运转时，通常仅一部分代码被真正执行。如处置非法输入和异常情况的代码，虽对。如处置非法输入和异常情况的代码，虽对程序的正确性至关重要，但它们很少被执行程序的正确性至关重要，但它们很少被执行 程序的大部分时间耗费在程序中最内层循环程序的大部分时间耗费在程序中最内层循环和深度递归的执行上和深度递归的执行上程序中的部分性程序中的部分性 两种部分性两种部分性 时间部分性时间部分性程序运转过程中被访问的内存单元存放程序运转过程中被访问的内存单元存放代码或数据在很短的时间内能够再次被程代码或数据在很短的时间内能够再次被程序访问序访问 空间部分性空

19、间部分性毗邻被访问单元的内存单元在很短的时间毗邻被访问单元的内存单元在很短的时间内会再内会再 次被访问次被访问 同一个缓存行上的元素一同被运用是空间部同一个缓存行上的元素一同被运用是空间部分性的一种重要方式。它能把缓存未命中次分性的一种重要方式。它能把缓存未命中次数降到最低，因此使得程度获得明显的加速数降到最低，因此使得程度获得明显的加速程序中的部分性程序中的部分性 部分性与内存分层部分性与内存分层 通常，最快的缓存没有大到足以把代码和数通常，最快的缓存没有大到足以把代码和数据同时放在其中据同时放在其中 从程序难以看出哪部分代码和数据会被频繁从程序难以看出哪部分代码和数据会被频繁运用运用 动态

20、调整最快缓存的内容不可防止动态调整最快缓存的内容不可防止 把最近运用的指令保管在缓存是一种较好的把最近运用的指令保管在缓存是一种较好的最优化利用内存分层的战略最优化利用内存分层的战略 改动数据规划或计算次序也可以改良程序数改动数据规划或计算次序也可以改良程序数据访问的时间和空间部分性据访问的时间和空间部分性 数据部分性数据部分性 计算向量计算向量X和和Y对应元素差的平方对应元素差的平方for (i = 0; i n; i+) / 该程序段对向该程序段对向量机来量机来 Zi = Xi Yi;/ 说是一种优化说是一种优化方式方式 for (i = 0; i n; i+) Zi = Zi Zi;fo

21、r (i = 0; i n; i+) / 有较好的数据有较好的数据部分性部分性 Zi = Xi Yi; Zi = Zi Zi;程序中的部分性程序中的部分性 数据部分性数据部分性 对行为主的数组对行为主的数组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 =

22、 ceil (n/M); for (i = bp; i min(n, b(p+1); i+) for (j = 0; j n; j+) Zi, j = 0;程序中的部分性程序中的部分性程序中的部分性程序中的部分性例：例： 一个构造体大数组一个构造体大数组分拆成假设干个数组分拆成假设干个数组 struct student int num10000; int num;char name1000020; char name20; struct student st10000; /非矩阵运算的例子非矩阵运算的例子假设是顺序处置每个构造体的多个域，左边方式的数假设是顺序处置每个构造体的多个域，左边方式的

23、数据部分性较好据部分性较好假设是先顺序处置每个构造的假设是先顺序处置每个构造的num域，再处置每个构域，再处置每个构造的造的name域，域，那么右边方式的数据部分性较好，那么右边方式的数据部分性较好最好是按左边方式编程，由编译器决议能否需求把数最好是按左边方式编程，由编译器决议能否需求把数据按右边方式规划据按右边方式规划 矩阵乘算法矩阵乘算法 计算计算Z = X Y，它们都是，它们都是nn的矩阵数组的矩阵数组 矩阵数据的规划是行为主矩阵数据的规划是行为主j = 0, 1, , n 1i = 0XY 当运用当运用X的一行的一行时，需求时，需求逐列访问逐列访问Y的一切的一切元素元素 矩阵乘算法及其

24、优化矩阵乘算法及其优化 矩阵乘算法矩阵乘算法 下面的算法是计算密集型的下面的算法是计算密集型的需完成需完成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;矩阵乘算法及其优化矩阵乘算法

25、及其优化 矩阵乘算法矩阵乘算法 假定在计算假定在计算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 =

26、 0.0; for (k = 0; k n; k+) Zij = Zij + Xik Ykj;矩阵乘算法及其优化矩阵乘算法及其优化j = 0, 1, , n 1i = 0XY 矩阵乘算法矩阵乘算法 当运用当运用X的一行时，需求逐列访问的一行时，需求逐列访问Y的一切元的一切元素素矩阵乘算法及其优化矩阵乘算法及其优化 完成Z一行 元素的计算过 程中，因取Y而出现的缓存 未命中次数最 好为n2/c (即Y 都可入缓存)灰色表示在缓存中灰色表示在缓存中j = 0, 1, , n 1i = 0XY 矩阵乘算法矩阵乘算法 当运用当运用X的一行时，需求逐列访问的一行时，需求逐列访问Y的一切元的一切元素素矩阵

27、乘算法及其优化矩阵乘算法及其优化 完成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的一行时，需求逐列访问的一行时，需

28、求逐列访问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 矩阵乘算法矩阵乘算法 当运用当运用

29、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

30、 矩阵乘算法矩阵乘算法 当运用当运用X的一行时，需求逐列访问的一行时，需求逐列访问Y的一切元的一切元素素矩阵乘算法及其优化矩阵乘算法及其优化灰色表示在缓存中灰色表示在缓存中 完成Z一行元素的计算过程中，因取Y而出现的缓存未命中次数最坏为n3 (缓存连Y的一列数据都不能驻留)j = 0, 1, , n 1i = 0XY 矩阵乘算法矩阵乘算法 当运用当运用X的一行时，需求逐列访问的一行时，需求逐列访问Y的一切元的一切元素素矩阵乘算法及其优化矩阵乘算法及其优化灰色表示在缓存中灰色表示在缓存中 完成Z一行元素的计算过程中，因取Y而出现的缓存未命中次数最坏为n3 (缓存连Y的一列数据都不能驻留) 矩阵乘

31、算法矩阵乘算法 继续对继续对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次,该算法一切缓存未命中为n

32、2/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行以及整个行以及

33、整个Y，用，用n3/p次乘加运算次乘加运算来完成对来完成对Z的的n2/p个元个元素的计算素的计算 j = 0, 1, , n 1i = 0XY 并行矩阵乘算法并行矩阵乘算法 再思索在再思索在p个处置器上并行计算个处置器上并行计算矩阵乘算法及其优化矩阵乘算法及其优化 计算时间计算时间虽与虽与 p 成比成比例减例减,通讯代通讯代价却与价却与 p 成成比例增比例增,因交因交付给付给 p 个处个处理器缓存的理器缓存的总缓存行至总缓存行至少 是少 是 n 2 / c +pn2/c j = 0, 1, , n 1i = 0XY 并行矩阵乘算法并行矩阵乘算法 再思索在再思索在p个处置器上并行计算个处置器上并

34、行计算矩阵乘算法及其优化矩阵乘算法及其优化 p 逼 近逼 近 n时，计算时时，计算时间为间为O(n2)，通讯代价，通讯代价为为O(n3)，即在内存和即在内存和处置器之间处置器之间传送数据的传送数据的总线成为瓶总线成为瓶颈颈 j = 0, 1, , n 1i = 0XY 并行矩阵乘算法并行矩阵乘算法 再思索在再思索在p个处置器上并行计算个处置器上并行计算矩阵乘算法及其优化矩阵乘算法及其优化 按这样的按这样的数据规划，数据规划，运用大量处运用大量处置器来分担置器来分担计算能够会计算能够会使得计算速使得计算速度降低度降低 j = 0, 1, , n 1i = 0XY 矩阵乘算法的优化矩阵乘算法的优化

35、 复用在缓存而不是内存的数据，那么数据部复用在缓存而不是内存的数据，那么数据部分性好分性好矩阵乘算法及其优化矩阵乘算法及其优化 要做到缓要做到缓存命中存命中, 复复用应在数据用应在数据从缓存移除从缓存移除前发生前发生 j = 0, 1, , n 1i = 0XY 矩阵乘算法的优化矩阵乘算法的优化 复用在缓存而不是内存的数据，那么数据部复用在缓存而不是内存的数据，那么数据部分性好分性好矩阵乘算法及其优化矩阵乘算法及其优化 在上述算在上述算法中，法中，Y中中一个数据的一个数据的复用被复用被n2个个乘加操作隔乘加操作隔开开,Y中一个中一个缓存行的复缓存行的复用 被用 被 n个 乘个 乘加操作隔开加操

36、作隔开 j = 0, 1, , n 1i = 0XY 矩阵乘算法的优化矩阵乘算法的优化 复用在缓存而不是内存的数据，那么数据部复用在缓存而不是内存的数据，那么数据部分性好分性好矩阵乘算法及其优化矩阵乘算法及其优化 在一个处在一个处置器上，数置器上，数据只需被本据只需被本处置器复用处置器复用时才能够出时才能够出现缓存命中现缓存命中 j = 0, 1, , n 1i = 0XY 矩阵乘算法的优化矩阵乘算法的优化 复用在缓存而不是内存的数据，那么数据部复用在缓存而不是内存的数据，那么数据部分性好分性好矩阵乘算法及其优化矩阵乘算法及其优化 改动数据改动数据规划和语句规划和语句执行次序都执行次序都能够改

37、良缓能够改良缓存行的复用存行的复用 j = 0, 1, , n 1i = 0XY 矩阵乘算法的优化矩阵乘算法的优化 复用在缓存而不是内存的数据，那么数据部复用在缓存而不是内存的数据，那么数据部分性好分性好矩阵乘算法及其优化矩阵乘算法及其优化 但分块计但分块计算是重排循算是重排循环中迭代次环中迭代次序的较好方序的较好方法，能极大法，能极大地改良程序地改良程序的部分性的部分性 分块计算的表示图分块计算的表示图1. X和和Y的灰色部分进展的灰色部分进展乘加运乘加运 算，可得到算，可得到Z的灰色部分的的灰色部分的结果结果2. 灰色部分可以是一行灰色部分可以是一行(或列或列)， 也可以是假设干行也可以是

38、假设干行(或列或列)3. 对对X和和Y进展分块，经进展分块，经过添加过添加 循环来分块计算循环来分块计算bn矩阵乘算法及其优化矩阵乘算法及其优化X:Y:Z: 分块计算的表示图分块计算的表示图1. X和和Y的灰色部分进展的灰色部分进展乘加运乘加运 算，可得到算，可得到Z的灰色部分的的灰色部分的结果结果2. 灰色部分可以是一行灰色部分可以是一行(或列或列)， 也可以是假设干行也可以是假设干行(或列或列)3. 对对X和和Y进展分块，经进展分块，经过添加过添加 循环来分块计算循环来分块计算bn矩阵乘算法及其优化矩阵乘算法及其优化X:Y:Z: 分块计算的表示图分块计算的表示图1. X和和Y的灰色部分进展

39、的灰色部分进展乘加运乘加运 算，可得到算，可得到Z的灰色部分的的灰色部分的结果结果2. 灰色部分可以是一行灰色部分可以是一行(或列或列)， 也可以是假设干行也可以是假设干行(或列或列)3. 对对X和和Y进展分块，经进展分块，经过添加过添加 循环来分块计算循环来分块计算bn矩阵乘算法及其优化矩阵乘算法及其优化X:Y:Z: 分块计算的表示图分块计算的表示图1. X和和Y的灰色部分进展的灰色部分进展乘加运乘加运 算，可得到算，可得到Z的灰色部分的的灰色部分的结果结果2. 灰色部分可以是一行灰色部分可以是一行(或列或列)， 也可以是假设干行也可以是假设干行(或列或列)3. 对对X和和Y进展分块，经进展分块，经过添加过添加 循环来分块计算循环来分块计算bn矩阵乘算法及其优化矩阵乘算法及其优化X:Y:Z: 矩阵乘算法的优化矩阵乘算法的优化 仍假定仍假定n能由能由b