计算机体系结构

.有关并行算法专 业 指导教师 班 级 学 号 姓 名 日 期 精品. 广西工学院计算机学院有关并行算法一、并行计算技术概述 60年代初期，由于晶体管技术与存储器技术的发展导致并行计算机的出现，这一时期的典型代表就是IBM 360。创建和使用并行计算机的主要原因是因为并行计算机是解决筚处理器速度瓶颈的最好方法之一。并行计算机是由一组处理单元组成的，这组处理单元通过相互之间的通信与协作以更快的速度共同完成一项大规模的计算任务。因此，并行计算机的两个最主要的组成部分是计算节点和节点间的通信与协作机制。并行计算机体系结构的发展也主要体现在计算节点性能的提高以及节点间通信技术的改进两方面。 就单台计算机系统而言采用SMP技术是扩展其佳能的比较有效的方法它可以将系统中的多个操作系统分布在多个处理器上执行以获得并行处理的效果。SMP技术可以通过多线程并行来提高性能。通过采用并行多线程技术，服务器可以通过SMP技术同时处理多个应用请求使得这些程序获得了更好的运行效果，而且在龠式机的专业应用软件中，并行多线程技术的采用也日益增多。 伴随SMP技术的出现带来另外的问题，那就是当应用增加时虽然可以通过增加处理器的方法来扩展系统能力，但是，一方面需要有扩展连接处理器的系统总线的高超技术，并不是每个系统厂商都能做到，另一方面由于对共享资源的竞争所造成的系统瓶颈使得单机系统的性能呈非线性增长。因此，当应用增加超过单机系统的承受能力时，就采用集群系统(CLUS-rIER)。在集群系统中，每台服务器处理各自的工作，提供各自的服务。当需要更高的的性能以适应更多的应用肘，既可以升级原有的服务器（增加更多的处理器、内存和存储等），又可以在集群系统中增加新的服务器。更进一步，集群系统在平衡和扩展整个计算机应用系统的工作负载的同时，也为用户提供了高性能和高可用性。 1977年,DEC公司推出了以VAX为结点机的松散耦合的集群系统并成功地糌VMS操作系统移植到该系统上。20世纪90年代后随着RISC技术的发展运用和高性能网络产品的出现，集群系统在性能价格比(Ct/Perfonuance)、【il扩展性&ala-bility)、可用性(Availability)等方面都显示出了很强的竞争力，尤其是它在对现有单机上的软硬件产品的继承和对商用软硬件最新研究成果的快速运用，从两方面表现出传统MPP无法比拟的优势。 这里所介绍的高性能计算环境，从程序开发角度主要分为以下两类：一大类是共享内存系统，包括并行向量机(PVP，Par-allel Vector Pnx:eswr)、分布式共享存储多处理机(DSM.Dis-tributied Shared Memory)和对称多处理饥(SMP,Symmer/calMuhiPmcessing)等结构，其特点是多个处理器拥有物理上共享的内存，如HP的SuperDome我国曙光1号，SGI Power Chal-lenge等；另一大类是分布存储系统(DMP)，如大规模并行处理机(MPPMassively Parallel Processor)和集群系统(Cluster)，其特点是系统由多个物理上分布的结蠃组成，每个结点拥有自己的内存二、什么是并行算法并行算法（parallel computing）是指，在并行机上，将一个应用分解成多个子任务，分配给不同的处理器，各处理器之间相互协调，并行地执行子任务，从而达到加速求解速度，或者求解大规模应用问题的目的。开展并行计算，必须具备三个节本条件：1. 并行机。并行机至少包含两台或两台以上处理机，这些处理机通过通过互联网相互连接，相互通信。精品.2. 应用问题必须具有并行度。也就是说，应用可以分解为多个子任务，这些子任务可以并行地执行，将一个应用分解为多个子任务的过程，称为并行算法的设计。3. 并行编程。在并行机提供的并行编程环境上，具体实现并行算法，编制并行程序，并运行该程序，从而达到并行求解应用问题的目的三、并行算法的基本原理并行计算是同时使用多种计算资源解决计算问题的过程。并行计算的主要目的是快速解决大型且复杂的计算问题。此外还包括：利用非本地资源，节约成本 使用多个“廉价”计算资源取代大型计算机，同时克服单个计算机上存在的存储器限制。传统地，串行计算是指在单个计算机（具有单个中央处理单元）上执行软件写操作。CPU 逐个使用一系列指令解决问题，但其中只有一种指令可提供随时并及时的使用。并行计算是在串行计算的基础上演变而来，它努力仿真自然世界中的事务状态：一个序列中众多同时发生的、复杂且相关的事件。 为利用并行计算，通常计算问题表现为以下特征： （1）将工作分离成离散部分，有助于同时解决； （2）随时并及时地执行多个程序指令； （3）多计算资源下解决问题的耗时要少于单个计算资源下的耗时。并行计算是相对于串行计算来说的，所谓并行计算分为时间上的并行和空间上的并行。 时间上的并行就是指流水线技术，而空间上的并行则是指用多个处理器并发的执行计算。 并行计算的主要研究内容大致可分为四个方面：(1)并行计算机的并行性抽取，充分理解和抽取当前并行计算机体系结构的高性能特征，提出实用的并行计算模型和并行计算评价方法。(2)并行计算设计与分析，设计高效率的并行算法，将应用问题分解为可并行计算的多个子任务。(3)并行实现技术，主要包含并行程序设计和并行性能优化(4)并行应用，这是并行计算研究的最终目的。四、并行计算机的分类SIMD机器是指单指令流多数据流并行机，也即指系统中各功能部件或处理机对多组数据执行相同的指令流或操作。SIMD机器在任何时刻只有一条指令在执行。所以该类计算机的主要特征是：同步的、确定的。它适合于指令操作级并行。 MIMD并行机是指多指令流多数据流并行机，也即指系统中的各处理机在各自唯一的数据流上执行各自的指令流，与其它处理机无关。MIMD的一个特例是单程序、多数据计算，即所有处理机执行同一程序，而由进程指标加以参数化，从而完成对不同数据的操作。分布存储MIMD并行多处理机，该系统中每台处理机都有自己的局部存储器，构成一个单独的节点，节点之间通过互连网络相互连接。每台处理机只能直接访问局存，不能访问其它处理机的存储器，它们之间的协调以消息传递的方式进行。 分布共享存储MIMD并行机，分布共享存储结构也称为非一致内存访问结构，是指系统中的每台处理机都有自己的局部存储器，但这些局存组合起来形成了一个统一的共享地址空间。五、并行计算机的体系结构并行计算机体系结构是指并行处理系统(主要是分布式系统)中处理机或节点机之间的互连方式，它直接影响并行算法的实现效率。精品. 并行计算机体系机构分类: （1）总线结构； （2）网格结构； （3）超立方体结构。总线结构中个处理机共享同一条物理线路，同一时刻只允许也有一个处理机发送消息，当有多个处理机同时发送消息时，将使用仲裁机制决定消息发送顺序，从而导致通信开销的增大。网络结构，也就是二维阵列，可以分为环绕连接和无环绕连接两种方式，n*n网格结构的网络直径为2（n-1）。超立方体结构，n=2q个节点可构成一个q维超立方体。若用q位二进制数对节点进行编号，则超立方体结构中有两个节点相连的充分必要条件是节点的编号有且仅有一个不同。六、并行算法的分类根据基本运算对象的不同可分为以下两种： 数值并行算法，主要是指为数值计算设计的并行算法，如矩阵运算、多项式求解、解线性方程组等。 非数值并行算法，是指为基于关系运算的一类诸如排序、选择、分类、搜索及图论等方面的非数值计算问题设计的并行算法。根据并行进程间执行顺序关系的不同可分为以下几种： 同步并行算法，是指某些进程必须等待别的进程的一类并行算法， 异步并行算法， 是指诸进程的执行一般不必相互等待的一类并行算法，进程间的通信一般是通过动态地读、取(修改)共享存储器的全局变量。如通常运行在MIMD 机模型上的并行算法。 独立并行算法，进程间执行是完成独立的，计算的整个过程不需要任何通信，例如气象预报应用中通常需要同时计算多个模型，以保证预报的实时性。七、并行算法的性能问题1、硬件性能指标a) 重要的性能指标是CPU和输入/输出的速度以及互连网络的性能。b) 互连网络的性能有两个重要的指标：延时（Latency）和带宽（Bandwidth）。i. 延迟时间是指从CPU发送分组至接收到响应的时间间隔。ii. 对分带宽、聚集带宽和平均带宽（按照CPU能力算 ）。2、软件性能指标最关键的性能指标是加速比（speedup）：一个程序在有n个处理器的计算机运行和在只有一个处理器的计算机上运行相比快多少倍。理想的加速比不可能达到的部分原因是几乎所有的程序都有串行部分。假定一个程序在单处理器计算机上运行需要T秒，其中一部分是串行代码，所占比例记为f，那么剩余的（1f）就是可以并行的。后一部分代码运行在n个CPU上而且没有任何其它开销，那么在最理想的情况下，执行时间可以从（1f）T减少到（1f）T/n。串行部分加并行部分的整个执行时间就是fT（1f）T/n 。加速比就是原来程序的执行时间除以新的程序的执行时间：八、并行程序的开发模式精品.1共享内存模式 共享内存并行模式编程相对较为简单，程序员不用考虑数据在内存中的位置，进程管理及同步操作由系统完成。但是用这种方式编制的程序通常并行效率不高，因为它属于细粒度并行，主要针对循环进行并行处理。另外共享内存并行模式只能运行在共享内存类型的计算机系统上。 在共享内存模型中，一个并行程序由多个共享内存的并行任务组成，数据的交换通过隐含地使用共享数据来完成。此编程模式一般仅衙指定可以并行执行的循环，而不需考虑计算与数据如何划分以及如何进行任务间通信，编译器会自动完成上述功能。 目前业界流行的共享内存模型开发标准是OpenMP。OpenMP定义了一套编译指导语句，用于指定程序的并行性、数据的共享，私有等信。其目标是为SMP系统提供可移植、可扩展的开发接口。Intel，DEC，Silicon GraphicsKuch&Associates和1BM早在15午前就联合定义了OpenMP早期标准新的OpenMP标准由OpenMP Architecture Review Board于1997年推出，现在已发展到2.0版。2.消息传递模式 在消息传递模式中，一个并行程序由多个并行任务组成。每个并行任务拥有自己的数据并对其进行计算操作。任务之间数据的交换是通过显式的消息传递语句来完成的。 消息传递的并行方式虽然是在分布式内存的计算机结构基础上发展而来的但是几乎所有类型的计算机都支持这种并行模式，因此更具通用性。消息传递方式的并行属于粗粒度并行，程序员负责进程管理、消息传递及同步并行的工作量要大于共享内存并行模式。但同时程序员可以控制的也更多，可以通过仔细考虑任务分配，并行算法等方式对程序进行优化，因而获得较高的并行效率。国际上采用消息传递方式的应用软件远远多于采用共享内存并行模式的应用软件。国内的高性能计算用户也大多采用消息传递的并行方式开发自己的应用程序。现在广泛使用的消息传递模型有两个：PVM和MPI。PVM即Parallel Vutual Machine并行虚拟机）与MPI即Message Pas8-ing Intedace(消息传递界面)。PVM与MPI所提供的功能大致相同但两者的侧重点有所不同。PVM强调在异构环境下的可移植性和互操作性。程序之间可以互相通信，并支持动态的资源管理和一定程度的容错：而MP!更强调性能，不同的MPI实现之间缺乏互操作性，本身也不支持容错（可以通过专门的容错软件来支持容错）。一般而言，使用MPI比较适合于开发MPP或同构集群上的并行应用，可以有较高的通信性能：而PVM更适合于异构的集群系统。九、目前流行的并行程序设计的方法及其优缺点1. MPIMPI(Message Passing Interface)消息传递接口是MPI论坛发布的一个库，而不是一门实现语言，支持C/C+/Fortran。是一种消息传递编程模型，为进程间通信服务。MPI提供了一种与平台无关，可以被广泛使用的编写消息传递程序的标准。用它来编写消息传递程序，不仅实用、可移植、高效和灵活，而且和当前已有的实现没有太大的变化。优点：可以在集群上使用，也可以在单核/多核CPU上使用，它能协调多台主机间的并行计算，因此并行规模上的可伸缩性很强，能在从个人电脑到世界TOP10的超级计算机上使用。缺点：第一，基于消息传递，需要显示划分和分布计算任务，显示进行消息传递与同步，且不易增量开发串行程序的并行性；第二，使用进程间通信的方式协调并行计算，这导致并行效率较低、内存开销大、不直观、编程麻烦。精品.2. OpenMPOpenMP(Open Multi Processing)是由Open ARB发布的一种用于并行编程的规范，是建立在串行语言上的扩展，目前可以在C/C+/Fortran中使用。OpenMP由三部分组成：编译指导(compiler directive)、运行库(runtime library)和环境变量(environment variables)。其语言模型基于以下假设：执行单元是共享一个地址空间的线程，即OpenMP是基于派生/连接(fork/join)的编程模型。Fork/join并行机制：并行区前，串行命令派生出多条并行命令并行执行，执行到并行区末等待，等所有并行任务都结束，再转到串行执行。OpenMP有两种常用的并行开发形式：一是通过简单的fork/join对串行程序并行化；二是采用单程序多数据对串行程序并行化。优点：第一，共享存储模型，使得程序员不必进行数据划分和分布，使得开发并行程序比较容易；第二，更适合于SMP系统；第三，主要面向循环级的并行开发，可以容易地实现增量性的并行化。缺点：第一，OpenMP只适用于SMP结构；第二，OpenMP主要开发循环级的并行程序，受此限制，对某些应用并不适合；第三，OpenMP的编写、正确性调试和性能调度复杂。3. Intel IPPIntel IPP(Integrated Performance Primitives)，Intel集成性能基元是Intel函数库的第二代。Intel为每种新的多核处理器都发布一个IPP函数库（C/C+ API），专用于多核架构，提供了调度优化的函数库，其中涉及的领域有数学、信号处理、音频视频、图像处理与编码、字符串、密码学。优点：是经过性能高度优化的库，执行效率高。缺点：专用于Intel处理器和某些领域，不方便移植发展趋势：为广泛的多媒体提供功能，并着眼于持续改进产品的生命周期。4. Intel TBBIntel TBB(Threading Building Blocks)，Intel线程构建模块，是一个为创建可靠的、可移植的和可扩展的并行程序的C+模板库。专用于编写高层抽象的C+程序，和可移植的程序。优点：可移植、可扩展。缺点：性能没有IPP高。发展趋势：扩展TBB到支持java和.net5. MapReduce MapReducesh是Google的人研究出来的一个模型，开发的一个针对大规模群组中的海量数据处理的分布式编程模型。优点：能用于处理大规模数据，能将很多繁琐的细节隐藏起来，伸缩性非常好缺点：不适应实时应用的需求精品.发展趋势：用优化云计算下的的编程如有侵权请联系告知删除，感谢你们的配合！精品