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

面向计算机系统结构的程序优化 计算机科学导论第七讲,计算机科学技术学院 陈意云,课 程 内 容,课程内容 围绕学科理论体系中的模型理论, 程序理论和计算理论 1. 模型理论关心的问题 给定模型M，哪些问题可以由模型M解决；如何比较模型的表达能力 2. 程序理论关心的问题 给定模型M，如何用模型M解决问题 包括程序设计范型、程序设计语言、程序设计、形式语义、类型论、程序验证、程序分析等 3. 计算理论关心的问题 给定模型M和一类问题, 解决该类问题需多少资源,讲 座 提 纲,基本知识 内存分层结构、多处理器的体系结构 并行计算 并行计算的常见方式、循环级并行 程序中的局部性 时间局部性、空间局部性、代码和数据局部性 矩阵乘算法及其优化 矩阵乘算法及分析、分块的矩阵乘算法及分析 围绕计算机体系结构而不是抽象模型来讨论,基 本 知 识,计算机内存 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); ,基 本 知 识,计算机内存 需要分出一块来作为数据栈,main,函数调用关系树,基 本 知 识,计算机内存 需要分出一块来作为数据栈,函数调用关系树,基 本 知 识,计算机内存 需要分出一块来作为数据栈,函数调用关系树,基 本 知 识,计算机内存 需要分出一块来作为数据栈,函数调用关系树,基 本 知 识,计算机内存 需要分出一块来作为数据栈,函数调用关系树,基 本 知 识,计算机内存 1. 初学编程时的认识 2. 学习递归函数时的认识 3. 学习动态存储分配时的认识 通过malloc等函数申请的空 间安排在堆上 内存的这种划分是通过操作 系统和编译器实现的，不是在 硬件层面上的划分,基 本 知 识,计算机内存分层 内存方面的基本局限：构造非常快的存储器或者非常大的存储器都是可能的，但是构造不出既快又大的存储器 内存分层是指整个内存由 几层不同速度和大小的存 储器组成，并且最靠近处 理器的那一层最快最小,基 本 知 识,计算机内存分层,两边的数据已过时,基 本 知 识,计算机内存分层 程序的效率不仅取决于被执行的指令数，还取决于执行每条指令需要多长时间，而执行一条指令的时间区别非常可观 若一个程序的大部分存储 访问都落在这种分层的较 快层次上，则平均内存访 问时间就会缩短,基 本 知 识,计算机内存分层 寄存器的内容由软件控制，虚拟内存由操作系统管理，其他各层被自动管理。对于内存访问，计算机从底层开始逐层查找， 直至定位数据为止 数据以块（缓存行、页） 为单位在相邻层次之间进 行传送。缓存行: 32256 字节, 页: 464千字节,基 本 知 识,计算机内存分层 现代计算机都设计成程序员不用关心内存子系统的细节就可以写出正确的程序 对应地，编程语言没有向 程序员提供干预数据进出 缓存的机制 数据密集型程序可从恰当 利用内存子系统中获益, 怎么做？,基 本 知 识,计算中潜在的并行性 数值应用，例如科学计算和信号处理，一般都有很多潜在的并行 这些应用处理有大批量元素的数据结构，在该结构每个元素上的运算相互独立，因而在不同元素上的运算可以并行执行，例如一些矩阵运算 这些领域的程序一般有比较简单的控制结构和规整的数据处理模式 下面介绍支持并行计算的较为简单的体系结构，和怎样写较优的代码,多处理器 对称多处理器的体系结构,多个高性 能处理器 可以集成 在一块芯 片上,必须在处理器的缓存中 找到它操作的大部分数 据，以保证性能,基 本 知 识,通过共 享内存来 进行通信,多处理器 分布式内存机器,两类机器：非均匀内存访问的 机器和消息传递的机器 为获得良好的性能，软件都必 须有很好局部性,基 本 知 识,在内存分 层中又引 入一层,处理器能 迅速访问 自己的局 部内存,并行计算的常见方式 任务并行：每个处理器执行不同的任务 数据并行：把大任务分别成若干个相同的子任务 并行应用性能衡量的两种标准 并行覆盖：整个计算中并行执行部分的百分比 并行粒度：处理器上无需和其它处理器同步或通信的计算量,循环级并行,循环级并行 耗时的应用一般都使用大数组，导致程序中出现有许多次迭代的循环，这些迭代经常相互独立，它们是并行计算的主要来源 可以把这类循环的大量迭代分到各处理器上,循环级并行,循环级并行 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; / 数据并行的例子,循环级并行,循环级并行 对并行化来说，任务级不像循环级那样有吸引力 对一个程序而言，独立的任务数是一个常数，它不像典型的循环那样，独立的计算单元随迭代次数增加而增加 任务通常不是等规模的，因此很难保证所有的处理器在所有时间都处于忙碌,循环级并行,程序中的局部性,局部性的表现 大多数程序的大部分时间在执行一小部分代码， 并且仅涉及一小部分数据。传统的说法：程序90 的时间消耗在执行10的代码上（代码的局部性） 程序经常包含许多决不会执行的代码，如由组件和库构建的程序经常仅用所提供功能的一小部分 程序运行时，通常仅一部分代码被真正执行。如处理非法输入和异常情况的代码，虽对程序的正确性至关重要，但它们很少被执行 程序的大部分时间消耗在程序中最内层循环和深度递归的执行上,程序中的局部性,两种局部性 时间局部性 程序运行过程中被访问的内存单元（存放代码或数据）在很短的时间内可能再次被程序访问 空间局部性 毗邻被访问单元的内存单元在很短的时间内会再 次被访问 同一个缓存行上的元素一起被使用是空间局部性的一种重要形式。它能把缓存未命中次数降到最低，因而使得程度获得明显的加速,程序中的局部性,局部性与内存分层 通常，最快的缓存没有大到足以把代码和数据同时放在其中 从程序难以看出哪部分代码和数据会被频繁使用 动态调整最快缓存的内容不可避免 把最近使用的指令保存在缓存是一种较好的最优化利用内存分层的策略 改变数据布局或计算次序也可以改进程序数据访问的时间和空间局部性,数据局部性 计算向量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 = 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域，再处理每个结构的name域，则右边方式的数据局部性较好 最好是按左边方式编程，由编译器决定是否需要把数据按右边方式布局,矩阵乘算法 计算Z = X Y，它们都是nn的矩阵（数组） 矩阵数据的布局是行为主,当使用X的一行时，需要逐列访问Y的所有元素,矩阵乘算法及其优化,矩阵乘算法 下面的算法是计算密集型的 需完成n3次操作 (1次操作指1次乘和1次加运算， 简称乘加操作) Z的每个元素的计算 是独立的, 因此它们 可以并行计算 先考虑在单处理器 上顺序执行,X, Y, Z: nn for (i = 0; i n; i+) for (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; k+) Zij = Zij + Xik Ykj; ,矩阵乘算法及其优化,矩阵乘算法 当使用X的一行时，需要逐列访问Y的所有元素,矩阵乘算法及其优化,完成Z一行 元素的计算过 程中，因取Y而出现的缓存 未命中次数最 好为n2/c (即Y 都可入缓存),灰色表示在缓存中,矩阵乘算法 当使用X的一行时，需要逐列访问Y的所有元素,矩阵乘算法及其优化,完成Z一行 元素的计算过 程中，因取Y而出现的缓存 未命中次数最 好为n2/c (即Y 都可入缓存),灰色表示在缓存中,矩阵乘算法 当使用X的一行时，需要逐列访问Y的所有元素,矩阵乘算法及其优化,完成Z一行 元素的计算过 程中，因取Y而出现的缓存 未命中次数最 好为n2/c (即Y 都可入缓存),灰色表示在缓存中,矩阵乘算法 当使用X的一行时，需要逐列访问Y的所有元素,矩阵乘算法及其优化,完成Z一行 元素的计算过 程中，因取Y而出现的缓存 未命中次数最 好为n2/c (即Y 都可入缓存),灰色表示在缓存中,矩阵乘算法 当使用X的一行时，需要逐列访问Y的所有元素,矩阵乘算法及其优化,完成Z一行 元素的计算过 程中，因取Y而出现的缓存 未命中次数最 好为n2/c (即Y 都可入缓存),灰色表示在缓存中,矩阵乘算法 当使用X的一行时，需要逐列访问Y的所有元素,矩阵乘算法及其优化,完成Z一行 元素的计算过 程中，因取Y而出现的缓存 未命中次数最 好为n2/c (即Y 都可入缓存),灰色表示在缓存中,矩阵乘算法 当使用X的一行时，需要逐列访问Y的所有元素,矩阵乘算法及其优化,完成Z一行 元素的计算过 程中，因取Y而出现的缓存 未命中次数最 坏为n3 (缓存 连Y的一列数 据都不能驻留),灰色表示在缓存中,矩阵乘算法 当使用X的一行时，需要逐列访问Y的所有元素,矩阵乘算法及其优化,灰色表示在缓存中,完成Z一行 元素的计算过 程中，因取Y而出现的缓存 未命中次数最 坏为n3 (缓存 连Y的一列数 据都不能驻留),矩阵乘算法 当使用X的一行时，需要逐列访问Y的所有元素,矩阵乘算法及其优化,灰色表示在缓存中,完成Z一行 元素的计算过 程中，因取Y而出现的缓存 未命中次数最 坏为n3 (缓存 连Y的一列数 据都不能驻留),矩阵乘算法 继续对i =1, 2, , n 1逐步完成最外循环的过程中,矩阵乘算法及其优化,完成Z所有 各行元素的计 算过程中，因 取Y而出现的 缓存未命中次 数最好是n2/c 次。该算法所 有缓存未命中 为n2/c +n2/c次,矩阵乘算法 继续对i =1, 2, , n 1逐步完成最外循环的过程中,矩阵乘算法及其优化,完成Z所有 各行元素的计 算过程中，因 取Y而出现的 缓存未命中次 数最坏是n3次, 该算法所有缓 存未命中为 n2/c + n3次,并行矩阵乘算法 再考虑在p个处理器上并行计算,矩阵乘算法及其优化,把Z不同行的计算指派到不同处理器，每个处理器计算Z的连续n/p行(假定n可由p整除)，用颜色区分,并行矩阵乘算法 再考虑在p个处理器上并行计算,矩阵乘算法及其优化,每个处理器访问矩阵X和Z各n/p行以及整个Y，用n3/p次乘加运算来完成对Z的n2/p个元素的计算,并行矩阵乘算法 再考虑在p个处理器上并行计算,矩阵乘算法及其优化,计算时间 虽与 p 成比 例减,通信代 价却与 p 成 比例增,因交 付给 p 个处 理器缓存的 总缓存行至 少是n2/c +pn2/c,并行矩阵乘算法 再考虑在p个处理器上并行计算,矩阵乘算法及其优化,p逼近n时，计算时间为O(n2)，通信代价为O(n3)，即在内存和处理器之间传送数据的总线成为瓶颈,并行矩阵乘算法 再考虑在p个处理器上并行计算,矩阵乘算法及其优化,按这样的数据布局，使用大量处理器来分担计算可能会使得计算速度降低,矩阵乘算法的优化 复用在缓存而不是内存的数据，则数据局部性好,矩阵乘算法及其优化,要做到缓存命中, 复用应在数据从缓存移除前发生,矩阵乘算法的优化 复用在缓存而不是内存的数据，则数据局部性好,矩阵乘算法及其优化,在上述算法中，Y中一个数据的复用被n2个乘加操作隔开,Y中一个缓存行的复用被n个乘加操作隔开,矩阵乘算法的优化 复用在缓存而不是内存的数据，则数据局部性好,矩阵乘算法及其优化,在一个处理器上，数据只有被本处理器复用时才可能出现缓存命中,矩阵乘算法的优化 复用在缓存而不是内存的数据，则数据局部性好,矩阵乘算法及其优化,改变数据布局和语句执行次序都可能改进缓存行的复用,矩阵乘算法的优化 复用在缓存而不是内存的数据，则数据局部性好,矩阵乘算法及其优化,但分块计算是重排循环中迭代次序的较好方法，能极大地改进程序的局部性,分块计算的示意图 1. X和Y的灰色部分进行乘加运 算，可得到Z的灰色部分的结果 2. 灰色部分可以是一行(或列)， 也可以是若干行(或列) 3. 对X和Y进行分块，通过增加 循环来分块计算,矩阵乘算法及其优化,Z:,分块计算的示意图 1. X和Y的灰色部分进行乘加运 算，可得到Z的灰色部分的结果 2. 灰色部分可以是一行(或列)， 也可以是若干行(或列) 3. 对X和Y进行分块，通过增加 循环来分块计算,矩阵乘算法及其优化,Z:,分块计算的示意图 1. X和Y的灰色部分进行乘加运 算，可得到Z的灰色部分的结果 2. 灰色部分可以是一行(或列)， 也可以是若干行(或列) 3. 对X和Y进行分块，通过增加 循环来分块计算,矩阵乘算法及其优化,Z:,分块计算的示意图 1. X和Y的灰色部分进行乘加运 算，可得到Z的灰色部分的结果 2. 灰色部分可以是一行(或列)， 也可以是若干行(或列) 3. 对X和Y进行分块，通过增加 循环来分块计算,矩阵乘算法及其优化,Z:,矩阵乘算法的优化 仍假定n能由b整除, 假定Z的元素已经先行置初值 从第4到8行的程序计算左上角为Xiikk和Ykk jj的两块对左上角为Ziijj的块的贡献,for (ii = 0; ii n; ii