基于芯片设计流程和应用设计流程的片上网络编码优化方法

摘要

本发明公开了一种基于芯片设计流程和应用设计流程的片上网络编码优化方法，包括下述步骤：S1、利用网络编码优化设计片上网络，根据多核芯片复杂组播行为的网络性能要求，以支持片上网络基本组件的方式，计算出各核心的物理位置，以最小的硬件和能力消耗满足多核芯片间的通信性能要求；S2、在现有芯片的互连体系结构中，将复杂网络通信拓扑结构进行分解。本发明利用信息流的方法对多组播拓扑进行分解，解决目标函数的稀疏优化问题，实现多组播网络在片上网络现有的拓扑结构总的性能优化,为片上网络的设计提供新的方法和思路，对于提高片上网络和众核芯片的性能、降低功耗具有重要的理论和实践意义。

说明书

技术领域

本发明涉及网络路由器的研究领域，特别涉及一种基于芯片设计流程和应用设计流程的片上网络编码优化方法。

背景技术

随着半导体工艺的持续发展，单一芯片容纳晶体管的数量不断增加，集成电路迈入了多核(multiple-core)或者众核(many-core)时代。核心依靠片上网络(Network-on-Chip or NoC)连接在一起，通过并行运算来提高芯片的整体性能。目前，众核芯片已经实现了大量的商业应用。例如：Intel 48核的云计算机单芯片云计算机“single-chip cloud computer”和Tilera 72核的TILE-Gx72单芯片。这些芯片广泛地应用于超级计算、云计算、大数据等系统中。

众核芯片的规模和并行度不断增大，核心之间的可靠互连和通信变得越来越困难，总线和点对点的互连方式逐渐不能满足片上互连的性能和可扩展的需要，人们提出了基于包交换的片上网络方式。众核芯片的应用不断增加，芯片中核心之间的并行协作日益紧密，相互之间传输的数据量不断加大，需要支持更为复杂的网络行为。此外，复杂多组播(multi-session multicast)通信在众核芯片中应用也非常频繁，例如：Cache一致性和传输共享数据等。这些因素增加了片上网络的通信量，造成了网络拥塞，降低了片上网络的性能，增加了整个芯片的功耗。人们急需新的片上网络设计以提高性能和能耗效率。

片上网络概念的提出是在2000年左右，借鉴宏观计算机网络包交换的数据传输形式和共享物理通道的结构方式，支持以“微片(flit)”为单位的传输模式。1999年，美国麻省理工大学的Raw微处理器将静态和动态两套通信网络相结合，共同实现多个处理器核心的协同和通信；Guerrier和Greiner于2000年提出了基于胖树(fat-tree)结构和包交换SPIN片上网络结构。2001年，Dally和Towles分析了片上系统硬件资源的特点，提出了一个通用NoC模型，从而证明了片上网络在解决SoC互连的可行性；同年，Benini和Micheli提出NoC的层次化构造模型。随后，研究者们在片上网络领域展开了广泛研究，提出了一系列的片上网络结构，较有影响的有：英国曼彻斯特大学的CHAIN和SpiNNaker， 意大利Bologna大学和美国斯坦福大学的XPIPES，飞利浦公司的AETHEREAL，瑞典皇家理工学院的NOSTRUM，法国UPMC大学的SPIN，以及丹麦理工大学的MANGO等。

随着多核处理器和共享数据应用的发展，更为复杂的网络行为，例如组播(multicast)，成为片上网络设计的重要考虑因素。片上网络的数据传输主要有单播(unicast)传输和组播传输。组播可以用多个单播操作来实现，但是效率十分低。研究者们在组播片上网络方面做了大量研究，提出了多种支持组播的NoC架构和组播优化算法。Merolla等人提出了一种支持组播的树形路由器，可以通过在子树(subtree)中循环广播的方式实现组播。Stefan等人提出了一种分时复用的片上网络架构，支持QoS、组播和高效的连接建立机制。Abad等人提出了一种支持组播的新路由机制，利用自适应树的组播方法保证组播的正确传输而无需路由的限制，因此提高了CMP组播的性能。Samman等人提出了一种无需虚拟通道就可以实现无死锁的组播，NoC的路由器支持以下功能：如果某些数据包被阻塞了，其它数据包的微片可以插入到它们之前，从而避免死锁。尤志强等人提出了基于BFT型的片上网络提出了一种组播路由协议和节点编码设计方案，用来完成对相同核的组播测试，降低了测试应用时间。

网络编码的概念第一次是由Ahlswede等人于2000年提出来的。它是一种网络数据传输方式，扩展了传统路由的概念和功能。在传统的基于路由的网络中，网络节点(路由器、交换机等)只执行数据的转发和复制两项操作；而在使用了网络编码之后，网络节点能够对接收到的数据进行任意的编码操作(如线性变换等)，再将编码结果复制或转发。与传统网络相比，网络编码的优势主要体现在组播应用中，可以提升吞吐率，实现有向网络(directed networks)的组播容量(multicast capacity)。网络编码一经提出便引起了国际学术界的广泛关注，其理论和应用已成为网络和通信领域研究的新热点。

网络编码的引入给网络带来一定的额外消耗，如额外的编码操作、复杂的路由器、较大的缓存。在网络编码中，需要在满足吞吐率的前提下，尽量使用简单的运算，较小的有限域，并且减少编码节点的数量。对于给定的网络拓扑结构，寻找最小的有限域来达到网络容量是有NP难度的。C.Fragouli andE.Soljanin在《Information flow decomposition for network coding》中证明有限域的大小与目标节点的数目密切相关，并且给出了一个最小有限域的上界。相类似的，寻找最少的编码节点数也是有NP难度的。M.Langberg,A. Sprintson,and J.Bruck在《The encoding complexity of network coding》中首先将一般的网络转换为所谓的简单网络。使用简单网络的方法，在无环和有环的网络下分别得出了编码节点数的上、下界。C.Fragouli and E.Soljanin利用贪婪算法，提出了一个新的网络信息流模型来研究编码节点和编码边数目的优化。编码节点、编码边优化还可以应用遗传算法(genetic algorithm)。M.Kim,C.W.Ahn,M.Médard,and M.Effros在《On minimizing network codingresources:An evolutionary approach》中首次考虑采用遗传算法优化编码边数。对于染色体的编码，首先将网络G转换为对应的线图G’。对于每一种编码方案，将对应的线图G’所有边上编码系数组成的比特向量作为染色体编码。用编码边的数量作为染色体的适应值。初步的仿真结果表明，应用遗传算法的结果优于贪婪算法。

Texas A&M University的研究团队2006年第一次提出将网络编码应用于集成电路互连领域。Jayakumar、Khatri和Gulati等人在ASIC总线中应用网络编码技术，降低能耗7％～8.5％，减少互连总线长度和面积6％～10％。随后，他们将网络编码的应用拓展到FPGA互连领域，取得了不错的效果。该研究团队还设计了一种支持网络编码的双向总线，网络编码技术可以利用一条双向总线实现两条单向总线的带宽，节约49％的总线资源和11％的总线能耗。

2011年，Indrusiak第一次将网络编码的概念运用于片上网络中，探讨其在NoC组播通讯中的潜在优势。文章从数据包传输的跳数(hops)的角度，比较network coding与XY routing传输所需要hop的总数，初步论证了将networkcoding应用到NoC中的优势。分析表明，网络编码可以减少10％～22％的传输跳数。Thuan等人从硬件实现方面，将网络编码应用于CMP中，设计了支持网络编码的路由器，证明在一个9核的CMP中，网络编码可以大大降低网络延时，并且提高网络的吞吐量1.48倍。Shalaby等人主要考虑蝶形网络在2D-mesh下的优化问题，提出了5个选择中间源节点is和中间目的地节点id的算法，证明网络编码可以降低传输跳数12％～35％。Vonbun等人将网络编码的优化问题从蝶形网络扩展到一般的组播拓扑结构，从理论上证明了网络编码可以降低片上网络的包传输距离。A.Shalaby,V.Goulart,and M.-S.Ragab在《Study ofapplication of network coding on NoCs for multicast communications》中，证明使用网络编码还可以在组播应用中有效地降低传输延迟。Hu等人也提出用网络编码技术的片上网络架构，取得了初步效果，但电路设计和实验结果 描述并不清晰。

从以上的文献分析可以看出，将网络编码技术应用于片上网络方面的研究工作刚刚起步，相关的研究成果还不全面。这些初步的探索证明了片上网络可以有效利用网络编码技术提高网络吞吐量、减小传输延迟、节约传输能耗。但是，大部分技术都局限于蝶形网络的构造，而蝶形网络只是网络编码应用的一个特例。虽然有些技术将蝶形网络扩展到一般的组播拓扑结构并给出了理论性能，然而文中并没有提到具体的网路编码构造以实现这些理论性能。但依然局限于组播内(Intra-session)编码。通过组播间(Inter-session)编码，我们应该可以实现更大的性能增益。此外，这些文献大多基于网络编码的粗略理论评估，缺乏实际电路环境下精确的延时和功耗实验数据，优化算法也是基于现有网络编码理论，没有针对片上网络的结构和性能特点进行有针对性的改进，难以实现对网络编码对于片上网络的促进作用进行全面、综合的研究和评价。

发明内容

本发明的主要目的在于克服现有技术的缺点与不足，提供一种基于芯片设计流程和应用设计流程的片上网络编码优化方法。

为了达到上述目的，本发明采用以下技术方案：

本发明提供了一种基于芯片设计流程和应用设计流程的片上网络编码优化方法，包括下述步骤：

S1、利用网络编码优化设计片上网络，根据多核芯片复杂组播行为的网络性能要求，以支持片上网络基本组件的方式，计算出各核心的物理位置，确定各核心之间的互连拓扑，确定网络编码路由器的个数和插入位置，定义数据链路的带宽参数，以最小的硬件和能力消耗满足多核芯片间的通信性能要求；

S2、在现有芯片的互连体系结构中，将复杂网络通信拓扑结构进行分解，确定哪些节点可以利用数据编码提升性能，确定中间源节点和中间目的地节点的位置，生成新的通信拓扑结构。

作为优选的技术方案，步骤S1具体为：

假设每增加一个节点需要增加花费α，对于给定的两个节点i和j，假设建立一条单位容量的信道花费为βd_ij，其中d_ij是节点i和j的距离，需要设计一个满足组播业务需求的，花费最小的拓扑结构G(V,E)，其中V是节点集，E是信道集， 用表示所有的中间节点，也就是说该优化问题可以被归纳为：

给定条件：

·一组或者多组源节点以及目标节点的位置；

·组播业务需求；

·α和β的取值；

优化目标：

设计参数：

·中间节点的数目以及位置；

·所有节点直接的信道连接；

满足条件：

●至少存在一种网络编码的方案来实现组播业务的需求。

作为优选的技术方案，在所述满足条件中，还包括下述条件：

●传输延时不超过设计最大限；

●传输跳跃数不超过设计最大限。

作为优选的技术方案，步骤S2具体为：

对于给定的源节点、目的地节点以及信息传输要求，优化算法需要在片上网络中选择合适的中间节点来实现传输要求，基于信息流的方法，编码子图的选择可以被定义为一个优化问题，片上网络中的无向信道可以被看作是两条平行的，指向相反方向有向信道，头节点和尾节点被用来标志有向信道，不同于传统的路由网络，网络编码需要区分信息流和物理流，假设需要在同一个片上网络中实现M个组播，用s_m和D_m分别表示第m个组播的源节点和目的地节点集，第m个组播需要传送x_m个数据包，算法可以用来表示在信道(i,j)上传输给第m个组播中目的地节点d的信息流，并且用表示信道(i,j)上的物理流，传统意义上的流守恒定律被修改为：

$g_{i,j}^{md}\le f_{i,j}^m,\forall d\in D_m.---\left(2\right)$

除了流守恒，每一个信道上的物理流还不应该超过信道容量，也就是说

$\underset{m=1}{\overset{M}{\Sigma }}{f}_{i,j}^m\le C_{i,j}---\left(3\right)$

编码子图的选择就是在满足(1),(2)(3)的条件下优化目标函数，如果要实现最小跳跃数，目标函数可以被定义成

$min\underset{(i,j)}{\Sigma }1(f_{i,j}^m>0)---\left(4\right)$

其中，公式(4)是一个稀疏优化问题。

作为优选的技术方案，在选定编码子图以后，还需要进行网络编码的构造，具体是：先将一个选定的子网络转化为线图，通过图形简化的方式来决定编码的节点；然后再设计每一个节点上的编码行为。

本发明与现有技术相比，具有如下优点和有益效果：

1、本发明从优化理论等多方面对网络编码在片上网络中的应用开展综合研究，实现对硬件、功耗、性能的精确评估和建模。本发明将为片上网络的设计提供新的方法和思路，也为网络编码拓展崭新的应用领域，对于进一步提高片上网络和众核芯片的性能、降低功耗具有理论和实践的创新性。本发明的特色与创新之处表现在，提出了适应片上网络特性的网络编码优化算法。

2、网络编码和片上网络相结合产生了一些新的科学问题，现有的网络编码理论无法在片上网络的设计和应用开发中直接使用。本发明针对片上网络拓扑结构的特性，有针对性地提出化繁为简(将复杂拓扑分解成若干简单子网)，再由简入繁(将多个简单子网合并成一个完整的拓扑)的研究方法，利用信息流的方法对多组播拓扑进行分解，解决目标函数的稀疏优化问题，将任意结构的网络组播映射到片上网络所采用的拓扑结构中，并且尽量减少优化算法的复杂度。这些优化算法既可以支持片上网络的设计，又可以支持现有芯片的应用设计优化。

3、在具体的实现技术手段方面，本发明集聚了网络编码、片上网络、片上多处理器和低功耗方面的最新研究成果，融合信号理论、集成电路和计算机等 相关学科知识，理论与实践相结合，物理建模和仿真实验相结合，提出一套较为全面的支持网络编码的片上网络基本组成电路部件，并在此基础上提出利用网络编码技术提高片上网络性能、降低功耗的优化方法。

4、评估片上网络电路设计是否优化的实验手段，则涉及到集成电路设计和仿真软件设计，如图3所示。NoC电路设计与建模采用IC设计EDA软件工具和FPGA相结合的方法，具体如图3左侧所示。本发明利用FPGA加快行为仿真的效率，检验功能的正确性，并利用EDA工具仿真测试出新的片上网络各部件的延时和功耗，并进行精确的延时和功耗建模。在仿真软件环境下进行测试评估，如图3右侧所示。延时和功耗模型输入到片上网络仿真软件工具中(根据之前的经验，二次开发NS2网络仿真工具来设计仿真环境)，结合本发明提出的网络编码优化方法，运用大量实际案例，成功验证网络编码对片上网络的提升效果。

附图说明

图1(a)-图1(b)分别为蝶形网络编码结构图和片上网络中网络编码处理图；

图2是以微片为单位的网络编码带来的对齐问题的示意图；

图3(a)-图3(c)分别是蝶形网络图、蝶形网络线图和简化线图；

图4是本发明的流程图。

具体实施方式

下面结合实施例及附图对本发明作进一步详细的描述，但本发明的实施方式不限于此。

实施例

网络编码的提出是在传统的宏观网络环境中的(如无线传感网络、计算机网络等)，这些网络的路由器具有较强的处理和存储功能，在支持路由功能的同时，可以足以应付网络编码的额外工作。并且，相对网络信道传输的延时和功耗来说，网络编码所消耗的额外延时和功耗很小或者可以忽略不计。但是，片上网络是一种对于速度和硬件资源要求极其严格的微型网络，其处理和缓存能力都很弱，不可能消耗过多额外的硬件和能耗资源来支持网络编码。

图1(a)是一个典型的蝶形网络编码结构：s1、s2为两个组播源节点；d1、 d2为两个组播的目的地节点；is为中间源节点，其既是一个路由器，又是一个编码器，将两路输入的原始数据包按照flit的顺序进行编码，然后转发；id为中间目的地节点，将其接收到的编码后的数据包分别转发给组播的目的地方向。中间源节点is需要接收来自s1、s2的数据包A、B，作简单的异或处理，然后传输给中间目的地节点id。中间目的地节点id将数据包分发给d1、d2。d1、d2接到数据包A⊕B后与数据包A或者B进行异或运算，得到B或者A。

在宏观网络中(例如无线网络)中，网络传输所需要的时间和能耗远远大于节点数据处理的时间，is和id一般为处理器节点，具有较强的处理能力和较大的缓存。数据包A、B完全到达is后才进行异或处理。

然而，如图1(b)所示的片上网络中，网络传输要求的速度极快，网络编码的处理和分发不可能经过处理器节点(如nis、nid)，否则将严重影响了片上网络的速度。这些操作必须由片上网络路由器(router)来完成(is、id)。但是，网络编码的恢复操作(如B＝A⊕A⊕B)可以在目的地节点(如d1、d2)中完成。

众所周知，片上网络的路由器只支持速度极快的电路级交换和路由操作，并且缓存很小，以微片(flit)作为传输的单元，无法容纳一个完整的数据包(package)。因此，新的片上网络的网络编码操作也必须以flit为单位，而不能以package为单位。由于片上网络存在阻塞，微片的传输可能出现断续，给路由器的网络编码带来了巨大的困难，如图2所示。

图2中灰色填充的方块(以c开头)代表异或编码后的flit。情况1是最理想的状况，即数据包A、B长度相等，并且同时到达某一中间源节点。该中间源节点将同时到达的微片进行异或处理，形成新的微片(c0-c6)并且发送。情况2表示数据包A、B相差两个时钟周期到达。a0、a1和b5、b6无法进行网络编码处理。情况3表示受到网络拥塞的影响，数据包A、B的微片断断续续到达中间源节点，网络编码的情况变得十分复杂，使得后续数据的恢复受到极大的影响。

此外，如图1(b)所示，芯片一旦完成后，其组播节点位置、网络特性、链路带宽等都已无法改变。而现有的网络编码的优化技术允许网络结构和参数根据优化的要求进行改变。这就产生了网络编码优化技术的新问题。

如图4所示，两个关键核心的技术路线如下：

1)利用网络编码优化设计片上网络

在芯片设计初期，根据以芯片和组播业务的功能需求，运用网络编码技术，设计性能和功耗最优的片上网络。对源节点和目的地节点进行简单的点对点连接需要建立过长的链路，并且导致大量重叠的路径。适当地添加中间节点，并合理地运用网络编码可以有效地利用带宽、降低功耗、提高性能。假设每增加一个节点需要增加花费α。对于给定的两个节点i和j，假设建立一条单位容量的信道花费为βd_ij，其中d_ij是节点i和j的距离。我们需要设计一个满足组播业务需求的，花费最小的拓扑结构G(V,E)，其中V是节点集，E是信道集。我们用表示所有的中间节点，也就是说这个优化问题可以被归纳为：

给定条件：

●一组或者多组源节点以及目标节点的位置

●组播业务需求

●α和β的取值

优化目标：

设计参数：

●中间节点的数目以及位置

●所有节点直接的信道连接

满足条件：

●至少存在一种网络编码的方案来实现组播业务的需求

●(可选)传输延时不超过设计最大限；

●(可选)传输跳跃数不超过设计最大限。

在实际应用中，可以根据实际需求对以上的优化问题进行调整，比如给传输延时和跳跃数分配相对应的花费，并将它们归纳于优化目标中；或者将中间节点区分为可编码节点和普通路由节点，并相应地调整他们的花费。

直接解决以上的优化问题是非常困难的。本发明致力于寻找一些次优，但是高效的解决方案。其中一个可行的方向是先建立一个满足条件的拓扑结构，再对其中的中间节点位置进行调整，对不必要的信道进行删减及合并。在不违背设计要求的情况下减少花费。

2)利用网络编码优化现有片上网络的应用程序

对于给定的芯片中，网络编码亦可在现有片上网络基础上对其应用程序进行优化。本发明采用的技术路线主要包含两方面：编码子图的选择(subgraphselection，即组播拓扑结构在片上网络中进行映射)和网络编码的构造(network code construction，即在给定的拓扑结构上选择适当的编码节点，数据包以及网络编码系数)。一般来说，这两个问题可以分开解决。

首先，对于给定的源节点、目的地节点以及信息传输要求，优化算法需要在片上网络中选择合适的中间节点来实现传输要求。这些被选择的中间节点和它们之间的传输方向决定了编码子图。根据不同的优化目标，我们可以选择不同的编码子图。目前，对于片上网络来说，最直接也是最常用的优化目标就是达到最小的跳跃数。基于信息流的方法，编码子图的选择可以被定义为一个优化问题。片上网络中的无向信道可以被看作是两条平行的，指向相反方向有向信道。头节点和尾节点被用来标志有向信道，比如信道(i,j)就是从节点i指向节点j。不同于传统的路由网络，网络编码需要区分信息流和物理流。假设需要在同一个片上网络中实现M个组播，用s_m和D_m分别表示第m个组播的源节点和目的地节点集。第m个组播需要传送x_m个数据包。算法可以用来表示在信道(i,j)上传输给第m个组播中目的地节点d的信息流，并且用表示信道(i,j)上的物理流。传统意义上的流守恒定律被修改为：

$g_{i,j}^{md}\le f_{i,j}^m,\forall d\in D_m.---\left(2\right)$

除了流守恒，每一个信道上的物理流还不应该超过信道容量，也就是说

$\underset{m=1}{\overset{M}{\Sigma }}{f}_{i,j}^m\le C_{i,j}---\left(3\right)$

编码子图的选择就是在满足(1),(2)(3)的条件下优化目标函数。如果要实现最小跳跃数，目标函数可以被定义成

$min\underset{(i,j)}{\Sigma }1(f_{i,j}^m>0)---\left(4\right)$

其中，公式(4)是一个稀疏优化问题。稀疏优化是著名的NP难度问题。

公式(1)(2)定义的流守恒定律并不适用组播间编码。组播间编码子网络的选择是一个非常困难的问题。本发明最倾向的解决方案就是合并组播。当两个组播的目的地节点集有很大的重叠，或者当目的地节点非常靠近的时候，可以将它们合并。合并组播的目的地节点集由原来两个目的地集的并集构成。在合并后的多组播传输中，可以利用前面提到的优化方法。

在选定编码子图以后，还需要进行网络编码的构造。目前最简单的分布式网络编码就是随机线性网络编码。然而随机线性网络编码需要用到比较大的有限域。当有限域增大，计算的复杂度也会快速增加。这将增加对路由器的计算要求，并且增加网络延时。另一方面，随机线性网络编码需要每一个节点都进行编码，这也是需要避免的。因此，需要设计一个简单高效的新型编码方式。课题组初步方案是先将一个选定的子网络转化为线图。通过图形简化的方式来决定编码的节点。然后再设计每一个节点上的编码行为。比如在蝶形网络中，它的线图由两个源节点，两个目的地节点，还有七个信道节点组成，如图3(b)所示。这七个信道节点分别对应图3(a)中的7条信道。在线图中，可以证明当一个信道节点对应的信道容量大于它所有父节点对应的信道容量之和时，这 个信道是不需要编码的。假设图3(a)中每个信道都是单位容量，那么图3(b)中的线图可以被简化为图3(c)。从图3(c)中我们可以看出，唯一个需要进行编码行为的就是信道e₅.也就是说，在原图3(a)，唯一需要编码的节点就是信道e₅的尾节点(节点1)。

虽然对于蝶形网络，简化线图得到了最优的编码节点数。但是对于一般的网络来说，通过简化线图，只可以得到一个编码节点数的上限，并不一点是最小值。

处于成本考虑，可以只给指定的路由器增加编码功能。对于这种情况，编码子图的选择和编码构造都需要进行相对应的调整。比如说，公式(1)(2)定义的流守恒只适用于可编码的节点的输出信道。对于其他信道，必须使用传统的流守恒定律，也就是说物理流守恒。

上述实施例为本发明较佳的实施方式，但本发明的实施方式并不受上述实施例的限制，其他的任何未背离本发明的精神实质与原理下所作的改变、修饰、替代、组合、简化，均应为等效的置换方式，都包含在本发明的保护范围之内。