图形处理器的通用计算研究综述
摘要多年来计算机图形处理器以大大超过摩尔定律的速度高速发展。图形处理器的发展极大地提高了计算机图形处理的速度和图形质量，并促进了与计算机图形相关应用领域的快速发展，与此同时，图形处理器绘制流水线的高速度和并行性以及近年来发展起来的可编程功能为图形处理以外的通用计算提供了良好的运行平台，这使得基于GPU的通用计算成为近两三年来人们关注的一个研究热点。本文从介绍GPU的发展历史及其现代GPU的基本结构开始，阐述GPU用于通用计算的技术原理，以及用于通用计算的主要领域和最新发展情况。最后，展望了GPU应用于通用计算的发展前景，并从软件和硬件两方面分析了这一领域未来所面临的挑战。
关键字GPU；GPGPU；CUDA；通用计算；可编程性
1引言
计算机图形处理器GPU（Graphics Processing Unit）具有极高计算性能和相对廉价的成本，以超过摩尔定律的速度更新硬件，从2003年后在通用计算领域图形处理器GPGPU （General-Purpose Computing Graphics Processing Unit）取得长足发展。在学术界人们研制了以下典型处理器芯片：斯坦福大学的Imagine、Merrimac及国防科学技术大学的飞腾FT64[1]，而飞腾处理器已成功应用于“天河一号”超级计算机的设计中。在工业界Nvidia[6]、AMD等公司持续更新其GPU硬件产品，利用推广软件的方式来扩大各自硬件产品的生态圈，目前Nvidia在通用计算领域中成果显著。
国内吴恩华教授[2-3]总结了2004年之前GPU的发展历史和现代GPU基本结构，阐述了通用计算的技术原理、软件工具及详细的发展之路，总结了各种应用领域的进展，如流体模拟、代数计算、数据库应用、频谱分析等。国外Owens研究团队综述了2008年之前GPGPU 的硬件及软件方面的应用进展[4-5]，分别从GPU体系、计算编程模型、软件开发环境和编程语言等方面作了详细介绍；然后重点分析了GPU计算中的关键技术和算法问题。本文重点关注最近3年内GPGPU发展过程中关键技术的研究与进展，特别是由于海量数据处理的需要，单节点GPU受到硬件限制，多GPU系统和GPU集群的应用研究成为新热点。本文第2节介绍GPU 通用计算的发展；第3节介绍GPGPU中关键技术的研究及进展；第4节介绍GPU通用计算的
应用；最后总结现有研究面临的挑战和展望未来工作。
2 GPU通用计算发展
2.1 GPU的提出及最早的通用计算应用
GeForce 256—代号NVl0于1999年8月发布。这是图形芯片领域创世之作，也是第一款提出GPU概念的产品。GeForce 256所采用的核心技术有硬体T＆L、立方环境材质贴图和顶点混合、纹理压缩和凹凸映射贴图、双重纹理四像素256位渲染引擎等，而硬体T&L技术可以说是GPU的标志。GeForce 256称作GPU原因就在于Geforce256创新性的在图形芯片集成了T＆L(几何光照转换)功能，使得GPU具有了初步的几何处理能力，完美的解决了CPU 几何吞吐量不够的瓶颈。
2.2 Shader的出现及其快速发展
在面向图形计算GPU渐渐找到了发展方向，这个方向就是给予用户更价逼真更加迅捷快地视觉体验，与此同时GPU架构遇到一些烦。首要问题就是，为了呈现更加丰富多彩的图形图像效果，不能只依靠三角形生成和固定光影转换。Shader概念的提出，使得程序员可通过它构建3D场景难度大大降低。当时最最重要的改进是增加对浮点数据的处理能力，以前GPU只能对整数进行处理，改进后提高渲染精度，使最终处理的色彩格式达到电影级别。Shader Model 2.0时代突破了以前限制PC图形图象质量在数学上的精度障碍，它的每条渲染流水线都升级为128位浮点颜色，让设计师更加自如的的创造出更炫丽的效果。在通用性计算方面，浮点运算让GPU已经具备了通用计算的基础，这一点让GPU在通用计算方面高速发展成为了可能。
2.3 GPGPU的概念及其发展
GPGPU[7]全称General Purpose GPU，它是一种支持通用计算的图像处理器, 它除了像一般的显卡一样拥有图像处理功能之外, 还能够像 CPU一样提供一定的通用计算能力。当前, 在产业界 AMD 公司和 NVIDIA 公司都已经在生产这种支持通用计算的GPU , 对应的典型显卡有 Firestream 系列和 GTX 系列。也就是将GPU用于3D图形处理已外的通用计算，由于图形处理器硬件以大大超过摩尔定律的速度发展，人们开始挖掘图形处理器的强大计算能力来从事非图形方面的应用，并称为图形处理器通用计算(general purpose computing on the GPU，GPGPU)。现在其应用领域已扩展到了几何造型、数值计算、流体模拟、场景绘制等领域。最初的GPGPU开发使用图形学API编程，在这种模式下，程序人员不仅要掌握需要实现的计算，还要对图形学硬件有深入的了解，使得的开发难度很大，传统的GPU并没有得到广
泛的应用。2003开始，斯坦福大学的Lan Buck等人对ANSI C进行了拓展，开发了Brook 编译器，大大简化了开发的过程。但是早期的Brook编译的效率很低。还由于受到GPU架构的限制，Brook也缺乏有效的数据通信机制。而后，AMD/ATI公司在其GPGPU通用计算产品Stream中采用了Brook的改进版本Brook+作为高级开发语言。由于Brook+还有一些限制，所以在灵活性方面并不如CUDA好。而且由于过多的封装，效率也并不很高，不支持多GPU，Rook+的kernel不支持高级的GPU命令，比如本地共享内存和原子操作等。已经被提交到了Source Forge上，已经没有太多的维护了。
3 GPGPU关键技术及进展
3.1 GPU编程模型
3.1.1片内编程模型
从片内与片间两个角度分析编程模型的发展。对于早期GPU片内，在数据并行编程模型基础上，程序员将各种算法映射到绘图流水线中，以此挖掘GPU硬件并行性。随着可编程部件功能增强，出现了以顶点、子素处理器等硬件为基础的渲染模型（Shader Model）。为解决片内负载均衡问题，统一各种可编程部件后出现了统一渲染模型（United Shader Model）[8]。CTM[9]对GPU片内编程模式有重要影响，抽象化GPU硬件来降低对底层的依赖，把开发控制策略返还编程人员。此后，由于更适合通用计算的流处理器SP（Stream Programming）的出现，流式编程模型（Stream Programming Model）逐渐成熟，并在Brook和CUDA编程语言中应用[10-11]。
3.1.2 片间编程模型
GPU长期以协处理或加速器的方式存在，因此GPU与CPU之间的耦合关系对片间编程模型有影响，如Nvidia GPU与CPU之间是松耦合关系，而larrabee与Fusion是紧耦合关系．松耦合体系侧重向用户提供灵活的编程模型，如OpenCL[12]存在数据并行模型、任务并行模型和混合编程模型，根据不同应用程序的性能特点灵活选择适当编程模型；CUDA也针对片间松耦合体系，基本编程模型是数据并行模型[13]，而且是细粒度数据并行。此外CUDA中提供流的机制，用户运用多流可以达到任务并行执行，因此在某种程度上CUDA给出一种任务并行编程的途径。在松耦合体系中存在一个问题，由于CPU即是计算管理者又是执行者，因此CPU未被充分利用。而片间紧耦合体系有效解决了该问题，平衡编程模型能在GPU与CPU之间合理分配计算负载，充分利用CPU计算资源；实现以线程为调度单位的细粒度数据和任务并行计算。
3.1.3 编程模型发展方向
未来编程模型预计向两个方向发展。为降低并行程序设计复杂性和提高非专业开发人员的效率，GPU片内要出现元编程模式．元程序设计是编写生成代码的程序。在元编程模式中自动生成任务划分、通信等代码，编程人员更专注于特定领域的算法设计。GPU片间通信能力增强后，片间编程模型必然向分布式方向演化。如CUDASA中的分布式编程模式能有效解决负载均衡和全局存储管理、通信的问题，降低GPU集群应用程序的开发难度[14]。
3.2 GPU开发语言
GPU开发语言从专门的着色语言、面向流计算模型的流语言，发展到现在的面向通用计算领域的编程语言。以下分3个方面介绍：GPU编程语言起源着色语言（Shading Language），如GLSL、HLSL、Cg[5]。着色语言是独立图形处理硬件的高级编程语言，为了开发者灵活、方便控制并行图形渲染．存在两个局限性：(1)对底层图形库依赖性强，可移植性差；(2)开发难度大，不仅要掌握并行开发技术，而且要了解硬件结构和图形库细节。随着非图形计算应用的增多，各种领域的用户对通用编程语言的需求增大。两大GPU厂商为扩大各自硬件产品的生态圈，分别推出不同通用计算语言，Ndivia的CUDA和AMD的Brook+。CUDA以C语言为基础，由于具备了以下两个优点，从而迅速增加了用户数量：(1)封装图形编程底层转化算法；(2)降低编程难度，用户无需考虑计算模型和操作资源的限制，利于集中设计特定应用领域算法。
4 GPU通用计算的应用
4.1在医疗领域的应用
（一）Folding@home项目，它(模拟蛋白质折叠)是一个研究研究蛋白质折叠，误折，聚合及由此引起的相关疾病的分布式计算工程。我们使用联网式的计算方式和大量的分布式计算能力来模拟蛋白质折叠的过程从而缩短人类对于癌症、阿兹海默症、帕金森氏症等的攻克过程。在NVIDIA@GeForce@GPU(图形处理器)上运行Folding@home客户端的实际结果表明，蛋白质折叠模拟工作的速度比当今的CPU快140倍。在Folding@home中应用如此强大的处理性能彻底改变了这一项目，极大地缩短了我们进行生物医学研究所需的时间。
（二）基于GPU通用计算的体绘制，体绘制是一种直接由三维数据产生屏幕上二维图像的技术。体绘制的相关研究实验分别从传统的基于GPU的体绘制和基于GPU通用计算的体绘制两个方面进行。传统体绘制使用吸收发射光照，CPU计算代理几何面，GPU绘制代理几何面用GPU通用计算时，使用阴影模型，GPU更新代理几何面，GPU进行多遍渲染。实验结构
表明，基于GPU通用计算的体会绘制无论是在代理几何更新速度还是体绘制速度都明显优于基于传统GPU的体绘制。因此，在体绘制方面GPU的通用计算能力是值得肯定的。
4.2在计算机网络领域的应用
在GPU 3D云计算网络应用方面，典型的应用有：建筑师及其客户将能够审阅精密的建筑模型，包括白天或黑夜不同设置下所渲染出的模型。在线买家将能够互动地设计家庭室内装潢、重新摆放家具以及查看家纺的装饰方式，所有这些都具备完美、精确的光照效果。这些成功案例表明未来我们网店选购时，可以实时的查看产品的三维立体动画，预览衣服、鞋子等的“试穿”效果，在房屋中随意摆放家具、调节灯光“体验”是否满足要求，这些强大的网络应用让人看到GPU计算在网络方面无限美好的未来。
5 结束语
GPU的通用计算能力已经在图形图像、医疗、高性能计算、网络等各个领域展取得了突破性的进展。随着GPU通用计算的继续高速的发展，今后将会引领出更多更好的应用技术，我们应该持续热衷于GPU通用性的研究和高度的关注GPU通用技术的发展，以挖掘出更强的GPU通用计算能力。图形处理器通用计算经过多年的发展，未来仍将继续保持高速发展。GPGPU的关键技术研究中存在如下挑战：（1）由于GPU硬件标准很难统一，因此导致编程模型中难以合理分配异构计算资源。而对硬件体系不敏感、高度抽象的通用编程语言一直会存在调试困难的挑战；（2）各种领域中的软件和算法向GPU移植的难题始终限制GPGPU发展，设计高可靠性和复用性的公共并行算法库是一种有效的解决途径；（3）有效地解决分布式共享存储模型中的数据一致性问题及造成的性能损失；（4）设计优化控制GPU缓存的普适性算法，对提高各类算法性能有重要价值． GPU通用计算的应用领域尚需拓展，复杂网络研究中社会网络、生物蛋白网络等均存在数据量大、计算密度大的重要算法，因此对复杂网络并行算法的研究是个崭新的交叉研究方向。
参考文献：
[1] Yang Xue-Jun, Yan Xiao-Bo, Xing Zuo-Cheng, Deng Yu, Jiang Jiang, Du Jing, Zhang Ying. Fei teng 64 stream processing system: Architecture, compiler, and programming. 2009, 20(8):1142-1156
[2] Wu En-Hua. State of the art and future challenge on general purposr computation by praphics processing unit. Journal of Software, 2004, 15(10):1493-1504
[3] Wu En-Hua, LIiu You-Quan. General purpose computation on GPU. Journal of computer Aided Design & Computer Graphics, 2004 , 16(5):601-611(in Chinese)
[4] Owens John D, Luebke D, Govindaraju N, Harris M, Kruger J, Lefohn Aaron E, Purcell Timothy J. A survey of general purpose computation on graphics hardware. Computer Graphics Forum, 2007 , 26(1):80-113
[5] Owens John D, Houston M, Luebke D, Green S, Stone John E, Phillips James C. GPU computing: Graphics processing units powerful, programmable, and highly parallel are increasingly targeting general-purposr computing applications. Proceedings of the IEEE, 2008 , 96(5): 879-899
[6] http: / / www1nvidia1com/ object/gpu1html[ OL]
[7 ]Dun das J, M udg e T . Improving Data Cache Performance by Pre-ex ecuting Instructions Under a Cache Miss[ C] // Proc of the 1997 Int, l Conf on Supercomputing, 1997.
[8] Owens John D, Houston M, Luebke D, Green S, Stone John E, Phillips James C. GPU computing: Graphics processing units powerful, programmable, and highly parallel are increasingly targeting general-purpose computing applications. Proceedings of the IEEE, 2008, 96(5):879-899
[9] Hensley Justin. AMD CTM overview//Proceedings of the Special Interest Group on Computer Graphics and Interactive Techniques (SIGGRAPH, 07). San Diego, California, USA, 2007 : 7-33 [10] Liu Wei, Lewis Brian, Zhou Xiao-Cheng et al. Abalanced programming model for emerging heterogeneous multicore system//Procecdings of the 2nd USENIX Conference on Hot Topics in Paralelism. California, USA, 2010: 3-6
[11] Buck I, Foley T, Horn D, Sugerman J, Fatahalian K ,Houston M, Hanrahan P. Brook for GPUs: Stream computing on graphics hardware. ACM Transactions on Graphics, 2004, 23(3): 777-786 [12] Karrenberg R, Hack S. Improving performance of OpenCL on CPUs// Proceedings of the 21st International Conference on Compiler Construction. Tallinn, Estonia, 2012: 1-20
[13] Noaje G, Jaillet C,Krajecki M. Source-to-source code translator: OpenMP C to CUD //Proceedings of the International Conference on High Performance Computing and Communication. Banff, AB, Canada,2011: 512-519
[14] Muller Christoph, Frey Steffen, Strengert Magnus. A compute unified system architecture for graphics clusters incorporating data locality. IEEE Transactions on Visualization and Computer Graphics ,2009, 15(4): 605-617
LSF高性能分布运算解决方案 一、系统组成 速度系统主要由IBM X3850 X5集群计算机、IBM X3650 M3 虚拟化服务器、Dell R5100图形工作站、存储系统组成。 IBM X3850 X5集群计算机：每个节点 4 颗CPU，每个 CPU 8核，主频 2.26GHz，节点内存 128GB。 IBM X3650 M3虚拟化服务器：每个节点 2 个 CPU，每个 CPU4核，主频 2.66GHz，节点内存 48GB。 Dell R5100图形工作站：每个节点包括 1个NVIDIA Quadro 6000 显示卡，主机CPU 主频为3.06 GHz，内存为 8GB，硬盘为 4*146GB。 存储系统：IBM DS5020 可用容量约为 12TB，由集群计算机、虚拟化服务器和图形工作站共享。 IBM X3850 X5计算集群运行用户的程序。 LSF高性能分布运算解决方案系统示意图 二、主要软件
1.操作系统：IBM X3850 X5集群计算机安装 64 位Windows2008 系统，IBM X3650 M3 安装Vmware ESX4.1系统，图形工作站安装64 位Windows2008 系统。 2.作业调度系统：Platform 公司的LSF。 3.应用软件：如表 1 所示。 名称厂家 LightTools ORA ZEMAX-EE Focus Software PADS ES Suite Ap SW Mentor Graphics Expedition PCB Pinnacle Mentor Graphics DxDesigner ExpPCB Bnd SW Mentor Graphics I/O Designer Ap SW Mentor Graphics Multi-FPGA Optimization Op S Mentor Graphics HyperLynx SI PI Bnd SW Mentor Graphics Questa Core VLOG Ap SW Mentor Graphics Precision RTL Plus Ap SW Mentor Graphics SystemVision 150 Ap SW Mentor Graphics FlowTHERM Parallel Ap SW Mentor Graphics Labview NI Code Composer Studio TI Quartus II Altera ISE Xilinx Vxworks Wind River Intel C++ Studio XE Intel MatLab及相关工具箱Mathworks Maple MapleSoft Oracle Oracle NX Mach 3 Product Design Siemens PLM Software ADAMS MSC
并行计算综述 姓名：尹航学号：S131020012 专业：计算机科学与技术摘要：本文对并行计算的基本概念和基本理论进行了分析和研究。主要内容有：并行计算提出的背景，目前国内外的研究现状，并行计算概念和并行计算机类型，并行计算的性能评价，并行计算模型，并行编程环境与并行编程语言。 关键词：并行计算；性能评价；并行计算模型；并行编程 1. 前言 网络并行计算是近几年国际上并行计算新出现的一个重要研究方向，也是热门课题。网络并行计算就是利用互联网上的计算机资源实现其它问题的计算，这种并行计算环境的显著优点是投资少、见效快、灵活性强等。由于科学计算的要求，越来越多的用户希望能具有并行计算的环境，但除了少数计算机大户（石油、天气预报等）外，很多用户由于工业资金的不足而不能使用并行计算机。一旦实现并行计算，就可以通过网络实现超级计算。这样，就不必要购买昂贵的并行计算机。 目前，国内一般的应用单位都具有局域网或广域网的结点，基本上具备网络计算的硬件环境。其次，网络并行计算的系统软件PVM是当前国际上公认的一种消息传递标准软件系统。有了该软件系统，可以在不具备并行机的情况下进行并行计算。该软件是美国国家基金资助的开放软件，没有版权问题。可以从国际互联网上获得其源代码及其相应的辅助工具程序。这无疑给人们对计算大问题带来了良好的机遇。这种计算环境特别适合我国国情。 近几年国内一些高校和科研院所投入了一些力量来进行并行计算软件的应用理论和方法的研究，并取得了可喜的成绩。到目前为止，网络并行计算已经在勘探地球物理、机械制造、计算数学、石油资源、数字模拟等许多应用领域开展研究。这将在计算机的应用的各应用领域科学开创一个崭新的环境。 2. 并行计算简介[1] 2.1并行计算与科学计算 并行计算（Parallel Computing），简单地讲，就是在并行计算机上所作的计算，它和常说的高性能计算（High Performance Computing）、超级计算（Super Computing）是同义词，因为任何高性能计算和超级计算都离不开并行技术。
西安科技大学 计算机科学与技术学院 实习报告 课程：大数据和并行计算 班级：网络工程 姓名： 学号：
前言 大数据技术(big data)，或称巨量资料，指的是所涉及的资料量规模巨大到无法通过目前主流软件工具，在合理时间内达到撷取、管理、处理、并整理成为帮助企业经营决策更积极目的的资讯。在维克托·迈尔-舍恩伯格及肯尼斯·库克耶编写的《大数据时代》中大数据指不用随机分析法（抽样调查）这样的捷径，而采用所有数据进行分析处理。大数据的4V特点：Volume（大量）、Velocity（高速）、Variety（多样）、Value（价值）。 特点具体有： 大数据分析相比于传统的数据仓库应用，具有数据量大、查询分析复杂等特点。《计算机学报》刊登的“架构大数据：挑战、现状与展望”一文列举了大数据分析平台需要具备的几个重要特性，对当前的主流实现平台——并行数据库、MapReduce及基于两者的混合架构进行了分析归纳，指出了各自的优势及不足，同时也对各个方向的研究现状及作者在大数据分析方面的努力进行了介绍，对未来研究做了展望。 大数据的4个“V”，或者说特点有四个层面：第一，数据体量巨大。从TB级别，跃升到PB级别；第二，数据类型繁多。前文提到的网络日志、视频、图片、地理位置信息等等。第三，处理速度快，1秒定律，可从各种类型的数据中快速获得高价值的信息，这一点也是和传统的数据挖掘技术有着本质的不同。第四，只要合理利用数据并对其进行正确、准确的分析，将会带来很高的价值回报。业界将其归纳为4个“V”——Volume（数据体量大）、Variety（数据类型繁多）、Velocity（处理速度快）、Value（价值密度低）。 从某种程度上说，大数据是数据分析的前沿技术。简言之，从各种各样类型的数据中，快速获得有价值信息的能力，就是大数据技术。明白这一点至关重要，也正是这一点促使该技术具备走向众多企业的潜力。 1.大数据概念及分析 毫无疑问，世界上所有关注开发技术的人都意识到“大数据”对企业商务所蕴含的潜在价值，其目的都在于解决在企业发展过程中各种业务数据增长所带来的痛苦。 现实是，许多问题阻碍了大数据技术的发展和实际应用。 因为一种成功的技术，需要一些衡量的标准。现在我们可以通过几个基本要素来衡量一下大数据技术，这就是——流处理、并行性、摘要索引和可视化。 大数据技术涵盖哪些内容? 1.1流处理 伴随着业务发展的步调，以及业务流程的复杂化，我们的注意力越来越集中在“数据流”而非“数据集”上面。 决策者感兴趣的是紧扣其组织机构的命脉，并获取实时的结果。他们需要的是能够处理随时发生的数据流的架构，当前的数据库技术并不适合数据流处理。 1.2并行化 大数据的定义有许多种，以下这种相对有用。“小数据”的情形类似于桌面环境，磁盘存储能力在1GB到10GB之间，“中数据”的数据量在100GB到1TB之间，“大数据”分布式的存储在多台机器上，包含1TB到多个PB的数据。 如果你在分布式数据环境中工作，并且想在很短的时间内处理数据，这就需要分布式处理。 1.3摘要索引 摘要索引是一个对数据创建预计算摘要，以加速查询运行的过程。摘要索引的问题是，你必须为要执行的查询做好计划，因此它有所限制。 数据增长飞速，对摘要索引的要求远不会停止，不论是长期考虑还是短期，供应商必须对摘要索引的制定有一个确定的策略。 1.4数据可视化 可视化工具有两大类。
2014年《并行计算系统》复习题 （15分）给出五种并行计算机体系结构的名称，并分别画出其典型结构。 ①并行向量处理机（PVP） ②对称多机系统（SMP） ③大规模并行处理机（MPP） ④分布式共享存储器多机系统（DSM） ⑤工作站机群（COW） （10分）给出五种典型的访存模型，并分别简要描述其特点。 ①均匀访存模型（UMA）： 物理存储器被所有处理机均匀共享 所有处理机访存时间相同 适于通用的或分时的应用程序类型 ②非均匀访存模型（NUMA）： 是所有处理机的本地存储器的集合 访问本地LM的访存时间较短 访问远程LM的访存时间较长 ③Cache一致性非均匀访存模型（CC-NUMA）： DSM结构 ④全局Cache访存模型（COMA）： 是NUMA的一种特例，是采用各处理机的Cache组成的全局地址空间 远程Cache的访问是由Cache目录支持的 ⑤非远程访存模型（NORMA）： 在分布式存储器多机系统中，如果所有存储器都是专用的，而且只能被本地存储机访问，则这种访问模型称为NORAM 绝大多数的NUMA支持NORAM 在DSM中，NORAM的特性被隐匿的 3. （15分）对于如下的静态互连网络，给出其网络直径、节点的度数、对剖宽度，说明该网络是否是一个对称网络。 网络直径：8 节点的度数：2 对剖宽度：2 该网络是一个对称网络 4. （15分）设一个计算任务，在一个处理机上执行需10个小时完成，其中可并行化的部分为9个小时，不可并行化的部分为1个小时。问： （1）该程序的串行比例因子是多少，并行比例因子是多少？ 串行比例因子：1/10
并行比例因子:9/10 如果有10个处理机并行执行该程序，可达到的加速比是多少？ 10/(9/10 + 1) = 5.263 （3）如果有20个处理机并行执行该程序，可达到的加速比是多少？ 10/(9/20 + 1)= 6.897 （15分）什么是并行计算系统的可扩放性？可放性包括哪些方面？可扩放性研究的目的是什么？ 一个计算机系统（硬件、软件、算法、程序等）被称为可扩放的，是指其性能随处理机数目的增加而按比例提高。例如，工作负载能力和加速比都可随处理机的数目的增加而增加。可扩放性包括: 1.机器规模的可扩放性 系统性能是如何随着处理机数目的增加而改善的 2.问题规模的可扩放性 系统的性能是如何随着数据规模和负载规模的增加而改善 3.技术的可扩放性 系统的性能上如何随着技术的改变而改善 可扩放性研究的目的: 确定解决某类问题时何种并行算法与何种并行体系结构的组合，可以有效的利用大量的处理器； 对于运用于某种并行机上的某种算法，根据在小规模处理机的运行性能预测移植到大规模处理机上的运行性能; 对固定问题规模，确定最优处理机数和可获得的最大的加速比 （15分）给出五个基本的并行计算模型，并说明其各自的优缺点。 ①PRAM：SIMD-SM 优点： 适于表示和分析并行计算的复杂性； 隐匿了并行计算机的大部底层细节（如通信、同步），从而易于使用。 缺点： 不适于MIMD计算机，存在存储器竞争和通信延迟问题。 ②APRAM:MIMD-SM 优点： 保存了PRAM的简单性； 可编程性和可调试性（correctness）好； 易于进行程序复杂性分析。 缺点： 不适于具有分布式存储器的MIMD计算机。 ③BSP：MIMD-DM 优点: 把计算和通信分割开来； 使用hashing自动进行存储器和通信管理； 提供了一个编程环境。 缺点： 显式的同步机制限制并行计算机数据的增加； 在一个Superstep中最多只能传递h各报文。
最短路径的并行算法综述 SA02011105 陈艾 (aiai@https://www.doczj.com/doc/d68343907.html,) 摘要：最短路径问题是图论中的一个典范问题，它被应用于众多领域。最短路径问题可以分成两类：单源最短路径、所有顶点对间的最短路径。本文对最短路径的并行算法进行综述，并介绍目前最短路径问题中的一个热点问题K条最短路径。 关键字：最短路径，单源最短路径，所有顶点对间的最短路径，K条最短路径 A Summary on Parallel Algorthms for Shortest Path Problems SA02011105 CHEN Ai Abstract:The shortest path problem plays an important role in graph theory .It is applied to numerous area . It is composed of two parts: single source shortest paths and all pairs shortest paths. This paper presents a summary on parallel algorithms for the shortest path problems including introducing a hot issue k shortest paths in shortest path problems at present. Keywords:Shortest paths，Single source shortest paths，All pairs shortest paths，K shortest paths 1. 引言 二十世纪中后期，随着计算机的出现和发展，图论的研究得到广泛重视，最短路径问题是图论中的一个典范问题，它已经被应用于众多领域。最短路径问题最直接的应用当数在地理信息领域，如：GIS网络分析、城市规划、电子导航等。在交通咨询方面，寻找交通路网中两个城市间最短的行车路线就是最短路径问题的一个典型的例子。在网络通信领域，信息包传递的路径选择问题也与最短路径问题息息相关。举个例子，OPSF开放路由选择协议，每 1 SA02011105 陈艾
万方数据
２ＬＢＧＫＤ２Ｑ９模型的并行计算 ２．１数据分布 将流场划分成Ｎ。ｘＮ，的网格。设有Ｐ＝只×Ｐｖ个进程参与并行计算，进程号Ｐ。＝Ｈ以（０≤ｉ＜只，０≤Ｊ＜尸ｖ）。将数据按照重叠一条边的分块分布到各进程中。其中，进程Ｐ。存储并处理的数据网格点集，如图ｌ所示。 图１进程珊存储并处理的区域（斜线处为重叠部分） ２．２交替方向的Ｊａｃｏｂｉ迭代通信 Ｊａｃｏｂｉ迭代是一类典型的通信迭代操作。文献［４】主要讨论了一个方向的Ｊａｃｏｂｉ迭代。根据数据分布及计算要求，需要采用２个方向交替的Ｊａｃｏｂｉ迭代通信操作。本文认为，“即发即收”的通信策略能有效避免完全的“先发后收”可能造成的通信数据“堆积”过多，从而避免数据的丢失。进程Ｐｌｉ的通信操作如下（见图２）： （１）Ｉｆｉ≠只一１ｔｈｅｎ发送数据到进程Ｐ¨，； （２）Ｉｆｉ≠０ｔｈｅｎ从进程Ｐｆ＿Ｊ，接收数据； （３）Ｉｆ，≠只－１ｔｈｅｎ发送数据到进程Ｐｍｌ； （４）ＩｆＪ≠０ｔｈｅｎ从进程Ｐ—ｌ接收数据。 各进程并行执行上述操作。 图２交普方向的Ｊａｃｏｂｉ迭代 ２．３通信时间理论 由一般的通信模型可知，若发送、接收信息长度为ｎ字节的数据所需时间为：丁（ｎ）＝口＋ｎ∥，其中，常数口为通信启动时间；∥为常系数，则上述一次交替方向的Ｊａｃｏｂｉ迭代通信操作的时间约为 ２０ｅ＋２ｆｌ＇Ｎ、．Ｐ，＝１ Ｐ。＝１ 其他 其中，∥７＝∥ｓｉｚｅｏｆ（ｄｏｕｂｌｅ）。 一般情况下，当等３鲁，即等＝鲁时，通信的数据量（字节数）是最少的，为４口＋４∥，．／丝堡。可见，通信的信息 Ｖ只×０ 总量和通信时间随进程总数只×尸ｖ的增加而减少。 由于ｃ语言中数组是按“行”存放的（Ｆｏｒｔｒａｎ是按“列”存放的），当存放、发送列数据时，需要一定的辅助操作，这就增加了并行计算的计算时间，因此在只：Ｐｖ无法恰好等于Ｎｘ：Ｎ。时，需要综合考虑流场形状及大小、数据在内存中的按“行”（或按“列”）的存放方式，以确定数据的最佳分布方案。 ３数值实验 数值实验是在“自强３０００”计算机上进行的ｏｕ自强３０００”计算机拥有１７４个计算结点，每个计算结点上有２个３．０６ＣＰＵ，２ＧＢ内存。本文的实验使用了其中的３２个计算结点共６４个ＣＰＵ。程序采用ＭＰＩ及Ｃ语言编写，程序执行时，每个计算结点中启动２个进程。数值实验针对不同规模的网格划分、不同进程数以及不同的数据分布方案进行了大量实验，测得如下结果：不同的流场规模对应着各自的最佳网格划分方式；计算次数越多，加速比越大，越能体现并行计算的优越性。 由表１数据可以得知，对于规模为Ｎｘ×Ｎ、，＝４００ｘ４００，数据划分成６×６块时的加速比最高，而对于ＭＸＮｙ＝６００ｘ２００，数据划分为１２×３块则更具优越性。合适的划分方式可以使总体通信量减至最少，从而提高加速比和并行效率。另外，计算规模越大，加速比越大。 表１并行计算Ｄ２Ｑ９模型的加速比（进程数为３６） 在固定计算规模，增加处理器的情况下，并行系统的加速比会上升，并行效率会下降；在固定处理器数目，增加计算规模的情况下，并行系统的加速比和效率都会随之增加。 从表２可见，流场规模越大，并行计算的优越性越显著。因为此时计算规模（粒度）较大，相对于通信量占有一定的优势。由图３可见，加速比随进程数呈线性增长，这表明ＬＢＧＫＤ２Ｑ９模型的并行计算具有良好的可扩展性。 表２漉场规模固定时并行计算Ｄ２Ｑ９模型的加速比 ０８１６２４３２４０４８５６６４ ｎｕｍｏｆｐｒｏｃｅｓｓ 图３藐场规模固定时Ｄ２Ｑ９模型并行计算的加速比 ４结束语 本文讨论了ＬＢＧＫＤ２Ｑ９模型的分布式并行计算，通过大量的数值实验重点研究了数据分布方案如何与问题规模匹配，以获得更高的并行效率的问题。展示了ＬＢＧＫ模型方法良好的并行性和可扩展性。得到了二维ＬＢＧＫ模型并行计算数据分布的一般原则、交替方向Ｊａｃｏｂｉ迭代的通信策略。这些结论对进一步开展三维ＬＢＧＫ模型的并行计算及其他类似问题的并行计算有一定的指导意义。（下转第１０４页） 一１０１—万方数据
Monte Carlo Methods in Parallel Computing Chuanyi Ding ding@https://www.doczj.com/doc/d68343907.html, Eric Haskin haskin@https://www.doczj.com/doc/d68343907.html, Copyright by UNM/ARC November 1995 Outline What Is Monte Carlo? Example 1 - Monte Carlo Integration To Estimate Pi Example 2 - Monte Carlo solutions of Poisson's Equation Example 3 - Monte Carlo Estimates of Thermodynamic Properties General Remarks on Parallel Monte Carlo What is Monte Carlo? ? A powerful method that can be applied to otherwise intractable problems ? A game of chance devised so that the outcome from a large number of plays is the value of the quantity sought ?On computers random number generators let us play the game ?The game of chance can be a direct analog of the process being studied or artificial ?Different games can often be devised to solve the same problem ?The art of Monte Carlo is in devising a suitably efficient game.
文献综述 计算机科学与技术 基于GPU并行计算的图像二值化研究 引言: 图像是当今社会运用的越来越多的元素之一，不过是动画还是静态的图片都是图像的动静呈现，所以对图像的处理也就越来越得到人们的关注。图像重要性，图像处理就是在图像中得到可靠的信息。而图像的二值化处理也是当今正盛行的一种图像的处理方法，它把图像原始化，使得数据更加简单的表现。 本毕业设计是GPU与二值化的并行运算，这无疑就是一种加速算法，也就是讲在二值化处理本来就跟快的基础上，能够更快的读取图像中的信息，得到我们想要的数据。而现在最常用的一种加速算法就是CUDA算法，他的并行运算可以使得二值化运算提高几十倍，在图像处理中是一个很庞大的数据。CUDA的并行运算在处理小图像时并不能很明显的突出速度，但是当遇到有大量的图像需要处理，而且图像又很大的情况下，这种并行运算可以节省很多时间。 1图像处理简介 1.1图像处理的概念 图像处理一般指数字图像处理。数字图像是指用数字摄像机、扫描仪等设备经过采样和数字化得到的一个大的二维数组，该数组的元素称为像素，其值为一整数，称为灰度值。图像处理技术的主要内容包括图像压缩，增强和复原，匹配、描述和识别3个部分。 常见的处理有图像数字化、图像编码、图像增强、图像复原、图像分割和图像分析等。图像处理一般指数字图像处理。虽然某些处理也可以用光学方法或模拟技术实现，但它们远不及数字图像处理那样灵活和方便，因而数字图像处理成为图像处理的主要方面。 1.2 图像二值化技术的简介 首先，图像的二值化有利于图像的进一步处理，使图像变得简单，而且数据量减小，能凸显出感兴趣的目标的轮廓。其次，要进行二值图像的处理与分析，首先要把灰度图像二值化，得到二值化图像。所有灰度大于或等于阀值的像素被判定为属于特定物体，其灰度值为255表示，否则这些像素点被排除在物体区域以外，灰度值为0，
计算机学院 课程设计 课程名称高性能计算设计 题目名称大规模并行计算 专业__ 软件工程 _ __ _ 年级班别 2012级 学号 学生姓名 指导教师 联系方式 2015年12月18日
结构化数据访问注释对于大规模并 行计算 马可aldinucci1索尼亚营，2，基尔帕特里克3，和马西莫torquati2p.kilpatrick@https://www.doczj.com/doc/d68343907.html, 1计算机科学系，大学都灵，意大利 aldinuc@di.unito.it 2比萨大学计算机科学系，意大利 {营，torquati}@di.unipi。它 3女王大学计算机科学系，贝尔法斯特 p.kilpatrick@https://www.doczj.com/doc/d68343907.html, 摘要。我们描述了一种方法，旨在解决的问题控制联合开发（流）和一个数据并行骨架吨并行编程环境，基于注释重构。注解驱动一个并行计算的高效实现。重构是用来改造相关联的骨架树到一个更高效，功能上相当于骨架树。在大多数情况下成本模型是用来驱动的重构过程。我们展示了如何示例用例应用程序/内核可以被优化，讨论初步的实验评估结果归属理论。 克-词：算法的骨架，并行设计模式，重构，数据并行性，成本模型。 1我新台币 结构化并行程序设计方法已抽象出概念控制和数据并行通过骨骼上的[ 10 ]，这是众所周知的PA T控制[ 8 ]燕鸥。控制并行的设想，设计和实施作为一个图的节点（骨架），每个节点代表一个函数。一股流独立的任务流经图：当每个节点的输入是有效的，它可以计算产生的输出被发送到它的连接节点。在另一方面，数据并行的kelet的描述一个计算模式定义如何在并行数据中访问数据，并将其应用于数据的功能分区以获得最终结果。传统上，控制之间的正交性并行和数据并行解决了采用双层模型控制流驱动的方法进行数据的并行能力增强，可能与并行数据结构暴露出集体行动[ 13 ]反之亦然。然而，控制并行和数据并行的方法。 这项工作已经由欧盟框架7批 ist-2011-288570”释义：自适应异构多核系统的并行模式” 我caragiannis 冯湛华。（E DS。）：E尿PAR 2012个车间，LNCS 7640，pp. 381–390，2013。他是cspringe r-ve rlag用IDE L B E RG 2013382米aldinucci等人。 往往缺乏有效的应用程序，在这两个问题的能力被利用，因为本质上不同的手段，通过并行表示，有时，优化。一种高效的任务分配控制驱动的环境，可我nvalidated由糟糕的数据访问策略，反之亦然[ 14 ]。 在本文中，我们勾勒出一个新的方法来面对的控制与基于数据并行二分法的思想，即：数据与控制并行关注需要独立表达因为他们描述正交方面的并行性，和II）的数据访问和控制的并行模式的需要becoordin ED为了有效地支持并行应用的实现。虽然利用并行模式是不是一个新的方法[ 11 ]和协调工作在过去的语言方面作出了努力[ 17,12 ]或框架，本文提出的想法是，这样的协调可以通过对控制定义的图形表示关于数据访问的骨架。此外，我们将展示如何这样的注释可以用来驱动优化的实施图的执行。 2他骨骼框架 考虑骨骼系统包括控制（即流）和数据并行骨架，造型更一般的并行开发模式。我们的骨架是由下面的语法定义的 这些骷髅代表著名的并行开发模式[ 4 ]：序列把现有的序列码，管/农场流并行骨架处理流项
Hadoop部署 所需要的软件 使用VMwareWorkstationPro搭建虚拟机，安装操作系统 Ubuntu14.04。 JDK1.8 Hadoop2.6.0 1.在Ubuntu中安装JDK 将JDK解压缩到 /home/kluas/java 在~/.bash_profile中配置环境变量，并通过source~/.bash_profile生效。 #java export JAVA_HOME=/home/kluas/java/jdk export JRE_HOME=/home/kluas/java/jdk/jre export PATH=$JAVA_HOME/bin;$JRE_HOME/bin:$PATH export CLASSPATH=$JAVA_HOME/lib:$JRE_HOME/lib:$CLASSPATH 检验JDK是否安装成功 java –version 2.配置ssh信任关系，实现无密码登录 生成机器A的公私密钥对：ssh-keygen -t rsa，之后一路回车。在~/.ssh 目录下生成公钥id_rsa.pub，私钥id_ras。 拷贝机器A的id_rsa.pub到机器B的认证文件中： cat id_rsa.pub >> ~/.ssh/authorized_keys 这时候机器A到机器B的信任关系就建立好了，此时在机器A可以不需要密码直接ssh登录机器B了 3.安装Hadoop2.6.0 解压hadoop软件包，编辑/etc/profile文件，并追加 export HADOOP_HOME=/usr/kluas/Hadoop export PATH=HADOOP_HOME/bin:$PATH 运行 source /etc/profile命令 修改配置文件hadoop目录etc/Hadoop/Hadoop-env.sh追加： export JAVA_HOME=/home/kluas/java/jdk 修改配置文件hadoop目录下etc/Hadoop/core-site.xml追加：
并行计算技术及其应用简介 XX （XXX，XX，XXX） 摘要：并行计算是实现高性能计算的主要技术手段。在本文中从并行计算的发展历程开始介绍，总结了并行计算在发展过程中所面临的问题以及其发展历程中出现的重要技术。通过分析在当前比较常用的实现并行计算的框架和技术，来对并行计算的现状进行阐述。常用的并行架构分为SMP（多处理系统）、NUMA （非统一内存存储）、MPP（巨型并行处理）以及集群。涉及并行计算的编程模型有MPI、PVM、OpenMP、TBB及Cilk++等。并结合当前研究比较多的云计算和大数据来探讨并行计算的应用。最后通过MPI编程模型，进行了并行编程的简单实验。 关键词：并行计算；框架；编写模型；应用；实验 A Succinct Survey about Parallel Computing Technology and It’s Application Abstract:Parallel computing is the main technology to implement high performance computing. This paper starts from the history of the development of Parallel Computing. It summarizes the problems faced in the development of parallel computing and the important technologies in the course of its development. Through the analysis of framework and technology commonly used in parallel computing currently,to explain the current situation of parallel computing.Framework commonly used in parallel are SMP(multi processing system),NUMA(non uniform memory storage),MPP(massively parallel processing) and cluster.The programming models of parallel computing are MPI, PVM, OpenMP, TBB and Cilk++, etc.Explored the application of parallel computing combined with cloud computing and big data which are very popular in current research.Finally ,through the MPI programming model,a simple experiment of parallel programming is carried out. Key words:parallel computing; framework; programming model; application; experiment 1引言 近年来多核处理器的快速发展，使得当前软件技术面临巨大的挑战。单纯的提高单机性能，已经不能满足软件发展的需求，特别是在处理一些大的计算问题上，单机性能越发显得不足。在最近AlphaGo与李世石的围棋大战中，AlphaGo就使用了分布式并行计算技术，才能获得强大的搜索计算能力。并行计算正是在这种背景下，应运而生。并行计算或称平行计算时相对于串行计算来说的。它是一种一次可执行多个指令的算法，目的是提高计算速度，及通过扩大问题求解规模，解决大型而复杂的计算问题。可分为时间上的并行和空间上的并行。时间上的并行就是指流水线技术，而空间上的并行则是指用多个处理器并发的执行计算。其中空间上的并行，也是本文主要的关注点。 并行计算（Parallel Computing）是指同时使用多种计算资源解决计算问题的过程，是提高计算机系统计算速度和处理能力的一种有效手段。它的基本思想是用多个处理器来协同求解同一问题，即将被求解的问题分解成若干个部分，各部分均由一个独立的处理机来并行计算。并行计算系统既可以是专门设计的，含有多个处理器的超级计算机，也可以是以某种方式互联的若干台的独立计算机构成的集群。通过并行计算集群完成数据的处理，再将处理的结果返回给用户。 目前常用的并行计算技术中，有调用系统函数启动多线程以及利用多种并行编程语言开发并行程序，常用的并行模型有MPI、PVM、OpenMP、TBB、Cilk++等。利用这些并行技术可以充分利用多核资源适应目前快速发展的社会需求。并行技术不仅要提高并行效率，也要在一定程度上减轻软件开发人员负担，如近年来的TBB、Cilk++并行模型就在一定程度上减少了开发难度，提高了开发效率，使得并行软件开发人员把更多精力专注于如何提高算法本身效率，而非把时间和精力放在如何去并行一个算法。
第三章互连网络 对于一颗K级二叉树（根为0级，叶为k-1级），共有N=2^k-1个节点，当推广至m-元树时（即每个非叶节点有m个子节点）时，试写出总节点数N的表达式。 答： 推广至M元树时，k级M元树总结点数N的表达式为： N=1+m^1+m^2+...+m^（k-1）=(1-m^k)*1/(1-m); 二元胖树如图所示，此时所有非根节点均有2个父节点。如果将图中的每个椭圆均视为单个节点，并且成对节点间的多条边视为一条边，则他实际上就是一个二叉树。试问：如果不管椭圆，只把小方块视为节点，则他从叶到根形成什么样的多级互联网络 答：8输入的完全混洗三级互联网络。 四元胖树如图所示，试问：每个内节点有几个子节点和几个父节点你知道那个机器使用了此种形式的胖树 答：每个内节点有4个子节点，2个父节点。CM-5使用了此类胖树结构。 试构造一个N=64的立方环网络，并将其直径和节点度与N=64的超立方比较之，你的结论是什么 答：A N=64的立方环网络,为4立方环（将4维超立方每个顶点以4面体替代得到），直径d=9，节点度n=4 B N=64的超立方网络，为六维超立方（将一个立方体分为8个小立方，以每个小立方作为简单立方体的节点，互联成6维超立方），直径d=6，节点度n=6 一个N=2^k个节点的 de Bruijin 。 。。。试问：该网络的直径和对剖宽度是多少 答：N=2^k个节点的 de Bruijin网络直径d=k 对剖宽带w=2^(k-1)
一个N=2^n个节点的洗牌交换网络如图所示。试问：此网络节点度==网络直径==网络对剖宽度== 答：N=2^n个节点的洗牌交换网络，网络节点度为=2 ，网络直径=n-1 ，网络对剖宽度=4 一个N=（k+1）2^k个节点的蝶形网络如图所示。试问：此网络节点度=网络直径=网络对剖宽度= 答：N=（k+1）2^k个节点的蝶形网络，网络节点度=4 ，网络直径=2*k ，网络对剖宽度=2^k 对于如下列举的网络技术，用体系结构描述，速率范围，电缆长度等填充下表中的各项。（提示：根据讨论的时间年限，每项可能是一个范围） 答： 如图所示，信包的片0，1，2，3要分别去向目的地A，B，C，D。此时片0占据信道CB，片1占据信道DC，片2占据信道AD，片3占据信道BA。试问： 1）这将会发生什么现象 2）如果采用X-Y选路策略，可避免上述现象吗为什么 答： 1）通路中形成环，发生死锁
并行计算简介 Blaise Barney, 劳伦斯利弗莫尔国家实验室 译者：卢洋，同济大学 原文地址：https://https://www.doczj.com/doc/d68343907.html,/tutorials/parallel_comp/ 目录 1 摘要 2 概述 2.1 什么是并行计算 2.2 为什么使用并行计算 3 概念和术语 3.1 冯诺依曼体系结构 3.2 Flynn经典分类法 3.3 一些通用的并行术语 4 并行计算机存储结构 4.1 共享内存 4.2 分布式内存 4.3 混合型分布式共享内存 5 并行编程模型 5.1 概览 5.2 共享内存模型 5.3 线程模型 5.4 消息传递模型 5.5 数据并行模型 5.6 其他模型 6 设计并行程序 6.1 自动化vs. 手工并行化 6.2 问题的理解和程序 6.3 问题分解
6.4 通信 6.5 同步 6.6 数据依赖 6.7 负载平衡 6.8 粒度 6.9 I/O 6.10 并行程序设计的限制和消耗 6.11 性能分析与调整 7 并行示例 7.1 数组程序 7.2 PI 的计算 7.3 简单的加热等式 7.4 一维的波等式 8 参考和更多信息 1 摘要 为了让新手更加容易熟悉此话题，本教程覆盖了并行计算中比较基础的部分。首先在概述中介绍的是与并行计算相关的术语和概念。然后探索并行存储模型和编程模型这两个话题。之后讨论一些并行程序设计相关的问题。本教程还包含了几个将简单串行化程序并行化的例子。无基础亦可阅读。 2 概述 2.1 什么是并行计算 传统上，一般的软件设计都是串行式计算： -软件在一台只有一个CPU的电脑上运行； -问题被分解成离散的指令序列； -指令被一条接一条的执行； -在任何时间CPU上最多只有一条指令在运行 图
Visual Studio 2010并行计算概述 并行计算(Parallel Computing)是指同时使用多台计算机协同合作解决计算问题的过程，其主要目的是快速解决大型且复杂的计算问题。 图1：计算原理 并行计算是相对于串行计算——即在单个计算机(具有单个中央处理单元)上执行的操作，所提出的。具体的说，并行计算是在多台(并行)计算机上将一个应用任务分解成多个子任务，分配给不同的处理器，各个处理器之间相互协同，同时执行子任务的过程。并行计算可分为时间上的并行和空间上的并行。时间上的并行就是指流水线技术，而空间上的并行则是指用多个处理器并发的执行计算。为执行并行计算，计算资源应包括一台配有多处理(或并行处理)机的计算机和一个与网络相连的计算机专有编号。
图2：(a)SIMD类型 (b)MIMD类型 目前，对于并行计算的研究主要集中在空间上的并行问题上。空间上的并行导致了两类并行机的产生，即单指令流多数据流(SIMD)和多指令流多数据流(MIMD)。类似地，我们常用的串行机有时也被称为单指令流单数据流(SISD)。在1972年诞生的第一台并行计算机ILLIAC IV就属于SIMD类型机器。而自上个世纪八十年代以来，都是以MIMD并行计算机的研制为主。常见的MIMD类的机器可分：并行向量处理机(PVP)、对称多处理机(SMP)、大规模并行处理机(MPP)、工作站机群(COW)、分布式共享存储处理机(DSM)等五 类。并行计算机主要有以下四种访存模型： l 均匀访存模型(UMA) 非均匀访存模型(NUMA)l 全高速缓存访存模型(COMA)l l 一致性高速缓存非均匀存储访问模型(CC-NUMA)和非远程存储访问模型(NORMA)。
并行计算环境介绍 计算机系04 级研究生 武志鹏 1 MPI简介 目前两种最重要的并行编程模型是数据并行和消息传递。 数据并 行编程模型的编程级别比较高，编程相对简单，但它仅适用于数据并 行问题；消息传递编程模型的编程级别相对较低，但消息传递编程模 型可以有更广泛的应用范围。 MPI就是一种消息传递编程模型，并成为这种编程模型的代表和 事实上的标准。 1.1什么是 MPI 对MPI的定义是多种多样的，但不外乎下面三个方面： (1) MPI是一个库，而不是一门语言； (2) MPI是一种标准或规范的代表，而不特指某一个对它的实现； (3) MPI是一种消息传递编程模型，MPI虽然很庞大，但是它的最 终目的是服务于进程间通信这一目标的。 1.2 MPI的历史 MPI的标准化开始于1992年4月在威吉尼亚的威廉姆斯堡召开的分 布存储环境中消息传递标准的讨论会，由Dongarra,Hempel,Hey和 Walker建议的初始草案，于1992年11月推出并在1993年2月完成了修
订版，这就是MPI 1.0。 1995年6月推出了MPI的新版本MPI1.1，对原来的MPI作了进一步 的修改完善和扩充。 在1997年7月在对原来的MPI作了重大扩充的基础上又推出了MPI 的扩充部分MPI-2，而把原来的MPI各种版本称为MPI-1。 MPI-2的扩 充很多但主要是三个方面：并行I/O、远程存储访问和动态进程管理。 1.3 MPI的语言绑定 在MPI-1中明确提出了MPI和FORTRAN 77与C语言的绑定，并且 给出了通用接口和针对FORTRAN 77与C的专用接口说明。在MPI-2 中除了和原来的FORTRAN 77和C语言实现绑定之外，进一步与 Fortran90和C++结合起来。 1.4 MPI的实现版本 MPICH是一种最重要的MPI实现， 它是与MPI-1规范同步发展的版 本，每当MPI推出新的版本，就会有相应的MPICH的实现版本，另外 它还支持部分MPI-2的特征。 LAM-MPI也是一种MPI实现， 主要用于异构的计算机网络计算系统。 以上2种版本的MPI实现可以分别从以下网址下载： MPICH(最新版本1.2.7): https://www.doczj.com/doc/d68343907.html,/mpi/mpich/ LAM-MPI(最新版本7.1.2)：
MapReduce并行计算技术发展综述 摘要:经过几年的发展,并行编程模型MapReduce产生了若干个改进框架,它们都是针对传统MapReduce的不足进行的修正或重写.本文阐述和分析了这些研究成果,包括:以HaLoop为代表的迭代计算框架、以Twitter为代表的实时计算框架、以ApacheHama为代表的图计算框架以及以ApacheY ARN为代表的框架管理平台.这些专用系统在大数据领域发挥着越来越重要的作用. MapReduce[1]是Google公司于2004年提出的能并发处理海量数据的并行编程模型,其特点是简单易学、适用广泛,能够降低并行编程难度,让程序员从繁杂的并行编程工作中解脱出来,轻松地编写简单、高效的并行程序.针对上述问题,MapReduce并行编程模型的最大优势在于能够屏蔽底层实现细节,有效降低并行编程难度,提高编程效率.其主要贡献在于: 使用廉价的商用机器组成集群,费用较低,同时又能具有较高的性能; 松耦合和无共享结构使之具有良好的可扩展性; 用户可根据需要自定义Map、Reduce和Partition等函数; 提供了一个运行时支持库,它支持任务的自动并行执行.提供的接口便于用户高效地进行任务调度、负载均衡、容错和一致性管理等; MapReduce适用范围广泛,不仅适用于搜索领域,也适用于满足MapReduce要求的其它领域计算任务 2 MapReduce总体研究状况 最近几年,在处理TB和PB级数据方面,MapReduce 已经成为使用最为广泛的并行编程模型之一.国内外MapReduce相关的研究成果主要有以下几方面: (1)在编程模型改进方面:MapReduce存在诸多不足.目前,典型研究成果有Barrier-lessMapReduce[6]、MapReduceMerge[7]、Oivos[8]、Kahnprocessnetworks[9]等.但这些模型均仅针对MapReduce某方面的不足,研究片面,并且都没有得到广泛应用,部分模型也不成熟 (2)在模型针对不同平台的实现方面:典型研究成果包括:Hadoop[10]、Phoenix[11,12]、Mars13]、CellMapRe-duce[14]、Misco[15]和Ussop[16]部分平台(例如:GPUs和Cell/B.E.)由于底层硬件比较复杂,造成编程难度较大,增加了用户编程的负担. \(3)在运行时支持库(包括:任务调度、负载均衡和容错)方面:常用的任务调度策略是任务窃取,但该策略有时会加大通信开销.典型的研究成果包括:延迟调度策略[17]、LATE调度策略[18]和基于性能驱动的任务调度策略[19]等.在容错方面的典型研究成果是reduce对象[20].目前,运行时支持库中针对一致性管理和资源分配等方面的研究相对较少. (4)在性能分析与优化方面: 目前, 文献[ 21]主要研究在全虚拟环境下MapReduce 性能分析, 文献[ 22]则提出了名为MRBench 的性能分析评价指标. 性能优化典型成果包括: 几何规划[ 23]、动态优先级管理[ 24]和硬件加速器[ 25]等. 着眼于性能, 结合运行时支持库, 将是MapReduce研究的热点之一. (5)在安全性和节能方面: 安全性方面典型研究成果是Sec ureMR模型[ 2 6]. 文献[ 27]和文献[ 28] 则在节能方面做了相应的研究. 目前国内外在安全性和节能方面的研究成果相对较少, 但是这方面研究的重要性已经得到了越来越多的重视. 如果一个模型没有很高的安全性, 同时也没有很好地考虑功耗问题, 那对其大范围推广将产生致命的影响. (6)在实际应用方面: MapReduce 应用范围广泛,Google 等诸多公司都在使用MapReduce 来加速或者简化各自公司的业务[ 29]. MapReduce 还广泛应用于云计算[ 3 0]和图像处理[ 31]等领域. 随着科技的进步, MapRe -duc e 将会得到越来越广泛的应用 .国内学者MapReduce 相关研究成果主要集中在实际应用方面. 例如, 把MapReduce 应用于模式发现[ 32]和数据挖掘[ 3 3]等领域. 部分研究成果涉及模型针对不同平台的实现、任务调度、容错和性能评估优化. 例如, 文献[ 34]提出了名为FPMR 的基于FPGA 平台的