CN101420380B - 一种双层双环型片上系统 - Google Patents

Abstract

本发明提出一种双层双环型片上网络拓扑结构，包括IP单元、交换单元、网络适配器、链路单元，交换单元实现各IP单元的相互通信，采用时分复用和优先级相结合的机制，可实现了公平路由和带宽的空分复用，同时有效的避免了拥塞和死锁。链路单元将上述的各单元依据一定的结构进行连接，该结构采用两层双环结构，第一层为主干环网结构，第二层称为子网络结构。主干环网结构又为双环型结构，共分为两组环网，其中有一组环网为主环，另一组为备用环，备用环用于片上网络结构的容错机制。每组环中包含一个控制环和一个数据环。本发明采用环网拓扑结构简单，结点之间具有固定的跳数，路由简单，易于实现时分复用、空分复用和容错诸多优点。

Description

一种双层双环型片上系统

技术领域

本发明属于片上互连网络设计领域，特别是一种具有公平路由和带宽可空分复用的一种双层双环型片上网络拓扑结构。 

随着半导体工艺的不断发展和片上系统(SoC，System-on-Chip)技术的不断完善，SoC中所包含的IP核数目不断增加。现有的以总线结构为通信基础的SoC技术面临着在性能、功耗、延时和可靠性等方面的巨大挑战。在2001年左右，一些研究机构借鉴和吸收了通信网络和并行计算的思想，提出了以通信为核心的复杂SoC的IP核集成方法，即片上网络(Network-on-Chip，NoC)，采用包交换和路由的方法替代传统总线，实现处理单元(IP核)与通信结构(网络)的分离，以解决复杂SoC面临的各种问题。 

由于Mesh拓扑结构的规则性和易扩展性，有利于布局布线，因此有关片上网络很多的路由算法、容错、服务质量、功耗等问题的研究都是基于Mesh结构及其变型结构(如Torus结构)。其中，比较有影响的Mesh NoC系统是瑞典皇家工学院的Nostrum系统。 

环网由于其拓扑结构简单，结点之间具有固定的跳数，路由简单，易于实现时分复用、空分复用和容错等诸多优点，在宏观网络中得到广泛应用。例如，世界范围内广泛使用同步数字体系SDH以及目前正在研究的弹性分组环RPR是典型的环网结构。 

在NoC研究领域，环形拓扑结构受到了诸多的关注。芬兰Tempere大学开发的Proteo，采用分层双环结构，不同的业务具有不同结构，不同的业务有不同的服务质量。瑞典 

University大学受城市交通线路启发，提出了环路的R2NoC结构，以解决路由延时问题。这两种结构均支持包交换。 

本发明的目的是解决复杂片上系统(SoC)面临的性能、功耗、延时和可靠性等各种问题，提出一种具有公平路由和带宽可空分复用的一种双层双环型片上网络拓扑结构。 

本发明的技术解决方案是：一种双层双环型片上网络拓扑结构，包括IP单元(IP)、交换单元(S)、网络适配器(NA)、链路单元，交换单元(S)采用时分复用、带宽的空分复用和优先级相结合的机制实现各IP单元(IP)的相互通信；链路单元将IP单元(IP)、交换单元(S)、网络适配器(NA)依据一定的结构进行连接，该结构为双层双环型结构，第一层为主干环网结构，第二层称为子网络结构，主干环网结构又分为两组环网，其中有一组环网为主环，另一组为备用环，备用环用于片上网络结构的容错机制，每组环中包含一个控制环和一个数据环，控制环采用包交换的形式交换IP单元(IP)间路由、链路错误和差错控制信息，数据环采用电路交换方式进行IP单元(IP)间的数据通信，子网络结构采用线性结构、总线结构或星形结构。 

所述的IP单元(IP)是处理器、存储单元、FPGA、DSP之一，各个IP单元(IP)既可以是同质的，也可以是非同质的；既可以是细粒度的，也可以是粗粒度的。 

所述的网络适配器(NA)是IP单元(IP)和交换单元(S)之间接口，使不同的IP单元(IP)都可以连接到相同接口的交换单元(S)。 

本发明的效果是：采用环网拓扑结构简单，结点之间具有固定的跳数，路由简单，易于实现时分复用、空分复用和容错诸多优点，本发明中的交换单元采用时分复用和优先级相结合的机制，可实现了公平路由和带宽的空分复用，采用带宽空分复用，多个IP单元可以同时发送数据。在链路带宽有剩余的情况下，保证优先级高的IP单元可以获得更多的带宽，多个IP单元可以同时发送数据，采用时分复用的方法，保证每个IP单元都有机会发送数据，因此，保证了环路每个IP单元不会产生饥饿的现象，每个IP单元知道全局的路由信息，预先建立通信链路。因此，可以保证不出现死锁、活锁以及拥塞现象。本发明中的主干环网结构分为两组环网，其中有一组环网为主环，另一组为备用环，备用环主要用于片上网络结构的容错机制，主环和备用环都包括一条数据环和一条控制环。在链路正常情况下，为了提高链路效率备用数据环也用于传递数据，备用控制环处于空闲状态。如果主环上有一条数据环或控制环发生故障，那么可以用备用环的一条数据环或一条控制环进行通信；如果备用环上的数据环发生故障，则只使用主环上的数据环和控制环；如果备用环的控制环发生故 障，不影响整个系统的工作，这样就可以有效地实现了系统容错。 

附图说明

图1为本发明拓扑结构示意图。 

图2为本发明的一种动态分配带宽算法流程图。 

图3为空分复用算法示意图。 

图4为容错机制示意图 

具体实施方式

本发明提出一种具有公平路由和带宽可空分复用的双层双环型片上网络拓扑结构，该结构示意图如图1所示，该结构包括IP单元(IP)、交换单元(S)、网络适配器(NA)和链路单元。IP单元(IP)可以是处理器、存储单元、FPGA、DSP等，各个IP单元(IP)既可以是同质的，也可以是非同质的；既可以是细粒度的，也可以是粗粒度的。交换单元(S)实现各IP单元(IP)的相互通信，采用时分复用和优先级相结合的机制，可实现公平路由和带宽的空分复用，同时有效的避免了拥塞和死锁。网络适配器(NA)是IP单元(IP)和交换单元(S)之间的接口，使不同的IP单元(IP)都可以连接到相同接口的交换单元(S)同时将网络通信和IP单元(IP)的计算功能分离。链路单元将IP单元(IP)、交换单元(S)和网络适配器(NA)依据一定的结构进行连接，该结构为双层双环型结构，第一层为主干环网结构，第二层称为子网络结构。主干环网结构又分为两组环网，其中有一组环网为主环，另一组为备用环，备用环用于片上网络结构的容错机制。每组环中包含一个控制环和一个数据环，在图1中虚线标识的环为控制环，实线标识的环为数据环。控制环采用包交换的形式交换IP单元(IP)间路由、链路错误和差错控制信息，数据环采用电路交换方式进行IP单元(IP)间的数据通信。子网络结构可以根据不同的应用，采用不同的结构形式。本发明的子网络包含了线性结构、总线结构和星形结构。一般而言，尽量将信息交换量大的IP单元(IP)放在一个子网络中，因此子网中的IP单元(IP)信息交换量比较大，而子网通过主干网进行数据交换的信息量相对子网络较少。 

该发明的交换单元(S)采用时分复用和优先级相结合的机制，可实现公平路由和带宽的空分复用，在链路带宽有剩余的情况下，保证优先级高的IP单元(IP)可以获得更多的带宽，多个IP单元(IP)可以同时发送数据，同时有效 的避免了拥塞和死锁。为叙述方便，下面将主环上的数据环称为正环，备用环上的数据环称为反环。下面对空分复用算法进行描述： 

1、IP单元(IP)编码与优先级：为链路上的每个IP单元(IP)分配一个二进制数，该二进制数代表了IP单元(IP)的编码，也代表了IP单元(IP)的优先级。这样，优先级与IP单元(IP)编码一致，优先级越高，IP单元(IP)编码越小。在比较IP单元(IP)优先级时，占用下个数据时隙IP单元(IP)的优先级变成最高优先级，其它IP单元(IP)的优先级自动降1后排列。例如，假设一个环路一共有16个IP单元(IP)，每个IP单元(IP)的编码依次为0，1，2，...，15，如果占用下个数据时隙的IP单元(IP)为3，则优先级排列顺序为：3，0，1，2，4，...，15； 

2、路径：路径定义为从源IP单元(IP)到目标IP单元(IP)之间IP单元(IP)的有序集合。环网上第p个IP单元(IP)发送数据的目标地址为q，那么，根据编码原则，第p个IP单元(IP)正向发送数据的IP单元(IP)集合为： 

set^p＝{addr|(p<addr<q)∧(p<q)‖(addr>p∨addr<q)∧(p<q)}， 

反向发送数据的IP单元(IP)集合为： 

set^p＝{addr|(q<addr<p)∧(p>q)‖(addr<p∨addr>q)∧(p<q)}； 

3、正环和反环的目标IP单元(IP)集合：假设在IP单元(IP)p之前的控制时隙中，在正向环上已经建立i条路径，在反向环上已经建立j条路径。定义D_i＝{e_i}为第i条路径结束元素的集合，在此定义：正环目标IP单元(IP)集合： 

reward_den_set＝{node|node∈setⁱ∧i<＝p-1∧node∈D_i} 

反环目标IP单元(IP)集合： 

forward_den_set＝{node|node∈set^j∧j<＝p-1∧node∈D_j} 

且有：

4、目标IP单元(IP)：如果p∈reward_den_set或者p∈forward_den_set，那么IP单元(IP)p是正环或者是反环目标IP单元(IP)； 

5、IP单元(IP)p在正环上转发的条件是：假设集合A_i＝{s_i，e_i}为第i路径开始与结束元素的集合，如，p是正环方向的 转发IP单元(IP)；

，那么p是反环方向上的转发IP单元(IP)； 

6、IP单元(IP)p在正环上可以发送数据的条件是：如果set^p集合中所有的IP单元(IP)之间的正环方向的链路正常且  $\&ForAll;i<p-1$ ，

IP单元(IP)p在反环上可以发送数据的条件是：如果set^p集合中所有的IP单元(IP)之间的反环方向的链路正常且  $\&ForAll;j<p-1$ ，

7、带宽以正环优先分配：也就是说，在正数据环无法建立某个IP单元(IP)的通信路径，然后在反环上建立通信路径。 

图2以IP单元(IP)p为例说明了这种动态分配带宽算法的过程： 

1、等待第p个数据时隙，如果为第p个数据时隙则进入过程2； 

2、收集第p个IP单元(IP)及比p优先级高的IP单元(IP)信息以及IP单元(IP)p下个数据时隙拟建立的链路信息； 

3、根据上述算法确定IP单元(IP)p是否满足正环发送数据条件，如果满足，p在正环发送数据，进入过程5，如果不满足，直接进入过程4； 

4、根据上述算法确定IP单元(IP)p是否满足反环发送数据条件，如果满足，p在反环发送数据，进入过程5，如果不满足，直接进入过程5； 

5、根据上述算法确定IP单元(IP)p是否是正环转发IP，如果是，p在正环上转发数据，进入过程7，如果不满足，直接进入过程6； 

6、根据上述算法确定IP单元(IP)p是否是正环接收IP，如果是，p在正环上接收数据，进入过程7，如果不满足，直接进入过程7； 

7、根据上述算法确定IP单元(IP)p是否是反环转发IP，如果是，p在反环上转发数据，过程结束，如果不满足，直接进入过程8； 

8、根据上述算法确定IP单元(IP)p是否是反环接收IP，如果是，p在反环上接收数据，过程结束，如果不满足，直接过程结束； 

该算法有以下优点： 

1、采用时分复用的方法，保证每个IP单元(IP)都有机会发送数据，因此，保证了环路每个IP单元(IP)不会产生饥饿的现象； 

2、采用带宽空分复用，多个IP单元(IP)可以同时发送数据。在链路有空闲的情况下，保证优先级高的IP单元(IP)有更多的带宽。图3给出了环上的IP单元(IP)之间的通信链路。如图3所示，IP单元(IP)3占用发送时隙， 因此，它的优先级最高，算法先满足IP单元(IP)3的带宽请求，然后按优先级对其它IP单元(IP)的带宽请求进行分配。该图3中，I链路用于正环通信，而II链路用于反环通信。IP单元(IP)1的双向链路用于数据的转发，而IP单元(IP)2中一条链路用于数据接收，而另外一条链路用于数据发送。 

3、每个IP单元(IP)知道全局的路由信息，预先建立通信链路。因此，可以保证不出现死锁、活锁以及拥塞现象。 

4、数据环上的IP单元(IP)不需要缓存； 

该结构中的主干环网结构分为两组环网，其中有一组环网为主环，另一组为备用环，备用环主要用于片上网络结构的容错机制，主环和备用环都包括一条数据环和一条控制环。在链路正常情况下，为了提高链路效率备用数据环也用于传递数据，备用控制环处于空闲状态。如果主环上有一条数据环或控制环发生故障，那么可以用备用环的一条数据环或一条控制环进行通信；如果备用环上的数据环发生故障，则只使用主环上的数据缓和控制环；如果备用环的控制环发生故障，不影响整个系统的工作，这样就可以有效地实现了系统容错。 

在环路中，每个IP单元(IP)或交换单元(S)都假设有一个检查数据链路和控制链路失效的检错单元。如果检错单元检测到数据链路故障，那么通过控制链路向环路上的所有交换单元(S)、IP单元(IP)广播出错的链路，每个交换单元(S)获取该信息后，通过将链路信息进行重新调度，避免从失效的链路上发送数据；如果检错单元检测主环的控制链路出现故障，那么可以通过另外一条备用控制环路向所有交换单元(S)、IP单元(IP)广播链路故障信息。图4给出了一条控制环路出现故障之后，控制信息倒换到另外一条环路工作的示意图，其中IP单元(IP)2和3之间的主环控制链路出现故障，控制信息无法从IP单元(IP)2向IP单元(IP)3发送，当检错单元检测到该故障后，就通过备用控制环向所有交换单元(S)、IP单元(IP)广播链路故障信息，这时系统自动将控制链路转换为备用环，完成倒换工作。

Claims (3)

1.一种具有公平路由和带宽可空分复用的双层双环型片上系统，包括IP单元、交换单元、网络适配器、链路单元，其特征在于：交换单元采用时分复用、带宽的空分复用和优先级相结合的机制实现各IP单元的相互通信；其算法描述如下：

①IP单元编码与优先级：为链路上的每个IP单元分配一个二进制数，该二进制数代表了IP单元的编码，也代表了IP单元的优先级，这样，优先级与IP单元编码一致，优先级越高，IP单元编码越小，在比较IP单元优先级时，占用下个数据时隙IP单元的优先级变成最高优先级，其它IP单元的优先级自动降1后排列；

②路径：路径定义为从源IP单元到目标IP单元之间IP单元的有序集合，环网上第p个IP单元发送数据的目标地址为q，那么，根据编码原则，第p个IP单元正向发送数据的IP单元集合为：

set^p＝{addr|(p＜addr＜q)∧(p＜q)||(addr＞p∨addr＜q)∧(p＜q)}，

反向发送数据的IP单元(IP)集合为：

set^p＝{addr|(q＜addr＜p)∧(p＞q)||(addr＜p∨addr＞q)∧(p＜q)}；

③正环和反环的目标IP单元集合：假设在IP单元p之前的控制时隙中，在正向环上已经建立i条路径，在反向环上已经建立j条路径，定义D_i＝{e_i}为第i条路径结束元素的集合，在此定义：正环目标IP单元集合：

reward_den_set＝{node|node∈setⁱ∧i＜＝p-1∧node∈D_i}

反环目标IP单元(IP)集合：

forward_den_set＝{node|node∈set^j∧j＜＝p-1∧node∈D_j}

且有：

④目标IP单元：如果p∈reward_den_set或者p∈forward_den_set，那么IP单元p是正环或者是反环目标IP单元(IP)；

⑤IP单元p在正环上转发的条件是：假设集合A_i＝{s_i，e_i}为第i路径开始与结束元素的集合，如果p是正环方向的转发IP单元；

那么p是反环方向上的转发IP单元；

⑥IP单元p在正环上可以发送数据的条件是：如果set^p集合中所有的IP单元之间的正环方向的链路正常且

IP单元p在反环上可以发送数据的条件是：如果set^p集合中所有的IP单元之间的反环方向的链路正常且

⑦带宽以正环优先分配：也就是说，在正数据环无法建立某个IP单元的通信路径，然后在反环上建立通信路径；

链路单元将IP单元、交换单元、网络适配器依据一定的结构进行连接，该结构为双层双环型结构，第一层为主干环网结构，第二层称为子网络结构，主干环网结构又分为两组环网，其中有一组环网为主环，另一组为备用环，备用环用于片上网络结构的容错机制，每组环中包含一个控制环和一个数据环，控制环采用包交换的形式交换IP单元间路由、链路错误和差错控制信息，数据环采用电路交换方式进行IP单元间的数据通信，子网络结构采用线性结构、总线结构或星形结构。

2.如权利要求1所述的具有公平路由和带宽可空分复用的双层双环型片上系统，其特征在于：所述的IP单元是处理器、存储单元、FPGA、DSP之一，各个IP单元既可以是同质的，也可以是非同质的；既可以是细粒度的，也可以是粗粒度的。

3.如权利要求1所述的具有公平路由和带宽可空分复用的双层双环型片上系统，其特征在于：所述的网络适配器是IP单元和交换单元之间接口，使不同的IP单元都可以连接到相同接口的交换单元。

Images