论文部分内容阅读
【摘要】并行处理是计算数学与新一代计算机科相结合的产物，是大型科学计算和工程试验的支持工具。本文从并行计算的必要性、产生、现状和发展趋势等几个方面，系统地阐述了并行计算技术的基本问题。
【关键词】并行算法；并行计算技术；并行处理系统
【Abstract】The parallel processing is a product which the computational mathematics and the new generation of computer branch unifies, is the large-scale science computation and the engineering test support tool. This article from the parallel computation necessity, has, the present situation and the development tendency and so on several aspects, systematically elaborated the parallel computation technology basic question.
【Key words】Parallel algorithm； parallel computation technology ；parallel processing system
并行计算与并行算法是计算数学与新一代计算机相结合的产物，是大规模科学计算的理论基础和支持工具。随着超级并行计算机的迅速发展，计算领域最高端的高性能计算将仍然是本世纪IT领域人们争夺的制高点。人们已经认识到了高性能计算机的发展趋势和意义，但是高性能计算机的发展一直面临着挑战，其巨大的计算潜力与性能始终没有被充分应用起来。如何将体系结构、硬件技术、编程环境、并行算法和基础理论紧密结合起来，涉及多个亟待解决的问题。并行算法，简单的说，就是适合在并行计算机和向量计算机上求解问题的数值方法。Kung(1980)年在《并行算法结构》一文中将并行算法定义为“多个并发进程的集合，这些进程同时并相互协作地进行运行处理，从而达到对给定问题的求解”。
1.并行计算技术的必要性
我们为什么需要并行计算，其最朴素的道理就是串行计算满足不了求解问题的要求了，这些要求或是计算时间上的要求，或是计算精度上的要求，也或许是快速响应的实时要求，也或许是某些不可替代的特殊计算任务的要求。现在的计算机工作站已经比10年前的要快100倍，但是计算机科学家和工程师还需要更快的速度。虽然他们已经对某些问题进行了大量的简化，但是现有的计算机仍然需要数小时、数日甚至数周的时间来完成他们的程序。如果使用并行计算方法，当程序突然快了十倍二十几倍的时候，过去的一些无法忍受的计算任务现在变的可以接受了，所以并行计算是获得计算的更高性能的有效方法。
2.国内外并行计算技术发展现状和趋势
虽然许多人都认识到并行计算技术的重要性，但并行计算技术的发展道路并不平坦。并行计算技术发展过程几起几落，究其原因，就是并行计算技术仍然遇到若干困难，使其无法推广应用，其中最主要的一个问题就是并行程序设计方法尚未达到科学化、实用化和大众化阶段。高性能并行机系统是当今世界的一项高科技关键技术，与国民经济的发展及国家综合国力的增强有着密切的联系。我国自行研制成功了若干系列的并行机系统，并引进了国外一些并行机系统，这为我国高性能计算提供了高起点的物质基础，但是并行软件与并行算法的滞后已成为当今国内外研制与推动高性能并行机的一个主要瓶颈。目前国内外并行计算技术总的来说呈现如下现状:并行软件和并行算法的发展远远落后于并行计算机系统的发展。并行和分布式计算应用的发展远远落后于并行和分布式计算技术的发展。并行计算机系统的规模可伸缩性和可编程性已成为并行和分布计算系统进一步发展的一对主要矛盾。大规模并行处理机系统(MPP)已经不再是主要研究领域。基于分布共享存储器DSM (Distributed Shared Memory)结构的并行机系统，由于其具有良好的可伸缩性和可编程性，己受到诸多计算机厂商的青睐，不少厂商己经和准备推出此种类型的并行机系统。
2.1 几个主要国家的研究状况：美国在并行和分布计算研究领域中，一直处于领先地位。研究重点己从原来热门非凡的MPP系统转向可伸缩并行机和各种类型的计算机机群口。特别是后者，因为如果部门或单位己有现成的由局域网连接起来的众多工作站、PC机、服务器及并行机系统，则组成计算机机群的分布计算系统的成本就相当低，而它们的整体性能可随机群局域互联网性能的提高(从1OMbps,100Mbps,155Mbps,622Mbps到1Gmps等)、构成机群的结点机性能提高以及运行软件的效率提高而不断提高。德国致力于MPP系统的研究，取得了一定成果。如GMD-FIRST柏林计算机研究所于1995年研制成规模可伸缩的MANNA并行机系统，采用高速、层次结构的纵横交叉开关(Crossbar Switch)互联网络。日本自90年代初推出RWC(Real World Computing)计划以来，研究前景不容乐观，原来计划要研制的光计算机和大规模神经网络计算机系统，看来困难重重。
2.2 我国的主要差距及薄弱环节：我国的并行和分布计算技术研究，自上个世纪60年代末开始至今已经历了三个阶段:第一阶段，上个世纪60年代末到70年代末，主要从事大型机中的并行计算技术研究;第二阶段，上个世纪70年代末至90年代初，主要从事向量机和并行多处理器系统研究；第三阶段，自上个世纪80年代末至今，主要从事MPP系统及工作站机群系统研究。每个阶段都研制成一些样机，但由于缺乏竞争能力，均无法形成批量生产规模。此外，我国在并行应用方面所开展的研究还较少，尽管很多部门和单位已有不少联网的计算资源，如工作站、PC机、服务器和各种并行机等，但通常这些用户单位都不知道如何从事并行计算及开展并行应用。
2.3 发展趋势当前国外主要的重点研究领域包括下面的几个部分:
2.3.1 并行算法的设计、分析和实现:其中包括数值和非数值并行算法、同步和异步算法以及分布式算法;上述算法的时间和空间复杂性分析;算法的实现方法等。
2.3.2 并行优化编译:其中包括粗、中、细精度三个层次上的并行优化编译。并化编译方法包括对程序中存在的并行性进行检测，即分析和判定各种相关性、相关性的消除方法、各种并行化程序变换技术，以及数组私有化识别和过程之间的分析等。优化编译方法包括减少程序执行的指令数的优化;提高Cache中对同一数据的时间重用和对同一数据行的空间重用，即提高对Cache访问的命中率优化，寄存器使用优化以及指令级程序并行执行优化，如基本块内指令级并行、跨基本块的指令级并行以及循环内的指令级并行优化等。
2.3.3 各种类型的规模可伸缩计算机机群间通信方法的研究包括同构和异构计算机机群，以及减小机群。
2.3.4 用NUMA，特别是CC-NUMA方法构成的并行机体系结构及各种实现方法的研究。综上所述，并行计算技术作为计算数学的一个较新研究分支，在计算数学的多个传统研究与应用领域中都已取得了令人瞩目的进展，具有重要的科研价值和广阔的发展前景。
参考文献
［1］ 孙世新、卢光辉.并行算法及其应用［M］北京:机械工业出版社，2005
［2］ 都志辉.高性能计算并行编程技术- MPI并行程序设计［M］.北京: 清华大学出版社，2001
［3］ 胡峰、胡保生.并行计算技术与并行算法综述.电脑与信息技术，1999,(5):47-59
【关键词】并行算法；并行计算技术；并行处理系统
【Abstract】The parallel processing is a product which the computational mathematics and the new generation of computer branch unifies, is the large-scale science computation and the engineering test support tool. This article from the parallel computation necessity, has, the present situation and the development tendency and so on several aspects, systematically elaborated the parallel computation technology basic question.
【Key words】Parallel algorithm； parallel computation technology ；parallel processing system
并行计算与并行算法是计算数学与新一代计算机相结合的产物，是大规模科学计算的理论基础和支持工具。随着超级并行计算机的迅速发展，计算领域最高端的高性能计算将仍然是本世纪IT领域人们争夺的制高点。人们已经认识到了高性能计算机的发展趋势和意义，但是高性能计算机的发展一直面临着挑战，其巨大的计算潜力与性能始终没有被充分应用起来。如何将体系结构、硬件技术、编程环境、并行算法和基础理论紧密结合起来，涉及多个亟待解决的问题。并行算法，简单的说，就是适合在并行计算机和向量计算机上求解问题的数值方法。Kung(1980)年在《并行算法结构》一文中将并行算法定义为“多个并发进程的集合，这些进程同时并相互协作地进行运行处理，从而达到对给定问题的求解”。
1.并行计算技术的必要性
我们为什么需要并行计算，其最朴素的道理就是串行计算满足不了求解问题的要求了，这些要求或是计算时间上的要求，或是计算精度上的要求，也或许是快速响应的实时要求，也或许是某些不可替代的特殊计算任务的要求。现在的计算机工作站已经比10年前的要快100倍，但是计算机科学家和工程师还需要更快的速度。虽然他们已经对某些问题进行了大量的简化，但是现有的计算机仍然需要数小时、数日甚至数周的时间来完成他们的程序。如果使用并行计算方法，当程序突然快了十倍二十几倍的时候，过去的一些无法忍受的计算任务现在变的可以接受了，所以并行计算是获得计算的更高性能的有效方法。
2.国内外并行计算技术发展现状和趋势
虽然许多人都认识到并行计算技术的重要性，但并行计算技术的发展道路并不平坦。并行计算技术发展过程几起几落，究其原因，就是并行计算技术仍然遇到若干困难，使其无法推广应用，其中最主要的一个问题就是并行程序设计方法尚未达到科学化、实用化和大众化阶段。高性能并行机系统是当今世界的一项高科技关键技术，与国民经济的发展及国家综合国力的增强有着密切的联系。我国自行研制成功了若干系列的并行机系统，并引进了国外一些并行机系统，这为我国高性能计算提供了高起点的物质基础，但是并行软件与并行算法的滞后已成为当今国内外研制与推动高性能并行机的一个主要瓶颈。目前国内外并行计算技术总的来说呈现如下现状:并行软件和并行算法的发展远远落后于并行计算机系统的发展。并行和分布式计算应用的发展远远落后于并行和分布式计算技术的发展。并行计算机系统的规模可伸缩性和可编程性已成为并行和分布计算系统进一步发展的一对主要矛盾。大规模并行处理机系统(MPP)已经不再是主要研究领域。基于分布共享存储器DSM (Distributed Shared Memory)结构的并行机系统，由于其具有良好的可伸缩性和可编程性，己受到诸多计算机厂商的青睐，不少厂商己经和准备推出此种类型的并行机系统。
2.1 几个主要国家的研究状况：美国在并行和分布计算研究领域中，一直处于领先地位。研究重点己从原来热门非凡的MPP系统转向可伸缩并行机和各种类型的计算机机群口。特别是后者，因为如果部门或单位己有现成的由局域网连接起来的众多工作站、PC机、服务器及并行机系统，则组成计算机机群的分布计算系统的成本就相当低，而它们的整体性能可随机群局域互联网性能的提高(从1OMbps,100Mbps,155Mbps,622Mbps到1Gmps等)、构成机群的结点机性能提高以及运行软件的效率提高而不断提高。德国致力于MPP系统的研究，取得了一定成果。如GMD-FIRST柏林计算机研究所于1995年研制成规模可伸缩的MANNA并行机系统，采用高速、层次结构的纵横交叉开关(Crossbar Switch)互联网络。日本自90年代初推出RWC(Real World Computing)计划以来，研究前景不容乐观，原来计划要研制的光计算机和大规模神经网络计算机系统，看来困难重重。
2.2 我国的主要差距及薄弱环节：我国的并行和分布计算技术研究，自上个世纪60年代末开始至今已经历了三个阶段:第一阶段，上个世纪60年代末到70年代末，主要从事大型机中的并行计算技术研究;第二阶段，上个世纪70年代末至90年代初，主要从事向量机和并行多处理器系统研究；第三阶段，自上个世纪80年代末至今，主要从事MPP系统及工作站机群系统研究。每个阶段都研制成一些样机，但由于缺乏竞争能力，均无法形成批量生产规模。此外，我国在并行应用方面所开展的研究还较少，尽管很多部门和单位已有不少联网的计算资源，如工作站、PC机、服务器和各种并行机等，但通常这些用户单位都不知道如何从事并行计算及开展并行应用。
2.3 发展趋势当前国外主要的重点研究领域包括下面的几个部分:
2.3.1 并行算法的设计、分析和实现:其中包括数值和非数值并行算法、同步和异步算法以及分布式算法;上述算法的时间和空间复杂性分析;算法的实现方法等。
2.3.2 并行优化编译:其中包括粗、中、细精度三个层次上的并行优化编译。并化编译方法包括对程序中存在的并行性进行检测，即分析和判定各种相关性、相关性的消除方法、各种并行化程序变换技术，以及数组私有化识别和过程之间的分析等。优化编译方法包括减少程序执行的指令数的优化;提高Cache中对同一数据的时间重用和对同一数据行的空间重用，即提高对Cache访问的命中率优化，寄存器使用优化以及指令级程序并行执行优化，如基本块内指令级并行、跨基本块的指令级并行以及循环内的指令级并行优化等。
2.3.3 各种类型的规模可伸缩计算机机群间通信方法的研究包括同构和异构计算机机群，以及减小机群。
2.3.4 用NUMA，特别是CC-NUMA方法构成的并行机体系结构及各种实现方法的研究。综上所述，并行计算技术作为计算数学的一个较新研究分支，在计算数学的多个传统研究与应用领域中都已取得了令人瞩目的进展，具有重要的科研价值和广阔的发展前景。
参考文献
［1］ 孙世新、卢光辉.并行算法及其应用［M］北京:机械工业出版社，2005
［2］ 都志辉.高性能计算并行编程技术- MPI并行程序设计［M］.北京: 清华大学出版社，2001
［3］ 胡峰、胡保生.并行计算技术与并行算法综述.电脑与信息技术，1999,(5):47-59