《第7章 多处理机.ppt》由会员分享,可在线阅读,更多相关《第7章 多处理机.ppt(162页珍藏版)》请在三一文库上搜索。
1、7.1 引 言 7.2 对称式共享存储器体系结构 7.3 分布式共享存储器体系结构 7.4 互连网络 7.5 同 步 7.6 同时多线程 7.7 多处理机实例,第章 多处理机,7.1.1 并行计算机体系结构的分类 1. 按照Flynn分类法,可把计算机分成,单指令流单数据流(SISD) 单指令流多数据流(SIMD) 多指令流单数据流(MISD) 多指令流多数据流(MIMD),7.1 引 言,第章 多处理机,2. MIMD已成为通用多处理机体系结构的选择,原因: (1) MIMD具有灵活性; (2) MIMD可以充分利用商品化微处理器在性能价格 比方面的优势。 3. 根据系统中处理器个数的多少,
2、可把现有的MIMD 机器分为两类 (每一类代表了一种存储器的结构和互连策略) (1) 集中式共享存储器结构 动画 这类机器有时被称为 SMP机器(Symmetric shared-memory MultiProcessor) UMA机器(Uniform Memory Access),7.1 引 言,集中共享存储器计算机,(2) 分布式存储器结构 动画 每个结点包含: ,处理器 存储器 IO,在许多情况下,分布式存储器结构优于集中式 共享存储器结构 ,7.1 引 言,分布共享存储器计算机,分布式存储器结构的优点,主要缺点 处理器之间的通信较为复杂,且各处理器之间的 访问延迟较大。 需要高带宽的互
3、连。 簇:超结点,如果大多数的访问是针对本结点的局部存储器, 则可降低对存储器和互连网络的带宽要求; 局部存储器的访问延迟低。,7.1 引 言,7.1.2 通信模型和存储器的结构模型 1. 地址空间的组织方案(两种) (1) 物理上分离的多个存储器作为一个逻辑上共享的 存储空间进行编址。,这类机器的结构被称为 分布式共享存储器结构 (DSM: Distributed Shared-Memory) 可缩放共享存储器结构 (SSM: Scalable Shared-Memory) NUMA机器 (NUMA: Non-Uniform Memory Access),7.1 引 言,(2) 整个地址空间
4、由多个独立的地址空间构成,它 们在逻辑上也是独立的,远程的处理器不能对 其直接寻址。,每一个处理器-存储器模块实际上是一个单独 的计算机,这种机器也称为多计算机。,7.1 引 言,共享地址空间的机器 利用Load和Store指令中的地址隐含地进行 数据通讯。 多个地址空间的机器 通过处理器间显式地传递消息完成。 (消息传递机器),2. 两种通信模型,7.1 引 言,消息传递机器根据简单的网络协议,通过传递消息 来请求某些服务或传输数据,从而完成通信。 例如:一个处理器要对远程存储器上的数据进行访问 或操作: (1) 发送消息,请求传递数据或对数据进行操作; 远程进程调用(RPC, Remote
5、 Process Call) (2) 目的处理器接收到消息以后,执行相应的操 作或代替远程处理器进行访问,并发送一个 应答消息将结果返回。,7.1 引 言,同步消息传递 请求处理器发送一个请求后一直要等到应答 结果才继续运行。 异步消息传递 发送方不先经请求就直接把数据送往数据接 受方。,3.通信机制的性能指标(3个) (1) 通信带宽 理想状态下的通信带宽受限于处理器、存储 器和互连网络的带宽。,7.1 引 言,(2) 通信延迟 理想状态下通信延迟应尽可能地小。 通信延迟发送开销 + 跨越时间 + 传输延迟 + 接收开销 (3) 通讯延迟的隐藏,如何才能较好地将通信和计算或多次通信之 间重叠
6、起来,以实现通讯延迟的隐藏。 通常的原则:只要可能就隐藏延迟。 通信延迟隐藏是一种提高性能的有效途径,但 它对操作系统和编程者来讲增加了额外的负担。,7.1 引 言,4. 不同通信机制的优点 A. 共享存储器通信的主要优点 (1) 与常用的集中式多处理机使用的通信机制兼容。 (2) 易于编程 与传统的编程模式一致 (3) 当通信数据较小时,通信开销较低,带宽利用 较好。 (4) 通过硬件控制的Cache减少了远程通信的频度, 减少了通信延迟以及对共享数据的访问冲突。,7.1 引 言,B. 消息传递通信机制的主要优点 (1) 硬件较简单。 (2) 通信是显式的,从而引起编程者和编译程序的 注意,
7、着重处理开销大的通信。,在共享存储器上支持消息传递相对简单 在消息传递的硬件上支持共享存储器就困难得多。 所有对共享存储器的访问均要求操作系统提供地 址转换和存储保护功能,即将存储器访问转换为消 息的发送和接收。,7.1 引 言,7.1.3 并行处理面临的挑战 并行处理面临着两个重要的挑战: 。,程序中有限的并行性 相对较高的通信开销,系统加速比 =,7.1 引 言,例7.1 如果想用100个处理器达到80的加速比, 求原计算程序中串行部分所占比例。 解 动画演示,2. 第二个挑战:多处理机中远程访问的延迟较大 在现有的机器中,处理器之间的数据通信 大约需要5010000个时钟周期。,1. 第
8、一个挑战:有限的并行性 使机器要达到好的加速比十分困难,7.1 引 言,远程访问一个字的延迟时间,例 一台32个处理器的计算机,对远程存储 器访问时间为2000ns。除了通信以外,假设计算中的 访问均命中局部存储器。当发出一个远程请求时,本 处理器挂起。处理器时钟时间为10ns,如果指令基本 的CPI为1.0(设所有访存均命中Cache),求在没有远程 访问的状态下与有0.5%的指令需要远程访问的状态下, 前者比后者快多少? 解 有0.5%远程访问的机器的实际CPI为 CPI基本CPI远程访问率远程访问开销 1.00.5%远程访问开销,7.1 引 言,远程访问开销远程访问时间/时钟时间 200
9、0ns/10ns200个时钟 CPI1.00.5%2002.0 它为只有局部访问的机器的2.01.02倍, 因此在没有远程访问的状态下的机器速度是有0.5% 远程访问的机器速度的2倍。,问题的解决 并行性不足: 采用并行性更好的算法 远程访问延迟的降低:靠体系结构支持和编程技术,7.1 引 言,3. 并行程序的计算通信比率,反映并行程序性能的一个重要的度量 计算与通信的比率 计算通信比率随着处理数据规模的增大而增 加;随着处理器数目的增加而降低。,7.1 引 言,7.2 对称式共享存储器体系结构,多个处理器共享一个存储器。 当处理器规模较小时,这种机器十分经济。 支持对共享数据和私有数据的Ca
10、che缓存 私有数据供一个单独的处理器使用,而共 享数据供多个处理器使用。 共享数据进入Cache产生了一个新的问题 Cache的一致性问题,第七章 多处理机,(1) 不一致产生的原因(Cache一致性问题),IO操作 Cache中的内容可能与由IO子系统输入输 出形成的存储器对应部分的内容不同。 共享数据 不同处理器的Cache都保存有对应存储器单元 的内容。,例 两个处理器的读写,7.2.1 多处理机Cache一致性,7.2 对称式共享存储器体系结构,(2) 存储器的一致性(非正式定义) 如果对某个数据项的任何读操作均可得到其最 新写入的值,则认为这个存储系统是一致的。,What: 返回给
11、读操作的是什么值 When: 什么时候才能将已写入的值返回给读操作,需要满足以下满足条件 处理器P对X进行一次写之后又对X进行读, 读和写之间没有其它处理器对X进行写,则 读的返回值总是写进的值。,存储系统行为的两个不同方面,7.2 对称式共享存储器体系结构, 一个处理器对X进行写之后,另一处理器对X进行 读,读和写之间无其它写,则读X的返回值应为写 进的值。 对同一单元的写是顺序化的,即任意两个处理器 对同一单元的两次写,从所有处理器看来顺序都应 是相同的。 假设 直到所有的处理器均看到了写的结果,一次写操 作才算完成;允许处理器无序读,但必须以程序规定 的顺序进行写。,7.2 对称式共享存
12、储器体系结构,在一致的多处理机中,Cache提供两种功能:,共享数据的迁移 降低了对远程共享数据的访问延迟。 共享数据的复制 不仅降低了访存的延迟,也减少了访问共 享数据所产生的冲突。,小规模多处理机不是采用软件而是采用硬件技术 实现Cache一致性。,7.2.2 实现一致性的基本方案,7.2 对称式共享存储器体系结构,(1) Cache一致性协议 对多个处理器维护一致性的协议。 (2) 关键:跟踪记录共享数据块的状态 (3) 共享数据状态跟踪记录技术,目录 物理存储器中共享数据块的状态及相关信息 均被保存在一个称为目录的地方。 监听(snooping) 每个Cache除了包含物理存储器中块的
13、数据拷 贝之外,也保存着各个块的共享状态信息。,7.2 对称式共享存储器体系结构,Cache通常连在共享存储器的总线上,各个Cache 控制器通过监听总线来判断它们是否有总线上请求的 数据块。,两种更新协议 (1) 写作废协议 在一个处理器写某个数据项之前保证它对该 数据项有唯一的访问权。 例 : 在写回Cache的条件下,监听总线中写作废协议的实现。,7.2 对称式共享存储器体系结构,(2) 写更新协议 当一个处理器写某数据项时,通过广播使其它 Cache中所有对应的该数据项拷贝进行更新。 例 在写回Cache的条件下,监听总线中写更新协议的实现。,(3) 写更新和写作废协议性能上的差别主要
14、来自:,对同一数据的多个写而中间无读操作的情况, 写更新协议需进行多次写广播操作,而在写 作废协议下只需一次作废操作。 对同一块中多个字进行写,写更新协议对每 个字的写均要进行一次广播,而在写作废协 议下仅在对本块第一次写时进行作废操作。 从一个处理器写到另一个处理器读之间的延 迟通常在写更新模式中较低。而在写作废协 议中,需要读一个新的拷贝。,7.2 对称式共享存储器体系结构,大多数多处理机系统都采用写作废协议,7.2 对称式共享存储器体系结构,7.2.3 监听协议及其实现,基本实现技术,小规模多处理机中实现写作废协议的关键 利用总线进行作废操作:把要作废的地址放到总线上(一个放,多个读)
15、写顺序化:由总线实现 写直达Cache:因为所有写的数据同时被写回主存,则从主存中总可以取到最新的数据值。 对于写回Cache,得到数据的最新值会困难一些,因为最新值可能在某个Cache中,也可能在主存中。,7.2 对称式共享存储器体系结构,增加Cache中块的标志位 状态: 无效(invalid) 无副本 共享(shared) 至少一个副本,clean 独占(exclusive) 唯一副本,dirty Cache块的拥有者:拥有唯一的Cache块副本 的处理器。 因为每次总线任务均要检查Cache的地址位,这 可能与CPU对Cache的访问冲突。可通过下列两种 技术之一降低冲突: 复制标志位
16、 采用多级包容Cache (许多系统采用),7.2 对称式共享存储器体系结构,监听协议举例,为简单起见,对于对共享块的 Write hit 和 Write miss 不加区分,都按 Write miss 处理,写作废,写回法,7.2 对称式共享存储器体系结构,存储器分布于各结点中,所有的结点通过网络互 连。访问可以是本地的,也可是远程的。 可以不支持Cache一致性:规定共享数据不进入Cache, 仅私有数据才能保存在Cache中。 优点: 所需的硬件支持很少 (因为远程访问存取量仅是一个字(或双字)而 不是一个Cache块),7.3 分布式共享存储器体系结构,第章 多处理机,缺点: (1)
17、实现透明的软件Cache一致性的编译机制能力 有限。 (2) 没有Cache一致性,机器就不能利用取出同一 块中的多个字的开销接近于取一个字的开销 这个优点,这是因为共享数据是以Cache块为 单位进行管理的。当每次访问要从远程存储 器取一个字时,不能有效利用共享数据的空 间局部性。 (3) 诸如预取等延迟隐藏技术对于多个字的存取 更为有效,比如针对一个Cache块的预取。,7.3 分布式共享存储器体系结构,解决Cache一致性问题的关键: 寻找替代监听协议的一致性协议。,目录协议 在每个结点增加目录存储器,用于存放目录 对每个结点增加目录表后的分布式存储器的系统结构,7.3 分布式共享存储器
18、体系结构, 目录协议必须实现两种基本操作,处理读失效 处理对共享、干净块的写 对共享块写失效的处理是这两个操作的简单组合,(2) 目录必须跟踪记录每个存储块的状态 存储块的状态有三种:,7.3.1 基于目录的Cache一致性及其实现,7.3 分布式共享存储器体系结构,共享 在一个或多个处理器上具有这个块的副本, 且主存中的值是最新值(所有Cache均相同)。 未缓冲 所有处理器的Cache都没有该块的拷贝。 专有 仅有一个处理器上有该块的副本,且已对该块 进行了写操作,而主存的拷贝仍是旧的。这个处理器 称为该块的拥有者。,7.3 分布式共享存储器体系结构,(3) 由于写作废操作的需要,还必须记
19、录哪些处理器 有该块的拷贝 方法:对每个主存块设置一个位向量 当该块被共享时,每个位指出与之对应的处 理器是否有该块的拷贝。 当该块为专有时,可根据位向量来寻找其拥 有者。,7.3 分布式共享存储器体系结构,结点之间发送的消息 及其作用,7.3 分布式共享存储器体系结构,目录状态转换图,对基于目录的Cache一致性的多种改进,有限映射目录 链式结构目录,基于目录的Cache一致性协议是完全由硬件实现的。 此外,还可以用软硬结合的办法实现。,7.3 分布式共享存储器体系结构,7.4 互连网络,互连网络是将集中式系统或分布式系统中的结点连 接起来所构成的网络。 在拓扑上,互连网络为输入和输出两组结
20、点之间提 供一组互连或映象。 本节介绍:构造多处理机的互连网络,第章 多处理机,7.4.1 互连网络的性能参数 1. 互连网络的拓扑结构 (1) 静态网络 由点和点直接相连而成,这种连接方式在 程序执行过程中不会改变。 (2) 动态网络 用开关通道实现,可动态地改变结构, 使其与用户程序中通信要求匹配。,7.4 互连网络,2. 性能参数 (1) 网络规模:结点数 (2) 结点度:与结点相连接的边的数目。 入度:进入结点的通道数 出度:从结点出来的通道数 (3) 网络直径 网络中任意两个结点间最短路径长度的最大值。 (4) 等分宽度 在将某一网络切成相等两半的各种切法中, 沿切口的最小通道边数。
21、,7.4 互连网络,对称网络 从其中的任何一个结点看,拓扑结构都是一样的。 (5) 路由 在网络通信中对路径的选择与指定。,3. 互连函数 如果把互连网络的N个入端和N个出端各自用 整数0,1,N-1代表,则互连函数表示互连的 出端号和入端号的一一对应关系。,7.4 互连网络,4. 几种数据路由功能 (1) 循环 若把互连函数f(x)表示为: (x0,x1,x2,xj) 则代表对应关系为: f(x0)=x1,f(x1)=x2,f(xj)=x0 j+1称为该循环的周期。 (2) 置换 指对象的重新排序。对于n个对象来说, 有n!种置换。,7.4 互连网络,例如 置换=(a,b,c)(d,e)表示
22、了置换映射: 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,x1,x0,xk-1) (将x循环左移1位),7.4 互连网络,(4) 超立方体路由功能 例 一个三维二进制立方体网络,7.4 互连网络,根据最低位C0路由 根据中间位C1路由 根据最高位C2路由,一个n维超立方体共有n种路由功能
23、,分别由n位地 址中的每一位求反位值来确定。将x=(xk-1,x1,x0)映 射到f(x),得到f(x)=( xk-1, , xk,x1,x0)。,有三种路由功能: 分别根据结点的二进制地址(C2 C1 C0)中的某一位来确定,7.4 互连网络,(5) 广播和选播,广播 一对全体的映射。 选播 一个子集到另一子集(多对多)的映射。,5. 影响互连网络性能的因素 (1) 功能特性 网络如何支持路由、中断处理、同步、请 求消息组合和一致性。,7.4 互连网络,(2) 网络时延 单位消息通过网络传送时最坏情况下的时间延迟。 (3) 带宽 通过网络的最大数据传输率,用MBs表示。 (4) 硬件复杂性
24、诸如导线、开关、连接器、仲裁和接口逻辑等 的造价。 (5) 可扩展性 在增加机器资源使性能可扩展的情况下,网络 具备模块化可扩展的能力。,7.4 互连网络,7.4.2 静态连接网络 1. 线性阵列 一种一维的线性网络,其中N个结点用N-1个链 路连成一行。,内部结点度:2 端结点度:1 直径:N-1 等分宽度b=1,7.4 互连网络,2. 环和带弦环 (1) 环 用一条附加链路将线性阵列的两个端点连接起 来而构成的。可以单向工作,也可以双向工作。,结点度:2 双向环的直径:N2 单向环的直径:N,7.4 互连网络,(2) 带弦环 增加的链路愈多,结点度愈高,网络直径就愈小。,7.4 互连网络,
25、全连接网络,结点度: N-1 直径最短,为1,7.4 互连网络,3. 循环移数网络 通过在环上每个结点到所有与其距离为2的整 数幂的结点之间都增加一条附加链而构成的。,结点数: 16 结点度: 7 直径: 2,7.4 互连网络,如果j-i=2 r,r=0,1,2,n-1,网络规模 N=2n,则结点i与结点j连接。这种循环移数网络的结 点度为d=2n-1,直径D=n2。,7.4 互连网络,4. 树形和星形 (1) 一棵5层31个结点的二叉树 一般说来,一棵k层完全平衡的二叉树有 N=2k-1个结点。 最大结点度是3,直径是2(k-1)。 (2) 星形,一种2层树 结点度较高,为d=N-1 直径较
26、小,是一常数2,7.4 互连网络,7.4 互连网络,5. 胖树形,7.4 互连网络,6. 网格形和环网形 (1) 一个33网格形网络 一般说来,N=nk 个结点的k维网络的内 部结点度为2k ,网络直径为k(n-1)。边结 点和角结点的结点度分别为3或2。 (2) 环形网,可看做是直径更短的另一种网格 环形网沿阵列每行和每列都有环形连接 一个nn二元环网,结点度为4 直径为2*n/2,7.4 互连网络,7.4 互连网络,7. 超立方体,一种二元n-立方体结构 一般说来,一个n-立方体由N=2n 个结点组成, 它们分布在n维上,每维有两个结点。 例 8个结点的3-立方体 4-立方体 一个n-立方
27、体的结点度等于n,也就是网络的 直径。,7.4 互连网络,7.4 互连网络,8. k元n-立方体网络 环形、网络形、环网形、二元n-立方体(超立方 体)等网络都是k元n-立方体网络系统的拓扑同构体。 参数n: 立方体的维数 k: 基数或者说是沿每个方向的结点数(多重性)。 N=kn, (n=logkN) K元n-立方体的结点可用基数为k的n位地址 A=a0a1a2an-1来表示,其中ai代表第i维结点的位置。 按照惯例,低维k元n-立方体称为环网,而高维二 元n-立方体则称为超立方体。,7.4 互连网络,例 一种4元3-立方体网络,7.4 互连网络,7.4.3 动态连接网络 1. 动态互连网络
28、的三个主要操作特征,定时 开关 控制,2. 根据级间连结方式,动态互连网络分为 (1) 单级网络 也称循环网络 (2) 多级网络 由一级以上的开关元件构成。 这类网络可以把任一输入与任一输出相连。,7.4 互连网络,阻塞网络 如果同时连接多个输入输出对时,可能会引 起开关和通信链路使用上的冲突。 大多数多级网络都是阻塞网络。 非阻塞网络 如果多级网络通过重新安排连接方式可以 建立所有可能的输入输出之间的连接。,7.4 互连网络,总线仲裁 中断处理 一致性协议 总线事务的处理,3. 几类主要的开关网络 (1) 总线系统,优点:价格较低 带宽较窄 缺点:容易产生故障 总线研制中的重要问题,7.4
29、互连网络,一种总线连接的多处理机系统,(2) 交叉开关网络 单级无阻塞置换网络,每个交叉点是一个可以打开或关闭的开关, 提供源(处理器)和目的(存储器)之间点对点 的连接通路。 交叉点开关网络中n对处理器可以同时传送 数据。 交叉开关网络的带宽和互连特性最好。 一种交叉开关网络,7.4 互连网络,7.4 互连网络,(3) 多端口存储器 主要思想 将所有交叉点仲裁逻辑和跟每个存储器模 块有关的开关功能移到存储器控制器中。 多端口存储器结构是一个折衷方案,它介于低 成本低性能的总线系统和高成本高带宽的交叉 开关系统之间。 缺点,十分昂贵 不能扩展 当系统配置很大时,需要大量的互连电缆和连接器。,7
30、.4 互连网络,用于多处理机系统的多端口存储器结构,(4) 多级网络 多级网络可用于构造大型多处理机系统。 一种通用多级网络 各种多级网络的区别就在于所用开关模 块和级间连接模式的不同。,7.4 互连网络,由ab开关模块和级间构成的通用多级互连网络结构,22开关四种可能的连接方式, Omega网络,7.4 互连网络,一个1616 Omega网络,7.5 同 步 通常是使用硬件提供的有关同步指令,通过用户级软件例程建立的。 7.5.1 基本硬件原语 在多处理器同步中,主要功能是一组能自动读出后并进行写存储单元的硬件原语。它们能够自动读修改单元。通常情况下,用户不直接使用基本的硬件原语,原语主要供
31、系统程序员用来编制同步库函数。,第章 多处理机,功能:将一个存储单元的值和一个寄存器的值 进行交换。建立一个锁,锁值为“0”表示开锁, 为“1”表示上锁。 处理器加锁时,将对应于该锁的存储单元的值 交换为某个寄存器的值“1”。如果返回值为“0”, 存储单元的值此时已置换为“1”,防止了别的进 程竞争该锁。 实现同步的关键: 操作的原子性,1. 典型操作:原子交换(atomic exchange),7.5 同 步,2. 测试并置定(test_and_set) 先测试一个值,如果符合条件则修改其值。 3. 读取并加1(fetch_and_increment) 它返回存储单元的值并自动增加该值。 4
32、. 使用指令对,LL(load linked或load locked)的取指令 SC(store conditional)的特殊存指令,7.5 同 步,例 实现对由R1指出的存储单元进行原子交换操作 try:mov R3,R4 ;送交换值 ll R2,0(R1) ;load linked sc R3,0(R1) ;store conditional beqz R3,try ;存失败转移 mov R4,R2 ;将取的值送往R4 最终R4和由R1指向的单元值进行原子交换,在ll和sc之间如有别的处理器插入并修改了存储单元的值,sc将返回“0”并存入R3中,从而使指令序列再重新循环。,7.5 同 步
33、,llsc机制的一个优点:可用来构造别的同步原语 例如:原子的fetch-and-increment try: ll R2,0(R1) ;load linked addi R2,R2,1 ;增加 sc R2,0(R1) ;store conditional beqz R2,try ;存失败转移 指令对的实现必须跟踪地址 由ll指令指定一个寄存器,该寄存器存放着一个 单元地址,这个寄存器常称为连接寄存器。,7.5 同 步,7.5.2 用一致性实现锁,采用多处理机的一致性机制来实现旋转锁。 旋转锁 处理器环绕一个锁不停地旋转而请求获得该锁。,1. 无Cache一致性机制 在存储器中保存锁变量,处理
34、器可以不断地通 过一个原子操作请求加锁,比如先交换,再测试返 回值从而知道锁的状况。释放锁的时候,处理器可 简单地将锁置为“0” 。,7.5 同 步,li R2,1 lockit: exch R2,0(R1) ;原子交换 bnez R2,lockit ;是否已加锁?,2. 机器支持Cache一致性 将锁缓冲进入Cache,并通过一致性机制使锁值保 持一致。,7.5 同 步,优点,可使“环绕”的进程对本地Cache块进行操作; 可利用锁访问的局部性,即处理器最近使用过 的锁不久又会使用。,改进旋转锁(获得第一条好处) 使其环绕过程仅对本地Cache中锁的拷贝进行读, 直到它返回“0”确认锁可用,
35、然后再进行加锁交换操 作。使用锁完毕后新竞争又开始进行。,7.5 同 步,lockit:lw R2,0(R1) ;取锁值 bnez R2,lockit ;锁不可用 li R2,1 ;存入锁值 exch R2,0(R1) ;交换 bnez R2,lockit ;如锁不为0转移 上面给出了对于三个处理器竞争锁的操作。一旦处理器存入“0”释放锁,所有别的Cache对应块均被作废,必须取新的值来更新它们锁的拷贝。 一个处理器Cache会先获得未加锁值并执行交换操作,当别的Cache失效处理完后,它们会发现已被加锁,所以又必须不停地测试环绕。,7.5 同 步,表7.5 三个处理机对锁的使用,7.5 同
36、步,llsc原语的另一个状态:读写操作明显分开。 Ll不产生总线数据传送,这使下面代码与使用经 过优化交换的代码具有相同的特点: lockit: ll R2,0(R1) ;load-linked bnez R2,lockit ;锁无效 li R2,,1 ;加锁值 sc R2,0(R1) ;存 beqz R2,lockit ;如存失败转移 第一个分支形成环绕的循环体,第二个分支解决了两个同时请求锁的处理器竞争问题。尽管旋转锁机制简单并且具有强制性,但难以将它扩展到处理器数量很多的情况。,7.5 同 步,7.5.3 同步性能问题 简单旋转锁不能很好地适应可伸缩性。大规模机器 中所有的处理器会产生出
37、大量的竞争问题。 例7.3:设总线上有10个处理器同时准备对同一变量加锁。假设每个总线事务处理(读失效或写失效)是100个时钟周期,忽略实际的Cache块锁的读写时间以及加锁的时间,求10个处理器请求加锁所需的总线事务数目。设时间为0时锁已释放并且所有处理器在旋转,求处理这10个请求时间为多长?假设总线在新的请求到达之前已服务完挂起的所有请求,并且处理器速度相同。,7.5 同 步,解 当i个处理器竞争锁的时候,他们完成下列操作序列,每一个操作产生一个总线事务: 访问该锁的i个LL指令操作; 试图锁住该锁的i个SC指令操作; 1个释放锁的存操作指令。 因此对n个处理器,总线事务的总和为: n (
38、2i+1)=n(n+1)+n=n2+2n i=1 对于10个处理器有120个总线事务,需要12000个时钟周期。,7.5 同 步, 本例中问题的根源是锁的竞争、存储器中锁访问的串行性以及总线访问的延迟。 旋转锁的主要优点: 对于总线或网络开销较低,7.5 同 步,并行循环的程序中另一个常用的同步操作: 栅栏 栅栏强制所有到达的进程进行等待,直到全部的 进程到达栅栏,然后释放全部的进程,从而形成同步。,栅栏的典型实现 用两个旋转锁 (1) 用来记录到达栅栏的进程数 (2) 用来封锁进程直至最后一个进程到达栅栏 栅栏的实现要不停地探测指定的变量, 直到它满足规定的条件。 一种典型的实现,其中loc
39、k和unlock提供基本的 旋转锁,total是要到达栅栏的进程总数。,7.5 同 步,Lock(counterlock); *确保更新的原子性* if(count=0) release=0; *第一个进程则重置release* count=count+1; *到达进程记数* unlock(counterlock); *释放锁* if(count=total) *进程全部到达* count=0; *重置计数器* release=1; *释放进程* else *还有进程未到达* spin(release=1); *等待别的进程到达* ,7.5 同 步,对counterlock加锁保证增量操作的原
40、子性,变 量 count记录着已到达栅栏的进程数,变量 release用来封锁进程直到最后一个进程到达栅栏。 实际情况中会出现的问题 可能反复使用一个栅栏,栅栏释放的进程运行 一段后又会再次返回栅栏,这样有可能出现某个进 程永远离不开栅栏的状况(它停在旋转操作上)。,7.5 同 步,例如:OS调度进程,可能一个进程速度较快,当它第二次到达栅栏时,第一次的进程还挂在栅栏中未能离开。这样所有的进程在这个栅栏的第二次使用中都处于无限等待状态,因为进程的数目永达不到total。,7.5 同 步,一种解决方法 当进程离开栅栏时进行计数,在上次栅栏使用中 的所有进程离开之前不允许任何进程重用并初始化本 栅
41、栏。 另一种解决办法 sense_reversing栅栏,每个进程均使用一个私 有变量local_sense,初始化为1。,7.5 同 步,Local_sense=! Local_sense; *local-sense取反* lock(counterlock); *确保增加的原子性* count+; *记算到达进程数* unlock(counterlock); *解锁* if(count=total) *进程全部到达* count=0; *重置计数器* release=local_sense; *释放进程* else *还有进程未到达* spin(release=local_sense); *
42、等待信号* ,7.5 同 步,例7.4 假设总线上10个处理器同时执行一个栅栏,设每个总线事务需100个时钟周期,忽略Cache块中锁的读、写实际花费的时间,以及栅栏实现中非同步操作的时间,计算10个处理器全部到达栅栏,被释放及离开栅栏所需的总线事务数。设总线完全公平,整个过程需多长时间? 答:下表给出一个处理器通过栅栏发出的事件序列,设第一个获得总线的进程并未拥有锁。 ,7.5 同 步,表7.6 第i个处理器通过栅栏产生的事件序列 事件 数量 对应源代码 说明 LL i Lock(counterlock); 所有处理器抢锁 SC i Lock(counterlock); 所有处理器抢锁 LD
43、 1 count=count+1; 一个成功 LL i-1 Lock(counterlock); 不成功的处理器再次抢锁 SD 1 count=count+1; 获得专有访问产生的失效 SD 1 unlock(counterlock); 获得锁产生的失效 LD 2 spin(release=local_sense);读释放:初次和最后写产 生的失效,7.5 同 步,当竞争不激烈且同步操作较少时,我们主要关心的 是一个同步原语操作的延迟。 基本的旋转锁操作可在两个总线周期内完成: 一个读锁,一个写锁。我们可用多种方法改进形成 在一个单周期内完成操作。 同步操作最严重的问题:进程的串行性 当出现竞
44、争时,就会出现串行性问题。它极大 地增加了同步操作的时间。 总线的使用是这个问题关键所在。 在基于目录的Cache一致性机器中,串行性问题也 同样严重。,7.5 同 步,7.5.4 大规模机器的同步 所希望的同步机制:在无竞争的条件下延迟较小 在竞争激烈时串行性小 1. 软件实现 旋转锁 (1) 旋转锁实现的主要问题 当多个进程检测并竞争锁时引起的延迟 (2) 一种解决办法: 当加锁失败时就人为地推延 这些进程的等待时间。 (3) 具有指数延迟的旋转锁代码,7.5 同 步,li R3,1 ;R3初始延迟值; lockit: ll R2,0(R1) ;load linked bnez R2,lo
45、ckit ;无效 addi R2,R2,1 ;取到加锁值 sc R2,0(R1) ;store conditional bnez R2,gotit ;存成功转移 sll R3,R3,1 ;将延迟时间增至2倍 pause R3 ;延迟R3中时间值 j lockit gotit: 使用加锁保护的数据 当sc失败时,进程推延R3个时间单位。,7.5 同 步,先讨论采用数组进行的软件实现。为此我们给出一种更好的栅栏实现代码。 前面栅栏机制实现中,所有的进程必须读取 release标志,形成冲突。 通过组合树来减小冲突 组合树是多个请求在局部结合起来形成树的一 种分级结构。 降低冲突的原因:将大冲突化解
46、成为并行的多 个小冲突。,锁实现的另一种技术是排队锁,7.5 同 步,组合树采用预定义的n叉树结构 用变量k表示扇入数目,实际中k=4效果较 好。当k个进程都到达树的某个结点时,则发 信号进入树的上一层。 当全部进程到达的信号汇集在根结点时,释放 所有的进程。 采用sense_reversing技术来给出下面的基于 组合树的栅栏代码。,7.5 同 步,struct node *组合树中一个结点* int counterlock;int count ;int parent; struct node tree 0p-1; *树中各结点* int local_sense;int release; b
47、arrier(int mynode) lock(treemynode.counterlock);*保护计数器* count+; *计数的累加* unlock(treemynode.conterlock);*解锁* if(treemynode.count=k) *本结点全部到达* if(treemynode.parent)=0 barrier(treemynode.parent); elserelease=local_sense; treemynode.count0; *为下次重用初始化* else spin(release=local_sense); local_sense= ! local_sense;barrier (mynode);,7.5 同 步,2. 硬件原语支持 介绍两种硬件同步原语:,(1) 排队锁 可以排队记录等待的进程,当锁释放时送 出一个已确定的等待进程。,第一个针对锁 第二个针对栅栏和要求进行计数或提供明确索 引的某些用户级操作,7.5 同 步,硬件实现,在基于目录的机器上,通过硬件向量等方式 来进行排队和同步控制。 在基于总线的机器中要
链接地址:https://www.31doc.com/p-3030108.html