维基百科

Dragon协议

Dragon 协议[1]是一种用于多处理器系统的基于更新的缓存一致性协议。通过直接更新跨多个处理器的所有缓存值来执行写传播。基于更新的协议（例如 Dragon 协议）在写入缓存块之后由其他处理器进行多次读取时会高效执行，因为更新的缓存块很容易在与所有处理器关联的缓存中使用。

状态 编辑

每个缓存块都处于以下四种状态之一：Exclusive-clean、Shared clean 、Shared modified和Modify。

  • Exclusive-clean (E) ：这意味着该缓存块首先由当前处理器获取，并且此后没有被任何其他处理器访问过。
  • Shared clean (Sc) ：这意味着该缓存块肯定存在于多个处理器的缓存中，并且当前处理器不是最后一个写入该块的处理器。状态 E 和 Sc 由协议单独维护，以防止对未共享的缓存块的读写操作引发总线事务，从而减慢执行速度。这在单线程程序中很常见。
  • Shared modified (Sm) ：这意味着该块存在于多个处理器的缓存中，并且当前处理器是最后一个修改该块的处理器。因此，当前处理器被称为块的所有者。与失效协议不同，块不需要在主存储器中是最新的，而只需在处理器中是最新的。当缓存块被驱逐时，处理器负责更新主存。
  • Modify（M） ：这意味着只有一个处理器拥有该缓存块，并且它已经修改了从内存中引入的值。


对于任何给定的缓存对，给定缓存块的允许状态连同其他缓存状态的状态如下（按上述顺序缩写的状态）：

 E   Sc   Sm   M 
 E         
 Sc         
 Sm         
 M         

事务 编辑

有 4 个处理器事务和 2 个总线事务。

处理器读取 (PrRd) ：当处理器成功读取放置在其缓存中的某个缓存块时，就会发生这个事务。

处理器写入 (PrWr) ：当处理器完成对放置在其缓存中的某个缓存块的成功写入时，就会发生这个事务。这使得处理器成为最新更新缓存块的处理器。

处理器读取未命中 (PrRdMiss) ：当处理器无法从其缓存中读取缓存块并需要从内存或另一个缓存中获取块时，就会发生这个事务。

处理器写入未命中 (PrWrMiss) ：当处理器无法从其缓存中写入缓存块时，会发生这个事务，需要从内存或另一个缓存中获取块然后写入。这再次使处理器成为最新更新缓存块的处理器。

总线读取（BusRd） ：当处理器请求总线获取缓存块的最新值时，会发生这个事务，无论它来自主存储器还是另一个处理器的缓存。

刷新（Flush）：当处理器将整个缓存块放在总线上时会发生这个事务。这是为了反映处理器对主存中缓存块所做的更改。

总线更新（BusUpd） ：当一个处理器修改一个缓存块，而其他处理器需要更新它们各自的缓存块时，就会发生这个事务。这是写更新协议所独有的。与 Flush 操作相比，BusUpd 需要更短的时间，因为对缓存的写入比对内存的写入要快。另一点需要注意的是，缓存不能更新其缓存块的本地副本，然后请求总线发送总线更新事务。如果确实发生了这种情况，那么两个缓存可能会独立更新它们的本地副本，然后请求总线。然后他们会同时看到两个不遵循顺序一致性的写入。

还需要一条shared line来指示某个缓存块在多个缓存中是否可用。这是必需的，因为其中一个缓存可以驱逐该块而无需更新其他块。在某些情况下，shared line有助于减少内存和总线事务，其中块仅在一个高速缓存中可用，因此不需要总线更新。这种检测共享的专用线路在写更新协议（如Firefly 协议）中可以找到，并基于Futurebus （IEEE 标准 P896.1）等总线标准实现。 [2]

状态转换 编辑

 
Dragon 协议 - 处理器发起的事务

处理器发起的转换 编辑

根据缓存块的当前状态和处理器发起的事务，一个缓存块会经历以下状态转换之一：

  • 当发生处理器读取未命中 ( PrRdMiss ) 并且该缓存块未共享时，状态转换为Exclusive
  • 当发生处理器读取未命中 ( PrRdMiss ) 并且该缓存块被共享时，状态转换到状态Shared Clean
  • 当发生处理器写入未命中 ( PrWrMiss ) 并且该缓存块被共享时，状态转换为Shared Modified并且处理器成为所有者。
  • 当发生处理器写入未命中 ( PrWrMiss ) 且该缓存块未共享时，状态转换为Modified
  • 当处理器读取 ( PrRd ) 命中时，该缓存块的状态不会改变，并保留该值。这是因为它只是一个读取命令，它不会产生任何总线事务
  • 如果该缓存块处于Modified状态，并且处理器写入（ PrWr ）该块，则没有转换，因为该块未被共享。
  • 当该缓存块处于Shared Modified状态时，处理器写入 ( PrWr )，但shared line未激活，状态转换为Modified 。
  • 如果该缓存块在写入 ( PrWr ) 发生并且shared line被激活时处于Shared Modified状态，则会生成总线更新 ( BusUpd ) 以更新另一个缓存块。
  • 如果该缓存块在写入 ( PrWr ) 发生并且shared line被激活时处于Shared Clean状态，则会生成总线更新 ( BusUpd ) 以更新另一个缓存块并且状态更改为Shared Modified 。
  • 但是，如果该缓存块在写入 ( PrWr ) 发生时处于Shared Clean状态，但shared line未激活，则状态转换为Modified ，并且不会生成总线事务。
  • 当该块处于Exclusive状态，并且处理器向其写入（ PrWr ）时，它将更改为Modified状态。
 
Dragon 协议 - 总线发起的事务

总线发起的转换 编辑

根据缓存块的当前状态和总线发起的事务，一个缓存块会经历以下状态转换之一：

  • 如果该缓存块在Modified中，并且发出了总线读取 ( BusRd )，则发出Flush以更新主内存并且状态转换为Shared Modified ，因为该块现在位于多个缓存中。
  • 如果该缓存块处于Shared Modified状态，并且总线读取（ BusRd ），则发出Flush以更新主内存，并且状态保持不变。
  • 如果该缓存块处于Shared Modified状态，并且发出了总线更新 ( BusUpd ) 事务，则状态转换为Shared Clean ，所有缓存都会更新。
  • 如果该缓存块处于Shared Clean状态，并且它接收到总线读取 ( BusRd ) 或总线更新 ( BusUpd )，它会继续保持其状态，因为值仍然是共享的。但是，在更新的情况下，它将更新缓存块中的值。
  • 如果该缓存块处于Exclusive状态并且总线读取值 ( BusRd )，则状态将转换为 Shared Clean，因为该块不再仅驻留在一个缓存中

底层设计选择 编辑

消除共享修改状态（Sm） 编辑

缓存块处于 Sm 状态的处理器负责在缓存块被替换时更新内存。但是如果每当发生总线更新事务时就更新主存储器，则不需要单独的 Sm 和 Sc 状态，并且协议可以提供单个共享状态。但是，这会导致更多的内存事务[3] ，这可能会降低系统速度，尤其是当多个处理器写入同一个缓存块时。

广播更换Sc块 编辑

该协议允许在没有任何总线活动的情况下静默替换 Sc 状态的缓存块。如果进行广播以让其他缓存知道正在替换 Sc 块，则它们可以测试shared line并在没有其他共享者的情况下移动到状态 E。有一个处于状态 E 的块的好处是，如果该块稍后被写入，它会进入 M 状态，并且不需要生成总线更新事务。因此，以广播 Sc 块的替换为代价，我们能够避免总线更新事务。而且由于广播替换不是时间关键，如果不需要缓存来立即处理替换，则没有缺点。另一方面，如果缓存不立即处理更新，则可能导致无序更新。在这种情况下，三态更新协议（如Firefly协议）可能具有性能优势。

比较 编辑

Dragon vs 写无效协议 编辑

写无效协议是另一套缓存一致性协议，一旦一个缓存块被修改，其他缓存中相同块的其他值不会被更新，而是失效。 [4]写入无效协议在对同一缓存块有许多后续写入的情况下更有效，因为无效发生一次，并且避免了其他处理器的进一步总线事务。但是，在对一个块进行写入之后对同一块进行多次读取的情况下，写入更新协议更有效。由于我们在写入后会更新其他缓存值，因此它们可以立即访问数据。在这种情况下。写无效协议是非常不利的，因为每次在另一个缓存中修改一个缓存块时，其余缓存需要会遇到一致性未命中，并启动总线事务以读取新值。相比之下，写入更新协议有时会使块的值保持更新的时间超过必要的时间，这将导致其他类型的未命中（即冲突和容量未命中）的增加。

Dragon vs Firefly 协议 编辑

在Firefly的情况下，修改块的缓存到缓存传输也会同时写回主内存。但是，由于与高速缓存相比，对主存储器的访问要慢几个数量级，因此需要增加执行回写作为单独总线操作的复杂性。在任何情况下，它都会导致性能下降。 [5]在 Dragon 协议的情况下完全避免了这个问题，因为共享块根本不会写回内存。然而，这是以增加一个状态（Shared-modified）为代价的。

参考 编辑

  1. ^ Atkinson, Russell R.; McCreight, Edward M. The Dragon Processor. Proceedings of the Second International Conference on Architectural Support for Programming Languages and Operating Systems. ASPLOS II (Los Alamitos, CA, USA: IEEE Computer Society Press). 1987-01-01: 65–69. ISBN 978-0818608056. doi:10.1145/36206.36185 (不活跃 28 February 2022). 
  2. ^ Stenström, Per. A Survey of Cache Coherence Schemes for Multiprocessors. Computer. 1990-06-01, 23 (6): 12–24. ISSN 0018-9162. doi:10.1109/2.55497. 
  3. ^ Culler, David; Singh, Jaswinder Pal; Gupta, Anoop. Parallel Computer Architecture, 1st Edition | David Culler, Jaswinder Pal Singh, Anoop Gupta |. store.elsevier.com. 1999 [2016-10-24]. ISBN 9781558603431. （原始内容存档于2016-10-25）. 
  4. ^ Solihin, Yan. Fundamentals of Parallel Multicore Architecture. Chapman and Hall/CRC. 2015: 205–206, 231–232. ISBN 9781482211184. 
  5. ^ Archibald, James; Baer, Jean-Loup. Cache Coherence Protocols: Evaluation Using a Multiprocessor Simulation Model. ACM Trans. Comput. Syst. 1986-09-01, 4 (4): 273–298. ISSN 0734-2071. doi:10.1145/6513.6514. 

参见 编辑

取自“https://zh.wikipedia.org/w/index.php?title=Dragon协议&oldid=79529218”