第一章 高等计算机的核心技术-并行处理

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

1.1.1并行处理定义 1.1.2并行性级别 1.2为什么要开发并行处理技术 1.3并行处理计算机结构沿革 1.4其它并行处理计算机技术1.1什么是并行处理

1.1.1并行处理定义

并行处理是指同时对多个任务或多条指令、或同时对多个数据项进行处理。 完成此项处理的计算机系统称为并行处理计算机系统。

同时性（simultaneity）——两个或多个事件在同一时刻发生。

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

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

1.1.2并行性级别

粒度（granularity）：衡量一个软件进程的计算量的度量。最简单的是指此程序段中的指令数。分细、中、粗三种。

按粒度的不同，并行性级别可以分为指令级、循环级、过程级、子程序级和作业级等不同的层次。它们对应的计算粒度可以为细粒度、中粒度和粗粒度。 1.指令级并行

典型细粒度，一般少于20条指令。借助优化编译器自动检测并行性，将源代码变成运行时系统能识别的并行形式。2.循环级并行 典型循环含少于500条指令，由于有些循环操作在连续迭代中并不相关，易于向量化，是在并行机或向量机上运行的最优程序结构。递归循环的并行化比较困难。向量处理由优化编译器在循环级开发，仍属于细粒度计算。 3.过程级并行

中粒度并行，指令少于2000条，分析过程间的并行性比细粒度要困难。有时需要重新设计程序，并要编译器的支持。SPMD、多任务处理属于这一层。

4.子程序级并行 （粗）中粒度并行，几千条指令，常在messagepassing多计算机上以SPMD或MPMD方式执行。并行性主要由算法设计人员与程序员开发。

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.天气预报 1990年10次台风登陆，福建、浙江两省损失79亿元，死亡950余人。 天气预报模式为非线性偏微分方程，预报台风暴雨过程，计算量为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主存储器，

Rerkperformance为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.3Shared-MemoryMultiprocessors

UMA(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.4Distributed-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)inteliPSC’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/3260GF

2.对称式多处理机SMP

SMP：SymmetricMultiProcessors 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/s

3.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，EM5 2.多线程 每台处理机有多个控制线程，同时运行多个现场，是实现时延隐藏的一种有效机制。 比如:

Tera，Alewife

成本高。 3.逻辑推理与规约结构

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

规约结构：

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

划分、调度与负载平衡 优化编译 并行调试 工具与环境 5.美国的主要行动

（1）组织基于NSF的国家科学计算联盟 （NationalComputationalScienceAlliance）

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

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

UIUC、SanDiago组织实施。

（2）DOE支持的ASIC计划 （AcceleratedStrategicComputingInitiative）

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

三个国家实验室为核心，组成遍及美国不同地区的“拆墙合作”。 为建立VirtualLaboratory奠定基础。 研制出超级计算机系统：万亿次量级的计算机，2的50次幂（约千万亿）容量的数据库系统。 提供高效、好用的计算环境。

能实现基于网络的、分布式协同工作环境。 能提供高效的、点对点的计算设施。 在CORBA的环境下有效的把计算平台和有关应用进行系统集成。 负载平衡。 可裁剪性。 6.ModelsofParallelComputers(1960s-1980s)DataMIMDSIMDInstructionImplicationMultipleDataStreamsMultipleDataStreamsSingleInstructionStreamsMultipleInstructionStreamsSingleProgram;Lotsofdatatohavelotsofparallelism;Programmingissimplersincecommunicationisalwayssynchronized;CommunicationsseperatefromcomputationsinceinstructionsdistinctMaybemanyProgramsLotsofprogramstohavelotsofparallelismH/Wconstructionissimplerusingoff-the-shelfuniprocessorscommunicationmergedwithcomputationImplicationIllivaIV、CM-2、MasParCrayX-MP、Sequent、nCube 7.一些缩写

SPMD——SingleProgramMultipleDataStream

MPMD——MultipleProgramMultiple DataStream

SIMD——SingleInstructionMultiple Data

MIMD——MultipleInstructionMultiple Data

网格是通过网络提供综合计算机资源和服务的基础设施

公用网络，计算机，存储。应用服务的支柱提供不间断的，无限的处理能力。Mainframe70sDistributedComputing21stCenturyInternetLate90sPC80sClient/Server90s什么是网格？

IanFoster关于网格的三个判断标准“WhatisGrid,aGuideforthePerplexed”GridToday,July17,2002,

网格的判断标准资源的协调而不仅仅是集中控制。使用标准的，开放式的，通用的协议和接口。提供安全可靠、高质量的服务。互联网服务提供方服务网格VirtualizationofservicesDynamicserviceprovisioningSelf-healingofservicesIntegratablewithEnterpriseapplications企业间及合作伙伴合作网格DOE,UKGrid&DoD协同共享公用的数据中心动态的提供资源企业内部网格及其三个阶段time共享程度企业网格Toshiba,TI,GMCluster-to-clustersharingmanagementReliablefiletransfer&stagingUseraccountmapping,Firewalls,Kerboros1996200020042008网格应用的挑战计算机制造业机械制造业

Projectfairshareflexiblelease适度的规模本地管理

ClearcasesupNFSloadbalanceWANfilesync

OptimaluseWANlicsharingBorrow/ReclaimServicedomains生命科学可靠文件传输

PDM集成

自动的工具最佳的应用

DatasourcesyncDatasetlifecycleDataCacheDataPipeline

WorkflowmgmtCapacityworkloadLargenumberofjobs

政府与教育

Efficientxferdatareplication

NUMACo-allocAdvanceRsv金融

WorkflowbusinessunitsilosDeadline

Messagingdatacaching计算机数据软件

第二章加速比性能模型与可扩展性分析 2.1加速比性能分析

2.1.1一般概念 2.1.2加速比 2.1.3三种加速比性能模型 2.2可扩展性分析2.1加速比性能模型

2.1.1一般概念 1.处理机—时间积

处理机数目与处理时间的乘积用以度量这些处理机运行时的资源利用率。 若一程序在

P台处理机上运行的时间为Tp，则此P台处理机在Tp时间间隔内完成的工作最大数量为Tp*P。

可将处理机实际工作曲线对时间的积分看成是这些处理机完成的有效工作量。

效率为有效工作量与最大工作量之比。2.并行度（DegreeOfParallelism—DOP）

并行度（DOP）是在一定时间间隔内执行一个程序所用的处理机的数目。3.并行性分布图

执行一个给定的程序时DOP对时间的分布图。

DOP与对应时间的间隔之积即为处理机要完成的工作或工作负载。下图所示为一个并行性分布图。DOPt1tt2并行性分布图2.1.2加速比1.绝对加速比

将最好的串行算法与并行算法相比较.

定义一（与具体机器有关）将最好的串行算法在一台上的运行时间与并行算法在N台运行的时间相比。

定义二（与具体机器无关）将最好的串行算法在最快的顺序机上的执行时间与并行算法在并行机上的运行时间相比。2.相对加速比

同一并行算法在单节点上运行时间与在多个相同节点构成的处理机系统上的运行时间之比。 这种定义侧重于描述算法和并行计算机本身的可扩展性。线性加速比：中间开销小，通信少，弱耦合计算超线性加速比：当应用需要大内存时可能出现病态加速比：加速比递减，可能是计算量太小2.1.3三种加速比性能模型

1.固定负载加速比性能模型—Amdahl定律 在许多实时应用领域，计算负载的大小常固定。在并行机中，此负载可分布至多台并行执行，获得的加速比称为fixed-loadspeedup。一个问题的负载可表示如下：W=Ws+Wp

其中，Ws代表问题中不可并行化的串行部分负载，Wp表示可并行化的部分负载。 则n个节点情况下，加速比可以表示如下：设串行因子α为串行部分所占的比例。即代入即得Amdahl’law：不管采用多少处理机，可望达到的最好加速比：效率En可以表示为：处理机数目n越大，效率En越低。Amdahl定律告诉我们：系统中某一部件由于采用某种更快的执行方式后整个系统性能的提高与这种执行方式的使用频率或占总执行时间的比例有关。加速比的两个决定因素：1.计算机执行某个任务的总时间中可被改进部分的时间所占的百分比，即

可被改进部分占用时间/改进前整个任务的执行时间， 记为Fe，它总小于1。2.改进部分采用改进措施后比没有采用改进措施前性能提高的倍数，即

改进前改进部分执行时间/改进后改进部分执行时间， 记为Se。例1： 假设将某系统的某一部件的处理速度加快到10倍，但该部件的原处理时间仅为整个运行时间的40%，则整个系统的性能提高了多少？

解：Fe=0.4，Se=10，例2： 采用哪种实现技术来求浮点数平方根FPSQR的操作对系统的性能影响较大。假设FPSQR操作占整个测试程序执行时间的20%。一种实现方法是采用FPSQR硬件，使FPSQR操作的速度加快到10倍。另一种方法是使所有浮点数据指令的速度加快，使FP指令的速度加快到2倍，还假设FP指令占整个执行时间的50%。请比较这两种设计方案。

解：Fe_FPSQR=0.2，Se_FPSQR=10， Fe_FP=0.5，Se_FP=2，Amdahl’law又称为固定规模加速比模型，问题规模不随处理机变化而变化。固定问题规模，看用并行技术能达到的最短时间是多少。在固定规模加速比模型下，负载和执行时间随系统中处理机数目n变化的情况如下图：WsWpWsWpWsWpWsWpWorkloadN1234ExecutionTimeNTsTp1TsTp2TsTp3TsTp4固定负载执行时间随N增加而减少固定负载加速比模型下的负载和执行时间情况当处理器数目n=1024，加速比Sn随α变化的情况如下：得出曲线如下图：91Snα102448312410可以比较不同的α对加速比带来的不同影响：α=0Snnα=0.01α=0.1α=0.9α=0时得到理想加速比，当α值增加时，加速比性能急剧下降。结论：加速比曲线随α的上升急剧下降，原因是存在顺序部分Ws，无法用增加系统的处理机数目来解决。这一性质在过去二十年间给人们造成了对并行处理非常悲观的印象。影响：两种意见： 1.劝阻制造商生产大规模并行计算机。 2.研究并行编译器，以降低α的值，从而提高系统的性能。规定负载加速比模型的可能应用范围：

对时间要求严格的应用问题。

2.固定时间加速比性能模型—Gustafsun定律 有许多应用领域强调精度而不时运行时间。1988年，Gustafsun提出了固定时间加速比模型。当机器的规模扩大时，解题的规模也随着扩大，从而得到更加精确的解，而使运行时间保持不变。 比如：有限元方法做结构分析，流体动力学做天气预报解PDE(偏微分方程组)就需要提高精度。 粗格要求的计算量较少，而细格的计算量多，得到的精确度也较高。天气预报模拟求解四维PDE，如果使每个实际方向（X，Y，Z）的格点距离减少10倍，并以同一幅度增加时间步，那么可以说格点增加了104倍，因而工作负载也至少增大了10000倍。模型提出的背景： 固定负载模型有缺陷：因为Amdahl’law中，α取决于问题及并行编译器的效率，无法描述系统固有的特性。加速比的公式： 其中，Wp’=nWp和Ws+Wp=Ws’+Wp’/n作为固定时间的条件。Ws’+Wp’/n表示在扩大负载后在增加处理机台数的情况下的平均负载（执行时间），它应当和负载没有扩大情况下的平均负载（执行时间）Ws+Wp相等。即有Ws+Wp=Ws’+Wp’/n。同时，负载的串行部分并没有改变，即有Ws=Ws’。在固定时间加速比模型下，负载和执行时间随系统中处理机数目n变化的情况如下图：WsWpWsWpWsWpWsWpWorkloadN1234ExecutionTimeNTsTp1TsTp2TsTp3TsTp4并行负载不断增加执行时间固定固定时间加速比模型下的负载和执行时间情况 增大问题规模的办法使所有处理机保持忙碌状态，在问题扩大到与可用的计算能力匹配时，程序中的顺序部分就不再是瓶颈了。 当处理器数目n=1024，加速比Sn随α变化的情况如下：Sn’α102410141004993983

3.受限于存储器的加速比模型

1993年，由Sun和Ni提出。 大型科学计算和工程设计需要较大的存储空间，许多应用问题是存储器受限，而不是CPU受限或者I/O受限。 比如：在分布存储系统中常遇到，总存储容量随节点数线性增加，许多节点集合起来解一个大题。 基本思想：要在存储空间有限条件下解尽可能大的问题，这同样需要扩展工作负载，才能提供较高的加速比、较高的精度和较好的资源利用率。加速比可以表示如下：其中：

在单个处理机上顺序执行的工作负载与问题的规模或系统的规模无关，即：而G(n)反映的是存储容量增加n倍时并行工作负载增加的倍数。讨论：

1. G(n)=

1，即为固定负载的情况； 2. G(n)=n，即存储器增加n倍，负载也增加n倍，为固定时间的情形； 3. G(n)>n，计算负载的增加情况比存储器增加快，会有较高的加速比。比较三种加速比，对于相同的处理机数量，有：在受限于存储器的加速比模型下，负载和执行时间随系统中处理机数目n变化的情况如下图：WsWpWsWpWsWpWsWpWorkloadN1234ExecutionTimeNTsTp1TsTp2TsTp3TsTp4规模扩展的工作负载执行时间稍有增加受限于存储器的加速比模型下的负载和执行时间情况例： n维矩阵乘法：A*B=C，其中A、B、C都是n*n的方阵。为得到C的每一个元素需要进行n次乘法、n次加法，所以总的计算量为：（n+n)*n2=2n3。需要的存储量为3n2（两个源矩阵，一个结果矩阵）。如果n台计算机组成多计算机系统，则存储容量扩大n倍，那么矩阵的维数（原来为n)也可以增加了，设为N倍，那么加速比为多少？

解：存储容量变为：nM=n*3n2=3n3，而N维需要的存储量为3N2，计算量变为2N3，则有：

4.并行计算的应用模型随机器规模的增大，工作负载增长的模式如下图：工作负载（问题规模）nθ（指数）γ（线性）β（亚线性）α（常数）上图中：

采用受限于存储器的加速比模型中给出的公式，

θ曲线对应的G(n)=n1.5

γ曲线对应的G(n)=n

β曲线对应的G(n)=0.5n

α曲线对应的G(n)=1

则有加速比公式:

给定一个程序，假设Ws/Wp=0.4，那么效率为：相应的处理器数目—效率曲线如下图：效率nθ（指数）γ（线性）β（亚线性）α（常数）结论： 1.如果工作负载（问题规模）保持不变，那么效率E随机器规模的增大而迅速下降，其原因是开销h比机器规模增加得快，为了使效率保持在一定的水平上，我们可以按比例增大机器规模和问题规模。

2.如果工作负载按指数增长模式，效率要保持恒定或保持良好的加速比，必须使问题规模猛增才行，这样就会超过存储器或I/O限制，而问题规模只允许在计算机存储器可用的限度以内增长。并行计算机的应用模型如下图：通信界限存储器界限受限于存储器模型工作负载（问题规模）机器规模固定负载模型固定时间模型第二章加速比性能模型与可扩展性分析 2.1加速比性能分析

2.2可扩展性分析 2.2.1可扩展性

2.2.2可扩展性分析2.2可扩展性分析

2.2.1可扩展性 1.可扩展性与可编程性增加可扩展性增加可编程性分布存储的消息传递型多计算机共享存储型多处理机理想并行计算机 2.可扩展性指标 机器规模（n） 时钟频率（f） 问题规模（s） CPU时间（T） I/O需求（d） 存储容量（m） 通信开销（h） 计算机价格（c） 程序设计开销（p） 3.可扩展性的直观定义

对任意数量（n）的处理机和任意规模（s）的问题，若所有算法的系统效率E=1，则系统是可扩展的。 4.规模可扩展性

系统性能随处理机数量线性增长，包括：

处理速度和效率 存储速度和容量 互连带宽和时延 I/O速度和容量 软件开销规模可扩展性与空间局部性、时间局部性以及部件瓶颈都有关系。例子：

CrayY-MP：16台处理机范围可伸缩

CM-2： 8K-64K台处理机范围可伸缩

CM-5： 1024-16K台处理机范围可伸缩

KSR-1： 8-1088台处理机范围可伸缩 5.换代（时间）可扩展性

对系统各部分更换成新技术后，性能随之易扩展，要求算法、S/W均能兼容运行。 6.问题可扩展性

问题规模扩大时，系统仍能很好的运行，或说问题规模扩展到很大时，系统能在给定粒度下高效运行。

2.2.2可扩展性 1.恒等效率概念（Isoefficiency）

恒等效率定义为一个并行算法在并行计算机上实现时，为保持效率E固定所需的工作负载与机器规模n的相对关系。 设:

W=W（s）为工作负载，

h=h（s，n）为通信开销，它随s、n增加而增大。其中，s为问题规模，n为机器规模。 则效率可以表示为：

问题的关键在于W（s）与h（s，n）之间的相对增长速度。机器规模一定，开销h的增长比工作负载W要慢。因而，对一定规模的机器来说，效率会随问题规模增大而提高。所以，假若工作负载W随机器规模适当增加，那么就有希望保持效率不变。

对于已知的算法来说，为了保持恒定的效率，工作负载W可能需要对n以多项式或指数规律增长。不同的算法可能需要不同的工作负载增长速率以便在n增加时保持效率不致下降。 一般并行算法的恒定效率函数是n的多项式函数，即它们为O（nk），k1。n的幂越小，并行系统的可扩展性越大（系统包括算法和结构的组合）。

2.恒等效率函数并行程序执行时间Tp=(T1+T0)/p， 其中，T1为总工作负载串行执行时间，T0为多节点总通信延时，p为节点数。那么，加速比为：

而T1=Wtc，W为以操作次数计算的总工作负载，tc为每个操作的平均执行时间。如前面所述，工作负载W与开销h均可以表示成n与s的函数，所以，效率也可以表示如下：为了使E保持不变，工作负载W（s）应该与开销h(s,n)成比例增长，由此可以得出以下条件：如果工作负载W(s)与fE(n)一样快的增长，那么已知算法结构组合就能使效率保持恒定。这个结论和前面的结论是一致的。此时，W(s)与fE(n)是相同的，只要求出了W(s)的数量级，就可知道fE(n)了。为了得到恒等效率，只要使W(s)与h(s,n)同一个数量级就可以了。例1： 矩阵乘法的W(s)=O（s3）（其中s为维数），还设h（s，n）=O（nlogn+s2n0.5）。求fE(n)。

解：要满足W与h同数量级的条件，需要在两式中选出大的：例2：

W(s)=O（s3）， h（s，n）=O（nlogn+s2n1/3logn）。求fE(n)。

解：比较两个式子，选出较大的：例3：

W(s)=O（s3）， h（s，n）=O（nlogn+s3）。求fE(n)。

解：第二个式子显然成立，故例4：在n台处理机网格和超立方体计算机上分别计算1维s点的FFT，其工作负载W(s)=O（slogs），已知：

超立方体计算机上：h1（s，n）=O（nlogn+slogn），

网格计算机上：h2（s，n）=O（nlogn+sn0.5），

问哪一种扩展性好？

解：对超立方体计算机，对网格计算机， 为了得到恒等效率，对网格计算机，它的负载必须以指数增长，而超立方体的负载的增长不超过多项式增长速度，

结论：超立方体具有更好的可扩展性。 对于相同的效率E，设k=2，它们的机器规模-问题规模曲线可能如下图所示：问题规模s机器规模n网格超立方体第三章互连与通信 3.1互连网络的作用 3.2静态网络 3.3动态网络 3.4通信问题3.1互连网络的作用定义：由开关元件按一定拓扑结构和控制方式构成的网络以实现计算机系统内部多个处理机或多个功能部件间的相互连接。操作方式： 同步通信（SynchronousCommunication) 异步通信(AsynchronousCommunication)控制策略：

集中控制(Centralizedcontrol) 分布控制(Distributedcontrol)交换方式： 电路交换(Circuitswitching) 分组交换(Packetswitching)

Wormhole交换(Wormholeswitching)虫洞交换，数据包被分成许多小的流量控制单位（flit），在网络中以流水的方式传送。

网络拓扑结构：

静态网络(Staticnetwork) 动态网络(Dynamicnetwork)第三章互连与通信

3.1互连网络的作用

3.2静态网络

3.2.1静态网络的特点与指标 3.2.2典型的静态网络 3.3动态网络 3.4通信问题3.2静态网络

3.2.1静态网络的特点与指标

1.静态网络的特点

静态网络由点—点直接相连而成，这种连结方式在程序执行过程中不会改变。

如果用图来表示，结点代表开关，边代表通信链路，则

(1)结点间的链路无源，不能重构

(2)开关元件与处理机相连

(3)不直接相连结点间的通信需通过中间结点中转。 2.静态网络的指标

结点度：与结点相连接的边（链路或通道）数，表示节点所需要的I/O端口数，模块化要求结点度保持恒定。根据通道到结点的方向，结点度可以进一步表示为：

结点度=入度+出度 其中入度是进入结点的通道数，出度是从结点出来的通道数。

距离：与两个结点之间相连的最少边数。

网络直径：网络中任意两个结点间距离的最大值。

网络规模：网络中结点数，表示该网络功能连结部件的多少。

等分宽度：某一网络被切成相等的两半时，沿切口的最小边数称为该网络的等分宽度。

结点间的线长：两个结点间的线的长度。

对称性：从任何结点看，拓扑结构都一样，这种网络实现和编程都很容易。 结点是否同构。 通道是否有缓冲。

3.2.2典型的静态网络

1.线性阵列 对N个结点的线性阵列，有N-1条链路，直径为N-1（任意两点之间距离的最大值），度为2，不对称，等分宽度为1。 N很大时，通信效率很低。

线性阵列与总线的区别：

线性阵列：允许不同的源结点和目的结点对并发使用系统的不同部分。

总线：通过切换与其相连的许多结点来实现时分特性，同一时刻只有一对结点在传送数据。

2.环对N个结点的环，考虑相邻结点数据传送方向：

双向环：链路数为N，直径N/2，度为2，对称，等分宽度为2。比如KSR-1（1990）。

单向环：链路数为N，直径N-1，度为2，对称，等分宽度为2。 3.带弦环对上图中12个结点的带弦双向环，

结点度为3：链路数为18，直径4（比如红色结点），度为3，不对称，等分宽度为2。

结点度为4：链路数为24，直径3（比如红色结点），度为4，对称，等分宽度为8。度为3的带弦环度为4的带弦环 4.全链接 全链接是带弦环的一种特殊情形。全链接中的每个结点和其他结点之间都有单一的直接链路。如下图中8个结点的全链接： 有28条链路，直径为1，度为7，对称，等分宽度为16。 5.树形

4层的二叉树 一棵K层完全二叉树应有N=2K-1个结点，大多数结点的结点度为3，直径为2（K-1）（即右边任意一个叶子结点到左边任意一个叶子结点）。不对称，等分度为1。 由于结点度为常数，所以树是一种可扩展的系统结构。 树形的扩展：

带环树二叉胖树 这两种结构都可以缓解根结点的瓶颈问题。 6.星形

星形实际上是一种二层树（如右图）。有N个结点的星形网络，有N-1条链路，直径为2，最大结点度为N-1，非对称，等分宽度为1。 7.网格

有N个结点的rr网格（其中 )，有2N-2r条链路，直径为2（r-1)，结点度为4，非对称，等分宽度为r。 网格的变形：

a.Illiac网

有N个结点的rr网格（其中 )，有2N条链路，直径为r-1，结点度为4。

b.环形网（2D—Torus）

有N个结点的rr网（其中 )，有2N条链路，直径为2r/2，结点度为4，对称。

c.搏动式阵列（SystolicArray）

8.超立方体0-立方体1-立方体2-立方体3-立方体4-立方体 一个n-立方体由N=2n个结点构成，它们分布在n维上，每维有两个结点。直径为n，结点度为n，对称。由于结点度随维数线性增加，所以超立方体不是一种可扩展结构。

例子：

Intel的iPSC/1、iPSC/2、nCUBE 9.带环立方体 一个带环n-立方体由N=2n个结点环构成，每个结点环是一个有n个结点的环，所以结点总数为n2n个。直径通常为2n，结点度为3，对称。带环3-立方体 10.k元n-立方体网络4元3-立方体（隐藏的结点与连接没有画出) 在一个k元n-立方体网络中，结点的数目N=kn，即： 其中，k称为基数（radix），n称为维数（dimension）。

k元n-立方体的结点可以用基数为k的n位地址A=a0a1a2...

an来表示，其中ai代表第i维结点的位置。 传统的环网等价于4元2-立方体。第三章互连与通信

3.1互连网络的作用 3.2静态网络

3.3动态网络

3.3.1互连函数 3.3.2多级互联网络 3.4通信问题3.3动态网络 特点： 网络的开关元件有源，链路可通过设置这些开关的状态来重构。 只有在网络边界上的开关元件才能与处理机相连。

3.3.1互连函数

排列：N个数的每一种有确定次序的放置方法叫做一个N排列。

置换：把一个N排列变成另一个N排列的变换叫做N阶置换。 在有N个输入端和N个输出端的网络中，输入端和输出端的连接关系可以用置换来表示（输入端与输出端一一对应）。

一些常见的置换方式可以用下面的函数表示：1.恒等函数其中，Xn-1Xn-2

Xk

X0是PE的地址（通常为二进制）。n为3时的恒等函数的连接情形如下：0000010100111001011101110000010100111001011101112.方体函数（cube0，cube1，…，cuben-1)方体函数是由n个互连函数组成，其中0kn。比如，n为3时，3-立方体各结点地址如下：YZX010011110000111001100101000001010011100101110111000001010011100101110111Cube0:01234567000001010011100101110111000001010011100101110111Cube1:01234567000001010011100101110111000001010011100101110111Cube2:012345670000010100111001011101110000010100111001011101113.洗牌函数01234567洗牌函数的变形：

a.均匀洗牌（Shuffle-Exchange)

是洗牌函数与Cube0函数的组合。01234567：Cube0：洗牌b.第k个子洗牌即最低k位循环左移一位。c.第k个超洗牌即最高k-1位循环左移一位。0000010100111001011101110000010100111001011101114.逆洗牌函数012345670000010100111001011101110000010100111001011101115.蝶式012345676.PM2I函数（加减2i）

共有2n个互连函数，对N个结点的网络为例1：

N=8（8个结点），则n=log28=3，所以：i=0，1，2；j=0，1，…，7。

6个PM2I函数如下：PM2+0: (01234567）01234567PM2-0: (76543210）01234567PM2+1: (0246）（1357）01234567PM2-1: (6420）（7531）01234567PM2

2: (04）（15）（26）（37）0123456701234567例2：89101112131415上面的网络可以用四个PM2I函数表示。PM2+0: (012…15)PM2-0: (151413…0)

PM2

2: (04）（15）（26）（37） (48）（59）（610）（711） (812）（913）（1014）（1115） (120）（131）（142）（153）

3.3.2多级互连网络

1.多级网络的三要素

（1）开关单元：a个输入a个输出的开关单元记做aa的开关单元，其中，a是2的整数倍。常见的有2

2、44、88等。

根据开关单元功能的多少，2

2又可以分为两功能和四功能开关。如下图所示：0101直送0101交叉0101上播0101下播

（2）级间互连模式（InterStageConnection）： 均匀洗牌、蝶式、多路洗牌（比如四路洗牌即是把牌平均分成4份，然后4堆分别进行均匀洗牌）、纵横开关（CrossSwitch)及立方体连结等。 （3）控制方式

级控制：每级只有一个控制信号 单元控制：每个开关一个控制信号 部分级控制：几个开关合用一个控制信号

2.Ω网0123456701234567第0级第1级第2级 Ω网的特点：

开关单元：22四功能开关

ISC：洗牌变换+恒等变换

控制方式：采用单元控制方式。当目的地址编码从高位开始的第i位（从0开始）为0时，第i级的22开关的输入端与上输出端连接，否则输入端与下输出端连接。 例子： UIUC的Cedar IBM的RP3 NYU的Ultracomputer0123456701234567第0级第1级第2级

无阻塞的实现置换

π1=（07642）（13）（5）0123456701234567第0级第1级第2级 置换π2=（06473）（15）（2）

在开关F、G、H、I和J上发生阻塞FGHJI Ω网的特点(2)：

并不是所有的置换在Ω网中一次通过便可以实现。

Ω网是阻塞网络：出现冲突时，可以采用几次通过的方法来解决冲突。0123456701234567第0级第1级第2级

Ω网的广播功能：

001

8个输出端01第1级44开关构成的Ω网：多路洗牌

如16输入4路洗牌：网路级数为log416=2

234567891011121314150123456789101112131415第0级 Ω网的特点(3)：

当采用kk开关元件时，则可以定义k路洗牌函数来构造更大的级数为logkn的Ω网络。

3.蝶式网络（Butterflyswitchnetwork）

蝶式网络的开关不允许广播功能，它实际上是Omega网的一个子集。 两级6464的蝶式网络如下图所示：它采用16个88交叉开关构成，两级间采用8路洗牌连接。8888880...7888888第1级第0级8...1556...63.........078155663........................两级6464的蝶式网络

4.其他连接方式

总线 交叉开关第三章互连与通信 3.1互连网络的作用 3.2静态网络 3.3动态网络

3.4通信问题

3.4.1基本术语与性能指标 3.4.2寻径算法 3.4.3虚拟通道与死锁 3.4.4包冲突的解决 3.4.5维序寻径 3.4.6通信模式3.4通信问题

3.4.1基本术语与性能指标 1.消息、包和片

消息（Message）：是在多计算机系统的处理结点之间传递包含数据和同步消息的信息包。它是一种逻辑单位，可由任意数量的包构成。

包（Packet）：包的长度随协议不同而不同，它是信息传送的最小单位，64-512位。 片（Flit）：片的长度固定，一般为8位。 它们的相互关系如下图：包……消息包片据片头片尾片……顺序号数bbbbbbbb 2.互连网络

互连网络用来在多计算机系统的处理结点之间传递消息。互连网络的描述：

拓扑（Topology） 寻径算法（Routing） 流控制（FlowControl） 互连网络性能的两个重要指标： 传输时延（TransmissionLatency） 吞吐量（Throughput） 3.传输时延与吞吐量

一个消息的传输时延：从它在源结点进行发送初始化到它在目的结点完整的被接收所耗费的时间。

一个网络的传输时延：在一定条件下发送消息的平均时延。 网络的吞吐量：单位时间内网络所能传输的消息数目或长度。 4.传输时延的公式

其中，Ts称为建立时延，Tn称为网络时延，Tb称为阻塞时延。 它们具体定义如下：

建立时延Ts：一个消息在源结点和目的结点上装配和分解、从存储器拷贝到通信缓冲区以及正确性验证等所耗费的时间。它和机器本身的硬件、软件技术有关。

其中：

Tss称为源结点时延：从发送进程开始消息发送初始化到消息的头部进入网络所经历的时间。

Tsd称为目的结点时延：从消息的尾部到达目的结点到消息完全被接收进程接收所经历的时间。

网络时延Tn：消息头部从源结点进入网络到消息的尾部到达目的结点的时间间隔。

其中：

TpD称为结点时延：其中Tp是消息在它所经过的路径上的每个中间结点上的平均时延，D为中间结点或源结点与目的结点之间的距离。

L/B称为线路时延：其中L为消息长度，B为结点之间的通道带宽。

阻塞时延Tb：消息传递过程中其他所有可能的时延（主要原因是资源冲突）。 5.网络的拓扑结构

第一代并行计算机：HyperCube

第二代并行计算机：n—Mesh 6.网络的寻径算法

决定发送一个消息到其目的地所经过的路径。 可以分为：

最短路径算法 非最短路径算法 或者：

确定性算法：路径的选择只依赖于它所发送的消息的源结点和目的结点。

可适应算法：消息从结点A到结点B可以由几条不同的路径。 7.网络的流控制

当一个消息在网络中沿着某条路径传送时，互连网络如何来为它分配通道和缓冲器。

3.4.2寻径算法 我们介绍四种寻径方式： 存储转发（Store-and-Forward） 虚拟直通（Virtualcutthrough） 线路交换（CircuitSwitching） Wormhole交换（WormholeSwitching) 1.存储转发

当一个消息到达中间结点A时，A把整个消息放入其通信缓冲器中，然后在寻径算法的控制下选择下一个相邻结点B，当从A到B的通道空闲并且B的通信缓冲器可用时，把消息从A发向B。缺点：

每个结点必须对整个消息进行缓冲，缓冲器较大。 网络时延与发送消息所经历的结点数成正比 2.虚拟直通

中间结点没有必要等到整个消息全部被缓冲后再作出路由选择，只要消息的目的信息域可用后，就可以作出路由选择。

其中，Lh为消息头部开始到其目的信息域的长度，显然有L>>Lh，所以D的影响比较小。 而当通向下一结点的通道忙或结点的缓冲器非空闲时，必须把整个消息缓冲起来，这时和存储转发一样。 3.线路开关

在传递一个消息之前，就为它建立一条从源结点到目的结点的物理通道。在传递的全部过程中，线路的每一段都被占用，当消息的尾部经过网络后，整条物理链路才被废弃。

其中，Lc是为消息建立物理通路所传递的控制信息的长度。当L>>Lc时，D的影响较小。

缺点：

物理通道非共享 传输过程中物理通道一直被占用 4.Wormhole

Dally于1986年提出。 首先把一个消息分成许多片，消息的头片包含了这个消息的所有寻径信息。尾片是一个其最后包含了消息结束符的片。中间的片均为数据片。 片是最小信息单位。每个结点上只需要缓冲一个片就能满足要求。 用一个头片直接开辟一条从输入链路到输出链路的路径的方法来进行操作。每个消息中的片以流水的方式在网络中向前“蠕动”。每个片相当于Worm的一个节，“蠕动”以节为单位顺序的向前爬行。 当消息的头片到达一个结点A的寻径器后，寻径器根据头片的寻径信息立即做出路由选择：

（1）如果所选择的通道空闲而且所选择的结点B的通信缓冲器可用，那么这个头片就不必等待，直接通过结点A传向下一个结点B；随后的其它片跟着相应的向前“蠕动