计算机系统结构-多处理机课件

1、计算机系统结构多处理机课件计算机系统结构多处理机课件提 示本章内容2 之 2 因为多处理机系统结构是一个巨大而多样的领域，其中很多领域仍处于不成熟的阶段，所以本课程集中于多处理机设计的主流进行讨论：由少量到中等数量的处理机（128）组成的机器。提 示本章内容2 之 2 因为多处理机系统结构多处理机结构本章内容 根据存储器的组织形式，多处理机有两种基本结构：集中式共享存储器结构分布式共享存储器结构多处理机结构本章内容 根据存储器的组织形式，多处集中式共享存储器结构多处理机本章内容多处理机结构 存储器是一个独立的子系统，通过互连网络（交叉开关/总线）为所有的处理机共享，任何两台处理机都可以通过访问

2、共享的存储器单元实现通信。 由于共享存储器对每个处理机都是对称关系，而且所有处理机对共享存储器的访问时间都相同，这种结构的多处理机也称为对称多处理机（SMP）和均匀存储器存取（UMA）。2 之 1集中式共享存储器结构多处理机本章内容多处理机结构 图 示本章内容多处理机结构2 之 2处理机1级/多级Cache存储器处理机1级/多级Cache处理机1级/多级Cache处理机1级/多级CacheI/O系统图 示本章内容多处理机结构2 之 2处理机1级/多级存分布式共享存储器结构(DSM)多处理机本章内容多处理机结构 存储器分布在各处理机中，但这些存储器在逻辑上统一编址，形成一个为所有处理机共享的虚拟

3、共享存储器。处理机之间信息交换的物理实现仍然是通过点-点的通信。 由于任何一个处理机访问本地存储器都较快，但是访问分布在其他处理机的远程存储器则较慢，这种结构的多处理机也称为非均匀存储器存取（NUMA）。3 之 1分布式共享存储器结构(DSM)多处理机本章内容多处理机结图 示本章内容多处理机结构3 之 2处理机+Cache存储器互 连 网 络I/O处理机+Cache存储器I/O处理机+Cache存储器I/O处理机+Cache存储器I/O处理机+Cache存储器I/O处理机+Cache存储器I/O图 示本章内容多处理机结构3 之 2处理机存储器互 连比 较本章内容多处理机结构3 之 3集中共享分

4、布共享处理机数301000限制结点间间距和延迟数据局部性比 较本章内容多处理机结构3 之 3集中共享分布共享处一致性问题本章内容Cache一致性存储一致性一致性问题本章内容Cache一致性Cache一致性本章内容一致性问题问题现象原因分析解决方法Cache一致性本章内容一致性问题问题现象问题现象本章内容一致性问题Cache一致性 Cache一致性是指私有Cache中共享数据的副本和共享存储器中共享数据之间的一致性。u:7u:?P1C u:5主存 CCP2P3特征 多处理器对相同存储单元的操作引起的一致性。u:5u:5u:7问题现象本章内容一致性问题Cache一致性 原因分析本章内容一致性问题C

5、ache一致性共享可写数据引起的不一致性进程迁移引起的数据不一致性I/O传输造成的数据不一致性原因分析本章内容一致性问题Cache一致性共享可写数共享可写数据引起的不一致性 不同处理器对相同单元在各自Cache的拷贝的异步写操作。本章内容一致性问题Cache一致性原因分析P1XXP2X处理机Cache共享存储器更新之前P1XXP2X更新之后（写通过）P1XXP2X更新之后（写回）共享可写数据引起的不一致性 不同处理器对相同单元进程迁移引起的数据不一致性本章内容一致性问题Cache一致性原因分析 多处理器中的进程迁移，而又不互相通报。P1XXP2X处理机Cache共享存储器初始状态P1XXP2X

6、迁移之前（写通过）进程P1XXP2X迁移之后（写通过）进程进程进程迁移引起的数据不一致性本章内容一致性问题CachI/O传输造成的数据不一致性本章内容一致性问题Cache一致性原因分析绕过Cache拷贝拥有者的I/O操作。P1XX处理机Cache共享存储器I/O前P2XI/OP1XXI/O后XP2XP1XXI/O后（写回）XP2X共享存储器输入共享存储器输出I/O传输造成的数据不一致性本章内容一致性问题Cac解决方法前两种原因监听法目录法第三种原因禁止法刷新法本章内容一致性问题Cache一致性解决方法前两种原因第三种原因本章内容一致性问题Cac监听协议基本原理具体实现采用写通过策略的Cache

7、采用写回策略的Cache写一次（Write-Once）协议本章内容一致性问题Cache一致性解决方法监听协议基本原理本章内容一致性问题Cache一致性基本原理本章内容一致性问题Cache一致性解决方法监听协议4 之 1 本方法只适用于采用基于总线互连结构的系统中，由于系统中每个处理机都能觉察到存储器系统正在进行的活动，在某个活动破坏了Cache的一致性时， Cache控制器将采取相应的动作使有关的拷贝无效或更新。基本原理本章内容一致性问题Cache一致性解决方写无效/写更新本章内容一致性问题Cache一致性解决方法监听协议4 之 2 使用监听协议来保持Cache一致性有两种方法：方法一：写无效

8、（Write Invalidate）策略 在本地Cache的数据块修改时使远程数据块都无效。方法二：写更新（Write Update）策略 在本地Cache数据块修改时通过总线把新的数据块广播给含该块的所有其他Cache。提示：采用写无效或写更新策略与Cache采用写回还是写通过方式无关。写无效/写更新本章内容一致性问题Cache一致性图 示本章内容一致性问题Cache一致性解决方法监听协议4 之 3P1XXP2X处理机Cache共享存储器更新之前P1XIP2X更新之后(Write-Invalidate)P1XXP2X更新之后(Write-Update)图 示本章内容一致性问题Cache一致性

9、解决方应用情况本章内容一致性问题Cache一致性解决方法监听协议4 之 4 由于写更新法在本地Cache修改时需要通过总线把修改过的数据块的内容广播给所有含该数据块的其他Cache，增加了总线的负担，所以在一般的应用系统中，极少使用写更新法。 本方法实现简单，但只适用于总线式互连的多处理机，而且写无效法和写更新法都要占用总线不少时间，因此只能用于机数少的多处理机中。应用情况本章内容一致性问题Cache一致性解决方采用写通过策略的Cache本章内容一致性问题Cache一致性解决方法监听协议 Cache数据块有两种状态: 有效和无效，有效状态表示该数据块内容正确，无效状态表示该数据块内容已“过时”

10、或不在Cache中。RL、WL表示本地处理机对Cache的读和写操作，RR、WR表示远程处理机对Cache中相同内容数据的读和写操作。采用写通过策略的Cache本章内容一致性问题Cach采用写回策略的Cache本章内容一致性问题Cache一致性解决方法监听协议2 之 1采用写回策略的Cache本章内容一致性问题Cache采用写回策略的Cache Cache数据块有三种状态: 只读、读写和无效。只读状态表示整个系统中有多个数据块拷贝是正确的；读写状态表示数据块至少被修改过一次，存储器中相应数据块还没有修改，在整个系统中只有一个数据块拷贝是正确的；无效状态表示该数据块内容已“过时”或不在Cache

11、中。 RL、WL表示本地处理机对Cache的读和写操作，RR、WR表示远程处理机对Cache中相同内容数据的读和写操作。本章内容一致性问题Cache一致性解决方法监听协议2 之 2采用写回策略的Cache Cache数据块有三种状态写一次协议本章内容一致性问题Cache一致性解决方法监听协议4 之 1 本方法为了降低总线流量，结合了写回和写通过策略的优点。在第一次写Cache采用写通过策略，以后写Cache采用写回策略，此时整个系统中只有一份正确的拷贝。写一次协议本章内容一致性问题Cache一致性解决写一次协议本章内容一致性问题Cache一致性解决方法监听协议4 之 2RR写一次协议本章内容一

12、致性问题Cache一致性解决写一次协议本章内容一致性问题Cache一致性解决方法监听协议4 之 3 Cache数据块有四种状态: 有效、保留、重写和无效。有效状态表示整个系统中有多个数据块拷贝是正确的；保留状态表示数据从存储器读入Cache后只被写过一次，Cache和存储器中拷贝都正确；重写状态表示Cache中的数据块被写过多次，而且是唯一正确的数据块；无效状态表示该数据块内容已“过时”或不在Cache中。 RL、WL表示本地处理机对Cache的读和写操作，RR、WR表示远程处理机对Cache中相同内容数据的读和写操作。写一次协议本章内容一致性问题Cache一致性解决写一次协议本章内容一致性问

13、题Cache一致性解决方法监听协议4 之 4 主要优点： 减少大量的无效操作，提高了总线效率。 主要缺点： 当主存储器的内容无效时,读缺失引起的总线读操作必须禁止主存储器的操作（以免造成总线冲突），而大多数总线不支持这种操作。IEEE Futurebus+总线支持该操作。写一次协议本章内容一致性问题Cache一致性解决目录协议基本原理具体实现全映射目录协议有限目录协议链式目录协议本章内容一致性问题Cache一致性解决方法目录协议基本原理本章内容一致性问题Cache一致性基本原理本章内容一致性问题Cache一致性解决方法目录协议 监听协议涉及大量广播通信及收集状态信息的任务，即使是总线型网络也会

14、使总线流量大大增加。 如果使无效信息只发给有关的数据块，可以避免广播，这需要有一套管理数据块的结构，这就是Cache一致性目录协议方案。3 之 1基本原理本章内容一致性问题Cache一致性解决方基本原理 建立目录表 为Cache在共享存储器建立一个目录表，用于保存每个数据块的状态：包括用几个标志位分别指示这个信息块的副本在其他几个处理机的Cache中是否有，另外再设置一个标志位（重写位）用以指明是否有一个Cache允许将有关数据写入。本章内容一致性问题Cache一致性解决方法目录协议3 之 2 目录协议用在实现广播功能比较困难的网络。主要思想为：基本原理 建立目录表本章内容一致性问题Cache

15、一基本原理 使用目录表 在CPU对Cache进行写操作时，系统根据目录表中的信息将所有其它存有相同内容的Cache拷贝无效，并置重写位。在CPU对Cache进行读操作时，如果重写未置位，则说明该内容未经重写，此时若Cache读缺失，则从主存储器中或拥有正确内容的Cache中读入块并修改目录即可；如果读命中，则直接读即可。本章内容一致性问题Cache一致性解决方法目录协议3 之 3基本原理 使用目录表本章内容一致性问题Cache一全映射目录协议本章内容一致性问题Cache一致性解决方法目录协议5 之 1目录项： 重写位 存在位 数据块C101X共享存储器CacheP2VCacheP1VXCach

16、eP3VXV-有效位：0-无效；1-有效C-重写位：0-不许；1-允许存在位：0-不存在；1-存在 位数等于处理机数全映射目录协议本章内容一致性问题Cache一致性举 例本章内容一致性问题Cache一致性解决方法目录协议5 之 2目录项： 重写位 存在位 数据块0000X共享存储器CacheP20CacheP10CacheP30 所有Cache都没有块X的拷贝有效位有效位有效位举 例本章内容一致性问题Cache一致性解决方举 例本章内容一致性问题Cache一致性解决方法目录协议5 之 3目录项： 重写位 存在位 数据块0111X共享存储器CacheP21XCacheP11XCacheP31X

17、三个处理机都读过块X后有效位有效位有效位举 例本章内容一致性问题Cache一致性解决方举 例本章内容一致性问题Cache一致性解决方法目录协议5 之 4目录项： 重写位 存在位 数据块1001X共享存储器CacheP20CacheP10CacheP31X P3获得写块X权力后有效位有效位有效位举 例本章内容一致性问题Cache一致性解决方特 点 全映射目录协议的效率比较高，但是其目录开销比较大，与处理器数平方成正比（因为目录项的多少与处理器数成正比，而且每个目录项的大小也与处理器数成正比），不具有可扩展性。本章内容一致性问题Cache一致性解决方法目录协议5 之 5特 点 全映射目录协议的效率

18、比较高，但是其目录有限目录协议本章内容一致性问题Cache一致性解决方法目录协议4 之 1目录项： 重写位 存在位 数据块C11X共享存储器CacheP2VCacheP1VXCacheP3VXV-有效位：0-无效；1-有效C-重写位：0-不许；1-允许存在位： 0-不存在；1-存在 位数 等于 log2处理机数有限目录协议本章内容一致性问题Cache一致性解举 例本章内容一致性问题Cache一致性解决方法目录协议4 之 2目录项： 重写位 存在位 数据块011X共享存储器CacheP20CacheP11XCacheP31X 当P1、P3的Cache中都有块X的拷贝时举 例本章内容一致性问题Ca

19、che一致性解决方举 例本章内容一致性问题Cache一致性解决方法目录协议4 之 3目录项： 重写位 存在位 数据块011X共享存储器CacheP21XCacheP10CacheP31X P2请求块X的拷贝（存在驱逐问题）举 例本章内容一致性问题Cache一致性解决方特 点 有限目录协议解决了目录过大的问题，其目录开销与Nlog2N成正比，N为处理器数（因为目录项的多少与处理器数成正比，而且每个目录项的大小与log2N成正比），但效率有所下降。本章内容一致性问题Cache一致性解决方法目录协议4 之 4特 点 有限目录协议解决了目录过大的问题，其目链式目录协议本章内容一致性问题Cache一致性

20、解决方法目录协议2 之 1目录项：重写位指针 数据块CX共享存储器CacheP2CacheP1VXCacheP3V-有效位：0-无效；1-有效C-重写位：0-不许；1-允许VXVXCT链式目录协议本章内容一致性问题Cache一致性解特 点 链式目录协议的复杂程度超过前两种目录协议，但它具有前两种目录协议所没有的重要特性：可扩展性。其指针的大小以处理机数目的对数关系增长，Cache的每个数据块的指针数目与处理机数目无关。本章内容一致性问题Cache一致性解决方法目录协议2 之 2特 点 链式目录协议的复杂程度超过前两种目录协I/O与Cache的一致性本章内容一致性问题Cache一致性解决方法 禁

21、止法 存储空间中的某些段不允许进入Cache。 刷新法 操作系统在I/O操作前，将有关的段先从Cache刷新过来，然后再进行I/O操作。I/O与Cache的一致性本章内容一致性问题Cach存储一致性本章内容一致性问题问题现象解决方法存储一致性本章内容一致性问题问题现象问题现象本章内容一致性问题存储一致性 存储一致性是指多个处理机程序的执行次序与共享存储器中共享数据存取次序之间的一致性。特征 不同处理机对不同存储单元的操作引起的一致性。a. A :=1b. print B,Cc. B :=1d. print A,Ce. C :=1f. print A,BA、B、C 为共享变量(初始状态均为0)处

22、理机1处理机2处理机3共享存储器问题现象本章内容一致性问题存储一致性 存解决方法本章内容一致性问题存储一致性 顺序一致性（SC） 任何执行结果认为是在多线程顺序机器上各操作交错执行的结果。 处理机一致性（PC） 每台处理机发出的写操作顺序不会乱，但两台处理机发出的写操作顺序可能会不一样。 弱一致性（WC） 程序员利用同步操作确保顺序一致性。 释放一致性（RC） 具有获得和释放两类同步操作的弱一致性，每类操作保证处理机一致性。解决方法本章内容一致性问题存储一致性 顺序一致性（同 步本章内容为什么要同步？ 在多处理机中，进程之间可以通过使用共享变量来实现信息交流，共享变量每次只能被一个进程访问，因

23、此当两个或两个以上的进程同时访问某个共享变量时，必须采用同步措施来协调并行执行的进程。如何实现同步？ 一般来说，同步机制是通过用户级的软件例程来构造的，而这些例程要使用硬件提供的同步指令。2 之 1同 步本章内容为什么要同步？2 之 1同 步本章内容基本硬件原语用户级的同步操作2 之 2同 步本章内容基本硬件原语2 之 2基本硬件原语本章内容同步在多处理机中实现同步，所需的主要功能是：一组能以原子操作的方式读出并修改存储单元的硬件原语。它们能够自动读修改单元。通常情况下，用户不直接使用基本的硬件原语，原语主要供系统程序员用来编制同步库函数。7 之 1基本硬件原语本章内容同步在多处理机中实现同步

24、，所需的主要原子交换（atomic exchange）本章内容同步功能 将一个存储单元的值和一个寄存器的值进行交换。例子 可以利用它构建一个简单的锁：0表示该锁未被占用，1表示该锁已被占用。如果某处理机想占用该锁，将对应于该锁的存储单元的值与存放在某个寄存器中的1进行交换，返回结果为0则占用成功，为1则未占用成功。实现同步的关键 操作的原子性（交换操作是不可再细分的）。7 之 2原子交换（atomic exchange）本章内容同步测试并置定（test_and_set）本章内容同步功能 先测试一个存储单元的值，如果符合条件则修改其值。例子 可以定义一个测试0和设置1的操作，该操作的使用方法与原

25、子交换类似。7 之 3测试并置定（test_and_set）本章内容同步功能读取并加1（fetch_and_increment）本章内容同步功能 返回存储器中的值并以原子操作的方式使存储器中的值增1。例子 如果用0表示同步变量未被占用，就可以象使用原子交换一样使用“取并增1”操作。7 之 4读取并加1（fetch_and_increment）本章内容使用指令对:LL/SC本章内容同步LL(load linked或load locked)：特殊的取指令SC(store conditional)：特殊的存指令指令对功能：如果由LL指明的存储单元的内容在SC对其进行写之前已被其他指令改写过，则第二条

26、指令SC执行失败。如果在两条指令间进行切换也会导致SC执行失败。SC将返回一个值来指出该指令操作是否成功：“1”表示成功，“0”表示不成功LL则返回该存储单元初始值。 7 之 5使用指令对:LL/SC本章内容同步LL(load linLL/SC指令对举例本章内容同步利用LL和SC指令实现“原子交换”操作 实现R4和由R1指出的存储单元进行原子交换操作。try：ORR3, R4, R0 LLR2, 0(R1) SCR3, 0(R1) BEQZR3, try MOVR4, R27 之 6LL/SC指令对举例本章内容同步利用LL和SC指令实现“LL/SC指令对举例本章内容同步利用LL和SC指令实现“

27、取并增1”操作 LL/SC机制的一个优点：用来构造别的同步原语。try： LLR2, 0(R1) DADDIUR2, R2, #1 SCR2, 0(R1) BEQZR2, try7 之 7LL/SC指令对举例本章内容同步利用LL和SC指令实现“用户级的同步操作本章内容同步旋转锁栅栏用户级的同步操作本章内容同步旋转锁旋转锁本章内容同步用户级的同步操作思想 处理机环绕一个锁不停地旋转而请求获得该锁。即：处理机围绕该锁反复地执行循环程序，直至获得该锁。适合场合 锁被占用的时间很少，在获得锁后加锁过程延迟很小，因为处理机一直在循环等待获得锁。11 之 1旋转锁本章内容同步用户级的同步操作思想11 之

28、1旋转锁的实现本章内容同步用户级的同步操作无Cache一致性机制 在存储器中保存锁变量，处理机可以不断地通过一个原子交换请求使用权。占用锁 DADDIUR2, R0, #1 lockit： EXCH R2, 0(R1) /原子交换 BNEZR2, lockit释放锁 处理机只需将0放入锁中即可。11 之 2旋转锁的实现本章内容同步用户级的同步操作无Cache旋转锁的实现本章内容同步用户级的同步操作无Cache一致性机制 在存储器中保存锁变量，处理机可以不断地通过一个原子交换请求使用权。缺点 每次交换（EXCH指令）都产生一次写操作，如果多个处理机试图占用一个锁时，则大多数写操作都会导致写无效，

29、因为每个处理机都想以独占的方式获得锁变量。11 之 3旋转锁的实现本章内容同步用户级的同步操作无Cache旋转锁的实现本章内容同步用户级的同步操作支持Cache一致性将锁变量调入Cache，并通过一致性机制使锁值保持一致。优点：每次尝试占用锁都可以在本地Cache中进行，而不需进行全局存储访问；大多数对锁的访问有局限性，这样做可以大大减少获取锁所需的时间。11 之 4旋转锁的实现本章内容同步用户级的同步操作支持Cach旋转锁的实现本章内容同步用户级的同步操作支持Cache一致性采用“原子交换”原语实现（改进）：只对本地Cache中锁的副本进行读取和检测，直到发现该锁已经被释放。然后，该程序立即

30、进行交换操作，去跟在其他处理器上的进程争用该锁变量。 lockit： LD R2, 0(R1) BNEZ R2, lockit DADDIU R2, R0, #1 EXCH R2, 0(R1) /原子交换 BNEZ R2, lockit11 之 5旋转锁的实现本章内容同步用户级的同步操作支持Cach步骤 处理机P0 处理机P1 处理机P2 锁的状态 总线/目录操作 1占有锁 环绕测试是否lock=0？环绕测试是否lock=0？ 共享 无 2将锁置为0 （收到作废命令） （收到作废命令）专有(P0) P0发出对锁变量的作废消息 3Cache失效 Cache失效 共享总线/目录收到P2 Cache

31、失效；锁从P0写回 4（因总线/目录忙而等待）lock=0共享P2 Cache失效被处理 5Lock=0 执行交换，导致Cache失效共享P1 Cache失效被处理 6执行交换，导致Cache失效 交换完毕：返回0并置lock=1 专有(P2) 总线/目录收到P2 Cache失效；发作废消息 7交换完毕：返回1 进入关键程序段 专有(P1)总线/目录处理P1 Cache失效；写回 8环绕测试是否lock=0？ 无3个处理机利用原子交换争用旋转锁所进行的操作 11 之 6步骤 处理机P0 处理机P1 处理机P2 锁的状态 总线/目旋转锁的实现本章内容同步用户级的同步操作支持Cache一致性采用L

32、L/SC原语实现：读/写操作明显分开，而且LL原语不产生总线数据传送，这使下面代码与前面方法具有相同的特点。 lockit：LL R2, 0(R1) BNEZ R2, lockit DADDIU R2, R0, #1 SC R2, 0(R1) BEQZ R2, lockit11 之 7旋转锁的实现本章内容同步用户级的同步操作支持Cach同步性能问题本章内容同步用户级的同步操作 简单旋转锁不能很好地适应可扩缩性。大规模多处理机中，若所有的处理器都同时争用同一个锁，则会导致大量的争用和通信开销。11 之 8同步性能问题本章内容同步用户级的同步操作 定量分析本章内容同步用户级的同步操作例：假设某条总

33、线上有10个处理机同时准备对同一变量加锁。如果每个总线事务处理（读失效或写失效）的时间是100个时钟周期，而且忽略对已调入Cache中的锁进行读写的时间以及占用该锁的时间。(1) 假设该锁在时间为0时被释放，并且所有处理机都在旋转等待该锁。问：所有10个处理机都获得该锁所需的总线事务数目是多少？(2) 假设总线是非常公平的，在处理新请求之前，要先全部处理好已有的请求。并且各处理机的速度相同。问：处理10个请求大概需要多少时间？11 之 9定量分析本章内容同步用户级的同步操作例：假设某条总线定量分析本章内容同步用户级的同步操作解：当i个处理器争用锁的时候，它们都各自完成以下操作序列，每一个操作产

34、生一个总线事务：访问该锁的i个LL指令操作试图占用该锁（并上锁）的i个SC指令操作1个释放锁的存操作指令 因此对于i个处理器来说，一个处理器获得该锁所要进行的总线事务的个数为2i+1。 由此可知，对n个处理器，总的总线事务个数为： 对于10个处理器来说，其总线事务数为120个，需要12000个时钟周期。11 之 10定量分析本章内容同步用户级的同步操作解：当i个处理器问题分析本章内容同步用户级的同步操作本例中问题的根源：锁的争用、对锁进行访问的串行性以及总线访问的延迟。旋转锁的主要优点：总线开销或网络开销比较低，而且当一个锁被同一个处理器重用时具有很好的性能。旋转锁的两个主要优点在本例中都没有得到体现11 之 11问题分析本章内容同步用户级的同步操作本例中问题的根源栅 栏本章内容同步用户级的同步操作栅栏思想 栅栏强制所有到达该栅栏的进程进行等待，直到全部的进程到达栅栏，然后释放全部的进程，从而形成同步。典型实现 用两个旋转锁：一个用来保护一个计数器，它记录已到达该栅栏的进程数；另一个用来封锁进程直至最后一个进程到达该栅栏。 6 之 1栅 栏本章内容同步用户级的同步操作栅栏思想6 之 一种典型的实现本章内容同步用户级的同步操作lock（counterlock）