并行处理与体系结构
任课教师：季振洲
联系方式：新技术楼 614房间
电话,86402036
课程背景
?并行处理技术已经成为现代计
算机科研与发展的关键技术；
?其推动力来自实际应用对高性
能、低价格和持续生产力日益
增长的要求
?计算机原理的概念
?计算机体系结构的概念
?(Amdahl)；
?并行主要研究,
?先行方式、流水方式、向量化；
?并发性、同时性；
?数据并行性、划分；
?交叉、重叠、多重性、重复；
?时间共享、空间共享；
?多任务处理、多道程序、多线程
方式和分布式计算。
第一章 并行计算机模型
??1 计算技术的现状
??2 多处理机和多计算机
??3 多向量机和 SIMD计算机
??4 并行计算机的抽象模型
??5 可扩展的范围和设计
?1 计算技术的现状
?一、并行技术的出现
? 二、现代并行计算机的组成
?涉及 6个问题,
?1.计算问题
?现实生活中对问题要求快速而精确地
求解推动了计算机的广泛使用。
? 科学技术中的数值计算问题
? 人工智能 (AI)问题
?2.算法和数据结构
? 并行计算问题中的运算和通信，需要
各种专门的算法和数据结构。
? 符号处理,
? 存在的问题,
?3.硬件资源
? 处理机、存储器和外围设备组成了计
算机系统的硬件核心
? 外围设备可以直接或通过局域网和广
域网与主机相连
?4.操作系统
? 管理用户程序执行过程中的资源分配
和再分配。
? 映射是一种算法结构与硬件结构相匹
配的双向过程。
? 并行操作系统的映射
? 算法和数据结构到机器结构的映射包括处
理机调度、存储器映象、处理器间的通信
等。
? 这些问题通常都与系统结构有关。
?5.系统软件支持
?存在的问题：不能以通用和可
移植方式进行并行程序设计
?开发并行编程环境,
?一种与系统结构无关的语言、编译器
和软件工具。
? 两个方向,
? 对于开发并行语言,
? 我们将着眼点放在语言执行的效率、对不
同机器的可移植性、与现有的顺序语言的
兼容性、并行性的表达和编程的简便性等
上面。可以设计一种新的语言,
? 逐步扩展现有的顺序语言。
? 新语言有用显式高级结构描述并行性的优
点，但是新语言往往与现有语言不兼容，
而需要新的编译器或者通过新的步骤才能
利用现有的编译器。大部分系统选用的是
语言扩展方式。
?6.编译器支持
?改进编译器有三种途径,
?预处理程序 ;
?预编译器 ;
?并行化编译器。
? 预处理程序采用顺序编译器和目标计算机的低
层程序库实现高级并行结构。预编译器需要程
序流分析、相关性检查和有限的优化来检测并
行性。
? 联接过程的效果取决于预处理程序、预编译器、
并行化编译器、加载程序和操作系统支持的功
效。由于程序行为的不可预测，现有的编译器
在检测所有类型的并行性时都不是完全自动或
完全智能进行的。
? 有效的方法,
? 将编译器命令插入源代码，帮编译器做出较好的结
果。这样，用户可与编译器进行交互重构程序，这
已被证明对提高并行计算机性能是十分有用的。
?7.并行程序的设计环境
? 隐式并行性
? 伊利诺依大学的 David Kuck和 Rice大学
的 KenKennedy以及他们的合作者都已采
用这种隐式并行性方法。
? 显式并行性
? 加州理工学院的 CharlesSeitz和麻省理
工学院的 WilliamDaily在开发多计算机
时采用了这种显式方法。
? 总结,
? 要使一个环境对用户更加友好，必须
要有专用软件工具。
? 一些工具是传统高级语言的并行扩展；
? 一些则是集成环境
? 其中包括提供不同级别的程序抽象、验证、
测试、查错和调试等各种工具；性能预测和
监控；辅助程序开发的可视化支持、性能测
量以及计算结果的图形显示及动画表示
?三、计算机系统结构向高性能
发展历程
?主要探讨顺序到并行的过程
?1.先行、并行性和流水线技术
? 用先行技术预取指令可使 I／ E(指令
读取／译码和执行 )
? 支持功能并行性的方法有两种,
? 一种是同时使用多个功能部件；
? 另一种是在不同处理级分别实施流水线
技术。
? 流水线指令执行、流水线算术计算和存储
器存取操作。
? 2.Flynn分类法
?MkhealFlynn(1972)根据指令和数据流概
念提出了不同计算机系统结构的分类法。
? 传统的顺序机被称为 SISD(单指令流
单数据流 )计算机。
? 向量计算机 --标量和向量硬件装备，
或以 SIMD(单指令流多数据流 )机的形
式出现。
? 并行计算机则属 MIMD(多指令流多数
据流 )机
?MISD(多指令流单数据流 )机
? 在执行不同的指令流时，同一数据流通
过处理机线性阵列。这种系统结构也就
是所谓流水线执行特定算法的脉动阵列
(Systolicarrays)。
? 由卡内基 — 梅隆大学的美籍华人学者
H,T,Kung于 1978年提出的。
? 这一结构是随着 VLSI技术的发展和各
种大运算量的信号 /图象处理及科学
计算的运算要求而建立起来的。
? 例 1：用脉动阵列 (Systolicarray)结构
计算矩阵乘
?脉动阵列的特点,
?处理单元简单
?流水
?算法专业
? 例 2：数据流计算机
? 数据流的计算模型 --试图使并行计算的
基本方面在机器层显式化，而不利用有
可能限制程序并行性的人为约束。
? 它的想法是程序由一个基本数据依赖图来表
示；
? 一个指令可能在获得了它的操作数后的任意
时刻被执行，不是显式控制线性程序列的固
定组合。
?3.并行／向量计算机
? 真正的并行计算机是那些以 MIMD模式执行程序的
计算机。
? 并行计算机有两大类，即共享存储型多处理机和
消息传递型多计算机。
? 多处理机和多计算机之间的主要差别就在
于存储器共享和处理机间通信机制的不同。
? 多处理机系统中的处理机通过公用存储器
的共享变量实现互相通信。
? 多计算机系统的每个计算机结点有一个与
其它结点不共享的本地存储器。处理机之
间的通信通过结点间的消息传递来实现。
? 显式向量计算机
? 指令是随向量处理机的问世而出现的。
一台向量处理机可以装备有用硬件或固
件并发控制的多条向量流水线。
?4.开发层次
?Lionel Ni的最新分类法 (1990),
? 并行计算机的分层开发可表示于下图
?四、性能的系统属性
?1,时钟频率和 CPI
? 主频
?当前数字计算机的 CPU(或简称处理
机 )是由一个恒定周期 (τ,以 ns表
示 )的时钟驱动的。
?周期的倒数是时钟频率
? (ｆ＝ 1/ τ ）（以 MHz表示）。
? 程序的规模
? 是由其指令数 (Ic)，也就是程序串要执
行的机器指令数来决定的。执行不同的
机器指令所需要的时钟周期数也是不一
样的。
? 一条指令的周期数 (CPl)就成为衡量执
行每条指令所需时间的重要参数。
?2.性能因子
?执行程序所需的 CPU时间,
?设 Ic为已知程序的指令条数。执
行程序所需的 CPU时间 (T，以秒 /
程序表示 )可用三个主要因素的乘
积来计算,
? T＝ Ic × CPI × τ
? 可将上式重写成如下形式,
? T＝ Ic × (p+m× k) × τ
?一种指令类型的 CPI可分为完成指令
所需的处理机周期数和存储器周期数
两部分。
?完整的指令执行过程可能包含一至四
次存储器访问 (一次用于取指令，两
次用于取操作数，一次用于存储结
果 )，这与指令的类型有关。
?式中的细化,
?p为指令译码和执行所需的处理机周
期数 ;
?m为所需的存储器访问次数 ;
?k为存储周期与处理机周期之比 ;
?Ic为指令条数，为处理机周期。
?3.系统属性
?计算机系统属性可以由五元组表
示,
?(Ic,p,m,k,τ ),
? 五个量可以称为性能因子。
? 与四种系统属性有关：指令系统结构、
编译技术,CPU实现和控制技术、高速缓
存与存储器层次结构。
?4.Mips速率
?5.吞吐率
?系统的吞吐率,
?系统在单位时间内能执行多少个
程序，这称为系统的吞吐率 (单位
为程序数／秒 ) Ws 。
? 在多道程序系统中，系统吞吐率常低
于 CPU吞吐率 Wp。 Wp可用下式表示,
? 或,Wp=(MIPS)× 106／ Ic
?Wp的单位是程序数／秒。
?CPU吞吐率是根据 MIPS速率和程序的
平均长度 (Ic)来衡量机器每秒钟能执
行多少个程序的尺度。
?Ws<Wp,
? 用多道程序或分时操作在 CPU上交叉执
行多个程序时,I／ O、编译器和操作系
统产生的额外系统开销所造成的。
? 总结,
一,并行的产生
二,并行背景下的计算问题
三,串行向并行的演化
四,并行的性能与系统的关系
并行处理与体系结构
第一章 并行计算机模型
? ?1 计算技术的现状
??2 多处理机和多计算机
? ?3 多向量机和 SIMD计算机
? ?4 并行计算机的抽象模型
? ?5 可扩展的范围和设计
?2 多处理机和多计算机
?一、共享存储型多处理机
?1,UMA模型
?UMA --Uniform Memory Access
?结构和特点,
? 紧耦合系统 (tightly coupled
system)
? 多处理机由于高度资源共享
? 系统的互连采用总线、交叉开关、或多
级网络形式
?对称 (symmetric)多处理机
?当所有处理机都能同样访问所有外
围设备时。
? 例 Fortran程序可在单处理机上顺序执
行,分析 CPU的运行时间,假设条件,
? 所有数组 A(I),B(I),C(I)都有 N个
元素；
? 分析：求和 Fortran程序
? 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所需
的时间可以忽略。
? 假定经过共享存储器的处理机之间的每
次通信操作需要 k个周期。
?结论,CPU用 2N个周期
串行程序并行化
?在 M— 处理机系统上执行程序
?将循环操作 划分 成 M段，每段有
L＝ N／ M个元素。
?假设经过共享存储器的处理机
之间的每次通信操作需要,
? k个周期 。
?Doall表示所有 M段在 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
? 分析,
? 循环 1是 L个周期；循环 2是 L个周期
? 总时间,
? 2L+ h(k+1)=2N/M+(k+1) log2M
2,NUAM模型
? 3.COMA模型
? 概念：只使用高速缓存的多处理机
?实现的机器,
?瑞典计算机科学研究所的数据扩
散机 (DDM,Hagersten等,1990)
?KendallSquareReserch公司的
KSR— 1机器 (Burkhart等,1992)。
?特点,
? COMA模型是 NUMA机的一种特例，将 NUMA
中分布主存储器换成了高速缓存；
? 全部高速缓冲存储器组成了全局地址空
间；
? 远程高速缓存访问则借助于分布高速缓
存目录进行，分级目录往往可用来寻找
高速缓存块的副本，这与所用的互连网
络有关；
? 数据的初始位置并不重要，因为它最终
将会迁移到要用到它的地方。
?模型的演变,
? 例如，高速缓存一致性非均匀存储存取
(CC— NUMA)模型。
?可以用分布共享存储器和高速缓存目
录来描述。
?CC— NUMA模型的实例
? 斯坦福大学的 Dash系统 (Lenosh等,1990)
和麻省理工学院的 Alewife系统 (Agarwal
等,1990)；
? 这些将在后面讨论。
4.典型的多处理机
? 二、分布存储型多计算机系统
? 1.概念
? 由多个计算机结点，通过消息传递网络
互相连接而成，每个结点是一台由处理
机、本地存储器和有时接有磁盘或 I／ 0
外围设备组成的自治的计算机。
? 2.特点,
? 消息传递网络提供结点之间的点到点 静态连接
? 传统的多计算机已被称为近地存储访问 (NORMA)
机
? 所有本地存储器是私用的，而且只有本地处
理机才能访问；
? 私用存储器逐渐在分布共享存储器的多计算机
中将被逐步取消。
? 3,多计算机的换代
? 现代多计算机用硬件寻径器来传送信息；
? 计算机结点与寻径器相连，边界上的寻
径器与 I／ O和外围设备连接；
? 任何两结点间的消息传递会涉及一连串
的寻径器和通道。
? 在异构多计算机系统中，可以有多种类
型的结点，结点间的通信是通过可兼容
的数据表示和消息传递协议来实现的。
? 消息传递型多计算机的发展换代
? 第一代 (1983— 1987)是基于处理机板技术，
采用了超立方体结构和软件控制的消息交换
方法。
? 加州理工学院的 Cosmic和 InteliPSC／ 1是
这一代研制的代表。
? 第二代 (1988— 1992)是用网格连接的系统结
构、硬件消息寻径和中粒度分布计算的软件
环境实现的；
? IntelParagon和 ParsysSuperNodel000可
作为代表性产品。
? 现在面临的第三代 (1993— )预期是细粒
度计算机
?麻省理工学院的 J-Machine和加州工
学院的 Mosaic,VLSI片上实现处理机
和通讯工具 。
示例,
IBM POWER4体系结构特点
?PowerPC 64位体系结构
?单芯片双处理器,MCM八处理器
?集成多处理器互连接口
?集成 I/O控制器
?集成 L3Cache控制器
?集成存储控制器
IBM POWER4 (MCM结构 )
IBM POWER4 (32CPU)
?4.典型多计算机
?多计算机的可编程性取决于,
?高效编译器实用
?高效的分布式操作系统实用
?总结,
? 本节区分了多处理机和多计算机的主
要差别和分类。
?3 多向量机和 SIMD计算机
?一、向量超级计算机
?1.早期的超级计算机可分为,
?流水线向量机；
?SIMD计算机两类。
? 执行过程,
? 当译出的指令为向量操作；
? 它将被送至向量控制器，控制器将监
督主存储器与向量功能流水线之间的
向量数据流，向量数据流由控制器协
调控制；
? 向量处理机则装有若干条向量功能流
水线。
?2.寄存器 — 寄存器的系统结构
? 如 1976年推出的 Cray 1。
?向量寄存器用来保存向量操作
数、中间和最终的向量结果 ;
?向量功能流水线从向量寄存器
检索操作数，并将结果放入寄
存器。
? 3.存储器 — 存储器结构
?这种结构比较早，与寄存器 — 寄存
器结构的区别就在于采用向量流水
部件代替了向量寄存器。
?例如,
二,SIMD超级计算机
? 1,SIMD的操作模型
? 可用五元组表示 M＝ <N,C,I,M，
R>
? N为机器的处理单元 (PE)数。
?例如,illiac IV有 64个 PE，而连接机
(ConnectionMachine)CM— 2采用 65
536个 PE。
? C为由控制部件 (CU)直接执行的指令集；
?包括标量和程序流控制指令。
? I为由 CU广播至所有 PE进行并行执行的指令
集；
? 它包括算术运算、逻辑运算、数据寻径、
屏蔽以及其它由每个活动的 PE对它的数据
所执行的局部操作。
? M为屏蔽方案集
? 其中每种屏蔽将 PE集划分为允许操作和禁
止操作两种子集。
? R是数据寻径功能集
? 说明互连网络中 PE间通信所需要的各种设
置模式。
?示例,
?描述具体的 SIMD机器 MasParMP— 1计
算机的操作特性 --五元组特性,
?MP— 1是一种 SIMD机器，其 PE数 N＝
1024至 16 384。 PE数目与机器配置有
关。
?CU执行标量指令，将译码后的向量指
令播送到 PE阵列，并控制 PE间的通信。
? 每个 PE都是基于寄存器的加载／存储
RISC处理机，能执行不同数据量的整数
运算和标准浮点运算。各 PE从 CU接受指
令。
? 屏蔽方案设在每个 PE中，并由 CU连续监
控，它能在运行时动态地使每个 PE处于
置位或复位状态。
? 例如,
? MP— 1有一个 X— Net网格网络和一个全
局多级交叉开关寻径器，以实现 CU— PE
之间,X— Net的 8个近邻之间和全局寻
径器的通信。
? 2.SIMD的实施模型
? （ 1）分布式存储器模型
? 存储器分布的 SIMD特点,
? SIMD计算机开发的是 PE之间的空间并行性。
? 存储器分布的 SIMD计算机由同一阵列控制
部件控制的 PE阵列组成。
? 程序和数据通过主机装入控制存储器。
? 指令是送到控制部件进行译码。
? 标量操作或控制操作，则将直接由与控制部件
相连的标量处理机执行。
? 向量操作，则将它广播到所有 PE并行地执行。
? 划分后的数据集合通过向量数据总线广播到
所有 PE的本地存储器。
? PE通过数据寻径网络互连。数据寻径网络执
行 PE间的通信，如移数、置换和其它寻径操
作。控制部件通过执行程序来控制数据寻径
网络。 PE的同步由控制部件的硬件实现。
? 所有 PE在同一个周期执行同一条指令。
? 可以用屏蔽逻辑来决定任何一个 PE在给定的
指令周期执行或不执行指令。
? （ 2） 共享存储器模型
? 是一种 PE使用共享存储器的 SIMD计算机。
PE和存储器之间的通信网络是一个对准
网络，它也受控制部件控制。
任课教师：季振洲
联系方式：新技术楼 614房间
电话,86402036
课程背景
?并行处理技术已经成为现代计
算机科研与发展的关键技术；
?其推动力来自实际应用对高性
能、低价格和持续生产力日益
增长的要求
?计算机原理的概念
?计算机体系结构的概念
?(Amdahl)；
?并行主要研究,
?先行方式、流水方式、向量化；
?并发性、同时性；
?数据并行性、划分；
?交叉、重叠、多重性、重复；
?时间共享、空间共享；
?多任务处理、多道程序、多线程
方式和分布式计算。
第一章 并行计算机模型
??1 计算技术的现状
??2 多处理机和多计算机
??3 多向量机和 SIMD计算机
??4 并行计算机的抽象模型
??5 可扩展的范围和设计
?1 计算技术的现状
?一、并行技术的出现
? 二、现代并行计算机的组成
?涉及 6个问题,
?1.计算问题
?现实生活中对问题要求快速而精确地
求解推动了计算机的广泛使用。
? 科学技术中的数值计算问题
? 人工智能 (AI)问题
?2.算法和数据结构
? 并行计算问题中的运算和通信，需要
各种专门的算法和数据结构。
? 符号处理,
? 存在的问题,
?3.硬件资源
? 处理机、存储器和外围设备组成了计
算机系统的硬件核心
? 外围设备可以直接或通过局域网和广
域网与主机相连
?4.操作系统
? 管理用户程序执行过程中的资源分配
和再分配。
? 映射是一种算法结构与硬件结构相匹
配的双向过程。
? 并行操作系统的映射
? 算法和数据结构到机器结构的映射包括处
理机调度、存储器映象、处理器间的通信
等。
? 这些问题通常都与系统结构有关。
?5.系统软件支持
?存在的问题：不能以通用和可
移植方式进行并行程序设计
?开发并行编程环境,
?一种与系统结构无关的语言、编译器
和软件工具。
? 两个方向,
? 对于开发并行语言,
? 我们将着眼点放在语言执行的效率、对不
同机器的可移植性、与现有的顺序语言的
兼容性、并行性的表达和编程的简便性等
上面。可以设计一种新的语言,
? 逐步扩展现有的顺序语言。
? 新语言有用显式高级结构描述并行性的优
点，但是新语言往往与现有语言不兼容，
而需要新的编译器或者通过新的步骤才能
利用现有的编译器。大部分系统选用的是
语言扩展方式。
?6.编译器支持
?改进编译器有三种途径,
?预处理程序 ;
?预编译器 ;
?并行化编译器。
? 预处理程序采用顺序编译器和目标计算机的低
层程序库实现高级并行结构。预编译器需要程
序流分析、相关性检查和有限的优化来检测并
行性。
? 联接过程的效果取决于预处理程序、预编译器、
并行化编译器、加载程序和操作系统支持的功
效。由于程序行为的不可预测，现有的编译器
在检测所有类型的并行性时都不是完全自动或
完全智能进行的。
? 有效的方法,
? 将编译器命令插入源代码，帮编译器做出较好的结
果。这样，用户可与编译器进行交互重构程序，这
已被证明对提高并行计算机性能是十分有用的。
?7.并行程序的设计环境
? 隐式并行性
? 伊利诺依大学的 David Kuck和 Rice大学
的 KenKennedy以及他们的合作者都已采
用这种隐式并行性方法。
? 显式并行性
? 加州理工学院的 CharlesSeitz和麻省理
工学院的 WilliamDaily在开发多计算机
时采用了这种显式方法。
? 总结,
? 要使一个环境对用户更加友好，必须
要有专用软件工具。
? 一些工具是传统高级语言的并行扩展；
? 一些则是集成环境
? 其中包括提供不同级别的程序抽象、验证、
测试、查错和调试等各种工具；性能预测和
监控；辅助程序开发的可视化支持、性能测
量以及计算结果的图形显示及动画表示
?三、计算机系统结构向高性能
发展历程
?主要探讨顺序到并行的过程
?1.先行、并行性和流水线技术
? 用先行技术预取指令可使 I／ E(指令
读取／译码和执行 )
? 支持功能并行性的方法有两种,
? 一种是同时使用多个功能部件；
? 另一种是在不同处理级分别实施流水线
技术。
? 流水线指令执行、流水线算术计算和存储
器存取操作。
? 2.Flynn分类法
?MkhealFlynn(1972)根据指令和数据流概
念提出了不同计算机系统结构的分类法。
? 传统的顺序机被称为 SISD(单指令流
单数据流 )计算机。
? 向量计算机 --标量和向量硬件装备，
或以 SIMD(单指令流多数据流 )机的形
式出现。
? 并行计算机则属 MIMD(多指令流多数
据流 )机
?MISD(多指令流单数据流 )机
? 在执行不同的指令流时，同一数据流通
过处理机线性阵列。这种系统结构也就
是所谓流水线执行特定算法的脉动阵列
(Systolicarrays)。
? 由卡内基 — 梅隆大学的美籍华人学者
H,T,Kung于 1978年提出的。
? 这一结构是随着 VLSI技术的发展和各
种大运算量的信号 /图象处理及科学
计算的运算要求而建立起来的。
? 例 1：用脉动阵列 (Systolicarray)结构
计算矩阵乘
?脉动阵列的特点,
?处理单元简单
?流水
?算法专业
? 例 2：数据流计算机
? 数据流的计算模型 --试图使并行计算的
基本方面在机器层显式化，而不利用有
可能限制程序并行性的人为约束。
? 它的想法是程序由一个基本数据依赖图来表
示；
? 一个指令可能在获得了它的操作数后的任意
时刻被执行，不是显式控制线性程序列的固
定组合。
?3.并行／向量计算机
? 真正的并行计算机是那些以 MIMD模式执行程序的
计算机。
? 并行计算机有两大类，即共享存储型多处理机和
消息传递型多计算机。
? 多处理机和多计算机之间的主要差别就在
于存储器共享和处理机间通信机制的不同。
? 多处理机系统中的处理机通过公用存储器
的共享变量实现互相通信。
? 多计算机系统的每个计算机结点有一个与
其它结点不共享的本地存储器。处理机之
间的通信通过结点间的消息传递来实现。
? 显式向量计算机
? 指令是随向量处理机的问世而出现的。
一台向量处理机可以装备有用硬件或固
件并发控制的多条向量流水线。
?4.开发层次
?Lionel Ni的最新分类法 (1990),
? 并行计算机的分层开发可表示于下图
?四、性能的系统属性
?1,时钟频率和 CPI
? 主频
?当前数字计算机的 CPU(或简称处理
机 )是由一个恒定周期 (τ,以 ns表
示 )的时钟驱动的。
?周期的倒数是时钟频率
? (ｆ＝ 1/ τ ）（以 MHz表示）。
? 程序的规模
? 是由其指令数 (Ic)，也就是程序串要执
行的机器指令数来决定的。执行不同的
机器指令所需要的时钟周期数也是不一
样的。
? 一条指令的周期数 (CPl)就成为衡量执
行每条指令所需时间的重要参数。
?2.性能因子
?执行程序所需的 CPU时间,
?设 Ic为已知程序的指令条数。执
行程序所需的 CPU时间 (T，以秒 /
程序表示 )可用三个主要因素的乘
积来计算,
? T＝ Ic × CPI × τ
? 可将上式重写成如下形式,
? T＝ Ic × (p+m× k) × τ
?一种指令类型的 CPI可分为完成指令
所需的处理机周期数和存储器周期数
两部分。
?完整的指令执行过程可能包含一至四
次存储器访问 (一次用于取指令，两
次用于取操作数，一次用于存储结
果 )，这与指令的类型有关。
?式中的细化,
?p为指令译码和执行所需的处理机周
期数 ;
?m为所需的存储器访问次数 ;
?k为存储周期与处理机周期之比 ;
?Ic为指令条数，为处理机周期。
?3.系统属性
?计算机系统属性可以由五元组表
示,
?(Ic,p,m,k,τ ),
? 五个量可以称为性能因子。
? 与四种系统属性有关：指令系统结构、
编译技术,CPU实现和控制技术、高速缓
存与存储器层次结构。
?4.Mips速率
?5.吞吐率
?系统的吞吐率,
?系统在单位时间内能执行多少个
程序，这称为系统的吞吐率 (单位
为程序数／秒 ) Ws 。
? 在多道程序系统中，系统吞吐率常低
于 CPU吞吐率 Wp。 Wp可用下式表示,
? 或,Wp=(MIPS)× 106／ Ic
?Wp的单位是程序数／秒。
?CPU吞吐率是根据 MIPS速率和程序的
平均长度 (Ic)来衡量机器每秒钟能执
行多少个程序的尺度。
?Ws<Wp,
? 用多道程序或分时操作在 CPU上交叉执
行多个程序时,I／ O、编译器和操作系
统产生的额外系统开销所造成的。
? 总结,
一,并行的产生
二,并行背景下的计算问题
三,串行向并行的演化
四,并行的性能与系统的关系
并行处理与体系结构
第一章 并行计算机模型
? ?1 计算技术的现状
??2 多处理机和多计算机
? ?3 多向量机和 SIMD计算机
? ?4 并行计算机的抽象模型
? ?5 可扩展的范围和设计
?2 多处理机和多计算机
?一、共享存储型多处理机
?1,UMA模型
?UMA --Uniform Memory Access
?结构和特点,
? 紧耦合系统 (tightly coupled
system)
? 多处理机由于高度资源共享
? 系统的互连采用总线、交叉开关、或多
级网络形式
?对称 (symmetric)多处理机
?当所有处理机都能同样访问所有外
围设备时。
? 例 Fortran程序可在单处理机上顺序执
行,分析 CPU的运行时间,假设条件,
? 所有数组 A(I),B(I),C(I)都有 N个
元素；
? 分析：求和 Fortran程序
? 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所需
的时间可以忽略。
? 假定经过共享存储器的处理机之间的每
次通信操作需要 k个周期。
?结论,CPU用 2N个周期
串行程序并行化
?在 M— 处理机系统上执行程序
?将循环操作 划分 成 M段，每段有
L＝ N／ M个元素。
?假设经过共享存储器的处理机
之间的每次通信操作需要,
? k个周期 。
?Doall表示所有 M段在 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
? 分析,
? 循环 1是 L个周期；循环 2是 L个周期
? 总时间,
? 2L+ h(k+1)=2N/M+(k+1) log2M
2,NUAM模型
? 3.COMA模型
? 概念：只使用高速缓存的多处理机
?实现的机器,
?瑞典计算机科学研究所的数据扩
散机 (DDM,Hagersten等,1990)
?KendallSquareReserch公司的
KSR— 1机器 (Burkhart等,1992)。
?特点,
? COMA模型是 NUMA机的一种特例，将 NUMA
中分布主存储器换成了高速缓存；
? 全部高速缓冲存储器组成了全局地址空
间；
? 远程高速缓存访问则借助于分布高速缓
存目录进行，分级目录往往可用来寻找
高速缓存块的副本，这与所用的互连网
络有关；
? 数据的初始位置并不重要，因为它最终
将会迁移到要用到它的地方。
?模型的演变,
? 例如，高速缓存一致性非均匀存储存取
(CC— NUMA)模型。
?可以用分布共享存储器和高速缓存目
录来描述。
?CC— NUMA模型的实例
? 斯坦福大学的 Dash系统 (Lenosh等,1990)
和麻省理工学院的 Alewife系统 (Agarwal
等,1990)；
? 这些将在后面讨论。
4.典型的多处理机
? 二、分布存储型多计算机系统
? 1.概念
? 由多个计算机结点，通过消息传递网络
互相连接而成，每个结点是一台由处理
机、本地存储器和有时接有磁盘或 I／ 0
外围设备组成的自治的计算机。
? 2.特点,
? 消息传递网络提供结点之间的点到点 静态连接
? 传统的多计算机已被称为近地存储访问 (NORMA)
机
? 所有本地存储器是私用的，而且只有本地处
理机才能访问；
? 私用存储器逐渐在分布共享存储器的多计算机
中将被逐步取消。
? 3,多计算机的换代
? 现代多计算机用硬件寻径器来传送信息；
? 计算机结点与寻径器相连，边界上的寻
径器与 I／ O和外围设备连接；
? 任何两结点间的消息传递会涉及一连串
的寻径器和通道。
? 在异构多计算机系统中，可以有多种类
型的结点，结点间的通信是通过可兼容
的数据表示和消息传递协议来实现的。
? 消息传递型多计算机的发展换代
? 第一代 (1983— 1987)是基于处理机板技术，
采用了超立方体结构和软件控制的消息交换
方法。
? 加州理工学院的 Cosmic和 InteliPSC／ 1是
这一代研制的代表。
? 第二代 (1988— 1992)是用网格连接的系统结
构、硬件消息寻径和中粒度分布计算的软件
环境实现的；
? IntelParagon和 ParsysSuperNodel000可
作为代表性产品。
? 现在面临的第三代 (1993— )预期是细粒
度计算机
?麻省理工学院的 J-Machine和加州工
学院的 Mosaic,VLSI片上实现处理机
和通讯工具 。
示例,
IBM POWER4体系结构特点
?PowerPC 64位体系结构
?单芯片双处理器,MCM八处理器
?集成多处理器互连接口
?集成 I/O控制器
?集成 L3Cache控制器
?集成存储控制器
IBM POWER4 (MCM结构 )
IBM POWER4 (32CPU)
?4.典型多计算机
?多计算机的可编程性取决于,
?高效编译器实用
?高效的分布式操作系统实用
?总结,
? 本节区分了多处理机和多计算机的主
要差别和分类。
?3 多向量机和 SIMD计算机
?一、向量超级计算机
?1.早期的超级计算机可分为,
?流水线向量机；
?SIMD计算机两类。
? 执行过程,
? 当译出的指令为向量操作；
? 它将被送至向量控制器，控制器将监
督主存储器与向量功能流水线之间的
向量数据流，向量数据流由控制器协
调控制；
? 向量处理机则装有若干条向量功能流
水线。
?2.寄存器 — 寄存器的系统结构
? 如 1976年推出的 Cray 1。
?向量寄存器用来保存向量操作
数、中间和最终的向量结果 ;
?向量功能流水线从向量寄存器
检索操作数，并将结果放入寄
存器。
? 3.存储器 — 存储器结构
?这种结构比较早，与寄存器 — 寄存
器结构的区别就在于采用向量流水
部件代替了向量寄存器。
?例如,
二,SIMD超级计算机
? 1,SIMD的操作模型
? 可用五元组表示 M＝ <N,C,I,M，
R>
? N为机器的处理单元 (PE)数。
?例如,illiac IV有 64个 PE，而连接机
(ConnectionMachine)CM— 2采用 65
536个 PE。
? C为由控制部件 (CU)直接执行的指令集；
?包括标量和程序流控制指令。
? I为由 CU广播至所有 PE进行并行执行的指令
集；
? 它包括算术运算、逻辑运算、数据寻径、
屏蔽以及其它由每个活动的 PE对它的数据
所执行的局部操作。
? M为屏蔽方案集
? 其中每种屏蔽将 PE集划分为允许操作和禁
止操作两种子集。
? R是数据寻径功能集
? 说明互连网络中 PE间通信所需要的各种设
置模式。
?示例,
?描述具体的 SIMD机器 MasParMP— 1计
算机的操作特性 --五元组特性,
?MP— 1是一种 SIMD机器，其 PE数 N＝
1024至 16 384。 PE数目与机器配置有
关。
?CU执行标量指令，将译码后的向量指
令播送到 PE阵列，并控制 PE间的通信。
? 每个 PE都是基于寄存器的加载／存储
RISC处理机，能执行不同数据量的整数
运算和标准浮点运算。各 PE从 CU接受指
令。
? 屏蔽方案设在每个 PE中，并由 CU连续监
控，它能在运行时动态地使每个 PE处于
置位或复位状态。
? 例如,
? MP— 1有一个 X— Net网格网络和一个全
局多级交叉开关寻径器，以实现 CU— PE
之间,X— Net的 8个近邻之间和全局寻
径器的通信。
? 2.SIMD的实施模型
? （ 1）分布式存储器模型
? 存储器分布的 SIMD特点,
? SIMD计算机开发的是 PE之间的空间并行性。
? 存储器分布的 SIMD计算机由同一阵列控制
部件控制的 PE阵列组成。
? 程序和数据通过主机装入控制存储器。
? 指令是送到控制部件进行译码。
? 标量操作或控制操作，则将直接由与控制部件
相连的标量处理机执行。
? 向量操作，则将它广播到所有 PE并行地执行。
? 划分后的数据集合通过向量数据总线广播到
所有 PE的本地存储器。
? PE通过数据寻径网络互连。数据寻径网络执
行 PE间的通信，如移数、置换和其它寻径操
作。控制部件通过执行程序来控制数据寻径
网络。 PE的同步由控制部件的硬件实现。
? 所有 PE在同一个周期执行同一条指令。
? 可以用屏蔽逻辑来决定任何一个 PE在给定的
指令周期执行或不执行指令。
? （ 2） 共享存储器模型
? 是一种 PE使用共享存储器的 SIMD计算机。
PE和存储器之间的通信网络是一个对准
网络，它也受控制部件控制。
