《并行处理与体系结构1》

《并行处理与体系结构》计算机学院计算机体系结构教研室嵌入式系统研究中心

张老师引言

SuperComputer超级计算机2011.11.8“天河一号”超级计算机“天河一号”超级计算机“天河一号”计算机排名世界第五天河一号”计算机排名“亚洲第一”基本信息数字1：速度1“天河一号”计算一天１６０年全系统峰值性能为每秒１２０６万亿次实测性能为每秒５６３．１万亿次相当于SPEED基本信息数字2：共享存储总容量1“天河一号”共享存储总容量4个国家图书馆共享存储总容量为１ＰＢ相当于存储容量基本信息数字3：大小与重量119个神舟飞船相当于占地重量…“天河一号”重量基本信息数字4：处理器1“天河一号”处理器处理器包括6144个IntelXeonE5540/E5450处理器5120个AMDRadeonHD4870X2显卡基本信息数字5：互联通信速率1“天河一号”互联结构一条信息高速公路互联通信网络的单根线传输速率为１０Ｇｂｐｓ相当于内部修建Interaction目前国际上最快的速率基本信息数字6：速度1“天河一号”造价“天河一号”目前投资为６亿人民币使用寿命预计为１０年价值MONEY６亿人民币863“高效能计算机及网格服务环境”重大项目“千万亿次高效能计算机系统研制”课题成果国家超级计算天津中心的业务主机，部署于天津市滨海新区中国国家网格计算主结点基本信息结构特点1√√√研制背景6144个通用处理器5120个加速处理器内存总容量98TB√√√天河一号典型系统配置点点通信带宽40Gbps共享磁盘总容量为1PB.√√①计算阵列2560个计算结点；每个计算结点集成2个IntelCPU，配32GB内存；②加速阵列2560个加速结点；每个加速结点含2个AMDGPU、2GB显存；③服务阵列512个服务结点每个服务结点含2个IntelEPCPU、32GB内存④互联通信子系统采用两级InfinibandQDR互联；单个通信链路的通信带宽为40Gbps，延迟1.2微妙；⑤I/O存储子系统采用全局分布共享并行I/O系统结构；磁盘总容量1PB⑥监控子系统采用分布式集中管理结构，实现全系统的实时安全检测、系统控制和调试诊断功能H硬件系统 由计算阵列、加速阵列、服务阵列，以及互联通信子系统、I/o存储子系统和

监控诊断子系统等构成。S软件系统 由操作系统、编译系统、资源管理系统和并行程序开发环境等四部分组成。①操作系统操作系统采用64位Linux；面向高性能并行环境、支持能耗管理、虚拟化和安全隔离等进行了针对性设计。②编译系统支持C、C++、Fortran77/90/95、JAVA语言支持OpenMP、MPI并行编程；提供异构协同编程框架，高效发挥CPU和GPU的协同计算能力；③资源管理提供全系统资源统一视图，实现多策略资源分配与作业调度，有效提高资源利用率和系统吞吐率；④并行程序开发环境并行程序开发环境提供一体化图形用户界面，支持应用程序的调试和性能分析。②操作系统符合B2级安全标准，提供基于隔离的用户安全工作环境，提供统一的全系统资源管理视图、友好的系统管理使用界面、一体化的并行应用集成开发环境和虚拟化的网络计算环境。T技术特点

①“天河一号”的峰值性能可以达到1.206PFlops，LINPACK测试性能563.1TFlops，超过2009年6月TOP500第四位；系统能效为431.7MFlops/W，超过2009年6月

Green500第五位。AT应用领域

“天河一号”可广泛应用于：石油勘探数据处理、生物医药研究、航空航天装备研制、资源勘测和卫星遥感数据处理、金融工程数据分析、气象预报和气候预测、海洋环境数值模拟、短临地震预报、新材料开发和设计、土木工程设计、基础科学理论计算等。“天河一号”的具体硬件配置配置硬件25120个通用处理器5120个加速处理器1024个通用处理器采用两级InfinibandQDR互连全局分布共享并行I/O系统结构分布式集中管理结构天河一号硬件配置配置硬件2配置软件2“天河一号”超级计算机技术关键技术3技术关键技术1/7:多阵列可配置协同并行体系结构31/7:多阵列可配置协同并行体系结构融合了计算阵列、加速阵列和服务阵列，结合资源管理的异构协同技术和编译的混合编程支撑技术，实现资源的动态配置和异构计算能力的协同工作。满足各类应用对计算资源的不同需求。在超大规模高性能计算机体系结构方面有所突破。天河一号具有数据级并行处理能力和指令级并行处理能力等在内的多种计算能力，可针对不同应用的计算需求，通过计算能力的动态组合，实现高效能计算。系统峰值性能1.206万亿次，LINKPACK测试性能560.3万亿次。①高可靠异构计算结点平衡设计技术；②高层任务抽象和管理技术；③多阵列可配置高速互联技术；④动态任务分布和调度技术；⑤全局共享并行I/O技术；⑥动态计算域构建技术；⑦异构协同的资源管理技术。技术关键技术2/7:高速率可扩展互联通信技术32/7：高速率扩展互联通信技术互联通信网络基于高速率InfinibandQDR技术，采用可扩展的互联网络结构和单线速率10Gps,链路带宽40Gbps高带宽互联。突破了高速率与高密度互联网络的关键技术，提高了系统效率，简化系统维护。统一实现了计算处理、I/O存储、系统管理等不同类型任务的同步与通信，系统管理与维护简洁，取得了40Gbps通信带宽，1.2us延迟的高效通信性能。②用户级低延迟通信协议；③链路自检测和自管理；④单线速率10Gbps的互联；⑤高吞吐高密度背板互联结构⑥光电混合传输。①高带宽可扩展互联网络技术；高效发挥CPU与GPU的协同计算能力，把GPU的计算效率从优化前的20%提高到70%。技术关键技术3/7:高效异构协同计算技术33/7:高效异构协同计算技术使用CPU+GPU的体系结构，GPU扮演加速器的作用，它加快了计算机的运行速度，却降低了功耗和成本。针对多阵列可配置协同并行体系结构中的异构混合计算资源，采用混合语言编程技术，突破了传统混合计算模式效率低的问题，为提高系统的整体性能起到关键作用。①自使用动态任务划分，自动平衡CPU和GPU的工作负载；②流式数据存储，减少GPU数据传输对CPU计算的干扰；③软件流水，重叠GPU计算与主存和GPU之间的数据传输；④亲和调度，优化计算结点间的进程调度和计算结点内的线程调度，减少数据、指令迁移和通信开销；⑤多层缓冲区双向异步数据传输，通过PCI-E数据缓冲区优化CPU与GPU之间的数据传输，减少带宽压力；⑥高级循环优化，通过编译器自动进行数据交换、循环变换和循环分块，增大⑦OpenMP与MPI混合并行支持，针对并行粒度的不同分别进行优化。Cache重用，改善多线程运行时的带宽受限问题；技术关键技术4/7:基于隔离的安全控制技术34/7:基于隔离的安全控制技术面向虚拟域的作用管理服务结点虚拟计算域计算结点高性能计算域安全控制系统的结构图资源管理分配模块环境监测设置模块虚拟计算域管理工具包面向虚拟域的服务质量保证模块虚拟计算域构建模块防止客体重用模块面向任务的服务质量保证模块高性能计算域构建模块针对超级计算中心的高信息安全需求，系统创新地采用了基于隔离的安全控制技术，在不增加系统开销的前提下，有效提高了用户运行信息和数据的安全性。充分发挥了系统的各项性能，在保证系统数据、用户数据安全的前提下，最大限度地提升了系统的服务能力，为每个用户提供了安全、高效、灵活、符合用户习惯的计算环境。①低开销的用户容器技术；②高效的虚拟文件系统隔离技术；③定制的用户运行环境技术；④灵活安全的文件穿透访问技术；⑤细粒度的高效资源和服务质量保证技术；⑥相互隔离的用户独立工作环境构建技术；⑦高效、简便的用户定制环境管理技术；⑧快速模板构建技术。技术关键技术5/7:虚拟化的网络计算支撑技术35/7:虚拟化的网络计算支撑技术针对网络化计算需求，通过高性能虚拟域技术，支持根据用户需求动态构造虚拟化的用户运行环境，并结合远程虚拟终端技术，屏蔽系统细节，高效支撑网络化使用和云计算。虚拟化网络计算支撑技术有效屏蔽了系统细节，简化了用户使用，提高应用开发效率，提供了有别于传统高性能计算机的使用方式，可以进一步扩展并满足未来云计算的需求。①面向对象的组件化系统结构；②动态服务发现技术；③友好的人机界面设计技术；④一体化图形集成开发框架；⑤高效能、低开销的虚拟域技术；⑥用户环境的动态构建迁移技术；⑦系统资源远程探测技术。技术关键技术6/7:多层次的大规模系统容错技术36/7:多层次的大规模系统容错技术多层次容错框架自动作业容错流程作业进程检查点库并行存储系统容错并行算法与断点续传应用程序检查点管理与与作业自动恢复资源管理并行任务协同通道重建MPI运行库用户透明的进程检查点技术OS内核用户界面统筹作业管理检查点插件故障检测模块资源管理系统采用多层容错技术，通过操作系统级的检查点功能、资源管理级的任务和作业的自动容错技术，以及并行应用级的容错并行算法和断点续传功能，有效提高了系统的可靠性。缓解了大规模系统固有可靠性低对用户应用运行的影响，使用户作业的运行成功率得到很大提高，提升了系统可用性与吞吐率。①操作系统内核实现用户透明的进程检查点支持；②MPI运行库进行并行任务检查点的协同与通信通道重建；③资源管理提供作业检查点的管理与自动故障恢复；④应用容错并行算法和断点续传；⑤资源管理控制进程的双机备份技术；⑥并行存储的Failover技术；技术关键技术7/7:系统能耗综合控制技术37/7:系统能耗综合控制技术操作系统、资源管理系统和编译系统相结合，通过系统动态重构技术，结点ACP能耗状态动态管理技术和动态调频技术，根据用户资源需求和系统工作状态，动态调整系统资源配置，调节结点功耗状态和CPU、GPU、内存的工作频率，实现最佳的系统能效，并有效提高系统的可靠性。通过一体化的能耗控制技术，使系统的空闲结点能耗降低比例大于80%；并行计算系统综合能耗降低比例大于20%；能耗管理系统对应用运行时间影响低于5%。

①应用能耗特征识别；②基于PMU事件和QoS的能耗状态监控；③能耗感知的资源分配；④能耗感知的作业调度；⑤能耗感知的分布式设备状态管理；⑥面向能效优化的编译。用数值方法预报台风应用典型应用1/N:用数值方法预报台风4通过天河一号辅助设计飞机气动外形应用典型应用2/N:辅助设计飞机气动外形4美洲豹（2009年的世界第一名美国“美洲豹”

）

同比超级计算机排名1/5:美洲豹5“走鹃”（2008年排名世界第一的美国“走鹃”超级计算机）同比超级计算机排名2/5走鹊5“走鹃”（2008年排名世界第一的美国“走鹃”超级计算机）“海妖”超级计算机同比超级计算机排名3/5海妖5“尤金”同比超级计算机排名4/5尤金52004年-2007年，美国“蓝色基因”曾多年雄踞世界第一位，速度为500万亿次，但耗电量高达6兆瓦“天河一号”同比超级计算机排名5/5天河一号5国家超级计算天津中心大楼落户国家超级计算天津中心天津滨海新区5争锋“超越只是一瞬间”不进则退92011年6月20日，国际TOP500组织对外公布了世界超级计算机最新排行榜：日本“京”超级计算机超越了我国“天河一号”，排名世界第一。日本理化学研究所20日宣布，与富士通共同研发中的超级计算机“京”以每秒8612万亿次的运算速度在最新全球超级计算机500强排名中位列第一。争锋“超越只是一瞬间”不进则退9今年，日本超级计算机“京”夺走Top500榜首之位，中国的“天河一号”仅保持半年的优势争锋“超越只是一瞬间”不进则退9日本超级计算机“京”单机柜图（2004年-2007年，美国“蓝色基因”曾多年雄踞世界第一位，速度为500万亿次，但耗电量高达6兆瓦）美国“蓝色基因”单机柜图中国超级计算机发展年谱节点机采用了曙光自主研发的TC3600刀片服务器，应用了大规模系统管理和调度系统、高性能计算机安全系统等自主技术，具有“四高二低”技术亮点，即高性能、高效能、高可靠、高密度、低功耗、低成本。简单来说，星云”的优势在于采用了我国自主研发的模块化服务器，能够按计算需求自行选择主要计算组件，同时它在每个节点容纳了10块GPU计算卡，因而在较重要的节点通过互相比对的计算模式，保证了数据的可靠性。骄傲“星云”超级计算机世界No.32010年6月1日，曙光公司在京宣布：我国首台达到每秒3000万亿次峰值运算速度的超级计算机“星云”，近日由中科院计算所、曙光公司、国家超算深圳中心共同研制成功。其实测性能超过每秒1271万亿次，在5月31日德国发布的第35届全球超级计算机前500强(TOP500)排行榜上居第二位（现在位居第三）

，创造了中国高性能计算的最高性能。国家超级计算天津中心招聘启事科研人员在对“天河一号”超级计算机进行系统性能测试国家超级计算天津中心大楼国家超级计算天津中心（NSCC-TJ）是由国家科技部、天津市和国防科学技术大学三方共同建设的国家级超级计算中心。中心采用我国首台千万亿次计算机“天河一号”作为业务主计算机，是我国第一个具有千万亿次计算能力的超级计算中心，也是世界上少数几个具有千万亿次计算机的超级计算机。中心立足天津，面向全国，以应用需求为牵引，按照“高科技公共服务、信息产业发展、信息专业人才聚集培养”三位一体的思路开展建设和进行运营，为提高国家科技创新能力和促进产业技术创新提供高性能计算服务。因中心工作需要，在全国范围内招聘如下职位：并行程序设计与开发工程师1、计算机及相关专业硕士，熟悉并行算法设计，精通MPI、OpenMP、CUDA等编程；2、熟悉linux/windows系统下的C/C++、Fortran编程，熟悉gnu、intel等编译器；3、2年以上软件开发经历或分布计算、并行计算相关经历优先；4、熟悉GPU、FPGA、DSP等优先；5、英语良好，有较强的沟通能力和团队合作精神。争锋中国全国产化的超级计算机“神威蓝光”问世《2011年中国高性能计算机TOP100排行榜》中，排名第二的神威蓝光(SunwayBlueLightMPP)2011年10月27日消息，2011年全国高性能计算学术年会(HPCChina2011)于10月26至29日在山东济南山东大厦召开申威1600微处理器“神威蓝光”超级计算机争锋中国全国产化的超级计算机“神威蓝光”问世“神威蓝光”超级计算机（争锋中国全国产化的超级计算机“神威蓝光”问世“神威蓝光”超级计算机申威1600微处理器及电路板等争锋中国全国产化的超级计算机“神威蓝光”问世全部采用自主设计生产的CPU(ShenWeiprocessorSW1600)，系统共8704个CPU

峰值1.07016PFlops，持续性能795.9TFlops

Linpack效率74.37%，总功耗1074KW

由山东省科学院计算中心负责建设、管理和运营《2011年中国高性能计算机TOP100排行榜》中，排名第二的神威蓝光(SunwayBlueLightMPP)该机器获得科技部863计划支持，由国家并行计算机工程技术研究中心制造，于2011年9月安装于国家超算济南中心

《并行处理与体系结构》并行主要研究先行方式、流水方式、向量化并发性、同时性数据并行性、划分交叉、重叠、多重性、重复时间共享、空间共享多任务处理、多道程序、多线程方式和分布式计算本章内容学习目标1.1计算技术的现状1.2多处理机和多计算机1.3多向量机和SIMD计算机第1章并行计算机模型掌握基本概念1.4并行计算机的抽象模型1.5可扩展的范围和设计

1计算技术的现状一、并行技术的出现二、现代并行计算机的组成涉及6个问题：1.计算问题现实生活中对问题要求快速而精确地求解推动了计算机的广泛使用。科学技术中的数值计算问题人工智能(AI)问题事务处理2.算法和数据结构并行计算问题中的运算和通信，需要各种专门的算法和数据结构。符号处理科学计算存在的问题3.硬件资源处理机、存储器和外围设备组成了计算机系统的硬件核心外围设备可以直接或通过局域网和广域网与主机相连Transaction4.操作系统管理用户程序执行过程中的资源分配和再分配映射是一种算法结构与硬件结构相匹配的双向过程。并行操作系统的映射算法和数据结构到机器结构的映射包括处理机调度、存储器映象、处理器间的通信等。这些问题通常都与系统结构有关。5.系统软件支持存在的问题：不能以通用和可移植方式进行并行程序设计开发并行编程环境：一种与系统结构无关的语言、编译器和软件工具。两个方向：对于开发并行语言:将着眼点放在语言执行的效率、对不同机器的可移植性、与现有的顺序语言的兼容性、并行性的表达和编程的简便性等上面。可以设计一种新的语言，逐步扩展现有的顺序语言。新语言有用显式高级结构描述并行性的优点，但是新语言往往与现有语言不兼容，而需要新的编译器或者通过新的步骤才能利用现有的编译器。大部分系统选用的是语言扩展方式。6.编译器支持改进编译器有三种途径：预处理程序预编译器并行化编译器预处理程序采用顺序编译器和目标计算机的低层程序库实现高级并行结构。预编译器需要程序流分析、相关性检查和有限的优化来检测并行性。联接过程的效果取决于预处理程序、预编译器、并行化编译器、加载程序和操作系统支持的功效。由于程序行为的不可预测，现有的编译器在检测所有类型的并行性时都不是完全自动或完全智能进行的。存在一些有效的方法：7.并行程序的设计环境隐式并行性显式并行性伊利诺依大学的DavidKuck和Rice大学的KenKennedy以及他们的合作者都已采用这种隐式并行性方法。加州理工学院的CharlesSeitz和麻省理工学院的WilliamDaily在开发多计算机时采用了这种显式方法弱强将编译器命令插入源代码，帮助编译器做出较好的结果。这样，用户可与编译器进行交互重构，这已被证明对提高并行计算机性能是十分有用的。总结要使一个环境对用户更加友好，必须要有专用软件工具一些工具是传统高级语言的并行扩展一些则是集成环境其中包括提供不同级别的程序抽象、验证、测试、查错和调试等各种工具；性能预测和监控；辅助程序开发的可视化支持、性能测量以及计算结果的图形显示及动画表示三、计算机系统结构向高性能发展历程主要探讨顺序到并行的过程SP集成传统工作环境+性能监控分析与预测+可视化技术超标量技术微型机采用的技术1.先行、并行性和流水线技术用先行技术预取指令可使I／E(指令读取／译码和执行)支持功能并行性的方法有两种①一种是同时使用多个功能部件②另一种是在不同处理级分别实施流水线技术流水线指令执行、流水线算术计算和存储器存取操作。2.Flynn分类法MkhealFlynn(1972)根据指令和数据流概念提出了不同计算机系统结构的分类法。1234多数据流(MD)一定是多个执行部件多指令流(MI)一定是多个控制部件单指令流(SI)一定是单个控制部件C-->P-->M传统的顺序机被称为SISD(单指令流单数据流)计算机。向量计算机--标量和向量硬件装备，或以SIMD(单指令流多数据流)机的形式出现。并行计算机则属MIMD(多指令流多数据流)机MISD(多指令流单数据流)机在执行不同的指令流时，同一数据流通过处理机线性阵列。这种系统结构也就是所谓流水线执行特定算法的脉动阵列(Systolicarrays)。由卡内基—梅隆大学的美籍华人学者H．T．Kung于1978年提出的。这一结构是随着VLSI技术的发展和各种大运算量的信号/图象处理及科学计算的运算要求而建立起来的MPMD：控制并行程序（待续）SPMD：数据并行程序（待续）共享存储型多处理机（待续）消息传递型多计算机（待续）图示含义这是一类为实现确定算法而设计的多维流水线阵列结构；如上图所示就是为完成矩阵--矩阵相乘而专门设计的搏动式阵列。此例的内部结点度为6。静态搏动式阵列可在多个方向上使数据流变成以流水线方式工作；商用IntelWarp系统(Anaratone等，1986)就是用搏动式结构设计而成的。自从1978年Kung和Leiserson提出搏动式阵列后，它已成为广泛研究的领域。多方向性处理单元简单;含义流水；算法专业。3.并行／向量计算机真正的并行计算机是那些以MIMD模式执行程序的计算机。并行计算机有两大类，即共享存储型多处理机和消息传递型多计算机。多处理机和多计算机之间的主要差别就在于存储器共享和处理机间通信机制的不同。多处理机系统中的处理机通过公用存储器的共享变量实现互相通信。多计算机系统的每个计算机结点有一个与其它结点不共享的本地存储器。处理机之间的通信通过结点间的消息传递来实现。显式向量计算机指令是随向量处理机的问世而出现的一台向量处理机可以装备有用硬件或固件并发控制的多条向量流水线4.开发层次LionelNi的最新分类法(1990)，并行计算机的分层开发可表示于下图2.性能因子设Ic为已知程序的指令条数。执行程序所需的CPU时间(T，以秒/程序表示)可用三个主要因素的乘积来计算：四、性能的系统属性1

.时钟频率和CPI主频当前数字计算机的CPU(或简称处理机)是由一个恒定周期(τ，以ns表示)的时钟驱动的。周期的倒数是时钟频率:(ｆ＝1/

τ）（以MHz表示）程序的规模是由其指令数(Ic)，也就是程序串要执行的机器指令数来决定的。执行不同的机器指令所需要的时钟周期数也是不一样的。一条指令的周期数(CPl)就成为衡量执行每条指令所需时间的重要参数T＝Ic

×CPI×τ可将上式重写成如下形式：T＝Ic

×(p+m×k)×τ

一种指令类型的CPI可分为完成指令所需的处理机周期数和存储器周期数两部分。完整的指令执行过程可能包含一至四次存储器访问(一次用于取指令，两次用于取操作数，一次用于存储结果)，这与指令的类型有关p为指令译码和执行所需的处理机周期数m为所需的存储器访问次数k为存储周期与处理机周期之比Ic为指令条数因为存储周期很大于处理机周期3.系统属性计算机系统属性可以由五元组表示：(Ic，p，m，k，τ)T＝Ic×(p+m×k)×τ五个量可以称为性能因子与四种系统属性有关：指令系统结构、编译技术、CPU实现和控制技术、高速缓存与存储器层次结构。X表示”有关”机器规模n—处理机个数时钟速率f工作负载W--程序中的计算操作数顺序执行时间T1并行执行时间Tn速度Pn=W/Tn加速比Sn=T1/Tn效率En=Sn/n

利用率Un=Pn/n(Ppeak)启动时间t0

渐进带宽r∞处理器的峰值速度推广并行系统的性能属性P11分母与分子上下同除以CPU时钟周期：τCPI=——————CICC是执行Ic条执行所用总的处理机周期C=—————————TCPU时钟周期：τT是总的执行时间，以CPU时钟周期为单位的4.Mips速率(其中C是总的周期数)5.吞吐率系统在单位时间内能执行多少个程序，这称为系统的吞吐率(单位为程序数／秒)Ws在多道程序系统中，系统吞吐率常低于CPU吞吐率Wp。Wp可用下式表示：CPI:每指令执行所需周期数

f是“频率”：1s钟内有多个处理机周期或：

Wp=(MIPS)×106／Ic

Wp的单位是程序数／秒。程序的指令条数(Ic)每秒钟执行的指令条数5.吞吐率CPU吞吐率是根据MIPS速率和程序的平均长度(Ic)来衡量机器每秒钟能执行多少个程序的尺度。Ws<Wp用多道程序或分时操作在CPU上交叉执行多个程序时，I／O、编译器和操作系统产生的额外系统开销所造成的。

2多处理机和多计算机一、共享存储型多处理机1.UMA模型UMA--UniformMemoryAccess含义均匀存储器访问/集中式存储器访问结构和特点紧耦合系统(tightlycoupledsystem)多处理机由于高度资源共享系统的互连采用总线、交叉开关、或多级网络形式对称(symmetric)多处理机当所有处理机都能同样访问所有外围设备时。SMP在UMA结构中，所有存储单元与任何处理器之间都是等距的，所以所有的存储器访问操作需要基本一致的时间。分类UMASMP:对称(symmetric)多处理机PVP:并行向量处理器（parallelvectorprocessor）在此，可不叫做“本地共享存储器”举例Fortran程序可在单处理机上顺序执行，分析CPU的运行时间，假设条件：所有数组A(I)，B(I)，C(I)都有N个元素；分析：求和Fortran程序L1:Do10I＝1，NL2:A(I)＝B(I)+C(I)L3:10ContinueL4:SUM＝0L5:Do20J＝1，NL6:SUM＝SUM+A(J)L7:20Continue假定取指令和加载数据的开销可以忽略不计；所有数组已经装入主存储器，并且短程序段已经装入高速缓冲存储器。忽略总线争用或存储器存取冲突问题。执行代码行L2，L4和L6，每行要用一个机器周期。执行程序控制语句L1，L3，L5和L7所需的时间可以忽略。应该是2N+1个周期（代码L4也需要一个周期）CPU用________个周期2N+1串行程序并行化:在M—处理机系统上执行程序将循环操作划分成M段，每段有L＝N／M个元素。假设经过共享存储器的处理机之间的每次通信操作需要：k个周期Doallk＝1，MDo10I＝L(k-1)+1，kL。

A(I)＝B(I)+C(I)10ContinueSUM(k)＝0Do20J＝1，LSUM(k)=SUM(k)+A(L(k-1)+J)20ContinueENDall结论Doall表示所有M段在M台处理机上并行执行分析循环1是L个周期；循环2是L个周期总时间：_____________________________需要通信h次数;h=log2Ma0a1a2a3a4a5a6a7+++++++递归折迭操作2L+h(k+1)=2N/M+log2M(k+1)123122.NUMA模型全局NUMA模型特点共享存储器物理上分布在各个处理机的本地存储器上，全部本地存储器组成了全局地址空间,可被所有处理机访问。处理机访问共享存储器的时间非均匀性共享存储器(SM)不一定就是UMA,也可以是NUMA，无必然联系!高度注意概念3.COMA模型只使用高速缓存的多处理机（cache-onlymemoryarchitecture）

只有高速缓存的多处理机全局瑞典计算机科学研究所的数据扩散机(DDM，Hagersten等，1990)KendallSquareReserch公司的KSR—1机器(Burkhart等，1992)。实现的机器特点COMA模型是NUMA机的一种特例，将NUMA中分布主存储器换成了高速缓存；全部高速缓冲存储器组成了全局地址空间；远程高速缓存访问则借助于分布高速缓存目录进行，分级目录往往可用来寻找高速缓存块的副本，这与所用的互连网络有关；数据的初始位置并不重要，因为它最终将会迁移到要用到它的地方。例如，高速缓存一致性非均匀存储存取(CC—NUMA)模型。可以用分布共享存储器和高速缓存目录来描述。CC—NUMA模型的实例模型的演变斯坦福大学的Dash系统(Lenosh等，1990)和麻省理工学院的Alewife系统(Agarwal等，1990)4.典型的多处理机二、分布存储型多计算机系统概念由多个计算机结点，通过消息传递网络互相连接而成，每个结点是一台由处理机、本地存储器和有时接有磁盘或I／0外围设备组成的自治的计算机。消息传递网络提供结点之间的点到点静态连接传统的多计算机已被称为近地存储访问机(NORMA)私用存储器逐渐在分布共享存储器的多计算机中将被逐步取消。特点√√√本节共享存储型多处理机系统分布存储型多计算机系统软件实现的DSM:为了在NORMA和NCC-NUMA上实现共享存储器技术，研究人员提出了软件一致性模型NUMA存储器模型，也称为分布式共享存储器模型（DSM）UMANUMACOMANORMA第五章P156关联与比较NORMA；近地存储访问机，所有本地存储器是私用的，而且只有本地处理机才能访问。所有本地存储器是私用的，而且只有本地处理机才能访问；DSM:分布存储器模型（distributedshared-memory）CC-NUMANCC-NUMA3.多计算机的换代现代多计算机用硬件寻径器来传送信息；计算机结点与寻径器相连，边界上的寻径器与I／O和外围设备连接；任何两结点间的消息传递会涉及一连串的寻径器和通道。在异构多计算机系统中，可以有多种类型的结点，结点间的通信是通过可兼容的数据表示和消息传递协议来实现的。加州理工学院的Cosmic和InteliPSC／1是这一代研制的代表IntelParagon和ParsysSuperNodel000可作为代表性产品消息传递型多计算机的发展换代第一代(1983—1987)是基于处理机板技术，采用了超立方体结构和软件控制的消息交换方法。第二代(1988—1992)是用网格连接的系统结构、硬件消息寻径和中粒度分布计算的软件环境实现的；现在面临的第三代(1993—)预期是细粒度计算机麻省理工学院的J-Machine和加州工学院的Mosaic，VLSI片上实现处理机和通讯工具。示例IBMPOWER4体系结构特点PowerPC64位体系结构单芯片双处理器，MCM八处理器集成多处理器互连接口集成I/O控制器集成L3Cache控制器集成存储控制器IBMPOWER4(MCM结构)八处理器IBMPOWER4(32CPU)88884.典型多计算机多计算机的可编程性取决于:高效编译器实用高效的分布式操作系统实用多计算机需要分布式操作系统!三.多处理机和多计算机之间的主要差别在于存储器共享和处理机间通信机制的不同。多处理机系统中的处理机通过公用存储器的共享变量实现互相通信。多计算机系统的每个计算机结点有一个与其它结点不共享的本地存储器。处理机之间的通信通过结点间的消息传递来实现。多处理机系统多计算机系统共享变量消息传递

3多向量机和SIMD计算机一、向量超级计算机1.早期的超级计算机可分为：流水线向量机SIMD计算机强调开发大规模数据并行性用带有少量带有向量硬件，但性能很高的处理机来装备.向量功能流水线向量数据流向量处理机：专门设计用来完成向量运算的协处理机，是执行向量操作的硬件资源，包括向量寄存器、流水线功能部件、处理部件和寄存器计数器。执行过程：当译出的指令为向量操作；①它将被送至向量控制器，控制器将监督主存储器与向量功能流水线之间的向量数据流，向量数据流由控制器协调控制；②向量处理机则装有若干条向量功能流水线。理解“向量运算”流水线向量处理机有两种类型：寄存器—寄存器结构存储器—存储器结构2.寄存器—寄存器的系统结构如1976年推出的Cray1向量寄存器用来保存向量操作数、中间和最终的向量结果;向量功能流水线从向量寄存器检索操作数，并将结果放入寄存器。说明利用向量寄存器作为存储器与功能流水线之间的接口重要特点

3.存储器—存储器结构这种结构比较早，与寄存器—寄存器结构的区别就在于采用向量流水部件代替了向量寄存器。将向量操作流直接从存储器取至流水线，然后再送回存储器.重要特点

可见:虽然起始模块不定,但向量依起始模块连续存放二、SIMD超级计算机特点一个控制部件;多个功能部件1.SIMD的操作模型可用五元组表示M＝<N，C，I，M，R>N为机器的处理单元(PE)数例如：SIMD机器MasParMP—1是一种SIMD机器，其PE数N＝1024至16384。PE数目与机器配置有关。C为由控制部件(CU)直接执行的指令集包括标量和程序流控制指令例如：MasParMP—1CU执行标量指令，将译码后的向量指令播送到PE阵列，并控制PE间的通信。大1.SIMD的操作模型可用五元组表示M＝<N，C，I，M，R>I为由CU广播至所有PE进行并行执行的指令集；它包括算术运算、逻辑运算、数据寻径、屏蔽以及其它由每个活动的PE对它的数据所执行的局部操作。例如：MasParMP—1每个PE都是基于寄存器的加载／存储RISC处理机，能执行不同数据量的整数运算和标准浮点运算。各PE从CU接受指令。小1.SIMD的操作模型可用五元组表示M＝<N，C，I，M，R>M为屏蔽方案集其中每种屏蔽将PE集划分为允许操作和禁止操作两种子集。例如：MasParMP—1屏蔽方案设在每个PE中，并由CU连续监控，它能在运行时动态地使每个PE处于置位或复位状态。精髓:由CU进行动态”编程”!1.SIMD的操作模型可用五元组表示M＝<N，C，I，M，R>R是数据寻径功能集说明互连网络中PE间通信所需要的各种设置模式。例如：MasParMP—1MP—1有一个X—Net网格网络和一个全局多级交叉开关寻径器，以实现CU—PE之间、X—Net的8个近邻之间和全局寻径器的通信。2.SIMD的实施模型（1）分布式存储器模型(DSM)（同一）阵列控制部件1.N（PE个数）向量操作2.CU3.I(PE并行执行的指令)程序和数据通过主机装入控制存储器控制部件通过执行程序来控制数据寻径网络存储器分布的SIMD特点SIMD计算机开发的是PE之间的空间并行性存储器分布的SIMD计算机由同一阵列控制部件控制的PE阵列组成程序和数据通过主机装入控制存储器指令是送到控制部件进行译码标量操作或控制操作，则将直接由与控制部件相连的标量处理机执行向量操作，则将它广播到所有PE并行地执行划分后的数据集合通过向量数据总线广播到所有PE的本地存储器PE通过数据寻径网络互连。数据寻径网络执行PE间的通信，如移数、置换和其它寻径操作。控制部件通过执行程序来控制数据寻径网络。PE的同步由控制部件的硬件实现所有PE在同一个周期执行同一条指令可以用屏蔽逻辑来决定任何一个PE在给定的指令周期执行或不执行指令√√√√√√√√12345678（2）

共享存储器模型是一种PE使用共享存储器的SIMD计算机。PE和存储器之间的通信网络是一个对准网络，它也受控制部件控制。总线型对等网络示意图星型对等网络示意图对等型网络是指在网络中不需要专门的服务器，网络中的各工作站之间是平等的关系，每台接入网络的计算机既可以是服务器，也可以是工作站。在工作过程中，既共享其他计算机上的资源，又要为其他计算机提供共享资源。在其他计算机访问其共享资源时，可将其视为服务器，在其访问其他计算机时又可将其视为工作站。在对等型网络中又有总线型对等网络和星型对等型网络之分。对等网络（PeertoPeer，简称P2P）也称为对等连接，是一种新的通信模式，每个参与者具有同等的能力，可以发起一个通信会话。

4并行计算机的抽象模型并行计算机的理论模型是从物理模型抽象的；为开发并行算法提供了一种方便的框架；用这些模型可求得并行计算机的理论性能界限；可在芯片制作前估算芯片区的VLSI复杂性和执行时间。一、时间与空间复杂性执行时间存储空间计算机求解一个规模为s的问题的算法复杂性取决于：时间复杂性时间复杂性g(s)为O(f(s))，可读作“数量级为f(s)”，如存在正的常量c和s0，则对所有s>s0的非负值就有g(s)≤cf(s)

。空间复杂性为问题规模s的函数。渐近空间复杂性(asymptoticspacecom—plexity)主要与大问题的数据存储有关，而程序(代码)存储的需求和输入数据的存储不考虑在内。串行算法的时间复杂性简称为串行复杂性;并行算法的时间复杂性就称为并行复杂性;并行复杂性应比串行复杂性低，至少是相近。常识只考虑确定性算法P类(即多项式类)具有多项式复杂性算法的问题集，如果存在一多项式p(s)，对任何问题规模s的时间复杂性为O(p(s))，则某算法即具有多项式复杂性。NP类(即不确定性多项式类)不能以多项式实现，用不确定性算法求解的问题集。P

NP确定性算法是不确定算法的特殊情况。P类问题是计算易解的，而NP-P类问题是难解的。现在不知道是否P＝NP或P≠NP难解的NP类问题又称为具有指数时间复杂性的问题。√√√√例题多项式复杂性和指数复杂性算法：将几个数排序的多项式时间复杂性分别为_________，属于P类对两个n×n矩阵相乘算法的多项式时间复杂性分别为_________

，属于P类。旅行推销员问题复杂性为_________指数复杂性问题是属_________的：到目前为止还未发现这类问题的确定性多项式算法。背包问题的复杂性为_________P、NP和NPC（NP完全问题）可见，P是NP的一种O(nlogn)O(n3)O(n22n)O(2n/2)NP类二、并行随机存取机模型(ParallelRandom—AccessMachine，PRAM)可用来开发并行算法和分析可扩展性及复杂性。MIMD细粒度严格同步零开销共享变量在PRAM上的一个并行程序由n个进程组成，其中第i个进程留驻在第i个处理器上，且由一串指令所组成。在每个基本时间步(称为周期)，每个处理器执行一条指令。这些指令包括数据传送、算/逻、控制流以及I/O指令，在典型的顺序计算机中均有这些指令。说明1.同构性规模为1的PRAM退化为传统的RAM。这种机器为SISD。当处理器多于1个时，一个PRAM将访问多个数据流，且通常可执行多个指令流。因此PRAM是一个MIMD机器。并行计算机则属MIMD(多指令流多数据流)机说明在那里程序执行单一指令流且访问单一数据流。这种机器被称为“单指令（流）、单数据（流）机（SISD）”，它能模型化普通的顺序计算机。MIMD的特例:如果在每一周期，所有处理器必须执行相同指令，即只有一个指令流时，则PRAM就成为单指令(流)、多数据(流)(SIMD)机器。(SPMD)计算：单程序多数据，所有进程执行同一程序，而由进程指标加以参数化。SIMD和SPMD间的差别是，在SPMD计算中，同一周期可以执行不同指令。2.同步性进程同步是严格的。PRAM是在指令级同步的。SIMD是指令级别同步的MIMD并行机则是异步的,每个进程按照自己速率执行，与其他进程的执行速度无关。3.交互机制这一属性描述了并行进程间如何相互影响行为的特性;在PRAM模型中，进程间通过共享变量(或共享存储器)进行交互。4.地址空间PRAM模型所有进程对所有存储单元均有相等的访问时间--均匀存储器访问(UMA)模型。针对多计算机不合适在多计算机中，每个处理机有它自己的分离地址空间。这些机器被称为具有多地址空间。多计算机的处理机间通信不是通过共享变量，而是借助消息传递。√5.存储器模型各种方案的主要区别在于如何协调RW的冲突。四种PRAM模型方案都与存储器读写如何处理有关。(1)EREW-PRAM模型——这种模型禁止一台以上处理机同时读、写同一存储单元.

这是限制最大的PRAM模型。(2)CREW-PRAM模型——用互斥使写冲突避免。可以并行读同一存储单元。(3)ERCW-PRAM模型——允许互斥读或并行写同一存储单元。(4)CRCW-PRAM模型——允许在同一时刻并行读或者并行写。写冲突可用下述四种策略之一分解：①共用——所有同时进行的写操作将相同数据存入热点存储单元②任选——将任何一个要写的数保存起来，而其它的忽略不计③最小值——将处理机要写的下标值最小的数保存起来④优先——对要写的数用求和或求最大值等联想函数加以组合严松6.原子操作原子操作的定义：一个原子操作是指有如下特性的一种操作。不可分有限更严格的原子操作定义：需要满足以下的4个性质。称这样的原子操作为一个事务操作。

原子性一致性隔离性持续性要么执行事务操作的所有子操作，要么不执行任何子操作一个事务操作总是将一个程序由一个一致性状态转换成另一个一致性状态在一个事务操作完成之前，该事务操作的效果（结果）不会对其他事务操作产生影响一旦完成，当系统失败时，事务操作的效果仍会持续原一隔持例题PRAM步中的计算复杂性：假设有三个PRAM算法A，B和C，当在一个有n个处理器的PRAM计算机上执行时，各自的时间复杂性为:A--7nB--(nlogn)／4C--nloglogn根据大O标志：算法A最快：(O(n))，C次之：O(nloglogn)，B为最慢：O(nlogn)。而实际上，假设当机器的处理器数等于1024时：A=7X1024=7168B=1024X10/4=2558C=1024log210>3076结论：算法B最快，其次是C，而A则是最慢的。PRAM与物理模型的差异实际上，这种并行计算机是不存在的。共享存储器SIMD机是与PRAM模型最接近的结构。更确切地说，以共享存储的同步MIMD模式运行。四种PRAM方案中，EREW和CRCW是应用最普遍的模型每个CRCW算法可用一个EREW算法来模拟CRCW算法比一个等效的EREW要快，经证明，最好的n—处理机EREW算法要比任一个n-处理机CRCW算法慢O(logn)倍对研究结构规则的并行性来说，用PRAM比用实际机器模型要好得多PRAM能指出实际并行计算机性能的上限研究PRAM模型目的三、异步PRAM模型—APRAM是一个异步的PRAM模型，简记为APRAM1.模型特点由p个处理器组成每个处理器都有其本地存储器、局部时钟和局部程序处理器间的通信经过共享全局存储器无全局时钟各处理器异步地独立执行各自的指令处理器任何时间依赖关系需明确地在各处理器的程序中加入同步(路)障(SynchronizationBarrier)一条指令可在非确定但有限的时间内完成√√√√√√2、APRAM模型中的指令类型有四类指令①全局读将全局存储单元中的内容读入局存单元中②局部操作对局存中的数执行操作，其结果存入局存中③全局写将局存单元中的内容写入全局存储单元中④同步同步是计算中的一个逻辑点，在该点各处理器均需等待别的处理器到达后，才能执行其局部程序3.APRAM模型中完成的计算计算是由一系列用同步障分开的全局相所组成在各全局相内，每个处理器异步地运行其局部程序每个局部程序中的最后一条指令是一条同步障指令各处理器均可异步地读取和写入全局存储器在同一相内不允许两个处理器访问同一单元不同的处理器访问存储单元总是由一同步障所分开，所以指令完成时间上的差异并不影响整个计算。√√√同步障指令局部程序…同步障指令局部程序…同步障指令局部程序…同步障指令局部程序…P1P2……4.APRAM模型中的时间计算使用APRAM模型计算算法的时间复杂度时，假定局部操作取单位时间全局读／写时间为d它定量化了通信延迟，代表读/写全局存储器的平均时间，d随机器中的处理器增加而增加同步障的时间为B它是处理器数P的非降函数B=B(P)在APRAM中假定上述参数服从如下关系：2≤d≤B≤P同时：B(P)∈O(dlogP)或B(P)∈O(dlogP/logd)令tph为全局相内各处理器指令执行时间中最长者，则整个程序运行时间T为各相的时间之和加上B乘以同步障次数，即:T=∑tph+B×同步障次数√√√四.BSP模型BSP-BulkSynchronizationParallel1.BSP模型的提出哈佛大学的LeslieValiant提出：块同步并行(BSP)，用以克服PRAM模型的缺点，但保留其简单性。一个BSP计算机由n个结点(处理器和存储器对)所组成。2.特点一个BSP程序有n个进程，每个驻留在一个结点上。基本时间单位是周期(或时间步)程序按严格的超步序列执行同步路障迫使进程等待BSP计算机是MIMD系统BSP模型是超步级的松同步在一个超步中，不同进程以不同速率异步执行BSP模型交互机制是共享变量或是消息传递3.h关系的定义一个h关系是任何通信操作的抽象，在其中，每个结点最多发出h个字到各结点，并且每个结点最多接收h个字在一个BSP计算机中，实现任何h关系的时间不会超过gh个周期(g是由机器平台决定的一个常数)超步程序…4.一个超步执行时间的确定计算时间w处理器中完成计算操作所需的最大周期数路障同步开销为L通信开销为gh周期g是实现h关系的比例系数，常数w+gh+L执行一个超步的时间为:结论在一个有n个处理器的EREWPRAM计算机上，对两个N维向量A和B求内积s，可指派每个处理器完成2N／n个加法和乘法;改用BSP机器模型实现一个并行执行上述内积求解。在一个有8个处理器的BSP计算机上，用4个超步完成问题求解：例题①每个处理器在w=2N／8周期内计算，求出局部和②通信1次：处理器0，2，4，6将其局部和→处理器1，3，5，7③路障同步计算时间通信开销同步开销超步１超步2①计算１、３、５、７各自完成一次加法②通讯1次：处理器１，５中间结果送处理器３和７③路障同步计算时间通信开销同步开销超步3①计算：处理器３和处理器７，各完成一次加②通讯：处理器３→处理器７，完成一次通讯③路障同步计算时间通信开销同步开销2N／8+3g+3Ｌ+3个周期超步4①处理器7完成一次加法(w＝１）产生最后和②不再需要任何通信或同步计算时间无同步通信开销总执行时间总共计算了3次（实际上每一次都发生了计算的“重叠”现象）比较点积在一个有n个处理器的BSP计算机上，执行时间为：2N／n+logｎ(g+L+1)个周期PRAM计算机的执行时间2N／n+logn个周期没有考虑进程管理的并行性开销点积在一个有1个处理器的普通顺序计算机上，执行时间为：2N个周期关于BSP模型的实际优点和评论：比起PRAM模型来，BSP模型更为现实:除了用于进程管理的并行性开销外，它考虑了所有其他开销。对两个N维向量A和B求内积s单机顺序：2N个周期在n个处理器的EREWPRAM计算机上，指派每个的处理器完成2N/n个加法和乘法，在2N/n个周期内产生一个局部结果，然后用树归约方法在logn周期中，将n个局部和相加，形成最后的总和s。则总的执行时间为2N/n+logn在一个有n个处理器的BSP计算机上，执行时间为：2N／n+logｎ(g+L+1)个周期。五.VLSI复杂性模型VLSI复杂性模型背景：以ClarkThompson(1980)的研究工作为基础的二维VLSI芯片的AT2模型。AT2模型设A是用VLSI电路芯片完成给定运算的芯片面积;T为执行时间;又设s为运算问题的规模。Thompson在其博士论文中曾指出：对某些运算存在一个下界f(s),有AT2≥O(

f(s))1、芯片面积A的存储界限许多计算在需要处理大型数据集时常受到存储器的限制。计算对存储量的需求常常决定了芯片面积A的下限。2、AT体积的I/O界限可以用乘积AT来表示I／O的下限。3、等分通信界限A1/2Ｔ等分面积A1/2Ｔ，限定通信的下限。4、例题矩阵相乘算法的VLSI芯片的实现(VictorPrasanna，1992)要求：如何计算芯片面积A和计算时间T？一个每行和每列处理单元(PE)都有广播总线的网格系统上做n×n矩阵乘法C＝A×B分析：二维网格结构如下图所示。PE间的通信通过广播总线实现PE广播总线每个PE占据一单位面积总芯片面积为O(n2)广播总线需要O(n2)导线面积nXn矩阵相乘可在此网格芯片上完成的时间为T＝O(n)说明：PE表示成PE(i，j)，0≤i，j≤n-1存储器分布在所有的PE上，每个PE只能访问自己的本地存储器。下面的并行算法，可完成C(i，j)＝∑A(i，k)XB(k，j)k=0n-1其中0≤i，j≤n-1的点积运算，并产生全部输出元素。40PE(i，j)computes

C(i，j)←C(i，j)+A(i，k)XB(k，j)50ContinueDoall10for0≤i，j≤n-110PE(i，j)setsC(i,j)to0／Initialization／Do50for0≤k≤n-1Doall20for0≤i≤n-120PE(i，k)broadcastA(i，k)alongitsrowbusDoall30for0≤j≤n-130PE(k，j)broadcastB(k，j)alongitscolumnbus／PE(i，j)nowhasA(i，k)andB(k，j)，0≤i，j≤n/Doall40for0≤i，j≤n-1

Doall表示所有M段在M台处理机上并行执行并行程序点积程序算法沿k方向有一顺序循环，用了n个单位时间(迭代)。已知，T＝O(n)，所以AT2＝O(n2)×(O(n))2＝O(n4)

5可扩展的范围和设计一、可扩展性范围系统伸缩：增加或减少系统资源。这里假定并行处理计算机的体系中的结点均为单一处理器结点可扩展性范围包括：资源可扩展性应用可扩展性技术可扩展性1.资源可扩展性资源可扩展性是指通过增加处理器数、更多的存储部件(高速缓存，主存，磁盘)以及增加软件等方法，使系统具有更高性能或功能。涉及三方面：规模可伸缩性资源扩展软件可扩展性规模可伸缩性与处理器数相关联扩展一个计算机系统增加机器规模（处理器数）不同并行计算机规模可扩展能力不同限制并行系统可扩展性的两个主要因素是：程序设计及通信（1）规模可伸缩性处理器数示例在1997年时：一个对称多处理机(SMP)系统最多能扩展到大约64个处理器；一个IBMSP2并行机能扩展到最多具有512个处理器。当前的并行计算机规模的扩展：增加互连网络、接口以及通信软件在内的子系统有效地利用更大并行性，即如何为扩大的系统进行编程。（2）资源扩展增加处理器数不是唯一方式保持处理器数不变通过增加更多存储容量、更大的芯片外高速缓存以及更大容量磁盘等方法来扩展系统。存储部件示例IBMSP2中的存储器需求当Maui高性能计算中心(MHPCC)决定升级它的具有400个结点的SP2系统时，它选择了增加存储器和磁盘容量方法，而不是增加更多结点数方法。加入更多处理器表概述了所扩展的存储容量要求：系统必须设计成能允许扩展这么多的容量。实际系统总有一个最大存储器容量的上限。例如：IBMSP2中的每个结点最多可容纳2GB存储器；CrayT3D为64MB（3）软件可扩展性包括：操作系统的一个新版本，它具有更多功能性，如多线程，从而可支持更多的用户进程，更大的地址空间以及更高效的内核功能等。具有更有效优化的编译器更有效的数学和工程库更有效和易于使用的应用软件对用户更友好的编程环境2、应用可扩展性相同程序在一个可扩展系统上运行时，其性能随规模扩大成比例地改进。两个度量：机器规模可扩展性问题规模的可扩展性应用程序（1）机器规模可扩展性随着附加处理器的增多，系统性能会有多大改进。示例假定一个有n个处理器的系统，作数据库服务器用它拥有美国人口数据库，通常有100位美国科学家查询，其性能为每秒1000个事务处理(TPS)。现在如果我们将处理器数加倍成2n，能期望速度有多少改进?期望是多少？所增加的资源中，处理器最为常见；也可能是存储器容量和I／O容量（2）问题规模可扩展性是指系统在处理更大数据量和工作负载的更大求解问题时其性能如何。示例例如：仍以上述的数据库服务器为例，如果该服务器上装有中国人口的数据库，则此服务器的服务质量将会如何?注意到此数据库的大小已增至原来的5倍。如果用户数增至200(100个美国和100中国科学家联合参与研究)，将会发生什么情况?在研究应用可扩展性时，有以下3点值得注意：许多实际的并行应用问题对于机器和问题规模已有内在限制应将“应用／机器”一起视为一个系统它也依赖于资源规模3、技术可扩展性是指该系统能适应技术的改变。它可进一步分为3类：代可扩展性空间可扩展性异构可扩展性技术创新（1）代(时间)可扩展性一个系统扩展可以通过使用：下一代的硬件部件更快的处理器更快存储器新版本的操作系统更强功能的编译器计算机系统中发展最快的部件是处理器进展最慢的部分是程序设计语言(Fortran77仍被广泛使用)单计算机每两年可以将处理器升级一次并以慢得多的速度更新其他部件并行计算机中这种更新不活跃例题IBM个人计算机的代可扩展性:最具有代可扩展的计算机是IBMPC机PC系统(从处理器到母板、I／O卡和软件)是设计成代可扩展的。现有系统中的二进制代码和应用程序(DOS、Windows、数据库、电子表格及字处理软件等)不用作任何修改，就可在升级的系统中运行得更快。（2）空间可扩展性这一用语是由GordenBell发明的，用来表示一个系统可从一个盒子、一间房间或一幢大楼中的多处理器扩展到多幢大楼和地理范围(远距离范围)中的多处理器的能力。因特网则具有最好的空间可扩展性SMP和MMP只具有有限的空间可扩展性（3）异构可扩展性一个系统扩展不同设计者和厂商所提供的硬件和软件部分的能力系统应使用具有标准、开放系统结构和接口的部件例题可扩展并行计算机的”软件可移植性”IBM并行操作环境(POE)在任何规模的RS6000系统上具有可扩展性POE特点支持一个并行程序无需任何修改就能在由RS6000结点机构成的任何网络中运行结点可以是一个低端PowerPC工作站，可以是一个高端SP2宽结点这些结点能由任何普通互联网络，从慢速以太网到SP2的高性能开关(HPS)，加以连接结点之间的距离不限例题并行虚拟机(PVM)，它也是异构可扩展的：它允许一个并行程序运行在来自不同厂商的结点机所构成的网络上。二、可扩展设计原理包括：独立原理平衡设计原理可扩展性设计原理时延隐藏原理(第5章介绍）1.独立原理（1）定义应努力使系统中的各个组成部分（硬、软件）相互独立。如果无法达到完全独立，则应尽力使相关程度减至最小并使相关性尽量清晰。（2）采用独立原理的