著录项信息
专利名称 | 分布式共享内存系统数据维护方法 |
申请号 | CN03109390.6 | 申请日期 | 2003-04-08 |
法律状态 | 授权 | 申报国家 | 中国 |
公开/公告日 | 2003-10-08 | 公开/公告号 | CN1447257 |
优先权 | 暂无 | 优先权号 | 暂无 |
主分类号 | G06F15/167 | IPC分类号 | G;0;6;F;1;5;/;1;6;7;;;G;0;6;F;1;3;/;1;4;;;G;0;6;F;1;2;/;1;2查看分类表>
|
申请人 | 威盛电子股份有限公司 | 申请人地址 | 台湾省台北
变更
专利地址、主体等相关变化,请及时变更,防止失效 |
权利人 | 威盛电子股份有限公司 | 当前权利人 | 威盛电子股份有限公司 |
发明人 | 陈维龙;曾纹郁;赖瑾 |
代理机构 | 隆天国际知识产权代理有限公司 | 代理人 | 潘培坤;楼仙英 |
摘要
本发明是关于一种分布式共享内存数据维护方法,应用于具有至少两个分布式共享内存节点的分布式共享内存系统内部,且任意一节点的一外部高速缓存可储存其它节点的一特定本地内存中的数据,该方法至少包括下列步骤:判断该外部高速缓存中所储存的特定本地内存中的数据,是否被任意一节点的一特定处理器所更改;当该特定本地内存中的数据被特定处理器更改时,判断该任意一节点的其它处理器是否可共享特定处理器更改特定本地内存中的数据后所产生的一最新数据;以及当其它处理器可共享最新数据时,由任意一节点内的一总线,直接向特定处理器索取最新数据。
1、一种分布式共享内存数据维护方法,应用于具有至少两个分布式共 享内存节点的分布式共享内存系统内部,且任意一节点的一外部高速缓存可 储存其它节点一特定本地内存中的数据,该方法至少包括下列步骤:
判断外部高速缓存中所储存的特定本地内存中的数据,是否被任意一节 点的一特定处理器所更改;
当特定本地内存中的数据被特定处理器更改时,判断任意一节点的其它 处理器是否可共享特定处理器更改特定本地内存中的数据后所产生的一最 新数据;
当其它处理器可共享最新数据时,由任意一节点内的一总线,直接向特 定处理器索取最新数据;以及
当其它处理器不可共享最新数据时,最新数据是提供给特定处理器专属 使用。
2、如权利要求1所述分布式共享内存数据维护方法,其特征在于该任 意一节点具有至少两个处理器,且至少两个处理器都电连接于总线。
3、如权利要求1所述分布式共享内存数据维护方法,其特征在于该总 线可为一系统总线。
4、如权利要求1所述分布式共享内存数据维护方法,其特征在于该任 意一节点具有一本地内存,电连接于任意一节点所具有的一内存控制芯片, 且本地内存可区分为多个本地内存,以储存多笔数据。
5、如权利要求4所述分布式共享内存数据维护方法,其特征在于该任 意一节点所具有的外部高速缓存电连接于任意一节点所具有的一DSM控制 器,该外部高速缓存可区分为多个外部高速缓存,以储存多笔其它节点所拥 有的本地内存中的数据。
6、如权利要求1所述分布式共享内存数据维护方法,其特征在于任意 两节点间的电连接路径可用一网络方式连接。
7、如权利要求6所述分布式共享内存数据维护方法,其特征在于该网 络的通讯协议可使用TCP/IP网络通讯协议。
8、如权利要求1所述分布式共享内存数据维护方法,其特征在于该最 新数据的存取状态,储存于一外部高速缓存储存区一致性对照表。
9、如权利要求8所述分布式共享内存数据维护方法,其特征在于还包 括下列步骤:
当该外部高速缓存中所储存的特定本地内存中的数据,被任意一节点中 的任意一处理器所更改或存取而使外部高速缓存储存区一致性对照表中相 对应的一第一存取状态转为一第二存取状态时,判断储存有特定本地内存中 的数据来源节点的任意一处理器,是否正使特定本地内存中的数据一本地内 存存取状态处于一过渡转换阶段;以及
当该特定本地内存中的数据正处于过渡转换阶段时,使第二存取状态恢 复为第一存取状态。
10、一种分布式共享内存数据维护方法,应用于具有至少两个分布式共 享内存节点的分布式共享内存系统内部,且任意一节点的一外部高速缓存可 储存其它节点的一特定本地内存中的数据,该方法至少包括下列步骤:
判断该外部高速缓存中所储存的特定本地内存中的数据存取状态,是否 为CLEAN状态;
当该特定本地内存中的数据的存取状态为CLEAN状态时,如果特定本 地内存中的数据被任意一节点的一特定处理器所更改,该特定本地内存中的 数据存取状态将由CLEAN状态转为DIRTY-SHARED状态或DIRTY-ONLY 状态中一种;
当该特定本地内存中的数据的存取状态为DIRTY-SHARED状态时,该 任意一节点的其它处理器可由任意一节点内的一总线,直接向特定处理器索 取最新数据;以及
当该特定本地内存中的数据的存取状态为DIRTY-ONLY状态时,该最 新数据是提供给特定处理器专属使用。
11、如权利要求10所述分布式共享内存数据维护方法,其特征在于该 任意一节点具有至少两个处理器,且至少两个处理器都电连接于总线。
12、如权利要求10所述分布式共享内存数据维护方法,其特征在于该 总线可为一系统总线。
13、如权利要求10所述分布式共享内存数据维护方法,其特征在于该 任意一节点具有一本地内存,电连接于任意一节点所具有的一内存控制芯 片,且该本地内存可区分为多个本地内存,以储存多笔数据。
14、如权利要求13所述分布式共享内存数据维护方法,其特征在于该 任意一节点所具有的外部高速缓存电连接于任意一节点所具有的一DSM控 制器,该外部高速缓存可区分为多个外部高速缓存,以储存多笔其它节点所 拥有的本地内存中的数据。
15、如权利要求10所述分布式共享内存数据维护方法,其特征在于任 意两节点间的电连接路径,可用一网络方式连接。
16、如权利要求15所述分布式共享内存数据维护方法,其特征在于该 网络的通讯协议可使用TCP/IP网络通讯协议。
17、如权利要求10所述分布式共享内存数据维护方法,其特征在于该 最新数据的存取状态,是储存于一外部高速缓存储存区一致性对照表。
18、如权利要求17所述分布式共享内存数据维护方法,其特征在于还 包括下列步骤:
当该外部高速缓存中所储存的特定本地内存中的数据,被该任意一节点 中的任意一处理器所更改或存取而使外部高速缓存储存区一致性对照表中 相对应的一第一存取状态转为一第二存取状态时,判断储存有特定本地内存 中的数据来源节点的任意一处理器,是否正使特定本地内存中的数据的一本 地内存存取状态处于一过渡转换阶段;以及
当该特定本地内存中的数据正处于过渡转换阶段时,使第二存取状态恢 复为第一存取状态。
19、如权利要求18所述分布式共享内存数据维护方法,其特征在于该 第一存取状态可为VOID状态,而第二存取状态可为IDLE状态。
20、如权利要求18所述分布式共享内存数据维护方法,其特征在于该 第一存取状态可为FRESH状态,而第二存取状态可为IDLE状态。
技术领域\n本发明涉及一种分布式共享内存(Distributed Shared Memory,DSM)系统 数据维护方法,特别涉及一种应用于具有外部高速缓存(或称为L3高速缓存) 的分布式共享内存系统的数据维护方法。\n背景技术\n随着渐渐接近处理器及存取速度的物理极限,用多个处理器来增强计算 机整体运算能力的做法,变得越来越有吸引力。其中,就以具有多个处理器 的并行处理结构而言,有两种系统较为普遍:一是紧密耦合(tightly coupled) 的并行处理系统;另一为松散耦合(loosely coupled)的并行处理系统。\n一个紧密耦合的并行处理系统包括有:多个CPU及一个可供所有CPU 存取的内存,这种结构可视为由单个CPU系统所自然扩展所致,故其比较 容易设计。但是,这种类型的并行处理系统存在一个很严重的瓶颈:即,通 过一条共享的总线而使多个CPU在其上进行存取动作,将会限制整体的系 统规模;而且,连接过多的CPU将增加了总线的负担。\n相反地,松散耦合并行处理系统则没有上述紧密耦合并行处理系统所衍 生的问题。松散耦合的并行处理系统是通过一个高速的网络来连接许多独立 的计算器而组成的系统。如果设计人员精心设计网络的拓扑结构,松散耦合 的并行处理系统往往可以比一个紧密耦合的并行处理系统更容易扩充规模, 其可包含更多数量的处理器。但是,这种系统的所有通讯,都必须同时在网 络上进行,故为达到一定的运作效率,整体结构的设计难度将较上述紧密耦 合并行处理系统高出许多。\n为克服上述两种并行处理系统的缺陷,一种新的分布式共享内存 (Distributed Shared Memory,DSM)系统即被提出。分布式共享内存系统可同 时兼有紧密耦合并行处理系统容易设计和松散耦合并行处理系统容易扩充 规模的优点。所以,从1980年代初开始,分布式共享内存系统就一直是很 活跃的研究领域,目前已有多个原型系统被实现。其中,以Cache Coherency Non-Uniform Memory Access(ccNUMA)方式所构成的分布式共享内存系统, 即是本发明的研究重点所在。\n图1为以ccNUMA方式所构成的分布式共享内存系统10的结构示例图。 其中,本发明所公开的分布式共享内存系统10,是以四个节点(包括一第一 ~第四节点11~14)为例,并通过一网络结构15而相互连结在一起。而且在 该第一~第四节点11~14内部都各包括有:至少一处理器(例如,包括两个 处理器111、112或121、122或131、132或141、142)、一可控制输入/输 出内存控制芯片(为图1中标示113、123、133、143)、一本地内存(为图1 中标示1131、1231、1331、1431)、一DSM控制器(为图1中标示114、124、 134、144)、一外部高速缓存(又称为L3高速缓存,且为图1中标示1141、 1241、1341、1441)、一系统总线(为图1中标示115、125、135、145)以及一 内部总线(为图1中标示116、126、136、146);其中,该本地内存1131、1231、 1331、1431各都可区分为多个本地内存(local memory line),以各自储存多笔 数据。另外,该外部高速缓存1141、1241、1341、1441亦都可区分为多个 外部高速缓存(cache memory line),以各自储存多笔外部高速缓存数据。当然, 任意一节点中的这些多笔外部高速缓存数据,为来自其它节点本地内存中的 数据,可节省该任意一节点存取其它节点本地内存中数据的时间。\n另外,每一个节点的DSM控制器114、124、134、144,都必须维护储 存其中的一内存储存区一致性(memory coherency)对照表(图未示出),以记录 各节点中每一本地内存内所有本地内存的状态,当任意一节点要读取某一本 地节点特定本地内存时,方可根据对照表中所记录的特定本地内存中的数据 状态,来决定读取动作如何进行,以确保读取正确数据。同时,每一个节点 的DSM控制器都必须维护一快取内存储存区一致性(cache memory coherency)对照表(图未示出),以记录各节点中每一外部高速缓存内所有外部 高速缓存的状态,当任意一节点要读取某一本地节点特定外部高速缓存时, 方可根据对照表中所记录的特定外部高速缓存中的数据状态,来决定读取动 作如何进行,以确保读取正确数据。\n图1中每一个节点的DSM控制器因都通过该网络结构15与其它节点的 DSM控制器相电连接,故各节点相互间通讯的数据传输格式通常选择诸如 TCP/IP之类的网络通讯协议作为彼此的沟通媒介。\n由于图1所示结构中使用到这些外部高速缓存1141、1241、1341、1441, 对于如何使任意一节点都能充分利用自身所具有的外部高速缓存的高速特 性,减少对系统总线115、125、135、145发出存取数据请求(request)的次数, 以节省系统总线115、125、135、145的运作负荷,正是本发明所要解决与 关心的重点所在。\n进一步讨论公知高速内存储存区一致性对照表中针对任意一特定外部 高速缓存中的数据存取状态可区分为六种状态,分别说明如下:\nCLEAN:表示该特定外部高速缓存中的数据是同时储存于一本地节点的 外部高速缓存以及一远程节点(或称为来源节点(home node))中,且该特定外 部高速缓存中的数据尚未被本地节点中的一特定处理器所更改;另外,该特 定处理器专属拥有该特定外部高速缓存中的数据。\nFRESH:表示拥有该特定外部高速缓存中数据的任意一节点(不论是属 于远程节点或来源节点),都未更改且不专属拥有该特定外部高速缓存中的数 据。\nDIRTY:表示该特定外部高速缓存中的数据是储存于该本地节点的外部 高速缓存中,并已被该本地节点中的一特定处理器所更改以及专属拥有,而 与位于来源节点内的同一笔原始数据不相同。\nVOID:表示该特定外部高速缓存中的数据已无效,原本其所储存于该 本地节点的外部高速缓存位置,可供写入其它新的外部高速缓存中的数据。\nIDLE:表示该本地节点的外部高速缓存中储存该特定外部高速缓存中的 数据的位置,正处于等待写入新的外部高速缓存中的数据的过渡状态。\nSTALE:表示该本地节点的外部高速缓存中储存该特定外部高速缓存中 的数据,正处于等待被删除的过渡状态。\n公知的高速内存储存区一致性对照表中的存取状态所引发的缺陷为:在 DIRTY状态下,同属于该本地节点中的其它处理器如要使用该特定外部高速 缓存中的数据,因为此时该特定外部高速缓存中的数据已被该本地节点中的 一特定处理器所专属拥有,故其它处理器只能再次发出系统总线请求,以向 位于同一节点内拥有该特定外部高速缓存中的数据的特定处理器索取数据, 如此一来,显将增加节点内部系统总线的工作负荷,进而降低系统的运作效 率。\n另外,目前任意两节点间平行处理数据的存取死锁(dead lock)问题,是 由操作系统(O.S.)来解决。然而,一旦操作系统发生不稳定或其它因素而未 能及时处理该项存取死锁的状况,即会有导致该分布式共享内存系统10当 机,如此一来,显将降低该分布式共享内存系统10运作的可靠度。\n本发明的主要目的,即在提供一种新的外部高速缓存存取状态分类,以 减少发出系统总线请求次数的分布式共享内存系统数据维护方法。\n本发明的另一目的,即在提供一种新的外部高速缓存存取状态分类,以 解决平行处理数据存取死锁(dead lock)问题的分布式共享内存系统的数据维 护方法。\n发明内容\n本发明所要解决的技术问题为提供一种分布式共享内存数据维护方法, 应用于具有至少两个分布式共享内存节点的分布式共享内存系统内部,且任 意一节点的一外部高速缓存可储存其它节点的一特定本地内存中的数据,该 方法至少包括下列步骤:判断该外部高速缓存中所储存的特定本地内存中的 数据,是否被该任意一节点的一特定处理器所更改;当该特定本地内存中的 数据被该特定处理器更改时,判断该任意一节点的其它处理器是否可共享特 定处理器更改该特定本地内存中的数据后所产生的一最新数据;以及当其它 处理器可共享该最新数据时,由该任意一节点内的一总线,直接向特定处理 器索取最新数据。\n根据本发明上述构想,其中该任意一节点具有至少两个处理器,且至少 两个处理器都电连接于该总线。\n根据本发明上述构想,其中该总线可为一系统总线。\n根据本发明上述构想,其中该任意一节点具有一本地内存,电连接于任 意一节点所具有的一内存控制芯片,且本地内存可区分为多个本地内存,以 储存多笔数据。\n根据本发明上述构想,其中该任意一节点所具有的外部高速缓存电连接 于任意一节点所具有的一DSM控制器,该外部高速缓存可区分为多个外部 高速缓存,以储存多笔其它节点所拥有的本地内存中的数据。\n根据本发明上述构想,其中任意两节点间的电连接路径,可用一网络方 式连接。\n根据本发明上述构想,其中该网络通讯协议可使用TCP/IP网络通讯协 议。\n根据本发明上述构想,其中还包括下列步骤:当其它处理器不可共享最 新数据时,该最新数据可提供给特定处理器专属使用。\n根据本发明上述构想,其中该最新数据的存取状态,可储存于一外部高 速缓存储存区一致性(cache memory coherency)对照表。\n根据本发明上述构想,其中还包括下列步骤:当该外部高速缓存中所储 存的特定本地内存中的数据,被任意一节点中的任意一处理器所更改或存取 而使该外部高速缓存储存区一致性对照表中相对应的一第一存取状态转为 一第二存取状态时,判断储存有该特定本地内存中的数据来源节点的任意一 处理器,是否正使该特定本地内存中的数据的一本地内存存取状态处于一过 渡转换阶段;以及当该特定本地内存中的数据正处于过渡转换阶段时,使该 第二存取状态恢复为第一存取状态。\n关于本发明的另一较佳实施方式,也是应用于具有至少两个分布式共享 内存节点的分布式共享内存系统内部,且任意一节点的一外部高速缓存可储 存其它节点的一特定本地内存中的数据,该方法至少包括下列步骤:判断该 外部高速缓存中所储存的特定本地内存中的数据存取状态是否为CLEAN状 态;当该特定本地内存中的数据存取状态为CLEAN状态时,如该特定本地 内存中的数据被任意一节点的一特定处理器所更改,该特定本地内存中的数 据存取状态将由CLEAN状态转为DIRTY-SHARED状态或DIRTY-ONLY状 态中的一种;以及当该特定本地内存中的数据的存取状态为 DIRTY-SHARED状态时,该任意一节点的其它处理器可由任意一节点内的 一总线,直接向该特定处理器索取最新数据。\n根据本发明上述构想,其中该任意一节点具有至少两个处理器,且至少 两个处理器都电连接于总线。\n根据本发明上述构想,其中该总线可为一系统总线。\n根据本发明上述构想,其中该任意一节点具有一本地内存,电连接于该 任意一节点所具有的一内存控制芯片,且该本地内存可区分为多个本地内存 中,以储存多笔数据。\n根据本发明上述的构想,其中该任意一节点所具有的外部高速缓存电连 接于任意一节点所具有的一DSM控制器,该外部高速缓存可区分为多个外 部高速缓存,以储存多笔其它节点所拥有的本地内存中的数据。\n根据本发明上述构想,其中任意两节点间的电连接路径,可用一网络方 式连接。\n根据本发明上述构想,其中该网络的通讯协议可使用TCP/IP网络通讯 协议。\n根据本发明上述构想,其中还包括下列步骤:当该特定本地内存中的数 据存取状态为DIRTY-ONLY状态时,该最新数据可提供给特定处理器专属 使用。\n根据本发明上述构想,其中该最新数据存取状态,储存在一外部高速缓 存储存区一致性(cache memory coherency)对照表。\n根据本发明上述构想,其中还包括下列步骤:当该外部高速缓存中所储 存的特定本地内存中数据,被任意一节点中的任意一处理器所更改或存取而 使外部高速缓存储存区一致性对照表中相对应的一第一存取状态转为一第 二存取状态时,判断储存有特定本地内存中的数据的来源节点任意一处理 器,是否正使特定本地内存中数据的一本地内存存取状态处于一过渡转换阶 段;以及当特定本地内存中的数据正处于过渡转换阶段时,使第二存取状态 恢复为第一存取状态。\n根据本发明上述构想,其中该第一存取状态可为VOID状态,而第二存 取状态可为IDLE状态。\n根据本发明上述构想,其中该第一存取状态可为FRESH状态,而第二 存取状态可为IDLE状态。\n为使本发明的目的、构造特征及其功能有进一步的了解,配合附图详细 说明如下:\n附图说明\n图1为分布式共享内存系统结构示例图。\n图2为本发明中因响应本地存取指令而使外部高速缓存储存区一致性对 照表中所相对应的外部高速缓存中的数据存取状态产生变化的状态图。\n图3为本发明中因响应远程访问指令而使外部高速缓存储存区一致性对 照表中所相对应的外部高速缓存中的数据存取状态产生变化的状态图。\n图4为本发明中因响应本地存取指令、释放(Rollout)指令以及与释放指 令相关确认信号而分别使本地与外部高速缓存储存区一致性对照表中所相 对应的本地与外部高速缓存中的数据存取状态产生变化的状态图;\n图5是本发明一较佳实施例的流程示例图。\n具体实施方式\n基于公知高速内存储存区一致性对照表中针对任意一特定外部高速缓 存中的数据存取状态仅可区分为六种状态缺陷,本发明拟将增加为七种状 态,并分别说明如下:\nCLEAN:表示该特定外部高速缓存中的数据是同时储存于一本地节点的 外部高速缓存以及一远程节点(或称为来源节点(home node),且其为该特定 外部高速缓存中的数据的原始储存节点)中,且该特定外部高速缓存中的数据 尚未被该本地节点中的一特定处理器所更改;另外,该特定处理器专属拥有 特定外部高速缓存中的数据。\nFRESH:表示拥有该特定外部高速缓存中的数据任意一节点(不论是属 于本地节点或来源节点),都未更改且未专属拥有特定外部高速缓存中的数 据。\nDIRTY-ONLY:表示该特定外部高速缓存中的数据是储存于本地节点的 外部高速缓存中,并已被本地节点中的特定处理器所更改以及专属拥有,而 与位于来源节点内的同一笔原始数据不相同。\nDIRTY-SHARED:表示该特定外部高速缓存中的数据储存于本地节点的 外部高速缓存中,并已被该本地节点中的特定处理器所更改过,而与位于来 源节点内的同一笔原始数据不相同;且,该本地节点中的其它处理器也可存 取该份已更改过的数据。\nVOID:表示该特定外部高速缓存中的数据已无效,原本其所储存于本 地节点的外部高速缓存位置,可供写入其它新的外部高速缓存中的数据。\nIDLE:表示该本地节点的外部高速缓存中储存特定外部高速缓存中的数 据位置,正处于等待写入新的外部高速缓存中的数据过渡状态。\nSTALE:表示该本地节点的外部高速缓存中储存特定外部高速缓存中的 数据,正处于等待被删除过渡状态。\n显然地,由本发明所增加的DIRTY-SHARED状态,当可使位于同一节 点内的其它处理器,可直接存取同一节点内的某一处理器所更改过的数据, 以减少向图1中的系统总线115、125、135、145发出存取数据请求(request) 次数。\n当然,本发明上述七种存取状态会因响应由处理器所发出的本地存取指 令以及远程访问指令,而产生各种状态变化。以下先说明与本发明有关的各 种本地存取指令与远程访问指令种类,以及与该本地内存1131、1231、1331、 1431(请参阅图1所示者)的任意一本地内存中的数据有关并储存于储存区一 致性对照表中的存取状态种类。之后,再以图2~4所示的状态图(state diagram),进一步公开本发明所提出新的外部高速缓存存取状态的操作方式。\n首先,与本发明有关的本地存取指令种类有:\nBRL(local bus read line):代表一本地节点内部处理器所下达的本地读取 指令。\nBRL(hit#):代表一本地节点内部处理器所下达的本地读取指令,且该特 定外部高速缓存中的数据已储存于本地节点内部以及尚未被处理器更改。\nBRL(hitm#):代表一本地节点内部处理器所下达的本地读取指令,且该 特定外部高速缓存中的数据已储存于本地节点内部以及已被处理器更改。\nBRIL(local bus read invalidate line):代表一本地节点内部处理器所下达 的本地读取无效指令。\nBRIL(hit#):代表一本地节点内部处理器所下达的本地读取无效指令, 且该特定外部高速缓存中的数据已储存于本地节点内部以及尚未被处理器 更改。\nBRIL(hitm#):代表一本地节点内部处理器所下达的本地读取无效指令, 且该特定外部高速缓存中的数据已储存于本地节点内部以及已被处理器更 改。\nBIL(local bus invalidate line):代表一本地节点内部处理器所下达的本地 无效指令。\nBWL(local bus write line):代表本地节点内部处理器所下达的本地写入 指令。\n再则,与本发明有关远程访问指令的种类有:\nLRL(remote read line):代表一远程节点内部处理器所下达的远程读取指 令。\nLRIL(remote read invalidate line):代表一远程节点内部处理器所下达的 远程读取无效指令。\nLIL(remote invalidate line):代表一远程节点内部处理器所下达的远程无 效指令。\nRTY_BOP(BIL):代表一远程节点内部处理器所下达的退回前次存取状 态的退回指令;其可使一本地节点中因BIL指令所引起的外部高速缓存中的 数据存取状态,退回尚未产生BIL指令时的存取状态。\nRTY_BOP(BRL,BRIL):代表一远程节点内部处理器所下达的退回前次 存取状态的退回指令;其可使一本地节点中因BRL或BRIL指令所引起外部 高速缓存中的数据存取状态,退回尚未产生BRL或BRIL指令时的存取状态。\nROD(Rollout DIRTY):代表一本地节点内部处理器下达给一远程节点的 释放指令;其可使储存于本地节点内部且其存取状态已由CLEAN、 DIRTY-SHARED或DIRTY-ONLY状态转成STALE状态的外部高速缓存中 的数据,其位于远程节点(或称之为来源节点)内部的同一笔原始数据,由 GONE状态改为HOME状态。\nROF(Rollout FRESH):代表一本地节点内部处理器下达给一远程节点的 释放指令;其可使储存于本地节点内部且其存取状态已由FRESH状态转成 STALE状态的外部高速缓存中的数据,其位于远程节点(或称之为来源节点) 内部的同一笔原始数据,由SHARED状态改为HOME状态。\n另外,本发明中这些本地内存1131、1231、1331、1431中的任意一者(请 参阅图1所示者)的任意一本地内存中的数据,其存取状态种类分别说明如 下:\nHOME:代表没有任意何远程节点来读取本地内存中的数据,且本地内 存中的最新数据已经储存在一本地内存内。\nSHARED:代表已有其它远程节点已读取本地内存中的数据,且本地内 存中的数据尚未被更改。\nGONE:代表已有远程节点已读取本地内存中的数据,且本地内存中的 数据已被远程节点所更改。\nWASH:代表被更改过的本地内存中的数据由远程节点回传到本地节点 的过渡状态。\n图2为本发明中因响应本地存取指令而使外部高速缓存储存区一致性对 照表中所相对应的外部高速缓存中的数据存取状态产生变化的状态图。\n现再以图1中第一节点11为一本地节点,且第二节点12为一远程节点 为例,因响应上述这些本地存取指令后所可能产生的各种变化,配合图2所 示而对本发明的重点部分举例说明如下:\n假设有一特定本地内存中的数据储存于第二节点12的本地内存1231 中,第二节点12对于特定本地内存中的数据而言,即属于来源节点(home node)。因此,一旦该第一节点11中的任意一处理器向第二节点12索取特定 本地内存中的数据后,这份数据即会由网络结构15而被储存于外部高速缓 存1141内。此时这份数据对于第一节点11而言,即属于一特定外部高速缓 存中的数据。\n当第一节点11中的第二处理器112发出本地存取指令BRL至系统总线 115时,由于特定外部高速缓存中的数据已位于外部高速缓存1141,故属于 快取命中(cache hit)的情形(于图2中以BRL(hit#)表示),该特定外部高速缓存 中的数据即将被直接读至第二处理器112内部。至于特定外部高速缓存中的 数据存取状态,如果这份数据为第二处理器112所专属拥有时,其存取状态 将设为CLEAN状态。\n在CLEAN状态下,如果第二处理器112想要更改特定外部高速缓存中 的数据时,第二处理器112可发出本地存取指令BRIL至系统总线115,由 于特定外部高速缓存中的数据已位于外部高速缓存1141,故也属于快取命中 (cache hit)。然而,因第二处理器112会更改这份数据(于图2中以BRIL(hitm#) 表示),该特定外部高速缓存中的数据不但将被直接读至第二处理器112内供 其专属拥有这份数据,该特定外部高速缓存中的数据存取状态也将由 CLEAN状态转为DIRTY-ONLY状态。\n本发明与公知技术的差别在于,在CLEAN状态下,如果第二处理器112 想要更改特定外部高速缓存中的数据,但可与同一节点内的其它处理器(例 如,图1中所示的处理器111)共同分享这份数据时,第二处理器112可发出 本地存取指令BRL至系统总线115,由于特定外部高速缓存中的数据已位于 外部高速缓存1141,故也属于快取命中(cache hit)。然而,因第二处理器112 会更改这份数据(于图2中以BRIL(hitm#)表示),特定外部高速缓存中的数据 不但将被直接读至第二处理器112,特定外部高速缓存中的数据的存取状态 也将由CLEAN状态转为DIRTY-SHARED状态。如此一来,在处理器111 需要存取该份数据时,即不必再向系统总线115发出存取数据请求(request) 来要求该处理器112解除其专属拥有的限制,而可直接至外部高速缓存1141 中存取这份数据。这样做法显然将可有效降低系统总线115的运作负荷。\n至于图1中标示B_ACK(BRL)指特定外部高速缓存中的数据存取状态为 VOID时,因响应本地节点所产生的本地存取指令BRL而先被设为过渡状态: IDLE,一旦本地存取指令BRL被执行完毕后,即会因响应由本地节点所发 出的确认(Acknowledge)信号B_ACK而被设定为FRESH状态。同理,图1 中标示B_ACK(BRIL,BIL)之意义,系指该特定外部高速缓存中的数据之存 取状态为FRESH时,因响应本地节点所产生的本地存取指令BRIL或BIL 而先被设定为过渡状态:IDLE,一旦本地存取指令BRIL或BIL被执行完毕 后,即会因响应由本地节点所发出的确认信号B_ACK而被设为CLEAN状 态。当然,图1中标示B_ACK(BWL)指特定外部高速缓存中的数据存取状态 为CLEAN或DIRTY-ONLY时,因响应本地节点所产生的本地存取指令BWL 而先被设定为过渡状态:STALE,一旦本地存取指令BWL被执行完毕后, 即会因响应由本地节点所发出的确认信号B_ACK而被设为VOID状态。\n至于其它存取状态因响应不同本地存取指令所产生的状态变化,任意何 熟悉本技艺的人士参阅上述关于本发明的说明后,应都可知悉其中详细运作 原理,在此即不再以赘述。\n图3为本发明中因响应远程访问指令而使外部高速缓存储存区一致性对 照表中所相对应的外部高速缓存中的数据存取状态产生变化的状态图(state diagram)。\n本发明的另一重点所在为不必依靠操作系统(O.S.)而可直接解决任意两 节点间平行处理数据的存取死锁(dead lock)问题。此部份与图3中所示的退 回指令RTY_BOP(BIL)与RTY_BOP(BRL,BRIL)的运作情形密切相关。现 以图1中的第一节点11为一本地节点并发出本地存取指令BRL,且第二节 点12为一远程节点为例,辅以图3中因响应退回指令RTY_BOP后所产生 的变化举例说明如下:\n假设有一特定本地内存中的数据储存于第二节点12的本地内存1231 中,第二节点12对于特定本地内存中的数据而言,即属于来源节点(home node)。因此,一旦第一节点11中的任意一处理器向第二节点12索取特定本 地内存中的数据后,这份数据即会由网络结构15而被储存于外部高速缓存 1141内。此时这份数据对于第一节点11而言,即属于一特定外部高速缓存 中的数据。\n再则,如果被储存于外部高速缓存1141内的这份数据存取状态被设定 为VOID,表示特定外部高速缓存中的数据已无效,原本其所储存于第一节 点11的外部高速缓存1141位置,即可供写入其它新的外部高速缓存中的数 据。\n接下来,一旦第一节点11中的处理器111或112向系统总线115发出 本地存取指令BRL要读取特定外部高速缓存中的数据时,因特定外部高速 缓存中的数据已被设定为VOID表示无效,故第一节点11即需再一次向第 二节点12中的本地内存1231索取特定外部高速缓存中的原始数据,并予以 填入原本储存于外部高速缓存1141内部的位置。因此,此时特定外部高速 缓存中的数据的存取状态可由VOID状态转变成IDLE状态。\n如果此时本地内存1231中的这份同一笔原始数据,正被第二节点12中 的处理器121或122进行存取而处于一过渡状态(例如,处于一WASH状态) 时,第二节点12即会发出退回RTY BOP指令给第一节点11,以告知这份 原始数据尚不能从第二节点12被传送到第一节点11。第一节点11为了避免 一直处于等待状态,在接收到来自第二节点12所发出的退回RTY_BOP指 令后,即会将特定外部高速缓存中的数据存取状态由IDLE状态退回到原先 的VOID状态(即图3中标示RTY_BOP(BRL,BRIL)处的存取状态变化)。\n倘若面临第一、第二节点11、12同时要向对方节点索取数据,而这份 数据又正处于被对方节点使用的过渡状态时,第一、第二节点11、12将可 及时因响应对方节点所发出的退回指令,而使各自节点中数据的存取状态退 回到原先未改变前的存取状态,避免出现所谓存取死锁(dead lock)的问题。\n至于其它存取状态因响应不同远程访问指令所产生的状态变化,任意何 熟悉本技艺人士可参阅上述关于本发明说明后,应都可知悉其中详细运作原 理,在此即不再赘述。\n再进一步而论,现针对图3中确认L_ACK(ROD、ROF)信号的运作情形, 以图4说明如下:\n图4为本发明中因响应本地存取指令、远程访问指令中的释放(Rollout) 指令(即图3、4中所标示的ROD、ROF)以及与释放指令相关的确认信号而 分别使本地与外部高速缓存储存区一致性对照表中所相对应的本地与外部 高速缓存中的数据存取状态产生变化的状态图。假设图4中所标示的节点 B(例如,可视为图1中所示的远程节点:第二节点12)有一特定本地内存的 数据,已被图4中所标示的节点AA(例如,可视为图1中所示的本地节点: 第一节点11)所读取,则这份数据将被储存于外部高速缓存1141,且对于第 一节点11而言,其表示为一特定外部高速缓存中的数据。\n此时,如果希望执行将第一节点11(节点A)中特定外部高速缓存中的数 据释放(Rollout)回到第二节点12(节点B)的目的,则因响应特定外部高速缓 存中的数据所处的存取状态,以及位于来源节点中的同一笔原始数据存取状 态,将会有不同的状态变化。\n若在第一节点11(节点A)中特定外部高速缓存中的数据,其存取状态处 于CLEAN、DIRTY-SHARED或DIRTY-ONLY状态,而且第二节点12(节点 B)中的同一笔原始数据处于GONE状态时,第一节点11(节点A)因响应内部 的任意一处理器所发出的本地存取指令BIL或BRIL,即可使特定外部高速 缓存中的数据,其存取状态都改为STALE状态,以表示位于第一节点11(节 点A)中的特定外部高速缓存中的数据等待被删除。之后,第一节点11(节点 A)向该第二节点12(节点B)发出ROD释放指令,以将位于第一节点11(节点 A)中的特定外部高速缓存中的数据写回到第二节点12(节点B)。当然,位于 第二节点12(节点B)内部的同一笔原始数据,会因响应ROD释放指令,而 由GONE状态改为HOME状态。紧接着位于第一节点11(节点A)中的特定 外部高速缓存中的数据全部写回到第二节点12(节点B)后,第二节点12(节 点B)将向第一节点11(节点A)发出一确认信号L_ACK(即图4中标示 L_ACK(ROD)处存取状态的变化),以使位于第一节点11(节点A)中的特定外 部高速缓存中的数据存取状态,由STALE状态改为VOID状态,并表示使 特定外部高速缓存中的数据无效。此时,原先储存特定外部高速缓存中的数 据位置,可供写入新的外部高速缓存中的数据。\n同理,若在第一节点11(节点A)中的特定外部高速缓存中的数据,其存 取状态处于FRESH状态,而且第二节点12(节点B)中的同一笔原始数据处 于SHARED状态时,第一节点11(节点A)因响应内部的任意一处理器所发出 的本地存取指令BIL,即可使特定外部高速缓存中的数据,其存取状态改为 STALE状态,以表示位于第一节点11(节点A)中的特定外部高速缓存中的数 据等待被删除。之后,第一节点11(节点A)向第二节点12(节点B)发出ROF 释放指令,以表示第一节点11(节点A)要放弃内部的特定外部高速缓存中的 数据。当然,位于第二节点12(节点B)内部的同一笔原始数据,会因响应ROF 释放指令,而由GONE状态改为HOME状态。紧接着第二节点12(节点B) 收到ROF释放指令后,即会立刻向第一节点11(节点A)发出一确认信号 L_ACK(即图4中标示L_ACK(ROF)处存取状态的变化),以使位于第一节点 11(节点A)中的特定外部高速缓存中的数据存取状态,由STALE状态改为 VOID状态,并表示使特定外部高速缓存中的数据无效。此时,原先储存特 定外部高速缓存中的数据位置,可供写入新的外部高速缓存中的数据。\n图5是本发明一较佳实施例的流程示例图。首先,在步骤a开始。 在步骤b,判断任意一节点的一外部高速缓存中所储存的一特定本地内存 中的数据,是否被任意一节点的特定处理器所更改,如果是,则进行到 步骤c,判断该任意一节点的其它处理器是否可以共享特定处理器更改的 特定本地内存中的数据所产生的一最新数据;如果否,则处理结束。如 果在步骤c中判断为是,则进行到步骤d,该任意一节点的其他处理器可 由任意一节点内的一总线,直接向该特定处理器索取该最新数据;如果 判断为否,则进行到步骤e,该最新数据仅提供给该特定处理器专用。在 步骤d或步骤e之后,处理进行到步骤f,当该外部高速缓存中所储存的 特定本地内存中的数据,被该任意一节点中的任意一处理器所更改或存 取而使该外部高速缓存区一致性对照表中相对应的一第一存取状态转为 第二存取状态时,判断储存有该特定本地内存中的数据来源节点的任意 一处理器,是否正使该特定本地内存的数据的一本地内存存取状态处于 一过渡转换阶段;如果是,则处理进行到步骤g,使该第二存取状态恢复 为第一存取状态,然后处理结果;如果否,处理直接进行到结束。\n综上所述,本发明将任意一节点内外部高速缓存中的数据,其存取状态 种类增加一项:DIRTY-SHARED状态,即可有效降低系统总线的运作负荷; 同时,本发明也可在不大幅增加操作复杂度的情况下,解决存取死锁(dead lock)问题。
法律信息
- 2006-09-27
- 2003-12-17
- 2003-10-08
引用专利(该专利引用了哪些专利)
序号 | 公开(公告)号 | 公开(公告)日 | 申请日 | 专利名称 | 申请人 | 该专利没有引用任何外部专利数据! |
被引用专利(该专利被哪些专利引用)
序号 | 公开(公告)号 | 公开(公告)日 | 申请日 | 专利名称 | 申请人 | 1 | | 2007-09-11 | 2007-09-11 | | |