哈尔滨工业大学计算机科学与技术学院
并行处理与体系结构
哈尔滨工业大学计算机科学与技术学院
第一章 并行计算机模型
? ?1 计算技术的现状
? ?2 多处理机和多计算机
? ?3 多向量机和 SIMD计算机
??4 并行计算机的抽象模型
? ?5 可扩展的范围和设计
哈尔滨工业大学计算机科学与技术学院
?4 并行计算机的抽象模型
? 并行计算机的理论模型是从物理模型
抽象的；
? 为开发并行算法提供了一种方便的框
架；
? 用这些模型可求得并行计算机的理论
性能界限；
? 可在芯片制作前估算芯片区的 VLSI复
杂性和执行时间。
哈尔滨工业大学计算机科学与技术学院
?一、时间与空间复杂性
?计算机求解一个规模为 s的问题
的算法复杂性取决于,
?执行时间
?存储空间
哈尔滨工业大学计算机科学与技术学院
? 时间复杂性,
?时间复杂性 g(s)为 O(f(s))，可读
作, 数量级为 f(s)”，如存在正的
常量 c和 s0，则对所有 s>s0的非负
值就有 g(s)≤ cf(s) 。
哈尔滨工业大学计算机科学与技术学院
? 空间复杂性
? 为问题规模 s的函数。
? 渐近空间复杂性 (asymptotic spacecom—
plexity)主要与大问题的数据存储有关，而程
序 (代码 )存储的需求和输入数据的存储不考虑
在内。
? 串行算法的时间复杂性简称为串行复杂性 ;
? 并行算法的时间复杂性就称为并行复杂性 ;
? 并行复杂性应比串行复杂性低，至少是相
近。
? 只考虑确定性算法。
哈尔滨工业大学计算机科学与技术学院
? NP完全性,
? P类 (即多项式类 ),
? 具有多项式复杂性算法的问题集，如果存在一
多项式 p(s)，对任何问题规模 s的时间复杂性为
O(p(s))，则某算法即具有多项式复杂性。
? NP类 (即不确定性多项式类 )：能以多项式时
间，用不确定性算法求解的问题集。
? P?NP
? 确定性算法是不确定算法的特殊情况。
? P类问题是计算易解的，而 NP-P类问题是难
解的。
哈尔滨工业大学计算机科学与技术学院
? 现在不知道是否 P＝ NP或 P≠ NP。
? 难解的 NP类问题又称为具有指数时间
复杂性的问题。
哈尔滨工业大学计算机科学与技术学院
?例题：多项式复杂性和指数复杂性
算法,
?将几个数排序的多项式时间复杂性
分别为 O(nlogn)，属于 P类
?对两个 n× n矩阵相乘算法的多项式
时间复杂性分别为 O(n3)，属于 P类。
哈尔滨工业大学计算机科学与技术学院
?旅行推销员问题复杂性为 O(n22n)和
背包问题的复杂性为 O(2n/2 )
?指数复杂性问题是属 NP类的,
?到目前为止还未发现这类问题的确定
性多项式算法。
哈尔滨工业大学计算机科学与技术学院
P,NP和 NPC（ NP完全问题）
哈尔滨工业大学计算机科学与技术学院
? 二,并行随机存取机模型
(Parallel Random— Access Machine，
PRAM)
?目的：可用来开发并行算法和分析
可扩展性及复杂性。
哈尔滨工业大学计算机科学与技术学院
?MIMD
?细粒度
?严格同步
?零开销
?共享变量
哈尔滨工业大学计算机科学与技术学院
? 在 PRAM上的一个并行程序由 n个进程组
成，其中第 i个进程留驻在第 i个处理
器上，且由一串指令所组成。
? 在每个基本时间步 (称为周期 )，每个
处理器执行一条指令。
? 这些指令包括数据传送、算 /逻、控制
流以及 I/O指令，在典型的顺序计算机
中均有这些指令。
哈尔滨工业大学计算机科学与技术学院
? 1.同构性
? 规模为 1的 PRAM退化为传统的 RAM。这种
机器为 SISD。
? 当处理器多于 1个时，一个 PRAM将访问
多个数据流，且通常可执行多个指令流。
因此 PRAM是一个 MIMD机器。
哈尔滨工业大学计算机科学与技术学院
? MIMD的特例,
? 如果在每一周期，所有处理器必须执行
相同指令，即只有一个指令流时，则
PRAM就成为单指令 (流 )、多数据
(流 )(SIMD)机器。
? (SPMD)计算：单程序、多数据，所有进
程执行同一程序，而由进程指标加以参
数化。
? SIMD和 SPMD间的差别是，在 SPMD计算中，
同一周期可以执行不同指令。
哈尔滨工业大学计算机科学与技术学院
?2,同步性
?进程 同步是严格的。
?PRAM是在指令级同步的。
哈尔滨工业大学计算机科学与技术学院
?3.交互机制
?这一属性描述了并行进程间如何相
互影响行为的特性。
?在 PRAM模型中，进程间通过共享变
量 (或共享存储器 )进行交互。
哈尔滨工业大学计算机科学与技术学院
? 4,地址空间
? 理论 PRAM模型的一个重要特征是所有进
程对所有存储单元均有相等的访问时间。
这种机器为均匀存储器访问 (UMA)。
? 在多计算机中，每个处理机有它自己的
分离地址空间。这些机器被称为具有多
地址空间。多计算机的处理机间通信不
是通过共享变量，而是借助消息传递。
哈尔滨工业大学计算机科学与技术学院
?5.存储器模型
? 各种方案的主要区别在于如何协调 CW的冲突。
? 四种 PRAM模型方案都与存储器读写如何处理
有关。
(1)EREW-PRAM模型 —— 这种模型禁止一台以上
处理机同时读、写同一存储单元
? (Snir,1982； Karp和 Ramachandran，
1988)。这是限制最大的 PRAM模型。
(2)CREW-PRAM模型 —— 用互斥使写冲突避免。
可以并行读同一存储单元。
哈尔滨工业大学计算机科学与技术学院
(3)ERCW-PRAM模型 —— 允许互斥读或并
行写同一存储单元。
(4)CRCW-PRAM模型 —— 允许在同一时刻
并行读或者并行写。
哈尔滨工业大学计算机科学与技术学院
? 写冲突可用下述四种策略之一分解,
? 共用 —— 所有同时进行的写操作将相同
数据存入热点存储单元。
? 任选 —— 将任何一个要写的数保存起来，
而其它的忽略不计。
? 最小值 —— 将处理机要写的下标值最小
的数保存起来。
? 优先 —— 对要写的数用求和或求最大值
等联想函数加以组合。
哈尔滨工业大学计算机科学与技术学院
? 6.原子操作
? 原子操作的定义：一个原子操作是指有
如下特性的一种操作。
?不可分
?有限
哈尔滨工业大学计算机科学与技术学院
? 更严格的原子操作定义,
? 需要满足以下的 4个性质。称这样的原
子操作为一个事务操作。
?原子性
?一致性
?隔离性
?持续性
哈尔滨工业大学计算机科学与技术学院
? 7.例题
? 例题 1,
? 在一台处理机数为 n3／ logn的 PRAM上，
用 O(logn)时间完成两个,nxn” 矩阵的
乘法 (Viktor Prasanna,1992)
? 设 A和 B为输入矩阵，假定最初可用的 PE
数为 n3个，后来降为 n3／ logn个。
哈尔滨工业大学计算机科学与技术学院
? 假设内存由三维阵列组成，将 A,B存入
其中两个平面。
? 假设了 PE的三维地址指标。 PE(i,j，
k),0≤k≤n -1可用来计算输出矩阵的
第 (i,j)项,0≤i, j≤n -1,n是 2的幂 。
哈尔滨工业大学计算机科学与技术学院
? 第一步，对应于每个输出的 n乘积项用 n个 PE
在 O(1)时间内进行计算。
? 第二步，这些乘积项用 O(logn)时间相加产生
一个输出。所用的 PE总数为 n3，结果存在 C(i，
j,0)中 (0≤i, j≤n -1)。
? 假定这里的 PRAM采用的是 CREW策略。
哈尔滨工业大学计算机科学与技术学院
? Step 1,
? 1,Read A(i,k)
? 2,Read B(k,j)
? 3,Compute A(i,k)× B(k,j)
? 4,Store in C(I,j,k)
? Step 2,
? 1,L←n
? 2,Repeat L←L ／ 2
? If (k<1)then
? begin
哈尔滨工业大学计算机科学与技术学院
? Read A(i,k)
? Read A(i,k)
? Compute C(i,j,k)+C(i,j,k,k+l)
? Store in C(i,j,k)
? End
? Until (l=1)
? 上述是每个 PE(i,j,k)要执行的程序。所
有 n3个 PE对 n3乘法进行并行运算。但对完成
(n3- n2 )加法最多只有 n3／ 2个 PE处于工作
状态。
哈尔滨工业大学计算机科学与技术学院
? 为了将 PE数降为 n3／ logn，可采用 nXnXn／
logn的 PE阵列。
? 每个 PE负责计算 logn个乘积项并将它们求和。
? 第一步很容易改写产生 n／ logn个部分和，每
一个部分和由 logn次乘法和 (logn-1)次加法完
成。
? 我们有数组 C(i,j,k),0≤i, j≤n -1，
0≤k≤n ／ logn-1，它们可在 log(n／ logn)时
间内完成求和，所以将第一步和第二步所花的
时间相加，我们就得到总执行时间为 2logn-
1+log(n／ logn),在 n比较大时近似为
O(logn)。
哈尔滨工业大学计算机科学与技术学院
?例题 2,PRAM步中的计算复杂性
? 假设有三个 PRAM算法 A,B和 C，当在一
个有 n个处理器的 PRAM计算机上执行时，
各自的时间复杂性为
? A--7n,
? B--(nlogn)／ 4
? C--nloglogn。
哈尔滨工业大学计算机科学与技术学院
? 根据大 O标志,
?算法 A最快,(O(n)),
?C次之,O(nloglogn),
?B为最慢,O(nlogn)。
哈尔滨工业大学计算机科学与技术学院
? 而实际上，当机器的处理器数小于、等
于 1024时,
? 有 log n<log1024=10
? 以及 loglogn≤ loglog1024<4。
? 如果，处理器数小于 1024时,
? 算法 B最快，其次是 C，而 A则是最慢的。
哈尔滨工业大学计算机科学与技术学院
?与物理模型的差异
? 实际上，这种并行计算机是不存在的。
共享存储器 SIMD机是与 PRAM模型最接近
的结构。
? 更确切地说，共享存储的同步 MIMD模式
运行。
哈尔滨工业大学计算机科学与技术学院
?四种 PRAM方案中,EREW和 CRCW是
应用最普遍的模型。
? 每个 CRCW算法可用一个 EREW算法来模拟。
? CRCW算法比一个等效的 EREW要快，经证
明，最好的 n— 处理机 EREW算法要比任一
个 n-处理机 CRCW算法慢 O(logn)倍。
? 对研究结构规则的并行性来说，用 PRAM
比用实际机器模型要好得多。
? PRAM能指出实际并行计算机性能的上限。
哈尔滨工业大学计算机科学与技术学院
? 三、异步 PRAM模型 — APRAM
? 是一个异步的 PRAM模型，简记为 APRAM
? 1.模型特点,
? 由 p个处理器组成；
? 每个处理器都有其本地存储器、局部时
钟和局部程序；
? 处理器间的通信经过共享全局存储器 ；
哈尔滨工业大学计算机科学与技术学院
?无全局时钟
?各处理器异步地独立执行各自的指令；
? 处理器任何时间依赖关系需明确地在
各处理器的程序中加入同步 (路 )障
(Synchronization Barrier)；
? 一条指令可在非确定但有限的时间内
完成。
哈尔滨工业大学计算机科学与技术学院
? 2,APRAM模型中的指令类型有四类指
令,
? ① 全局读
?将全局存储单元中的内容读入局存
单元中；
? ② 局部操作
?对局存中的数执行操作，其结果存
入局存中；
哈尔滨工业大学计算机科学与技术学院
? ③ 全局写
?将局存单元中的内容写入全局存储
单元中；
? ④ 同步
?同步是计算中的一个逻辑点，在该
点各处理器均需等待别的处理器到
达后，才能执行其局部程序。
哈尔滨工业大学计算机科学与技术学院
? 3,APRAM模型中完成的计算
? 计算是由一系列用同步障分开的全局相所组成。
? 在各全局相内，每个处理器异步地运行其局
部程序；
? 每个局部程序中的最后一条指令是一条同步障
指令；
? 各处理器均可异步地读取和写入全局存储器,
? 在同一相内不允许两个处理器访问同一单元。
? 不同的处理器访问存储单元总是由一同步障所分开，
所以指令完成时间上的差异并不影响整个计算
哈尔滨工业大学计算机科学与技术学院
? 4,APRAM模型中的时间计算
? 使用 APRAM模型计算算法的时间复杂度时，
假定局部操作取单位时间；
? 全局读／写时间为 d
? 它定量化了通信延迟，代表读 /写全局存
储器的平均时间,d随机器中的处理器增
加而增加；
? 同步障的时间为 B
? 它是处理器数 P的非降函数 B=B(P)。
哈尔滨工业大学计算机科学与技术学院
? 在 APRAM中假定上述参数服从如下关系,
? 2≤d≤B≤P
? 同时,B(P)∈ O(dlogP)或
B(P)∈ O(dlogP/logd)。
? 令 tph为全局相内各处理器指令执行时间中
最长者，则整个程序运行时间 T为各相的时
间之和加上 B乘以同步障次数，即,
? T=∑t ph+B× 同步障次数
哈尔滨工业大学计算机科学与技术学院
?四, BSP模型
? BSP-Bulk Synchronization Parallel
? 1,BSP模型的提出,
? 哈佛大学的 Leslie Valiant提出,
? 块同步并行 (BSP)，用以克服 PRAM模型的
缺点，但保留其简单性。
? 一个 BSP计算机由 n个结点 (处理器和存
储器对 )所组成。
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
?2.特点,
? 一个 BSP程序有 n个进程，每个驻留在
一个结点上。基本时间单位是周期 (或
时间步 )。
? 程序按严格的超步序列执行。
哈尔滨工业大学计算机科学与技术学院
?特点,
?同步路障迫使进程等待
?BSP计算机是 MIMD系统
?BSP模型是超步级的松同步
?在一个超步中，不同进程以不同速
率异步执行。
?BSP模型交互机制是共享变量或是
消息传递。
哈尔滨工业大学计算机科学与技术学院
?3.h关系的定义,
? 一个 h关系是任何通信操作的抽象，在
其中，每个结点最多发出 h个字到各结
点，并且每个结点最多接收 h个字。
? 在一个 BSP计算机中，实现任何 h关系
的时间不会超过 gh个周期。
?g是由机器平台决定的一个常数。
哈尔滨工业大学计算机科学与技术学院
?4.一个超步执行时间的确定
?计算时间 w
?处理器中完成计算操作所需的最大
周期数。
?同步开销为 L。
?通信开销为 gh周期
?g是实现 h关系的比例系数，常数。
哈尔滨工业大学计算机科学与技术学院
?结论,
?执行一个超步的时间为 w+gh+L
哈尔滨工业大学计算机科学与技术学院
?5.例题,
? 在一个有 n个处理器的 EREW PRAM计算
机上，对两个 N维向量 A和 B求内积 s，
可指派每个处理器完成 2N／ n个加法和
乘法（ 2N／ n+logn ）；
? 改用 BSP机器模型实现一个并行执行上
述内积求解。
? 在一个有 8个处理器的 BSP计算机上，
用 4个超步完成问题求解,
哈尔滨工业大学计算机科学与技术学院
?超步１,
?每个处理器在 w=2N／ 8周期内计算，
求出局部和。
?通信 1次：处理器 0,2,4,6将其局
部和 → 处理器 1,3,5,7。
?路障同步。
哈尔滨工业大学计算机科学与技术学院
?超步２,
?计算１、３、５、７各自完成一次
加法；
?通讯 1次,处理器１，５中间结果
送处理器３和７。
?路障同步
哈尔滨工业大学计算机科学与技术学院
?超步３,
?计算：处理器３和处理器７，各完
成一次加；
?通讯：处理器３ → 处理器７，完成
一次通讯
?路障同步。
哈尔滨工业大学计算机科学与技术学院
?超步 4计算,
?处理器 7完成一次加法 (w＝１）产
生最后和。
?不再需要任何通信或同步。
哈尔滨工业大学计算机科学与技术学院
?总执行时间,
?2N／ 8+3g+3Ｌ +3个周期
? 总之,
? 点积在一个有 n个处理器的 BSP计算机
上，执行时间为,
2N／ n+logｎ (g+L+1)个周期。
? 与 PRAM计算机的 2N／ n+logn时间相比,
? 多了两项 glogn和 Llogn
哈尔滨工业大学计算机科学与技术学院
?关于 BSP模型的 实际优点和 评论,
?比起 PRAM模型来,BSP模型更为现实
?除了用于进程管理的并行性开销外，
它考虑了所有其他开销。
哈尔滨工业大学计算机科学与技术学院
?五, VLSI复杂性模型
?基本概念
?VLSI复杂性模型
背景：以 Clark Thompson(1980)的
研究工作为基础的二维 VLSI芯片的
AT2模型。
哈尔滨工业大学计算机科学与技术学院
?AT2模型,
?设 A是用 VLSI电路芯片完成给定运
算的芯片面积,T为执行时间，又
设 s为运算问题的规模。
哈尔滨工业大学计算机科学与技术学院
?Thompson在其博士论文中曾指
出,
?对某些运算存在一个下界 f(s)，
有
?AT2≥O( f(s))
哈尔滨工业大学计算机科学与技术学院
?1、芯片面积 A的存储界限
?许多计算在需要处理大型数据集时
常受到存储器的限制。
?计算对存储量的需求常常决定了芯
片面积 A的下限。
哈尔滨工业大学计算机科学与技术学院
?2,AT体积的 I/O界限
?可以用乘积 AT来表示 I／ O的下限。
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
?3、等分通信界限 A1/2Ｔ
?等分面积 A1/2Ｔ，限定通信的下限。
哈尔滨工业大学计算机科学与技术学院
4、例题,
?矩阵相乘算法的 VLSI芯片的实现
(Victor Prasanna,1992)
?要求,
?在一个每行和每列处理单元 (PE)都
有广播总线的网格系统上做 n× n矩
阵乘法 C＝ A× B
?如何计算芯片面积 A和计算时间 T？
哈尔滨工业大学计算机科学与技术学院
?分析,
?二维网格结构如下图所示。
?PE间的通信通过广播总线实现 。
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
?每个 PE占据一单位面积,
?总芯片面积为 O(n2)。
?广播总线需要 O(n2)导线面积。
?nXn矩阵相乘可在此网格芯片上
完成的时间为 T＝ O(n)。
哈尔滨工业大学计算机科学与技术学院
?说明,
?PE表示成 PE(i,j),0≤i,
j≤n -1。
?存储器分布在所有的 PE上，每
个 PE只能访问自己的本地存储
器。
哈尔滨工业大学计算机科学与技术学院
?下面的并行算法，可完成 C(i,j)
＝ ∑ n-1k=0A(i,k)XB(k,j),
?其中 0≤i, j≤n -1的点积运算，
并产生全部输出元素。
哈尔滨工业大学计算机科学与技术学院
? Doall 10 for 0≤i,j≤n-1
? 10 PE(i,j) sets C(i,j) to 0／ Initializaton／
? Do 50 for 0≤k≤n-1
? Doall 20 for 0≤i≤n-1
? 20 PE(i,k) broadcast A(i,k) along is row
bus
? Doall 30 for 0≤j≤n-1
? 30 PE(k,j) broadcast B(k,j) along its column
bus ／ PE(i,j) now has A(i,k) and B(k,j)，
0≤i,j≤n/
? Doall 40 for 0≤i,j≤n-1
哈尔滨工业大学计算机科学与技术学院
? 40 PE(i,j) computes
C(i,j)← C(i,j)+A(i,k)XB(k,j)
? 50 Continue
哈尔滨工业大学计算机科学与技术学院
?点积程序算法沿 k方向有一顺序循
环，用了 n个单位时间 (迭代 )。
?已知,T＝ O(n)，所以,
AT2＝ O(n2)× (O(n))2＝ O(n4)
并行处理与体系结构
哈尔滨工业大学计算机科学与技术学院
第一章 并行计算机模型
? ?1 计算技术的现状
? ?2 多处理机和多计算机
? ?3 多向量机和 SIMD计算机
??4 并行计算机的抽象模型
? ?5 可扩展的范围和设计
哈尔滨工业大学计算机科学与技术学院
?4 并行计算机的抽象模型
? 并行计算机的理论模型是从物理模型
抽象的；
? 为开发并行算法提供了一种方便的框
架；
? 用这些模型可求得并行计算机的理论
性能界限；
? 可在芯片制作前估算芯片区的 VLSI复
杂性和执行时间。
哈尔滨工业大学计算机科学与技术学院
?一、时间与空间复杂性
?计算机求解一个规模为 s的问题
的算法复杂性取决于,
?执行时间
?存储空间
哈尔滨工业大学计算机科学与技术学院
? 时间复杂性,
?时间复杂性 g(s)为 O(f(s))，可读
作, 数量级为 f(s)”，如存在正的
常量 c和 s0，则对所有 s>s0的非负
值就有 g(s)≤ cf(s) 。
哈尔滨工业大学计算机科学与技术学院
? 空间复杂性
? 为问题规模 s的函数。
? 渐近空间复杂性 (asymptotic spacecom—
plexity)主要与大问题的数据存储有关，而程
序 (代码 )存储的需求和输入数据的存储不考虑
在内。
? 串行算法的时间复杂性简称为串行复杂性 ;
? 并行算法的时间复杂性就称为并行复杂性 ;
? 并行复杂性应比串行复杂性低，至少是相
近。
? 只考虑确定性算法。
哈尔滨工业大学计算机科学与技术学院
? NP完全性,
? P类 (即多项式类 ),
? 具有多项式复杂性算法的问题集，如果存在一
多项式 p(s)，对任何问题规模 s的时间复杂性为
O(p(s))，则某算法即具有多项式复杂性。
? NP类 (即不确定性多项式类 )：能以多项式时
间，用不确定性算法求解的问题集。
? P?NP
? 确定性算法是不确定算法的特殊情况。
? P类问题是计算易解的，而 NP-P类问题是难
解的。
哈尔滨工业大学计算机科学与技术学院
? 现在不知道是否 P＝ NP或 P≠ NP。
? 难解的 NP类问题又称为具有指数时间
复杂性的问题。
哈尔滨工业大学计算机科学与技术学院
?例题：多项式复杂性和指数复杂性
算法,
?将几个数排序的多项式时间复杂性
分别为 O(nlogn)，属于 P类
?对两个 n× n矩阵相乘算法的多项式
时间复杂性分别为 O(n3)，属于 P类。
哈尔滨工业大学计算机科学与技术学院
?旅行推销员问题复杂性为 O(n22n)和
背包问题的复杂性为 O(2n/2 )
?指数复杂性问题是属 NP类的,
?到目前为止还未发现这类问题的确定
性多项式算法。
哈尔滨工业大学计算机科学与技术学院
P,NP和 NPC（ NP完全问题）
哈尔滨工业大学计算机科学与技术学院
? 二,并行随机存取机模型
(Parallel Random— Access Machine，
PRAM)
?目的：可用来开发并行算法和分析
可扩展性及复杂性。
哈尔滨工业大学计算机科学与技术学院
?MIMD
?细粒度
?严格同步
?零开销
?共享变量
哈尔滨工业大学计算机科学与技术学院
? 在 PRAM上的一个并行程序由 n个进程组
成，其中第 i个进程留驻在第 i个处理
器上，且由一串指令所组成。
? 在每个基本时间步 (称为周期 )，每个
处理器执行一条指令。
? 这些指令包括数据传送、算 /逻、控制
流以及 I/O指令，在典型的顺序计算机
中均有这些指令。
哈尔滨工业大学计算机科学与技术学院
? 1.同构性
? 规模为 1的 PRAM退化为传统的 RAM。这种
机器为 SISD。
? 当处理器多于 1个时，一个 PRAM将访问
多个数据流，且通常可执行多个指令流。
因此 PRAM是一个 MIMD机器。
哈尔滨工业大学计算机科学与技术学院
? MIMD的特例,
? 如果在每一周期，所有处理器必须执行
相同指令，即只有一个指令流时，则
PRAM就成为单指令 (流 )、多数据
(流 )(SIMD)机器。
? (SPMD)计算：单程序、多数据，所有进
程执行同一程序，而由进程指标加以参
数化。
? SIMD和 SPMD间的差别是，在 SPMD计算中，
同一周期可以执行不同指令。
哈尔滨工业大学计算机科学与技术学院
?2,同步性
?进程 同步是严格的。
?PRAM是在指令级同步的。
哈尔滨工业大学计算机科学与技术学院
?3.交互机制
?这一属性描述了并行进程间如何相
互影响行为的特性。
?在 PRAM模型中，进程间通过共享变
量 (或共享存储器 )进行交互。
哈尔滨工业大学计算机科学与技术学院
? 4,地址空间
? 理论 PRAM模型的一个重要特征是所有进
程对所有存储单元均有相等的访问时间。
这种机器为均匀存储器访问 (UMA)。
? 在多计算机中，每个处理机有它自己的
分离地址空间。这些机器被称为具有多
地址空间。多计算机的处理机间通信不
是通过共享变量，而是借助消息传递。
哈尔滨工业大学计算机科学与技术学院
?5.存储器模型
? 各种方案的主要区别在于如何协调 CW的冲突。
? 四种 PRAM模型方案都与存储器读写如何处理
有关。
(1)EREW-PRAM模型 —— 这种模型禁止一台以上
处理机同时读、写同一存储单元
? (Snir,1982； Karp和 Ramachandran，
1988)。这是限制最大的 PRAM模型。
(2)CREW-PRAM模型 —— 用互斥使写冲突避免。
可以并行读同一存储单元。
哈尔滨工业大学计算机科学与技术学院
(3)ERCW-PRAM模型 —— 允许互斥读或并
行写同一存储单元。
(4)CRCW-PRAM模型 —— 允许在同一时刻
并行读或者并行写。
哈尔滨工业大学计算机科学与技术学院
? 写冲突可用下述四种策略之一分解,
? 共用 —— 所有同时进行的写操作将相同
数据存入热点存储单元。
? 任选 —— 将任何一个要写的数保存起来，
而其它的忽略不计。
? 最小值 —— 将处理机要写的下标值最小
的数保存起来。
? 优先 —— 对要写的数用求和或求最大值
等联想函数加以组合。
哈尔滨工业大学计算机科学与技术学院
? 6.原子操作
? 原子操作的定义：一个原子操作是指有
如下特性的一种操作。
?不可分
?有限
哈尔滨工业大学计算机科学与技术学院
? 更严格的原子操作定义,
? 需要满足以下的 4个性质。称这样的原
子操作为一个事务操作。
?原子性
?一致性
?隔离性
?持续性
哈尔滨工业大学计算机科学与技术学院
? 7.例题
? 例题 1,
? 在一台处理机数为 n3／ logn的 PRAM上，
用 O(logn)时间完成两个,nxn” 矩阵的
乘法 (Viktor Prasanna,1992)
? 设 A和 B为输入矩阵，假定最初可用的 PE
数为 n3个，后来降为 n3／ logn个。
哈尔滨工业大学计算机科学与技术学院
? 假设内存由三维阵列组成，将 A,B存入
其中两个平面。
? 假设了 PE的三维地址指标。 PE(i,j，
k),0≤k≤n -1可用来计算输出矩阵的
第 (i,j)项,0≤i, j≤n -1,n是 2的幂 。
哈尔滨工业大学计算机科学与技术学院
? 第一步，对应于每个输出的 n乘积项用 n个 PE
在 O(1)时间内进行计算。
? 第二步，这些乘积项用 O(logn)时间相加产生
一个输出。所用的 PE总数为 n3，结果存在 C(i，
j,0)中 (0≤i, j≤n -1)。
? 假定这里的 PRAM采用的是 CREW策略。
哈尔滨工业大学计算机科学与技术学院
? Step 1,
? 1,Read A(i,k)
? 2,Read B(k,j)
? 3,Compute A(i,k)× B(k,j)
? 4,Store in C(I,j,k)
? Step 2,
? 1,L←n
? 2,Repeat L←L ／ 2
? If (k<1)then
? begin
哈尔滨工业大学计算机科学与技术学院
? Read A(i,k)
? Read A(i,k)
? Compute C(i,j,k)+C(i,j,k,k+l)
? Store in C(i,j,k)
? End
? Until (l=1)
? 上述是每个 PE(i,j,k)要执行的程序。所
有 n3个 PE对 n3乘法进行并行运算。但对完成
(n3- n2 )加法最多只有 n3／ 2个 PE处于工作
状态。
哈尔滨工业大学计算机科学与技术学院
? 为了将 PE数降为 n3／ logn，可采用 nXnXn／
logn的 PE阵列。
? 每个 PE负责计算 logn个乘积项并将它们求和。
? 第一步很容易改写产生 n／ logn个部分和，每
一个部分和由 logn次乘法和 (logn-1)次加法完
成。
? 我们有数组 C(i,j,k),0≤i, j≤n -1，
0≤k≤n ／ logn-1，它们可在 log(n／ logn)时
间内完成求和，所以将第一步和第二步所花的
时间相加，我们就得到总执行时间为 2logn-
1+log(n／ logn),在 n比较大时近似为
O(logn)。
哈尔滨工业大学计算机科学与技术学院
?例题 2,PRAM步中的计算复杂性
? 假设有三个 PRAM算法 A,B和 C，当在一
个有 n个处理器的 PRAM计算机上执行时，
各自的时间复杂性为
? A--7n,
? B--(nlogn)／ 4
? C--nloglogn。
哈尔滨工业大学计算机科学与技术学院
? 根据大 O标志,
?算法 A最快,(O(n)),
?C次之,O(nloglogn),
?B为最慢,O(nlogn)。
哈尔滨工业大学计算机科学与技术学院
? 而实际上，当机器的处理器数小于、等
于 1024时,
? 有 log n<log1024=10
? 以及 loglogn≤ loglog1024<4。
? 如果，处理器数小于 1024时,
? 算法 B最快，其次是 C，而 A则是最慢的。
哈尔滨工业大学计算机科学与技术学院
?与物理模型的差异
? 实际上，这种并行计算机是不存在的。
共享存储器 SIMD机是与 PRAM模型最接近
的结构。
? 更确切地说，共享存储的同步 MIMD模式
运行。
哈尔滨工业大学计算机科学与技术学院
?四种 PRAM方案中,EREW和 CRCW是
应用最普遍的模型。
? 每个 CRCW算法可用一个 EREW算法来模拟。
? CRCW算法比一个等效的 EREW要快，经证
明，最好的 n— 处理机 EREW算法要比任一
个 n-处理机 CRCW算法慢 O(logn)倍。
? 对研究结构规则的并行性来说，用 PRAM
比用实际机器模型要好得多。
? PRAM能指出实际并行计算机性能的上限。
哈尔滨工业大学计算机科学与技术学院
? 三、异步 PRAM模型 — APRAM
? 是一个异步的 PRAM模型，简记为 APRAM
? 1.模型特点,
? 由 p个处理器组成；
? 每个处理器都有其本地存储器、局部时
钟和局部程序；
? 处理器间的通信经过共享全局存储器 ；
哈尔滨工业大学计算机科学与技术学院
?无全局时钟
?各处理器异步地独立执行各自的指令；
? 处理器任何时间依赖关系需明确地在
各处理器的程序中加入同步 (路 )障
(Synchronization Barrier)；
? 一条指令可在非确定但有限的时间内
完成。
哈尔滨工业大学计算机科学与技术学院
? 2,APRAM模型中的指令类型有四类指
令,
? ① 全局读
?将全局存储单元中的内容读入局存
单元中；
? ② 局部操作
?对局存中的数执行操作，其结果存
入局存中；
哈尔滨工业大学计算机科学与技术学院
? ③ 全局写
?将局存单元中的内容写入全局存储
单元中；
? ④ 同步
?同步是计算中的一个逻辑点，在该
点各处理器均需等待别的处理器到
达后，才能执行其局部程序。
哈尔滨工业大学计算机科学与技术学院
? 3,APRAM模型中完成的计算
? 计算是由一系列用同步障分开的全局相所组成。
? 在各全局相内，每个处理器异步地运行其局
部程序；
? 每个局部程序中的最后一条指令是一条同步障
指令；
? 各处理器均可异步地读取和写入全局存储器,
? 在同一相内不允许两个处理器访问同一单元。
? 不同的处理器访问存储单元总是由一同步障所分开，
所以指令完成时间上的差异并不影响整个计算
哈尔滨工业大学计算机科学与技术学院
? 4,APRAM模型中的时间计算
? 使用 APRAM模型计算算法的时间复杂度时，
假定局部操作取单位时间；
? 全局读／写时间为 d
? 它定量化了通信延迟，代表读 /写全局存
储器的平均时间,d随机器中的处理器增
加而增加；
? 同步障的时间为 B
? 它是处理器数 P的非降函数 B=B(P)。
哈尔滨工业大学计算机科学与技术学院
? 在 APRAM中假定上述参数服从如下关系,
? 2≤d≤B≤P
? 同时,B(P)∈ O(dlogP)或
B(P)∈ O(dlogP/logd)。
? 令 tph为全局相内各处理器指令执行时间中
最长者，则整个程序运行时间 T为各相的时
间之和加上 B乘以同步障次数，即,
? T=∑t ph+B× 同步障次数
哈尔滨工业大学计算机科学与技术学院
?四, BSP模型
? BSP-Bulk Synchronization Parallel
? 1,BSP模型的提出,
? 哈佛大学的 Leslie Valiant提出,
? 块同步并行 (BSP)，用以克服 PRAM模型的
缺点，但保留其简单性。
? 一个 BSP计算机由 n个结点 (处理器和存
储器对 )所组成。
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
?2.特点,
? 一个 BSP程序有 n个进程，每个驻留在
一个结点上。基本时间单位是周期 (或
时间步 )。
? 程序按严格的超步序列执行。
哈尔滨工业大学计算机科学与技术学院
?特点,
?同步路障迫使进程等待
?BSP计算机是 MIMD系统
?BSP模型是超步级的松同步
?在一个超步中，不同进程以不同速
率异步执行。
?BSP模型交互机制是共享变量或是
消息传递。
哈尔滨工业大学计算机科学与技术学院
?3.h关系的定义,
? 一个 h关系是任何通信操作的抽象，在
其中，每个结点最多发出 h个字到各结
点，并且每个结点最多接收 h个字。
? 在一个 BSP计算机中，实现任何 h关系
的时间不会超过 gh个周期。
?g是由机器平台决定的一个常数。
哈尔滨工业大学计算机科学与技术学院
?4.一个超步执行时间的确定
?计算时间 w
?处理器中完成计算操作所需的最大
周期数。
?同步开销为 L。
?通信开销为 gh周期
?g是实现 h关系的比例系数，常数。
哈尔滨工业大学计算机科学与技术学院
?结论,
?执行一个超步的时间为 w+gh+L
哈尔滨工业大学计算机科学与技术学院
?5.例题,
? 在一个有 n个处理器的 EREW PRAM计算
机上，对两个 N维向量 A和 B求内积 s，
可指派每个处理器完成 2N／ n个加法和
乘法（ 2N／ n+logn ）；
? 改用 BSP机器模型实现一个并行执行上
述内积求解。
? 在一个有 8个处理器的 BSP计算机上，
用 4个超步完成问题求解,
哈尔滨工业大学计算机科学与技术学院
?超步１,
?每个处理器在 w=2N／ 8周期内计算，
求出局部和。
?通信 1次：处理器 0,2,4,6将其局
部和 → 处理器 1,3,5,7。
?路障同步。
哈尔滨工业大学计算机科学与技术学院
?超步２,
?计算１、３、５、７各自完成一次
加法；
?通讯 1次,处理器１，５中间结果
送处理器３和７。
?路障同步
哈尔滨工业大学计算机科学与技术学院
?超步３,
?计算：处理器３和处理器７，各完
成一次加；
?通讯：处理器３ → 处理器７，完成
一次通讯
?路障同步。
哈尔滨工业大学计算机科学与技术学院
?超步 4计算,
?处理器 7完成一次加法 (w＝１）产
生最后和。
?不再需要任何通信或同步。
哈尔滨工业大学计算机科学与技术学院
?总执行时间,
?2N／ 8+3g+3Ｌ +3个周期
? 总之,
? 点积在一个有 n个处理器的 BSP计算机
上，执行时间为,
2N／ n+logｎ (g+L+1)个周期。
? 与 PRAM计算机的 2N／ n+logn时间相比,
? 多了两项 glogn和 Llogn
哈尔滨工业大学计算机科学与技术学院
?关于 BSP模型的 实际优点和 评论,
?比起 PRAM模型来,BSP模型更为现实
?除了用于进程管理的并行性开销外，
它考虑了所有其他开销。
哈尔滨工业大学计算机科学与技术学院
?五, VLSI复杂性模型
?基本概念
?VLSI复杂性模型
背景：以 Clark Thompson(1980)的
研究工作为基础的二维 VLSI芯片的
AT2模型。
哈尔滨工业大学计算机科学与技术学院
?AT2模型,
?设 A是用 VLSI电路芯片完成给定运
算的芯片面积,T为执行时间，又
设 s为运算问题的规模。
哈尔滨工业大学计算机科学与技术学院
?Thompson在其博士论文中曾指
出,
?对某些运算存在一个下界 f(s)，
有
?AT2≥O( f(s))
哈尔滨工业大学计算机科学与技术学院
?1、芯片面积 A的存储界限
?许多计算在需要处理大型数据集时
常受到存储器的限制。
?计算对存储量的需求常常决定了芯
片面积 A的下限。
哈尔滨工业大学计算机科学与技术学院
?2,AT体积的 I/O界限
?可以用乘积 AT来表示 I／ O的下限。
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
?3、等分通信界限 A1/2Ｔ
?等分面积 A1/2Ｔ，限定通信的下限。
哈尔滨工业大学计算机科学与技术学院
4、例题,
?矩阵相乘算法的 VLSI芯片的实现
(Victor Prasanna,1992)
?要求,
?在一个每行和每列处理单元 (PE)都
有广播总线的网格系统上做 n× n矩
阵乘法 C＝ A× B
?如何计算芯片面积 A和计算时间 T？
哈尔滨工业大学计算机科学与技术学院
?分析,
?二维网格结构如下图所示。
?PE间的通信通过广播总线实现 。
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
?每个 PE占据一单位面积,
?总芯片面积为 O(n2)。
?广播总线需要 O(n2)导线面积。
?nXn矩阵相乘可在此网格芯片上
完成的时间为 T＝ O(n)。
哈尔滨工业大学计算机科学与技术学院
?说明,
?PE表示成 PE(i,j),0≤i,
j≤n -1。
?存储器分布在所有的 PE上，每
个 PE只能访问自己的本地存储
器。
哈尔滨工业大学计算机科学与技术学院
?下面的并行算法，可完成 C(i,j)
＝ ∑ n-1k=0A(i,k)XB(k,j),
?其中 0≤i, j≤n -1的点积运算，
并产生全部输出元素。
哈尔滨工业大学计算机科学与技术学院
? Doall 10 for 0≤i,j≤n-1
? 10 PE(i,j) sets C(i,j) to 0／ Initializaton／
? Do 50 for 0≤k≤n-1
? Doall 20 for 0≤i≤n-1
? 20 PE(i,k) broadcast A(i,k) along is row
bus
? Doall 30 for 0≤j≤n-1
? 30 PE(k,j) broadcast B(k,j) along its column
bus ／ PE(i,j) now has A(i,k) and B(k,j)，
0≤i,j≤n/
? Doall 40 for 0≤i,j≤n-1
哈尔滨工业大学计算机科学与技术学院
? 40 PE(i,j) computes
C(i,j)← C(i,j)+A(i,k)XB(k,j)
? 50 Continue
哈尔滨工业大学计算机科学与技术学院
?点积程序算法沿 k方向有一顺序循
环，用了 n个单位时间 (迭代 )。
?已知,T＝ O(n)，所以,
AT2＝ O(n2)× (O(n))2＝ O(n4)
