面向计算机体系结构的程序优化计算机科学导论第七讲.ppt
《面向计算机体系结构的程序优化计算机科学导论第七讲.ppt》由会员分享,可在线阅读,更多相关《面向计算机体系结构的程序优化计算机科学导论第七讲.ppt(77页珍藏版)》请在三一办公上搜索。
1、面向计算机体系结构的程序优化计算机科学导论第七讲,计算机科学技术学院陈意云0551-63607043http:/,课 程 内 容,课程内容围绕学科理论体系中的模型理论,程序理论和计算理论1.模型理论关心的问题 给定模型M,哪些问题可以由模型M解决;如何比较模型的表达能力2.程序理论关心的问题给定模型M,如何用模型M解决问题包括程序设计范型、程序设计语言、程序设计、形式语义、类型论、程序验证、程序分析等3.计算理论关心的问题给定模型M和一类问题,解决该类问题需多少资源,本讲座以矩阵乘算法为例,介绍围绕体系结构的优化,2,讲 座 提 纲,基本知识内存分层结构、多处理器的体系结构并行计算并行计算的常
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=
3、-9999;quickSort(m,i-1);a10=9999;quickSort(1,9);quickSort(i+1,n);,允许声明递归函数,存储分配有什么变化,4,基 本 知 识,计算机内存需要分出一块来作为数据栈,main,函数调用关系树,5,基 本 知 识,计算机内存需要分出一块来作为数据栈,函数调用关系树,6,基 本 知 识,计算机内存需要分出一块来作为数据栈,函数调用关系树,7,基 本 知 识,计算机内存需要分出一块来作为数据栈,函数调用关系树,8,基 本 知 识,计算机内存需要分出一块来作为数据栈,函数调用关系树,9,基 本 知 识,计算机内存1.初学编程时的认识2.学习递归
4、函数时的认识3.学习动态存储分配时的认识通过malloc等函数申请的空间安排在堆上内存的这种划分是通过操作系统和编译器实现的,不是在硬件层面上的划分,10,基 本 知 识,计算机内存分层内存方面的基本局限:构造非常快的存储器或者非常大的存储器都是可能的,但是构造不出既快又大的存储器内存分层是指整个内存由 几层不同速度和大小的存 储器组成,并且最靠近处 理器的那一层最快最小,11,基 本 知 识,计算机内存分层,两边数据可能已过时,12,基 本 知 识,计算机内存分层程序的效率不仅取决于被执行的指令数,还取决于执行每条指令需要多长时间,而执行一条指令的时间区别非常可观若一个程序的大部分存储 访问
5、都落在这种分层的较 快层次上,则平均内存访 问时间就会缩短,13,基 本 知 识,计算机内存分层寄存器由编译器生成的代码来管理,虚拟内存由操作系统管理,其他各层被自动管理。对于内存访问,计算机从底层开始逐 层查找,直至定位数据为止数据以块(缓存行、页)为单位在相邻层次之间进 行传送。缓存行:32256 字节,页:464千字节,14,基 本 知 识,计算机内存分层现代计算机都设计成程序员不用关心内存子系统的细节就可以写出正确的程序对应地,编程语言没有向 程序员提供干预数据进出 缓存的机制数据密集型程序可从恰当 利用内存子系统中获益,怎么做?,15,基 本 知 识,计算中潜在的并行性数值应用,例如
6、科学计算和信号处理,一般都有很多潜在的并行这些应用处理有大批量元素的数据结构,在该结构每个元素上的运算相互独立,因而在不同元素上的运算可以并行执行,例如一些矩阵运算这些领域的程序一般有比较简单的控制结构和规整的数据处理模式下面介绍支持并行计算的较为简单的体系结构,和怎样写较优的代码,16,多处理器对称多处理器的体系结构,多个高性能处理器可以集成在一块芯片上(下次课涉及),必须在处理器的缓存中找到它操作的大部分数据,以保证性能,基 本 知 识,通过共享内存来进行通信,17,多处理器分布式内存机器,两类机器:非均匀内存访问的机器和消息传递的机器 为获得良好的性能,软件都必须有很好局部性,基 本 知
7、 识,在内存分层中又引入一层,处理器能迅速访问自己的局部内存,18,并行计算的常见方式任务并行:每个处理器执行不同的任务数据并行:把大任务分别成若干个相同的子任务并行应用的性能衡量的两种标准并行覆盖:整个计算中并行执行部分的百分比并行粒度:处理器上无需和其它处理器同步或通信的计算量,循环级并行,19,循环级并行耗时的应用一般都使用大数组,导致程序中出现有许多次迭代的循环,每次迭代用于计算数组中的一个元素。这些迭代经常相互独立,它们是并行计算的主要来源可以把这类循环的大量迭代分到各处理器上,循环级并行,20,循环级并行for(i=0;i n;i+)/计算向量X和YZi=Xi Yi;/对应元素差的
8、平方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,程序中的局部性,局部性的表现 大多数程序的大部分时间在执行一小部分代码,并且仅涉及一小部
9、分数据。传统的说法:程序90的时间消耗在执行10的代码上(代码的局部性)程序经常包含许多决不会执行的代码,如由组件和库构建的程序经常仅用所提供功能的一小部分程序运行时,通常仅一部分代码被真正执行。如处理非法输入和异常情况的代码,虽对程序的正确性至关重要,但它们很少被执行程序的大部分时间消耗在程序中最内层循环和深度递归的执行上,23,程序中的局部性,两种局部性时间局部性程序运行过程中被访问的内存单元(存放代码或数据)在很短的时间内可能再次被程序访问空间局部性毗邻被访问单元的内存单元在很短的时间内会被访问同一个缓存行上的元素一起被使用是空间局部性的一种重要形式。它能把缓存未命中次数降到最低,因而使
10、得程序获得明显的加速,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;,程序中的局部性,
11、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
12、;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,
13、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的矩阵(数组)矩阵数据的布局是行为
14、主,矩阵乘算法及其优化,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的过程中,其值保存在寄存器中,则计算过
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 面向 计算机体系结构 程序 优化 计算机科学 导论 第七
![提示](https://www.31ppt.com/images/bang_tan.gif)
链接地址:https://www.31ppt.com/p-6435996.html