一种基于同步哈密顿环的TriBA-cNoC死锁避免方法

一种基于同步哈密顿环的triba-cnoc死锁避免方法
技术领域
1.本发明涉及一种基于同步哈密顿环的triba-cnoc(基三内核间片上网络)众核处理器死锁避免方法，属于计算机众核处理器技术领域。


背景技术：

2.众核处理器是一种在单一晶片上实现的多节点/内核计算系统。虽然一般的多节点计算系统可以使用全互连避免通信死锁，但因片上资源有限，众核处理器不适于采用全互连方式，不得不采用各种方式的资源共享。由此，资源共享在基于片上网络(noc)的众核处理器中，会不可避免地引发通信死锁，而只有解决(避免或预防)死锁问题，众核处理器才可用。
3.死锁是一种僵局状态，当计算系统的多个(两个或以上)进程(或并发硬件模块)在竞争资源时，各进程都处于等待得到资源才能继续向前推进的状态，且如果没有外界干涉，则系统本身无法退出此状态，即计算系统发生死锁。死锁发生的4个必要条件包括：
4.互斥：一个资源每次只能被一个进程使用；
5.请求与保持：一个进程因请求资源而阻塞时，对已获资源保持不放；
6.不可剥夺：进程已获得的资源，在末使用完之前，不能强行剥夺；
7.循环等待：若干进程之间形成一种头尾相接的循环等待资源关系。
8.在基于片上网络的众核处理器中，因大量环形路径的存在和存储转发缓冲区的共享，不可避免地会产生通信死锁。图1为一种共享缓冲区导致死锁的示例，其中，数据沿着虚线所示环形路径传输，当路径上各节点的存储转发缓冲区耗尽时，每个节点都将面临等待前方节点出现空闲缓冲区接收数据的状态，于是前方节点和当前节点之间形成了依赖关系，且因为环路上的所有缓冲区都耗尽，导致这种依赖关系扩展到整个路径，从而形成死锁。
9.如果能够破坏发生死锁的必要条件，则计算系统就不会出现死锁。因此，采用某种技术手段，通过破坏系统中存在的上述某个或多个必要条件，使得系统不会发生死锁，这种方法称为死锁预防或预防死锁。由于上述4个条件仅仅是必要条件，它对产生死锁而言仅仅是一种可能性，而不是充分条件，即不一定会真实地出现死锁。因此在运行时刻，系统可以存在上述必要条件，但是通过某种方式避免系统进入死锁，这称为死锁避免或避免死锁。
10.目前，本领域技术人员针对死锁的技术手段，主要包括以下几类：
11.1.对消息请求路由资源的顺序进行严格规定，确保不会产生循环依赖关系。例如，经典的转弯模型和奇偶转弯模型通过限定特定的转弯从而打破对环的依赖。但是，此方式会产生进程启动延迟过高、通信效率低的问题。
12.2.加入额外的缓存作为逃离路径，用于死锁避免和恢复。例如，典型的虚拟网络划分以及平面自适应路由算法，基于物理通道建立虚拟通道，从而确保无依赖关系。但是，由于资源过多使用，造成成本上的增长。
13.3.通过某种技术监视和调控网络中空闲的缓存数量，保证消息能够获得资源并向
前转发。例如，冒泡流技术，通过控制缓存数量避免发生死锁。但是，由于进程阻塞时间长，需调用额外资源进行处理等问题不可忽略。
14.4.采用绕道路由的方法，安排路由器的每个输入微片到某些输出端口，从而确保每个周期消息都可以传递。但是，有可能不是在从当前节点到目的节点的最短路径上移动。


技术实现要素：

15.本发明的目的是为了克服现有技术存在的缺陷，为了解决triba-cnoc节点因共享存储转发缓冲区以及共享物理传输通道导致死锁的技术问题，特别是为了破坏引发死锁的必要条件，避免计算系统出现死锁状态，创造性地提出一种基于同步哈密顿环的triba-cnoc死锁避免方法。基三多核体系结构triba(triplet-based architecture)，是一种多核处理器结构，汇集了tiled、流式处理器、pim等先进多核体系结构的优点。
16.本发明基于triba-cnoc的拓扑特征，这种特征完全不同于现有其他片上网络，并且借助于这种特征能够在无负面影响的情况下实现无死锁的高效通信，因此是一种全新的去死锁方法。
17.为能够使本领域技术人员能够更加清楚的理解本方法，首先，对基三内核问片上网络triba-cnoc进行说明。
18.本发明用到的关于triba-cnoc拓扑tcf构造方法和图论定义、基本组、顶点、超顶点、最短路径路由算法等概念，可参考公开文献——《石峰等.基于s3变换的triba-net最短路径路由机制，中国科学：信息科学v.48.01(2018)：100-114》，在该文献中，拓扑构造方法及其图论定义中含有triba-cnoc节点的编码/命名方法。该文献中的tc
l
，即为本发明中的tcf，f和l的含义相同，本发明中的triba-cnoc与参考文献中的triba-net相同。此外，网络和其拓扑研究分别属于网络和图论两个不同领域，常规做法是分别使用各自领域的术语，但因为它们问的对应关系是显然的。
19.由于本发明同时涉及这两个领域。因此，除非情况特殊，本发明对各种术语不再做解释并且将不加区分的同时使用。例如，图论中的顶点对应于网络术语中的节点、超顶点对应于超节点、子图对应于子网，等等。
20.基三内核间片上网络triba-cnoc，拓扑名tcf，其平面图表示如图2所示，也称节点数3f，其中，f称为该拓扑的层次数(tcf具有清晰的层次结构)。
21.tcf的拼接构造方法如下：
22.首先，将三个相同的tc
f-1
作为三个超节点，分别命名为xf∈{1，2，3}。然后，将三个超节点两两互连，如图2中tc1所示，形成一个f层新图。在这个新图中，原本所有的三个tc
f-1
节点需要重新命名，命名规则是：在原本三个tc
f-1
的节点名x
f-1
…
x1之前添加相应的超节点名，形成新名xfx
f-1
…
x1。
23.上述构造法中，节点的命名(编码)规则称为idc-132。由该构造法可见，tcf由三个超顶点tc
f-1
两两互连拼接而成，任何子图都由三个作为超节点的子图tc
f-1
两两互连构成，这三个超节点分别记为和
24.tcf的图论定义如下：
25.定义：图tcf＝{v(tcf)，e(tcf)}，顶点集v(tcf)和边集e(tcf)分别为：
[0026][0027][0028]
其中，其中，是由中文字组成的长度为f-f的文字串xf…
x
f+1
，在语义明确时记作a
f-1
表示(f-1)个文字a构成的文字串；为自然数集合；表示顶点和邻接，即两点间存在边f为拓扑的层次数，f为子图的层次数。另外，tcf的是无向(即双向)图，故
[0029]
tcf具有以下特征：
[0030]
1.尖端
[0031]
tcf的三个顶角称为尖端(apex)或尖端顶点，尖端i的名字(编码)为if。
[0032]
2.基本组
[0033]
tcf的三个顶点两两互连形成的最小“三角形”结构称为基本组，即图论中的团(clique)。
[0034]
3.嵌套结构
[0035]
tcf呈现明显的嵌套层次结构，f层的tcf含3f个顶点，或称节点(也称内核)。本发明同时采用图论和网络的术语，非必要不作详细区分。
[0036]
4.输入/出端口
[0037]
tcf的节点包含3个双向端口，也称为3个输入口和3个输出口，其命名规则如图所示，连接基本组节点i的端口编号为i，将输出端口和输入端口分别记作pouti和pini。例如，一个节点连接基本组内节点3的输出和输入端口，分别记作pout3和pin3。
[0038]
虽然图论只以顶点和边描述数据传输，但在网络术语中，传输需要由节点内部电路实施，经端口放置于物理通道(相当于边)加以传输。因此，端口等信息很重要，例如端口名或编码。
[0039]
同时，本发明还涉及到基三内核间片上网络triba-cnoc的路由算法。此处，以最短路径路由(起点)算法为例，对其进行描述。
[0040]
1.焦点路由图
[0041]
因采用了最短路径路由策略，路由计算总是局限在某子网内，与区域外其他节点无关。该区域称为焦点路由子图，简称焦路子图frgf，f为该子图层次，如图所示。
[0042]
2.旋转变换
[0043]
triba-cnoc具有明显的旋转对称性，利用此特点，能够大幅简化路由计算和实现。该旋转使用三文字集上的选择变换群s3加以描述。本发明定义了与之对应的具体地，是元素具有确定顺序的旋转变换群s3：
[0044][0045]
其中，表示triba-cnoc上节点(包含超节点和尖端)旋转变换的顺序。例如，表示1节点旋转变换至1节点位置，即自身保持不变；表示节点1旋转变换至节点2的位置，2节点旋转变换至1节点位置，其余同理。
[0046]
3.传输模式
[0047]
在通信中，传输宏观上分为6种情况，称为传输模式，分别记为tm0～tm5，编号用二进制形式表示，如图4所示，其中，tm0对应路由节点和通信终点，分别位于triba-cnoc左下角和右下角区域，路由算法根据tcf的对称性在等价的tm0模式下计算，然后通过逆变换回原本模式。
[0048]
具体地，路由节点与通信终点间的数据传输模式如下：
[0049][0050]
其中，焦点路由图frgf；是按位or；“·”是按位and；tm
ith
是二进制数的第i位。s
″f、s
′f分别表示路由节点第f位层码的二进制第一位和第二位(例如，层码为2时，其二进制表示为10，则s
″f、s
′f分别表示为1和0)；t
′f、t
″f类似s
″f、s
′f。在变换下，当前传输模式路由计算与等价的tm0中的路由结果相同，即，对模式为tmi的通信，路由节点和通信终点经变换后，节点间的数据传输模式变为等价的tm0。因此，使用该关系，能够在当前通信模式和对应的等价tm0模式问变换。
[0051]
4.tm0模式的路由计算
[0052]
在最短路径路由约束下，fm0模式的源节点、通信终点和备选路径如图6所示，使用patha、pathb分别指代毗连路径、跨越路径。该模式下的路由计算的核心，是比较毗连路径patha和跨越路径pathb的长短，短者即为所选的路由路径。
[0053]
在上述基础上，本发明提出的一种基于同步哈密顿环的triba-cnoc死锁避免方法。第一，本方法基于triba-cnoc所具有的哈密顿环设计了相应的虚通道，所采用的哈密顿环为triba-cnoc拓扑所独有，不可能与其他拓扑相同。第二，本方法基于哈密顿环、采用同步传输，这与现有技术具有本质区别。第三，目前主流众核处理器的拓扑特征，导致其在应用中几乎无一例外地需利用应用特征优化后才能无死锁高效运行，即无法通用，而本发明的去死锁方法仅适用于triba-cnoc，且与应用无关，使得基于triba-cnoc的处理器可进一步作为通用处理器。
[0054]
有益效果
[0055]
本发明，对比现有技术，具有以下优点：
[0056]
1.本发明采用的同步传输机制，避免了握手信号的使用，不需前方节点反馈其缓
冲区占用状况信息，进而缩小了时间代价，提高了通信性能；
[0057]
2.本发明基于triba-cnoc架构特征，能够避免当前众核处理器普遍存在的通用性受限(在当代主流众核拓扑架构(2d-mesh或其改进)中，由于数据传输方向的随机性极易导致通信死锁，通常只能由用户提供面向应用的静态路由，或只能利用部分物理通道构成同步环网(ring network，一种拓扑相对简单的网络)，为triba-cnoc以及基于该片上网络的多/众核处理器的通用性奠定基础。
[0058]
由此可见，本方法为基于triba-cnoc的多/众核处理器可用，提供了解决方案。
附图说明
[0059]
图1为共享缓冲区导致的死锁；
[0060]
图2为triba-cnoc的拓扑及其图论定义tcf；
[0061]
图3为焦点路由图frgf；
[0062]
图4为triba-cnoc通信的数据传输模式；
[0063]
图5为triba-cnoc节点内部端口的编码；
[0064]
图6为tm0模式通信及焦点路由图frgf示意图；
[0065]
图7为tcf尖端节点间的哈密顿路径及其证明示意图(以尖端apex-1和apex-2为例)，其中为tc
f-1
的对称点；
[0066]
图8为tcf的哈密顿环路示意图；
[0067]
图9为tc3的三个双向虚哈密顿通所形成的哈密顿环流；其中，虚线仅为了表明物理传输通道的分组，而非惯常的虚连接；
[0068]
图10为tm0模式通信中哈密顿路径的对称点及数据将经过的边的最大层数示意图，以frg4对称点为左下方顶点为例。
具体实施方式
[0069]
下面结合附图对本发明方法做进一步详细说明。
[0070]
一种基于同步哈密顿环的triba-cnoc死锁避免方法。基于网络本身拓扑将通信数据进行逻辑分组，各分组本身独立实施传输，且各组间无数据交互，即便同类型数据的不同方向分组间也不存在交互，因而组间无竞争。在各同向环内部，采用同步传输，避免了缓冲区竞争。
[0071]
在现有技术基础上，本发明采用以下新的技术手段。
[0072]
基三内核间片上网络triba-cnoc，拓扑名tcf。
[0073]
基于tcf的哈密顿性，指哈密顿路径及哈密顿环。tcf的任意两尖端间存在哈密顿路径(h-path，如图7a所示)，且tcf含有哈密顿环(h-cycle，如图7所示)。
[0074]
具体说明，tcf的任意两尖端节点间存在一条哈密顿路径，即：该路径以某尖端节点为起始节点，以另一个尖端节点为终点，途经每个顶点一次且仅一次。
[0075]
对tcf的规模f，以尖端1f和2f间所存在的哈密顿路径为例，其哈密顿路径如图7a所示。
[0076]
基础步骤：f＝1，tc1(图7b所示)。双向路径为所述哈密顿路径。
[0077]
归纳步骤：f》1，tcf(图7b所示)。tcf由三个tc
f-1
及之间三个互连边构成，因归纳假
设，各tc
f-1
尖端间均有哈密顿路径，因此，由上述三个tc
f-1
的哈密顿路径及两条互连边(图7b所示)构成tcf的哈密顿路径。
[0078]
tcf中存在哈密顿环，即穿越每个顶点一次并仅一次的闭合路径。
[0079]
为更直观地理解利用triba-cnoc的哈密顿性去死锁的原理，以圆环的风格将tcf的哈密顿环路重新绘制如图(以tc3为例)。显然，虽然运行时刻随机地遍布各种方向的数据在传输，但宏观上呈现了沿环路的流动，因此称为虚拟哈密顿环流或简称哈密顿环流，甚至环流。称作虚拟的意愿在于数据并非仅在哈密顿边或非哈密顿边上运动，可能在两种边上跳跃。
[0080]
如图所示，围绕哈密顿环，非哈密顿边连接的两个端点就像在哈密顿环上不时出现“捷径”，随着传输，数据在哈密顿环和捷径间跳跃。如果认为“捷径”上数据在哈密顿环中使用了自己的独立通道传输，则triba-cnoc上的数据传输“逻辑上”形成沿着f个独立逻辑通道传输。例如图的三层triba-cnoc拓扑tc3逻辑上划分为三个环。
[0081]
如果在技术上保证数据在triba-cnoc上沿着其逻辑环路独立(即数据在其整个生命周期中仅位于一个逻辑环内)并同步传输，则环上数据永远不会与始终位于后方的数据发生冲突，从而打破了发生死锁的必要条件之一——循环等待，因此防止了死锁的发生。
[0082]
另外，图中，哈密顿环路位于外侧，内侧向心方向依次出现间接连接两顶点、连接两tc1、连接两tc2、
…
等的非哈密顿边，这些边的层次依次称为2、3、4
…
；哈密顿边是第1层边。
[0083]
哈密顿路径中点
[0084]
本发明中，通信数据使用自己“逻辑上”独立的通道传输，技术上是分时共享物理通道，但独享各自数据类型对应的存储转发缓冲来实现。对通信数据所使用缓冲区类型的判断，需在路由计算的同时，根据哈密顿路径结构和走向情况进行。为此，采用以下方案：
[0085]
任一tcf尖端节点都是另两个尖端节点间哈密顿路径的中点，即该尖端沿该哈密顿路径到另两个尖端节点的距离(简称哈密顿距离)相同。
[0086]
对tcf的规模f，以尖端3f到另外两个尖端1f和2f的哈密顿距离为例，证明该方案的正确性。
[0087]
基础步骤：f＝1，即tc1。尖端3到尖端1和2的哈密顿距离均为1。
[0088]
归纳步骤：f＞1，tcf由三个顶点及其互连边(共三个)构成，因归纳假设，尖端3
f-1
到所在tc
f-1
另两尖端的哈密顿距离相等(均为)，这两顶点到1f和2f的哈密顿距离均为3
f-1-1，即尖端3f到1f和2f的哈密顿距离均为
[0089]
子图的对称轴/点：
[0090]
tcf的每个子图均拥有自己的对称轴，它随tcf的哈密顿路径形状而变化。本发明中，将子图的对称轴标记如下：
[0091]
子图平面图示(如图所示)中，两尖端if和jf间的哈密顿路径(tcf的哈密顿路径一部分)中点(或称对称点)尖端kf，该顶点或其所在对称轴记为其中，
是tcf名(长度为f-f的文字串)，且i≠j≠k。
[0092]
例如，是名称为213的tc4子图，其对称轴/顶点是尖端24或顶点2132222。
[0093]
子图对称轴的结构：
[0094]
一个具有特定对称轴的子图由三个具有特定对称轴的低一个层次的子图构成，具体如下：
[0095]
对称轴为的图由对称轴分别为和的tc
f-1
子图及互连单边构成，其中是tcf名，且i≠j≠k。
[0096]
对tcf的f，以对称轴为例，证明该方案的正确性：
[0097]
基础步骤：f＝1时(图7a中的tc1)，如果该三顶点的tc1的名字为则它的对称点为也就是顶点这与实际情况相同。当f＝2时(图7a中的tc2)，如果它的对称轴为此时，其三个tc1子图的对称轴按定理所述分别为和也就是顶点和与实际情况相同。
[0098]
归纳步骤：f＞2时，tcf由三个tc
f-1
及三个互连单边构成，如果tcf的对称点显然考虑到三个tc
f-1
的哈密顿路径片段的端点情况，位于tcf左下角的tc
f-1
的对称点必然是即位于正上方的tc
f-1
的对称轴必然是即位于右下方的tc
f-1
的对称点必然是即
[0099]
例如，tc4对称轴可以转开一层后，下一层次三个tc3子图的对称点分别为和每个对称轴所在子图均可继续深入展开，例如所在tc3子图继续展开后的tc2子图对称轴分别为子图对称轴分别为和
……
。
[0100]
本发明方法，路由核心计算在等价的tm0模式中进行，随着焦点路由图frgf位置不同，它所具有的哈密顿环(部分)形状也不同，因此路由核心计算在得到转发端口后，还必须确定当前frgf及其对称点/轴等信息，从而确定通信数据将使用的缓冲区类型，也就是确定它属于哪个逻辑哈密顿环。结合子图对称轴结构和路由算法，本发明包括对判别frgf对称点/轴、计算tm0模式frgf的对称轴(axis)和判断所述数据使用的缓冲区类型的过程，具体如下：
[0101]
其中，frgf对称点/轴判别过程如下：
[0102]
以frgf的名字xf…
x
f+1
作为为输入，将对称轴axis设为xf，xf为初始对称点。
[0103]
建立一个循环变量i，对循环变量i，从f到f+1降序执行“如果x
i-1
与axis不同，令axis为集合{1，2，3}中非x
i-1
和非axis的另外值”。最后，将得到的对称点/轴axis作为最终结果输出(也可按形式输出)。其中，源节点所在frgf由起点路由算法的流水线给出。
[0104]
具体地，如算法1所示：
[0105][0106]
*算法中f为有限值，因此算法可以硬件实现
[0107]
计算tm0模式frgf对称轴，过程如下：
[0108]
以源节点s＝sf…
s1、目标节点t＝tf…
t1和当前通信模式tm(f为处理器的triba-cnoc最大层次)为输入，对称轴axis为输出，确定tm0模式frgf的对称轴。
[0109]
其原理如下：
[0110]
首先，当sf＝1且tf＝2或sf＝2且tf＝1时，必有axis＝3；当sf＝1且tf＝3或sf＝3且tf＝1时，必有axis＝2；当sf＝2且tf＝3或sf＝3且tf＝2时，必有axis＝1。由此得到对称轴的初始值；
[0111]
其次，要向下逐层分解哈密顿路径的构成，这里需要反复应用上述子图对称轴的结构过程，在一个循环变量i(每次循环递减1)从f-1到1的循环体对各层次的子图进行对称轴结构分解和分析。
[0112]
具体地，如算法2所示。
[0113][0114]
*算法中所有变量均为有限值，因此可硬件实现所有过程间并行
[0115]
tm0模式通信中数据缓冲区类型的判断(去死锁方法的总体框架)
[0116]
如前所述(参见文献1)，路由计算的核心工作在当前通信的等价tm0模式中进行，因此，需要在该模式下，在路由计算的同时确定通信数据所需要的缓冲区类型，将此计算称作“tm0模式通信中数据缓冲区类型的判断”(算法3)，其具体计算任务是：计算在各种情况下，通信在从源节点到终点的整个过程中将经由的所有的边层次数的最大值，将以此作为相应数据的缓冲区类型(即所属的逻辑哈密顿环)。
[0117]
该计算以焦点路由图frgf、对称点axis、当前通信模式tm、源节点s＝s
f...f+1
…
s1，目标节点t＝t
f...f+1
…
t1为输入，分别针对路由计算选择pathb或patha的两种情况，具体如下：
[0118]
当路由选择pathb时：如果f＝f，则输出f并结束。这是因为，由拓扑特征表明，此时数据必经由边
[0119]
如f≠f，输出f+1并结束。这是因为，由拓扑特征表明，对称点为x
f..f+11f
时，数据必经由边而对称点为x
f..f+12f
时，数据必经由边
[0120]
当路由选择patha时：存在三种可能，当对称点为1，即位于左下；当对称点为2，即位于右下；当对称点为3，即位于正上。对每一种可能，根据拓扑特征均能够确定后续通信数据传输过程中将经由边的最大层次；
[0121]
最后，计算得到的最高边层次为数据缓冲区类型，即逻辑哈密顿环编号。
[0122]
上述过程如算法3所示。
[0123][0124][0125]
*所有过程和子过程均并行
[0126]
另外，在本发明的方法中，缓冲区类型按哈密顿环流的逻辑层次编号，1层对应哈密顿边，2～f层为非哈密顿边。确定数据缓冲区类型时，应在数据创建(通信源节点)处确定，这需要结合起点路由算法的流水线实现，该流水线会给出一系列相关信息(例如当前传输模式tm、当前frgf及其对称点等)用于计算缓冲区类型。在等价的tm0模式中，源和目标节
点分别呈xf…
x
f+1
1s
f-1
…
s1和xf…
x
f+1
2t
f-1
…
t1形式的名字。
[0127]
图9展示了以圆环的风格绘制tc3的哈密顿环路图。在图9中数据的传输路径被划分成了三个逻辑环，包括直接连接所有节点的第一层哈密顿边、间接连接两个节点(例如等)的第二层非哈密顿边和连接两个tc1(例如等)第三层的跨组边，在技术上保证网络中的数据分别在三个逻辑环中进行独立(在其整个生命周期中仅位于一个逻辑环内)并同步传输，即确保了环路中的数据永远不会与始终位于后方的数据发生冲突，即打破了发生死锁的必要条件之一——循环等待，从而防止了死锁的发生。
[0128]
图10展示了以frg4为例，判断tm0模式通信中数据缓冲区类型的具体实现过程。在图10中，以tm0模式的frg4、对称点xf…
x
514
、源节点x
f..f+1
1s3s2s1、通信终点x
f..f+1
2t3t2t1为输入信息，路由选择为path a，判断当前通信数据未来传输中将经由边的最高层次(即缓冲区类型)过程如下：
[0129]
1.当s3＝3或t3＝2时，即源节点名为x
f..f+1
13s2s1，通信终点x
f..f+1
22t2t1时，通信必然经过第四层非哈密顿边或即缓冲区类型为四；
[0130]
2.当s3＝1或t3＝3时，即源节点名为x
f..f+1
11s2s1，通信终点x
f..f+1
23t2t1时通信必然经过第三层非哈密顿边或即缓冲区类型为三；
[0131]
3.当s2＝1或t2＝3时，即源节点名为x
f..f+1
121s1(s3＝2即符合对源节点位于含v2的各规模frgf子图，下同)，通信终点x
f..f+1
213t1时，通信必然经过第三层非哈密顿边或或即缓冲区类型为三；
[0132]
4.当s2＝3或t2＝2时，即源节点名为x
f..f+1
123s1，通信终点x
f..f+1
212t1时，通信必然经过第二层非哈密顿边或即缓冲区类型为二；
[0133]
5.当s1＝3或t1＝2时，即源节点名为x
f..f+1
1223，通信终点x
f..f+1
2112时，通信必然经过第二层非哈密顿边或即缓冲区类型为二；
[0134]
6.其他情况经过哈密顿边为第一层，即缓冲区类型为一。
[0135]
实施例1
[0136]
tcf上的每个双向边在triba-cnoc的具体实现时，采用两个传输方向相反的通道，在传输时各分组分时循环使用，即，以虚通道的方式实现本发明所述方法1～f层的双向哈密顿环路。这是成本相对低的实现方式，能够被大多数处理器应用场合所采纳。
[0137]
实施例2
[0138]
对传输的分组与实施例2相同，不同之处在于，各分组使用独享的物理通道构成的双向哈密顿环路实施传输，虽然实现成本相对较高，但性能大幅提升。
[0139]
实施例3
[0140]
对传输的分组与实施例2相同，对部分分组采用虚通道形式实现双向传输，类似实
施例1。另外的分组采用类似实施例3的独享双向哈密顿环路实施传输。该方式实现成本和性能的均衡。
[0141]
在具体应用中，分组可以使用分时复用物理通道或独享物理通道方式实现，也可以二者结合，因此实现方式灵活。以上通过实施例表明本方法的具体应用特征，需要说明的是，以上实施例仅用于说明本发明，而并非对本发明的限制。

技术特征：
1.一种基于同步哈密顿环的triba-cnoc死锁避免方法，其特征在于，利用基三内核间片上网络triba-cnoc的哈密顿性去死锁，基于网络本身拓扑将通信数据进行逻辑分组，各分组本身独立实施传输，且各组间无数据交互，即便同类型数据的不同方向分组间也不存在交互，组间无竞争；在各同向环内部，采用同步传输，避免缓冲区竞争；其中，triba-cnoc，拓扑名tc
f
，基于tc
f
的哈密顿性，指哈密顿路径及哈密顿环，tc
f
的任意两尖端间存在哈密顿路径h-path，且tc
f
含有哈密顿环h-cycle；路由核心计算在等价的tm0模式中进行，随着焦点路由图frg
f
位置不同，它所具有的哈密顿环形状也不同，路由核心计算在得到转发端口后，必须确定当前frg
f
及其对称点/轴等信息，从而确定通信数据将使用的缓冲区类型，即：确定它属于哪个逻辑哈密顿环；结合子图对称轴结构和路由算法，包括对判别frg
f
对称点/轴、计算tm0模式frg
f
的对称轴axis和判断所述数据使用的缓冲区类型。2.如权利要求1所述一种基于同步哈密顿环的triba-cnoc死锁避免方法，其特征在于：tc
f
的任意两尖端间存在哈密顿路径h-path，是指tc
f
的任意两尖端节点间存在一条哈密顿路径，即：该路径以某尖端节点为起始节点，以另一个尖端节点为终点，途经每个顶点一次且仅一次；tc
f
含有哈密顿环h-cycle，是指即穿越每个顶点一次并仅一次的闭合路径；其中，哈密顿路径中点：通信数据使用自己“逻辑上”独立的通道传输，技术上是分时共享物理通道，但独享各自数据类型对应的存储转发缓冲来实现；对通信数据所使用缓冲区类型的判断，在路由计算的同时，根据哈密顿路径结构和走向情况进行，采用以下方案：任一tc
f
尖端节点都是另两个尖端节点间哈密顿路径的中点，即该尖端沿该哈密顿路径到另两个尖端节点的距离相同，简称哈密顿距离相同；子图的对称轴/点：tc
f
的每个子图均拥有自己的对称轴，它随tc
f
的哈密顿路径形状而变化；子图的对称轴标记如下：子图平面图示中，两尖端i
f
和j
f
间的哈密顿路径中点尖端k
f
，该顶点或其所在对称轴记为其中，是tc
f
名，长度为f-f的文字串，且i≠j≠k；子图对称轴的结构：一个具有特定对称轴的子图由三个具有特定对称轴的低一个层次的子图构成，具体如下：对称轴为的图由对称轴分别为和的tc
f-1
子图及互连单边构成，其中是tc
f
名，且i≠j≠k。3.如权利要求1或2所述一种基于同步哈密顿环的triba-cnoc死锁避免方法，其特征在于：frg
f
对称点/轴判别过程如下：以frg
f
的名字x
f
…
x
f+1
作为为输入，将对称轴axis设为x
f
，x
f
为初始对称点；建立一个循环变量i，对循环变量i，从f到f+1降序执行“如果x
i-1
与axis不同，令axis为集合{1,2,3}中非x
i-1
和非axis的另外值”；最后，将得到的对称点/轴axis作为最终结果输
出，或者按形式输出；其中，源节点所在frg
f
由起点路由算法的流水线给出；计算tm0模式frg
f
对称轴，过程如下：以源节点s＝s
f
…
s1、目标节点t＝t
f
…
t1和当前通信模式tm为输入，对称轴axis为输出，确定tm0模式frg
f
的对称轴，f为处理器的triba-cnoc最大层次；首先，当s
f
＝1且t
f
＝2或s
f
＝2且t
f
＝1时，必有axis＝3；当s
f
＝1且t
f
＝3或s
f
＝3且t
f
＝1时，必有axis＝2；当s
f
＝2且t
f
＝3或s
f
＝3且t
f
＝2时，必有axis＝1，由此得到对称轴的初始值；其次，要向下逐层分解哈密顿路径的构成，这里需要反复应用上述子图对称轴的结构过程，在一个循环变量i从f-1到1的循环体对各层次的子图进行对称轴结构分解和分析，每次循环递减1；模式通信中数据缓冲区类型的判断，过程如下：路由计算的核心工作在当前通信的等价tm0模式中进行，因此，需要在该模式下，在路由计算的同时确定通信数据所需要的缓冲区类型，将此计算称作“tm0模式通信中数据缓冲区类型的判断”，其具体计算任务是：计算在各种情况下，通信在从源节点到终点的整个过程中将经由的所有的边层次数的最大值，将以此作为相应数据的缓冲区类型，即所属的逻辑哈密顿环；该计算以焦点路由图frg
f
、对称点axis、当前通信模式tm、源节点s＝s
f
…
f+1
…
s1，目标节点t＝t
f
…
f+1
…
t1为输入，分别针对路由计算选择pathb或patha的两种情况，具体如下：当路由选择pathb时：如果f＝f，则输出f并结束；这是因为，由拓扑特征表明，此时数据必经由边如f≠f，输出f+1并结束；这是因为，由拓扑特征表明，对称点为x
f..f+11f
时，数据必经由边而对称点为x
f..f+12f
时，数据必经由边当路由选择patha时：存在三种可能，当对称点为1，即位于左下；当对称点为2，即位于右下；当对称点为3，即位于正上；对每一种可能，根据拓扑特征均能够确定后续通信数据传输过程中将经由边的最大层次；最后，计算得到的最高边层次为数据缓冲区类型，即逻辑哈密顿环编号。4.如权利要求3所述一种基于同步哈密顿环的triba-cnoc死锁避免方法，其特征在于：缓冲区类型按哈密顿环流的逻辑层次编号，1层对应哈密顿边，2～f层为非哈密顿边；确定数据缓冲区类型时，应在数据创建处确定，这需要结合起点路由算法的流水线实现，该流水线给出相关信息用于计算缓冲区类型；在等价的tm0模式中，源和目标节点分别呈x
f
…
x
f+1
1s
f-1
…
s1和x
f
…
x
f+1
2t
f-1
…
t1形式的名字。

技术总结
本发明涉及一种基于同步哈密顿环的TriBA-cNoC死锁避免方法，属于计算机众核处理器技术领域。本方法解决了TriBA-cNoC节点因共享存储转发缓冲区以及共享物理传输通道导致死锁的技术问题，基于TriBA-cNoC的拓扑特征，能够避免当前众核处理器普遍存在的通用性受限中，由于数据传输方向的随机性极易导致通信死锁，通常只能由用户提供面向应用的静态路由，或只能利用部分物理通道构成同步环网。本方法避免了握手信号的使用，不需前方节点反馈其缓冲区占用状况信息，进而缩小了时间代价，提高了通信性能，为TriBA-cNoC以及基于该片上网络的多/众核处理器的通用性奠定基础。网络的多/众核处理器的通用性奠定基础。网络的多/众核处理器的通用性奠定基础。


技术研发人员：石峰 李春峰 计卫星
受保护的技术使用者：北京理工大学
技术研发日：2022.09.20
技术公布日：2023/7/11