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

《面向计算机系统结构的程序优化计算机科学导论第七讲.ppt》由会员分享，可在线阅读，更多相关《面向计算机系统结构的程序优化计算机科学导论第七讲.ppt（61页珍藏版）》请在三一文库上搜索。

1、面向计算机系统结构的程序优化 计算机科学导论第七讲 计算机科学技术学院 陈意云 0551-63607043 课 程 内 容 课程内容 围绕学科理论体系中的模型理论, 程序理论和计算理论 1. 模型理论关心的问题 给定模型M，哪些问题可以由模型M解决；如何比 较模型的表达能力 2. 程序理论关心的问题 给定模型M，如何用模型M解决问题 包括程序设计范型、程序设计语言、程序设计、 形式语义、类型论、程序验证、程序分析等 3. 计算理论关心的问题 给定模型M和一类问题, 解决该类问题需多少资源 讲 座 提 纲 基本知识 内存分层结构、多处理器的体系结构 并行计算 并行计算的常见方式、循环级并行 程

2、序中的局部性 时间局部性、空间局部性、代码和数据局部性 矩阵乘算法及其优化 矩阵乘算法及分析、分块的矩阵乘算法及分析 围绕计算机体系结构而不是抽象模型来讨论 基 本 知 识 计算机内存 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); re

3、adArray(); a0 = -9999; quickSort(m, i-1); a10 = 9999; quickSort(1, 9); quickSort(i+1, n); 基 本 知 识 计算机内存 需要分出一块来作为数据栈 main 函数调用关系树 main 栈 基 本 知 识 计算机内存 需要分出一块来作为数据栈 main r 函数调用关系树 main int i r ( ) 栈 基 本 知 识 计算机内存 需要分出一块来作为数据栈 main q(1,9)r 函数调用关系树 main int i q (1, 9) int m, n 栈 基 本 知 识 计算机内存 需要分出一块来作为

4、数据栈 main q(1,9)r p(1,9)q(1,3) main int i q (1, 9) int m, n int i q (1, 3) int m, n 栈 函数调用关系树 基 本 知 识 计算机内存 需要分出一块来作为数据栈 main q(1,9)r p(1,9)q(1,3) q(1,0) p(1,3) main int i q (1, 9) int m, n int i q (1, 3) int m, n int i q (1, 0) int m, n 栈 函数调用关系树 基 本 知 识 计算机内存 1. 初学编程时的认识 2. 学习递归函数时的认识 3. 学习动态存储分配时的

5、认识 通过malloc等函数申请的空 间安排在堆上 内存的这种划分是通过操作 系统和编译器实现的，不是在 硬件层面上的划分 代 码 静 态 数 据 堆 栈 基 本 知 识 计算机内存分层 内存方面的基本局限：构造非常快的存储器或者 非常大的存储器都是可能的，但是构造不出既快 又大的存储器 内存分层是指整个内存由 几层不同速度和大小的存 储器组成，并且最靠近处 理器的那一层最快最小 虚拟内存(磁盘) 物理内存 2级缓存 1级缓存 寄存器(处理器) 基 本 知 识 计算机内存分层 虚拟内存(磁盘) 物理内存 2级缓存 1级缓存 寄存器(处理器) 典型大小 2千兆字节 256兆2千兆字节 128千4

6、兆字节 1664千字节 32字 典型访问时间 315微秒 100150纳秒 4060纳秒 510纳秒 1纳秒 两边的数据已过时 基 本 知 识 计算机内存分层 程序的效率不仅取决于被执行的指令数，还取决 于执行每条指令需要多长时间，而执行一条指令 的时间区别非常可观 若一个程序的大部分存储 访问都落在这种分层的较 快层次上，则平均内存访 问时间就会缩短 虚拟内存(磁盘) 物理内存 2级缓存 1级缓存 寄存器(处理器) 基 本 知 识 计算机内存分层 寄存器的内容由软件控制，虚拟内存由操作系统 管理，其他各层被自动管理。对于内存访问，计 算机从底层开始逐层查找， 直至定位数据为止 数据以块（缓存

7、行、页） 为单位在相邻层次之间进 行传送。缓存行: 32256 字节, 页: 464千字节 虚拟内存(磁盘) 物理内存 2级缓存 1级缓存 寄存器(处理器) 基 本 知 识 计算机内存分层 现代计算机都设计成程序员不用关心内存子系统 的细节就可以写出正确的程序 对应地，编程语言没有向 程序员提供干预数据进出 缓存的机制 数据密集型程序可从恰当 利用内存子系统中获益, 怎么做？ 虚拟内存(磁盘) 物理内存 2级缓存 1级缓存 寄存器(处理器) 基 本 知 识 计算中潜在的并行性 数值应用，例如科学计算和信号处理，一般都有 很多潜在的并行 这些应用处理有大批量元素的数据结构，在该结 构每个元素上的

8、运算相互独立，因而在不同元素 上的运算可以并行执行，例如一些矩阵运算 这些领域的程序一般有比较简单的控制结构和规 整的数据处理模式 下面介绍支持并行计算的较为简单的体系结构， 和怎样写较优的代码 多处理器 对称多处理器的体系结构 多个高性 能处理器 可以集成 在一块芯 片上 必须在处理器的缓存中 找到它操作的大部分数 据，以保证性能 基 本 知 识 二级 缓存 内存 总线 二级 缓存 二级 缓存 二级 缓存 一级 缓存 一级 缓存 一级 缓存 一级 缓存 处理器处理器处理器 处理器 通过共 享内存来 进行通信 多处理器 分布式内存机器 两类机器：非均匀内存访问的 机器和消息传递的机器 为获得良

9、好的性能，软件都必 须有很好局部性 基 本 知 识 总线或其它互连 二级 缓存 二级 缓存 二级 缓存 二级 缓存 一级 缓存 一级 缓存 一级 缓存 一级 缓存 处理器处理器处理器处理器 局部 内存 局部 内存 局部 内存 局部 内存 在内存分 层中又引 入一层 处理器能 迅速访问 自己的局 部内存 并行计算的常见方式 任务并行：每个处理器执行不同的任务 数据并行：把大任务分别成若干个相同的子任务 并行应用性能衡量的两种标准 并行覆盖：整个计算中并行执行部分的百分比 并行粒度：处理器上无需和其它处理器同步或通 信的计算量 循环级并行 循环级并行 耗时的应用一般都使用大数组，导致程序中出现 有

10、许多次迭代的循环，这些迭代经常相互独立， 它们是并行计算的主要来源 可以把这类循环的大量迭代分到各处理器上 循环级并行 循环级并行 for (i = 0; i n; i+) /计算向量X和Y Zi = 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; / 数据并行的例子 循环级并行 循环级并行 对并行化来说，任务级不像循环级那样有吸引力 对一个程序而言，独立的任务数是一个常数

11、，它 不像典型的循环那样，独立的计算单元随迭代次 数增加而增加 任务通常不是等规模的，因此很难保证所有的处 理器在所有时间都处于忙碌 循环级并行 程序中的局部性 局部性的表现 大多数程序的大部分时间在执行一小部分代码， 并且仅涉及一小部分数据。传统的说法：程序90 的时间消耗在执行10的代码上（代码的局部性） 程序经常包含许多决不会执行的代码，如由组件 和库构建的程序经常仅用所提供功能的一小部分 程序运行时，通常仅一部分代码被真正执行。如 处理非法输入和异常情况的代码，虽对程序的正 确性至关重要，但它们很少被执行 程序的大部分时间消耗在程序中最内层循环和深 度递归的执行上 程序中的局部性 两种

12、局部性 时间局部性 程序运行过程中被访问的内存单元（存放代码或 数据）在很短的时间内可能再次被程序访问 空间局部性 毗邻被访问单元的内存单元在很短的时间内会再 次被访问 同一个缓存行上的元素一起被使用是空间局部性 的一种重要形式。它能把缓存未命中次数降到最 低，因而使得程度获得明显的加速 程序中的局部性 局部性与内存分层 通常，最快的缓存没有大到足以把代码和数据同 时放在其中 从程序难以看出哪部分代码和数据会被频繁使用 动态调整最快缓存的内容不可避免 把最近使用的指令保存在缓存是一种较好的最优 化利用内存分层的策略 改变数据布局或计算次序也可以改进程序数据访 问的时间和空间局部性 数据局部性

13、计算向量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; 程序中的局部性 数据局部性 对行为主的数组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 =

14、 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; 程序中的局部性 程序中的局部性 例： 一个结构体大数组分拆成若干个数组 struct student int num10000; int num;char name1000020; char name20; struct student st10000; /非矩阵运算的例子 若是顺序处理每个结构体的多个域，左边方式的数 据局部性较好 若是先顺序处理每个结构的num域

15、，再处理每个结 构的name域，则右边方式的数据局部性较好 最好是按左边方式编程，由编译器决定是否需要把 数据按右边方式布局 矩阵乘算法 计算Z = X Y，它们都是nn的矩阵（数组） 矩阵数据的布局是行为主 j = 0, 1, , n 1 i = 0 XY 当使用 X的一行 时，需要 逐列访问 Y的所有 元素 矩阵乘算法及其优化 矩阵乘算法 下面的算法是计算密集型的 需完成n3次操作 (1次操作指1次乘和1次加运算， 简称乘加操作) Z的每个元素的计算 是独立的, 因此它们 可以并行计算 先考虑在单处理器 上顺序执行 X, Y, Z: nn for (i = 0; i n; i+) for

16、(j = 0; j n; j+) Zij = 0.0; for (k = 0; k n; k+) Zij = Zij + Xik Ykj; 矩阵乘算法及其优化 矩阵乘算法 假定在计算Zij的过程中, 其值保存在寄存器中, 则计算过程中不访问其内存单元，仅最后存储1次 假定c个元素正好占满 一个缓存行，则X的 1行散布在n/c个缓存 行上。令c = 4, n = 12 假定缓存足以放下X所 有的缓存行，则读入X 出现n2/c次缓存未命中 X, Y, Z: nn for (i = 0; i n; i+) for (j = 0; j n; j+) Zij = 0.0; for (k = 0; k n

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

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

19、完成Z一行 元素的计算过 程中，因取Y 而出现的缓 存 未命中次数最 好为n2/c (即Y 都可入缓存) 灰色表示在缓存中 j = 0, 1, , n 1 i = 0 XY 矩阵乘算法 当使用X的一行时，需要逐列访问Y的所有元素 矩阵乘算法及其优化 完成Z一行 元素的计算过 程中，因取Y 而出现的缓 存 未命中次数最 好为n2/c (即Y 都可入缓存) 灰色表示在缓存中 j = 0, 1, , n 1 i = 0 XY 矩阵乘算法 当使用X的一行时，需要逐列访问Y的所有元素 矩阵乘算法及其优化 完成Z一行 元素的计算过 程中，因取Y 而出现的缓 存 未命中次数最 坏为n3 (缓存 连Y的一列数

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

21、n 1逐步完成最外循环的过程中 j = 0, 1, , n 1 i = 0 XY 矩阵乘算法及其优化 完成Z所有 各行元素的计 算过程中，因 取Y而出现的 缓存未命中次 数最好是n2/c 次。该算法所 有缓存未命中 为n2/c +n2/c次 矩阵乘算法 继续对i =1, 2, , n 1逐步完成最外循环的过程中 j = 0, 1, , n 1 i = 0 XY 矩阵乘算法及其优化 完成Z所有 各行元素的计 算过程中，因 取Y而出现的 缓存未命中次 数最坏是n3次, 该算法所有缓 存未命中为 n2/c + n3次 j = 0, 1, , n 1 i = 0 XY 并行矩阵乘算法 再考虑在p个处理

22、器上并行计算 矩阵乘算法及其优化 把Z不同 行的计算指 派到不同处 理器，每个 处理器计算 Z的连续n/p 行(假定n可 由p整除)， 用颜色区分 j = 0, 1, , n 1 i = 0 XY 并行矩阵乘算法 再考虑在p个处理器上并行计算 矩阵乘算法及其优化 每个处理 器访问矩阵 X和Z各n/p 行以及整个 Y，用n3/p 次乘加运算 来完成对Z 的n2/p个元 素的计算 j = 0, 1, , n 1 i = 0 XY 并行矩阵乘算法 再考虑在p个处理器上并行计算 矩阵乘算法及其优化 计算时间 虽与 p 成比 例减,通信代 价却与 p 成 比例增,因交 付给 p 个处 理器缓存的 总缓存

23、行至 少是n2/c +pn2/c j = 0, 1, , n 1 i = 0 XY 并行矩阵乘算法 再考虑在p个处理器上并行计算 矩阵乘算法及其优化 p逼近n 时，计算时 间为O(n2)， 通信代价为 O(n3)，即在 内存和处理 器之间传送 数据的总线 成为瓶颈 j = 0, 1, , n 1 i = 0 XY 并行矩阵乘算法 再考虑在p个处理器上并行计算 矩阵乘算法及其优化 按这样的 数据布局， 使用大量处 理器来分担 计算可能会 使得计算速 度降低 j = 0, 1, , n 1 i = 0 XY 矩阵乘算法的优化 复用在缓存而不是内存的数据，则数据局部性好 矩阵乘算法及其优化 要做到缓

24、 存命中, 复 用应在数据 从缓存移除 前发生 j = 0, 1, , n 1 i = 0 XY 矩阵乘算法的优化 复用在缓存而不是内存的数据，则数据局部性好 矩阵乘算法及其优化 在上述算 法中，Y中 一个数据的 复用被n2个 乘加操作隔 开,Y中一个 缓存行的复 用被n个乘 加操作隔开 j = 0, 1, , n 1 i = 0 XY 矩阵乘算法的优化 复用在缓存而不是内存的数据，则数据局部性好 矩阵乘算法及其优化 在一个处 理器上，数 据只有被本 处理器复用 时才可能出 现缓存命中 j = 0, 1, , n 1 i = 0 XY 矩阵乘算法的优化 复用在缓存而不是内存的数据，则数据局部性

25、好 矩阵乘算法及其优化 改变数据 布局和语句 执行次序都 可能改进缓 存行的复用 j = 0, 1, , n 1 i = 0 XY 矩阵乘算法的优化 复用在缓存而不是内存的数据，则数据局部性好 矩阵乘算法及其优化 但分块计 算是重排循 环中迭代次 序的较好方 法，能极大 地改进程序 的局部性 分块计算的示意图 1. X和Y的灰色部分进行乘加运 算，可得到Z的灰色部分的结果 2. 灰色部分可以是一行(或列)， 也可以是若干行(或列) 3. 对X和Y进行分块，通过增加 循环来分块计算 b n 矩阵乘算法及其优化 X:Y: Z: 分块计算的示意图 1. X和Y的灰色部分进行乘加运 算，可得到Z的灰色

26、部分的结果 2. 灰色部分可以是一行(或列)， 也可以是若干行(或列) 3. 对X和Y进行分块，通过增加 循环来分块计算 b n 矩阵乘算法及其优化 X:Y: Z: 分块计算的示意图 1. X和Y的灰色部分进行乘加运 算，可得到Z的灰色部分的结果 2. 灰色部分可以是一行(或列)， 也可以是若干行(或列) 3. 对X和Y进行分块，通过增加 循环来分块计算 b n 矩阵乘算法及其优化 X:Y: Z: 分块计算的示意图 1. X和Y的灰色部分进行乘加运 算，可得到Z的灰色部分的结果 2. 灰色部分可以是一行(或列)， 也可以是若干行(或列) 3. 对X和Y进行分块，通过增加 循环来分块计算 b n

27、 矩阵乘算法及其优化 X:Y: Z: 矩阵乘算法的优化 仍假定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; 矩阵乘

28、算法及其优化 b n 矩阵乘算法的优化 适当选择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能体现出分块方法的好处 矩阵乘算法及其优化 矩阵乘算法的优化 分块技术可以用到内存分层的每一层，例如，可 以把22矩阵乘的运算对象都保存在寄存器中 缓存的实际情况不像这里介绍的这么简单，这里 介绍的方法要依据缓存的约束进行调整 矩阵乘算法及其优化 小 结 本讲座小结 算法分析是比较算法优劣的一个重要依据 程序的运行效率还依赖于体系结构的很多特点， 有些特点没有反映在描述算法的编程语言中，导 致仅基于编程语言的语义难以比较算法优劣 熟悉体系结构、算法分析、编程语言、编译原理 的程序员更有可能写出效率较高的程序 相关课程 算法基础、程序设计语言基础、编译原理、计算 机体系结构、并行计算 小 结 研究方向 怎样从现代体系结构抽象出计算模型 在这些抽象模型上的算法分析方法