? 构成多处理机协同工作的互连网络
(性能参数、类型、机理 )
支持多处理机协同工作的同步技术
并行化技术 ---把一个具体问题用并行化方式解决的支持技术
多处理机实例第七章 多处理机
7.1 引 言单处理机 的发展正在走向尽头,并行计算机 在未来将会发挥更大的作用?
1,获得超过单处理器的性能，最直接的方法就是把多个处理器连在一起；
2,自 1985年以来，体系结构的改进使性能迅速提高，
这种改进的速度能否持续下去还不清楚，但通过复杂度和硅技术的提高而得到的性能的提高正在减小；
3,并行计算机应用软件已有缓慢但稳定的发展。
本章重点,
中小规模的机器 (处理器的个数＜ 100)
（多处理机设计的主流）
7.1.1
1,按照 Flynn分类法，可把计算机分成
单指令流单数据流 （ SISD）
单指令流多数据流（ SIMD）
多指令流单数据流（ MISD）
多指令流多数据流（ MIMD）
2,MIMD已成为通用多处理机体系结构的选择，原因,
(1) MIMD具有灵活性：
高性能单用户机
(2) MIMD可以充分利用商品化微处理器在性能价格
3,根据多处理机系统中处理器个数的多少，可把现有的 MIMD机器分为两类
（每一类代表了一种存储器的结构和互连策略）
(1) 集中式共享存储器结构这类机器有时被称为 UMA(uniform memory
access)机器。
C P U 0
C a c he
C P U 1
C a c he
C P U 2
C a c he
C P U 3
C a c he
存储器
I / O
适用于处理机数目不大情况。
(2) 分布式存储器结构每个结点包含：
◆ 在许多情况下，分布式存储器结构优于采用集中式共享存储器结构。
◆
处理器
存储器
I／ O
互连网络
I / o 存储器 I / o 存储器 I / o 存储器 I / o存储器
C P U 0
C a c h e
C P U 1
C a c h e
C P U 2
C a c h e
C P U 3
C a c h e
存储器 I / o 存储器 I / o 存储器 I / o 存储器 I / o
C P U 4
C a c h e
C P U 5
C a c h e
C P U 6
C a c h e
C P U 7
C a c h e
适用于处理机数目较大情况。
◆ 分布式存储器结构的 优点
(1) 如果大多数的访问是针对本结点的局部存储器，
则可降低对存储器和互连网络的带宽要求；
(2) 对局部存储器的访问延迟低。
◆ 主要 缺点处理器之间的通信较为复杂，且各处理器之间访问延迟较大。
◆ 簇,超结点 ----每个结点有多个处理器 (2 ~ 8)
7.1.2
1,两种地址空间的组织方案
(1) 物理上分离的多个存储器可作为一个逻辑上共享的存储空间进行编址。
这类机器的结构被称为 分布式共享存储器 (DSM)
或 可缩放共享存储器 (SSM)体系结构。
DSM机器被称为 NUMA(non-uniform memory access)机器。
(2) 整个地址空间由多个独立的地址空间构成，它们在逻辑上也是独立的，远程的处理器不能对其直接寻址。
每一个处理器 -存储器模块实际上是一个单独的计算机，这种机器也称为 多计算机 。
2,两种通信模型这种机器常称为 消息传递机器
共享地址空间的机器利用 Load和 Store指令中的地址隐含地进行数据通讯。
多个地址空间的机器通过处理器间显式地传递消息完成。
◆ 消息传递机器根据简单的网络协议，通过传递消息来请求某些服务或传输数据，从而完成通信。
例如 一个处理器要对远程存储器上的数据进行访问或操作
(1) 发送消息，请求传递数据或对数据进行操作；
远程进程调用 (RPC,remote process call)
(2) 目的处理器接收到消息以后，执行相应的操作或代替远程处理器进行访问，并发送一个应答消息将结果返回。
◆ 同步消息传递请求处理器发送一个请求后一直要等到应答结果才继续运行。
◆ 异步消息传递发送方不先经请求就直接把数据送往数据接受方。
7.1.3
1,通信带宽理想状态下的通信带宽受限于处理器、存储器和互连网络的带宽。
2,通信延迟理想状态下通信延迟应尽可能地小。
通信延迟＝发送开销＋跨越时间＋传输延迟
3,通讯延迟的隐藏程度
◆ 如何才能较好地将通信和计算或多次通信之间重叠起来，以实现通讯延迟的隐藏。
◆ 通常的原则是,只要可能就隐藏延迟。
◆ 通信延迟隐藏是一种提高性能的有效途径，但它对操作系统和编程者来讲增加了额外的负担。
上述三个指标都受到通信机制影响。
7.1.4
1.共享存储器通信的主要 优点
(1) 与常用的集中式多处理机使用的通信机制兼容。
(2) 当处理器通信活动方式复杂或动态变化时易于编程，同时在简化编译器设计方面也占有
(3) 当通信数据较小时，通信开销较低，带宽利用较好 (通信过程隐含，内存映射实现存储器保护 )。
(4) 通过硬件控制的 Cache减少了远程通信的频度，
2,消息传递通信机制的主要优点
(1)
(2) 通信是显式的，从而引起编程者和编译程序的注意，着重处理开销大的通信。
◆ 在共享存储器上支持消息传递相对简单：
将消息传递实现时转换成远端内存访问。
◆ 在消息传递的硬件上支持共享存储器就非常困难：
所有对共享存储器的访问均要求操作系统提供地址转换和存储保护功能，即将存储器访问转换为消息的发送和接收
7.1.5 并行处理面临的挑战并行处理面临着两个重要的挑战：
（ 可通过 Amdahl定律解释 ）
1,有限的并行性使机器要达到好的加速比十分困难 。
程序中有限的并行性
相对较高的通信开销例 7.1 如果想用 100个处理器达到 80的加速比,
求原计算程序中串行部分所占比例 。
解 Amdahl定律为加速比＝
得出,并行比例＝ 0.9975
可以看出要用 100个处理器达到 80的加速比，串行计算的部分只能占 0.25%。
1
可加速部分比例理论加速比 ＋ （ 1－可加速部分比例）
80＝ 1并行比例
100 ＋ （ 1－并行比例）
2,面临的第二个挑战主要是指多处理机中远程访问的较大延迟。
在现有的机器中，处理器之间的数据通信大约需要 50～ 10000个时钟周期。
机 器 通信机制 互连网络 处理机数量 典型远程存储器访问时间
SPARC Center 共享存储器 总线 ≤20 1μs
SGI Challenge 共享存储器 总线 ≤36 1μs
Cray T3D 共享存储器 3维环网 32－ 2048 1μs
Convex Exemplar 共享存储器 交叉开关＋环 8－ 64 2μs
KSR-1 共享存储器 多层次环 32－ 256 2-6μs
CM-5 消息传递 胖树 32－ 1024 10μs
Intel Paragon 消息传递 2维网格 32－ 2048 10-30μs
IBM SP-2 消息传递 多级开关 2－ 512 30-100μs
远程访问一个字的延迟时间例 7.2 一台 32个处理器的计算机，对远程存储器访问时间为 2000ns。除了通信以外，假设计算中的访问均命中局部存储器。当发出一个远程请求时，本处理器挂起。处理器时钟时间为 10ns，如果指令基本的 CPI为 1.0(设所有访存均命中 Cache)，求在没有远程访问的状态下与有 0.5%的指令需要远程访问的状态下，
前者比后者快多少?
解 有 0.5%远程访问的机器的实际 CPI
CPI＝基本 CPI＋远程访问率 × 远程访问开销
＝ 1.0＋ 0.5%× 远程访问开销远程访问开销＝远程访问时间 /时钟时间
＝ 2000ns/10ns＝ 200
∴ CPI＝ 1.0＋ 0.5%× 200＝ 2.0
它为只有局部访问的机器的 2.0／ 1.0＝ 2倍,
因此在没有远程访问的状态下的机器速度是有 0.5%
远程访问的机器速度的 2倍 。
◆ 问题的解决并行性不足,通过采用并行性更好的算法来解决远程访问延迟的降低,靠体系结构支持和编程技术
7.1.6 并行程序的 计算／通信比率
◆ 反映并行程序性能的一个重要的度量计算与通信的比率
◆ 计算／通信比率随着处理数据规模的增大而增加；随着处理器数目的增加而降低。
7.2 多处理机的存储器体系结构
◆ 多个处理器共享一个存储器。
◆ 当处理器规模较小时，这种机器十分经济。
◆ 支持对共享数据和私有数据的 Cache缓存。
私有数据供一个单独的处理器使用，而共享数据供多个处理器使用。
◆ 共享数据进入 Cache产生了一个新的问题
Cache的一致性问题
7.2.1 集中式共享存储器体系结构例 两个处理器 Cache对应同一存储器单元产生出不同的值假设：初始条件下各个 Cache无 X值,X单元值为 1；
写直达方式的 Cache
时间 事件 CPU ACache 内容 CPU B Cache 内容 X单元存储器内容
0 1
1 CPU A读 X 1 1
2 CPU B读 X 1 1
3 CPU A将 0存入 X 0 1 0
存储器是一致的（非正式地定义）
如果对某个数据项的任何读操作均可得到其最新写入的值，则认为这个 存储系统是一致的。
◆ 存储系统行为的两个不同方面
返回给读操作的是什么值
什么时候才能将已写入的值返回给读操作项编写正确共享存储器程序必须明确的问题
◆ 满足条件
① 处理器 P对 X进行一次写之后又对 X进行读，
读和写之间没有其它处理器对 X进行写，则
② 一个处理器对 X进行写之后 足够时间,另一处理器对 X进行读，读和写之间无其它写，则读 X的返回值
③ 对同一单元的写是顺序化的，即任意两个处理器对同一单元的两次写，从所有处理器看来顺序都应是相同的。
◆ 假设足够时间？
简单处理方法,直到所有的处理器均看到了写的结果，一次写操作才算完成；
2,实现一致性的基本方案在一致的多处理机中,Cache对 共享数据 提供两种功能：
共享数据的迁移降低了对远程共享数据的访问延迟。
共享数据的复制不仅降低了访存的延迟，也减少了访问共享数据所产生的冲突。
实现 Cache一致性的目的：
确保上述两种功能实现过程中不会出现 Cache的不一致。
实现方法,Cache一致性协议实现技术,小规模多处理机不是采用软件而是采用硬件技术实现 Cache一致性。
(1) Cache一致性协议对多个处理器维护一致性的协议
(2) 协议实现基础,跟踪共享数据块的状态
(3) 共享数据状态跟踪技术
◆ 目录物理存储器中共享数据块的状态及相关信息均被保存在一个称为目录的地方。
◆ 监听每个 Cache除了包含物理存储器中块的数据拷贝之外，也保存着各个块的共享状态信息。
Cache通常连在共享存储器的总线上，各个 Cache
控制器通过监听总线来判断它们是否有总线上请求的数据块。
3,
(1) 写作废协议在一个处理器写某个数据项之前保证它对该数据项例 在写回 Cache的条件下，监听总线中写作废协议的实现。
处理器行为 总线行为 CPU A Cache内容
CPU B Cache内容主存 X单元内容
0
CPU A 读 X Cache失效 0 0
CPU B 读 X Cache失效 0 0 0
CPUA将 X单元写 1 作废 X单元 1 0
CPU B 读 X Cache失效 1 1 1
(2) 写更新协议当一个处理器写某数据项时，通过广播使其它
Cache
例 在写回 Cache的条件下，监听总线中写更新协议的实现。
处理器行为 总线行为 CPUA Cache
内容
CPUB Cache
内容主存 X单元内容
0
CPU A 读 X Cach失效 0 0
CPU B 读 X Cach失效 0 0 0
CPUA将 X单元写 1
广播写 X
单元
1 1 1
CPU B 读 X 1 1 1
(3) 写更新和写作废协议 性能上的差别
◆ 对同一数据的多个写而中间无读操作的情况，
写更新协议需进行多次写广播操作，而在写
◆ 对同一块中多个字进行写，写更新协议对每个字的写均要进行一次广播，而在写作废协议下仅在对本块第一次写时进行作废操作。
◆ 从一个处理器写到另一个处理器读之间的延迟通常在写更新模式中较低。而在写作废协议中，需要读一个新的拷贝。
在基于总线的多处理机中，写作废协议成为绝大多数系统设计的选择。
4,监听协议的基本实现技术小规模多处理机中实现写作废协议进行写操作时,
a)获得总线控制权
b)将要作废的数据块地址发在总线上
c)其他处理器一直监听总线，若它们的 Cache中含有要作废的块，则作废该块
* 获得总线控制权的顺序性保证了写的顺序性 (唯一访问权 )
进行读操作时,
如果 Cache命中，从 Cache中获得数据如果 Cache不命中：
(1) 写直达 Cache，因为所有写的数据同时被写回主存，则从主存中总可以取到最新的数据值。
(2) 对于 写回 Cache，得到数据的最新值会困难一些，因为最新值可能在某个 Cache中，也可能在主存中 ----同样需要使用监听机制，如果某个处理器发现它有被读请求的块的被修改拷贝则需提供该块数据，并阻止请求方对内存的访问。
实现技术
◆ 用 Cache中块的 标志位 实现监听过程。
◆ 用 Cache中块的 有效标志 实现作废机制。
◆ 给每个 Cache块加一个 特殊的状态位 说明它是否为共享。
Cache块的拥有者,拥有唯一的 Cache块拷贝的处理器。
◆ 因为每次总线任务均要检查 Cache的地址位，这可能与 CPU对 Cache的访问冲突。可通过下列两种技术之 一降低冲突：
复制标志位或采用多级包含 Cache。
7.2.2 分布式共享存储器体系结构通常结构,存储器分布于各结点中，所有的结点通过网络互连。访问可以是本地的，也可是远程的。
不支持 Cache一致性,规定共享数据不进入 Cache，
仅私有数据才能保存在 Cache中。
优点,所需的硬件支持很少
(因为远程访问存取量仅是一个字 (或双字 )而不是一个 Cache块 )
缺点：
(1) 实现透明的软件 Cache一致性的编译机制能力有限。
编译器无法确切知道哪些数据当前共享
(2) 没有 Cache一致性，机器就不能利用取出同一块中的多个字的开销接近于取一个字的开销这个优点，这是因为共享数据是以 Cache块为单位进行管理的。当每次访问要从远程存储器取一个字时,不能有效利用共享数据的空间局部性。
(3) 诸如预取等延迟隐藏技术对于多个字的存取更为有效，比如针对一个 Cache块的预取。
解决 Cache一致性问题 关键：
寻找替代监听协议的一致性协议。
◆ 目录协议目录,用一种专用的存储器所记录的数据结构，它记录着可以进入 Cache的每个数据块的访问状态、该块在各个处理器的共享状态以及是否修改过等信息。
◆ 对每个结点增加目录表后的分布式存储器的系统结构。
互连网络
I/ o 存储器 I/ o 存储器 I/ o 存储器 I/ o 存储器
C P U 0
C a c h e
C P U 1
C a c h e
C P U 2
C a c h e
C P U 3
C a c h e
存储器 I/ o 存储器 I/ o 存储器 I/ o 存储器 I/ o
C P U 4
C a c h e
C P U 5
C a c h e
C P U 6
C a c h e
C P U 7
C a c h e
目 录目 录 目 录 目 录 目 录目 录 目 录 目 录
1,基于目录的 Cache
(1) 目录协议必须完成两个主要的操作。
处理读失效
处理对共享、干净块的写 (对一个共享块的写失效处理是这两个操作的简单结合 )
(2) 目录必须跟踪每个 Cache块的状态。
Cache块状态有三种：
共享在一个或多个处理器上具有这个块的拷贝，
且主存中的值是最新值 (所有 Cache均相同 )
未缓冲所有处理器的 Cache
专有仅有一个处理器上有此块的拷贝，且已对此块进行了写操作，而主存的拷贝仍是旧的。 这个处理器称为此块的 拥有者 。
(3) 由于写作废操作的需要，还必须记录共享此块的处理器信息。
方法：对每个主存块设臵一个 位向量 。
当此块被共享时，每个位指出与之对应的处理器是否有此块的拷贝。
当此块为专有时，可根据位向量来寻找此块
(4) 宿主结点存放有存储器块和对应地址目录项的结点。
(5) 目录协议的 基本点
◆ 在每个结点增加了目录存储器用于存放目录；
◆ 存储器的每一块在目录中对应有一项；
◆ 每一个目录项主要有 状态 和 位向量 两种成分。
状态 描述该目录所对应存储块的当前情况；
位向量 共有 N位,其每一位对应于一个处理器的局部 Cache，用于指出该 Cache中有无该存储块的拷贝。
2,目录协议的基本实现技术在基于目录的协议中，目录承担了一致性协议操作的主要功能。
(1) 发往一个目录的消息会产生两种不同类型的动作
更新目录状态
发送消息满足请求服务
(2) 目录项可能接收到三种不同的请求
读失效
写失效
数据写回
(3) 在各个状态下所接收到的请求和相应的操作
① 当一个块处于 未缓冲状态 时，对此块发出的请求及处理操作为
◆ 读失效将存储器数据送往请求方处理器，且本处理器成为此块的唯一共享结点，本块的状态转换为共享。
◆ 写失效将存储器数据送往请求方处理器，此块成为专有。
② 当一个块是 共享状态 时，存储器中的数据是其当前最新值，对此块发出的请求及处理操作为
◆ 读失效将存储器数据送往请求方处理器，并将其加入共
◆ 写失效将数据送往请求方处理器，对共享集合中所有的处理器发送写作废消息，且将共享集合臵为仅含有此
③ 当某块处于 专有状态 时,本块的最新值保存在共享集合指出的拥有者处理器中,从而有三种可能的目录请求 。
◆ 读失效将,取数据,的消息发往拥有者处理器，使该块的状态转变为共享，并将数据送回目录结点写入存储器，进而把该数据返送请求方处理器，将请求方处理器加入共享集合。
◆ 写失效本块将有一个新的拥有者。
◆ 数据写回拥有者处理器的 Cache要替换此块时必须将其写回，从而使存储器中有最新拷贝 (宿主结点实际上成为拥有者 )，此块成为非共享，共享集合为空。
3,对基于目录的 Cache一致性的多种改进
有限映射目录
链式结构目录
4,基于目录的 Cache一致性协议是完全由硬件实现的。
此外，还可以用软硬结合的办法实现。
7.3 互连网络
◆ 互连网络 是将集中式系统或分布式系统中的结点连接起来所构成的网络。
◆ 互连网络的任务是为输入和输出两组结点之间提供一组互连或映象。
◆ 好坏标准,处理单元使用率、求解算法适应性、通信速度、拓扑结构灵活性以及成本。
◆ 互连网络的分类：静态和动态静态：由点和点直接相连而成，连结方式在程序执行过程中不会改变。
动态：由开关通道实现的，连结方式在程序执行过程中可改变。
7.3.1 互连网络的性能参数
(1) 网络规模,结点数
(2) 结点度,与结点相连接的边的数目。
入度,进入结点的通道数出度,从结点出来的通道数
(3) 网络直径网络中任意两个结点间最短路径长度的最大值。
(4) 等分宽度在将某一网络切成相等两半的各种切法中，
沿切口的最小通道边数。
◆ 对称网络从其中的任何一个结点看，拓扑结构都是一样的网络。
(5) 路由在网络通信中对路径的选择与指定。
3,互连函数如果把互连网络的 N个 入端和 N个 出端各自用整数 0,1,…,N-1代表，则互连函数表示互连的出端号和入端号的一一对应关系。
4,几种数据路由功能
(1) 循环若把互连函数 f(x)表示为：
(x0,x1,x2,……,xj)
则代表对应关系为：
f(x0)=x1,f(x1)=x2,……,f(xj)=x0
j+1称为该 循环的周期。
(2) 臵换指对象的重新排序。对于 n个 对象来说，
有 n!种臵换。
例如 臵换 π=(a,b,c)(d,e) 表示了臵换映射：
f(a)=b,f(b)=c,f(c)=a,f(d)=e和 f(e)=d。
这里循环 (a,b,c)周期为 3，循环 (d,e)周期为 2。
(3) 均匀混洗
n=8（对象个数）的均匀混洗所对应的映射与其逆过程对 n=2k个对象均匀混洗，可用 k位二进制数
x=(xk-1,…,x1,x0)
来表示定义域中的每个对象。
均匀混洗将 x映射到 f(x)，得到 f(x)=( xk-2,…,x 1,x0,xk-1) 。
这是将 x循环左移 1位 得到。
(4) 超立方体路由功能例 一个三维二进制立方体网络有三种路由功能,分别根据结点的二进制地址 （ C2 C1 C0） 中的某一位来确定。
一个 n维 超立方体共有 n种 路由功能，分别由 n位 地址中的每一位求反位值来确定。将 x=(xk-1,…,x1,x0)映射到 f(x)，得到 f(x)=( xk-1,…,xk,…,x1,x0)。
(5) 广播和选播?
广播一对全体的映射
选播一个子集到另一子集 (多对多 )的映射。
5,影响互连网络性能的因素
(1) 功能特性网络如何支持路由、中断处理、同步、请求／消息组合和一致性。
(2) 网络时延单位消息通过网络传送时最坏情况下的时间延迟。
(3) 带宽通过网络的最大数据传输率，用 MB／ s表示。
(4) 硬件复杂性诸如导线、开关、连接器、仲裁和接口逻辑等的造价。
(5) 可扩展性在增加机器资源使性能可扩展的情况下，网络具备模块化可扩展的能力。
7.3.2 静态连接网络指各结点之间有专用的连结通路，且在运行中不能改变的网络。
1,线性阵列一种一维的线性网络，其中 N个结点用 N-1个链路连成一行。
内部结点度,2
端结点度,1
直径,N-1
等分宽度 b=1
2,环 和 带弦环
(1) 环用一条附加链路将线性阵列的两个端点连接起来而构成的。可以单向工作，也可以双向工作。
结点度,2
双向环的直径,N／ 2
单向环的直径,N
(2) 带弦环增加的链路愈多，结点度愈高，网络直径就愈小。
全连接网络结点度,1
直径最短,为 1。
3,循环移数网络通过在环上每个结点到所有与其 距离为 2的整数幂 的结点之间都增加一条附加链而构成的。
结点数,16
结点度,7
直径,2
如果 ｜ j-i｜ =2 r,r=0,1,2,…,n-1，网络规模
N=2n，则结点 i与结点 j连接。这种循环移数网络的结点度为 d=2n-1，直径 D=n／ 2。
4,树形 和 星形
(1) 一棵 5层 31个结点的 二叉树一般说来，一棵 k层 完全平衡的二叉树有
N=2k-1个结点。
最大结点度是 3，直径是 2(k-1)。
(2) 星形?
一种 2层树 。
结点度较高，为 d=N-1。
直径较小，是一常数 2。
5,胖树形
6,网格形 和 环网形
(1) 一个 3× 3网格形网络一般说来,N=nk 个结点的 k维 网络的内部结点度为 2k,网络直径为 k(n-1)。边结点和角结点的结点度分别为 3或 2。
(2) 环形网
◆ 可看做是直径更短的另一种网格。
◆ 环形网沿阵列每行和每列都有环形连接。
◆ 一个 n× n二元环网结点度为 4
直径为 2*[n/2」
7,超立方体
◆ 一种 二元 n-立方体 结构。
◆ 一般说来，一个 n-立方体 由 N=2n 个结点组成，
它们分布在 n维 上，每维有 两个 结点。
例 8个结点的 3-立方体
4-立方体
◆ 一个 n-立方体 的结点度等于 n，也就是网络的直径。
8,k元 n-立方体网络环形、网络形、环网形、二元 n-立方体 (超立方体 )等网络都是 k元 n-立方体网络 系统的拓扑同构体。
◆ 参数 n,立方体的维数
◆ k,基数或者说是沿每个方向的结点数 (多重性 )。
N=kn,(n=logkN)
K元 n-立方体 的结点可用基数为 k的 n位地址
A=a0a1a2…an来表示，其中 ai代表第 i维结点的位臵。
按照惯例，低维 k元 n-立方体称为环网，而高维二元 n-立方体则称为 超立方体 。
例 一种 4元 3-立方体网络
7.3.3 动态连接网络根据程序要求的通信模式，动态实现连结通路的网络
1,动态互连网络的三个主要操作特征
定时
开关
控制
2,根据级间连结方式，动态互连网络分为
(1) 单级网络也称循环网络
(2) 多级网络由一级以上的开关元件构成。
这类网络可以把任一输入与任一输出相连。
◆ 阻塞网络如果同时连接多个输入输出对时,可能会引起开关和通信链路使用上的冲突。
大多数多级网络都是阻塞网络。
◆ 非阻塞网络如果多级网络通过重新安排连接方式可以建立所有可能的输入输出之间的连接。
◆ 缺点,容易产生故障
◆ 总线研制中的重要问题
总线仲裁
中断处理
一致性协议
总线事务的处理
3,几类主要的开关网络
(1) 总线系统
◆ 优点：
价格较低带宽较窄
◆ 一种总线连接的多处理机系统
(2) 交叉开关网络单级无阻塞臵换网络
◆ 每个交叉点是一个可以打开或关闭的一元开关，提供源 (处理器 )和目的 (存储器 )之间点对点的连接通路。
◆ 交叉点开关网络中 n对 处理器可以同时传送数据。
◆ 交叉开关网络的带宽和互连特性最好。
◆ 一种交叉开关网络
(3) 多端口存储器
① 主要思想将所有交叉点仲裁逻辑和跟每个存储器模块有关的开关功能移到存储器控制器中。
② 多端口存储器结构是一个折衷方案，它介于低成本低性能的总线系统和高成本高带宽的交叉开关系统之间。
③ 缺点?
十分昂贵
不能扩展
当系统配臵很大时，需要大量的互连电缆和连接器 。
◆ 用于多处理机系统的多端口存储器结构
(4) 多级网络多级网络可用于构造大型多处理机系统。
① 一种通用多级网络各种多级网络的区别就在于所用开关模块和级间连接模式的不同。
◆ 由 a× b开关模块和级间构成的通用多级互连网络结构
② Omega网
◆ 2× 2开关四种可能的连接方式
◆ 一个 16× 16 Omega网络
③ 路 由算法举例
◆ 臵换 π 1=(0,7,6,4,2)(1,3)(5)
◆ 臵换 π 2=(0,6,4,7,3)(1,5)(2)
7.4 同步与通信
7.4.1 同步机制
1,
(1) 原子交换
◆ 将一个存储单元的值和一个寄存器的值进行交换。
◆ 将一个存储单元定义为锁，该锁的值为,0”
表示锁是开的，为,1”
实现同步的关键,操作的原子性
(2) 测试并臵定 （ test_and_set）
先测试一个值，如果符合条件则修改其值。
(3) 读取并加 1（ fetch_and_increment）
(4) 使用指令对
LL(load linked或 load locked)的取指令
SC(store conditional)的特殊存指令
LL指令,
(1)读取内存内容存入寄存器
(2)将该内存地址存入一个特殊寄存器 ----连接寄存器
(link register)中连接寄存器：
监视该内存地址，如果可能被修改，则清零
SC指令如果存储地址与连接寄存器内容一致，则将寄存器值存入该内存地址，并返回,1”，否则放弃存操作，返回,0”
什么时候该内存地址可能被修改？
(1)对应的 Cache块失效
(2)发生中断例 实现对由 R1指出的存储单元进行原子交换操作
try,mov R3,R4
ll R2,0(R1) ； load linked
sc R3,0(R1) ； store conditional
beqz R3,try
mov R4,R2 ；将取的值送往 R4
◆ LL/SC机制的一个 优点,
可用来构造别的同步原语。
例如 原子的 fetch_and_increment
try,ll R2,0(R1) ； load linked
addi R2,R2,＃ 1
sc R2,0(R1) ； store conditional
beqz R2,try
2,使用一致性实现锁采用多处理机的一致性机制 (上述用于同步的硬件原语 )来实现旋转锁。
◆ 旋转锁处理器环绕一个锁不停地旋转而请求获得该锁。
(1) 无 Cache一致性机制
◆ 实现方法在存储器中保存锁变量，处理器可以不断地通过一个原子操作请求加锁，比如先交换，再测试返回值从而知道锁的状况。释放锁的时候，处理器可简单地将锁臵为,0” 。
◆ 一个旋转锁的代码段
（ R1中的地址对应为用来进行原子交换的锁）
li R2，＃ 1
lockit,exch R2,0(R1)
bnez R2,lockit ；是否已加锁?
(2) 机器支持 Cache一致性将锁缓冲进入 Cache，并通过一致性机制使锁值保持一致。
lockit,lw R2,0(R1)
bnez R2,lockit
li R2，＃ 1
exch R2,0(R1)
bnez R2,lockit ；如果锁不为 0
(3) 旋转锁是怎样使用 Cache一致性机制的？
三个处理器竞争锁的操作步骤 处理器 P0 处理器 P1 处理器 P2 锁状态 总线 /目录操作
1 占有锁 环绕测试 lock=0 环绕测试 lock=0 Shared 无
2 将锁臵为
0
（ 收到作废命令 ） (收到作废命令 ) Exclusive P0发锁变量作废消息
3 Cache失效 Cache失效 Shared 总线 / 目录处理 P2
Cache失效,锁从 P0写回
4 总线 /目录忙则等待
Lock=0 Shared P2 Cache失效处理
5 Lock=0 执行交换,导致
Cache失效
Shared P1Cache失效处理
6 执行交换,导致
Cache失效交换完毕,返回 0
臵 lock=1
Exclusive 总线 / 目录处理 P2
Cache失效,发作废消息
7 交换完毕,返回 1 进入关键处理段
Shared 总线 / 目录处理 P2
Cache失效,写回
8 环绕测试 lock=0 无
(4) 下面代码与使用经过优化交换的代码具有相同的特点
(R1中保存锁的地址 )
lockit,ll R2,0(R1) ； load-linked
bnez R2,lockit ； 锁无效
li R2，＃ 1 ； 加锁值
sc R2,0(R1) ； 存
beqz R2,lockit ； 如果存失败则转移
3,
竞争问题例 7.3 设总线上有 20个处理器同时准备对同一变量加锁。假设每个总线事务处理 (读失效或写失效 )
是 50个时钟周期，忽略实际的 Cache块锁的读写时间以及加锁的时间，求 20个处理器请求加锁所需的总线事务数目。设时间为 0时锁已释放并且所有处理器在旋转，求处理这 20个请求时间为多长?假设总线在新的请求到达之前已服务完挂起的所有请求，并且答事件 时间所有等待的处理器取锁产生的读失效 (20× 50) 1000
释放锁的处理器导致的写失效及作废 50
所有等待的处理器的读失效 (20× 50) 1000
所有等待的处理器写失效,一个成功获得锁 (50)，
并作废其余的锁拷贝 (19× 50) 1000
一个处理器获得和释放锁的总时间 3050个时钟周期
20个处理器竞争同一锁时，从请求到释放的时间假设每个总线事务处理时间为 50个时钟周期。
上面表格给出了从一次释放锁到下一次释放锁之间发生的事件。考虑到每次获得锁后竞争的处理器数目也会减 1，从而使平均开销降为
3050/2 = 1532 个周期。
20个处理器总通过锁的时间为
20?1532 =30640 个周期。
4,栅栏 同步栅栏强制所有到达该栅栏的进程进行等待，
直到全部的进程到达栅栏，然后释放全部的进程，
从而形成同步。
(1) 栅栏的典型实现用两个 旋转锁
一个用来记录到达栅栏的进程数
一个用来封锁进程直至最后一个进程到达栅栏
Lock(counterlock)； ／ * *／
if(count=0) release=0； ／ * release *
count=count+1； ／ * *
unlock(counterlock)； ／ * *
if(count==total){ ／ * *
count=0； ／ * *
release=1； ／ * *
else { ／ * *
spin(release=1)； ／ * *
｝
其中 lock和 unlock提供基本的旋转锁,total规定了要到达栅栏的进程总数。
(2) 问题通常反复使用一个栅栏，栅栏释放的进程运行一段后又会再次返回该栅栏，这样有可能出现某个进程永远离不开栅栏的状况 (它停在旋转操作上 )。
解决方法
(1)当进程离开栅栏时进行计数 (和入口一样 )，在上次栅栏使用中的所有进程离开之前不允许任何进程重用并初始化本栅栏。
(2)sense_reversing栅栏，每个进程均使用一个私有变量 local_sense，该变量初始化为 1。而公用变量
(全局变量 ) release的初值与它们相同 (也为 1)。
local_sense=! local_sense； ／ * local-sense *
lock(counterlock)； ／ * *／
count++； ／ * *
unlock(counterlock)； ／ * *
if(count==total) { ／ * *
count=0； ／ * *
release=local_sense； ／ * *
else { ／ * *
spin(release=local_sense)；／ * *
｝
关键点,release 直到最后一个进程到达时才修改。
例 7.4 假设总线上 20个处理器同时执行一个栅栏，设每个总线事务需 50个时钟周期，忽略 Cache块中锁的读、写实际花费的时间以及栅栏实现中非同步操作的时间，计算 20个处理器全部到达栅栏，被释放及离开栅栏所需的总线事务数。设总线完全公平，整个过程需多长时间?
答 表给出一个处理器通过栅栏产生的事件序列，设第一个获得总线的进程还没有获得锁。
事件 每个处理器时间 20个处理器时间每个处理器获得锁,增量,1525 30500
释放锁的时间执行释放的时间 50 50
每个处理器获得释放标志 50 1000
的时间总和 1625 31550
一个处理器通过栅栏产生的事件序列
7.4.2
希望的同步机制：
1,软件实现旋转锁
◆ 主要问题当多个进程检测并竞争锁时引起的延迟。
◆ 解决办法
(1) 当加锁失败时就人为地推延这些进程的等待时间。
在无竞争的条件下延迟较小
在竞争激烈时串行性小
◆ 具有指数延迟的旋转锁代码
li R3,1 ； R3
lockit,ll R2,0(R1) ； load linked
bnez R2,lockit
addi R2,R2,1
sc R2,0(R1) ； store conditional
bnez R2,gotit
sll R3,R3,1 ；将延迟时间增至 2倍（左移 1位）
pause R3 ；延迟 R3
j lockit
gotit：
(2) 排队锁造成串行化的原因：
(1)读取并修改 count
(2)读取 release
针对 (1)的一种解决方法：
◆ 基本思想：将 count分散成多个变量。
◆ 使用 组合树 ---- k叉树结构。
◆ 每个叶子对应 k个进程
◆ 基本过程：每个 结 点的计数
(1)小于 k:等待解锁
(2)等于 k:将控制权转移至父 结 点
struct node ｛ ／ * *
int counterlock； ／ * *
int count； ／ * *
int parent； ／ * -1 *
struct node tree ［ 0..p-1］； ／ * *
int local_sense； ／ * *
int release； ／ * *
／ * *
barrier(int mynode)
lock(tree[mynode].counterlock)； ／ * *
tree[mynode],count++； ／ * *
unlock(tree[mynode].conterlock)； ／ * *
if(tree[mynode].count==k)｛ ／ * *
if(tree[mynode].parent)>=0｛
barrier(tree[mynode］,parent)；
｝ else｛
release=local_sense；
tree[mynode].count＝ 0； ／ * *
｝ else
spin(release=local_sense)； ／ * *／
／ * *
local_sense= ! local_sense；
barrier (mynode)；
结论：对 count的争用被限制于 k 个进程实际使用时 k=4 时效果较好
2,
◆ 两种硬件同步原语
针对锁
针对栅栏和一些要求进行计数或提供明确索引的用户级操作
◆ 排队锁排队记录等待的进程，当锁释放时送出一
(1) 工作过程
在第一次取锁变量失效时，失效被送入同步控制器。
如果锁空闲，将其交给该处理器；
如果锁忙，控制器产生一个结点请求记录 (比如可以是向量中某一位 )，并将锁忙的标志返回给处理器，
然后该处理器进入旋转等待。
当该锁被释放时，控制器从等待的进程排队中选出一个使用该锁。
例 7.5 如果在排队锁的使用中，失效时进行锁更新，求 20个处理器完成 lock和 unlock所需的时间和总答 每个处理器初始加锁及随后释放锁各产生 1次失效，所以总共需 40个总线事务。 20个初始失效需
1000个时钟周期，接着是每次需要 50个周期的 20次释放，总和为 2050个周期。与通常的基于 Cache一致性的旋转锁相比，性能大大提高。
(2) 关键问题
◆ 需要识别出对锁进行初次访问的进程，从而对其进行排队操作；
◆ 等待进程队列可通过多种机制实现；
◆ 有硬件来回收锁。
(3) Fetch_and_increment原语原子地取值并增量，返回的值可以为增量后的值，也可以为取出的值。
例 7.6 写出采用 fetch_and_increment栅栏的代码。
条件与前面假设相同，并设一次 fetch_and_increment
操作也需 50个时钟周期。计算 20个处理器通过栅栏的答 下面的程序段给出栅栏的代码，这种实现需要进行 20次 fetch_and_increment操作，释放时有 20次
Cache失效，总共需时间 2000个时钟周期,40个总线事务操作。与前面实现的栅栏机制相比，前面所需时间长达 15倍，总线操作多达 10倍。当然，实现组合树栅栏时也可采用 fetch_and_increment来降低树中每个结
local_sense= ! local_sense； ／ * local_sense *／
fetch_and_increment(count)； ／ * *
if(count==total){ ／ * *
count=0； ／ * *
release=local_sense； ／ * *
｝
else { ／ * *
spin(releaze=local_sense)； ／ * *
}
7.5 并行化技术
7.5.1 并行化的基本策略并行程序设计模型是专门为 多处理机,多计算机或 向量／ SIMD计算机而设计的。
并行性的五种模型,
1,共享变量模型
(1) 多处理机程序设计的基础利用共享变量来实现进程间的通信。
这需要使用共享存储器以及访问同一组共享变量的多个进程间的同步特性。
(2) 遇到的主要问题?
临界区的保护性访问
存储器的一致性
存储操作的可分性
快速同步
共享的数据结构
快速数据迁移技术
2,消息传递模型驻留在不同处理机结点上的两个进程可以通过网络传递消息来相互通信。
消息可以是指令、数据、同步信号或中断信号等。
(1) 同步消息传递在时间和空间上必须对发送进程和接收进程实现同步。
(2) 异步消息传递
◆ 通道中常用缓冲区。
◆ 倘若缓冲区足够大或网络通信量不饱和，则消息传递就不会阻塞。
◆ 不管接收者是否准备好，都允许发送者发送消息而不被阻塞。
◆ 关键问题如何把程序代码和数据分布或复制到所有处理结点上。
3,数据并行模型
◆ 数据并行程序要求使用预先分布好的数据集。
◆ 数据并行程序设计强调的是局部计算和数据路由操作。
◆ 数据并行性取决于粒度大小以及所采用的操作方式。
◆ 数据并行通常研究有几千个并发数据操作的高度并行性问题。
4,面向对象模型
◆ 对象把数据和操作封装在一个计算单元中的程序实体。
◆ 对象是动态建立和控制的。
◆ 处理是通过在对象间发送和接收消息来完成的。
5,函数和逻辑模型
(1) 函数程序设计模型强调程序的函数性，程序在执行后不应该产生副作用。
(2) 逻辑程序设计模型以谓词逻辑为基础，适用于涉及大型数据库的知识处理。
7.5.2 并行语言与编译器
1,并行性的语言特征并行程序设计的语言特性：
(1) 优化特性
(2) 可用性包括,? 扩展性
兼容性
可移植性
(3) 同步／通信特性主要包括,?
共享变量 (锁 )的支持
消息传递的发送／接收
远程过程调用
栅栏同步机制和邮 箱
(4) 并行性控制包括以各种形式确定并行性的控制结构。
主要处理：
各种粒度的并行性
显式并行性与隐式并行性
整个程序中的全局并行性
迭代中的循环并行性
任务分割并行性
共享任务队列
共享抽象数据类型
(5) 数据并行性说明访问数据以及把数据分布在多处理计算机上的方法。
主要包括：
◆ 无需用户干预的运行时数据自动分布；
◆ 为用户提供一种能指定通信模式或说明数据和进程映射到硬件上的方法；
◆ 编译器将虚处理机动态或静态地映射到物理处理机上的虚拟处理机支持；
◆ 共享数据可被直接访问而不用管程控制；
◆ SPMD(single program multiple data)程序设计支持。
(6) 进程管理特性用来支持并行进程的高效创建、多线程处理和多任务处理的实现、程序划分和复制以及运行 时的动态负载平衡。
2,并行语言结构
(1) Fortran 90数组表示符多维数组是用一个带下标三元组序列的数组名来表示的，每维一个三元组，不同维的三元组用逗号隔开。
例如
e1,e2,e3
e1,e2
e1,*,e3
e1,*
e1
*
每个 ei一定是能产生一个标量整数值的算术表达式。
(2) 并行流控制
◆ (Doall,Endall)语句对说明并行活动
◆ (Doacross,Endacross)语句说明循环体间相关并行性。
例如,Doacross I=2,N
Do J=2,N
S1:A(I,J)=(A(I(J-1))+A(I,J+1))／ 2
Enddo
Endacross
◆ (Cobegin,Coend)语句对
Cobegin
P1
P2
.
.
.
Coend
◆ Fork和 Join命令在进程 P的执行过程中，可以使用 Fork Q命令来产生一个新的进程 Q：
Process P Process Q
.,
.,
.,
Fork Q
.,
.,
.,
Join Q End
3,并行优化编译器由三个主要部分组成：
流分析
优化
代码生成
(1) 流分析为确定源代码中的数据和控制一致性，将程序流的模式分析出来。
数据相关控制相关重用分析向量化并行化局部性，流水线操作粒度并行度代码调度源代码流分析程序优化并行代码生成分布存储器多计算机，分布数据，计算，
消息传递，…
超标量处理机；
调度,
寄存器分配,
现场切换共享存储器多处理机，划分，同步，负载平衡，…
(2) 程序优化
◆ 目的,尽可能多地挖掘硬件的潜能。
◆ 最终目标,使代码执行速度达到最高。
◆ 要求
代码的长度最短
存储器的访问次数最少
程序并行性得到较好的开发
优化技术包括：
用流水线硬件完成向量化
同时用多台处理机实现并行化
(3) 并行代码生成
◆ 涉及从一种描述到另一种称之为中间形式描述的转换。
◆ 代码生成与所用的指令调度策略是紧密联系在一起的。
(性能参数、类型、机理 )
支持多处理机协同工作的同步技术
并行化技术 ---把一个具体问题用并行化方式解决的支持技术
多处理机实例第七章 多处理机
7.1 引 言单处理机 的发展正在走向尽头,并行计算机 在未来将会发挥更大的作用?
1,获得超过单处理器的性能，最直接的方法就是把多个处理器连在一起；
2,自 1985年以来，体系结构的改进使性能迅速提高，
这种改进的速度能否持续下去还不清楚，但通过复杂度和硅技术的提高而得到的性能的提高正在减小；
3,并行计算机应用软件已有缓慢但稳定的发展。
本章重点,
中小规模的机器 (处理器的个数＜ 100)
（多处理机设计的主流）
7.1.1
1,按照 Flynn分类法，可把计算机分成
单指令流单数据流 （ SISD）
单指令流多数据流（ SIMD）
多指令流单数据流（ MISD）
多指令流多数据流（ MIMD）
2,MIMD已成为通用多处理机体系结构的选择，原因,
(1) MIMD具有灵活性：
高性能单用户机
(2) MIMD可以充分利用商品化微处理器在性能价格
3,根据多处理机系统中处理器个数的多少，可把现有的 MIMD机器分为两类
（每一类代表了一种存储器的结构和互连策略）
(1) 集中式共享存储器结构这类机器有时被称为 UMA(uniform memory
access)机器。
C P U 0
C a c he
C P U 1
C a c he
C P U 2
C a c he
C P U 3
C a c he
存储器
I / O
适用于处理机数目不大情况。
(2) 分布式存储器结构每个结点包含：
◆ 在许多情况下，分布式存储器结构优于采用集中式共享存储器结构。
◆
处理器
存储器
I／ O
互连网络
I / o 存储器 I / o 存储器 I / o 存储器 I / o存储器
C P U 0
C a c h e
C P U 1
C a c h e
C P U 2
C a c h e
C P U 3
C a c h e
存储器 I / o 存储器 I / o 存储器 I / o 存储器 I / o
C P U 4
C a c h e
C P U 5
C a c h e
C P U 6
C a c h e
C P U 7
C a c h e
适用于处理机数目较大情况。
◆ 分布式存储器结构的 优点
(1) 如果大多数的访问是针对本结点的局部存储器，
则可降低对存储器和互连网络的带宽要求；
(2) 对局部存储器的访问延迟低。
◆ 主要 缺点处理器之间的通信较为复杂，且各处理器之间访问延迟较大。
◆ 簇,超结点 ----每个结点有多个处理器 (2 ~ 8)
7.1.2
1,两种地址空间的组织方案
(1) 物理上分离的多个存储器可作为一个逻辑上共享的存储空间进行编址。
这类机器的结构被称为 分布式共享存储器 (DSM)
或 可缩放共享存储器 (SSM)体系结构。
DSM机器被称为 NUMA(non-uniform memory access)机器。
(2) 整个地址空间由多个独立的地址空间构成，它们在逻辑上也是独立的，远程的处理器不能对其直接寻址。
每一个处理器 -存储器模块实际上是一个单独的计算机，这种机器也称为 多计算机 。
2,两种通信模型这种机器常称为 消息传递机器
共享地址空间的机器利用 Load和 Store指令中的地址隐含地进行数据通讯。
多个地址空间的机器通过处理器间显式地传递消息完成。
◆ 消息传递机器根据简单的网络协议，通过传递消息来请求某些服务或传输数据，从而完成通信。
例如 一个处理器要对远程存储器上的数据进行访问或操作
(1) 发送消息，请求传递数据或对数据进行操作；
远程进程调用 (RPC,remote process call)
(2) 目的处理器接收到消息以后，执行相应的操作或代替远程处理器进行访问，并发送一个应答消息将结果返回。
◆ 同步消息传递请求处理器发送一个请求后一直要等到应答结果才继续运行。
◆ 异步消息传递发送方不先经请求就直接把数据送往数据接受方。
7.1.3
1,通信带宽理想状态下的通信带宽受限于处理器、存储器和互连网络的带宽。
2,通信延迟理想状态下通信延迟应尽可能地小。
通信延迟＝发送开销＋跨越时间＋传输延迟
3,通讯延迟的隐藏程度
◆ 如何才能较好地将通信和计算或多次通信之间重叠起来，以实现通讯延迟的隐藏。
◆ 通常的原则是,只要可能就隐藏延迟。
◆ 通信延迟隐藏是一种提高性能的有效途径，但它对操作系统和编程者来讲增加了额外的负担。
上述三个指标都受到通信机制影响。
7.1.4
1.共享存储器通信的主要 优点
(1) 与常用的集中式多处理机使用的通信机制兼容。
(2) 当处理器通信活动方式复杂或动态变化时易于编程，同时在简化编译器设计方面也占有
(3) 当通信数据较小时，通信开销较低，带宽利用较好 (通信过程隐含，内存映射实现存储器保护 )。
(4) 通过硬件控制的 Cache减少了远程通信的频度，
2,消息传递通信机制的主要优点
(1)
(2) 通信是显式的，从而引起编程者和编译程序的注意，着重处理开销大的通信。
◆ 在共享存储器上支持消息传递相对简单：
将消息传递实现时转换成远端内存访问。
◆ 在消息传递的硬件上支持共享存储器就非常困难：
所有对共享存储器的访问均要求操作系统提供地址转换和存储保护功能，即将存储器访问转换为消息的发送和接收
7.1.5 并行处理面临的挑战并行处理面临着两个重要的挑战：
（ 可通过 Amdahl定律解释 ）
1,有限的并行性使机器要达到好的加速比十分困难 。
程序中有限的并行性
相对较高的通信开销例 7.1 如果想用 100个处理器达到 80的加速比,
求原计算程序中串行部分所占比例 。
解 Amdahl定律为加速比＝
得出,并行比例＝ 0.9975
可以看出要用 100个处理器达到 80的加速比，串行计算的部分只能占 0.25%。
1
可加速部分比例理论加速比 ＋ （ 1－可加速部分比例）
80＝ 1并行比例
100 ＋ （ 1－并行比例）
2,面临的第二个挑战主要是指多处理机中远程访问的较大延迟。
在现有的机器中，处理器之间的数据通信大约需要 50～ 10000个时钟周期。
机 器 通信机制 互连网络 处理机数量 典型远程存储器访问时间
SPARC Center 共享存储器 总线 ≤20 1μs
SGI Challenge 共享存储器 总线 ≤36 1μs
Cray T3D 共享存储器 3维环网 32－ 2048 1μs
Convex Exemplar 共享存储器 交叉开关＋环 8－ 64 2μs
KSR-1 共享存储器 多层次环 32－ 256 2-6μs
CM-5 消息传递 胖树 32－ 1024 10μs
Intel Paragon 消息传递 2维网格 32－ 2048 10-30μs
IBM SP-2 消息传递 多级开关 2－ 512 30-100μs
远程访问一个字的延迟时间例 7.2 一台 32个处理器的计算机，对远程存储器访问时间为 2000ns。除了通信以外，假设计算中的访问均命中局部存储器。当发出一个远程请求时，本处理器挂起。处理器时钟时间为 10ns，如果指令基本的 CPI为 1.0(设所有访存均命中 Cache)，求在没有远程访问的状态下与有 0.5%的指令需要远程访问的状态下，
前者比后者快多少?
解 有 0.5%远程访问的机器的实际 CPI
CPI＝基本 CPI＋远程访问率 × 远程访问开销
＝ 1.0＋ 0.5%× 远程访问开销远程访问开销＝远程访问时间 /时钟时间
＝ 2000ns/10ns＝ 200
∴ CPI＝ 1.0＋ 0.5%× 200＝ 2.0
它为只有局部访问的机器的 2.0／ 1.0＝ 2倍,
因此在没有远程访问的状态下的机器速度是有 0.5%
远程访问的机器速度的 2倍 。
◆ 问题的解决并行性不足,通过采用并行性更好的算法来解决远程访问延迟的降低,靠体系结构支持和编程技术
7.1.6 并行程序的 计算／通信比率
◆ 反映并行程序性能的一个重要的度量计算与通信的比率
◆ 计算／通信比率随着处理数据规模的增大而增加；随着处理器数目的增加而降低。
7.2 多处理机的存储器体系结构
◆ 多个处理器共享一个存储器。
◆ 当处理器规模较小时，这种机器十分经济。
◆ 支持对共享数据和私有数据的 Cache缓存。
私有数据供一个单独的处理器使用，而共享数据供多个处理器使用。
◆ 共享数据进入 Cache产生了一个新的问题
Cache的一致性问题
7.2.1 集中式共享存储器体系结构例 两个处理器 Cache对应同一存储器单元产生出不同的值假设：初始条件下各个 Cache无 X值,X单元值为 1；
写直达方式的 Cache
时间 事件 CPU ACache 内容 CPU B Cache 内容 X单元存储器内容
0 1
1 CPU A读 X 1 1
2 CPU B读 X 1 1
3 CPU A将 0存入 X 0 1 0
存储器是一致的（非正式地定义）
如果对某个数据项的任何读操作均可得到其最新写入的值，则认为这个 存储系统是一致的。
◆ 存储系统行为的两个不同方面
返回给读操作的是什么值
什么时候才能将已写入的值返回给读操作项编写正确共享存储器程序必须明确的问题
◆ 满足条件
① 处理器 P对 X进行一次写之后又对 X进行读，
读和写之间没有其它处理器对 X进行写，则
② 一个处理器对 X进行写之后 足够时间,另一处理器对 X进行读，读和写之间无其它写，则读 X的返回值
③ 对同一单元的写是顺序化的，即任意两个处理器对同一单元的两次写，从所有处理器看来顺序都应是相同的。
◆ 假设足够时间？
简单处理方法,直到所有的处理器均看到了写的结果，一次写操作才算完成；
2,实现一致性的基本方案在一致的多处理机中,Cache对 共享数据 提供两种功能：
共享数据的迁移降低了对远程共享数据的访问延迟。
共享数据的复制不仅降低了访存的延迟，也减少了访问共享数据所产生的冲突。
实现 Cache一致性的目的：
确保上述两种功能实现过程中不会出现 Cache的不一致。
实现方法,Cache一致性协议实现技术,小规模多处理机不是采用软件而是采用硬件技术实现 Cache一致性。
(1) Cache一致性协议对多个处理器维护一致性的协议
(2) 协议实现基础,跟踪共享数据块的状态
(3) 共享数据状态跟踪技术
◆ 目录物理存储器中共享数据块的状态及相关信息均被保存在一个称为目录的地方。
◆ 监听每个 Cache除了包含物理存储器中块的数据拷贝之外，也保存着各个块的共享状态信息。
Cache通常连在共享存储器的总线上，各个 Cache
控制器通过监听总线来判断它们是否有总线上请求的数据块。
3,
(1) 写作废协议在一个处理器写某个数据项之前保证它对该数据项例 在写回 Cache的条件下，监听总线中写作废协议的实现。
处理器行为 总线行为 CPU A Cache内容
CPU B Cache内容主存 X单元内容
0
CPU A 读 X Cache失效 0 0
CPU B 读 X Cache失效 0 0 0
CPUA将 X单元写 1 作废 X单元 1 0
CPU B 读 X Cache失效 1 1 1
(2) 写更新协议当一个处理器写某数据项时，通过广播使其它
Cache
例 在写回 Cache的条件下，监听总线中写更新协议的实现。
处理器行为 总线行为 CPUA Cache
内容
CPUB Cache
内容主存 X单元内容
0
CPU A 读 X Cach失效 0 0
CPU B 读 X Cach失效 0 0 0
CPUA将 X单元写 1
广播写 X
单元
1 1 1
CPU B 读 X 1 1 1
(3) 写更新和写作废协议 性能上的差别
◆ 对同一数据的多个写而中间无读操作的情况，
写更新协议需进行多次写广播操作，而在写
◆ 对同一块中多个字进行写，写更新协议对每个字的写均要进行一次广播，而在写作废协议下仅在对本块第一次写时进行作废操作。
◆ 从一个处理器写到另一个处理器读之间的延迟通常在写更新模式中较低。而在写作废协议中，需要读一个新的拷贝。
在基于总线的多处理机中，写作废协议成为绝大多数系统设计的选择。
4,监听协议的基本实现技术小规模多处理机中实现写作废协议进行写操作时,
a)获得总线控制权
b)将要作废的数据块地址发在总线上
c)其他处理器一直监听总线，若它们的 Cache中含有要作废的块，则作废该块
* 获得总线控制权的顺序性保证了写的顺序性 (唯一访问权 )
进行读操作时,
如果 Cache命中，从 Cache中获得数据如果 Cache不命中：
(1) 写直达 Cache，因为所有写的数据同时被写回主存，则从主存中总可以取到最新的数据值。
(2) 对于 写回 Cache，得到数据的最新值会困难一些，因为最新值可能在某个 Cache中，也可能在主存中 ----同样需要使用监听机制，如果某个处理器发现它有被读请求的块的被修改拷贝则需提供该块数据，并阻止请求方对内存的访问。
实现技术
◆ 用 Cache中块的 标志位 实现监听过程。
◆ 用 Cache中块的 有效标志 实现作废机制。
◆ 给每个 Cache块加一个 特殊的状态位 说明它是否为共享。
Cache块的拥有者,拥有唯一的 Cache块拷贝的处理器。
◆ 因为每次总线任务均要检查 Cache的地址位，这可能与 CPU对 Cache的访问冲突。可通过下列两种技术之 一降低冲突：
复制标志位或采用多级包含 Cache。
7.2.2 分布式共享存储器体系结构通常结构,存储器分布于各结点中，所有的结点通过网络互连。访问可以是本地的，也可是远程的。
不支持 Cache一致性,规定共享数据不进入 Cache，
仅私有数据才能保存在 Cache中。
优点,所需的硬件支持很少
(因为远程访问存取量仅是一个字 (或双字 )而不是一个 Cache块 )
缺点：
(1) 实现透明的软件 Cache一致性的编译机制能力有限。
编译器无法确切知道哪些数据当前共享
(2) 没有 Cache一致性，机器就不能利用取出同一块中的多个字的开销接近于取一个字的开销这个优点，这是因为共享数据是以 Cache块为单位进行管理的。当每次访问要从远程存储器取一个字时,不能有效利用共享数据的空间局部性。
(3) 诸如预取等延迟隐藏技术对于多个字的存取更为有效，比如针对一个 Cache块的预取。
解决 Cache一致性问题 关键：
寻找替代监听协议的一致性协议。
◆ 目录协议目录,用一种专用的存储器所记录的数据结构，它记录着可以进入 Cache的每个数据块的访问状态、该块在各个处理器的共享状态以及是否修改过等信息。
◆ 对每个结点增加目录表后的分布式存储器的系统结构。
互连网络
I/ o 存储器 I/ o 存储器 I/ o 存储器 I/ o 存储器
C P U 0
C a c h e
C P U 1
C a c h e
C P U 2
C a c h e
C P U 3
C a c h e
存储器 I/ o 存储器 I/ o 存储器 I/ o 存储器 I/ o
C P U 4
C a c h e
C P U 5
C a c h e
C P U 6
C a c h e
C P U 7
C a c h e
目 录目 录 目 录 目 录 目 录目 录 目 录 目 录
1,基于目录的 Cache
(1) 目录协议必须完成两个主要的操作。
处理读失效
处理对共享、干净块的写 (对一个共享块的写失效处理是这两个操作的简单结合 )
(2) 目录必须跟踪每个 Cache块的状态。
Cache块状态有三种：
共享在一个或多个处理器上具有这个块的拷贝，
且主存中的值是最新值 (所有 Cache均相同 )
未缓冲所有处理器的 Cache
专有仅有一个处理器上有此块的拷贝，且已对此块进行了写操作，而主存的拷贝仍是旧的。 这个处理器称为此块的 拥有者 。
(3) 由于写作废操作的需要，还必须记录共享此块的处理器信息。
方法：对每个主存块设臵一个 位向量 。
当此块被共享时，每个位指出与之对应的处理器是否有此块的拷贝。
当此块为专有时，可根据位向量来寻找此块
(4) 宿主结点存放有存储器块和对应地址目录项的结点。
(5) 目录协议的 基本点
◆ 在每个结点增加了目录存储器用于存放目录；
◆ 存储器的每一块在目录中对应有一项；
◆ 每一个目录项主要有 状态 和 位向量 两种成分。
状态 描述该目录所对应存储块的当前情况；
位向量 共有 N位,其每一位对应于一个处理器的局部 Cache，用于指出该 Cache中有无该存储块的拷贝。
2,目录协议的基本实现技术在基于目录的协议中，目录承担了一致性协议操作的主要功能。
(1) 发往一个目录的消息会产生两种不同类型的动作
更新目录状态
发送消息满足请求服务
(2) 目录项可能接收到三种不同的请求
读失效
写失效
数据写回
(3) 在各个状态下所接收到的请求和相应的操作
① 当一个块处于 未缓冲状态 时，对此块发出的请求及处理操作为
◆ 读失效将存储器数据送往请求方处理器，且本处理器成为此块的唯一共享结点，本块的状态转换为共享。
◆ 写失效将存储器数据送往请求方处理器，此块成为专有。
② 当一个块是 共享状态 时，存储器中的数据是其当前最新值，对此块发出的请求及处理操作为
◆ 读失效将存储器数据送往请求方处理器，并将其加入共
◆ 写失效将数据送往请求方处理器，对共享集合中所有的处理器发送写作废消息，且将共享集合臵为仅含有此
③ 当某块处于 专有状态 时,本块的最新值保存在共享集合指出的拥有者处理器中,从而有三种可能的目录请求 。
◆ 读失效将,取数据,的消息发往拥有者处理器，使该块的状态转变为共享，并将数据送回目录结点写入存储器，进而把该数据返送请求方处理器，将请求方处理器加入共享集合。
◆ 写失效本块将有一个新的拥有者。
◆ 数据写回拥有者处理器的 Cache要替换此块时必须将其写回，从而使存储器中有最新拷贝 (宿主结点实际上成为拥有者 )，此块成为非共享，共享集合为空。
3,对基于目录的 Cache一致性的多种改进
有限映射目录
链式结构目录
4,基于目录的 Cache一致性协议是完全由硬件实现的。
此外，还可以用软硬结合的办法实现。
7.3 互连网络
◆ 互连网络 是将集中式系统或分布式系统中的结点连接起来所构成的网络。
◆ 互连网络的任务是为输入和输出两组结点之间提供一组互连或映象。
◆ 好坏标准,处理单元使用率、求解算法适应性、通信速度、拓扑结构灵活性以及成本。
◆ 互连网络的分类：静态和动态静态：由点和点直接相连而成，连结方式在程序执行过程中不会改变。
动态：由开关通道实现的，连结方式在程序执行过程中可改变。
7.3.1 互连网络的性能参数
(1) 网络规模,结点数
(2) 结点度,与结点相连接的边的数目。
入度,进入结点的通道数出度,从结点出来的通道数
(3) 网络直径网络中任意两个结点间最短路径长度的最大值。
(4) 等分宽度在将某一网络切成相等两半的各种切法中，
沿切口的最小通道边数。
◆ 对称网络从其中的任何一个结点看，拓扑结构都是一样的网络。
(5) 路由在网络通信中对路径的选择与指定。
3,互连函数如果把互连网络的 N个 入端和 N个 出端各自用整数 0,1,…,N-1代表，则互连函数表示互连的出端号和入端号的一一对应关系。
4,几种数据路由功能
(1) 循环若把互连函数 f(x)表示为：
(x0,x1,x2,……,xj)
则代表对应关系为：
f(x0)=x1,f(x1)=x2,……,f(xj)=x0
j+1称为该 循环的周期。
(2) 臵换指对象的重新排序。对于 n个 对象来说，
有 n!种臵换。
例如 臵换 π=(a,b,c)(d,e) 表示了臵换映射：
f(a)=b,f(b)=c,f(c)=a,f(d)=e和 f(e)=d。
这里循环 (a,b,c)周期为 3，循环 (d,e)周期为 2。
(3) 均匀混洗
n=8（对象个数）的均匀混洗所对应的映射与其逆过程对 n=2k个对象均匀混洗，可用 k位二进制数
x=(xk-1,…,x1,x0)
来表示定义域中的每个对象。
均匀混洗将 x映射到 f(x)，得到 f(x)=( xk-2,…,x 1,x0,xk-1) 。
这是将 x循环左移 1位 得到。
(4) 超立方体路由功能例 一个三维二进制立方体网络有三种路由功能,分别根据结点的二进制地址 （ C2 C1 C0） 中的某一位来确定。
一个 n维 超立方体共有 n种 路由功能，分别由 n位 地址中的每一位求反位值来确定。将 x=(xk-1,…,x1,x0)映射到 f(x)，得到 f(x)=( xk-1,…,xk,…,x1,x0)。
(5) 广播和选播?
广播一对全体的映射
选播一个子集到另一子集 (多对多 )的映射。
5,影响互连网络性能的因素
(1) 功能特性网络如何支持路由、中断处理、同步、请求／消息组合和一致性。
(2) 网络时延单位消息通过网络传送时最坏情况下的时间延迟。
(3) 带宽通过网络的最大数据传输率，用 MB／ s表示。
(4) 硬件复杂性诸如导线、开关、连接器、仲裁和接口逻辑等的造价。
(5) 可扩展性在增加机器资源使性能可扩展的情况下，网络具备模块化可扩展的能力。
7.3.2 静态连接网络指各结点之间有专用的连结通路，且在运行中不能改变的网络。
1,线性阵列一种一维的线性网络，其中 N个结点用 N-1个链路连成一行。
内部结点度,2
端结点度,1
直径,N-1
等分宽度 b=1
2,环 和 带弦环
(1) 环用一条附加链路将线性阵列的两个端点连接起来而构成的。可以单向工作，也可以双向工作。
结点度,2
双向环的直径,N／ 2
单向环的直径,N
(2) 带弦环增加的链路愈多，结点度愈高，网络直径就愈小。
全连接网络结点度,1
直径最短,为 1。
3,循环移数网络通过在环上每个结点到所有与其 距离为 2的整数幂 的结点之间都增加一条附加链而构成的。
结点数,16
结点度,7
直径,2
如果 ｜ j-i｜ =2 r,r=0,1,2,…,n-1，网络规模
N=2n，则结点 i与结点 j连接。这种循环移数网络的结点度为 d=2n-1，直径 D=n／ 2。
4,树形 和 星形
(1) 一棵 5层 31个结点的 二叉树一般说来，一棵 k层 完全平衡的二叉树有
N=2k-1个结点。
最大结点度是 3，直径是 2(k-1)。
(2) 星形?
一种 2层树 。
结点度较高，为 d=N-1。
直径较小，是一常数 2。
5,胖树形
6,网格形 和 环网形
(1) 一个 3× 3网格形网络一般说来,N=nk 个结点的 k维 网络的内部结点度为 2k,网络直径为 k(n-1)。边结点和角结点的结点度分别为 3或 2。
(2) 环形网
◆ 可看做是直径更短的另一种网格。
◆ 环形网沿阵列每行和每列都有环形连接。
◆ 一个 n× n二元环网结点度为 4
直径为 2*[n/2」
7,超立方体
◆ 一种 二元 n-立方体 结构。
◆ 一般说来，一个 n-立方体 由 N=2n 个结点组成，
它们分布在 n维 上，每维有 两个 结点。
例 8个结点的 3-立方体
4-立方体
◆ 一个 n-立方体 的结点度等于 n，也就是网络的直径。
8,k元 n-立方体网络环形、网络形、环网形、二元 n-立方体 (超立方体 )等网络都是 k元 n-立方体网络 系统的拓扑同构体。
◆ 参数 n,立方体的维数
◆ k,基数或者说是沿每个方向的结点数 (多重性 )。
N=kn,(n=logkN)
K元 n-立方体 的结点可用基数为 k的 n位地址
A=a0a1a2…an来表示，其中 ai代表第 i维结点的位臵。
按照惯例，低维 k元 n-立方体称为环网，而高维二元 n-立方体则称为 超立方体 。
例 一种 4元 3-立方体网络
7.3.3 动态连接网络根据程序要求的通信模式，动态实现连结通路的网络
1,动态互连网络的三个主要操作特征
定时
开关
控制
2,根据级间连结方式，动态互连网络分为
(1) 单级网络也称循环网络
(2) 多级网络由一级以上的开关元件构成。
这类网络可以把任一输入与任一输出相连。
◆ 阻塞网络如果同时连接多个输入输出对时,可能会引起开关和通信链路使用上的冲突。
大多数多级网络都是阻塞网络。
◆ 非阻塞网络如果多级网络通过重新安排连接方式可以建立所有可能的输入输出之间的连接。
◆ 缺点,容易产生故障
◆ 总线研制中的重要问题
总线仲裁
中断处理
一致性协议
总线事务的处理
3,几类主要的开关网络
(1) 总线系统
◆ 优点：
价格较低带宽较窄
◆ 一种总线连接的多处理机系统
(2) 交叉开关网络单级无阻塞臵换网络
◆ 每个交叉点是一个可以打开或关闭的一元开关，提供源 (处理器 )和目的 (存储器 )之间点对点的连接通路。
◆ 交叉点开关网络中 n对 处理器可以同时传送数据。
◆ 交叉开关网络的带宽和互连特性最好。
◆ 一种交叉开关网络
(3) 多端口存储器
① 主要思想将所有交叉点仲裁逻辑和跟每个存储器模块有关的开关功能移到存储器控制器中。
② 多端口存储器结构是一个折衷方案，它介于低成本低性能的总线系统和高成本高带宽的交叉开关系统之间。
③ 缺点?
十分昂贵
不能扩展
当系统配臵很大时，需要大量的互连电缆和连接器 。
◆ 用于多处理机系统的多端口存储器结构
(4) 多级网络多级网络可用于构造大型多处理机系统。
① 一种通用多级网络各种多级网络的区别就在于所用开关模块和级间连接模式的不同。
◆ 由 a× b开关模块和级间构成的通用多级互连网络结构
② Omega网
◆ 2× 2开关四种可能的连接方式
◆ 一个 16× 16 Omega网络
③ 路 由算法举例
◆ 臵换 π 1=(0,7,6,4,2)(1,3)(5)
◆ 臵换 π 2=(0,6,4,7,3)(1,5)(2)
7.4 同步与通信
7.4.1 同步机制
1,
(1) 原子交换
◆ 将一个存储单元的值和一个寄存器的值进行交换。
◆ 将一个存储单元定义为锁，该锁的值为,0”
表示锁是开的，为,1”
实现同步的关键,操作的原子性
(2) 测试并臵定 （ test_and_set）
先测试一个值，如果符合条件则修改其值。
(3) 读取并加 1（ fetch_and_increment）
(4) 使用指令对
LL(load linked或 load locked)的取指令
SC(store conditional)的特殊存指令
LL指令,
(1)读取内存内容存入寄存器
(2)将该内存地址存入一个特殊寄存器 ----连接寄存器
(link register)中连接寄存器：
监视该内存地址，如果可能被修改，则清零
SC指令如果存储地址与连接寄存器内容一致，则将寄存器值存入该内存地址，并返回,1”，否则放弃存操作，返回,0”
什么时候该内存地址可能被修改？
(1)对应的 Cache块失效
(2)发生中断例 实现对由 R1指出的存储单元进行原子交换操作
try,mov R3,R4
ll R2,0(R1) ； load linked
sc R3,0(R1) ； store conditional
beqz R3,try
mov R4,R2 ；将取的值送往 R4
◆ LL/SC机制的一个 优点,
可用来构造别的同步原语。
例如 原子的 fetch_and_increment
try,ll R2,0(R1) ； load linked
addi R2,R2,＃ 1
sc R2,0(R1) ； store conditional
beqz R2,try
2,使用一致性实现锁采用多处理机的一致性机制 (上述用于同步的硬件原语 )来实现旋转锁。
◆ 旋转锁处理器环绕一个锁不停地旋转而请求获得该锁。
(1) 无 Cache一致性机制
◆ 实现方法在存储器中保存锁变量，处理器可以不断地通过一个原子操作请求加锁，比如先交换，再测试返回值从而知道锁的状况。释放锁的时候，处理器可简单地将锁臵为,0” 。
◆ 一个旋转锁的代码段
（ R1中的地址对应为用来进行原子交换的锁）
li R2，＃ 1
lockit,exch R2,0(R1)
bnez R2,lockit ；是否已加锁?
(2) 机器支持 Cache一致性将锁缓冲进入 Cache，并通过一致性机制使锁值保持一致。
lockit,lw R2,0(R1)
bnez R2,lockit
li R2，＃ 1
exch R2,0(R1)
bnez R2,lockit ；如果锁不为 0
(3) 旋转锁是怎样使用 Cache一致性机制的？
三个处理器竞争锁的操作步骤 处理器 P0 处理器 P1 处理器 P2 锁状态 总线 /目录操作
1 占有锁 环绕测试 lock=0 环绕测试 lock=0 Shared 无
2 将锁臵为
0
（ 收到作废命令 ） (收到作废命令 ) Exclusive P0发锁变量作废消息
3 Cache失效 Cache失效 Shared 总线 / 目录处理 P2
Cache失效,锁从 P0写回
4 总线 /目录忙则等待
Lock=0 Shared P2 Cache失效处理
5 Lock=0 执行交换,导致
Cache失效
Shared P1Cache失效处理
6 执行交换,导致
Cache失效交换完毕,返回 0
臵 lock=1
Exclusive 总线 / 目录处理 P2
Cache失效,发作废消息
7 交换完毕,返回 1 进入关键处理段
Shared 总线 / 目录处理 P2
Cache失效,写回
8 环绕测试 lock=0 无
(4) 下面代码与使用经过优化交换的代码具有相同的特点
(R1中保存锁的地址 )
lockit,ll R2,0(R1) ； load-linked
bnez R2,lockit ； 锁无效
li R2，＃ 1 ； 加锁值
sc R2,0(R1) ； 存
beqz R2,lockit ； 如果存失败则转移
3,
竞争问题例 7.3 设总线上有 20个处理器同时准备对同一变量加锁。假设每个总线事务处理 (读失效或写失效 )
是 50个时钟周期，忽略实际的 Cache块锁的读写时间以及加锁的时间，求 20个处理器请求加锁所需的总线事务数目。设时间为 0时锁已释放并且所有处理器在旋转，求处理这 20个请求时间为多长?假设总线在新的请求到达之前已服务完挂起的所有请求，并且答事件 时间所有等待的处理器取锁产生的读失效 (20× 50) 1000
释放锁的处理器导致的写失效及作废 50
所有等待的处理器的读失效 (20× 50) 1000
所有等待的处理器写失效,一个成功获得锁 (50)，
并作废其余的锁拷贝 (19× 50) 1000
一个处理器获得和释放锁的总时间 3050个时钟周期
20个处理器竞争同一锁时，从请求到释放的时间假设每个总线事务处理时间为 50个时钟周期。
上面表格给出了从一次释放锁到下一次释放锁之间发生的事件。考虑到每次获得锁后竞争的处理器数目也会减 1，从而使平均开销降为
3050/2 = 1532 个周期。
20个处理器总通过锁的时间为
20?1532 =30640 个周期。
4,栅栏 同步栅栏强制所有到达该栅栏的进程进行等待，
直到全部的进程到达栅栏，然后释放全部的进程，
从而形成同步。
(1) 栅栏的典型实现用两个 旋转锁
一个用来记录到达栅栏的进程数
一个用来封锁进程直至最后一个进程到达栅栏
Lock(counterlock)； ／ * *／
if(count=0) release=0； ／ * release *
count=count+1； ／ * *
unlock(counterlock)； ／ * *
if(count==total){ ／ * *
count=0； ／ * *
release=1； ／ * *
else { ／ * *
spin(release=1)； ／ * *
｝
其中 lock和 unlock提供基本的旋转锁,total规定了要到达栅栏的进程总数。
(2) 问题通常反复使用一个栅栏，栅栏释放的进程运行一段后又会再次返回该栅栏，这样有可能出现某个进程永远离不开栅栏的状况 (它停在旋转操作上 )。
解决方法
(1)当进程离开栅栏时进行计数 (和入口一样 )，在上次栅栏使用中的所有进程离开之前不允许任何进程重用并初始化本栅栏。
(2)sense_reversing栅栏，每个进程均使用一个私有变量 local_sense，该变量初始化为 1。而公用变量
(全局变量 ) release的初值与它们相同 (也为 1)。
local_sense=! local_sense； ／ * local-sense *
lock(counterlock)； ／ * *／
count++； ／ * *
unlock(counterlock)； ／ * *
if(count==total) { ／ * *
count=0； ／ * *
release=local_sense； ／ * *
else { ／ * *
spin(release=local_sense)；／ * *
｝
关键点,release 直到最后一个进程到达时才修改。
例 7.4 假设总线上 20个处理器同时执行一个栅栏，设每个总线事务需 50个时钟周期，忽略 Cache块中锁的读、写实际花费的时间以及栅栏实现中非同步操作的时间，计算 20个处理器全部到达栅栏，被释放及离开栅栏所需的总线事务数。设总线完全公平，整个过程需多长时间?
答 表给出一个处理器通过栅栏产生的事件序列，设第一个获得总线的进程还没有获得锁。
事件 每个处理器时间 20个处理器时间每个处理器获得锁,增量,1525 30500
释放锁的时间执行释放的时间 50 50
每个处理器获得释放标志 50 1000
的时间总和 1625 31550
一个处理器通过栅栏产生的事件序列
7.4.2
希望的同步机制：
1,软件实现旋转锁
◆ 主要问题当多个进程检测并竞争锁时引起的延迟。
◆ 解决办法
(1) 当加锁失败时就人为地推延这些进程的等待时间。
在无竞争的条件下延迟较小
在竞争激烈时串行性小
◆ 具有指数延迟的旋转锁代码
li R3,1 ； R3
lockit,ll R2,0(R1) ； load linked
bnez R2,lockit
addi R2,R2,1
sc R2,0(R1) ； store conditional
bnez R2,gotit
sll R3,R3,1 ；将延迟时间增至 2倍（左移 1位）
pause R3 ；延迟 R3
j lockit
gotit：
(2) 排队锁造成串行化的原因：
(1)读取并修改 count
(2)读取 release
针对 (1)的一种解决方法：
◆ 基本思想：将 count分散成多个变量。
◆ 使用 组合树 ---- k叉树结构。
◆ 每个叶子对应 k个进程
◆ 基本过程：每个 结 点的计数
(1)小于 k:等待解锁
(2)等于 k:将控制权转移至父 结 点
struct node ｛ ／ * *
int counterlock； ／ * *
int count； ／ * *
int parent； ／ * -1 *
struct node tree ［ 0..p-1］； ／ * *
int local_sense； ／ * *
int release； ／ * *
／ * *
barrier(int mynode)
lock(tree[mynode].counterlock)； ／ * *
tree[mynode],count++； ／ * *
unlock(tree[mynode].conterlock)； ／ * *
if(tree[mynode].count==k)｛ ／ * *
if(tree[mynode].parent)>=0｛
barrier(tree[mynode］,parent)；
｝ else｛
release=local_sense；
tree[mynode].count＝ 0； ／ * *
｝ else
spin(release=local_sense)； ／ * *／
／ * *
local_sense= ! local_sense；
barrier (mynode)；
结论：对 count的争用被限制于 k 个进程实际使用时 k=4 时效果较好
2,
◆ 两种硬件同步原语
针对锁
针对栅栏和一些要求进行计数或提供明确索引的用户级操作
◆ 排队锁排队记录等待的进程，当锁释放时送出一
(1) 工作过程
在第一次取锁变量失效时，失效被送入同步控制器。
如果锁空闲，将其交给该处理器；
如果锁忙，控制器产生一个结点请求记录 (比如可以是向量中某一位 )，并将锁忙的标志返回给处理器，
然后该处理器进入旋转等待。
当该锁被释放时，控制器从等待的进程排队中选出一个使用该锁。
例 7.5 如果在排队锁的使用中，失效时进行锁更新，求 20个处理器完成 lock和 unlock所需的时间和总答 每个处理器初始加锁及随后释放锁各产生 1次失效，所以总共需 40个总线事务。 20个初始失效需
1000个时钟周期，接着是每次需要 50个周期的 20次释放，总和为 2050个周期。与通常的基于 Cache一致性的旋转锁相比，性能大大提高。
(2) 关键问题
◆ 需要识别出对锁进行初次访问的进程，从而对其进行排队操作；
◆ 等待进程队列可通过多种机制实现；
◆ 有硬件来回收锁。
(3) Fetch_and_increment原语原子地取值并增量，返回的值可以为增量后的值，也可以为取出的值。
例 7.6 写出采用 fetch_and_increment栅栏的代码。
条件与前面假设相同，并设一次 fetch_and_increment
操作也需 50个时钟周期。计算 20个处理器通过栅栏的答 下面的程序段给出栅栏的代码，这种实现需要进行 20次 fetch_and_increment操作，释放时有 20次
Cache失效，总共需时间 2000个时钟周期,40个总线事务操作。与前面实现的栅栏机制相比，前面所需时间长达 15倍，总线操作多达 10倍。当然，实现组合树栅栏时也可采用 fetch_and_increment来降低树中每个结
local_sense= ! local_sense； ／ * local_sense *／
fetch_and_increment(count)； ／ * *
if(count==total){ ／ * *
count=0； ／ * *
release=local_sense； ／ * *
｝
else { ／ * *
spin(releaze=local_sense)； ／ * *
}
7.5 并行化技术
7.5.1 并行化的基本策略并行程序设计模型是专门为 多处理机,多计算机或 向量／ SIMD计算机而设计的。
并行性的五种模型,
1,共享变量模型
(1) 多处理机程序设计的基础利用共享变量来实现进程间的通信。
这需要使用共享存储器以及访问同一组共享变量的多个进程间的同步特性。
(2) 遇到的主要问题?
临界区的保护性访问
存储器的一致性
存储操作的可分性
快速同步
共享的数据结构
快速数据迁移技术
2,消息传递模型驻留在不同处理机结点上的两个进程可以通过网络传递消息来相互通信。
消息可以是指令、数据、同步信号或中断信号等。
(1) 同步消息传递在时间和空间上必须对发送进程和接收进程实现同步。
(2) 异步消息传递
◆ 通道中常用缓冲区。
◆ 倘若缓冲区足够大或网络通信量不饱和，则消息传递就不会阻塞。
◆ 不管接收者是否准备好，都允许发送者发送消息而不被阻塞。
◆ 关键问题如何把程序代码和数据分布或复制到所有处理结点上。
3,数据并行模型
◆ 数据并行程序要求使用预先分布好的数据集。
◆ 数据并行程序设计强调的是局部计算和数据路由操作。
◆ 数据并行性取决于粒度大小以及所采用的操作方式。
◆ 数据并行通常研究有几千个并发数据操作的高度并行性问题。
4,面向对象模型
◆ 对象把数据和操作封装在一个计算单元中的程序实体。
◆ 对象是动态建立和控制的。
◆ 处理是通过在对象间发送和接收消息来完成的。
5,函数和逻辑模型
(1) 函数程序设计模型强调程序的函数性，程序在执行后不应该产生副作用。
(2) 逻辑程序设计模型以谓词逻辑为基础，适用于涉及大型数据库的知识处理。
7.5.2 并行语言与编译器
1,并行性的语言特征并行程序设计的语言特性：
(1) 优化特性
(2) 可用性包括,? 扩展性
兼容性
可移植性
(3) 同步／通信特性主要包括,?
共享变量 (锁 )的支持
消息传递的发送／接收
远程过程调用
栅栏同步机制和邮 箱
(4) 并行性控制包括以各种形式确定并行性的控制结构。
主要处理：
各种粒度的并行性
显式并行性与隐式并行性
整个程序中的全局并行性
迭代中的循环并行性
任务分割并行性
共享任务队列
共享抽象数据类型
(5) 数据并行性说明访问数据以及把数据分布在多处理计算机上的方法。
主要包括：
◆ 无需用户干预的运行时数据自动分布；
◆ 为用户提供一种能指定通信模式或说明数据和进程映射到硬件上的方法；
◆ 编译器将虚处理机动态或静态地映射到物理处理机上的虚拟处理机支持；
◆ 共享数据可被直接访问而不用管程控制；
◆ SPMD(single program multiple data)程序设计支持。
(6) 进程管理特性用来支持并行进程的高效创建、多线程处理和多任务处理的实现、程序划分和复制以及运行 时的动态负载平衡。
2,并行语言结构
(1) Fortran 90数组表示符多维数组是用一个带下标三元组序列的数组名来表示的，每维一个三元组，不同维的三元组用逗号隔开。
例如
e1,e2,e3
e1,e2
e1,*,e3
e1,*
e1
*
每个 ei一定是能产生一个标量整数值的算术表达式。
(2) 并行流控制
◆ (Doall,Endall)语句对说明并行活动
◆ (Doacross,Endacross)语句说明循环体间相关并行性。
例如,Doacross I=2,N
Do J=2,N
S1:A(I,J)=(A(I(J-1))+A(I,J+1))／ 2
Enddo
Endacross
◆ (Cobegin,Coend)语句对
Cobegin
P1
P2
.
.
.
Coend
◆ Fork和 Join命令在进程 P的执行过程中，可以使用 Fork Q命令来产生一个新的进程 Q：
Process P Process Q
.,
.,
.,
Fork Q
.,
.,
.,
Join Q End
3,并行优化编译器由三个主要部分组成：
流分析
优化
代码生成
(1) 流分析为确定源代码中的数据和控制一致性，将程序流的模式分析出来。
数据相关控制相关重用分析向量化并行化局部性，流水线操作粒度并行度代码调度源代码流分析程序优化并行代码生成分布存储器多计算机，分布数据，计算，
消息传递，…
超标量处理机；
调度,
寄存器分配,
现场切换共享存储器多处理机，划分，同步，负载平衡，…
(2) 程序优化
◆ 目的,尽可能多地挖掘硬件的潜能。
◆ 最终目标,使代码执行速度达到最高。
◆ 要求
代码的长度最短
存储器的访问次数最少
程序并行性得到较好的开发
优化技术包括：
用流水线硬件完成向量化
同时用多台处理机实现并行化
(3) 并行代码生成
◆ 涉及从一种描述到另一种称之为中间形式描述的转换。
◆ 代码生成与所用的指令调度策略是紧密联系在一起的。
