体系结构复习4——线程级并行

体系结构复习 CH7 线程级并行


7.1 多处理器与线程级并行

7.1.1 多处理器体系结构

线程级并行是多处理器支持多个线程同时并行执行,多处理器体系结构大致分成两种:

  • 对称共享存储器多处理器(SMP):又叫集中式共享存储器体系结构,核心数目较小并共享一个集中式的存储器,所有处理器能够平等地访问它(又称为UMA,一致存储器访问);SMP的存储结构大致分成三层:共享主存、共享缓存和专用缓存,本章最重要的讨论即是专用缓存和共享存储之间的一致性问题。

  • 分布式共享存储(DSM):多处理采用物理分布式存储器,多个核心/分布式存储器通过高速互联网络连接;DSM中对不同的存储器访问时间是不一致的,显然核心对自身节点内部存储器访问速度大于其他节点存储器访问速度,并且访问其他节点存储器访问速度还与节点间的网络拓扑有关(又称为NUMA,非一致存储器访问);DSM共享存储器指的是共享地址空间,同样DSM需要关注分布式共享存储之间的一致性问题。

7.1.2 并行处理的挑战

并行处理面临2个重要的挑战:

  • 程序中有限的并行性:通过Amdahl定律可以计算加速比的瓶颈是串行部分占比
  • 多处理器远程访问延迟较大:同芯片不同核心之间的延迟、不同芯片不同核心之间的延迟

解决这两个问题的策略为:

  • 采用并行性更好的算法
  • 寻求更佳的体系结构和编程技术

7.2 集中式共享存储器体系结构和监听一致性协议

假设处理器A和B先后读取X(各自的缓存中存有X的副本),A修改了X并写回到主存,但此时B的缓存中X仍然是未修改的X,发生了缓存不一致现象

7.2.1 缓存一致性策略和方法

保证缓存一致性有两种策略:

  • 监听式:如果一个缓存拥有一个物理存储块中数据的副本,那么它就可以跟踪这个块的共享状态;SMP主要采用监听式缓存一致性协议
  • 目录式:为物理缓存块专门设立一个保存共享状态的目录,缓存去查询目录得到块的共享状态;DSM多采用分布式的目录一致性协议

实现缓存一致性有两种方法:

  • 写入失效法:如果一个处理器对某一共享的物理存储块副本写入,那么其他拥有该共享的物理存储块的缓存中全部失效
  • 写入更新法:如果一个处理器对某一共享的物理存储块副本写入,那么其他拥有该共享的物理存储块的缓存中全部更新为写入值

由于写更新需要占用相当多的带宽(有时还可能不必要),一半采取写失效的方法

7.2.2 监听一致性协议

简单的监听一致性协议为专用缓存中的缓存块分配一个有效位(标志有效无效)以及一个状态位(标志共享还是独占),那么一个缓存块有三种状态(无效块状态位无意义):

  • 无效:该缓存块中不存在有效的物理存储器块副本
  • 共享:该缓存块中存放的有效的物理存储器块副本被所有其他处理器共享,其含义是未做修改和主存中物理存储器块一致;并且其他处理器缓存中并不是一定存在该共享块,但保证一旦存在一定是和该块一致
  • 独占/已修改:该缓存块中存放的有效的物理存储器块副本是唯一的,和主存中物理存储器块不一致并且其他处理器缓存中一定保证没有该块的副本

监听协议中有几个关键动作:

  • 处理器写入共享块:直接写入并通知其他处理器该块失效,并修改状态为独占
  • 处理器写入独占块:直接写入不做通知不改状态
  • 处理器读入另一处理器的独占块:另一处理器收到有处理器尝试读取自己的独占块的通知,将独占块写回主存,并修改状态为共享,然后该处理器读取该块读取,并标记为共享
  • 处理器写入另一处理器的独占块:另一处理器收到有处理器尝试写入自己的独占块的通知,将独占块写回主存,并修改状态为失效,然后该处理器读取该块写入,然后标记为独占

把上述通知请求的形式给出并按其发送分类有一下完整的动作:

请求 寻址缓存块状态 缓存操作类型 动作
处理器 读命中 共享或独占 正常命中 直接读取本地缓存数据
处理器 读缺失 失效 正常缺失 向总线发送读缺失请求,请求数据装入缓存后读取,并标记为共享
处理器 读缺失 共享 替换 向总线发送读缺失请求,请求数据装入缓存替换原共享块后读取,并标记为共享
处理器 读缺失 独占 替换 写回独占块并标记为共享,向总线发送读缺失请求,请求数据装入缓存替换原独占块(现标记是共享)后读取,并标记为共享
处理器 写命中 共享 一致性 写入并标记独占,然后把失效请求放在总线上
处理器 写命中 独占 正常命中 直接写入本地缓存
处理器 写缺失 失效 正常缺失 向总线发送写缺失请求,请求数据装入缓存后写入,并标记为独占
处理器 写缺失 共享 替换 向总线发送写缺失请求,请求数据装入缓存替换原共享块后写入,并标记为独占
处理器 写缺失 独占 替换 先写回独占块并标记为失效,向总线发送写缺失请求,请求数据装入缓存替换该失效块后写入,并标记为独占
总线 读缺失 共享 无操作 允许共享块并不做动作
总线 读缺失 独占 一致性 写回独占块并标记为共享
总线 写缺失 共享 一致性 标记该共享块失效
总线 写缺失 独占 一致性 写回该独占块,并标记失效
总线 失效 共享 一致性 标记该共享块失效

注意:上述独占状态MSI协议(该简单一致性协议的另一种称呼)的Modified已修改状态(书上有时候叫它独占、有时候叫它已修改需要区分开来)

7.2.3 MSI协议扩展

(1)MESI

MSI有一个缺陷,先读一个block(读缺失)然后修改一个block时(写命中),将产生2个总线事务(读缺失时I->S,写命中时S->M并发送失效),即使是一个块“独占”这个读取的块时写命中也会在总线上发布失效请求,并且这种情形在多道程序负载时十分普遍

为了减少总线事务,针对这种情形提出了MESI协议,扩展了状态Exclusive State来表示仅有当前缓存中有该块副本并且该块是干净的(为了和之前独占的称呼区别开,我称它为干净独占状态),即该块和主存中的块是一致的

干净独占状态的块写入时,不产生总线写失效请求(因为事先已经知道其他缓存中没有该块副本,失效请求无意义),则上述“先读后写”的操作只产生一次总线事务,得到优化(注意:写入已修改状态的块时也不产生失效请求)

干净独占状态的定义我们知道只有一种情况能够产生这种状态:读失效时发现没有其他缓存有该块副本,并从主存加载该块

我的疑问:判断其他缓存中是否有该块副本不是需要在存储器块中增加标志位(复杂情况增加标志位也无法解决),那么是否这个判断过程又讲产生其他的总线事务呢?我认为是的

余老板提点,MESI也引入Cache-to-Cache的共享,若其他缓存监听到读缺失时检测到自己有相应块的副本时,终止内存访问而主动提供该块副本

然而我又有进一步的疑问:但这样多块都有S的相应副本,都去终止内存访问发送自己缓存中的副本?这不算是额外的开销?或者这样总线不会乱套(虽然发送的是相同数据)?[PS:这就是不听课的下场,花样作死]

(2)MOESI

MOESI在MESI的基础上增加了Owned拥有状态,表示一个块由该缓存拥有并和其他缓存共享该块,并且主存中该块已经过时

MOESI针对的情形是Cache-to-Cache的共享,即缺失时不向主存中索要副本而是在其他Cache中寻求副本(思想是Cache访问快于主存访问)

那么在MOESI中,尝试共享缓存A中已修改的块时不会将该块写回,A标记其为拥有,尝试获取该块共享的缓存从A中获取缓存副本,并标记为共享(只有A中标记为拥有);那么以后都需要保持这种行为,即发生缺失时,拥有某块的缓存必须主动提供拥有块的副本;拥有块被替换时再写入主存


7.3 分布式共享存储器体系结构和目录一致性协议

DSM中不采用监听一致性协议,是因为:

  • 总线可扩放性有限:处理器数目增多时竞争共享总线使用,易达到监听带宽瓶颈
  • 非总线或环的网络上监听困难:必须广播一致性通知,复杂拓扑的网络上带宽占用高并且低效

由此引入另一种一致性协议:目录一致性协议,目录也是分布式的位于各个节点中,和节点的存储器一一对应,即存储器中每块的状态记录在目录中;布式目录寻址和分布式存储器寻址相同,在DSM中各目录共用同一地址空间

目录一致性协议有三种状态:

  • 共享:一个或多个节点缓存该块,存储器中该块是最新的(目录还需要记录哪些节点共享该块)
  • 未缓存:所有节点都没有该缓存块副本
  • 已修改:只有一个节点拥有这个缓存块的副本,且已经对该块做了写操作,存储器中该块已过期(目录还需要记录哪个节点修改了该块)

因此目录中不仅要记录存储器块的缓存状态,还要用一个位向量来记录共享/修改的节点

定义三种节点类型:

  • 本地节点:发出请求的节点
  • 远程节点:非本地节点的其他节点
  • 主节点:目标缓存块存储器的位置和目录所在位置

弄懂几类节点间的关系就很容易理解目录一致性协议:

  • 主节点可能是本地节点,也可能是远程节点
  • 目标缓存块有可能能从主节点中获取,也有可能从其他节点获取
  • 本地节点发现缓存缺失时,查询主节点的目录,得知缓存块状态以及记录共享/修改的节点:主节点目录中显示是共享状态且读失效,则向本地节点发送缓存块副本并在共享节点记录中增加该节点;主节点目录中显示是共享状态且写失效,则向本地节点发送缓存块副本并在通知共享节点记录中所有节点该缓存块失效,最后标记为已修改;主节点目录中显示是未缓存状态,则根据本地节点缺失类型(写或读)标记为已修改或共享并记录节点号;主节点目录中显示是已修改状态,则向修改了缓存块中的节点发送一条消息,让它写回已修改的缓存块后再向本地节点提供该块副本

最后也在表中给出目录一致性协议的完整状态转换和相应动作:

[记P为发出请求节点编号、A为所请求的地址、D为所请求的数据]

消息类型 来源 目标 消息内容 消息功能
读缺失 本地缓存 主目录 P,A 节点P在地址A发生读缺失,请求数据并将P加入共享节点列表
写缺失 本地缓存 主目录 P,A 节点P在地址A发生写缺失,请求数据并将P记录为独占节点,然后主目录发送失效
失效 本地缓存 主目录 A 主目录向所有缓存了A的节点(远程缓存)发送失效
失效 主目录 远程缓存 A A处共享副本失效
取数据 主目录 远程缓存 A 取回地址A的块,发送到主目录,并标记为共享
取数据失效 主目录 远程缓存 A 取回地址A的块,发送到主目录,并标记为失效
数据应答 主目录 本地缓存 D 从主节点返回数据值
数据写回 远程缓存 主目录 A,D 写回地址A的数据值

7.4 同步

同步问题最主要的一些概念:

  • 原子操作
  • 临界区
  • 互斥锁
  • 信号量
  • 死锁
  • 同步障

这些概念《操作系统》课程中的基本概念,这里就不再复习了


7.5 存储同一性

存储同一性(也叫连贯性)指的是:在多个处理器对不同存储单元并发读写操作时,每个进程看到的这些操作被完成的序的一种约定

存储一致性是保证的是当对共享存储空间中的某一单元修改后,对所有读取者是可见的,它不涉及:

  • 什么时候让写入数据成为可见的
  • 处理器P1和P2对不同地址单元的访问顺序
  • P2对不同存储单元的读操作相对于P1所见到的顺序

顺序同一性模型要求所有处理器读写操作串行执行所形成的全局存储器访问次序必须符合原有程序的顺序,即无论指令流如何交替执行,全局次序必须保证所有程序局部次序

顺序同一性的充分条件:

  1. 每个进程按照程序执行序发出存储操作
  2. 发出写操作后进程要等待写操作完成后才能发出下一个操作
  3. 发出读操作后进程不仅要等待读完成,还要等待产生所读数据的那个写操作完成,才能发出下一个操作

注:这一块看的不是很懂,举例将以后补充

时间: 06-20

体系结构复习4——线程级并行的相关文章

体系结构复习3——数据级并行

体系结构复习 CH6 数据级并行 6.1 数据级并行DLP和SIMD 数据级并行(Data Level Parallel,DLP)是指处理器能够同时处理多条数据,属于SIMD模型,即单指令流多数据流模型 继续挖掘传统ILP的缺陷: 提高流水线时钟频率可能导致CPI增加 每个时钟周期很难预取和译码多条指令 大型科学计算.媒体流处理局部性较差,Cache命中率低 并且SIMD模型有以下优点: SIMD可有效挖掘DLP,如矩阵运算.图像声音等多媒体数据处理 SIMD比MIMD更节能,对于一组数据相同操

体系结构复习5——仓库级计算机的并行

体系结构复习 CH8 仓库级计算机的并行 注:本章不做重点要求,简略复习 8.1 仓库级计算机 8.1.1 仓库级计算机WSC 一般把作为商用因特网基础的超大型规模的集群称做仓库级计算机(WSC),WSC的建设主要关心: 成本和性能 能耗效率 可靠性(冗余备份) 网络I/O 工作负载平衡 并?性 运?成本 规模 计算WSC的可靠性(通过软件冗余来屏蔽停用次数): availability =全年宕机时间全年时间=软件故障次数×软件系统重启时间+硬件故障次数×硬件系统修复时间全年时间 8.1.2

体系结构复习1——指令级并行(循环展开和Tomasulo算法)

体系结构复习 CH5 指令级并行 5.1 指令级并行概念 5.1.1 指令级并行 指令级并行(ILP)指通过通过流水线等技术实现多条指令同时并行执行的并行技术 实现ILP主要的方法有: 依靠硬件动态发现和开发并行 依靠软件在编译时静态发现并行 5.1.2 指令间相关性 指令间的相关性限制了指令级的并行度,相关性主要分为(真)数据相关.名称相关和控制相关 (1)数据相关 指令i位于指令j的前面,下面两种情况下称指令j数据相关于指令i: 指令i生成的结果可能会被指令j用到 指令j数据相关于指令k,而

体系结构复习2——指令级并行(分支预測和VLIW)

第五章内容较多,接体系结构复习1 5.4 基于硬件猜測的指令级并行 动态分支预測是在程序运行时.依据转移的历史信息等动态确定预測分支方向.主要方法有: 基于BPB(Branch Prediction Buffer)和BHT(Branch History Table)的方法 高性能指令发送(High Performance Instruction Delivery) 5.4.1 基于BPB和BHT的方法 (1)1-bit BHT 分支指令PC的低位索引1位记录上一次转移是否成功(不是预測是否正确)

体系结构复习2——指令级并行(分支预测和VLIW)

第五章内容较多,接体系结构复习1 5.4 基于硬件推测的指令级并行 动态分支预测是在程序运行时,根据转移的历史信息等动态确定预测分支方向,主要方法有: 基于BPB(Branch Prediction Buffer)和BHT(Branch History Table)的方法 高性能指令发送(High Performance Instruction Delivery) 5.4.1 基于BPB和BHT的方法 (1)1-bit BHT 分支指令PC的低位索引1位记录上一次转移是否成功(不是预测是否正确)

JavaSE中线程与并行API框架学习笔记——线程为什么会不安全?

前言:休整一个多月之后,终于开始投简历了.这段时间休息了一阵子,又病了几天,真正用来复习准备的时间其实并不多.说实话,心里不是非常有底气. 这可能是学生时代遗留的思维惯性--总想着做好万全准备才去做事.当然,在学校里考试之前当然要把所有内容学一遍和复习一遍.但是,到了社会里做事,很多时候都是边做边学.应聘如此,工作如此,很多的挑战都是如此.没办法,硬着头皮上吧. 3.5 线程的分组管理 在实际的开发过程当中,可能会有多个线程同时存在,这对批量处理有了需求.这就有点像用迅雷下载电视剧,假设你在同时

python threading --- 基于线程的并行

threading --- 基于线程的并行 这个模块在较低级的模块 _thread 基础上建立较高级的线程接口. 这个模块定义了以下函数: threading.active_count() 返回当前存活的线程类 Thread 对象.返回的计数等于 enumerate() 返回的列表长度. threading.current_thread() 返回当前对应调用者的控制线程的 Thread 对象.如果调用者的控制线程不是利用 threading 创建,会返回一个功能受限的虚拟线程对象. thread

javaSE复习之——线程

线程其实就是程序执行的一条路径,一个进程中可以包含多条线程,多线程并发执行可以提高程序效率,可以同使完成多项任务 多线程的应用场景 迅雷多线程一起下载 服务器同时处理多个客户请求 多线程原理(单核CPU) 在电脑上运行多个程序时,其实cpu一次只能做一个事,做一段时间后然后换另一个另一个做一段时间,只是cpu的速度太快了,看起来就是同时做很多事,也就是说多线程其实只是表面上的多线程,底层cpu还是一次只能做一个事,但是这有个前提,那就是那个cpu是单核cpu,如果事多核cpu,那么就可以真正的达

游戏中逻辑线程和逻辑线程的并行

为什么要将游戏的渲染线程和逻辑线程分离? 游戏中渲染是一个非常耗时的操作,特别是相对复杂的游戏,渲染通常会占据一帧中的大部分时间.而高品质的游戏都会要求FPS在60,所以一帧的时间仅仅16毫秒. 如果要在16毫秒内完成逻辑和渲染双重的任务,对于大型游戏来说,通常是艰难的,即使在极度优化的情况下,也可能只能满足性能较好的设备,在性能较差的设备上,几乎不可能在16毫秒内完成所有任务. 所以如果将渲染线程和逻辑线程分离,那么理论上,他们各自都有16毫秒的时间来完成各自的任务,因为他们是并行进行的,这样