ch6

Size: px

Start display at page:

Download "ch6"

用钮
5 years ago
Views:

1 Chapter four Multiprocessors and Thread-Level Parallelism ( 续 1) 陈文智 2014/12/15 1

2 4.2.2 Basic schemes for Enforcing Coherence 一多处理器 cache 的作用 1. 作用 Caching, 即在相关处理器的 Caches 中保留共享数据的 copy 因此多处理器的 Cache 应提供两种功能 : 共享数据的迁移 (migration): 通过 move shared data to local cache, 并且 use the shared data in local cache, 来达到降低访问共享数据的 latency 共享数据的复制 (replication): 指一旦某数据在某一 Cache 被改写后, 应及时将改写值复制到其它 Cache 中去保证多个处理器可同时读出共享数据达到降低 latency( 远程调用 ) 和减少对共享数据的竞争 2014/12/15 2

3 2. 实现思路在小规模多处理器系统中, 采用硬件解决方法, 而不是软件方法 ; 引进维护 Cache coherence 的协议, 称为 cachecoherence protocol 实现 cache-coherence protocol 的关键是 : 跟踪共享数据块的状态存在两类 protocols, 对应两种不同的跟踪共享状态的技术 : 基于目录的技术和监听技术 2014/12/15 3

4 二两类一致性协议 1. Directory based( 基于目录 ) 把物理存储器中数据块的共享状态放在一个称为目录的结构之中 2. Snooping( 监听 ) 数据块的共享状态分散保留在每一拥有该数据块 copy 的 Cache 中, 即不存在集中保留共享状态的结构由于 Cache 通常是与共享存储器总线相连接, 所有 Cache 控制器监控 (monitor)or 监听 (snoop) 总线, 去发现它们 (cache) 是否拥有总线请求的数据块 2014/12/15 4

5 2014/12/15 5

6 Cache controller Bus snooping Address tag Snooping protocol 在采用微处理器 +Cache 的共享存储多处理器系统中日益受到欢迎因为协议可利用已存在的物理连接 (bus to memory) 达到查询 Cache 状态的目的 2014/12/15 6

7 4.2.3 两种监听协议 1. Write invalidate protocol( 写时无效协议 ) 在进行写操作时, 该 item 在所有其它 Cache 中的 copies 均无效所以一旦写过某 item, 则所有处理器从其 cache 中读该 item 时均发生 miss( 因为已无效, 需从共享存储器中重新读出 ), 即需取最新写入的 copy 若两个处理器要同时写同一 item 时, 只有一个赢得写的权利 ( 以后再介绍, 如何决定输赢 ), 而另一个处理器必须得到该数据的新 copy 后再写, 因此这一 protocol 能强制性的实现写串行化 ( 思考 : 同一个处理器连续写的情况 ) 2014/12/15 7

8 例 : 回写 Cache 和写无效 snooping protocol Processor Activity CPU A Reads X CPU B Reads X CPU A writes A 1 to X CPU B Reads X Bus activity Cache miss for X Cache miss for X Invalidation for X Cache miss for X Contents of CPU A s cache Contents of CPU B s cache Contents of Memory Location X /12/15 8

9 两种监听协议 (2) 2. Write update or write broadcast protocol( 写时更新或写广播协议 ) 当某 item 被写后, 该数据的所有 copies 均同时更新为保证不超出存储器访问带宽, 必须辨识被写的数据是否是共享数据, 只有那些共享数据被写后才需广播, 改写其需所有 copies, 否则就没有必要这样做 2014/12/15 9

10 例 : 回写 cache 和写时更新监听协议 Processor Activity CPU A Reads X CPU B Reads X CPU A writes A 1 to X CPU B Reads X Bus activity Cache miss for X Cache miss for X Write broadcast Of X Contents of CPU A s cache Contents of CPU B s cache Contents of Memory Location X /12/15 10

11 三两种协议性能的定性分析对同一字的多次写操作, 多次写广播 ;( 写更新 ) 只要一次无效化操作 ;( 写无效 ) ( 思考 : 为什么不是多次无效化操作?) Cache 数据块由多字组成的话, 对块中每一字进行写操作 : 每次都要写广播 ;( 写更新 )(write merge) 只在第一次写块中任一字时, 需要产生一无效信号 ; ( 写无效 ) 从一个处理器写数到另一处理器读出写入的数的延时 : 写广播完成后, 读命中 ; 写无效化, 读失配,stall 直到得到返回值 2014/12/15 11

12 两种监听协议的比较 : 两种方法自提出以来已有 10 年时间, 目前写无效比写更新更为普及由两种协议性能的定性分析可知, 写无效协议对 bus 和 memory 的带宽要求较低, 因此成为几乎所有实现技术的选择在后面主要讨论写无效协议 2014/12/15 12

13 4.2.4 基本实现技术一实现写无效协议的关键是利用总线完成无效化 1. 如何实现无效化监听协议处理器请求总线访问 ; 处理器向总线广播将被无效的数据的地址 ; 所有 Cache 控制器不断监听 (snooping) 总线, 察看总线上的地址是否与其 cache 中的地址相符若相符, 则 cache 中该数据被无效化总线访问的顺序性 ( 只有先取得总线访问权限的处理器才有权访问总线 ) 2014/12/15 13

14 基本实现技术 (2) 2. 如何保证写操作的顺序性因为两个处理器竞争同时写同一 location 的话, 只有其中一个可获得总线的访问权, 则另一处理器的 Cache 中的 copy 无效, 从而使写操作按顺序执行 2014/12/15 14

15 基本实现技术 (3) 3. 如何找到数据项最新 ( 最近 ) 的值? 即在哪一个 Cache 中? 对 write-through cache 很容易, 因为 Cache 和 memory 的内容总是一致的对 write-back cache 较复杂用 snoop 方法, 每一 Cache 控制器 snoops every address on the bus 若处理器找到它有一 dirty copy of the requested cache block, 该处理器就响应读的请求, 提供该 block 的最新值, 将该块写回存储器, 并终止存储器访问 2014/12/15 15

16 二如何实现 snooping? 1. 地址如何比较利用 Cache 地址的 tag 项, 即将 bus 上的地址与其 cache tags 比较 2. 如何实现无效化? 利用 Cache block 的 Valid bit 可方便地使该 block 无效化 3. 如何处理读 miss? 即找到该块的 dirty copy? 不管读 miss 是由无效化造成还是其他事件造成, 可通过 snooping 获得最新的 block 的值 2014/12/15 16

17 4. 如何处理写操作? 先区分是否是共享数据, 即知道将写的 block 是否也在其它 cache 中若无其它 cached copies,( 即为非共享数据 ), 则对 write-back cache 讲, 没有必要把写操作放到 bus 上, 从而达到节省时间, 又减轻带宽的负担 5. 如何跟踪一 cache block 是否是共享的? 在每一 block 上加一新的状态位来指示该 block 是否是共享的 ( 类似于 valid bit 或 dirty bit) 若写入的 block 处于共享状态, 则 cache 在写后要向 bus 送一无效信号, 并将该 block 标记为 private 然后 block 状态要改变 2014/12/15 17

18 2014/12/15 18

19 三如何减少由 bus 检查 cache-address tag 引起的对 CPU cache access 的干涉? 1. 复制 tags: 在同一 block 增加一个 tags 若 tags 复制以后, 则 CPU 和 snooping 的访问可并行进行 ; 2. 多级 Cache with inclusion property: Snooping activity 可对次级 Cache 进行, 而大多数 CPU activity 可对初级 Cache 进行由于大多数高级微处理器均采用多级 Cache 来降低对带宽的要求, 故这一方法已被大多数设计所采用, 有时还复制二级 Cache 的 tags 来进一步减少 CPU 和 snooping 的竞争 2014/12/15 19

20 2014/12/15 20

21 小结保证 Cache 一致性的写时无效协议, 意味着 : 必须对被写 Cache 块的其它拷贝进行无效化处理必须能在 Cache 失配时找到有效数据, 对直写 cache---- 总是到 memory 中去找最新值 ; 对回写 cache---- 采用监听方法, 所有 CPU 先比较地址, 再发现是否 dirty 是 dirty, 即最新的数据使用监听在总线上完成判断 : 不断监听总线上的地址不断检查是否与自己 cache 中地址相符合如果是, 则根据不同事件采取不同措施 2014/12/15 21

22 Name Write once Synapse N+1 Berkeley Illinois Firefly 五种 snooping protocols Protocol type Write invalidate Write invalidate Write invalidate Write invalidate Write broadcast Memory-write policy Write back after first write Write back Write back Write back Write back When private, Write through When shared Unique feature First snooping protocol described in literature Explicit state Where Memory is the owner Owned shared state Clean private State; Can supply data from any cache with a clean copy Memory updated on broadcast Machine using Synapse machine; first cache-coherence machines available Berkeley SPUR machine SGI Power and Challenge series No current machines; SPARCCenter 2000 closest 2014/12/15 22

23 4.2.5 An example protocol 一一致性机制的请求和操作 2014/12/15 23

24 CPU write Place write Miss on bus Cache state transitions based on requests 1. from CPU CPU read Place read miss on bus Invalid Shared Read only CPU read hit Exclusive Read/write CPU read miss Write-back block CPU write Place write miss on bus CPU write miss Write-back cache block Place write miss on bus CPU read hit CPU write hit CPU read miss Place read miss on bus 2014/12/15 24

25 Write miss for this block Write-back block; Abort memory access Cache state transitions based on requests 2. from the bus Invalid Write miss for this block Shared Read only Read miss for this block Write-back block; Abort memory access Exclusive Read/write 2014/12/15 25

26 Write miss for block write back block CPU write Place write Miss on bus 3. 两图合并之后的 Cache 块的状态图 Invalid Exclusive Read/write CPU read hit CPU write hit Write miss for this block CPU read Place read miss on bus Shared Read only CPU read hit CPU read miss Write-back block Place read miss on bus CPU read miss Place read read miss for block miss on bus Write-back block CPU write Place write miss on bus CPU write miss Write-back data Place write miss on bus 2014/12/15 26

27 Example P1 P2 Bus Memory step State Addr Value State Addr Value Action Proc. Addr Value Addr Value P1: Write 10 to A1 P1: P1: Read Read A1 A1 P2: Read A1 P2: Write 20 to A1 P2: Write 40 to A2 Assumes A1 and A2 map to same cache block, initial cache state is invalid 2014/12/15 27

28 Example: step 1 P1 P2 Bus Memory step State Addr Value State Addr Value Action Proc. Addr Value Addr Value P1: Write 10 to A1 Excl. A1 10 WrMs P1 A1 P1: P1: Read Read A1 A1 P2: Read A1 P2: Write 20 to A1 P2: Write 40 to A2 Assumes initial cache state is invalid and A1 and A2 map to same cache block, but A1!= A2. Remote Write Write Back Invalid Remote Write Read miss on bus Write miss on bus Remote Read Write Back Shared CPU Write Place Write Miss on Bus CPU Read hit Exclusive 2014/12/15 CPU read hit 28 CPU write hit

29 Example: step 2 P1 P2 Bus Memory step State Addr Value State Addr Value Action Proc. Addr Value Addr Value P1: Write 10 to A1 Excl. A1 10 WrMs P1 A1 P1: P1: Read Read A1 A1 Excl. A1 10 P2: Read A1 P2: Write 20 to A1 P2: Write 40 to A2 Remote Write Write Back Invalid Remote Write Read miss on bus Write miss on bus Remote Read Write Back Shared CPU Write Place Write Miss on Bus CPU Read hit Exclusive CPU Write Miss 2014/12/15 CPU read hit Write Back 29 CPU write hit

30 Example:step 3 P1 P2 Bus Memory step State Addr Value State Addr Value Action Proc. Addr Value Addr Value P1: Write 10 to A1 Excl. A1 10 WrMs P1 A1 P1: P1: Read Read A1 A1 Excl. A1 10 P2: Read A1 Shar. A1 RdMs P2 A1 Shar. A1 10 WrBk P1 A1 10 A1 10 Shar. A1 10 RdDa P2 A1 10 A1 10 P2: Write 20 to A1 P2: Write 40 to A2 Remote Write CPU Read hit Remote Write Write Back Invalid Read miss on bus Write miss on bus Remote Read Write Back Shared CPU Write Place Write Miss on Bus Exclusive 2014/12/15 CPU read hit CPU Write Miss CPU write hit Write Back 30

31 Example: step4 P1 P2 Bus Memory step State Addr Value State Addr Value Action Proc. Addr Value Addr Value P1: Write 10 to A1 Excl. A1 10 WrMs P1 A1 P1: P1: Read Read A1 A1 Excl. A1 10 P2: Read A1 Shar. A1 RdMs P2 A1 Shar. A1 10 WrBk P1 A1 10 A1 10 Shar. A1 10 RdDa P2 A1 10 A1 10 P2: Write 20 to A1 Inv. Excl. A1 20 WrMs P2 A1 A1 10 P2: Write 40 to A2 Remote Write CPU Read hit Remote Write Write Back Invalid Read miss on bus Write miss on bus Remote Read Write Back Shared CPU Write Place Write Miss on Bus Exclusive 2014/12/15 CPU read hit CPU write hit 31

32 Example:step 5 P1 P2 Bus Memory step State Addr Value State Addr Value Action Proc. Addr Value Addr Value P1: Write 10 to A1 Excl. A1 10 WrMs P1 A1 P1: P1: Read Read A1 A1 Excl. A1 10 P2: Read A1 Shar. A1 RdMs P2 A1 Shar. A1 10 WrBk P1 A1 10 A1 10 Shar. A1 10 RdDa P2 A1 10 A1 10 P2: Write 20 to A1 Inv. Excl. A1 20 WrMs P2 A1 A1 10 P2: Write 40 to A2 WrMs P2 A2 A1 10 Excl. A2 40 WrBk P2 A1 20 A1 20 Remote Write CPU Read hit Remote Write Write Back Invalid Read miss on bus Write miss on bus Remote Read Write Back Shared CPU Write Place Write Miss on Bus Exclusive 2014/12/15 CPU read hit CPU Write Miss CPU write hit Write Back 32

33 2014/12/15 33

34 2014/12/15 34

35 2014/12/15 35

36 4.3 Distributed shared-memory Architectures 分布式存储器结构一在这一体系结构下有两种结构无 Cache coherence 共享数据不进入缓存例子 :Cray T3D, 注意力集中在可缩放存储系统有 Cache coherence 2014/12/15 36

37 二无 Cache coherence(1) memory distributed among the nodes all nodes are interconnected by a network access can be either local or remote, 由 node 中的控制器根据地址决定数据是在本地存储器还是在远程存储器若需远程访问, 则发消息给远程存储器的控制器去访问数据 ; 这类系统是带 cache 的, 但为避免 coherence 问题, 将那些共享数据标记为 uncacheable, 只允许 private data 存放于 Cache 因为共享数据不会在 Cache, 所以远程访问只能按字, 而不能按 block 进行 2014/12/15 37

38 无 Cache coherence(2) 仍然可用软件显式地将共享数据放进 cache, 然后由软件来管理 coherence ( 通常,cache 是由硬件管理, 而不是由软件管理 ) 优点 : 不需要任何硬件缺点 : 不能实现基于 compiler 的透明的软件 cache coherence; 因为无 cache coherence, 丧失了取 single cache block 的优点, 也丧失了利用共享数据的空间局部性 ( 因为每次远程访问只能按字进行 ) 失去了 prefetch 等带来的 tolerating latency 机制 2014/12/15 38

39 根据上述分析, 小规模多处理器 ( 集中式存储 ) 比较容易支持 cache coherence; 对大规模多处理器体系结构 ( 分布式存储 ) 而言, 还存在其它挑战, 如缺乏监听 coherence 机制的缩放性问题 2014/12/15 39

40 三有 Cache coherence 关键 : 找到另一种不同于 snooping protocol 的 coherence protocol, 这就是 directory protocol 因为在分布存储器结构中, 不能采用总线作为仲裁, 而且处理器之间通信要采用显式的消息发送目录保存的信息每一可能存入 cache 的 block 的状态 : 包括共享 (shared) 未进入 cache(uncached) 独占的 (exclusive) 哪些 cache 拥有该 block 的 copies,block 是否 dirty 等等 2014/12/15 40

41 Directory protocol 实现方法目录的 entry 与存储器的 block 相联系的方法典型的基于目录协议的所含的信息量与各存储器中 block 数与处理器数的乘积成正比对于处理器个数小于 100 的机器, 这样的信息量还是可允许的, 但对于大规模多处理器而言, 必须设法减小目录的信息量常用减少信息量的方法 : 在目录里只放少数 block 的信息, 而不是针对存储器中所有的 block; 每一 entry 缩减 bits 数 2014/12/15 41

42 为了防止访问目录成为瓶颈, 目录的 entries 可分布存放在存储器上, 成为分布式目录每个目录负责跟踪拥有本节点存储器部分地址的 cache 2014/12/15 42

43 Memory Processor +cache I/O Memory Processor +cache I/O Memory Processor +cache I/O Directory Directory Interconnection network Directory Directory Directory Directory Memory I/O Memory I/O Memory I/O Processor +cache Processor +cache Processor +cache 2014/12/15 43

44 4.3.2 基于目录的 cache 一致性协议基础一基于目录协议的两种基本操作 : 处理读失配 ; 处理对共享的干净的 cache 块的写入实现关键 : 目录必须跟踪每一 cache 块的状态每一个处理器跟踪各自 cache 中每一数据块的状态必须跟踪保存了共享块拷贝的各处理器, 因为一旦某处理器对该共享数据写过一次后, 须对其它 copies 作无效处理 2014/12/15 44

45 二目录中 Cache 块可能的状态共享 (shared) 该块的 copies 存在于一个或多个 processor 的 caches 中 ; 未进入 Cache(uncached) 没有一个处理器将此块拷入其 cache 中 ; 独占 (exclusive) 只有一个处理器保存此块的拷贝, 并更新过数据, 于是内存中的数据已过时此处理器为此数据的拥有者 (owner) 2014/12/15 45

46 三如何表示共享 block 被哪一处理器共享? ( 其 copies 在哪些处理器的 Cache 中?) 1. 每一个 data block 设置一个 bit vectors bit vector 中的每一位表示一个对应的处理器, 将其 bit 置位表示该处理器共享该 block( 保存有该块的 copy), 可用该 bit vector 表示该 block 处于 exclusive 状态时的 owner 置位表示对应处理器拥有共享数据 2014/12/15 46

47 2. 目录协议的操作约定 ( 与监听技术相同的假设 ) 写入非独占数据时, 一定会导致 Cache 写失配, 且处理器将暂停直到一次访问结束 3. 基于目录的 Cache 一致性协议与 snooping 不同之处 : Snooping 把总线 ( 互连机制 ) 作为判断点, 起仲裁作用 Director 协议不能把互连网络作为判断点 Director 写是面向消息的,( 不象总线是面向事务的, 可采用中断方式 ), 所有消息必须明确应答 2014/12/15 47

48 四处理器与目录间传递消息的种类 2014/12/15 48

49 节点分类本地节点 (local node) 指产生访问请求的节点家节点 (home node) 指该节点拥有要访问地址的存储器单元和目录项 ( 即要访问的数据的家 ) 远程节点 (remote node) 指拥有要访问数据拷贝的节点 2014/12/15 49

50 Fetch invalidate Data write back 目录协议中的范例一目录协议的 Cache 中数据块状态转换图 CPU write Send write Miss message Invalidate CPU read hit Invalid CPU read Shared Send read miss message CPU read miss Date Write-back read miss Fetch Data write-back Read only CPU read miss Read miss Exclusive Read/write CPU read hit CPU write hit CPU write Send write miss message CPU write miss Data Write-back write miss 2014/12/15 50

51 Date write back Sharers={ } Write miss Data value reply, Sharers ={P} 二目录中数据块记录的状态转换图 Data value reply, Uncached Sharers={P} Read miss Shared Read only read miss Fetch;Date value reply, sharers+={p} Read miss Data value reply, Sharers+={P} Exclusive Read/write Write miss Invalidte; Shares={P}; data value reply write miss Fetch/Invalidate, data value reply, shares={p} 2014/12/15 51

52 Example Processor 1 Processor 2 Interconnect Directory Memory step P1: Write 10 to A1 P1 P2 Bus Directory Memory State Addr Value State Addr Value Action Proc. Addr Value Addr State {Procs} Value P1: Read A1 P2: Read A1 P2: Write 20 to A1 P2: Write 40 to A2 A1 and A2 map to the same cache block 2014/12/15 52

53 Example Processor 1 Processor 2 Interconnect Directory Memory P1 P2 Bus Directory Memory step State Addr Value State Addr Value Action Proc. Addr Value Addr State {Procs} Value P1: Write 10 to A1 WrMs P1 A1 A1 Ex {P1} Excl. A1 10 DaRp P1 A1 0 P1: Read A1 P2: Read A1 P2: Write 20 to A1 P2: Write 40 to A2 A1 and A2 map to the same cache block 2014/12/15 53

54 Example Processor 1 Processor 2 Interconnect Directory Memory P1 P2 Bus Directory Memory step State Addr Value State Addr Value Action Proc. Addr Value Addr State {Procs} Value P1: Write 10 to A1 WrMs P1 A1 A1 Ex {P1} Excl. A1 10 DaRp P1 A1 0 P1: Read A1 Excl. A1 10 P2: Read A1 P2: Write 20 to A1 P2: Write 40 to A2 A1 and A2 map to the same cache block 2014/12/15 54

55 Example Processor 1 Processor 2 Interconnect Directory Memory P1 P2 Bus Directory Memory step State Addr Value State Addr Value Action Proc. Addr Value Addr State {Procs} Value P1: Write 10 to A1 WrMs P1 A1 A1 Ex {P1} Excl. A1 10 DaRp P1 A1 0 P1: Read A1 Excl. A1 10 P2: Read A1 Shar. A1 RdMs P2 A1 Shar. A1 10 Ftch P1 A1 10 A1 A1 10 Shar. A1 10 DaRp P2 A1 10 A1 Shar. P1,P2} 10 P2: Write 20 to A P2: Write 40 to A2 10 Write Back A1 and A2 map to the same cache block 2014/12/15 55

56 Example Processor 1 Processor 2 Interconnect Directory Memory P1 P2 Bus Directory Memory step State Addr Value State Addr Value Action Proc. Addr Value Addr State {Procs} Value P1: Write 10 to A1 WrMs P1 A1 A1 Ex {P1} Excl. A1 10 DaRp P1 A1 0 P1: Read A1 Excl. A1 10 P2: Read A1 Shar. A1 RdMs P2 A1 Shar. A1 10 Ftch P1 A1 10 A1 A1 10 Shar. A1 10 DaRp P2 A1 10 A1 Shar. P1,P2} 10 P2: Write 20 to A1 Excl. A1 20 WrMs P2 A1 10 Inv. Inval. P1 A1 A1 Excl. {P2} 10 P2: Write 40 to A2 10 A1 and A2 map to the same cache block 2014/12/15 56

57 Example Processor 1 Processor 2 Interconnect Directory Memory P1 P2 Bus Directory Memory step State Addr Value State Addr Value Action Proc. Addr Value Addr State {Procs} Value P1: Write 10 to A1 WrMs P1 A1 A1 Ex {P1} Excl. A1 10 DaRp P1 A1 0 P1: Read A1 Excl. A1 10 P2: Read A1 Shar. A1 RdMs P2 A1 Shar. A1 10 Ftch P1 A1 10 A1 A1 10 Shar. A1 10 DaRp P2 A1 10 A1 Shar. P1,P2} 10 P2: Write 20 to A1 Excl. A1 20 WrMs P2 A1 10 Inv. Inval. P1 A1 A1 Excl. {P2} 10 P2: Write 40 to A2 WrMs P2 A2 A2 Excl. {P2} 0 WrBk P2 A1 20 A1 Unca. {} 20 Excl. A2 40 DaRp P2 A2 0 A2 Excl. {P2} 0 A1 and A2 map to the same cache block 2014/12/15 57

58 Invalidate CPU write Invalid CPU WRITE MISS 发 invalidate Invalidate CPU read Place read miss on bus Shared Read only CPU read hit CPU read miss Write-back block Place read miss on bus CPU read miss Place read read miss for block miss on bus Write-back block Exclusive Read/write CPU read hit CPU write hit CPU write hit 发 Invalidate CPU write miss Write-back data Place write miss on bus 2014/12/15 58

Chapter #

Chapter # 第三章 TCP/IP 协议栈本章目标通过本章的学习, 您应该掌握以下内容 : 掌握 TCP/IP 分层模型掌握 IP 协议原理理解 OSI 和 TCP/IP 模型的区别和联系 TCP/IP 介绍主机主机 Internet TCP/IP 早期的协议族全球范围 TCP/IP 协议栈 7 6 5 4 3 应用层表示层会话层传输层网络层应用层主机到主机层 Internet 层 2 1 数据链路层