并行算法与并行软件设计第五章现代并行算法基础.doc

第五章 现代并行算法基础 本章将详细介绍并行算法的基本概念、并行程序设计方法和并行实现环境，为从事并行计算研究和使用超级计算机系统奠定基础。其中主要涉及的内容有：介绍并行计算机的发展，当今并行计算机的主流发展方向；并行计算的基本概念，并行算法的基本类型及设计技术；矩阵并行计算问题，重点介绍并行矩阵乘法，线性代数方程组并行求解方法，代数特征值问题的并行求解，经典迭代算法的并行化；并行程序设计技术，介绍并行程序的特点和实现技术等。 5.1 并行计算综述 5.1.1 并行计算的目标和内容 目标：求解大规模问题和复杂系统。早期并行计算以加速求解问题为目的，这来源于单处理机的计算速度受到物理上的限制，光速是其上限。随着计算在科学研究和实际应用中发挥越来越大的作用，人们对计算已经产生了依赖，将数值模拟作为许多决策的依据。现在人们已经习惯将计算作为科学研究的第三种手段，和传统的科学研究的理论方法和实验方法并列。 自90 年代以来，并行计算得以空前的飞速发展，一方面，由于单处理机的计算速度不断提高，并行计算机的体系结构趋于成熟，数据传输网络的标准化和传输速率的大幅提升，使得并行计算机的研制周期能够从几年到几个月，为研制并行计算机系统创造了有利条件。另一方面，推动并行计算发展的主要动力来自于国际上的一些重要研究计划。 美国HPCC 计划：（High Performance Computing and Communications）科学和工程计算需要能够提供1TFLOPS 计算能力、1TB 内存容量、1TB/s 的I/O 带宽，也就是3T 性能目标。美国为了保持其在高性能计算与计算机通信领域的领先地位，在1993 年，由科学、工程、技术联邦协调理事会向国会提交了“重大挑战项目：高性能计算与通信”的报告，也就是被称为HPCC 计划的报告，即美国总统科学战略项目，其目的是通过加强研究与开发解决一批重要的科学与技术挑战问题。该项目由四部分组成： 1) 高性能计算机系统（HPCS），内容包括今后几代计算机系统的研究、系统设计工具、先进的典型系统及原有系统的评价等； 2) 先进软件技术与算法（ASTA），内容有巨大挑战问题的软件支撑、新算法设计、软件分支与工具、计算技术及高性能计算研究中心等； 3) 国家科研与教育网（NREN），内容有中接站及10 亿位级传输的研究与开发； 4) 基本研究与人类资源（BRHR），内容有基础研究、培训、教育及课程教材。 HPCC 计划中近期要解决的“巨大挑战”问题有： 1) 磁记录技术。要在一平方厘米的磁盘表面上压缩记录10 亿位数据； 2) 新药研制。特别是防治癌症与艾滋病新药的研制； 3) 高速城市交通。新型低噪音飞机的研制，空气动力学的计算； 4) 催化剂设计。改变至今为止多数催化剂靠经验设计的习惯，转向计算机辅助设计，主要分析这些复杂系统的大规模量子化学模型； 5) 燃料燃烧原理。通过化学动力学计算，揭示流体力学的作用，研制新型发动机； 6) 海洋模型模拟。对海洋活动与大气流的热交换进行整体海洋模拟； 7) 臭氧层空洞。研究控制臭氧消耗过程的化学和动力学机制； 8) 数字解剖。如三维CT 扫描图象处理，人脑主题模型，三维生物结构与四维时间 结构； 9) 空气污染。计算模拟能提供有效控制污染传播的途径，揭示其物理与化学机理； 10) 蛋白质结构设计。使用计算机模拟，对蛋白质组成的三维结构进行研究； 11) 图象理解。实时绘制图象或动画； 12) 密码破译技术。破译长位数的密码，主要是寻找一个大数的两个素因子。 请参阅 美国ASCI 计划(Accelerated Strategic Computing Initiative)：全面禁止核试验条约签订后，对核武器的研制只能通过在实验室的数值模拟来完成。1996 年6 月由美国能源部提出了“加速战略计算创新”计划，也即ASCI 计划项目。提出通过数值模拟来评估核武器的性能、安全性、可靠性、更新等。要求数值模拟达到高分辨率、高逼真度、三维、全物理、全系统的规模和能力。该计划被认为是与当年曼哈顿计划等同的一个巨大的挑战，它不仅需要自然科学家的参与，而且也需要与计算机等工业界的合作，提供保障ASCI 计划中的应用所需的计算机平台。为此，美国三大核武器实验室（Lawrence Livermore、Los Alamos、Sandia国家实验室）分别向三大计算机公司（Intel、IBM、SGI/Cray 公司）预订了峰值浮点运算速度超过1TFLOPS 的并行计算机。目前已经在这些实验室投入使用的并行计算机系统，其峰值浮点运算速度已经超过了50TFLOPS。 5.1.2目前世界高性能计算机的状况 并行计算机随着微处理芯片的发展，已经进入了一个新时代。目前并行计算机的性能已经接近100TFL