清华大学计算机科学与技术系高性能计算研究所 郑纬民 教授 2005年5月 计算机科学与技术系研究生课程 高等计算机系统结构 清华大学计算机科学与技术系高性能计算研究所 郑纬民 教授 2005年5月

高等计算机系统结构课程介绍 教材 1．Kai Huang著，王鼎兴、郑纬民、沈美明译，高等计算机系统结构　并行性　可扩展性　可编程性，清华大学出版社。 2．Patterson 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 Hardware／Software Interface。

高等计算机系统结构 第一章 高等计算机的核心技术——并行处理 第二章 加速比性能模型与可扩展性分析 第三章 互连与通信 第四章 划分与调度 第一章 高等计算机的核心技术——并行处理 第二章 加速比性能模型与可扩展性分析 第三章 互连与通信 第四章 划分与调度 第五章 并行存储器系统 第六章 Cache Coherence 第七章 Memory Consistency 第八章 指令级并行处理 第九章 微处理器设计与实现方法 第十章 网格计算

第一章 高等计算机的核心技术——并行处理 1.1 什么是并行处理 1.2 为什么要开发并行处理技术 1.3 并行处理计算机结构沿革 第一章 高等计算机的核心技术——并行处理 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.子程序级并行 （粗）中粒度并行，几千条指令，常在message passing多计算机上以SPMD或MPMD方式执行。并行性主要由算法设计人员与程序员开发。

5.作业级并行 粗粒度并行，数万条指令，常由加载程序和操作系统处理这类并行性，靠算法有效性来保证。 一般说来： 细粒度：用并行化或向量化编译器来开发，共享变量通信支持。 中粒度：靠程序员和编译器一起开发，共享变量通信。 粗粒度：取决于操作系统和算法的效率，消息传递通信。

所有数组已经装入主存，程序已装入Cache中（取指令和加载数据可以忽略不计）。 忽略总线争用或存储器访问冲突。 例子：共享存储型多处理机上执行： 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)相加，最后得到一个总和。 共享存储多处理机结构如下图： 处理机 共享存储器 …… P1 Pm 系统互连 …… I/O SM1 SMm 共享存储器

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

Doall k= 1, M Do 10 I= L(k-1) + 1 , kL A(I) = B(I) +C(I) 10 Continue SUM(k)=0 Do 20 J=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 为什么要开发并行处理技术 对单用户，可以提高加速比（Speedup Oriented)； 对多用户，可以提高吞吐率（Throughput Oriented). 对不同的需求我们可以做需求分析如下：

1.天气预报 1990年10次台风登陆，福建、浙江两省损失79亿元，死亡950余人。 天气预报模式为非线性偏微分方程，预报台风暴雨过程，计算量为1014—1016次浮点运算，需要10GFlops—100GFlops的巨型机。 用途：局部灾害性天气预报。

2.石油工业 地震勘探资料处理 油藏数值模拟 测井资料处理 地震勘探由数据采集、数据处理和资料解释三阶段组成。 目前采用的三维地震勘探比较精确的反映地下情况，但数据量大，处理周期长。 100平方公里的三维勘探面积，道距25米，60次覆盖，6秒长记录，2毫秒采样，一共采集2.881010个数据，约为116GB。

叠加后数据为4.8108个数据。用二维叠前深度偏移方法精确的产生地下深度图像，需要进行251012FLOP，采用100MFLOPs机器计算250天，1GFLOPs机计算25天，10GFLOPs机器35分。考虑到机器持续速度常常是峰值速度的10-30%，所以需要100GFlops的机器。Cray T932/32约为60GFLOPs。

3.航空航天 研究三维翼型对飞机性能的影响。数值模拟用时间相关法解Navier-Stoker方程，网格分点为1204050，需内存160MB，6亿计算机上解12小时，如果在数分钟内完成设计，则需要千亿次计算机。

4.重大挑战性课题需求（图3.5） 计算空气动力学：千亿次/秒（1011） 图像处理： 百亿次/秒（1010） AI： 万亿次/秒（1012）

5.核武器 核爆炸数值模拟，推断出不同结构与不同条件下核装置的能量释放效应。 压力： 几百万大气压 温度： 几千万摄氏度 能量在秒级内释放出来。 设计一个核武器型号，从模型规律、调整各种参数到优选，需计算成百上千次核试验。 Los Alamos实验室要求计算一个模型的上限为8-10小时。

千万次机上算椭球程序的计算模型需要40-60CPU小时。 二维计算，每方向上网格点数取100，二维计算是一维的200倍，三维是一维的33000倍。若每维设1000网格点，则三维计算是一维的几十万倍之多。此时对主存储器容量要数十、数百亿字单元（64位）。 另外还有I/O能力的要求，可视化图形输出。

6.解决方案 只有开发并行处理技术才能满足要求： 3T performance： Teraflops of Computing Power Terabyte of Main Memory Terabyte/s of I/O bandwidth

第一章 高等计算机的核心技术——并行处理 1.1 什么是并行处理 1.2 为什么要开发并行处理技术 1.3 并行处理计算机结构沿革 第一章 高等计算机的核心技术——并行处理 1.1 什么是并行处理 1.2 为什么要开发并行处理技术 1.3 并行处理计算机结构沿革 1.3.1 向量机与多向量机 1.3.2 SIMD计算机 1.3.3 Shared-Memory Multiprocessors 1.3.4 Distributed-Memory Multiprocessors 1.3.5 四类实用的并行系统 1.4 其它并行处理计算机技术

1.3 并行处理计算机结构沿革 1.3.1 向量机与多向量机 向量机的结构如下图：

scalar processor vector instruction Scalar Functional pipelines vector processor Vector Control unit control scalar instruction Scalar Control unit vector registers Vector Functional pipelines …… Main Memory (Program and data) Vector Functional pipelines Mass Storage Host Computer I/O(user)

程序和数据从Host进入主机 指令先在Scalar control unit译码，如是标量或控制操作指令，则在标量功能流水部件种执行。如果是向量指令，则进入向量控制部件。 register-to-register： Cray series Fujitsu VP2000 series memory-to-memory： Cyber 205 向量化。

多向量机发展过程： CDC Cyber205 (Levine,1982) Memory-Memory ETA 10 (ETA,Inc,1989) CDC7600 (CDC,1970) Cray Y-MP Cray Research 1989 Cray MPP Cray Research 1993 Cray 1 (Russell,1978) register-register Fujitsu NEC Hitachi Models

其中： Cray Y-MP, C90： Y-MP有2，4，8个处理器，而C90有16个处理单元（PE），处理速度16GFlops。 Convex C3800 family： 8个处理器，4GB主存储器， Rerkperformance 为2GFlops。

InterConnection Network 1.3.2 SIMD计算机 SIMD计算机的结构如下图： Control Unit PE0 PE1 PE N-1 Proc 0 Proc 1 Proc N-1 …… Mem 0 Mem 1 Mem N-1 InterConnection Network

MasPar MP-1： 可有1024，4096，…，16384个处理器。在16K PEs，32位整数运算，16KB局部存储器模块的配置下，可达26000MIPS，单精度浮点运算1.5GFlops，双精度浮点运算650MFlops。 CM-2： 65536个处理单元，1Mbit/PE。 峰值速率为28GFlops，持续速率5.6GFlops。 SIMD计算机发展过程图如下：

DAP 610 (AMT，Inc.1987) GoodYear MPP (1980) CM2 (1990) CM5 (1991) Illiac IV (1968) MasPar MP1 (1990) BSP (1982) IBM GF/11 (1985)

1.3.3 Shared-Memory Multiprocessors UMA(Uniform-memory-access) model： 物理存储器被所有处理机均匀共享，所有处理机对所有存储字具有相同的存取时间。 P0 P1 …… Pn 处理器 InterConnection Network (Bus、Crossbar、Multistage Network) 共享存储器 I/O SM1 SMn ……

NUMA(NonUniform-memory-access) model： 访问时间随存储字的位置不同而变化。 LM1 P1 LM2 P2 Inter- Connection Network …… …… …… LMn Pn

COMA(Cache-only memoryarchitecture)： 只用高速缓存的多处理机 远程高速缓存访问则借助于分布高速缓存目录进行。 Kendall Square Research’s KSR-1 InterConnection Network D D D C C C distributed cache directories …… P P P

Shared-Memory Multiprocessors发展过程如下： stanford/Dash (1992) Illinois Cedar (1987) Fujitsu VPP500 (1992) KSR-1 (1990) C mmp (cmu,1972) IBM RP3 (1985) UltraComputer NYU (1983) BBN Butterfly (1989)

1.3.4 Distributed-Memory Multiprocessors …… M P Message-passing interconnection network (Mesh,ring,torus,hypercube,cube,cycle) P M …… …… M P P M P P P …… M M M

例子： Intel Paragon XP/s： 采用50MHz的i860处理器，每个节点16-128MB主存储器，采用2D-Mesh互连，浮点运算5-300GFlops，或2.8-160Gips。 nCube 2S Model 80： 有4096-8192个PE，主存储器16384-262144MB，浮点运算163800-34000MFlops，整数运算61000-123000MIPS。

Distributed-Memory multiprocessors发展进程： nCube-2/6400 (1990) Cosmic Cube (1981) Intel paragon (1992) intel iPSC’s (1983) Mosaic (1992) MIT/J machine (1992)

1.3.5 四类实用的并行系统 1.向量机与多向量机 硬、软件技术相对成熟、应用广泛、市场占有率高。很难达到3T performance来解决Grand Challenge 问题。 下面图表说明了这一类机器的发展过程。

GFlops 100 Cray T932/32 60GF Cray C 916/16 16GF 10 Cray J916/16 3.2GF Cray Y-MP/8 2.6GF Cray 2/4 1.9GF Cray X-MP/2 0.24GF Cray1/1 0.16GF 0.1 1976 1979 1982 1985 1988 1991 1994 Year

2.对称式多处理机SMP SMP：Symmetric MultiProcessors Shared Memory multiProcessors Small size MultiProcessors 处理机之间无主从之分，对外有相同的访问权，都有执行操作系统核心和I/O服务程序的能力。 共享存储器、统一地址空间，系统编程比较容易。 CPU可多至16台左右，做服务器用，市场前景好。

典型的SMP有： Sun SPARC server 1000 Sun SPARC center 2000 SGI Power Challenge SGI Power Challenge L：2-6CPU，1.8GFlops SGI Power Challenge XL： 2-18CPU，5.4GFlops *64位MIPS chip，每周期指令发射数为4 *8路交错主存、带宽为1.2GB/s *I/O带宽320MB/s（每个控制器），配置4个可达1.2GB/s

3.MPP系统（分布存储） 多于100个PE，消息传递，分布存储； 可扩展，峰值可达3T performance； 贵，市场有限； 持续速度是峰值速度的3-10%； 可解决某些Grand Challenge问题，是国家综合实力的象征。

4.机群系统 NOW：Network Of Workstations COW：Cluster Of Workstations 特点： 投资风险小，软件财富继承性好； 可构成异构系统，资源利用率高； 通信开销大。 一种典型的机群系统结构如下：

CPU Memory I/O I/O Memory CPU CPU Memory I/O I/O Memory CPU …… …… CPU Memory I/O I/O Memory CPU Network

第一章 高等计算机的核心技术——并行处理 1.1 什么是并行处理 1.2 为什么要开发并行处理技术 1.3 并行处理计算机结构沿革 1.4 其它并行处理计算机技术

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

2.多线程 每台处理机有多个控制线程，同时运行多个现场，是实现时延隐藏的一种有效机制。 比如: Tera，Alewife 成本高。

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

4.关键技术 并行算法（数值算法与非数值算法） 并行计算模型 互连与通信 并行存储技术 同步与时延隐藏技术 并行I/O 划分、调度与负载平衡 优化编译 并行调试 工具与环境

5.美国的主要行动 （1）组织基于NSF的国家科学计算联盟 （National Computational Science Alliance） 建立国家科技网（Grid）：97.11开始，五年计划，总经费3.4亿美元。 目标：使美国在全国范围内的元计算机（网上的计算机可作为一个整体看待）达到实用水平。 为在桌面上解决计算科学与工程时提供一个有力的解题环境。 解决基于元计算环境的并行、分布、协作和immersive等问题。 UIUC、San Diago组织实施。

（2）DOE支持的ASIC计划 （Accelerated Strategic Computing Initiative） 保证在21世纪美国在核研究和核储备继续处于领先地位。 以Los Alamos，Sandia和Lawrence Livermore 三个国家实验室为核心，组成遍及美国不同地区的“拆墙合作”。 为建立Virtual Laboratory奠定基础。 研制出超级计算机系统：万亿次量级的计算机，2的50次幂（约千万亿）容量的数据库系统。 提供高效、好用的计算环境。

能实现基于网络的、分布式协同工作环境。 能提供高效的、点对点的计算设施。 在CORBA的环境下有效的把计算平台和有关应用进行系统集成。 负载平衡。 可裁剪性。

6.Models of Parallel Computers(1960s-1980s) SIMD MIMD Data Multiple Data Streams Multiple Data Streams Instruction Single Instruction Streams Multiple Instruction Streams Implication Single Program; May be many Programs Lots of data to have lots of parallelism; Lots of programs to have lots of parallelism Programming is simpler since communication is always synchronized; H/W construction is simpler using off-the-shelf uniprocessors Communications seperate from computation since instructions distinct communication merged with computation Implication Illiva IV、CM-2、MasPar Cray X-MP、Sequent、nCube

7.一些缩写 SPMD——Single Program Multiple DataStream MPMD——Multiple Program Multiple DataStream SIMD——Single Instruction Multiple Data MIMD——Multiple Instruction Multiple

Distributed Computing 什么是网格？ Mainframe 70s Distributed Computing 21st Century Internet Late 90s PC 80s Client/Server 90s 网格是通过网络提供综合计算机资源和服务的基础设施 公用网络，计算机，存储。应用服务的支柱提供不间断的，无限的处理能力。

Ian Foster 关于网格的三个判断标准 “What is Grid, a Guide for the Perplexed” Grid Today, July 17, 2002, 网格的判断标准 资源的协调而不仅仅是集中控制。 使用标准的， 开放式的， 通用 的协议和接口。 提供安全可靠、高质量的服务。

网格及其三个阶段 服务网格 合作网格 企业网格 共享程度 DOE, UK Grid & DoD Toshiba, TI, GM Virtualization of services Dynamic service provisioning Self-healing of services Integratable with Enterprise applications 企业间及合作伙伴 合作网格 DOE, UK Grid & DoD 协同共享 公用的数据中心 动态的提供资源 共享程度 企业网格 Toshiba, TI, GM Cluster-to-cluster sharing management Reliable file transfer & staging User account mapping, Firewalls, Kerboros 互联网服务提供方 企业内部 time 1996 2000 2004 2008

网格应用的挑战 计算机制造业 机械制造业 生命科学 政府与教育 金融 计算机 数据 软件 Project fairshare flexible lease 适度的规模 本地管理 Clearcase sup NFS load balance WAN file 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 计算机 数据 软件