并行处理技术与并行计算机

并行处理技术与并行计算机[摘要]：本文从计算机的体系结构和软件系统两方面阐述了并行处理技术的主要技术，并介绍了并行计算机发展的现状和趋势。[关键词]：并行处理，并行计算机[ABSTRACT]:Inthispaper,wesummarizetheprimarytechnologyofparallelprocessingfromtwoaspect--------architectureandsoftware,andwealsointroducethestatusinquoandtrendofparallelcomputer.[KEYWORDS]:ParallelProcessing;ParallelComputer;引言计算机系统发展到今天,其性能价格已经极大的满足了多数人的需要,VLSI技术的发展使得计算机系统的性能得以飞速的提高..单处理机系统提高运算速度的主要途径是体系结构和电路工艺上的改进.结构上包括流水线结构,向量处理和指令级并行性的开发等,它只能把速度提高大约十倍,电路上的新材料还未成熟,而微小化几乎要接近极限.在80年代中期,美国科技政策署就提出了巨大挑战(GrandChallenges)的任务,其中的气候模拟,半导体模拟,受控核聚变研究,海洋环流等需要大量复杂计算的问题都需要运算速度比现有的系统高的多的超级计算机.早在80年代初,各种16/32位的高性能微处理机的并行机系统就出现了,并行处理技术以其高性能,广大的发展潜力,必将成为21世纪制造高性能计算机的关键计算.对并行处理技术的研究包括了并行机硬件和并行软件系统.本文将在这两方面进行探讨,最后说明目前并行计算机的一些发展概况及趋势.并行处理技术1.并行机的体系结构对于计算机系统，存在着几种不同的分类法。本文将根据并行计算机的基本结构特点，分成以下四种结构：传统的向量并行机VPP，多处理机MP，工作站机群NOW及大规模并行处理机MPP。1.1VPP传统的向量并行机向量机已经使用了十几年，到现在，其编译技术日益成熟，适用范围逐步扩大。向量机发展到现在，已经遇到了严重的障碍，主要有三个方面：首先，它的效率取决于应用程序中可向量化语句所占的比例。仅仅采用向量流水技术，加速比不会很高。另一方面，提高向量机性能的主要途径是加快主频，而现在主频的再提高潜力不大。其次，向量机主要开发低层次的并行性，而低层次的并行有一定的限度。最后是它的可伸缩性。复杂度不允许连接太多的处理机。一些主要的向量机有CDC7600,Cyber205,ETA-10,CRAY1,CRAYYMP/C90,FujitsuVP200VP500,NEC的SX-3等。1.2多处理机MPMP(Multiprocessor)结构具有两台以上的处理机，在操作系统控制下通过共享的主存或输入输出子系统或高速通讯网络进行通讯。多处理机属MIMD系统。MP系统有两种不同的系统结构：紧耦合系统（TCS）和松耦合系统（LCS）.紧耦合是通过共享主存实现处理机间的互相通信，处理机间的相互联系比较紧密。按所用处理机类型是否相同及对称，又可分为同构或异构及对称或非对称的形式。常见组合是同构对称式和异构非对称式多机系统。同时它有两种典型的形式：一种是不带高速缓冲存储器（如CMMP多机系统）；另一种是带专用高速缓冲寄存器（如IBM3084多机系统）。松耦合是通过消息传递方式来实现处理机间的相互通信，而每个处理机是由一个独立性较强的计算机模块组成。在多机系统中，无论使用什么耦合的结构，在处理机之间，处理机和主存之间以及处理机和I/O之间都要通过互联网络实现信息交换。多机系统的性能在很大程度上依赖于互联网络。多处理机之间数据的交换可以使用串口，并口，DMA，共享存储器和双端口RMA等方法达到此目的。衡量多处理机调度性能好坏的主要参数通常有：完成所有任务所需最少时间；完成所有任务所需最少处理机数；最小平均流时间即执行每个任务所需平均时间；处理机的最大利用率或最小空闲时间1.3工作站群NOW（NetworkofWorkstations）NOW是用互联网将两个以上高性能的工作站连接在一起，并配以相应的支撑软件，构成一个分布式并行计算机系统，工作站之间的程序执行和消息传递都是并行的。具有并行计算性能的NOW，能加速作业的执行，NOW的互联可以采用Ethernet，FDDI，VLTRAnet，ATM等。它是一种新兴的并行机结构，充分利用各工作站或微机资源，统一调度，协调处理，以实现高效并行处理。NOW具有用户投资风险小，编程方便，结构灵活，可扩展性好等优点。需要解决的关键问题是实现高带宽，低延迟的互联网技术。一些NOW有：SGI公司的PowerChallengeArray(CPU数128个，速度46.1GFLOPS),DEC公司的TurboLaserCluster(CPU数96个，速度57，6GFLOPS)。1.4大规模并行处理机MPPMPP用各种互联网络把成百上千个处理器互联起来，具有很好的可扩充性，处理器间的同步是以消息传递为主，没有共享存储器。通常处理器数量有100个以上，有两种常见的结构：SIMD（单指令流多数据流）和MIMD（多指令流多数据流）。SIMD将大量重复设置的处理单元按一定方式互连成阵列，在单一控制部件CU(ContrulUnit)控制下对各自所分配的不同数据并行执行同一指令规定的操作，是操作并行的SIMD计算机。MIMD是系统由多个处理器自动的对不同数据执行不同的操作，它是实现作业，任务，指令和数组各个级别的全面并行处理的理想结构。MPP的处理器间的连接方式主要有：hypercube，mesh，tree结构等。而对于诸如单总线结构，单环结构，星形结构，全互连结构等则不适宜于MPP系统。对单总线或单环结构，总线瓶颈严重，当结点数超过数十台后系统性能随结点数增加而急剧下降，虽然为改善这一不足出现了双总线，双环等结构，但对于超大规模（结点数上千时）MPP系统来说，系统性能仍然很低。对于星型结构，中央节点将成为系统的瓶颈，而且一旦中央节点故障，整个系统就瘫痪。对于全互连结构，虽然理论上来说时最佳互连结构，但当互连结点数很多情况下，物理上实现极为困难。即使能实现代价也会很高。如何减少通信开销和同步开销是MPP技术的关键所在，当前的研究集中在如何获得高效的通信技术上，其目的是提高应用中的计算通信比。通信开销有以下几个来源：网络接口，通信延迟，收发开销。要想尽可能的减少通信开销，有效的途径是改善网络接口，减小或重叠通信延迟和降低发收开销。由于网络接口与结点体系结构有事不可分的一个整体，因而对高效的通信技术的研究和追求正是MPP体系结构迅速进步的巨大动力。决定互连网络性能的另一个重要因素是网络的路由算法。近年来被广为采用的“虫蛀式”路由算法（WormholeRouting）将流水线技术的原理用于数据传输技术，不但减少了设备量，提高了数据传输速度，更为重要的是，它在相当程度上减轻了传送一个信息包所需时间与结点间距离的相关性，从而使用户编程时不必过多的考虑系统的拓扑结构。这种算法已成为当前的主流技术。目前MPP一般采用低价格，高性能的通用微处理机芯片做处理单元，因而性价比高，通用性好。典型代表有Cray公司的T3D（CPU数1024个，速度152GFLOPS），Intel公司的ParagonXP/S(CPU数3680个，速度184GFLOPS)。2并行软件并行机使用的效率和方便性的解决有赖于并行软件（ParallelSoftware）的发展。对并行软件的讨论包括：并行操作系统，2.1并行操作系统任何操作系统的功能都有两个：一是对计算机资源进行管理，二是为用户使用计算机提供支持。对并行机而言，一般可以划分成两类：主从式结构和浮动式结构。在主从式系统中，在一个或多个处理机上运行主操作系统，在其他大量的处理机上运行从操作系统。主操作系统具有完善的操作系统功能，并为从系统分配任务；从系统是一个简单的操作系统内核，负责对主系统分配的多个运行任务进行管理和调度。在浮动式结构中，每个处理机上的操作系统都是一个完整的系统，它们具有完全相同的功能。所谓浮动，是指各处理机上的操作系统都可以作为主系统与其他处理机发生关系，也都可以作为从系统承担运算任务。并行操作系统的主要研究内容有：机间通信和处理机负载平衡；进程通信；线程机制。较著名的并行操作系统有：Mach，SVR，4.2/MP，Solaris及OSF/1等。2.2并行算法并行算法是研究在各种并行计算机上求解问题，处理数据的算法。它由一些独立的，可以并行运算的计算模块组成，这些模块彼此间能互相通信。把一个问题分解成为互相独立，但彼此又有联系的若干问题（或若干进程）是并行算法研究的主要方法和手段。并行算法的特点可归纳为“多，分，高，模，混，序”。所谓“多”是指“多重”，“多层”，“多步”等方法；“分”是指“分裂”，“分解”，“分块”，“分片”，“分区”等一系列：分而治之方法；“高”，是指“高精度”，“高维化”等；“模”是一批有效的物理或数值模拟方法，如求解大型组合优化问题用的模拟退火法SAA。“混”主要指“混乱迭代”等异步并行方法。“序”是指重新排序。并行算法按不同处理范畴分为数值并行算法和非数值并行算法。按照指令流分为SIMD算法和MIMD算法；按是否同步分为同步算法和异步算法。同步算法是某些进程必须等待别的进程的一类并行算法；异步算法是指诸进程不必相互等待的一类并行算法。一般，当有K(1)个进程时，可以同一分为：SIMD算法（1个指令流保证同步）；同步MIMD算法（K个指令流需同步）；异步算法（K个指令流中MIMD不需同步）。并行算法的主要来源于两个方面：一是将串行算法改写成并行算法。这种较容易实现，当受到串行框架的限制，难以取得较高并行度的算法；二是从数学模型出发直接构造并行算法。这比较难实现，但深入研究会使并行算法的设计有所突破。现已形成了一些理论和技术：NC理论，并行复杂度理论，下界技术，倍增技术，划分原理，对称技术，平衡树法，分治策略，流水线技术等。2.3并行语言并行语言是描述和设计并行程序的工具，人们从七十年代开始才将并行程序设计的概念引入程序设计语言，开发出了并发Pascal，ModulaII和Ada等并行语言；八十年代在通用的串行语言基础上进行功能性扩充。目前实现通用语言并行化的方法有三种：(1)在原语言的基础上增加一些并行处理的语言描述成分。(2)增加一个并行程序库，用户通过使用库函数实现并行处理。(3)把前两种方法结合起来，即在语言中增加必要的描述成分和一个并行程序库；并行程序程序设计主要有以下两种方法：自动并行化以及设计并行程序2.4并行编译并行程序的性能在很大程度上取决于并行编译产生的目标程序的质量。编译系统并行化的技术难点是对一个源程序自动识别出可并行自行的部分，并将其并行化，同时保证这个程序正确运行。并行识别的目标是完成串行程序向并行程序的自动转化，由语言编译器实现，关键是充分开发并行性。著名的并行编译系统有Illinois大学的Parafrase系统，ParafraseII系统，Rice大学的PFC系统，IBM的Ptran系统等。2.5并行程序开发环境由于并行计算机程序设计设计程序分割，数据分配，进程同步，负荷均衡，性能优化等诸多方面的问题，其难度比传统的单机程序开发大得多，因此提供功能完备的并行程序开发环境是降低并行计算机编程难度，促进并行计算机的推广应用的关键。并行程序开发环境主要包括并行语言及其编译系统，程序优化重构工具，图形可视化工具，编辑工具及智能性工具等，较流行的并行程序开发环境有PPME，Express及PVM等。并行计算机的现状及前景并行计算机已有20多年的历史。九十年代，无疑是并行处理，超并行处理飞速发展的年代。目前如COMPAQ的Systempro以及ATT的StarServerE等微机多机系统已开始发展并逐渐成熟。并行机产品目前分为两种：共享存储器式和分布存储器式（报文传递式）。其中共享存储器式应用最为普遍，其中总线式共享存储器的并行计算机更为突出。分