并行计算机体系结构

第一章并行计算机体系结构在介绍并行算法及其软件设计之前，必须先介绍一下并行计算机与分布式并行的一些基本知识。目前国内这方面的资料不是很完善，为此，本章将阐述一下并行计算机体系结构的一些基本知识。1.1并行计算机定义简单地讲，并行计算机就是由多个处理单元(以下也称为处理器，或简称为CPU)组成的计算机系统，这些处理单元相互通信和协作能快速、高效的求解大型复杂问题。定义中涉及的问题：a)并行计算机的规模：,例如处理单元有多少，这就涉及到系统是小规模的(十个或几十个)、中规模的(上百个)和大规模的(成千上万个)的问题；b)处理单元的功能：处理单元的功能有多强，这就涉及到系统的组织策略是平行对称的“蚁军法”(ArmyofAnts)或是一种主从的形式“象群法”(HertofElephants)的问题；c)处理单元之间怎样连接，这就涉及到系统是按照什么样的拓朴结构彼此互连起来的问题；d)处理单元的数据是如何传递的，这就涉及到通信是按照共享变量方式的或消息传递方式的问题。e)各处理单元彼此相互协作共同求解大型复杂问题，则涉及到的问题更多，例如如何保证多处理单元操作的顺序性，这就涉及到同步互斥问题；如何确保共享数据的完整性问题，这就涉及到不同存储层次中的数据的一致性问题。f)此外，还有求解具体问题的并行程序的编写、调试、运行和性能分析等方面的问题。1.2并行机的由来并行计算机是相对串行计算机而言的，所谓串行计算机就是只有单个处理单元顺序执行计算程序的计算机，所以也称为顺序计算机。顺序计算机最早是从位串行操作到字并行操作、从定点运算到浮点运算改进过来的；然后它按照图1.1所示的过程逐步演变出各种并行计算机系统：从顺序标量处理(ScalarProcessing)计算机开始，首先用先行(Look-ahead)技术预取指令，达到重叠操作实现功能并行；支持功能并行可使用多功能部件和流水线两种方法；而流水线技术对处理向量数据元素的重复相同的操作表现出强大的威力，从而产生了向量流水线（Vector-pipelining）计算机（包括存储器到存储器和寄存器到寄存器两种结构）；不同于时间上并行的流水线计算机，另一分支的并行机是空间上并行的SIMD（单指令流多数据流）并行机，它用同一控制器同步地控制所有处理器阵列执行相同操作来开发空间上的并行性；如果用不同的控制器异步地控制相应的处理单元执行各自的操作，则就派生出另一类非常主要的MIMD（多指令流多数据流）并行机；其中，如果各处理单元通过公用存储器中的共享变量实现相互通信，则就称为多处理机（Multiprossors）；如果处理单元之间使用消息传递的方式来实现相互通信，则就称为多计算机（Multicomputers），它也是当今最流行的并行计算机，也是本书讨论的重点。顺序的标量先行功能并行流水线显式向量寄存器到寄存器MIMD多处理机I/E重叠多个功能部件隐式向量存储器到存储器SIMD多计算机处理器阵列联想处理器大规模并行处理机（MPP）I/E:取指与执行SIMD:单指令流与多数据流MIMD:多指令流与多数据流图1.1从标量到向量和并行计算机的演变1.3当代并行机系统自20世纪70年代初到现在，并行计算机的发展已有20多年的历史.在此期间，出现了各种不同类型的并行机，包括历史上曾经风行一时的并行向量机PVP(ParallelVectorProcessor)和SIMD计算机，但它们现在均已衰落了下来，而MIMD类型的并行机却占了主导地位。当代的主流并行机是可扩放的并行计算机(Scalable-ParallelComputer)，包括共享存储的对称多处理机SMP(SymmetricMultiprocessor)，分布存储的大规模并行机MPP(MassivelyParallelProcessor)，分布式共享存储DSM(DistributedSharedMemory)多处理机和工作站机群COW(ClusterofWorkstations)以及刚刚兴起的跨地域性的、用高速网络将异构性计算节点连接起来满足用户分布式计算要求的所谓网格计算环境GCE(GridComputationalEnvironment)。本课程将重点讨论前4种当代可扩放的主流并行计算机。1.4高性能计算机顺便讲一下并行计算机与高性能计算机的关系。其实，高性能计算机并无明确严格的定义。因为性能可定义为求解问题所花费的时间的倒数，即求解问题的速度，所以按此意义，只要那些速度非常快的计算机都可认为是高性能计算机。当然，能高速求解问题的计算机，可以包括大型计算机(Mainframe)，如早期的IBM370系列；超级计算机(Supercomputer)，如Cray-1向量计算机以及各种并行计算机。因为为了达到高性能，仅靠改进电路工艺，提高单机器件速度是有限的，所以使用并行计算机的方法则更为普通和有效，于是并行计算机也就渐渐地变成了高性能计算机的同义词了，这种说法虽不严格，但已被普遍认可。1.5并行计算机发展背景90年代，并行计算机已成为计算机技术中的关键部分，预计下20年它对计算机的发展冲击会更大。并行计算机虽然有着漫长的历史，但其突飞猛进的发展却是得益于高度集成的微处理器芯片和快速大容量存储器芯片。历史上看，从60年代中期开始，小型计算机（Minicomputer）和大型计算机(Mainframe)便迅速发展起来；从70年代初期起，超级计算机(Supercomputer)则得以蓬勃发展；但到了80年代中期，微处理器的性能（速度）每年改进50%，而大型计算机和超级计算机的性能，每年只改进25%。高度集成的、单片CMOS微处理器的性能稳定地压倒了那些较大的和较昂贵的其它处理器芯片，这样使用小型的、便宜的、低功耗的和批量生产的处理器作为基本模块来构筑计算机系统就变得非常直观的事了。到了90年代后期，单片微处理器占据着计算的各个方面，而并行计算也撑管了主流计算的很多领域。在微处理器出现之前，为了获得高性能，人们主要是通过特殊的电路工艺和机器组织，而现今大家普遍意识到使用多个处理器构成并行机和编写并行程序才是更为有效的途径。以上是并行机发展的基本硬件背景。下面我们将深入讨论，是什么力量和趋势促进了并行计算机的发展，包括应用和技术进展以及并行计算机体系结构发展趋势。1.6应用需求从计算机的市场上看，一般的计算机用户都是使用低端计算机（PC机和工作站等），而那些富有挑战性的应用问题都需要使用高端计算机（超级计算机和并行计算机）。这些挑战的应用问题大都来自复杂科学计算，大型工程应用以及大存储容量和高RAS（Reliability，Availability，Serviceability）的商务处理，而且市场统计表明，科学和工程计算方面的应用只占并行机市场的小头，而大头却在众多的商业事务处理上。1.6.1科学和工程计算主流的科学计算主要有物理、化学、材料科学、生物学、天文学和地球科学等等；典型的工程应用主要有能源勘探、油藏模拟、药物分析、燃烧效率分析、汽车碰撞模拟、飞行器气流分析等等。这些当代科学与工程问题对计算机的应用需求，典型地反映在美国HPCC计划和美国ASCI计划中。（1）美国HPCC计划：美国为了保持在高性能计算机和通信领域中的世界领先地位，美国科学、工程、技术联邦协调理事会于1993年向国会提交了题为“重大挑战项目：高性能计算和通信”(HighPerformanceComputingandCommunication)的报告，简称为HPCC计划，即美国总统科学战略项目，这些重大挑战性课题的应用领域兹汇总于表1.1中。应用领域计算任务和预期结果磁记录技术研究静磁和交互感应以降低高密度磁盘的噪音新药设计通过抑制人的免疫故障病毒蛋白酶的作用来研制治疗癌症和艾滋病的药物高速民航用计算流体动力学来研制超音速喷气发动机催化作用仿生催化剂计算机建模，分析合成过程中的酶作用燃料燃烧通过化学动力学计算，揭示流体力学的作用，设计新型发动机海洋建模对海洋活动与大气流的热交换进行整体海洋模拟臭氧耗损研究控制臭氧消耗过程的化学和动力学机制数字解析用计算机研究实时临床成像、计算层析术、磁共振成像大气污染对大气质量模型进行模拟研究，控制污染的传播，提示其物理与化学机理蛋白质结构设计使用计算机模拟，对蛋白质组成的三维结构进行研究图像理解实时绘制图像或动画密码破译破译由长位数组成的密码，求找该数的两个乘积因子表1.1美国HPCC计划公布的重大挑战性应用课题一览表HPCC计划所提出的某些重大挑战性课题的计算需求如图1.3所示。它列出了支持科学模拟、先进计算机辅助设计和大型数据库与信息检索操作的实时处理等所需要的处理速度和存储器容量的量级。HPCC计划中的重大挑战课题对计算机提出了3T要求：即1Tflops的计算能力、1TB的主存容量和1TB/s的I/O带宽。在HPCC计划提出的当时，性能最好的计算机与3T要求也相差甚远：速度慢100~1000倍，而存储容量太小，I/O带宽过窄。这就刺激了高性能并行计算机的研制。事隔3年之后，世界上第一台峰值速度超过1Tflops的高性能并行计算机才由Intel公司于1996年12月研制成功。（2）美国ASCI计划：全面禁止核试验条约签订后，核武器的研究代之以实验室数值模拟。因此禁试后数值模拟成了唯一可能进行的全系统（虚拟）试验。这样，1996年6月由美国能源部联合美国三大核武器实验室（LawrenceLivermore国家实验室、LosAlamos国家实验室和Sandia国家实验室）共同提出了“加速战略计算创新”(AcceleratedStrategic全球气候变化系统速度天气预报72小时油藏建模机翼设计物体特性分析年后19951991198019881993存储器容量48结构生物学药物设计化学动力学1000GB100GB10GB1GB100MB10MB小时天气预报100Mflops1Gflops10Gflops100Gflops1Tflops人类基因湍流飞行海洋环流粘滞流体超导建模半导体建模视觉量子染色3维等离子体建模动力学动力学动力学图1.2HPCC方面重大挑战性课题的需求ComputingInitiative，简称为ASCI)项目计划。提出通过数值模拟，评估核武器的性能、安全性、可靠性、更新等。要求数值模拟达到高分辨率、高逼真度、三维、全物理、全系统的规模和能力。该计划被认为是与当年曼哈顿计划等同的一个巨大的挑战，不仅需要科学界的参与，也需要计算机工业界合作，提供保障ASCI应用所需的计算机平台。为此，三大核武器实验室分别向美国三大公司（Intel、IBM和SGI/CRAY）预定了峰值速度超过1Tflops的并行计算机。美国能源部计划在2003年要使用运算速度为100Tflops、内存容量为50TB的并行机（见表1.2）。目前ASCI计划正把各项应用需求与计算平台推进到万亿级规模的体系中去（即每秒可执行万亿次浮点运算、万亿个字节的RAM、数十万亿个字节的磁盘、千万亿个字节的档案存储器、数百亿个字节的网络带宽）。时间（年代）运算时间（OPS）存储容量（TB）海存容量(PB)I/O传输率(GB/s)网络传输率(GB/s)199610110.050.1350.13199710120.51.3501.3200010135135001320031014501305000130表1.2美国ASCI计划中的并行机性能一览表1.6.2商务应用统计数据表明，科学和工程计算方面的应用只占并行机销售市场的少部分，大部分应用却在商业事务处理中。它们在计算能力方面可能不像科学和工程计算要求那么强大，但它们却需求大的存储和磁盘容量以及高的I/O传输率，同时对可靠性、有效性和服务性（即RAS要求）也要求很高。典型的商务应用有数据库管理和查询、在线事务处理、数据仓库、数据开采和决策支持系统等。评价这些应用时，可将计算机系统的速度、容量直接换算成每分钟事务处理数tpm(TransccctionsPerMinute)。TPC(TransactionProcessingPerformanc