Ch1 高等计算机的核心技术-并行处理

高等计算机系统结构研究生课程高等计算机系统结构课程介绍参考书目：1．PattersonD.A.，Hennesy

J.L.，Computer

Architecture：AQuantitativeApproach，Morgan

KanfmannPublishers，1995。2．ComputerOrganization &Design：The

Hardware／SoftwareInterface。第一章高等计算机的核心技术——并行处理第二章加速比性能模型与可扩展性分析第三章互连与通信第四章划分与调度第五章并行存储器系统第六章CacheCoherence第七章MemoryConsistency第八章指令级并行处理第一章高等计算机的核心技术——并行处理1.1什么是并行处理

1.1.1并行处理定义 1.1.2并行性级别1.2为什么要开发并行处理技术1.3并行处理计算机结构沿革1.4其它并行处理计算机技术1.1什么是并行处理1.1.1并行处理定义并行处理是指同时对多个任务或多条指令、或同时对多个数据项进行处理。 完成此项处理的计算机系统称为并行处理计算机系统。弗林分类法按照指令流和数据流多倍性的特点，计算机可以划分为以下四类：1、SISD：单指令流单数据流计算机2、SIMD：单指令流多数据流计算机3、MISD：多指令流单数据流计算机4、MIMD：多指令流多数据流计算机SISD：传统的单CPU顺序机SIMD：空间并行，多PE，向量处理MISD：流水线＋脉动阵列，专用MIMD：真正的并行处理机，包括共享存储器型和消息传递型。MMPUCUDSISIS1、SISD：单指令流单数据流计算机

SISD典型单处理机，包括：单功能部件处理机：IBM1401，VAX-11

多功能部件处理机：IBM360/91，370/168，CDC6600

流水线处理机：标量流水线处理机MM1PU2CU….ISISPUnPU1MM2MMnDS2DSnDS12、SIMD：单指令流多数据流计算机

SIMD并行处理机、阵列处理机、向量处理机、相联处理机、超标量处理机、超流水线处理机、…多个PU按一定方式互连，在同一个CU控制下，多各自的数据完成同一条指令规定的操作；从CU看，指令顺序（串行）执行，从PU看，数据并行执行。3、MISD：多指令流单多数据流计算机MMCU1PU1CUnPUnCU2PU2……IO脉动式阵列（systolicarray）PU2CU1….IS3IS1PUnPU1MM1DS1CU2CUn….IS2MM2DS2MM2DS2IS1IS2IS3包括：紧密偶合：IBM3081、IBM3084松散偶合：D-825、Cmmp、CRAP-23、MIMD：多指令流单多数据流计算机

同时性（simultaneity）——两个或多个事件在同一时刻发生，资源重复。

并发性（concurrency）——两个或多个事件在同一时间间隔内发生，分时共用。

流水特性（pipelining）——在一个重叠的时间内所发生的流水事件，时间重叠。

1.1.2并行性级别

粒度（granularity）：衡量一个软件进程的计算量的度量。最简单的是指此程序段中的指令数。分细、中、粗三种。 按粒度的不同，并行性级别可以分为指令级、循环级、过程级、子程序级和作业级等不同的层次。它们对应的计算粒度可以为细粒度、中粒度和粗粒度。如下：1.指令级并行典型细粒度，一般少于20条指令。借助优化编译器自动检测并行性，将源代码变成运行时系统能识别的并行形式。2.循环级并行

典型循环含少于500条指令，由于有些循环操作在连续迭代中并不相关，易于向量化，是在并行机或向量机上运行的最优程序结构。递归循环的并行化比较困难。向量处理由优化编译器在循环级开发，仍属于细粒度计算。3.过程级并行

中粒度并行，指令少于2000条，分析过程间的并行性比细粒度要困难。有时需要重新设计程序，并要编译器的支持。SIMD、多任务处理属于这一层。4.子程序级并行（粗）中粒度并行，几千条指令，常在messagepassing多计算机上以SIMD或MIMD方式执行。并行性主要由算法设计人员与程序员开发。5.作业级并行粗粒度并行，数万条指令，常由加载程序和操作系统处理这类并行性，靠算法有效性来保证。一般说来： 细粒度：用并行化或向量化编译器来开发，共享变量通信支持。 中粒度：靠程序员和编译器一起开发，共享变量通信。 粗粒度：取决于操作系统和算法的效率，消息传递通信。例子：在共享存储器型多处理机上执行：

L1: DO 10 I=1,N L2: A(I)=B(I)+C(I) L3: 10 Continue L4: SUM=0 L5: DO 20 J=1,N L6: SUM=SUM+A(J) L7: 20 Continue假设：L2，L4，L6每行要用一个机器周期。L1，L3，L5，L7所需时间可以忽略。 所有数组已经装入主存，程序已装入Cache中（取指令和加载数据可以忽略不计）。 忽略总线争用或存储器访问冲突。 上面的程序实际上把数组B(I)和C(I)相加，最后得到一个总和。

共享存储多处理机结构如下图：P1P2……Pm系统互连I/OSM1……SMm处理机共享存储器 在单机系统中，2N个周期可以完成上述的操作：

I循环中执行N次独立迭代需要N个周期；

J循环中执行N次递归迭代也需要N个周期。 在共享存储型的多处理机系统上： 假设有M台处理机，可以将循环分成M段，每段有L=N/M个元素。 代码如下所示：

Doall k=1,M Do10I=L(k-1)+1,kL A(I)=B(I)+C(I) 10 Continue

SUM(k)=0 Do20J=1,L

SUM(k)=SUM(k)+A(L(k-1)+J) 20 Continue

Endall 分段的I循环可以在L个周期中完成； 分段的J循环在L个周期中产生M个部分和。 所以产生所有的M个部分和共需要2L个周期（还需要将这些部分和合并）。 假设经过共享存储器的处理机之间的每次通信操作需要k个周期。 设N=32，M=8，则经过2L（即8个周期）后在8台处理机上各有一个部分和，还需要8个数相加。 为了合并部分和，可以设计一个l层的二进制加法树，其中l=log2M，加法树用l(k+1)个周期从树叶到树根顺序合并M个部分和，如下：

二进制加法树： 所以，多处理机系统需要 才能得到最终的结果。 假定数组中有N=220个元素，顺序执行需要2N=221个机器周期，假设机器间通信的开销平均值为k=200个周期，则在M=256台处理机的并行执行需要：第一章高等计算机的核心技术——并行处理 1.1什么是并行处理

1.2为什么要开发并行处理技术 1.3并行处理计算机结构沿革 1.4其它并行处理计算机技术1.2为什么要开发并行处理技术

对单用户，可以提高加速比（SpeedupOriented)；

对多用户，可以提高吞吐率（ThroughputOriented).

对不同的需求我们可以做需求分析如下： 1.天气预报 天气预报模式为非线性偏微分方程，预报台风暴雨过程，计算量为1014—1016次浮点运算，需要10GFlops—100GFlops的巨型机。 用途：局部灾害性天气预报。2.石油工业

地震勘探资料处理 油藏数值模拟 测井资料处理 地震勘探由数据采集、数据处理和资料解释三阶段组成。 目前采用的三维地震勘探比较精确的反映地下情况，但数据量大，处理周期长。

100平方公里的三维勘探面积，道距25米，60次覆盖，6秒长记录，2毫秒采样，一共采集2.881010个数据，约为116GB。 叠加后数据为4.8108个数据。用二维叠前深度偏移方法精确的产生地下深度图像，需要进行251012FLOP，采用100MFLOPs机器计算250天，1GFLOPs机计算25天，10GFLOPs机器35分。考虑到机器持续速度常常是峰值速度的10-30%，所以需要100GFlops的机器。CrayT932/32约为60GFLOPs。3.航空航天 研究三维翼型对飞机性能的影响。数值模拟用时间相关法解Navier-Stoker方程，网格分点为1204050，需内存160MB，6亿计算机上解12小时，如果在数分钟内完成设计，则需要千亿次计算机。4.重大挑战性课题需求（图3.5）

计算空气动力学：千亿次/秒（1011）

图像处理： 百亿次/秒（1010）

AI： 万亿次/秒（1012）5.核武器 核爆炸数值模拟，推断出不同结构与不同条件下核装置的能量释放效应。 压力： 几百万大气压 温度： 几千万摄氏度 能量在秒级内释放出来。设计一个核武器型号，从模型规律、调整各种参数到优选，需计算成百上千次核试验。LosAlamos实验室要求计算一个模型的上限为8-10小时。 千万次机上算椭球程序的计算模型需要40-60CPU小时。 二维计算，每方向上网格点数取100，二维计算是一维的200倍，三维是一维的33000倍。若每维设1000网格点，则三维计算是一维的几十万倍之多。此时对主存储器容量要数十、数百亿字单元（64位）。 另外还有I/O能力的要求，可视化图形输出。 6.解决方案只有开发并行处理技术才能满足要求：

3Tperformance：

TeraflopsofComputingPower TerabyteofMainMemory Terabyte/sofI/Obandwidth第一章高等计算机的核心技术——并行处理1.1什么是并行处理1.2为什么要开发并行处理技术1.3并行处理计算机结构沿革

1.3.1向量机与多向量机 1.3.2SIMD计算机 1.3.3Shared-MemoryMultiprocessors 1.3.4Distributed-MemoryMultiprocessors

1.3.5四类实用的并行系统1.4其它并行处理计算机技术1.3并行处理计算机结构沿革1.3.1向量机与多向量机向量机的结构如下图：ScalarFunctionalpipelinesScalarControlunitscalarprocessorscalarinstructionMainMemory(Programanddata)MassStorageHostComputerI/O(user)VectorControlunitvectorregistersvectorprocessorcontrolVectorFunctionalpipelinesVectorFunctionalpipelines……vectorinstruction程序和数据从Host进入主机指令先在Scalarcontrolunit译码，如是标量或控制操作指令，则在标量功能流水部件种执行。如果是向量指令，则进入向量控制部件。register-to-register：

Crayseries FujitsuVP2000seriesmemory-to-memory：

Cyber205多向量机发展过程：CDC7600(CDC,1970)CDCCyber205(Levine,1982)Memory-MemoryCray1(Russell,1978)register-registerETA10(ETA,Inc,1989)CrayY-MPCrayResearch1989FujitsuNECHitachiModelsCrayMPPCrayResearch1993其中：

CrayY-MP,C90：

Y-MP有2，4，8个处理器，而C90有16个处理单元（PE），处理速度16GFlops。

ConvexC3800family：8个处理器，4GB主存储器，

Peakperformance为2GFlops。1.3.2SIMD计算机SIMD计算机的结构如下图：ControlUnitProc0Mem0Proc1Mem1……ProcN-1MemN-1PE0PE1PEN-1InterConnectionNetworkMasParMP-1：可有1024，4096，…，16384个处理器。在16KPEs，32位整数运算，16KB局部存储器模块的配置下，可达26000MIPS，单精度浮点运算1.5GFlops，双精度浮点运算650MFlops。CM-2：

65536个处理单元，1Mbit/PE。 峰值速率为28GFlops，持续速率5.6GFlops。SIMD计算机发展过程图如下：IlliacIV(1968)GoodYearMPP(1980)BSP(1982)MasParMP1(1990)IBMGF/11(1985)DAP610(AMT，Inc.1987)CM2(1990)CM5(1991)1.3.3MIMD－Shared-MemoryMultiprocessorsUMA(Uniform-memory-access)model：

物理存储器被所有处理机均匀共享，所有处理机对所有存储字具有相同的存取时间。P0I/OP1SM1……PnSMnInterConnectionNetwork(Bus、Crossbar、MultistageNetwork)……处理器共享存储器NUMA(NonUniform-memory-access)model：访问时间随存储字的位置不同而变化。P1……PnLMnInter-ConnectionNetwork……LM1P2LM2……COMA(Cache-onlymemoryarchitecture)：只用高速缓存的多处理机 远程高速缓存访问则借助于分布高速缓存目录进行。PDInterConnectionNetwork……distributedcachedirectoriesCPDCPDCKendallSquareResearch’sKSR-1Shared-MemoryMultiprocessors发展过程如下：Cmmp(cmu,1972)IllinoisCedar(1987)UltraComputerNYU(1983)FujitsuVPP500(1992)IBMRP3(1985)BBNButterfly(1989)stanford/Dash(1992)KSR-1(1990)1.3.4MIMD－Distributed-MemoryMultiprocessorsP……Message-passinginterconnectionnetwork(Mesh,ring,torus,hypercube,cube,cycle)MPMPMP……PPMMMMP……MPMP……MP例子：

IntelParagonXP/s：

采用50MHz的i860处理器，每个节点16-128MB主存储器，采用2D-Mesh互连，浮点运算5-300GFlops，或2.8-160Gips。

nCube2SModel80：

有4096-8192个PE，主存储器16384-262144MB，浮点运算163800-34000MFlops，整数运算61000-123000MIPS。 CosmicCube(1981)nCube-2/6400(1990)Mosaic(1992)Intelparagon(1992)MIT/Jmachine(1992)intel

iPSC’s(1983)Distributed-Memorymultiprocessors发展进程：1.3.5四类实用的并行系统1.向量机与多向量机硬、软件技术相对成熟、应用广泛、市场占有率高。很难达到3Tperformance来解决GrandChallenge

问题。 下面图表说明了这一类机器的发展过程。GFlops100100.11976197919821985198819911994YearCray1/10.16GFCrayX-MP/20.24GFCray2/41.9GFCrayY-MP/82.6GFCrayJ916/163.2GFCrayC916/1616GFCrayT932/3260GF2.对称式多处理机SMP

SMP：Symmetric

MultiProcessors SharedMemorymultiProcessors SmallsizeMultiProcessors

处理机之间无主从之分，对外有相同的访问权，都有执行操作系统核心和I/O服务程序的能力。 共享存储器、统一地址空间，系统编程比较容易。

CPU可多至16台左右，做服务器用，市场前景好。典型的SMP有：

SunSPARCserver1000 SunSPARCcenter2000 SGIPowerChallengeSGIPowerChallengeL：2-6CPU，1.8GFlopsSGIPowerChallengeXL：

2-18CPU，5.4GFlops

*64位MIPSchip，每周期指令发射数为4

*8路交错主存、带宽为1.2GB/s

*I/O带宽320MB/s（每个控制器），配置4个可达1.2GB/s3.MPP系统（分布存储）多于100个PE，消息传递，分布存储； 可扩展，峰值可达3Tperformance；

贵，市场有限； 持续速度是峰值速度的3-10%； 可解决某些GrandChallenge问题，是国家综合实力的象征。 4.机群系统

NOW：NetworkOfWorkstations

COW：ClusterOfWorkstations特点： 投资风险小，软件财富继承性好；可构成异构系统，资源利用率高； 通信开销大。 一种典型的机群系统结构如下：CPUMemoryI/OCPUMemoryI/O……CPUMemoryI/OI/OI/OI/OMemoryMemory……MemoryCPUCPUCPUNetwork第一章高等计算机的核心技术——并行处理

1.1什么是并行处理 1.2为什么要开发并行处理技术

1.3并行处理计算机结构沿革

1.4其它并行处理计算机技术1.4其它并行处理计算机技术1.数据流技术 dataflow以数据驱动机制代替控制流机制 当功能部件输入端的操作数可用时就启动执行；可开发程序中所有的并行性，但费用昂贵，实际性能与功能部件数量、存储器带宽以及挂起和可用部件相匹配的程度有关。 如：MIT的MonSoos，*T

ETL的Sigma1，EM52.多线程 每台处理机有多个控制线程，同时运行多个现场，是实现时延隐藏的一种有效机制。 比如:

Tera，Alewife

成本高。3.逻辑推理与规约结构 逻辑推理： 日本第五代机，面向逻辑语言、执行速度慢，软件与程序设计环境欠丰富。

规约结构：

Alice，PGR，面向函数语言，执行速度慢，软件与环境欠丰富。4.关键技术 并行算法（数值算法与非数值算法） 并行计算模型 互连与通信 并行存储技术 同步与时延隐藏技术 并行I/O

划分、调度与负载平衡 优化编译 并行调试 工具与环境5.美国的主要行动（1）组织基于NSF的国家科学计算联盟 （NationalComputationalScienceAlliance）

建立国家科技网（Grid）：97.11开始，五年计划，总经费3.4亿美元。

目标：使美国在全国范围内的元计算机（网上的计算机可作为一个整体看待）达到实用水平。 为在桌面上解决计算科学与工程时提供一个有力的解题环境。 解决基于元计算环境的并行、分布、协作和immersive等问题。

UIUC、San

Diago组织实施。（2）DOE（能源部）支持的ASIC计划 （AcceleratedStrategicComputingInitiative）

保证在21世纪美国在核研究和核储备继续处于领先地位。 以LosAlamos，