32结点COMA协议设计

1．COMA简介

COMA是并行机结构体系中的一种，它的全称是Cache Only Memory Architecture，它是NUMA模型的一种特例，它利用各节点的高速缓存构成全局地址空间。COMA结构如图1所示。由图可以看出，COMA是由阶层BUS构成的，其中P指的是各个结点的Processor，M指的是各个结点的Memory，D指的是目录Directory。

COMA模型的各处理器结点中没有存储层次结构，全部的Memory组成了全局地址空间。而各个Memory由上层的目录Directory管理。Directory在结构上也是Memory，但其中存储的不是数据而是某一页内容的位置信息。

COMA的基本思想是，数据对象不应该静态地分配到一个物理存储器位置。数据应该向CC-NUMA中的cache层次上表现的那样，为了应答应用的访问模式，可以在无需操作系统的干预下，在整个存储器层次上动态移动或复制。COMA通过把每个处理结点的主存储器组织成存储cache(memory cache)来支持迁移和复制。同其它的cache一样，这些cache保证自动把处理器最近访问的数据迁移或复制到本地存储器中。如果命中率足够高的话，则利用cache方式来组织内存的开销较之于减少访问远程存储器次数而得来的好处相比是可以忽略不计的。

由于没有主结点的概念，在存储cache失效时，如何找到相应的数据对象是一个要处理的问题。在COMA中，这个问题是通过一个基于层次化目录的cache一致性策略来完成的。

图1  COMA结构

2．32节点COMA一致性协议

2.1．提案

层次化的目录组织成树结构，其中叶子为处理结点，而全部中间结点和根结点为目录存储器。一个结点的目录存储器包括所有的在其下面的子树所拥有的存储块的状态信息。如果目录结点接收到一个数据对象，则为其建立一个目录项并存在目录存储器中。当数据对象的最后一个副本从子树中去掉时，这个目录项被释放。这样的结构在其目录存储器中需要的目录项的数目只是在其下面子树中不相同的存储块的数目。每个目录项包含在其子树中相应块的状态以及当前结点的哪些子树有这块的副本。

2.2．方案设计

2.2.1．数据访问

当处理器P需要访问数据时首先查询上一级的D若所需的数据在D内有记录则根据指示找到相应的数据返回，若没有则查找上一级的D，若有则返回，否则查找最上面的D，找到数据并返回。

2.2.2．状态迁移

我们采用Cache一致性中的后写无效化协议，因此每页的状态可为以下六种状态中的一种：

I(Invalid)：无效(当某个Cache中不含有此页时标志为I)。

E(Exclusive)：其他位置不存在副本。

S(Shared)：在其他位置存在副本的可能。

R(Reading)：发出读请求后的等待状态。

W(Waiting)：发出其他Copy无效化的等待状态。

A(Answering)：正在回答其他Processor的读请求。

在上述的六个状态中，后三个状态Reading、Waiting、Answering都只是瞬间的状态。在这里定义了瞬间的状态是因为在有些动作是由一些个分离的动作组成的，在这些分离的动作进行的过程中，需要一些暂时的状态来表示。

系统中存在以下的一些动作：

B(Bus)：来自总线的。

P(Processor)：来自Processor的。

Data：数据的传输。

ACK：接到Invalid请求，并执行之后的确认。

Invalid：使除了本节点之外所有结点的这一页无效化。

(1)Invalid

当某节点的某页数据处于Invalid状态时，若Bus上有读请求或者写请求，则对此页没有影响，此页的Invalid状态不变。

当此节点需要对Invalid页进行读操作时，先向Bus发出读请求，同时此页的状态变为Reading，然后Bus在一级目录中寻找此页，假如一级目录中也不包括此页，则向二级目录中寻找，找到此页后，Bus选择其中一个结点来处理这个读请求。之后，Bus执行Data操作，将数据传输给此结点。此节点在收到被读数据时，将这一页的状态该变为Shared。

当此节点需要对Invalid页进行写操作时，将这个写操作分解为两个步骤：首先，先向Bus发出读请求，具体的过程与上一段所叙述的相同。收到被读数据之后，将这一页的状态改变为Shared；然后，向Bus发Invalid请求，同时将自己的状态改为Waiting，在收到Bus传来的无效化的ACK回复之后，将自己的状态改为Exclusive。此时，即可对数据进行写操作。

(2)Shared

当本节点的Processor有读请求时，对此页的状态没有影响，此页的状态依然为Shared。

当Bus上有读请求时，若Bus没有选中本节点对此读请求进行处理，则此页的状态依然为Shared；若Bus选中本节点对此读请求进行处理，则此页状态改变为Answering，然后将数据传送到Bus上，然后将本页状态变回到Shared。

当Bus上对Shared页有Invalid请求时(当某结点对某一页进行写时，并不向Bus发送写请求，而是经过分解后发送Invalid请求，因此Bus的Invalid请求就相当于Bus上的写请求)，此页的Shared状态改变为Invalid状态，然后向Bus发送ACK确认信息。

当本节点的Processor对Shared页有写请求时，向Bus发出Invalid请求，同时将自己的状态改为Waiting。在收到Bus传来的无效化的ACK回复之后，将自己的状态改为Exclusive状态。此时，即可对数据进行写操作。

(3)Exclusive

当本结点有读请求或者写请求时，对此页的状态没有影响，此页的状态依然为Exclusive。

当Bus上有读请求时，此页将自己的状态改变为Answering，然后将数据传送到Bus上，本页的状态改变为Shared。当Bus上有Invalid请求时（当某结点对Invalid页进行写时，并不向Bus发送写请求，而是经过分解后发送Invalid请求，因此Bus的Invalid请求就相当于Bus上的写请求），此页改变为Invalid状态，并发送Invalid的ACK回复到Bus上。

2.2.3 替换

首先，假如Cache中存在状态为Invalid页，则将此Invalid页替换为从Bus上读取的新页。因为Invalid页中的数据都是无效的，因此对于多个Invalid页中将哪一页替换出来，采取随机替换的原则。

假如Cache中不存在Invalid页，但存在Shared页，则将某一个Shared页替换为从Bus上读取的新页。对于存在多个Shared页的情况，则将本结点的Processor使用次数最少的Shared页替换出去。

假如Cache中不存在Invalid页和Shared页，则将某一个Exclusive页转移到其他节点的Cache中，然后将此Exclusive页替换为从Bus上读取的新页。对于存在多个Exclusive页的情况，同样将本结点的Processor使用次数最少的Exclusive页替换出去。

对于处于状态Reading，Waiting和Answering的页，不能用来替换新页。因此，当此Cache中不存在Invalid，Shared和Exclusive页时，此次读取Bus上的数据失败，稍后再重新进行相关的申请。

3．总结

应用于分布式共享存储器系统上的协议多半是基于写回策略的，即修改完某页的内容后，要么立即写回home memory要么等该页换出或者其他处理器需要时写回home memory。但是在COMA结构中，没有固定的memory，每个处理器的memory都当做Cache来使用。本文就根据COMA的特点，提出了一种基于目录的32个节点COMA并行机的一致性协议。该协议的目录存储空间开销不大，并能解决COMA中的特定问题，对于众多副本该从哪里读取以及系统的最后一个副本的换页问题都有了解决方法。

参考文献:

[1]D.PattersonandJ.L.Hennessy.Computer OrganizationandDesign:TheHardware/SoftwareInterface[M].MorganKaufmann.SanFrancisco.1994.

[2]潘国腾.CC-NUMA系统存储体系结构关键技术研究.长沙：国防科技大学，2007.3

[3]陈石坤.多核处理器中Cache一致性协议研究和实现.长沙：国防科技大学，2005.11