多核程序设计——缓存一致性协议MESI

MESI协议

    在MP系统中,每个CPU都有自己独立的cache,缓存之间的一致性很很容易受到破坏的,所以缓存一致性协议就应运而生了。MESI是一种使用非常广泛的缓存一致性协议。

    MESI存在”modified”,”exclusive”,”shared”和”invalid”四种状态,协议可以在一个指定的缓存中应用这四种状态。因此,协议在每一个缓存行中维护一个两位的状态”tag”,这个”tag”附着在缓存行的物理地址或者数据后。

  • 处于“ modified” 状态的缓存行是由于相应的 CPU 最近进行了内存存储。并且相应的内存确保没有在其他 CPU 的缓存中出现。下边的图有一些误导嫌疑,可以把“叉”看做是invalid状态。这些图是《大话处理器》作者的图,这里直接偷过来了。

modified

  • “exclusive”状态非常类似于“ modified” 状态,唯一的例外是缓存行还没有被相应的 CPU 修改,这表示缓存行中的数据及内存中的数据都是最新的。
    exclusive
  • 处于“ shared” 状态的缓存行可能被复制到至少一个其他 CPU 缓存中,这样在没有得到其他 CPU 的许可时,不能向缓存行存储数据。
    shared
  • 处于“ invalid” 状态的行是空的,换句话说,它没有保存任何有效数据。

MESI消息

     根据几幅图来看,MESI协议的各个状态是非常容易理解的。但事实上,MESI协议的核心却是MESI消息和状态转移。《Is parallel programming hard, …》中是把消息和状态转移分开讲的,我觉得不是特别直观,所以我把这两个混在一起了。如果CPUs在单个共享总线上,MESI协议一般有以下这些消息。

  • Read:当CPU在自己的cache中没有发现需要的物理地址,就会发送一条“READ”消息,该消息包括缓存行需要读的物理地址。

  • Read Response: 顾名思义,”Read Response”消息是回复“Read”消息的。“Read Response”消息是由内存或者其他CPU缓存提供的。如果其他缓存请求一个处于“modified”状态的数据,则本地缓存必须提供“Read Response”消息。这个很容易理解,别的CPU在请求本地缓存中的数据,而这份数据还没有刷新到内存,所以必须告诉其他CPU该数据的最新值。接收到”Read Response”消息后,该数据的缓存状态就由”invalid”变成了”share”或者”exclusive”,这取决于”Read Response”的提供者是内存还是其他CPU缓存。

  • Invalidate:“ invalidate” 消息包含要使无效的缓存行的物理地址。其他的缓存必须从它们的缓存中移除相应的数据并且响应此消息。当CPU要对一个变量进行写操作,而此变量处于只读状态(share),就需要发送“invalid”消息。由于一个变量被多个CPU缓存,所以单个CPU的改写会造成缓存不一致,所以在写之前必须告诉其他CPU你们缓存的值马上就要过时了。接受到”invalidate”消息的CPU就会把本地缓存中的对应数据无效掉。

  • Invalidate Acknowledge:一个接收到“invalidate”消息的 CPU必须在移除指定数据后响应一个“invalidate acknowledge”消息。这个消息就是告诉“invalidate”消息的提供者“我已经知道你要更改这个数据了,我放弃使用自己缓存中的拷贝!”

  • Read Invalidate:”read invalidate”消息包含要缓存行读取的物理地址。同时指示其他缓存移除数据。因此,它包含一个”read”和一个”invalidate”。“read invalidate”也需要“read response”以及”invalidate acknowledge”消息集。
         “Read Invalidate”消息的发送时机有两个:第一个是CPU对一个数据进行原子读写操作,但是该数据没有在本地CPU的缓存中,在其他CPU缓存中可能有该数据的拷贝。所以它需要发送一条“Read Invalidate”消息,它不仅需要读取该数据的最新值,还要无效掉其他的CPU缓存(它马上就要改写该数据)。

  • Writeback:“writeback”消息包含要回写到内存的地址和数据。这个消息允许缓存在必要时换出“modified”状态的数据以腾出空间。消息的发送时机是,CPU把本地缓存中的数据刷新到内存中,而该数据是share状态(只读),它需要告诉其他CPU”我不再使用这些缓存数据了”

MESI状态转移

有了前面的学习,MESI的状态转移也就不难理解了。MESI协议的状态转移图如下:
这里写图片描述
其中,a-l是状态转移路径。关于全部状态转移路径,我不准备详细记录了,《Is parallel programming hard…》中有详细的描述。这里我记录几条自己觉得不容易理解的。

  • Transition(e):这条路径从”share”状态通往”Modified”装态。这种状态转移的发生时机是CPU执行一条原子读写指令(如test_and_set或者exchg)。其实从本质上说,是不存在一条从S直接到M的状态转移的。原子读写指令的微指令逻辑依然是先读后写,写之前需要invalid其他的CPU缓存,所以先还是从S到E,然后开始改写,状态从E转移到M。但是,原子读写指令与load+store的区别在于它是原子性的,不能被分割,整个指令执行过程是事务性的,必须一次完成。因此,MESI协议中才会有这样一条状态转移。

  • Transition(h):h是从S到E的一条状态转移路径。该状态转移发生的时机有两个。第一个是:CPU马上要对一个数据进行写入操作,它首先要先invalidate其他的CPU缓存,所以它进入了E状态(其他CPU缓存中都不存在该数据)。另一个时机是接收到其他全部共享某数据的CPU发送的writeback消息,也即是说本地缓存是唯一缓存了,所它就是exclusive了。需要强调的东西是——要改写某数据,要先”拥有”它,即处于S状态其实是无法改写该数据的。

    在《深入理解并行编程V1.0》中,我觉得对Transition(h)部分的翻译是有误的。同时我也已经发现了不少其他错误,在以后的博文中会陆续写出来。

    Blog: intheworld

发表评论