并行计算综述
并行计算综述
姓名：尹航学号：S131020012 专业：计算机科学与技术摘要：本文对并行计算的基本概念和基本理论进行了分析和研究。主要内容有：并行计算提出的背景，目前国内外的研究现状，并行计算概念和并行计算机类型，并行计算的性能评价，并行计算模型，并行编程环境与并行编程语言。
关键词：并行计算；性能评价；并行计算模型；并行编程
1. 前言
网络并行计算是近几年国际上并行计算新出现的一个重要研究方向，也是热门课题。网络并行计算就是利用互联网上的计算机资源实现其它问题的计算，这种并行计算环境的显著优点是投资少、见效快、灵活性强等。由于科学计算的要求，越来越多的用户希望能具有并行计算的环境，但除了少数计算机大户（石油、天气预报等）外，很多用户由于工业资金的不足而不能使用并行计算机。一旦实现并行计算，就可以通过网络实现超级计算。这样，就不必要购买昂贵的并行计算机。
目前，国内一般的应用单位都具有局域网或广域网的结点，基本上具备网络计算的硬件环境。其次，网络并行计算的系统软件PVM是当前国际上公认的一种消息传递标准软件系统。有了该软件系统，可以在不具备并行机的情况下进行并行计算。该软件是美国国家基金资助的开放软件，没有版权问题。可以从国际互联网上获得其源代码及其相应的辅助工具程序。这无疑给人们对计算大问题带来了良好的机遇。这种计算环境特别适合我国国情。
近几年国内一些高校和科研院所投入了一些力量来进行并行计算软件的应用理论和方法的研究，并取得了可喜的成绩。到目前为止，网络并行计算已经在勘探地球物理、机械制造、计算数学、石油资源、数字模拟等许多应用领域开展研究。这将在计算机的应用的各应用领域科学开创一个崭新的环境。
2. 并行计算简介[1]
2.1并行计算与科学计算
并行计算（Parallel Computing），简单地讲，就是在并行计算机上所作的计算，它和常说的高性能计算（High Performance Computing）、超级计算（Super Computing）是同义词，因为任何高性能计算和超级计算都离不开并行技术。
2.1.1科学与工程计算的需求
在应用需求方面，人类对计算机性能的需求总是永无止境的，在诸如预测模型的构造和模拟、工程设计和自动化、能源勘探、医学、军事以及基础理论研究等领域中都对计算提出了极高的具有挑战性的要求。例如，在作数值气象预报时，要提高全球气象预报的准确性，据估计在经度、纬度和大气层方向上至少要取200*100*20＝40万各网格点。
并行计算机产生和发展的目的就是为了满足日益增长的大规模科学和工程计算、事务处理和商业计算的需求。问题求解最大规模是并行计算机的最重要的指标之一，也是一个国家高新技术发展的重要标志。
一般地，问题规模分解为输入输出规模、计算规模、内存需求、通信（同步）规模，分别表示问题求解所需的I/O量、计算量、内存大小和通信量（包括通信次数和通信数据量）。根据在求解中所消耗资源的程度，问题由相应分为CPU密集型应用、Memory密集型应用、Disk密集型应用和网络密集型应用。针对不同类型的问题，性能瓶颈也往往不同，并行算法就是有针对性地消除相应的瓶颈，从而达到缩短计算时间的目的。
对并行计算的需求是广泛的，但归纳起来主要有三种类型的应用需求：计算密集（Compute-Intensive）型应用，如大型科学工程计算与数值模拟；数据密集(Data-Intensive)型应用,如数值图书馆、数据仓库、数据开采和计算可视化等；网络密集（Network-Intensive）型应用，如协同工作、遥控和远程医疗诊断等。
2.2目前国内外的研究现状
随着科学技术的进步和并行计算机的计算速度和容量的迅速增长，以前无法实现的大型计算问题得到了很快的解决。许多科技工作者在解释自己研究的科技领域中出现的物理现象时提出了一些现代复杂数学和计算技术问题，而这些理论和方法都要解决大问题的计算，最后归结到求解大型方程组等。不少应用软件，在求解方程组方面耗费的实际时间占80％以上，因而研究高效并行算法及其计算环境在国内外引起了许多科学家的注意。
预测模型的构造和模拟、工程设计和自动化、能源勘探、医学、军事、机械制造、计算数学、石油资源数学模拟问题，常常涉及到现代的复杂数学问题和计算方法，又具有很强的实用性。这些领域的许多现象的描述都是各种数学物理方程，从数学物理方程的求解方法导出大型稀疏线性方程组。近几年又有将分形、神经网络及遗传算法应用于这些领域的计算。
由此，许多数学家、科学家在这些领域上提出了许多高效的计算方法。这些计算方法都有一个共同的特点，那就是计算空间大。目前将这些高效的计算方法真正应用于解决实际问题而且行之有效的则并不多见。究其原因，主要是这类问题要求解大型线性方程组，许多用
户又不具备并行计算机。一些优秀的算法在应用领域中借助于串行计算机计算，其优越性不能充分体现出来，直接影响了这些领域的科技应用的发展。网络并行计算时利用网络上的计算机资源实现大问题的并行计算，这使得许多优秀的算法得以体现和广泛的应用，使得这些领域中应用高效数值计算成为可能。
随着商品化微处理器、网络设备的发展，以及MPI/PVM等并行编程标准的发布，出现了机群架构的并行计算机。IBM SP2系列机群系统就是其中的典型代表。在这些系统中，各个结点都采用标准的商品化计算机，它们之间通过高速网络连接。
近几年来机群计算成为国内外研究的热门课题。国际上，机群系统并行环境在进一步完善中，不少国外大学推出了自己的机群系统，商业机群也逐渐成熟起来。在国内，中科院、国家高性能计算中心和一些大学投入了相当的力量对其应用理论和方法进行研究，如国家智能计算机研究开发中心的有关机群的在研项目，有机群系统I/O负载的收集与分析、面向机群和网格的分布式构建平台研究和机群服务器功能软件等。机群并行系统具有构造成本低、编程方便、投资风险小、性能/价格比高、系统结构灵活、可扩展性好、能充分利用分散的计算资源等特点和优势，研究机群并行计算在科学和工程领域中的应用具有十分重要的意义。
3.并行计算概述
从事网络并行计算，首先要对并行计算概念和并行计算机类型有一个初步的了解。
3.1.并行算法概述[2]
3.1.1并行算法的定义和分类
算法是解决问题的精确描述，是一组有穷的规则。它规定了某一特定类型问题的一系列运算。并行计算是可同时求解的诸进程的集合，这些进程相互作用和协调动作，并最终获得问题的求解，并行算法就是对并行计算过程的精确描述，是给定并行模型的一种具体的解决方法和步骤。
并行算法可以从不同的角度分类为：
·数值计算并行算法和非数值计算并行算法；
·同步并行算法、异步并行算法、纯并行算法；
·粗粒度并行算法、中粒度并行算法和细粒度并行算法；
根据运算的基本对象不同，并行计算分为数值并行算法和非数值数值并行算法是针对基于代数关系运算的计算问题如矩阵运算、多项式线性代数方程组求解等的并行算法；非数值并行算法是针对基于比较关算如排序、选择、查找、匹配等符号处理等的并行算法。当然，
这两种是绝对分开的，比如在数值计算的过程中会用到查找、匹配等非数值算分，而在非数值计算中也会用到数值计算的方法。划分为何种算法取决的计算量和宏观的计算方法。
根据进程之间的依赖关系，并行算法分为同步并行算法（步调一并行算法（步调、进展互不相同）和纯并行算法（各部分之间没有关同步并行算法，任务的各个部分是同步向前推进的，有一个全局的时钟定是物理的）来控制各个部分的步伐；对于异步并行算法，各个部分的
互不相同的，它们根据计算过程的不同阶段决定等待、继续或终止；纯法是理想的情况，各个部分之间可以尽可能快地向前推进，不需要任何等待，但是这样的问题一般很少见。
根据并行计算任务的大小，并行算法可以分为粗粒度并行算法（一个任务包含较长的程序段和较大的计算量）和细粒度并行算法（一个并行含较短的程序段和较小的计算量）以及介于二者之间的中粒度并行算法而言，并行的粒度越小，越有可能开发更多的并行性，提高并行度，这方面；不利方面是并行的粒度越小，通信次数和通信量就会相对增多，加了额外的开销。因此，合适的并行粒度需要根据计算量、通信量、通信速度等因素进行综合平衡，这样才能取得高效率。
3.1.2并行算法的设计方法
利用并行处理机系统求解一个给定的问题，需要根据体统类型和特相应的并行算法。通常有三种途径：
·检查和开发现有串行算法中固有的并行性直接将其并行化；
·从问题本身的特征出发，设计一个新的并行算法；
·修改已有的并行算法使其可求解另一类相似的问题。
对一类具有内在顺序性的串行算法难于并行化；修改已有的并行算法依赖于特定的一类问题；设计全新的并行算法，尽管技术上尚不成熟，但还是有章可循的。目前普遍使用的并行算法的设计技术有流水线技术、分治策略、平衡树方法、倍增技术以及加速级联策略等。
3.1.3并行算法的复杂性
对算法进行分析时，常要使用上界（Upper Bound）、下界（Lower Bound）和紧致界（Tightly Bound）等概念，分别定义如下：
·上界：令f(n)和g(n)是定义在自然数集合N上的两个函数，如果存在正整数c和n0，使得对于所有的n>=n0，均有f(n)<=g(n)，则称g(n)是f(n)的一个上界，记做f(n)=O(g(n))。·下界：令f(n)和g(n)是定义在自然数集合N上的两个函数，如果存在正整数c和n0，使得对于所有的n>=n0，均有f(n)>=g(n)，则称g(n)是f(n)的一个下界，记做f(n)=O(g(n))。
·紧致界：令f(n)和g(n)是定义在自然数集合N上的两个函数，如果存在正整数c1，c2和n0，使得对于所有的n>=n0，均有c1*g(n)<=f(n)<= c2 *g(n)，则称g(n)是f(n)的一个紧致界，记做f(n)=Θ(g(n))。
在算法分析时，如果对算法的所有输入分析其平均性态时的复杂度，则称之为期望复杂度（Expected Complexity），在某些输入时，可以使得算法的时间、空间复杂度最坏，此时的时间复杂度称为最坏情况下的复杂度（Worst-Case Complexity）。
3.1.4并行算法性能评价
并行算法的性能主要通过下列三个因素评价：
·计算时间（时间复杂度）
·所需的处理器个数（处理器复杂度）
·所需的机器模型
主要性能指标有加速比（Speedup）和效率(Efficiency)。加速比和效率考虑一个已知的串行算法，其时间复杂度为T s，我们有一个针对相同问题的并行算法，其时间复杂度为T p，处理器复杂度为P，定义
加速比=Ts Tp
效率＝
Ts Tp?P
加速比最大不超过处理器的个数，我们总是试图开发加速比几乎等于处理器数目的并行算法。实际上，只有有限问题的加速比能达到这一要求。效率最大为1，它表明所有处理器的有效利用率。
串行和并行执行时间的定义有多种方式，这导致了五种不同的加速比定义，即相对加速比（Relative Speedup）、实际加速比（Real Speedup）、绝对加速比（Absolute Speedup）、渐近实际加速比（Asymptotic Real Speedup）和渐近相对加速比（Asymptotic Relative Speedup）。
相对加速比这里串行时间定义为运行在并行计算机的单个处理器上的并行程序的执行时间，因此，并行算法A在用p个处理器解决规模为n的问题实例P时的相对加速比定义为：
Relative Speedup(n,p)=单个处理器用算法A解决问题P的时间P个处理器用算法A解决问题P的时间
并行系统的加速比并不是固定的，它依赖于问题的规模n和处理器的个数p。相对加速比是n和p的函数。固定n，可以画出以p为一个坐标轴，相对加速比为另一个坐标轴的相
对加速比曲线。这可以用于在处理器数目增加时分析算法的性能。相似地，也可以固定p，画出一条以n为一个坐标轴，相对加速比为另一坐标轴的相对加速比曲线。这可以用于在问题规模增加时分析算法的性能。利用这两条曲线，可以找到相对加速比的最大点，称为最大相对加速比。平均相对加速比、最小相对加速比和期望相对加速比可以用相似的方法定义。
实际加速比在这一度量中，并行执行时间是和针对应用的最快串行算法或程序所需的时间相比较的。在并行计算机单个处理器上最快算法的执行时间将被采用。由于对很多应用尚不知道最快的算法，对某些应用不存在最快的算法，因此，实际使用的串行算法执行时间被用来代替最快串行算法的执行时间。这样得到的加速比就是实际加速比。
Real Speedup(n,p)=用最好的串行算法解决问题的时间用P个处理器解决问题的时间
我们可以像相对加速比那样定义最大实际加速比、最小实际加速比、平均实际加速比、期望实际加速比等。
绝对加速比在此定义中，通过比较并行执行时间与最快串行算法在最快的串行计算机上的执行时间得到加速比。
A bsolute Speedup(n,p)=用最快的处理器和最好的串行算法解决问题的时间用算法A和p个处理器解决问题的时间
绝对加速比的定义可以扩展到最大绝对加速比、最小绝对加速比、平均绝对加速比等。
渐近实际加速比设S(n)为针对问题的最好串行算法的渐近复杂度，P(n)为在并行计算机可以满足所需处理器的假设基础上并行算法A的渐近复杂度。渐近实际加速比定义为：Asymptotic Real Speedup(n)=S(n)/P(n)
对于像排序之类的渐近复杂度不能用实例规模n唯一表征的问题，采用最坏情况下的复杂度。
渐近相对加速比渐近相对加速比和渐近实际加速比的不同点在于串行复杂度，这里采用在单个处理器上运行的并行算法的渐近时间复杂度。
效率效率是和加速比关系密切的性能尺度。它是加速比和处理器个数的p的比值。采用不同的加速比得到不同的效率。
3. 2并行计算机的分类[3]
1966年美国学者Flynn按照指令流和数据流的不同将计算机分为以下四类：
·单指令流单数据流（Single Instruction Stream–Single Data Stream，SISD）计算机。大多
数个人计算机属于此类，它不属于并行计算机，而属于传统的串行计算机。它有两个非常重要的特征：串行性和确定性。
·单指令流多数据流（Single Instruction Stream–Multiple Data Stream,SIMD）计算机，这是计算机体系结构历史上的一个重要分类，对于数据并行类问题，这种计算机能达到很高的处理速度。特征：同步、确定，适合于指令/操作级并行。
·多指令流单数据流（Multiple Instruction Stream–Single Data Stream,MISD）计算机，此类计算机很少有实例存在，适合于特殊用途。
·多指令流多数据流（Multiple Instruction Stream–Multiple Data Stream,MIMD）计算机，这类计算机是并行处理机的一种比较理想的结构，每个处理器在各自唯一的数据流上执行各自的指令流，与其它处理器无关。其主要特征有：指令流可以同步执行或异步执行；
指令流的执行有确定性和不确定性；适合于子程序级的并行；可以按照多指令或单程序的模式运作。多处理机和多计算机都属于此类计算机，它们都是由一些可编程的且均可各自执行自己的程序的多台处理器组成。
并行计算机系统大多是MIMD系统，包括：
·并行向量机（PVP，Parallel Vector Processor）
·对称多处理机（SMP，Symmetric Multiprocessor）
·大规模并行处理机（MPP，Massively Parallel Processor）
·机群（Cluster）
·分布式共享存储多处理机（DSM，Distributied Parallel Shared Memory）
3. 3并行计算体系结构
并行计算技术自60年代中期出现以来，其并行处理形式经历了从阵列机（SIMD）、向量机、共享存储的多处理器系统（SMP）、分布式存储的大规模并行处理系统（MPP）到计算机机群（Cluster）的演变过程。
并行体系结构是并行计算的基础，各种并行程序的设计机制也都是针对不同的并行体系结构的。其大致可以分为如下五类：
·阵列处理机（SIMD）由成千上万个功能非常简单的处理机构成，数据以某种方式流经各个处理机，由它们进行处理。SIMD类型并行计算机对并行计算机的发展起到了重要的推动作用，但由于处理器芯片技术的发展，90年代以后，用于科学和工程计算的SIMD 类型并行机已基本上退出了历史舞台。
·向量处理机（V ector Machine）向量处理机除了标量寄存器和标量功能部件以外，还专
门设有向量寄存器和向量流水功能部件，能对向量运算进行高速处理。
·共享主存储处理机系统（Shared Memory Multiprocessor System，SMP）多个处理器共享一个中央存储器，一般还有专门的多机同步通信部件，能支持数据并行或控制并行的开发。但处理机的数目太多时，各处理机到中央存储器的通道会成为瓶颈，限制了该类并行机的发展，这也是分布主存大规模并行机发展起来的主要原因之一。
·分布主存多处理机系统（Distributed Memory Massively Parallel Processor，MPP）它是由很多结点构成的并行机，每个结点有自己的处理机和存储器，结点之间以互连网络相连，主要支持数据并行开发，也支持控制并行开发。
·计算机机群系统由高性能网络或局域网物理地互连起来的全体计算机结点的集合。典型情况下，每个结点是一台SMP服务器、工作站或是一台PC机，结点可以同构，也可以异构。计算机数目一般为几个到几十个，支持控制并行和数据并行。每个结点上都有完整的操作系统、网络软件和用户界面，都可以作为控制结点和运算结点，即结点之间是平等的。机群系统最近几年的表现引人注目，由于其具有出色的性价比、灵活性和良好的并行处理能力，除了广泛地作为研究课题外，在各个行业的应用发展也很快。3. 4并行计算模型[4]
并行计算模型是一个将高层次特点与低层次特性分离开来的界面，提供在其上进行编程的特定操作，对其下所有结构中每个操作的实现作出要求。它是用来把软件设计与高效并行执行分离开来，提供抽象性和稳定性。迄今为止，已有多种并行计算模型存在，如PRAM 模型、LogP模型、C3模型、BDM模型等，但其中的每一种只抽象了实际并行机的一个或几个方面，尚无一种适用于所有并行机。
·PRAM模型是对一种共享存储并行机的特征的提取，假设了网络带宽无限，可直接开发原始算法内在粒度并行。
·LogP模型是对一类分布式并行计算机的特征提取，基于点对点通信的计算机模型，集中分析了处理机与网络之间的瓶颈。
·C3模型是对一类基于消息传递的分布式粗粒度系统的特征提取，集中反映了网络拥挤和路由影响。
·BDM模型是共享存储编程模式与消息传递的分布式存储系统之间的一个桥梁模型，反映的是存储系统中流水线预取等方面的影响。一个好的模型应具有易于编程、确保程序正确性、模型易于理解、可高效实现、提供程序开销的度量方法等特性。
3. 5并行编程模型与并行语言
目前两种最重要的并行编程模型是数据并行和消息传递（其它编程模型还有共享变量模型和函数模型等，它们应用得不是很普遍，这里不作介绍）。数据并行编程模型的级别比较高，编程相对简单，但它仅适合于数据并行问题。数据并行即将相同的操作作用于不同的数据，适合在SIMD并行计算机上运行。消息传递编程模型的编程级别相对较低，但消息传递编程模型有更广泛的应用。
消息传递即各个并行执行的部分之间通过消息传递来交换信息、协调步伐、控制执行，消息传递一般面向分布式内存，但也适用于共享内存的并行机。消息传递为编程者提供了更灵活的控制手段和表达并行的方法，一些用数据并行方法很难表达的并行算法，都可以用消息传递模型来实现。灵活性和控制手段的多样化，是消息传递并行程序能提供高的执行效率的原因。另一方面，它也将各个并行执行部分之间复杂的信息交换和协调、控制的任务交给了编程者，这在一定程度上增加了编程者的负担，这是消息传递编程模型级别低的主要原因。虽然如此，消息传递的基本通信模式简单清楚，学习和掌握并不困难。目前大量的并行程序设计仍然是消息传递并行编程模式。
并行程序是通过并行语言来表达的，并行语言的产生主要有三种：设计全新的并行语言；扩展原来的串行语言的语法成分，使之支持并行特征；不改变串行语言，仅为串行语言提供可调用的并行库。由于并行计算至今还没有一个统一的标准，不像串行计算那样有统一的模型（冯·诺依曼模型）可遵循，所以并行机、并行模型、并行算法和并行语言的设计和开发方法千差万别，至今仍无任何一种并行语言成为人们普遍接受的标准。设计新的并行语言难度和工作量都很大，目前最常用的是上述三种方式中的第二、三种，尤其是第三种。
目前通用的消息传递并行编程模型主要有：Express，Linda，RARMSCS，P4，Zipcode，PVM，MPI等几种。用得最为广泛的是MPI和PVM，下面对MPI和PVM作简要介绍。3. 5.1消息传递标准平台MPI[5]
MPI是消息传递界面（Message Passing Interface）的简称。为了统一互不兼容的用户界面，1992年成立了MPI委员会，负责制定消息传递界面的新标准，支持最佳的可移植平台。
MPI的目标是要开发一个广泛用于编写消息传递程序的标准。要求用户界面实用、可移植强，并且高效、灵活，能广泛用于各类并行计算机，特别是分布式存储的并行计算机。近10年来，每个计算机厂商都在开发标准平台上做了大量的工作，出现的一批可移植的消息传递环境。MPI正是吸取了它们各自的有益经验，同时从句法和语法两个方面确定核心库函数，使之能适用于更多的并行计算机。
MPI在标准化的过程中吸收了许多代表参加，包括研制并行计算机的大多数厂商，以及来自大学、实验室与工业界的研究人员。正式的标准化过程是从1992年4月开始的，当年11月发表了草稿（1993年2月修改）。1994年发布了MPI的定义与试验版本MPI 1，相应的标准MPI 2平台将极有可能形成一个类似于Fortran 77那样的国际消息传递标准平台，这是一个值得重视的技术动向。
确立消息传递标准的好处主要在于可移植和便于使用。在分布式存储通信环境中，高一级的子程序建立在低一级消息传递子程序的基础之上，这时的标准化好处更为明显。其次，消息传递标准一经建立，就可以提供给厂商，它们就能在各自的机器上有效的加以实现，或者提供相应的硬件支持，从而提高并行计算机的可扩展性。
MPI 1的重点放在点到点的通信上，MPI 2进一步增强了以下几个方面的功能[6]：
·输入、输出
·主动消息（Active messages）
·进程启动（process startup）
·动态进程控制（dynamic process control）
·远程存储与远程访问
·Fortran 90与C++
·图形
·实时支持
3. 5.2异构编程环境PVM[7]
PVM（Parallel Virtural Machine）是美国国家基金会资助的公开软件系统，具有通用性强和系统规模小的特点，既适合TCP/IP网络环境，又适用于MPP大型并行系统，当前所有的并行机公司都已宣布支持PVM3。一些大公司还针对产品的特点推出高效率的PVM产品。如IBM在SP2上提供了PVMe及相应的调试工具pdbx。PVM是美国Oak Ridge国家实验室研制的，1995年初推出3.3.7版。与PVM3配套的异构计算机网络环境（HeNCE）及可视化工具XPVM已在世界范围内推广。一批标准的软件正在移植到PVM平台。
PVM具有以下主要特点：
·系统规模小（约几兆字节）
·通用性强，既适于TCP/IP网络，又适用于MPP大规模并行系统
·所有现有并行机厂商都宣布支持PVM3
·成熟程度高
·应用范围广
MPI与PVM相比，有以下特点：
·MPI的实现方式多样化，同一编程界面有多种开发工具
·MPI能实现完全的异步通信
·MPI能有效地管理消息缓存区
·MPI能在MPP与工作站机群上有效运行
·MPI异步执行时能保护用户的其它软件不受影响
·MPI完全是可移植的标准平台
4. 总结
网络并行环境是近年来国际上并行环境的一个重要方向。网络并行，就是通过高速信息网络，充分利用网上的计算机资源，实现大型问题的并行计算。网络并行具有投资少、见效快、灵活性强等优点。国内外的经验表明，除了少数固定的计算机大户以外，许多用户并不经常需要超级计算，也就不必每个单位都购置昂贵的高性能并行机，一旦需要，可通过网络实现。
并行计算就是利用互联网上的计算机资源实现大问题的计算。并行计算机是指有两个或两个以上的处理器连接起来可以并发操作的机器。这样的机器有时也称为多处理机。并行计算机主要可分为两大类：SIMD和MIMD。多处理器一般可分为两类：共享存储和分布式存储。网络并行计算所使用的消息传递环境主要有Express，Linda，RARMACS，P4，Zipcode，PVM与MPI等几种。
参考文献：
[1] Ananth Grama. 并行计算导论[M]. 北京: 工业出版社,2005:201-210.
[2] 陈国良.并行计算[M]. 北京: 高等教育出版社, 2003:155-165.
[3] 陈国良,孙广中,徐云等.并行计算的一体化研究现状与发展趋势[J].科学通
报,2009,54(8):1043-1049.
[4] Shameem Akhter, Jason Roberts. 程序设计技术——通过软件多线程提升性能［M］．电
子工业出版社,2007:267-289.
[5] 王萃寒,赵晨. 布式并行计算环境:MPI[J] .计算机科学,2003,1:23-32
[6] 张武生,薛巍,李建江等.PI并行程序设计实例教程[M].清华大学出版社.2005:356-379.
[7] 纪珊珊. 基于PVM的并行计算在PC机群上的实现[D].大连理工大学,2000.
LSF高性能分布运算解决方案
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数据可视化 可视化工具有两大类。
并行计算1
并行计算 实 验 报 告 学院名称计算机科学与技术学院专业计算机科学与技术 学生姓名 学号 年班级 2016年5 月20 日
一、实验内容 本次试验的主要内容为采用多线程的方法计算pi的值，熟悉linux下pthread 形式的多线程编程，对实验结果进行统计并分析以及加速比曲线分析，从而对并行计算有初步了解。 二、实验原理 本次实验利用中值积分定理计算pi的值 图1 中值定理计算pi 其中公式可以变换如下： 图2 积分计算pi公式的变形 当N足够大时，可以足够逼近pi，多线程的计算方法主要通过将for循环的计算过程分到几个线程中去，每次计算都要更新sum的值，为避免一个线程更新sum 值后，另一个线程仍读到旧的值，所以每个线程计算自己的部分，最后相加。三、程序流程图 程序主体部分流程图如下：
多线程执行函数流程图如下： 四、实验结果及分析
令线程数分别为1、2、5、10、20、30、40、50和100，并且对于每次实验重复十次求平均值。结果如下： 图5 时间随线程的变化 实验加速比曲线的计算公式类似于 结果如下： 图5 加速比曲线 实验结果与预期类似，当线程总数较少时，线程数的增多会对程序计算速度带来明显的提升，当线程总数增大到足够大时，由于物理节点的核心数是有限的，因此会给cpu带来较多的调度，线程的切换和最后结果的汇总带来的时间开销较大，所以线程数较大时，增加线程数不会带来明显的速度提升，甚至可能下降。 五、实验总结
本次试验的主要内容是多线程计算pi的实现，通过这次实验，我对并行计算有了进一步的理解。上学期的操作系统课程中，已经做过相似的题目，因此程序主体部分相似。不同的地方在于，首先本程序按照老师要求应在命令行提供参数，而非将数值写定在程序里，其次是程序不是在自己的电脑上运行，而是通过ssh和批处理脚本等登录到远程服务器提交任务执行。 在运行方面，因为对批处理任务不够熟悉，出现了提交任务无结果的情况，原因在于windows系统要采用换行的方式来表明结束。在实验过程中也遇到了其他问题，大多还是来自于经验的缺乏。 在分析实验结果方面，因为自己是第一次分析多线程程序的加速比，因此比较生疏，参考网上资料和ppt后分析得出结果。 从自己遇到的问题来看，自己对批处理的理解和认识还比较有限，经过本次实验，我对并行计算的理解有了进一步的提高，也意识到了自己存在的一些问题。 六、程序代码及部署 程序源代码见cpp文件 部署说明： 使用gcc编译即可，编译时加上-pthread参数，运行时任务提交到服务器上。 编译命令如下： gcc -pthread PI_3013216011.cpp -o pi pbs脚本(runPI.pbs)如下： #!/bin/bash #PBS -N pi #PBS -l nodes=1:ppn=8 #PBS -q AM016_queue #PBS -j oe cd $PBS_O_WORKDIR for ((i=1;i<=10;i++)) do ./pi num_threads N >> runPI.log
最短路径的并行算法综述
最短路径的并行算法综述 SA02011105 陈艾 (aiai@https://www.wendangku.net/doc/0512290530.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 陈艾
并行计算实验报告一
江苏科技大学 计算机科学与工程学院 实验报告 实验名称：Java多线程编程 学号：姓名：班级： 完成日期：2014年04月22日
1.1 实验目的 (1) 掌握多线程编程的特点； (2) 了解线程的调度和执行过程； (3)掌握资源共享访问的实现方法。 1.2 知识要点 1.2.1线程的概念 (1)线程是程序中的一个执行流,多线程则指多个执行流; (2)线程是比进程更小的执行单位,一个进程包括多个线程; (3)Java语言中线程包括3部分:虚拟CPU、该CPU执行的代码及代码所操作的数据。 (4)Java代码可以为不同线程共享，数据也可以为不同线程共享； 1.2.2 线程的创建 (1) 方式1：实现Runnable接口 Thread类使用一个实现Runnable接口的实例对象作为其构造方法的参数，该对象提供了run方法，启动Thread将执行该run方法； (2)方式2：继承Thread类 重写Thread类的run方法； 1.2.3 线程的调度 (1) 线程的优先级 ●取值范围1～10，在Thread类提供了3个常量，MIN_PRIORITY=1、MAX_ PRIORITY=10、NORM_PRIORITY=5； ●用setPriority()设置线程优先级，用getPriority()获取线程优先级； ●子线程继承父线程的优先级，主线程具有正常优先级。 (2) 线程的调度：采用抢占式调度策略，高优先级的线程优先执行，在Java中，系统按照优先级的级别设置不同的等待队列。 1.2.4 线程的状态与生命周期
说明：新创建的线程处于“新建状态”，必须通过执行start()方法，让其进入到“就绪状态”，处于就绪状态的线程才有机会得到调度执行。线程在运行时也可能因资源等待或主动睡眠而放弃运行,进入“阻塞状态”,线程执行完毕，或主动执行stop方法将进入“终止状态”。 1.2.5 线程的同步--解决资源访问冲突问题 (1) 对象的加锁 所有被共享访问的数据及访问代码必须作为临界区，用synchronized加锁。对象的同步代码的执行过程如图14-2所示。 synchronized关键字的使用方法有两种： ●用在对象前面限制一段代码的执行，表示执行该段代码必须取得对象锁。 ●在方法前面，表示该方法为同步方法,执行该方法必须取得对象锁。 (2) wait()和notify()方法 用于解决多线程中对资源的访问控制问题。 ●wait()方法：释放对象锁，将线程进入等待唤醒队列； ●notify()方法：唤醒等待资源锁的线程，让其进入对象锁的获取等待队列。 (3)避免死锁 指多个线程相互等待对方释放持有的锁，并且在得到对方锁之前不会释放自己的锁。 1.3 上机测试下列程序 样例1：利用多线程编程编写一个龟兔赛跑程序。 乌龟：速度慢，休息时间短；
LBGK模型的分布式并行计算
万方数据
２ＬＢＧＫＤ２Ｑ９模型的并行计算 ２．１数据分布 将流场划分成Ｎ。ｘＮ，的网格。设有Ｐ＝只×Ｐｖ个进程参与并行计算，进程号Ｐ。＝Ｈ以（０≤ｉ＜只，０≤Ｊ＜尸ｖ）。将数据按照重叠一条边的分块分布到各进程中。其中，进程Ｐ。存储并处理的数据网格点集，如图ｌ所示。 图１进程珊存储并处理的区域（斜线处为重叠部分） ２．２交替方向的Ｊａｃｏｂｉ迭代通信 Ｊａｃｏｂｉ迭代是一类典型的通信迭代操作。文献［４】主要讨论了一个方向的Ｊａｃｏｂｉ迭代。根据数据分布及计算要求，需要采用２个方向交替的Ｊａｃｏｂｉ迭代通信操作。本文认为，“即发即收”的通信策略能有效避免完全的“先发后收”可能造成的通信数据“堆积”过多，从而避免数据的丢失。进程Ｐｌｉ的通信操作如下（见图２）： （１）Ｉｆｉ≠只一１ｔｈｅｎ发送数据到进程Ｐ¨，； （２）Ｉｆｉ≠０ｔｈｅｎ从进程Ｐｆ＿Ｊ，接收数据； （３）Ｉｆ，≠只－１ｔｈｅｎ发送数据到进程Ｐｍｌ； （４）ＩｆＪ≠０ｔｈｅｎ从进程Ｐ—ｌ接收数据。 各进程并行执行上述操作。 图２交普方向的Ｊａｃｏｂｉ迭代 ２．３通信时间理论 由一般的通信模型可知，若发送、接收信息长度为ｎ字节的数据所需时间为：丁（ｎ）＝口＋ｎ∥，其中，常数口为通信启动时间；∥为常系数，则上述一次交替方向的Ｊａｃｏｂｉ迭代通信操作的时间约为 ２０ｅ＋２ｆｌ＇Ｎ、．Ｐ，＝１ Ｐ。＝１ 其他 其中，∥７＝∥ｓｉｚｅｏｆ（ｄｏｕｂｌｅ）。 一般情况下，当等３鲁，即等＝鲁时，通信的数据量（字节数）是最少的，为４口＋４∥，．／丝堡。可见，通信的信息 Ｖ只×０ 总量和通信时间随进程总数只×尸ｖ的增加而减少。 由于ｃ语言中数组是按“行”存放的（Ｆｏｒｔｒａｎ是按“列”存放的），当存放、发送列数据时，需要一定的辅助操作，这就增加了并行计算的计算时间，因此在只：Ｐｖ无法恰好等于Ｎｘ：Ｎ。时，需要综合考虑流场形状及大小、数据在内存中的按“行”（或按“列”）的存放方式，以确定数据的最佳分布方案。 ３数值实验 数值实验是在“自强３０００”计算机上进行的ｏｕ自强３０００”计算机拥有１７４个计算结点，每个计算结点上有２个３．０６ＣＰＵ，２ＧＢ内存。本文的实验使用了其中的３２个计算结点共６４个ＣＰＵ。程序采用ＭＰＩ及Ｃ语言编写，程序执行时，每个计算结点中启动２个进程。数值实验针对不同规模的网格划分、不同进程数以及不同的数据分布方案进行了大量实验，测得如下结果：不同的流场规模对应着各自的最佳网格划分方式；计算次数越多，加速比越大，越能体现并行计算的优越性。 由表１数据可以得知，对于规模为Ｎｘ×Ｎ、，＝４００ｘ４００，数据划分成６×６块时的加速比最高，而对于ＭＸＮｙ＝６００ｘ２００，数据划分为１２×３块则更具优越性。合适的划分方式可以使总体通信量减至最少，从而提高加速比和并行效率。另外，计算规模越大，加速比越大。 表１并行计算Ｄ２Ｑ９模型的加速比（进程数为３６） 在固定计算规模，增加处理器的情况下，并行系统的加速比会上升，并行效率会下降；在固定处理器数目，增加计算规模的情况下，并行系统的加速比和效率都会随之增加。 从表２可见，流场规模越大，并行计算的优越性越显著。因为此时计算规模（粒度）较大，相对于通信量占有一定的优势。由图３可见，加速比随进程数呈线性增长，这表明ＬＢＧＫＤ２Ｑ９模型的并行计算具有良好的可扩展性。 表２漉场规模固定时并行计算Ｄ２Ｑ９模型的加速比 ０８１６２４３２４０４８５６６４ ｎｕｍｏｆｐｒｏｃｅｓｓ 图３藐场规模固定时Ｄ２Ｑ９模型并行计算的加速比 ４结束语 本文讨论了ＬＢＧＫＤ２Ｑ９模型的分布式并行计算，通过大量的数值实验重点研究了数据分布方案如何与问题规模匹配，以获得更高的并行效率的问题。展示了ＬＢＧＫ模型方法良好的并行性和可扩展性。得到了二维ＬＢＧＫ模型并行计算数据分布的一般原则、交替方向Ｊａｃｏｂｉ迭代的通信策略。这些结论对进一步开展三维ＬＢＧＫ模型的并行计算及其他类似问题的并行计算有一定的指导意义。（下转第１０４页） 一１０１—万方数据
蒙特卡罗方法并行计算
Monte Carlo Methods in Parallel Computing Chuanyi Ding ding@https://www.wendangku.net/doc/0512290530.html, Eric Haskin haskin@https://www.wendangku.net/doc/0512290530.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并行计算的图像二值化研究 引言: 图像是当今社会运用的越来越多的元素之一，不过是动画还是静态的图片都是图像的动静呈现，所以对图像的处理也就越来越得到人们的关注。图像重要性，图像处理就是在图像中得到可靠的信息。而图像的二值化处理也是当今正盛行的一种图像的处理方法，它把图像原始化，使得数据更加简单的表现。 本毕业设计是GPU与二值化的并行运算，这无疑就是一种加速算法，也就是讲在二值化处理本来就跟快的基础上，能够更快的读取图像中的信息，得到我们想要的数据。而现在最常用的一种加速算法就是CUDA算法，他的并行运算可以使得二值化运算提高几十倍，在图像处理中是一个很庞大的数据。CUDA的并行运算在处理小图像时并不能很明显的突出速度，但是当遇到有大量的图像需要处理，而且图像又很大的情况下，这种并行运算可以节省很多时间。 1图像处理简介 1.1图像处理的概念 图像处理一般指数字图像处理。数字图像是指用数字摄像机、扫描仪等设备经过采样和数字化得到的一个大的二维数组，该数组的元素称为像素，其值为一整数，称为灰度值。图像处理技术的主要内容包括图像压缩，增强和复原，匹配、描述和识别3个部分。 常见的处理有图像数字化、图像编码、图像增强、图像复原、图像分割和图像分析等。图像处理一般指数字图像处理。虽然某些处理也可以用光学方法或模拟技术实现，但它们远不及数字图像处理那样灵活和方便，因而数字图像处理成为图像处理的主要方面。 1.2 图像二值化技术的简介 首先，图像的二值化有利于图像的进一步处理，使图像变得简单，而且数据量减小，能凸显出感兴趣的目标的轮廓。其次，要进行二值图像的处理与分析，首先要把灰度图像二值化，得到二值化图像。所有灰度大于或等于阀值的像素被判定为属于特定物体，其灰度值为255表示，否则这些像素点被排除在物体区域以外，灰度值为0，
多核编程与并行计算实验报告 (1)
(此文档为word格式，下载后您可任意编辑修改！) 多核编程与并行计算实验报告 姓名： 日期：2014年 4月20日
实验一 // exa1.cpp : Defines the entry point for the console application. // #include"stdafx.h" #include 实验二 // exa2.cpp : Defines the entry point for the console application. // #include"stdafx.h" #include 并行计算课程报告 1．学习总结 1.1并行计算简介 并行计算是相对于串行计算来说的。它是一种一次可执行多个指令的算法，目的是提高计算速度，及通过扩大问题求解规模，解决大型而复杂的计算问题。所谓并行计算可分为时间上的并行和空间上的并行。时间上的并行就是指流水线技术，而空间上的并行则是指用多个处理器并发的执行计算。 1.2并行计算机分类和并行机体系结构的特征 按内存访问模型、微处理器和互联网络的不同，当前流行的并行机可分为对称多处理共享存储并行机（SMP：Symmetric Multi-Processing）、分布共享存储并行机（DSM：Distributed Shared Memory）、机群（cluster）、星群（constellation）和大规模并行机（MPP：Massively Parallel Processing）等五类。 SMP并行机有如下主要特征：对称共享存储、单一的操作系统映像、局部高速缓存cache 及其数据一致性、低通信延迟、共享总线带宽、支持消息传递、共享存储并行程序设计。SMP 并行机具有如下缺点：欠可靠、可扩展性（scalability）较差。 DSM 并行机具有如下主要特征：并行机以结点为单位，每个结点包含一个或多个CPU，每个CPU 拥有自己的局部cache，并共享局部存储器和I/O设备，所有结点通过高性能互联网络相互连接；物理上分布存储；单一的内存地址空间；非一致内存访问（NUMA）模式；单一的操作系统映像；基于cache 的数据一致性；低通信延迟与高通信带宽；DSM 并行机可扩展到数百个结点，能提供每秒数千亿次的浮点运算性能；支持消息传递、共享存储并行程序设计。 机群(cluster)有三个明显的特征： ①系统由商用结点构成，每个结点包含2-4 个商用微处理器，结点内部 共享存储。 ②采用商用机群交换机连接结点，结点间分布存储。 ③在各个结点上，采用机群Linux 操作系统、GNU 编译系统和作业管理 系统。 星群(constellation)有三个明显的特征： ①系统由结点构成，每个结点是一台共享存储或者分布共享存储的并行 机子系统，包含数十、数百、乃至上千个微处理器，计算功能强大。 ②采用商用机群交换机连接结点，结点间分布存储。 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++并行模型就在一定程度上减少了开发难度，提高了开发效率，使得并行软件开发人员把更多精力专注于如何提高算法本身效率，而非把时间和精力放在如何去并行一个算法。 并行编程报告 课程名称：并行编程原理 专业班级：物联网1102 班 学号 : U201114483 学生姓名：陈炳良 指导教师：金海 报告日期：2014-6-11 计算机科学与技术学院 目录 实验一：利用pthread 并行实现矩阵的乘法运算 (3) 实验目的 (3) 实验概述 (3) 实验结果 (3) 实验代码 (5) 实验总结 (9) 实验二：使用并行方法优化K-means 算法 (10) 实验目的 (10) 实验概述 (10) 实验结果 (10) 实验代码............................................................................................. .11 实验总结............................................................................................. .18 实验一：利用 pthread 并行实现矩阵的乘法运算 实验目的 该实验旨在让学生掌握利用 pthread 进行并行程序设计和性能优化的基本原理和方法，了解并行程序设计中数据划分和任务划分的基本方法，并能够利用pthread 实现矩阵的乘法运算的并行算法，然后对程序执行结果进行简单分析和总结。具体包括：利用 for 循环编写串行的矩阵乘法运算；熟悉 pthread 进行线程创建、管理和销毁的基本原理和方法；利用 pthread 对上述串行的矩阵乘法运算加以改造；通过调整数据划分和任务划分的粒度(改变工作线程的数目)，测试并行程序的执行效率；对实验结果进行总结和分析。 实验概述 使用 pThread 完成这项工作。 创建一个新的线程： int pthread_create( pthread_t *thread, const pthread_attr_t *attr, void *(*func) (void *), void *arg); thread 表示线程 ID，与线程中的 pid 概念类似 attr 表示设定线程的属性，可以暂时不用考虑 func 表示新创建的线程会从这个函数指针处开始运行 arg 表示这个函数的参数指针 返回值为 0 代表成功，其他值为错误编号。 主进程等待线程结束： int pthread_join( pthread_t thread, void **retval ); thread 表示线程 ID，与线程中的 pid 概念类似 retval 用于存储等待线程的返回值 两个矩阵相乘： 一个 m 行 n 列的矩阵与一个 n 行 p 列的矩阵可以相乘，得到的结果是一个 m 行 p 列的矩阵，其中的第 i 行第 j 列位置上的数为第一个矩阵第 i 行上的 n 个 数与第二个矩阵第 j 列上的 n 个数对应相乘后所得的 n 个乘积之和。 实验结果 第三章互连网络 对于一颗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）通路中形成环，发生死锁 并行计算上机实验报告题目：多线程计算Pi值 学生姓名 学院名称计算机学院 专业计算机科学与技术时间 一. 实验目的 1、掌握集群任务提交方式； 2、掌握多线程编程。 二.实验内容 1、通过下图中的近似公式，使用多线程编程实现pi的计算； 2、通过控制变量N的数值以及线程的数量，观察程序的执行效率。 三.实现方法 1. 下载配置SSH客户端 2. 用多线程编写pi代码 3. 通过文件传输界面，将文件上传到集群上 4.将命令行目录切换至data，对.c文件进行编译 5.编写PBS脚本，提交作业 6.实验代码如下： #include #include 并行计算课程报告
分布并行计算技术
分布式与并行计算报告
并行编程报告
并行计算(陈国良版)课后答案
并行计算第一次实验报告