第一章并行计算机模型

高级计算机系统结构上海大学计算机学院徐炜民

1AdvancedComputerArchitecture《高级计算机系统结构》这里的‘高级’其含义是指与本科教育中已经介绍的‘常规’的系统结构类型的区别，着重在模型、算法和并行处理上。计算机系统结构是计算机专业本科教育中的骨干课程，是ACM和IEEE/CS联合教程专题组所确定的主干课程。上海大学计算机学院计算机系统结构课程被国家教育部列入“十五”规划的重点建设课程。学习的困难：1。概念性强，形式描述弱2。面广，强调工程实现3。背景机大而多，且著名，但不易全面介绍和了解2AdvancedComputerArchitecture

参考教材：(1)英文原版：KaiHwang,AdvancedComputerArchitecture–Parallelism,Scalability,Programmability(1993)

中译本：高等计算机系统结构：并行性、可扩展性、可编程性（王鼎兴等译，1995）(2)英文原版：KaiHwang&ZhiweiXu,ScalableParallelComputingTechnology,Architecture,Programming(1998)

中译本：可扩展并行计算：技术、结构与编程（陆鑫达等译，2000）

(3)英文原版：DavidE.Culler,JaswinderPalSingh,AnoopGupta,ParallelComputerArchitecture–AHardware/SoftwareApproach[SecondEdition](1996)(4)英文原版：DavidA.Patterson,JohnL.Hennessy,ComputerArchitecture–AQuantitativeApproach[SecondEdition](1996)3AdvancedComputerArchitecture第一篇并行性理论1。并行计算机模型2。程序和网络特性3。可扩展性能原理第二篇硬件技术4。处理机与存储器层次结构5。总线，高速缓存和共享存储器6。流水线与超标量技术4AdvancedComputerArchitecture第三篇并行和可扩展系统结构7。多处理机和多计算机8。多向量机与SIMD计算机9。可扩展，多线程与数据流系统结构第四篇并行程序设计软件10。并行模型，语言和编译器11。并行程序开发与环境12。并行机的UNIX,Mach和OSF/15AdvancedComputerArchitecture

第一篇 并行性理论目前，衡量超级计算(supercomputing)仍用习惯的方法（小时、作业、程序数、程序可移植性）采用共享存储器的向量多处理器系统仍是主流（CrayResearch,Fujitsu,IBM,Hitachi,NEC）。例如，1993年的C90用16台处理器，Gigaflops=1610，9,500次/美元。九十年代，RISC标量处理机可达5000次/美元。基于消息传递的多计算机系统可达到Teraflops。

从广义上讲，可扩展性反映了系统结构、算法、软件和环境之间的相互关系。它涉及到系统结构的通用性、可扩展性、可编程性、可实现性。

6AdvancedComputerArchitecture第一章 并行计算机模型并行性在不同的处理级别中可表现为多种形式：先行方式、流水线方式、向量化、并发性、同时性、数据并行性、划分、交叉、重叠、多重性、重复、时间共享、空间共享、多任务处理、多道程序、多线程方式、分布式计算。7AdvancedComputerArchitecture一． 计算技术的现状1．历史演变：公元前500年，中国的算盘。1642年，法国BlaisePascal的机械加法器减法器。1827年，英国CharlesBabbage用于多项式计算的差分机。1941年，德国KonradZused用于通用的二进制机械计算机。1944年，HowardAiken提出由IBM制造用于通用计算的HavardMarkI十进制机电计算机。以后，就表现为所谓的“五代”计算机演变（表1－1）。8AdvancedComputerArchitectureIntel（Oct.2001）认为：计算模式的演变过程EnterpriseCentralizedMainframesServerCentricWebDistributedSolutions包括 1.PeertoPeer 2.Wirelessandmobile 3.OneIP 4.XML9AdvancedComputerArchitecture2．现代计算机组成：（图1－1）现代计算机是一种包括机器硬件、指令系统、系统软件、应用程序和用户接口的集成系统。各种求解方法可能需要不同的计算资源，这与求解问题的性质有关。10AdvancedComputerArchitecture11AdvancedComputerArchitecture冯诺依曼结构的特点：使用单一处理部件来完成计算、存储及通信功能；线性组织的定长存储单元（地址）；存储空间的单元是直接寻址的（地址）；使用低级机器语言，其指令完成基本操作码的简单操作；对计算进行集中的顺序控制（程序存储）。首次提出“地址”和“程序存储”的概念。冯诺依曼结构是传统计算机系统的理论“基石”。“集中的顺序控制”是计算机发展的“瓶颈”，以后计算机理论的发展，出现了非冯诺依曼结构的计算机系统。重要性在于多机和并行处理的概念是计算机发展的最主要的地方。12AdvancedComputerArchitecture计算机系统的层次结构:信息处理过程可以用控制流程的概念来描述，而实现描述控制流程的是有一定规则的字符集合的“计算机语言”。计算机语言并不专属软件范畴，它可以分属计算机系统的各个层次，分别对该层次的控制流程进行描述。基于对语言广义的理解，可以把计算机系统看成由多级“虚拟”计算机所组成。从内向外，层层相套，形成“洋葱”式结构的功能模型。（见图1-6）例：用户--建模--应用程序--高级语言--汇编语言--操作系统--机器语言--微程序--硬布线逻辑13AdvancedComputerArchitecture14AdvancedComputerArchitecture虚拟计算机的概念洋葱模型的每一层都是一个虚拟计算机，它只对“观察者”而存在，它的功能体现在广义语言上，对该语言提供解释手段，然后作用在信息处理或控制对象上，并从对象上获得必要的状态信息。从某一层次的观察者看来，他只能是通过该层次的语言来了解和使用计算机，至于内部任何工作和实现是不必关心的。（即：虚拟计算机是由软件实现的机器）虚拟计算机的组成，见图1-7用虚拟计算机观点定义的计算机系统的功能层次，见图1-815AdvancedComputerArchitecture16AdvancedComputerArchitecture17AdvancedComputerArchitecture系列机概念先设计一种系统结构（机器属性），而后按这种系统结构设计它的系统软件，按器件状况和硬件技术研究这种结构的各种实现方法，并按照速度、价格等不同要求，分别提供不同速度、不同配置的各挡机器。（系列机必须保证用户看到的机器属性一致）例：IBMAS/400优点：1。在使用共同系统软件的基础上，解决程序的兼容性问题；2。在统一数据结构和指令系统的基础上，便于组成多机系统和网络；3。使用标准的总线规程，实现接插件和扩展功能卡的兼容，便于实现OEM（OriginalEquipmentManufacture）。4。扩大计算机应用领域，提供用户在同系列的多种机型内选用最合适的机器的可能性；5。有利于机器的使用、维护和人员培训6。有利于计算机升级换代；7。有利于提高劳动生产率，增加产量、降低成本、促进计算机的发展。18AdvancedComputerArchitecture3．Flynn分类法MichealFlynn(1972)提出指令流、数据流和多倍性概念，把不同的计算机分为四大类（图1－3）：SISD（Single-InstructionSingle-Data,单处理机结构）SIMD（Single-InstructionMulti-Data,带分布存储器）MISD（Multi-InstructionSingle-Data,搏动式阵列）MIMD（Multi-InstructionMulti-Data,带共享存储器）19AdvancedComputerArchitecture20AdvancedComputerArchitecture4．性能的系统属性理想的计算机系统的性能要求机器功能和程序行为之间有良好的匹配。机器功能：好的硬件技术、改进的系统结构特性、有效的资源管理…程序行为：难预测，与应用和运行条件有密切的关系。如算法设计、数据结构、语言效率、程序员的技能、编译技术…21AdvancedComputerArchitecture

由于机器性能会随程序而变化，因此，应该在一定范围内或按调和分布来描述性能。描述性能的一些术语和公式：时钟频率：CPU是由一个恒定周期（τ，以ns表示）的时钟驱动。周期的倒数是时钟频率f=1/τ，以MHz表示

CPI(CyclePerInstruction)：一条指令的周期数。不针对某类指令，则表示给定的指令系统和综合程序的平均值。22AdvancedComputerArchitecture

性能因子：五个

Ic－已知程序的指令条数或指令计数，

p－指令译码和执行所需的处理机周期数，

m－所需的存储器访问次数，

k－存储周期与处理机周期之比，k值与存储器技术及处理机—存储器互连方法有关。存储周期比处理机周期τ大k倍。

T－执行程序所需的CPU时间。一条指令执行的过程一般分为取指令、译码、取操作数、执行、存储结果五个阶段。其中译码和执行由CPU完成，称处理机周期；取指令、取操作数（有可能操作二次）和存储结果是对存储器操作，称存储器周期。

T=Ic×CPI×τ

=Ic×(p＋m×k)×τ

23AdvancedComputerArchitecture系统属性：四个指令系统结构编译技术处理机实现和控制技术高速缓存与存储器层次结构MIPS速率：每秒百万次，表示CPU的执行速度吞吐率：系统在单位时间内能执行多少个程序24AdvancedComputerArchitectureMIPS速率：(MillionInstructionPerSecond)每秒百万次，表示CPU的执行速度。MISP速率=Ic/(T×106)=f/(CPI×106)=(f×Ic)/(C×106)C是执行已知程序所需的时钟周期总数。25AdvancedComputerArchitecture吞吐率：Wp（处理机吞吐率）：处理机在单位时间内能执行多少个程序。Wp=f/(Ic×CPI)

Ws（系统吞吐率）：系统在单位时间内能执行多少个程序。Ws<Wp（Ws有额外系统开销：I/O、编译、OS…）26AdvancedComputerArchitecture并行程序设计方法：有二种并行程序设计方法：隐式并行性和显式并行性。隐式并行性：常用传统的语言编程成顺序源编码，经并行编译器编译成并行目标码执行。（语言容易，编译器难）显式并行性：需要并行语言来编程，编译器仅保持并行性和把资源分配给目标机器。（语言难，编译器容易）27AdvancedComputerArchitecture28AdvancedComputerArchitecture多处理机与多计算机从不同角度分析，有三种模型结构组织模型理论模型复杂性模型先讨论结构组织模型29AdvancedComputerArchitecture

1．共享存储型多处理机：l 均匀存储器存取-UMA模型（UMA－UniformMemoryAccess）l 非均匀存储器存取-NUMA模型（NUMA－NonuniformMemoryAccess）l 只用高速缓存的存储器结构-COMA模型（COMA－CacheOnlyMemoryArchitecture）30AdvancedComputerArchitecture1．共享存储型多处理机：（1） 均匀存储器存取（UMA－UniformMemoryAccess）UMA模型（图1－6）适用于多用户的一般应用和分时应用。它可以在限时应用中用来加快单个大程序的执行。所有处理器均匀（所谓均匀是指所有处理器对所有存储字具有相同的存取时间）共享物理存储器。各处理机之间的通信是通过共享存储器的共享变量来实现的。这一类多处理机由于对资源的高度共享,常称紧耦合系统(tightlycoupledsystem)。系统互联常采用总线、交叉开关、多级网络。

31AdvancedComputerArchitecture32AdvancedComputerArchitecture对称多处理机系统(symmetricmulti-processor)

所有处理机都能同样访问所有外围设备；所有处理机都能同样运行执行程序，如操作系统的内核、I/O服务程序。

不对称处理机系统(asymmtricmulti-processor)只有一台或一组处理机（MP主处理机）执行操作系统并操纵I/O，其余处理机（AP附属处理机）没有I/O能力。33AdvancedComputerArchitecture

NUMA模型NUMA模型的共享存储器物理上是分布在所有处理机的本地存储器上，这些存储器的集合组成全局地址空间。由于访问本地存储器快，访问远程存储器慢（经过互联网络），所以访问时间取决于存储字所在位置。图1-7b表示了层次结构NUMA模型。处理机被分成若干机群（cluster），每个机群内可以是UMA模型或NUMA模型，但整个系统被认为NUMA模型。34AdvancedComputerArchitecture

35AdvancedComputerArchitecture

COMA模型COMA模型是NUMA模型的一种特例。由全部高速缓存组成全局地址空间，访问远程缓存是通过分布在各处理机上的高速缓存目录来进行的。图1-836AdvancedComputerArchitecture

37AdvancedComputerArchitecture

2．分布存储型多处理机(1)系统由多个结点（由处理机、本地存储器、I/O设备组成的自治的计算机）通过消息传递网络互相连接。图1-938AdvancedComputerArchitecture

39AdvancedComputerArchitecture

(2)消息传递型多计算机的演变：l 第一代（1983-1987）基于处理机板技术，采用超立方体结构和软件控制的消息交换方法。（IntelIpsc/1）l 第二代（1988-1992）用网络连结的系统结构、硬件消息寻径、中粒度分布计算的软件环境。（IntelParagon）

l 第三代（1993-）处理机与通信工 具在同一芯片上实现的细粒度多计算环境。 （MITJ-Machine）40AdvancedComputerArchitecture

(3)消息传递型多计算机研究的重要问题：l 消息寻径方式l 网络的流控制策略l 死锁避免l 虚拟通道l 消息传递原语

l 程序分解技术41AdvancedComputerArchitecture

多向量机和SIMD计算机1．向量超级计算机向量计算机往往是在标量处理机与向量处理机的“混合物”,程序与数据由主机加载到主存储器；全部指令由标量控制器译码，若是标量操作或程序控制操作则有标量处理机的标量功能流水线执行；若是向量操作则送入向量控制器，由主存储器与向量功能流水线执行向量数据流。图1-1142AdvancedComputerArchitecture

43AdvancedComputerArchitecture

2．SIMD超级计算机SIMD计算机的操作模型可以用五元组表示：M=（N，C，I，M，R）式中：N：机器的处理单元（PE-ProcessorElement）数C：由控制部件（CU-ControlUnit）直接执行的指令集，包括标量与程序流控制指令；I：由CU广播到所有PE进行并行执行的指令集，包括算逻运算、数据寻径、屏蔽操作、PE执行的局部操作；M：屏蔽方案集，把PE划分为允许操作与禁止操作两种子集；

R：数据寻径功能集，互连网络中PE间通信所需的 各种设置模式。图1-1244AdvancedComputerArchitecture

45AdvancedComputerArchitecture

PRAM和VLSI模型并行计算机的理论模型是从物理模型抽象得到的.算法和芯片设计者利用理论模型为开发并行算法提供了一种方便的框架(无需关心实现细节或物理约束条件.这些模型可为并行计算机求的理论性能界限或芯片制作前估算芯片区的VLSI复杂性和执行时间.当将实际机器与联想机器(不考虑结点间通信开销)作比较时,抽象模型在分析可扩展性和可编程性方面是十分有用的.46AdvancedComputerArchitecture

并行随机存取机(RAM-RandomAccessMachine)随机存取机(RAM-RandomAccessMachine)并行随机存取机(PRAM-ParallelRandomAccessMachine)计算的易解性(tractability)：时间复杂性，空间复杂性，NP

完全性目的：利用复杂性模型可方便讨论在并行计算机上实现算法的渐近特性.47AdvancedComputerArchitecture

时间复杂性和空间复杂性计算机求解一个规模为s的问题的算法复杂性取决于所需的执行时间和存储空间。所以：时间复杂性是问题规模的函数（时间复杂性函数是算法的渐近时间复杂性）。通常考虑最坏情况下的时间复杂性。空间复杂性也是问题规模的函数（空间复杂性函数是算法的渐近空间复杂性）。通常考虑大问题的数据存储，而程序存储和输入数据的存储一般不考虑。48AdvancedComputerArchitecture

串行复杂性：串行算法的时间复杂性并行复杂性：并行算法的时间复杂性一般认为：并行复杂性比串行复杂性低，或相近确定性算法：每个操作步骤是唯一确定的；与实际计算机上程序执行的过程是一致的。不确定性算法：目前没有这类的实际机器。49AdvancedComputerArchitecture

NPC（NP完全问题）：如果存在一多项式p(s)，对任何问题规模s的时间复杂性为O(p(s))，则某算法即具有多项式复杂性。具有多项式复杂性算法的问题称为P类，能以多项式时间用不确定性算法求解的问题集称为NP类。P类问题是计算易解的，NP-P类问题是难解的，用确定性算法模拟不确定性算法可能是指数量级的时间，又称具有指数时间复杂性的问题。∵P∈NP，目前不知道：P=NP或P≠NP，推测有NP完全=NPC，NPC∈NP，NPC∩P=φ。用P模拟NP是指数级时间假如任何NP完全问题是多项式时间可解问题，则P=NP。结论：只能用近似算法求解某些NP完全问题。图1-1350AdvancedComputerArchitecture

PRAM模型（Fortune&Wyllie1978）此前有RAM模型(Sheperdson&Sturgis1963)主要描述单机系统PRAM模型如图1-14，可开发并行算法和分析可扩展性及复杂性。多PE共享全局可寻址存储器，按照同步地读存储器、计算、写存储器循环方式运行。由于共享存储器，存在对存储器并发读和并发写的控制。51AdvancedComputerArchitecture

存储器修改的四种可能选择：互斥读（ER）：在每一循环中最多有一台PE从任何一存储单元读操作（限制较大）互斥写（EW）：每次最多有一台PE对存储单元写入内容并发读（CR）：多台PE在同时对同一存储单元读取同一信息并发写（CW）：同时写入同一单元（会产生混乱，要有避免冲突的策略）52AdvancedComputerArchitecture

由此形成四种PRAM模型方案：EREW-PRAM模型：禁止一台以上PE同时读/写同一存储单元（限制最大的PRAM模型）CREW-PRAM模型：