并行程序设计.ppt

《并行程序设计.ppt》由会员分享，可在线阅读，更多相关《并行程序设计.ppt（47页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、并行程序设计现在学习的是第1页，共47页什么是并行计算?n通过计算机硬件和软件协作，同时执行多个数据运算的一种计算模式n提高计算效率，包括提高计算速度、以及降低数据处理的成本n四种不同粒度/层次的并行计算n微指令级(SSE:streaming SIMD extensions)：向量处理指令n指令级(ILP:instruction-level parallelism):一颗core微处理器，有3个ALU、2个FPU、3个SSEn超标量技术：依靠微处理器体系结构技术，动态调整指令流的顺序，一次发射多条指令，主流处理器几乎都采用的技术n超长指令字技术：编译时将多条普通指令组装成“超级指令”，比如IA

2、微处理器n线程级(TLP:thread-level parallelism)：由程序将计算任务划分成可以同时执行的操作序列，每个操作序列分别由不同的处理器执行内核来处理n进程级：由程序将计算任务划分成可以独立分配计算资源的子任务，每个子任务分别由不同的计算机系统来处理现在学习的是第2页，共47页并行程序与并行计算机n串行程序:将计算任务分解成标量操作的序列的程序。串行串行程序是可以并行执行的程序是可以并行执行的n被编译器编译成面向SIMD的指令n被编译器编译成面向VLIW 指令n由支持superscalar技术的处理器执行n并行程序:显式表达计算任务中各数据运算无关性的程序n并行计算机:能够同

3、时执行并行程序中无关数据运算的计算机n采用向量处理器n一条指令完成多个数据单元的处理n提供多个互相独立的处理执行核:每个执行核分别执行自己的指令流n多处理器系统:Multi-core/SMP/CPU+Coprocessorn多计算机系统:MPP/Cluster/Grid/Cloud现在学习的是第3页，共47页并行程序的开发与并行计算串行程序串行程序程序员程序员串行编译串行编译串行程序串行程序串行处理器串行处理器串行串行执行执行超标量超标量处理器处理器并行并行执行执行 并行编译并行编译SIMD并行程序并行程序SIMD处理器处理器并行并行执行执行VLIW并行程序并行程序VLIW处理器处理器并行并行

4、执行执行线程并行程序线程并行程序多处理多处理器系统器系统并行并行执行执行进程并行程序进程并行程序多计算多计算机系统机系统并行并行执行执行线程线程并行并行程序程序进程进程并行并行程序程序编编译译编编译译现在学习的是第4页，共47页我们一直在不自觉的使用并行计算技术来提升计算效能n当前几乎所有的计算机都是并行计算机：多核当前几乎所有的计算机都是并行计算机：多核/微处理器内多个执行单元微处理器内多个执行单元/SIMD指令指令n几乎每个程序运行时都在执行并行计算：几乎每个程序运行时都在执行并行计算：专家们专家们(体系结构体系结构/编译编译/操作系统操作系统)一直在替我一直在替我们做并行技术的开发和运用

5、们做并行技术的开发和运用n指令级并行:提高同时执行的指令数缩短指令流的执行时间程序执行效率的提升程序执行效率的提升n指令的基本执行过程:instruction fetch decode execute memory access write backn每个过程分别是由不同的部件执行n通过流水,使得多条指令同时执行,每条指令分别处于不同的执行阶段:依靠pre-fetch/re-order等技术n提供多个执行单元，支持多条指令流水同时执行n数据级并行(data-level parallelism)和任务级并行(task-level parallelism):提高同时执行的线程数用户工作效率的提升用

6、户工作效率的提升(同时做多件事情同时做多件事情,互不耽搁互不耽搁)n基本技术支撑:interrupt/lock/hyper-threading/nCache/virtual memory/disk file:执行一个线程,总会发生数据访问失效现在学习的是第5页，共47页为什么要程序员编写并行程序?n并行计算机:提升计算系统计算潜力的必然趋势nFrequency wall:物理上限n指令流的执行时间下限nMemory wall:CPU与Memory的速度鸿沟n指令级并行的流水深度限制nPower wall:P=C(电容/晶体管的数量)V2(电压)F(频率)n单个芯片的计算潜力上限nMulti-c

7、ore:提升单个芯片计算潜力的必然选择,n保持Moores law:增加执行核(用于数据运算的晶体管的数量),降低主频n提高用于数据运算的晶体管的比率:降低指令级并行的流水深度n提高晶体管的利用率:执行核之间按需共享cache/FBIn挖掘处理器的计算潜力:提高芯片内用于数据处理的晶体管的比率n微指令级并行(SIMD):提高计算机的字长n一次解码,处理更多的数据n例如core微处理器的SSE指令采用128bit寄存器,一个指令周期可处理4个float数n数据级并行(data-level parallelism)和任务级并行(task-level parallelism):multi-core,

8、支持多个指令流同时处于数据运算阶段现在学习的是第6页，共47页n如何提高数据处理的效率:n利用多个执行核分摊数据处理任务n指令级并行/提高主频:缩短指令流的执行时间n并行程序:缩短指令流的长度n数据级并行/任务级并行:同时执行多个短的指令流n向量计算:提高单条指令的数据处理量n处理器的主导技术已由提高处理器主频转向n多核技术多核技术n指令流的执行时间延长了n同时执行的指令流数量增加了n专用协处理器技术(X86指令集包括近300条指令,科学计算只需要其中的约80条指令)n提高用于数据处理的晶体管的比率n提高晶体管的利用率n可重构计算技术(FPGA):由应用程序动态将芯片定制成专用协处理器n单个数

9、据处理部件的运算速度有上限:frequency walln多核时代,计算平台的关键特征:不是单个执行核的性能提升了,而是可利用的执行核的数量提升了现在学习的是第7页，共47页n如何处理更大规模的问题,即:如何在可接受的时间里完成更大规模数据的处理?例如n电信计费n网络搜索n视频点播n地震现象反演:有限元法,地震区域的10m10m10m作为一个粒子,模拟这些粒子在地震前后的运动轨迹n一台计算机的服务能力有上限：n处理器:计算能力（处理器的数量、处理器内执行核的数量）n内存:容量/访问速度和带宽n磁盘及IO:容量/访问速度和带宽n数据级并行(data-level parallelism)和任务级并

10、行(task-level parallelism)n多台计算机协作n面向领域/应用的并行计算机/协处理器(如GPU)/可重构计算(FPGA)现在学习的是第8页，共47页编译技术/微处理器体系结构技术不足以开发并行计算机的计算能力nVLIW/superscalar：适合开发微处理器内部各个执行单元的并行能力n编译技术：发现串行程序中无关的数据运算n串行程序：隐藏了计算任务的数据运算无关性n分析问题的数学/物理模型n设计串行算法n用串行语言编码算法n例如：寻找N以内的素数,该如何并行？prime0=2;prime1=3;p=2;for(i=5;iN;i=i+2)for(j=1;jp;j+)if(i

11、%primej=0)break;if(jp)break;primep=i;p+;现在学习的是第9页，共47页并行程序设计n以问题分解为基础,开发面向并行计算机的程序:通过多颗处理器协作、以及挖掘处理器的计算潜力,达到加速数据处理的效率和提高问题求解的规模的目标n手段n挖掘每个处理器的计算潜力n提供更多的并行线程，避免由于内存壁垒等因素导致执行单元处于空等待状态n微指令级并行(向量计算),提高单条指令的数据处理量n多个处理器协作,分摊计算任务:缩短每个指令流的长度n多计算机间数据划分:增加存储容量n目标n加速数据处理的效率n提高问题求解的规模n并行程序设计(本门课程)关注:发现计算任务中无关的数

12、据运算，并利用数据运算的无关性开发并行计算机的计算能力n向量处理器/阵列处理器系统n多处理器系统n多计算机系统现在学习的是第10页，共47页多核时代：当多核处理器给用户相应提高的性能体验时，才真正到了多核时代n计算平台可为程序的运行提供多个执行核n多核时代不等于多核处理器时代n如何获得多个执行核?n多核处理器nSMP/CPU+Coprocessor(专用协处理器/FPGA)nCluster/MPPnGrid/Cloudn大多数人并没有多个执行核协同计算多个执行核协同计算(并行计算)的体会n计算机专业的整个本科教学，都是基于Von Neumann，仅在操作系统、体系结构里提到一点并行和并发的概念

13、n使用的应用软件也基本是基于串行技术:对计算性能的体验并未改进,甚至有所下降n串行程序+降低了主频和指令流水深度的多核处理器n更复杂的操作系统:多线程支持/早先的超线程技术n操作系统程序与用户程序同时运行:Cache、FBI的瓶颈效应nn可以在一台机器上同时运行几个程序:多核处理器之前已经如此n操作系统的多进程/多线程/超线程支持技术n用于超级计算机(Cluster/MPP)的HTC(high-throughput computing)现在学习的是第11页，共47页多核时代的特点n已经具备的特点:并行计算机不再与“昂贵”、“高性能”有必然联系，从体系结构上看，我们所使用的都是并行计算机n支持S

14、SE的多核CPU+GPU(每个GPU是一个微处理器阵列)nCPU的微处理器内核包括多个执行单元，采用了superscalar/VLIW技术n尚不具备的特点:体验并行计算机对计算性能的提升效果n数据处理的速度更快n可处理的数据规模更大n挑战性问题:并行程序的可移植性(衡量程序算法/代码与目标平台体系结构的紧密程度),来自并行计算平台的异构性nIntel/AMD处理器：CPU+CPUnIBM CELL处理器:CPU+Coprocessorn多处理器系统:SMP/(CPU+Coprocessor)/(CPU+FGPA)n多计算机系统:Cluster/MPP/Grid/Cloudn编程人员：“傻瓜”还

15、是“精英”n“傻瓜”：知道语法就够了，其他事情交给编译、运行支持去做吧n“精英”：我能，但只有我能；我能，但我只会这一点n尽管都是面向流媒体计算nCPU中的SSE：SIMD，向量指令nGPU：阵列处理器，线程并行编程(CUDA)现在学习的是第12页，共47页新软件危机n硬件上多核、软件上串行n大量的晶体管闲置、使用效率不高n主频的降低，导致性能体验的下降n性能，再次成为编程技术的焦点：线程级并行对开发多核处理器的计算能力至关重要n性能，依赖“精英”们实现n体系结构的特征n数学/物理模型中的计算并行性特征并行算法n编写程序：既要做“经理”，又要做“业务员”n“业务员”：完成数据处理n“经理”：“

16、业务员”的分工、协调(在单核处理器时代，可以由编译技术/微处理器体系结构技术自动解决)n能以来自动机理论(运行时支持)、形式化理论(编译技术)代替“精英”吗？n能：当这个问题很简单时n不能：并行算法设计是“艺术性”、而非“技术性”的工作。请将一个求素数的串行程序并行化吧。并行程序设计：少数人的专利、编程人员的基本要求？现在学习的是第13页，共47页内容提要n课程基本信息n对并行计算的认识n并行计算的概念n并行计算平台n并行计算技术的使用n问题是什么？n课程目标与定位n教学安排现在学习的是第14页，共47页课程相关信息n成绩评定：平时成绩(50%)+max兴趣研究报告，期末笔试n平时练习、编程实

17、验:50分n兴趣研究报告：50分。1-3人一组，自选题目，题目来源：n所在研究组面临的计算性能需求，结合课程学习，提出解决方案n所在课题组正在解决的计算性能/计算效能方面的技术问题，结合课程学习，提出并行处理技术对该问题的促进n高性能/高效能/云计算领域中感兴趣的前沿研究方向，结合课程学习，开展调研，给出该方向的研究进展、趋势和评价n期末考试：50分n课程网页http:/现在学习的是第15页，共47页课程历史与内容沿革n1999-2002年，李晓明nMPI、HPF、OpenMP、并行编译n集群、MPP、SMPn2003年开始，余华山n2005年nMPI、OpenMP、并行算法设计与应用实例、基

18、于网络的并行处理n集群、MPP、SMP、网格n2007年：教育部-Intel精品课程建设项目nMPI、pthread与Intel多核技术、并行算法设计与应用实例、OpenMP、基于网络的并行处理n多核、SMP、集群、MPP、网格n2008年：教育部-IBM精品课程建设项目npthread与Intel多核技术、CELL BE技术、MPI、并行算法设计与应用实例、基于网络的并行处理(网格)n多核、SMP、集群、MPP、网格现在学习的是第16页，共47页n2011年：北京大学研究生课程建设n以出版为目标的讲义n完成一章，在课程网站发布一章现在学习的是第17页，共47页并行程序设计的基本概念n“并行程

19、序”：支持多个操作、或者任务同时执行的一种规规划划n做事情，总要规划动作的顺序：确定房子的地址、设计结构图、作预算、选择施工者、规划施工进度、买建筑材料和施工。n规划的关键是分析问题各个部分之间的内在联系，任何规划都不能破坏这个联系n总有一些部分之间是没有内在联系的，可以同时执行：房屋建筑的第一阶段施工、购买第二阶段建筑材料n什么是并行程序设计：以任务分解任务分解为基础,开发面向并行计并行计算机算机的应用程序,以提高数据处理的效率数据处理的效率、或者提高可解问可解问题的规模题的规模.n计算平台：支持同时执行多个数据处理运算(提供多个执行核/向量处理器)n操作系统：支持多指令流调度(多核处理器计

20、算平台)、或者多数据流访问(向量处理器平台)n编程语言(以及编译运行系统)：支持计算并行性的表达现在学习的是第18页，共47页并行计算有什么用途n并非所有问题都需要使用并行计算技术并非所有问题都需要使用并行计算技术n写WORD文档、写C/C+程序代码n一个字符、一个字符地从键盘输入n即使用最低端的机器，没有人感觉到不能及时得到响应(你同时打开了很多文档、再边听MP3除外)n使用Google、Baidu搜索网页n时刻都有成千上万的用户在搜索n有兴趣吗？对比一下从Google、Baidu得到的响应速度、在一台高端服务器上模拟100个用户搜索1,000,000条记录的响应速度n汶川地震研究：反演地震

21、过程，整个中国几乎都有震感n震区离散化，每10个立方米作为一个粒子n使用当今运算速度最快的处理器，对这个三维数组做一次最简单的运算，比如对每个元素做一次加法，需要多久？现在学习的是第19页，共47页并行程序的时代已经到了？n并行计算：在计算平台上同时执行多个数据运算n提高计算的效能n提高处理器的计算潜力n提高处理器的利用率n提高数据处理的速度n提高可解问题的规模n并行计算平台随处可见n多核处理器：PC机、笔记本nSMP：服务器nCluster：大型计算中心服务器n网络计算环境：CN Grid、China Grid、TeraGrid、Google？n并行程序的需求来自各个领域n我们的生活已经离不

22、开网络：成千上万的并发用户访问搜索引擎、新闻网站、通信聊天网站、娱乐视频网站、多人网络游戏、公共服务网站(图书馆、电子文献数据库)、电子银行、电子政务n工程、科研、生活服务越来越依赖于大规模数据的高效计算：飞机设计、汽车碰撞模拟、武器设计、油气勘探、神州飞船跟踪、基因数据分析、地震运动过程模拟、太阳风磁场重联模拟、三峡大坝选址、气象预报、现在学习的是第20页，共47页并行计算的现状nCPU执行程序时，使用了superscalar/VLIWnCPU早就提供了SIMD支持，从MMX到现在的SSE4。n一些商业软件使用了SIMDn一些函数包使用了SIMDn一些编译器在对循环优化时使用了SIMDn程序

23、员使用了吗？n谁在用桌面机的多核处理器计算能力？n桌面机上的应用以串行程序为主n自己会写并行程序的人不多n一边写程序、一边听MP3时，可以用上，但影响编程、不用多核处理器时计算能力也够了nSMP(Symmetric Multi Processing)服务器n商业软件：开发了并行能力n自己开发的软件：以串行程序为主n主要是依靠操作系统支持多个进程/线程的同时执行现在学习的是第21页，共47页能同时使用成百上千颗处理器的应用有多少?n集群上的并行计算情况：以CCSE128节点使用情况为例(2006年3月)n3309个计算任务n平均使用1.85个计算节点n节点资源利用率94.7%nIBM RoadR

24、unnern哪个应用能同时使用12960颗CELLnCELL处理器执行标量计算程序将非常慢(6912颗AMD Opteron似乎只是为了让每个节点也能够正常执行原来的标量计算进程)n天河计算机：主要计算能力来自GPUn2048颗飞腾FT-1000八核心处理器 n14336颗Intel Xeon X5670 2.93GHz六核心处理器 n7168块NVIDIA Tesla M2050高性能计算卡(GPU)现在学习的是第22页，共47页如何看待我国的天河一号A？n这是一个了不起的成就：2万多颗处理器放在一起，并让它们一起协作，采用LU分解的方法求解一个密集矩阵的方程n通信问题n稳定性问题：一个部件

25、的出错/故障率是百万分之一，这么多通信、存储、计算、及其他辅助部件放在一起，怎么能够稳定运行？n功耗和散热问题nn这台机器本身也许并不是一个特别值得炫耀的成就n有多少支持GPU的软件？n支持GPU的软件能够在哪些领域使用？GPU的基本数据类型是float，这样一个精度下如何进行迭代模拟类计算、高精度场计算？n有多少应用能够有效开发1024颗处理器执行核的计算能力？比如速度能够提高600倍n有多少人在开发面向这个机器的软件？软件的开发周期软件的开发周期5-10年年。现在学习的是第23页，共47页谁依靠网络环境进行并行计算?nTeraGrid:主要用户是SSHn没有网格对这类用户没有影响n其实就是

26、使用超级计算机nEGEE:主要工作是提供一个统一的用户接口n支持并发用户，避免相互恶性竞争：把计算任务动态绑定到具体的超级计算机上n没有支持一个问题同时使用多台超级计算机nCN Grid、ChinaGrid上是否有跨超级计算机求解问题的应用？nGoogle search engine：依靠网络计算环境支持大规模并发用户n云计算的概念n以数据为中心，根据数据需求选择计算资源现在学习的是第24页，共47页并行技术的应用为何不如人意？n并行计算平台有其适用范围n并行处理技术的使用离不开人的参与n并行求解算法的设计不是简单的串行算法并行化：按照体系结构设计算法n向量处理器：标量数据要向量化n多颗标量处

27、理器：设计多个指令流现在学习的是第25页，共47页你的笔记本、桌面机需要提高性能吗？n需要性能提高的理由n系统启动慢n启动一个应用程序慢：打开一个PDF、WORD、VC编程环境、DVD视频文件、n打开很多个应用程序时，系统响应很慢n打开一个大的PDF文件、WORD文件，翻页浏览时响应慢n如何提高性能:CPU的计算能力按照moore定律成长，你体验的性能成长多少了？n微软的应用程序都很大，载入系统慢n同时运行的应用越多，系统切换需要的存储交换越大n如果你觉得翻页浏览时响应慢，请你看看被打开的PDF文件、WORD文件有多大n你使用的CPU性能早就远超过你的需求：软件的质量、存储的速度？n把VIST

28、A还原成XP，把XP替换成WIN98，速度的体验会如何？n把CPU从INTEL CORE i5换成Pentium IV 1.8/3.2，速度的体验会如何？现在学习的是第26页，共47页多核处理器：CELLnDMA(Direct Memory Access)数据存取：编程人员需要知道一切细节，内存的大小、被访问数据的大小、计算和数据的划分方法、n标量计算速度慢：没有数据预取、乱序执行等。我猜想这是在RoadRunner中需要AMD处理器的根本原因：支持已有的MPI并行程序n如何编程N-body问题？(IBM开发的方法：按照空间对粒子排序，一个空间的交给一个处理器，不考虑空间之间的互相作用。如此一

29、来，粒子排序成为性能瓶颈)n除了MPEG这类计算，CELL还能在哪地方用？GPGPU能走多远？现在急需回答这个问题nIBM已经放弃CELL，GPU会面临同样的困境吗？现在学习的是第27页，共47页多核处理器：Intel Core 2nCACHE数据存取：完全屏蔽数据访问细节，CACHE的命中率成为关键n运行两个无关的进程n涉及的数据都小：互相没有影响n两个进程分别对一棵大的树进行搜索，串行执行两个进程与并发执行两个进程：哪个更快？要协要协商对商对cache与系统内存之间系统与系统内存之间系统总线的占用总线的占用n已经遇到一个应用：对一个大的数组进行变换n确定数组A的元素值AI，J：产生两个随机

30、数X，Y，将BX，Y赋值给AI，Jn使用串行程序要比并行程序更快执行核执行核cache系统内存系统内存现在学习的是第28页，共47页SMPn存储一致性问题n我在本课程的实验中，对N-body问题测试n计算任务直接更新全局空间的数据，并行程序更慢：同步开销n更适合计算松耦合问题。耦合：进程/线程运行过程中，互相交换数据、同步的频率n(通信)求素数问题：判断I是否为素数，需要用到I之前的素数n(同步)a=f(i)求和：任何时刻，只能有一个进程/线程在阅读、修改变量an程序员要设法避免频繁的同步现在学习的是第29页，共47页clustern适合计算松耦合问题、问题要有一定的复杂度n程序员划分计算任务

31、、数据n确定数据的交换和同步n当前最主要的超级计算机结构，其成功与MPI(message passing interface)这一并行编程模式分不开n能够占用一台超级计算机全部CPU的应用很少现在学习的是第30页，共47页网络计算环境(Grid/Cloud)n访问网络中的某台超级计算机：当前主要的模式nEGEE希望帮助用户选择需要访问的超级计算机n不适合计算松耦合问题：计算无耦合问题不错，我们做了这方面的工作n网格刚兴起的时候，很多人尝试在网络环境运行MPI程序，效果很不理想n计算的问题要足够复杂：通信-计算比现在学习的是第31页，共47页并行技术的使用离不开人的参与n需要人根据问题特征发现并

32、行性、选择计算平台n需要人根据计算平台划分计算任务、优化数据存取效率n在基于Cache的多核处理器上，计算任务的粒度要考虑Cache的命中率n在网络计算环境上，计算任务的粒度要到批作业级才合适n看几个问题n求素数问题：如何并行nN-body问题：如何减少同步、维护数据一致性n物体间的万有引力定律，促使粒子的运动n规则的大数组计算：C语言中以行优先访问、Fortran语言中以列优先访问可以提高数据的存取效率，在基于Cache的多核处理器平台上，这个将更重要现在学习的是第32页，共47页并行算法的设计问题n从串行算法出发，寻找能够并行的循环n串型程序自动并行化的思路，实践表明不理想n串行算法本身常

33、常没有体现问题的并行性、或者隐藏了数学/物理模型中的并行性n求素数问题n并行算法的设计实现要考虑计算平台：以我们做的大规模基因组可变剪接问题为例n问题域中有几万个互相独立的批作业n在SMP/(有NFS、PFS支持的)cluster环境上：每个批作业作为一个任务n在网络计算环境上，要把几百个、甚至几千个批作业合并成一个子任务才会有效：这方面国际上已经有些类似的工作现在学习的是第33页，共47页新的软件危机？n软件危机：与软件消耗的计算能力相比，硬件提供的计算能力过剩n20世纪60、70年代，计算机的能力已经比50年代有巨大进步n计算机的应用领域已经不只是在核武器计算n人们使用汇编语言编写程序：程

34、序员少、生产效率低n难题：如何开发更多的软件n解决n高级语言和编译技术，屏蔽计算任务到硬件设备的映射：Fortran、Cn操作系统技术，屏蔽硬件的实现和操作细节：软件移植、应用软件分时共享系统资源n编程方法(软件复用、可维护、可扩充)：结构化、面向对象现在学习的是第34页，共47页今天的情形n计算能力过剩nIntel、AMD、IBM都在力推多核处理器n网络已经不只是交流信息，在P2P方面事实上已经成为计算平台n应用程序主要是串行的n编写并行程序是少数人的专利、效率低n需求在扩展n网络计算已经深入社会生活的方方面面：支持大量的并发用户n科学工程领域更加依赖高性能计算技术n研究工作的深度扩展：高精

35、度、大规模n研究工作的广度扩展：软件的协同、数据的综合现在学习的是第35页，共47页汇编语言写串行程序C语言写CELL处理器程序CPU操作寄存器数据，编程人员负责寄存器与内存数据的交换SPU操作局部内存数据，编程人员负责局部内存与全局内存的数据交换编程人员将计算任务分解到指令，规划指令的执行次序编程人员将计算任务分解到SPU的粒度(代码和数据的规模不超过256KB)，规划子任务的并发关系以BYTE为数据存取的基本单位以128BTYE(SPU寄存器大小)为数据存取的基本单位n在Intel和AMD的多核处理器上：如何开发多个执行核的并行计算能力n使用C语言：只使用了一个处理器执行核的计算能力n使用

36、C+pthread：并行算法设计、cache的命中率n分别执行不同的进程：进程之间的Cache竞争n更进一步：如何开发SMP服务器、CLUSTER、网络计算环境的并行能力？现在学习的是第36页，共47页多核的硬件时代已经到来n采用的多核技术，CPU的运算速度继续按照Moore定律增长n18个月，运算速度增长一倍n一块芯片上通用微处理器执行核的数量真的会很多(比如超过32)吗？制造工艺也许允许厂商这么做，但真能从软件方面发挥其计算性能吗？n矛盾：最终用户体验到的性能改进极其有限n多核的存储模型是什么？存储设备的性能早已成为性能的瓶颈，(我认为)也成为决定多核处理器时代存续的关键n基于cache？

37、(我认为)至少不能对程序员完全透明n基于DMA？(我认为)至少不能完全将细节交给程序员n一种全新的技术？我们拭目以待n适合多核时代的软件技术是什么？n操作系统的理论和技术需要创新n编译理论和技术需要创新n编程语言和模式需要创新现在学习的是第37页，共47页网络计算的时代已经到来n曾经，网络对我们而言n快速、廉价的数据交换：FTPn有限的资源共享：TELNET/SSHn快速、廉价的通信：EMAILn用低端设备实现高性能的计算：分布式计算、CLUSTERn今天的网络是信息存储、交流、聚合的平台n网页搜索、浏览nBBS/微博n电子商务n电子政务n但我们还希望网络是计算资源、软件资源、数据资源的聚集聚

38、集和共享和共享平台：人们象使用今天的大型计算机一样使用网络环境、人人都可以随时访问n网格计算技术、云计算技术、还是其他计算技术？现在学习的是第38页，共47页网络计算环境与超级计算机n今天人们对网络计算环境的需求，用现有的超级计算机都能够满足，但难度要大、成本要高nGoogle搜索：把所有的服务器聚集在一起，做一个集群n出口带宽要很高n散热问题很大n所有数据维护人员要集中在一起nn还未有一个高性能应用，能够占用RoadRunner/天河一号A的全部处理器资源n当北大CCSE的集群有大量用户排队的时候，科学院计算中心的超级计算机没有人使用n北大CCSE集群和科学院计算中心的超级计算机都有大量用户

39、排队，但都有一个处理器空闲，因为每个用户的计算都需要至少两颗处理器n处于维护成本等方面因素的考虑，每个应用软件、数据库都只会安装在数量有限的几台机器上现在学习的是第39页，共47页课程目标与定位n并行计算环境的时代已经到来n多核处理器、SMP、集群、网络计算环境n程序开发的目的：提高处理器运算单元的利用率，达到计算性能提高的目的n未来的程序开发，是并行程序的开发：我们假定n多核是处理器发展的必然n网络是社会生活、工程设计制造、科学研究的基本工具n通过这门课程的学习，你成为合格的程序员：开发程序，最大限度发挥计算平台中处理器运算单元的利用率n并行计算的基本原理：程序运行过程中，除了执行数据处理语

40、句外，还有哪些事情是必须做的n并行程序开发的基本方法：计算并行性的挖掘、算法设计、实现优化n并行计算机的体系结构：工作原理、数据存储与访问现在学习的是第40页，共47页教什么？n近10年并行处理技术研究、推广应用的体会和认识n把其中积累的应用实例拿来讲，抛弃“教科书”上的示例n请学生讲他科研工作中面临的问题，帮助他提出解决方案n请同学们“照猫画虎”n准备几只“猫”：求素数、N-Body、Laplace等n准备几个“动作”：MPI、pthread、CELL上的实现n观摩“猫”的表演：样例并行程序n请同学们体会“不要与虎谋皮”：没有并行技术是不行的，但任何技术都有其局限性n油气勘探地震数据处理，一

41、个三维数组的规模在15GB，虽然现在的处理器速度已经很快，在每个数组元素上加1，要多久？n分子化学运动过程模拟，做一个大分子(几千个原子)，一个时间步上，有多少次浮点计算、一个数据要被访问多少次？nN颗共享存储的处理器，数据访问的平均排队时间是多长nN颗分布存储的处理器，数据交换的规模是多少现在学习的是第41页，共47页教学方法n结合具体的并行计算平台nCELL处理器、Intel Core 2处理器nSMP服务器n集群n结合教员在大规模科学工程计算积累的实例n生物信息计算、流体力学、地质运动过程模拟、油气勘探计算、天体物理、n教员讲授nPPTn习题n电子版参考资料n自编讲义：完成一章，在网站发

42、布一章n同学们的兴趣研究n科研工作中的问题n感兴趣的高性能/高效能研究前沿现在学习的是第42页，共47页如何教？n以实例和实践为牵引nIntel多核处理器/SMP服务器：pthread并行技术n集群：MPI并行技术nCELL处理器：数据存储和访问的原理、实现机制，向量并行计算nN-body：加速比上限n求素数：计算并行性的发现n“不求甚解”：“艺术家”需要“天赋”n并行计算涉及的计算机技术：操作系统、体系结构、编译技术、网络通信n有大量的trade-off：负载均衡与同步通信、重复计算与同步通信等n实际问题基本是“一事一议”：没有通用的并行算法和模式n“知其然”，然后“知其所以然”n从并行基础

43、理论出发，认识并行技术、分析应用需求n运用并行基础理论，解释并行计算的现象n“经典”也要“与时俱进”n基础理论：加速比上限、BSP/MPI、计算-通信比、SPMD/MPMDn教研相长n及时取舍:取新技术(多核技术/线程技术),舍未通过实践检验的技术(HPF/OpenMP技术)现在学习的是第43页，共47页教学内容 n并行计算的基本概念与基础理论n并行计算机与Flynn分类法、Amdahl定律、BSP模型、并行程序及设计方法和评判标准、加速比、并行效率、伸缩性、并行算法的评判标准、计算并行性与分治策略(divide-and-conquer)等。n并行计算平台的体系结构n对称结构多核处理器(以In

44、tel多核处理器为例)、异构非对称结构多核处理器(以CELL/B.E.处理器为例)、数据存储、并行数据访问的一致性(cache技术、DMA技术)、SIMD计算、多处理器系统(SMP)、多计算机系统(集群)等。n并行编程模型与性能优化策略n线程并行编程(POSIX并行线程模型、CELL线程模型)、进程并行编程(MPI消息传递模型)、SPMD并行程序结构、MPMD并行程序结构、并行程序性能的度量、子任务粒度与并行开销、负载均衡、动态任务划分、数据局部化、计算与数据传输的重叠、计算复制、非阻塞通信等。n并行算法设计与子任务的调度协作模式n理想并行、分治并行、流水并行、Barnes-Hut算法、FOX

45、算法、对等协作的并行计算模式(peer-to-peer collaborating)、主从协作的(master-slave collaborating)并行计算模式等。n并行任务调度/协作的实现机制n进程、线程、互斥锁与临界区、信号量、通道、消息交换等。现在学习的是第44页，共47页进度安排（暂定）n第一讲 并行计算概述(一)n第二讲 并行计算概述(二)n第三讲 POSIX线程与多核处理器基础n第四讲并行程序性能分析基础n第五讲 并行算法设计基础：PCAMn第六讲 CELL BE处理器的体系结构和线程模型n第七讲 SIMD编程n第八讲 并行计算中的通信：同步与数据传输n第九讲 并行计算中的任务

46、分配n第十讲 MPI并行程序开发基础(示例程序)n第十一讲 阻塞式MPI”点到点(Point-to-Point)”通信n第十二讲 MPI群通信、并行函数调用、并行程序性能分析n第十三讲 并行算法设计(一)n第十四讲 并行算法设计(二)n第十五讲 网络环境上的并行处理：网格/云/千万亿次超级计算机的并行计算现在学习的是第45页，共47页通过课程能学到什么n基本目标：n不同处理器的并行计算基本原理nIntel Core 2处理器的并行计算基本原理nCell处理器并行编程基本技术：CELL处理器npThread并行编程技术：Intel多核处理器、AMD多核处理器、SMP服务器nMPI并行编程技术：S

47、MP多核服务器、CLUSTER、MPP(Massively Parallel Processing)nPCAM并行程序设计方法、程序性能分析与优化基本策略nBSP并行程序模型n进一步n认识并行平台、并行技术的适用限制n认识并行性能的局限：问题特征n并行算法设计方法n将并行技术应用于研究工作中现在学习的是第46页，共47页练习n结合你的生活和科研实践，给出两个使用网络计算环境的例子。在这两个例子中，n如果没有网络计算环境，会产生什么样的影响？n对你使用的网络计算技术有何改进的建议？n你所在的课题组是否困于计算机的运算速度太慢？调查一下对计算性能的需求是什么？n你所在课题组的各类计算机中，最多的一台计算机有多少颗通用微处理器核？这台机器在课题组中的关键用途是什么？。现在学习的是第47页，共47页