【文档说明】计算机系统结构—多处理机课件.pptx，共(75)页，295.362 KB，由小橙橙上传

转载请保留链接：https://www.ichengzhen.cn/view-76837.html

以下为本文档部分文字说明：

计算机系统结构—多处理机课件提示本章内容2之2因为多处理机系统结构是一个巨大而多样的领域，其中很多领域仍处于不成熟的阶段，所以本课程集中于多处理机设计的主流进行讨论：由少量到中等数量的处理机（≤128）组成的机器。多处理机结构本章内容根据存储器的组织形式，多处理机有两种基本结构：

集中式共享存储器结构分布式共享存储器结构集中式共享存储器结构多处理机本章内容>>多处理机结构存储器是一个独立的子系统，通过互连网络（交叉开关/总线）为所有的处理机共享，任何两台处理机都可以通过访问共享的存储器单元实现通信。由于共享存储器对每个处理机都是对称关系，而且所有处理机对共享存储器的访

问时间都相同，这种结构的多处理机也称为对称多处理机（SMP）和均匀存储器存取（UMA）。2之1图示本章内容>>多处理机结构2之2处理机1级/多级Cache存储器处理机1级/多级Cache处理机1级/多级Cache处理机1级/多级Cac

heI/O系统分布式共享存储器结构(DSM)多处理机本章内容>>多处理机结构存储器分布在各处理机中，但这些存储器在逻辑上统一编址，形成一个为所有处理机共享的虚拟共享存储器。处理机之间信息交换的物理实现仍然

是通过点-点的通信。由于任何一个处理机访问本地存储器都较快，但是访问分布在其他处理机的远程存储器则较慢，这种结构的多处理机也称为非均匀存储器存取（NUMA）。3之1图示本章内容>>多处理机结构3之2处理机+Cache存储器互连网络I/O处理机+Cache

存储器I/O处理机+Cache存储器I/O处理机+Cache存储器I/O处理机+Cache存储器I/O处理机+Cache存储器I/O比较本章内容>>多处理机结构3之3集中共享分布共享处理机数≤30≤1000限制结点间间距和延迟数据局部性一致性问题本章内容•Cache一致性•

存储一致性Cache一致性本章内容>>一致性问题•问题现象•原因分析•解决方法问题现象本章内容>>一致性问题>>Cache一致性Cache一致性是指私有Cache中共享数据的副本和共享存储器中共享数据之间的一致性。②③u:7④u:?P1Cu:5主存CC①P2P3特征多处理器对相同存储单元的

操作引起的一致性。u:5u:5u:7原因分析本章内容>>一致性问题>>Cache一致性•共享可写数据引起的不一致性•进程迁移引起的数据不一致性•I/O传输造成的数据不一致性共享可写数据引起的不一致性不同处理器对相同单元在各自Cache的拷贝的异步写操作。本章内容>>一致性问题>>Cac

he一致性>>原因分析P1XXP2X处理机Cache共享存储器更新之前P1X’XP2X’更新之后（写通过）P1XXP2X’更新之后（写回）进程迁移引起的数据不一致性本章内容>>一致性问题>>Cache一致性>>原因分析多处理器中的进程迁移，而又不互相通报。P1XXP2X处理机

Cache共享存储器初始状态P1X’XP2X’迁移之前（写通过）进程P1X’XP2X’迁移之后（写通过）进程进程I/O传输造成的数据不一致性本章内容>>一致性问题>>Cache一致性>>原因分析绕过Cache拷贝拥有者的I/O操作。P1XX处理机Cache共享存储器I/O前P

2XI/OP1X’XI/O后X’P2XP1XX’I/O后（写回）XP2X共享存储器输入共享存储器输出解决方法前两种原因•监听法•目录法第三种原因•禁止法•刷新法本章内容>>一致性问题>>Cache一致性监听协议•基本原理•具体实现–采用写通过策略的Cache–采用写回策略的Cache–写一次（Wr

ite-Once）协议本章内容>>一致性问题>>Cache一致性>>解决方法基本原理本章内容>>一致性问题>>Cache一致性>>解决方法>>监听协议4之1本方法只适用于采用基于总线互连结构的系统中，由于系统中每个

处理机都能觉察到存储器系统正在进行的活动，在某个活动破坏了Cache的一致性时，Cache控制器将采取相应的动作使有关的拷贝无效或更新。写无效/写更新本章内容>>一致性问题>>Cache一致性>>解决方法>>监听协议4之2使用监听协议来保持Cache一致性有两种方法：方法

一：写无效（WriteInvalidate）策略在本地Cache的数据块修改时使远程数据块都无效。方法二：写更新（WriteUpdate）策略在本地Cache数据块修改时通过总线把新的数据块广播给含该块的所有其他Cache。提示：采用写无效或写更新策略与Cache采用写回还是写通过方式无关。图示

本章内容>>一致性问题>>Cache一致性>>解决方法>>监听协议4之3P1XXP2X处理机Cache共享存储器更新之前P1X’IP2X’更新之后(Write-Invalidate)P1X’X’P2X’更新之后(Write-Update)应用情况本章内容>>一致性问题>>Ca

che一致性>>解决方法>>监听协议4之4由于写更新法在本地Cache修改时需要通过总线把修改过的数据块的内容广播给所有含该数据块的其他Cache，增加了总线的负担，所以在一般的应用系统中，极少使用写更新法。本

方法实现简单，但只适用于总线式互连的多处理机，而且写无效法和写更新法都要占用总线不少时间，因此只能用于机数少的多处理机中。采用写通过策略的Cache本章内容>>一致性问题>>Cache一致性>>解决方法>>监听协议Cache数据块有两种状态:有效和无效，有效状态表示该数据

块内容正确，无效状态表示该数据块内容已“过时”或不在Cache中。RL、WL表示本地处理机对Cache的读和写操作，RR、WR表示远程处理机对Cache中相同内容数据的读和写操作。RL,WLRL,WLRR,WRRR有效无效WR采用写回策略的Cache本

章内容>>一致性问题>>Cache一致性>>解决方法>>监听协议2之1WLRL,WLRL,RR读写只读RRWLWRWRRL无效RR,WR采用写回方式的Cache状态图采用写回策略的CacheCache数据块有三种状态:只读

、读写和无效。只读状态表示整个系统中有多个数据块拷贝是正确的；读写状态表示数据块至少被修改过一次，存储器中相应数据块还没有修改，在整个系统中只有一个数据块拷贝是正确的；无效状态表示该数据块内容已“过时”或不在Cac

he中。RL、WL表示本地处理机对Cache的读和写操作，RR、WR表示远程处理机对Cache中相同内容数据的读和写操作。本章内容>>一致性问题>>Cache一致性>>解决方法>>监听协议2之2写一次协议本章内容>>一致性问题>>Cache一致性>>解决方法>>监听

协议4之1本方法为了降低总线流量，结合了写回和写通过策略的优点。在第一次写Cache采用写通过策略，以后写Cache采用写回策略，此时整个系统中只有一份正确的拷贝。写一次协议本章内容>>一致性问题>>Cache一致性>>解决方法>>监听协议4之2RLR

L,RRRR,WR有效无效WRWLRRWLWRWRRL保留重写RL,WLWLRR写一次协议本章内容>>一致性问题>>Cache一致性>>解决方法>>监听协议4之3Cache数据块有四种状态:有效、保留、重写和无效。有效状态表示整个系统中有多个数据块拷贝是正

确的；保留状态表示数据从存储器读入Cache后只被写过一次，Cache和存储器中拷贝都正确；重写状态表示Cache中的数据块被写过多次，而且是唯一正确的数据块；无效状态表示该数据块内容已“过时”或不在Cache中。RL、WL表示本地处理机对Cache的读和写操作，

RR、WR表示远程处理机对Cache中相同内容数据的读和写操作。写一次协议本章内容>>一致性问题>>Cache一致性>>解决方法>>监听协议4之4•主要优点：减少大量的无效操作，提高了总线效率。•主要缺点：当主存储器的内容无效时,读缺失引起的总线读操作必须禁止主存储器的操作（以免造成总线冲突），而

大多数总线不支持这种操作。IEEEFuturebus+总线支持该操作。目录协议•基本原理•具体实现–全映射目录协议–有限目录协议–链式目录协议本章内容>>一致性问题>>Cache一致性>>解决方法基本原理本

章内容>>一致性问题>>Cache一致性>>解决方法>>目录协议监听协议涉及大量广播通信及收集状态信息的任务，即使是总线型网络也会使总线流量大大增加。如果使无效信息只发给有关的数据块，可以避免广播，这需要有一套管理数据块的结构，这就是Cach

e一致性目录协议方案。3之1基本原理•建立目录表为Cache在共享存储器建立一个目录表，用于保存每个数据块的状态：包括用几个标志位分别指示这个信息块的副本在其他几个处理机的Cache中是否有，另外再设置一个标志位（重写位）用以指明是否有一个Cache允许将有关数据写入。本章内容

>>一致性问题>>Cache一致性>>解决方法>>目录协议3之2目录协议用在实现广播功能比较困难的网络。主要思想为：基本原理•使用目录表在CPU对Cache进行写操作时，系统根据目录表中的信息将所有其它存有相同内容的Cache拷贝无效，并置重写位。在CPU对Cache

进行读操作时，如果重写未置位，则说明该内容未经重写，此时若Cache读缺失，则从主存储器中或拥有正确内容的Cache中读入块并修改目录即可；如果读命中，则直接读即可。本章内容>>一致性问题>>Cache一

致性>>解决方法>>目录协议3之3全映射目录协议本章内容>>一致性问题>>Cache一致性>>解决方法>>目录协议5之1目录项：重写位存在位数据块C101X共享存储器CacheP2VCacheP1VXCacheP3VXV-有效位：0-无效；1-有效C-重写位

：0-不许；1-允许存在位：0-不存在；1-存在位数等于处理机数举例本章内容>>一致性问题>>Cache一致性>>解决方法>>目录协议5之2目录项：重写位存在位数据块0000X共享存储器CacheP20CacheP

10CacheP30①所有Cache都没有块X的拷贝有效位有效位有效位举例本章内容>>一致性问题>>Cache一致性>>解决方法>>目录协议5之3目录项：重写位存在位数据块0111X共享存储器CacheP21XCacheP11XCacheP31X②三个处理机都读过块X后有效位有效位有效位举例本章

内容>>一致性问题>>Cache一致性>>解决方法>>目录协议5之4目录项：重写位存在位数据块1001X共享存储器CacheP20CacheP10CacheP31X③P3获得写块X权力后有效位有效位有效位特点全映射目录协议的效率比较高，但是其目录开销比较大，与处理器数平方成正比（因为目

录项的多少与处理器数成正比，而且每个目录项的大小也与处理器数成正比），不具有可扩展性。本章内容>>一致性问题>>Cache一致性>>解决方法>>目录协议5之5有限目录协议本章内容>>一致性问题>>Ca

che一致性>>解决方法>>目录协议4之1目录项：重写位存在位数据块C11X共享存储器CacheP2VCacheP1VXCacheP3VXV-有效位：0-无效；1-有效C-重写位：0-不许；1-允许存在位：0-不存在；1-存在位数等于l

og2处理机数举例本章内容>>一致性问题>>Cache一致性>>解决方法>>目录协议4之2目录项：重写位存在位数据块011X共享存储器CacheP20CacheP11XCacheP31X①当P1、P3的Cache中都有块X的拷贝时举例本章内容>>一致性

问题>>Cache一致性>>解决方法>>目录协议4之3目录项：重写位存在位数据块011X共享存储器CacheP21XCacheP10CacheP31X②P2请求块X的拷贝（存在驱逐问题）特点有限目录协议解决了目录过大的问题，其目录开销与Nlog2

N成正比，N为处理器数（因为目录项的多少与处理器数成正比，而且每个目录项的大小与log2N成正比），但效率有所下降。本章内容>>一致性问题>>Cache一致性>>解决方法>>目录协议4之4链式目录协议本章内容>>一致性问

题>>Cache一致性>>解决方法>>目录协议2之1目录项：重写位指针数据块CX共享存储器CacheP2CacheP1VXCacheP3V-有效位：0-无效；1-有效C-重写位：0-不许；1-允许VXVXCT特点链

式目录协议的复杂程度超过前两种目录协议，但它具有前两种目录协议所没有的重要特性：可扩展性。其指针的大小以处理机数目的对数关系增长，Cache的每个数据块的指针数目与处理机数目无关。本章内容>>一致性问题>>Cache一致性>>解决方法>>目录协议2之2I/O与Cache的一致性本章内容>>一致性

问题>>Cache一致性>>解决方法•禁止法存储空间中的某些段不允许进入Cache。•刷新法操作系统在I/O操作前，将有关的段先从Cache刷新过来，然后再进行I/O操作。存储一致性本章内容>>一致性问题•问题现象•解决方法问题现象本章内容>>一致性问题>>存储一致性存储

一致性是指多个处理机程序的执行次序与共享存储器中共享数据存取次序之间的一致性。特征不同处理机对不同存储单元的操作引起的一致性。a.A:=1b.printB,Cc.B:=1d.printA,Ce.C:=1f.printA,BA、B、C为共享变量(初始状态均为0)处理机1处理

机2处理机3共享存储器解决方法本章内容>>一致性问题>>存储一致性•顺序一致性（SC）任何执行结果认为是在多线程顺序机器上各操作交错执行的结果。•处理机一致性（PC）每台处理机发出的写操作顺序不会乱，但两台处理机发出的写操作顺序可能会不一样。•弱一致性（WC）程序员利用同步

操作确保顺序一致性。•释放一致性（RC）具有获得和释放两类同步操作的弱一致性，每类操作保证处理机一致性。同步本章内容•为什么要同步？在多处理机中，进程之间可以通过使用共享变量来实现信息交流，共享变量每次只能被一个进程访问，因此当两个或两个以上的进程同时访问某个共享变量时，必须

采用同步措施来协调并行执行的进程。•如何实现同步？一般来说，同步机制是通过用户级的软件例程来构造的，而这些例程要使用硬件提供的同步指令。2之1同步本章内容•基本硬件原语•用户级的同步操作2之2基本硬件原语本章内容>>同步•在多处理机中实现同步，所需的主

要功能是：一组能以原子操作的方式读出并修改存储单元的硬件原语。它们能够自动读／修改单元。•通常情况下，用户不直接使用基本的硬件原语，原语主要供系统程序员用来编制同步库函数。7之1原子交换（atomicexchange）本章内容>>同步•功能将一个存储单元的值和一个寄存器的值进行交换。•例子可以利用

它构建一个简单的锁：0表示该锁未被占用，1表示该锁已被占用。如果某处理机想占用该锁，将对应于该锁的存储单元的值与存放在某个寄存器中的1进行交换，返回结果为0则占用成功，为1则未占用成功。•实现同步的关键操作的原子性（交换操作是不可再细分的）。7之2测试并置定（test_and_set）本章内容>

>同步•功能先测试一个存储单元的值，如果符合条件则修改其值。•例子可以定义一个测试0和设置1的操作，该操作的使用方法与原子交换类似。7之3读取并加1（fetch_and_increment）本章内容>>同步•功能返回存储

器中的值并以原子操作的方式使存储器中的值增1。•例子如果用0表示同步变量未被占用，就可以象使用原子交换一样使用“取并增1‖操作。7之4使用指令对:LL/SC本章内容>>同步•LL(loadlinked或loadlocked)：特殊的取指令•SC(storeconditional)：特殊

的存指令•指令对功能：–如果由LL指明的存储单元的内容在SC对其进行写之前已被其他指令改写过，则第二条指令SC执行失败。–如果在两条指令间进行切换也会导致SC执行失败。–SC将返回一个值来指出该指令操作是否成功：“1‖表示成功，“0‖表示

不成功–LL则返回该存储单元初始值。7之5LL/SC指令对举例本章内容>>同步•利用LL和SC指令实现“原子交换”操作实现R4和由R1指出的存储单元进行原子交换操作。try：ORR3,R4,R0LLR2,0(R1)SCR3,0(R

1)BEQZR3,tryMOVR4,R27之6LL/SC指令对举例本章内容>>同步•利用LL和SC指令实现“取并增1‖操作LL/SC机制的一个优点：用来构造别的同步原语。try：LLR2,0(R1)DADDIUR2,R2,#1SCR2,0(R1)BEQZR2,try7之7用户级的同步操作

本章内容>>同步•旋转锁•栅栏旋转锁本章内容>>同步>>用户级的同步操作•思想处理机环绕一个锁不停地旋转而请求获得该锁。即：处理机围绕该锁反复地执行循环程序，直至获得该锁。•适合场合锁被占用的时间很少，在获得锁后

加锁过程延迟很小，因为处理机一直在循环等待获得锁。11之1旋转锁的实现本章内容>>同步>>用户级的同步操作•无Cache一致性机制在存储器中保存锁变量，处理机可以不断地通过一个原子交换请求使用权。–占用锁DADDIUR2,R0

,#1lockit：EXCHR2,0(R1)//原子交换BNEZR2,lockit–释放锁处理机只需将0放入锁中即可。11之2旋转锁的实现本章内容>>同步>>用户级的同步操作•无Cache一致性机制在存储器中保存锁变量，处理

机可以不断地通过一个原子交换请求使用权。–缺点每次交换（EXCH指令）都产生一次写操作，如果多个处理机试图占用一个锁时，则大多数写操作都会导致写无效，因为每个处理机都想以独占的方式获得锁变量。11之3旋转锁的实现本章内容>>同步>>用户级的

同步操作•支持Cache一致性–将锁变量调入Cache，并通过一致性机制使锁值保持一致。–优点：•每次尝试占用锁都可以在本地Cache中进行，而不需进行全局存储访问；•大多数对锁的访问有局限性，这样做可以大大减少获取锁所需的时间。11之4旋转锁的实现本章内容>>同步>>用户级的

同步操作•支持Cache一致性–采用“原子交换”原语实现（改进）：只对本地Cache中锁的副本进行读取和检测，直到发现该锁已经被释放。然后，该程序立即进行交换操作，去跟在其他处理器上的进程争用该锁变量。lockit：LDR2,0(R1)BNEZR

2,lockitDADDIUR2,R0,#1EXCHR2,0(R1)//原子交换BNEZR2,lockit11之5步骤处理机P0处理机P1处理机P2锁的状态总线/目录操作1占有锁环绕测试是否lock=0？环绕测试是否lock=0？共享无2将锁置为0（收到作废

命令）（收到作废命令）专有(P0)P0发出对锁变量的作废消息3Cache失效Cache失效共享总线/目录收到P2Cache失效；锁从P0写回4（因总线/目录忙而等待）lock=0共享P2Cache失效被处理5Lock=0执行

交换，导致Cache失效共享P1Cache失效被处理6执行交换，导致Cache失效交换完毕：返回0并置lock=1专有(P2)总线/目录收到P2Cache失效；发作废消息7交换完毕：返回1进入关键程序段专有(P1)总线/目录处理P1Cac

he失效；写回8环绕测试是否lock=0？无3个处理机利用原子交换争用旋转锁所进行的操作11之6旋转锁的实现本章内容>>同步>>用户级的同步操作•支持Cache一致性–采用LL/SC原语实现：读/写操作明显分开，而且LL原语不产生总线数据传送，这使

下面代码与前面方法具有相同的特点。lockit：LLR2,0(R1)BNEZR2,lockitDADDIUR2,R0,#1SCR2,0(R1)BEQZR2,lockit11之7同步性能问题本章内容>>同步>>用户级的同步操作简单旋转锁不能很好地适应可扩缩性。大规模

多处理机中，若所有的处理器都同时争用同一个锁，则会导致大量的争用和通信开销。11之8定量分析本章内容>>同步>>用户级的同步操作例：假设某条总线上有10个处理机同时准备对同一变量加锁。如果每个总线事务处理（读失效或写失效）的时间是100个时钟周期，而且忽略对已调入Cache中的

锁进行读写的时间以及占用该锁的时间。(1)假设该锁在时间为0时被释放，并且所有处理机都在旋转等待该锁。问：所有10个处理机都获得该锁所需的总线事务数目是多少？(2)假设总线是非常公平的，在处理新请求之前，要先全部处

理好已有的请求。并且各处理机的速度相同。问：处理10个请求大概需要多少时间？11之9定量分析本章内容>>同步>>用户级的同步操作解：当i个处理器争用锁的时候，它们都各自完成以下操作序列，每一个操作产生一个总线事务：

–访问该锁的i个LL指令操作–试图占用该锁（并上锁）的i个SC指令操作–1个释放锁的存操作指令因此对于i个处理器来说，一个处理器获得该锁所要进行的总线事务的个数为2i+1。由此可知，对n个处理器，总的总线事务个数为：对于10个处理器来说，其总线事务数为120个，需要

12000个时钟周期。n1i2n2nn)1n(n)1i2(11之10问题分析本章内容>>同步>>用户级的同步操作•本例中问题的根源：锁的争用、对锁进行访问的串行性以及总线访问的延迟。•旋转锁的主要优点：总线开销或网络开销比较低，而且当一个锁被同一

个处理器重用时具有很好的性能。•旋转锁的两个主要优点在本例中都没有得到体现11之11栅栏本章内容>>同步>>用户级的同步操作•栅栏思想栅栏强制所有到达该栅栏的进程进行等待，直到全部的进程到达栅栏，然后释放全部的进程，从而形成同步。•典型实现用两个旋转锁：–一个用来保护一个计数器

，它记录已到达该栅栏的进程数；–另一个用来封锁进程直至最后一个进程到达该栅栏。6之1一种典型的实现本章内容>>同步>>用户级的同步操作lock（counterlock）；//if（count==0）release=0；//第一个进程则重置releasecount=count+1

；//到达进程数加1unlock（counterlock）；//if（count==total）{//count=0；//release=1；//｝else{//spin（release=1）；//｝6之

2解释本章内容>>同步>>用户级的同步操作•counterlock用来保护计数器，使其以原子操作的方式递增。•变量count计算到达栅栏的进程数目。•total规定了要到达栅栏的进程总数•变量release用于标识最

后一个处理机是否到达栅栏。•Spin(release)操作使处理机等待直到所有处理机到达栅栏。6之3问题及解决本章内容>>同步>>用户级的同步操作•问题栅栏经常在循环内使用，因此有可能在最后一个进程离开栅栏之前最先得到

调度的进程再次到达同一栅栏，然后先被调度的进程通过重置release标志又将未调度的进程陷在栅栏中。这样这些进程会永远等在这个栅栏上，因为有一个进程还未从上一次栅栏中出来，故而进程数目无法到达total值。•解

决–方法1：计算离开栅栏的进程数目，直到所有进程都离开栅栏之前不允许任何进程再次进入栅栏或初始化栅栏。–方法2：采用“判断-回转栅栏”6之4判断-回转栅栏（sense-reversingbarrier）本章内容>>同步>>用户级的同步操作local_sense=!local

_sense；//local-senselock（counterlock）；//count++；//到达进程数加1unlock（counterlock）；//if（count==total）{//count=0；//release=loca

l_sense；//｝else{//spin（release==local_sense）；//｝6之5解释本章内容>>同步>>用户级的同步操作•每个进程均使用一个私有变量local_sense，该变量初始化为1。•优缺点：使用安全，但性能

比较差。对于10个处理器来说，当同时进行栅栏操作时，如果忽略对Cache的访问时间以及其他非同步操作所需的时间，则其总线事务数为204个，如果每个总线事物需要100个时钟周期，则总共需要20400个时钟周期。6之

6