1、高等计算机系统结构清华大学计算机科学与技术系高性能计算研究所郑纬民 教授2005年5月计算机科学与技术系研究生课程高等计算机系统结构课程介绍教材1Kai Huang著，王鼎兴、郑纬民、沈美明译，高等计算机系统结构并行性可扩展性可编程性，清华大学出版社。2Patterson D.A.，Hennesy J.L.，Computer Architecture：A Quantitative Approach，Morgan Kanfmann Publishers，1995。3 Patterson D.A.，Hennesy J.L.， Computer Organization & Design：The H
2、ardwareSoftware Interface。高等计算机系统结构第一章 高等计算机的核心技术并行处理第二章 加速比性能模型与可扩展性分析第三章 互连与通信第四章 划分与调度第五章 并行存储器系统第六章 Cache Coherence第七章 Memory Consistency第八章 指令级并行处理第九章 微处理器设计与实现方法第十十章 网格计算第一章 高等计算机的核心技术并行处理1.1 什么是并行处理1.1.1 并行处理定义1.1.2 并行性级别1.2 为什么要开发并行处理技术1.3 并行处理计算机结构沿革1.4 其它并行处理计算机技术1.1 什么是并行处理1.1.1 并行处理定义 并行
3、处理是指同时对多个任务或多条指令、或同时对多个数据项进行处理。 完成此项处理的计算机系统称为并行处理计算机系统。 同时性（simultaneity）两个或多个事件在同一时刻发生。 并发性（concurrency）两个或多个事件在同一时间间隔内发生。 流水特性（pipelining）在一个重叠的时间内所发生的流水事件。1.1.2 并行性级别 粒度（granularity）：衡量一个软件进程的计算量的度量。最简单的是指此程序段中的指令数。分细、中、粗三种。 按粒度的不同，并行性级别可以分为指令级、循环级、过程级、子程序级和作业级等不同的层次。它们对应的计算粒度可以为细粒度、中粒度和粗粒度。如下：1
4、.指令级并行 典型细粒度，一般少于20条指令。借助优化编译器自动检测并行性，将源代码变成运行时系统能识别的并行形式。2.循环级并行 典型循环含少于500条指令，由于有些循环操作在连续迭代中并不相关，易于向量化，是在并行机或向量机上运行的最优程序结构。递归循环的并行化比较困难。向量处理由优化编译器在循环级开发，仍属于细粒度计算。3.过程级并行 中粒度并行，指令少于2000条，分析过程间的并行性比细粒度要困难。有时需要重新设计程序，并要编译器的支持。SPMD、多任务处理属于这一层。4.子程序级并行 （粗）中粒度并行，几千条指令，常在message passing多计算机上以SPMD或MPMD方式执
5、行。并行性主要由算法设计人员与程序员开发。5.作业级并行 粗粒度并行，数万条指令，常由加载程序和操作系统处理这类并行性，靠算法有效性来保证。一般说来：细粒度：用并行化或向量化编译器来开发，共享变量通信支持。 中粒度：靠程序员和编译器一起开发，共享变量通信。 粗粒度：取决于操作系统和算法的效率，消息传递通信。例子：共享存储型多处理机上执行：L1:DO10I=1, NL2:A(I)=B(I)+C(I)L3:10 ContinueL4:SUM=0L5:DO20J=1, NL6:SUM=SUM+A(J)L7:20Continue假设：L2，L4，L6每行要用一个机器周期。L1，L3，L5，L7所需时间
6、可以忽略。所有数组已经装入主存，程序已装入Cache中（取指令和加载数据可以忽略不计）。忽略总线争用或存储器访问冲突。上面的程序实际上把数组B(I)和C(I)相加，最后得到一个总和。共享存储多处理机结构如下图：P1P2Pm系统互连I/OSM1SMm处理机共享存储器在单机系统中，2N个周期可以完成上述的操作：I循环中执行N次独立迭代需要N个周期；J循环中执行N次递归迭代也需要N个周期。在共享存储型的多处理机系统上：假设有M台处理机，可以将循环分成M段，每段有L = N/M个元素。代码如下所示：Doallk= 1, MDo 10 I= L(k-1) + 1 , kLA(I) = B(I) +C(I
7、)10ContinueSUM(k)=0Do 20 J=1 , LSUM(k)= SUM(k)+A(L(k-1)+J)20ContinueEndall分段的I循环可以在L个周期中完成；分段的J循环在L个周期中产生M个部分和。所以产生所有的M个部分和共需要2L个周期（还需要将这些部分和合并）。假设经过共享存储器的处理机之间的每次通信操作需要k个周期。设N=32，M=8，则经过2L（即8个周期）后在8台处理机上各有一个部分和，还需要8个数相加。为了合并部分和，可以设计一个l层的二进制加法树，其中l=log2M，加法树用l(k+1)个周期从树叶到树根顺序合并M个部分和，如下：二进制加法树：所以，多处理
8、机系统需要周期MkMNklL2log)1(2)1(2才能得到最终的结果。假定数组中有N=220个元素，顺序执行需要2N=221个机器周期，假设机器间通信的开销平均值为k = 200个周期，则在M=256台处理机的并行执行需要：%6.832562142149800298001608282012256log20125622log)1(22113132202效率加速比周期MkMN第一章 高等计算机的核心技术并行处理1.1 什么是并行处理1.2 为什么要开发并行处理技术1.3 并行处理计算机结构沿革1.4 其它并行处理计算机技术1.2 为什么要开发并行处理技术对单用户，可以提高加速比（Speedup
9、Oriented)；对多用户，可以提高吞吐率（Throughput Oriented).对不同的需求我们可以做需求分析如下：1.天气预报 1990年10次台风登陆，福建、浙江两省损失79亿元，死亡950余人。 天气预报模式为非线性偏微分方程，预报台风暴雨过程，计算量为10141016次浮点运算，需要10GFlops100GFlops的巨型机。 用途：局部灾害性天气预报。2.石油工业 地震勘探资料处理 油藏数值模拟 测井资料处理 地震勘探由数据采集、数据处理和资料解释三阶段组成。 目前采用的三维地震勘探比较精确的反映地下情况，但数据量大，处理周期长。 100平方公里的三维勘探面积，道距25米，6
10、0次覆盖，6秒长记录，2毫秒采样，一共采集2.881010个数据，约为116GB。 叠加后数据为4.8108个数据。用二维叠前深度偏移方法精确的产生地下深度图像，需要进行251012FLOP，采用100MFLOPs机器计算250天，1GFLOPs机计算25天，10GFLOPs机器35分。考虑到机器持续速度常常是峰值速度的10-30%，所以需要100GFlops的机器。Cray T932/32约为60GFLOPs。3.航空航天 研究三维翼型对飞机性能的影响。数值模拟用时间相关法解Navier-Stoker方程，网格分点为1204050，需内存160MB，6亿计算机上解12小时，如果在数分钟内完成
11、设计，则需要千亿次计算机。4.重大挑战性课题需求（图3.5） 计算空气动力学：千亿次/秒（1011） 图像处理： 百亿次/秒（1010） AI： 万亿次/秒（1012）5.核武器 核爆炸数值模拟，推断出不同结构与不同条件下核装置的能量释放效应。压力：几百万大气压温度：几千万摄氏度能量在秒级内释放出来。 设计一个核武器型号，从模型规律、调整各种参数到优选，需计算成百上千次核试验。 Los Alamos实验室要求计算一个模型的上限为8-10小时。 千万次机上算椭球程序的计算模型需要40-60CPU小时。 二维计算，每方向上网格点数取100，二维计算是一维的200倍，三维是一维的33000倍。若每维
12、设1000网格点，则三维计算是一维的几十万倍之多。此时对主存储器容量要数十、数百亿字单元（64位）。 另外还有I/O能力的要求，可视化图形输出。6.解决方案 只有开发并行处理技术才能满足要求：3T performance：Teraflops of Computing PowerTerabyte of Main MemoryTerabyte/s of I/O bandwidth第一章 高等计算机的核心技术并行处理1.1 什么是并行处理1.2 为什么要开发并行处理技术1.3 并行处理计算机结构沿革1.3.1 向量机与多向量机1.3.2 SIMD计算机1.3.3 Shared-Memory Mult
13、iprocessors1.3.4 Distributed-Memory Multiprocessors1.3.5 四类实用的并行系统1.4 其它并行处理计算机技术1.3 并行处理计算机结构沿革1.3.1 向量机与多向量机 向量机的结构如下图：ScalarFunctionalpipelinesScalarControlunitscalar processorscalar instructionMain Memory(Program and data)MassStorageHostComputerI/O(user)VectorControlunitvectorregistersvector pro
14、cessorcontrolVectorFunctionalpipelinesVectorFunctionalpipelinesvectorinstruction程序和数据从Host进入主机指令先在Scalar control unit译码，如是标量或控制操作指令，则在标量功能流水部件种执行。如果是向量指令，则进入向量控制部件。register-to-register：Cray seriesFujitsu VP2000 seriesmemory-to-memory：Cyber 205向量化。多向量机发展过程：CDC7600(CDC,1970)CDC Cyber205(Levine,1982)Me
15、mory-MemoryCray 1(Russell,1978)register-registerETA 10(ETA,Inc,1989)Cray Y-MPCray Research1989FujitsuNECHitachi ModelsCray MPPCray Research1993其中：Cray Y-MP, C90： Y-MP有2，4，8个处理器，而C90有16个处理单元（PE），处理速度16GFlops。Convex C3800 family： 8个处理器，4GB主存储器， Rerkperformance 为2GFlops。1.3.2 SIMD计算机 SIMD计算机的结构如下图：Cont
16、rol UnitProc 0Mem 0Proc 1Mem 1Proc N-1Mem N-1PE0PE1PE N-1InterConnection NetworkMasPar MP-1： 可有1024，4096，16384个处理器。在16K PEs，32位整数运算，16KB局部存储器模块的配置下，可达26000MIPS，单精度浮点运算1.5GFlops，双精度浮点运算650MFlops。CM-2： 65536个处理单元，1Mbit/PE。 峰值速率为28GFlops，持续速率5.6GFlops。SIMD计算机发展过程图如下：Illiac IV(1968)GoodYear MPP(1980)BSP
17、(1982)MasPar MP1(1990)IBM GF/11(1985)DAP 610(AMT，Inc.1987)CM2(1990)CM5(1991)1.3.3 Shared-Memory Multiprocessors UMA(Uniform-memory-access) model：物理存储器被所有处理机均匀共享，所有处理机对所有存储字具有相同的存取时间。P0I/OP1SM1PnSMnInterConnection Network(Bus、Crossbar、Multistage Network)处理器共享存储器NUMA(NonUniform-memory-access) model：访问
18、时间随存储字的位置不同而变化。P1PnLMnInter-Connection NetworkLM1P2LM2COMA(Cache-only memoryarchitecture)： 只用高速缓存的多处理机 远程高速缓存访问则借助于分布高速缓存目录进行。PDInterConnection NetworkdistributedcachedirectoriesCPDCPDCKendall Square Researchs KSR-1Shared-Memory Multiprocessors发展过程如下：C mmp(cmu,1972)IllinoisCedar(1987)UltraComputerNY
19、U(1983)Fujitsu VPP500(1992)IBM RP3(1985)BBN Butterfly(1989)stanford/Dash(1992)KSR-1(1990)1.3.4 Distributed-Memory MultiprocessorsPMessage-passinginterconnection network(Mesh,ring,torus,hypercube,cube,cycle)MPMPMPPPMMMMPMPMPMP例子：Intel Paragon XP/s：采用50MHz的i860处理器，每个节点16-128MB主存储器，采用2D-Mesh互连，浮点运算5-30
20、0GFlops，或2.8-160Gips。nCube 2S Model 80：有4096-8192个PE，主存储器16384-262144MB，浮点运算163800-34000MFlops，整数运算61000-123000MIPS。Cosmic Cube(1981)nCube-2/6400(1990)Mosaic(1992)Intel paragon(1992)MIT/J machine(1992)intel iPSCs(1983)Distributed-Memory multiprocessors发展进程：1.3.5 四类实用的并行系统1.向量机与多向量机硬、软件技术相对成熟、应用广泛、市场
21、占有率高。很难达到3T performance来解决Grand Challenge 问题。下面图表说明了这一类机器的发展过程。GFlops100100.11976 1979 1982 1985 1988 1991 1994YearCray1/10.16GFCray X-MP/20.24GFCray 2/41.9GFCray Y-MP/82.6GFCray J916/163.2GFCray C 916/1616GFCray T932/3260GF2.对称式多处理机SMPSMP：Symmetric MultiProcessors Shared Memory multiProcessors Smal
22、l size MultiProcessors 处理机之间无主从之分，对外有相同的访问权，都有执行操作系统核心和I/O服务程序的能力。 共享存储器、统一地址空间，系统编程比较容易。 CPU可多至16台左右，做服务器用，市场前景好。典型的SMP有：Sun SPARC server 1000Sun SPARC center 2000SGI Power ChallengeSGI Power Challenge L：2-6CPU，1.8GFlopsSGI Power Challenge XL：2-18CPU，5.4GFlops*64位MIPS chip，每周期指令发射数为4*8路交错主存、带宽为1.2G
23、B/s *I/O带宽320MB/s（每个控制器），配置4个可达1.2GB/s3.MPP系统（分布存储） 多于100个PE，消息传递，分布存储； 可扩展，峰值可达3T performance； 贵，市场有限； 持续速度是峰值速度的3-10%； 可解决某些Grand Challenge问题，是国家综合实力的象征。4.机群系统NOW：Network Of WorkstationsCOW：Cluster Of Workstations特点： 投资风险小，软件财富继承性好； 可构成异构系统，资源利用率高； 通信开销大。一种典型的机群系统结构如下：CPU MemoryI/OCPU MemoryI/OCPU
24、 MemoryI/OI/OI/OI/OMemoryMemoryMemoryCPUCPUCPUNetwork第一章 高等计算机的核心技术并行处理1.1 什么是并行处理1.2 为什么要开发并行处理技术1.3 并行处理计算机结构沿革1.4 其它并行处理计算机技术1.4 其它并行处理计算机技术1.数据流技术data flow以数据驱动机制代替控制流机制当功能部件输入端的操作数可用时就启动执行；可开发程序中所有的并行性，但费用昂贵，实际性能与功能部件数量、存储器带宽以及挂起和可用部件相匹配的程度有关。如：MIT的MonSoos，*T ETL的Sigma1，EM52.多线程每台处理机有多个控制线程，同时运
25、行多个现场，是实现时延隐藏的一种有效机制。比如:Tera，Alewife成本高。3.逻辑推理与规约结构逻辑推理：日本第五代机，面向逻辑语言、执行速度慢，软件与程序设计环境欠丰富。规约结构：Alice，PGR，面向函数语言，执行速度慢，软件与环境欠丰富。4.关键技术并行算法（数值算法与非数值算法）并行计算模型互连与通信并行存储技术同步与时延隐藏技术并行I/O划分、调度与负载平衡优化编译并行调试工具与环境5.美国的主要行动（1）组织基于NSF的国家科学计算联盟（National Computational Science Alliance）建立国家科技网（Grid）：97.11开始，五年计划，总经
26、费3.4亿美元。目标：使美国在全国范围内的元计算机（网上的计算机可作为一个整体看待）达到实用水平。 为在桌面上解决计算科学与工程时提供一个有力的解题环境。 解决基于元计算环境的并行、分布、协作和immersive等问题。 UIUC、San Diago组织实施。（2）DOE支持的ASIC计划（Accelerated Strategic Computing Initiative）保证在21世纪美国在核研究和核储备继续处于领先地位。以Los Alamos，Sandia和Lawrence Livermore三个国家实验室为核心，组成遍及美国不同地区的“拆墙合作”。为建立Virtual Laborato
27、ry奠定基础。研制出超级计算机系统：万亿次量级的计算机，2的50次幂（约千万亿）容量的数据库系统。提供高效、好用的计算环境。能实现基于网络的、分布式协同工作环境。能提供高效的、点对点的计算设施。在CORBA的环境下有效的把计算平台和有关应用进行系统集成。负载平衡。可裁剪性。6.Models of Parallel Computers(1960s-1980s)DataMIMDSIMDInstructionImplicationMultiple Data StreamsMultiple Data StreamsSingle Instruction StreamsMultiple Instructi
28、on StreamsSingle Program;Lots of data to havelots of parallelism;Programming is simplersince communicationis always synchronized;Communications seperatefrom computation sinceinstructions distinctMay be many ProgramsLots of programs to havelots of parallelismH/W construction is simplerusing off-the-s
29、helfuniprocessorscommunication merged with computationImplicationIlliva IV、CM-2、MasPar Cray X-MP、Sequent、nCube7.一些缩写SPMDSingle Program Multiple DataStreamMPMDMultiple Program MultipleDataStreamSIMDSingle Instruction MultipleDataMIMDMultiple Instruction MultipleData网格是通过网络提供综合计算机资网格是通过网络提供综合计算机资源和服务的
30、基础设施源和服务的基础设施公用网络，计算机，存储。应用服务的支柱提供公用网络，计算机，存储。应用服务的支柱提供不间断的，无限的处理能力。不间断的，无限的处理能力。Mainframe70sDistributed Computing21st CenturyInternetLate 90sPC80sClient/Server90s什么是网格？什么是网格？Ian Foster 关于网格的三个判断标准关于网格的三个判断标准“What is Grid, a Guide for the Perplexed”Grid Today, July 17, 2002, 网格的判断标准网格的判断标准 资源的协调而不仅仅
31、是集中控制。资源的协调而不仅仅是集中控制。 使用标准的，使用标准的， 开放式的，开放式的， 通用通用 的协议和接口。的协议和接口。 提供安全可靠、高质量的服务提供安全可靠、高质量的服务。互联网服务提供方互联网服务提供方服务网格服务网格Virtualization of servicesDynamic service provisioningSelf-healing of servicesIntegratable with Enterprise applications企业间及合作伙伴企业间及合作伙伴合作网格合作网格DOE, UK Grid & DoD协同共享公用的数据中心动态的提供资源企业内部
32、企业内部网格及其三个阶段网格及其三个阶段time共享程度共享程度企业网格企业网格Toshiba, TI, GMCluster-to-cluster sharing managementReliable file transfer & stagingUser account mapping, Firewalls, Kerboros1996200020042008网格应用的挑战网格应用的挑战计算机制造业计算机制造业机械制造业机械制造业 Project fairshare flexible lease 适度的规模 本地管理 Clearcase sup NFS load balance WAN fil
33、e sync Optimal use WAN lic sharing Borrow / Reclaim Service domains生命科学生命科学可靠文件传输 PDM 集成 自动的工具 最佳的应用 Data source sync Data set lifecycle Data Cache Data Pipeline Workflow mgmt Capacity workload Large number of jobs 政府与教育政府与教育 Efficient xfer data replication NUMA Co-alloc Advance Rsv金融金融 Workflow business unit silos Deadline Messaging data caching计算机计算机数据数据软件软件
