功耗优先的NoC通讯架构测试方法

欧阳一鸣, 黄 河, 梁华国

(1.合肥工业大学 计算机与信息学院,安徽 合肥 230009;2.合肥工业大学 电子科学与应用物理学院,安徽 合肥 230009)

传统基于共享总线的片上系统,其通讯能力已经不能满足未来SoC(System on Chip,简称SoC)设计的要求。为此,计算机网络通讯技术被移植到芯片设计中来,以分组交换作为基本通讯技术,采用全局异步-局部同步GALS(Globally Asynchronous Locally Synchronous,简称GALS)通讯机制,彻底解决了片上通讯的瓶颈问题。这就是片上网络——NoC(Network on Chip简称NoC)。NoC不仅具有良好的空间可扩展性,还支持并行的多重通讯及提供更高的带宽。

1 NoC的相关知识

NoC的通讯架构是由控制数据传输的router和互联网络中各 router之间的channel构成,NoC的拓扑结构主要有：2D-Mesh、T orus和Fat-T ree等,本文提出的测试方法是针对2D-Mesh结构,3×3的 2D-Mesh结构片上网络如图1所示。

图1 3×3的2D-Mesh结构模型

本文所涉及的有关基本概念如下：①节点。就是对片上网络中路由器的简称。②数据包。网络中传输的消息通常由头部、传输数据和尾组成。由于通讯效率的需要,再将传输数据分割成更小的数据段,在测试模式下,测试向量加上包头包尾封装成一个数据包。③XY路由算法。基本思想是数据包在向目的节点发送的过程中,先在X方向上发送,等到达目的节点所在列后,再在Y方向上发送直至到达目的节点。④Y X路由算法。基本思想是数据包在向目的节点发送的过程中,先在Y方向上传送,然后再在X方向上传送。⑤曼哈顿距离。假设片上网络中节点P1坐标为(x1,y1),节点P2坐标为(x2,y2),那么该对节点间的曼哈顿距离为|x1-y1|+|x2-y2|。⑥曼哈顿路径。指片上网络中任意两节点间,距离长度等于横向距离与纵向距离之和,即距离值等于曼哈顿距离的一条路径。⑦曼哈顿路径数。指片上网络中任意两节点间的曼哈顿路径总数,可由(1)式算出,即

其中,m表示NoC的行数;n表示NoC的列数。

2 NoC测试

(1)针对NoC通讯架构的测试方法。文献[1]提出了用于测试2D-Mesh结构NoC的可扩展BIST方式,该方法几乎适用于各种故障检测,并能定位出故障点,根据反馈的故障信息,重新对整个NoC进行配置;而文献[2]则提出了针对2D-Mesh结构中路由器里多路选择器的外建自测试方法,该方法主要用于检测多路选择器和FIFO中存在的固定故障,以及延时故障、相邻链路中的断路和短路故障;对于非规则结构的片上网络,文献[3]提出了增加测试外壳,采用并行的测试方式,对片上网络的路由器进行测试。

(2)针对IP核的测试调度方法。文献[4]提出了一种NoC测试端口位置和数量的优化选取方法,既能高效地完成对核的测试,又能有效地避免因测试带来的器件损坏;而文献[5]提出的方法是基于IP核的优先权调度,即一旦某个IP核获得调度,就必须等到属于该核的所有向量都施加完毕,才释放所占用资源。

3 针对2D-Mesh通讯架构的测试方法

3.1 基于洪泛的穷举测试方法

文献[6]提出了基于洪泛的穷举测试方法,其思想是：借鉴普通通信网络中的洪泛思想,即在片上网络中,由测试访问源节点发送一个数据包给其所有邻接节点。而网络中每个节点在接收到数据包后,将向除接收端口以外的所有端口,复制转发数据包。为防止数据包在网络中无限制地复制转发,数据包包头被设置了跳数计数域,跳数值设为两测试访问节点间曼哈顿距离,即最短路径所需的跳数。每经过一个节点,跳数减1,然后复制转发。当跳数为零时,没有到达目的节点则丢弃该数据包。

3.2 基于洪泛的伪穷举测试方法

在基于洪泛的穷举测试方法的基础上,文献[7]提出了基于洪泛的伪穷举测试方法,其思想是：类似洪泛思想,只是每个通讯节点将它所接收到的数据包,同时以YX路由算法和XY路由算法向目的节点转发,所以每个节点只需要将所接收的数据包复制2份向其邻接节点转发,这样相对穷举方法,可以降低功耗,缩短测试时间,但是网络中产生的数据包数量仍然较大。

3.3 功耗优先的伪穷举测试方法

由于NoC的电路规模十分巨大,其测试功耗比正常工作模式下的功耗高很多,因此如何降低或限制测试片上系统时的通讯功耗,就成为设计者设计测试方法时越来越关心的问题。文献[8]指出：一个路由器的功耗主要分成3部分,即缓冲区功耗、控制逻辑功耗和交换开关功耗。其功耗计算公式为：

其中,m表示一个路由器中缓冲区的数量;n表示对整个片上网络中对路由器的采样数;Pcrossbar为交换开关的功耗;Pcontrol为逻辑控制的功耗。

而2D-Mesh结构中各路由器的结构基本一致,在一个测试过程中只注入一个数据包,这样各路由器转发数据包内容完全相同,其产生的功耗也一样,因此可以得出测试过程中的总功耗跟网络中产生的数据包数量成正比。

从上述2种测试方法可以得出,测试方法决定整个网络中的数据包数量,在整个测试过程中中间节点所产生的冗余数据包最多,因此本文提出了功耗优先的伪穷举测试方法。

要实现本方法,需要根据网络中各节点的不同位置,将它们重新定义：

(1)边缘节点。指2D-Mesh结构中,邻接节点数少于4的节点。在坐标系中表现为X坐标值等于0或n,或者Y坐标值等于0或m。如图2中坐标值为(0,0)、(2,0)就是边缘节点。

图2 4×4的2D-Mesh结构模型

(2)中间节点。指2D-Mesh结构中,邻接节点数为4的节点。在坐标系中表现为X坐标值大于0,且小于n,同时满足Y坐标值大于0,且小于m。如在图2中节点坐标值为(1,1)、(2,1)、(1,2)和(2,2)等节点均为中间节点。

(3)测试访问节点。指与测试处理单元相连的节点,如在图2中节点(0,0)、(3,3)被选为测试访问节点 TAS(Test Access Switch,简称TAS)。

(4)基本思想。当片上网络处于测试状态时,选取2个对角的边缘节点为测试访问节点TAS,同时以对方为目的节点发送数据包,每个节点接收到测试数据包后,判断自己所处位置。如果是边缘节点,则同时以XY和Y X 2种方式转发数据包。如果是中间节点,则再判断数据包来自哪个方向上端口。如果是来自X方向上,则采用XY路由算法转发;如果是来自Y方向上,则采用YX路由转发。在到达目的节点后,所接收到的数据包数应当等于本测试状态下的对角边缘节点间的曼哈顿路径数。测试状态下的对角边缘节点曼哈顿路径数计算公式为：

K(m,n)=m+n-2 (3)其中,m、n分别表示要测试2D-Mesh结构NoC的行数和列数。如果电路中存在链路故障,则数据包数量将小于测试状态下的曼哈顿路径数。

3.4 节点所执行的路由算法描述

对所要测试的片上网络,先任意选择一个对角节点为坐标原点。那么判断一个节点S(Xs,Ys)位置的条件就是：当|Xs|=0或n,或|Ys|=0或m时,S为边缘节点;当0＜|Xs|＜n,且0＜|Ys|＜m时,S为中间节点。其中,m为行数;n为列数;E、W 、S和N 分别表示东、西 、南、北4个方向的通道。

算法：测试状态下,每个节点所执行的路由算法。输入：当前节点坐标(Xcurrent,Ycurrent)和目的节点坐标(Xdest,Ydest)。输出：选择输出的通道Channel。过程如下：

该算法的伪码图描述,如图3所示。

图3 算法伪码图

3.5 测试数据包总数的计算

本方法主要是基于节点在网络中不同位置,而采取不同路由算法的。计算数据包总数分成如下2个部分。

(1)计算边缘节点产生的数据包总数。现在以图2所示的2个对角边缘节点为例,该节点接收到数据包后,X、Y坐标值为0的边缘节点,向目的节点以XY和YX路由算法同时复制转发数据包,可推导出(4)式。但是X坐标值为n和Y坐标值为m的边缘节点,与目的节点同行或同列,则只执行XY或YX算法。这样可推导出(5)式,即

(2)计算中间节点产生的数据包。边缘节点在XY方向转发的数据包和在Y X方向的数据包都要经过中间节点,而且这些数据包均只复制一份转发。这样,根据中间节点区域的规模大小可计算得出数据包总数为：

测试处理单元向测试访问节点发送一份数据包,同时由于2个测试访问节点是互为目的节点对发数据包,最终得到一个测试过程中所产生的数据包总数的计算公式为：

4 实验结果比较

本文方法是在OPNET仿真平台上进行模拟并得出实验结果的,文献[9]介绍了怎样使用OPENET作为NoC的仿真平台,现从以下几个方面评价本文方法。

4.1 测试数据包数量的统计

采用基于洪泛的伪穷举测试方法和功耗优先的伪穷举测试方法比较,如图4所示。

图4 采用2种方法所产生的测试数据包总数比较

从图4可以看出,随着NoC的规模增大,本方法所产生的数据包总数增长得较为缓慢,而基于洪泛的伪穷举测试方法,则随着片上网络规模增大,所产生的数据包数量增长较快。这说明本方法在测试过程中产生数据包数量较少,有效地减少了冗余的测试数据包。

4.2 测试功耗

文献[10]指出,对于2D-Mesh结构的NoC,其总通讯功耗是最小的,而在2个节点之间发送每一位数据所需的平均功耗是由其曼哈顿距离决定的。这样,可以用交换数据包数量和通过的路径长度估算出功耗大小,其计算公式为：

其中,e表示从一个通讯节点向它的邻节点发送一个数据包所需要的平均功耗,可以由(2)式计算得出。

采用2种测试方法在不同规模NoC中所产生功耗的比较,见表1所列。

表1 2种测试方法在不同规模NoC中所产生功耗的比较

本文所提出的方法正是以降低测试功耗为优先考虑的目标,通过减少产生多余的测试数据包数量,达到降低总测试功耗的目的。从图4可以看出,在网络中分别采用了伪穷举测试方法和功耗优先的伪穷举测试方法,所产生总测试数据包数有较大差别,而表1所列则反映了2种方法在测试功耗上的差别。本文提出的测试方法在测试功耗方面有了很大的降低,随着NoC规模的增大,降低得越多。这是因为在网络中产生的复制转发数据包得到了有效减少,从而降低整个网络中的测试功耗。

4.3 测试时间

根据基于洪泛的伪穷举测试方法中的定义,测试时间的计算是从一个测试访问节点发送一个数据包开始,到最后一个测试数据包被目的节点接收。文献[7]给出测试时间的计算公式为：

从(9)式可以看出,整个片上网络的测试通讯功耗与产生的复制转发数据包成正比,数据包总数越少,总测试功耗就越低。

采用基于洪泛的伪穷举测试方法和本文所提出的功耗优先的伪穷举测试方法,对不同规模NoC测试所需时间的比较,如图5所示。从图5可以看出,本文所提出的方法比基于洪泛的伪穷举方法所需要的时间有较大的减少,并且随着NoC的规模增大,减少就更多。

图5 测试时间的比较

4.4 对比分析

基于洪泛的伪穷举测试方法,是让每个节点都采取同一种方式转发,即同时以XY和YX路由算法转发数据包,这样中间节点就会产生很多的冗余数据包,其包总数计算公式为：

而本文所提出的方法,把整个网络划分成边缘节点区和中间节点区。边缘节点在接收到数据包后,同时以XY和Y X路由算法向目的节点转发数据包,而中间节点经过端口判断后,再执行相应的路由算法发送。这样由边缘节点控制数据包走向,中间节点判断后,再转发1份数据包。其中间节点产生数据包数就大大减少,整个网络中数据包总数也得到减少,这可由(7)式计算得出。所以,本方法在降低测试功耗方面有显著改善。

5 结 论

NoC这种新体系结构的提出,解决了总线结构中存在的问题,对其测试也与总线结构SoC所采用的方法有所不同。而其中2D-Mesh结构特点是,整个网络的总功耗跟网络中所产生数据包的数量成正比,因此本文的基本思想是采用合理的测试方法,在保证测试效果的同时,使整个网络中产生的数据包总数降低,从而降低了总功耗。

[1]Petersen K,Oberg J.T oward a scalable test methodology for 2D-mesh network-on-chips[C]//Design Automation and Test in Europe (DAT E).Nice, France,2007：367-372.

[2]Raik J,Govind V,Ubar R.An external test approach for network-on-a-chip switches[C]//15th Asian Test Symposium(AT S).Fukuoka,Japan,2006：437-442.

[3]Hosseinabady M,Banaiyan A,Bojnordi M N,et al.A concurrent testing method for NoC switches[C]//Design Automation and Test in Europe(DATE).Munich,Germany,2006：1171-1176.

[4]欧阳一鸣,冯 伟,梁华国.功耗限制下的NoC测试端口的优化选择方法[J].计算机应用,2008,28(4)：204-206,209.

[5]Cota E,Liu C.Constraint-driven test scheduling for NoC-based systems[J].IEEE T ransactions on Computer-Aided Desig n of Integrated Circuits and Systems,2006,25(11)：2465-2478.

[6]Sedghi M,Koopahi E,Alaghi A,et al.An ex haustive test strategy based on flooding routing fo r NoC switch testing[C]//IEEE East-WestDesign and TestSymposium(EWDTS).Yerevan,A rmenia,2007：262-267.

[7]Sedg hi M,Koopahi E,Alaghi A,et al.An NoC test strategy based on flooding with power,test time and coverage considerations[C]//V LSID 2008,21st International Conference.Hyderabad,India,2008：409-414.

[8]Guindani G,Reinbrecht C,Raupp T,et al.NoC power estimation at the RT L abstraction level[C]//IEEE Computer Society Annual Symposium on VLSI.Montpellier,France,2008：475-478.

[9]Wu Ning,Ge Fen,Wang Qi.Simulation and performance analysis of network on chip architectures using OPNET[C]//7th International Conference on ASIC.Guilin,China,2007：1285-1288.

[10]Hu J,Marculescu R.Energy-and performance-aware mapping for regular NoC architectures[J].IEEE T ransactions on Computer-Aided Desig n of ICs and Systems,2005,24(4)：551-562.