多核系统中NoC通讯架构的关键技术（二）

3  NoC的通讯协议

　　NoC是片上通信基础结构，借鉴网络中的分层思想，NoC设计采用普通的通信分层方法，定义5个协议层：物理层、数据链路层、网络层、传输层和系统层。图5是NoC一个典型的层次结构。

　　（1）物理层。物理层实现连接处理器资源与网络的链路宽度和链路方向，因此带宽负载能力、数据包大小及在两节点之间的传输延迟等物理信息都是检验物理层设计质量的评估标准。片上网络的物理层通讯采用握手协议完成，而握手协议可以分为同步协议与异步协议两种。图6为同步握手协议的示意图，图6（a）为物理通道信号。与计算机网络多采用串行通讯方式不同，由于片上连线资源丰富，NoC可以使用并行通讯方式。因此同步方式和异步方式的Data信号宽度n，为》1的整数。握手协议需要请求信号Req和应答信号Ack完成通讯双方握手操作，除此以外，同步方式需要时钟信号Clock同步其余信号。

　　（2）数据链路层。数据链路层的功能就是将信息的每一个字准确地从一个节点传输到相邻的节点上，定义了资源节点、通讯节点以及两个通讯节点之间的传输协议，保证物理连接之间可靠的信息传输。由于两个相邻的节点可能以异步传输模式工作，因此需要考虑数据的出错检测与纠错外，数据链路层还需要注意硬件同步问题，同时实现数据编码和更好地控制数据传输率以及功耗管理。物理层和数据链路层均与工艺有关，即如采用新工艺，必须重新定义这两个层。

　　报文格式的定义如图7所示。报文由若干个帧组成。帧可分为头帧、尾帧和实体帧3类。所有3类帧的组成相同，如图8所示，均由头标识位，尾标识位和帧负载位组成。

　　（3）网络层。负责建立互连链接以及路由策略，因此片上网络中各传输路径的利用情况，在较大程度上取决于网络层的设计结果。不同的链接建立方式在不同的网络拓扑结构中性能各不相同，因此针对不同的应用和片上网络结构，需要制定相应的链接建立方式。

　　（4）传输层。负责监视网络流量、对数据包进行拆分及组装，因此数据包发送速度、掉包率以及解决方案是衡量传输层设计质量的标准。另外传输层对网络传输路径上的流量控制，直接影响到数据传输的吞吐量，这也是衡量传输层性能的指标。

　　（5）系统层。该层的重要功能包括信息的同步和管理、接收端数据格式的转换以及一些与应用相关的功能等。

4  路由算法

　　路由策略的研究是NoC中的一个重要内容，在给定的网络拓扑结构下，决定数据包在网络中的投递路径。其目的是使数据包的网络延时、数据吞吐率、数据包投递所需的功耗和可靠性都达到指标。

　　NoC路由算法的分类：依照路由结果的计算位置、路径选择方式、路径距离等方法，由算法决定数据包在网络结构中传输的方向，把传输路径集合限制为合理的路径子集。如果消息的路由完全由它的源和目的地址决定，与网络中其他流量无关，这种路由算法称为确定性路由，对于每一个源节点和目的节点之间，采用确定性路由得到一条路径计算结果。而自适应路由算法是允许路径上的其它流量影响数据包的路由策略，对于每一对源和目的节点，算法可根据网络的拥堵状况给出多条的路径计算结果。路由计算模块是一个相对独立的处理单元，通常需要根据不同的算法改变交换节点中的路由计算模块，就可以实现NoC路由算法的改变。

　　维序路由采用较为广泛的路由算法，应用了确定性路由的方法，数据包无论其路径上的链路是否阻塞都要沿该路径走下去。该算法的思想是数据包先在低维上投递，直至数据包在该维度上相对于目的节点的偏移量为0，然后转移到下一维度以相同的模式进行投递，直到达到目的节点。因此维序路由是分布式路由，也是一种较小距离路由。

　　图9是二维Mesh网格中维序路由的一种算法，称为xy路由。表示不同源节点、目的节点下维序路由算法得出的路由路径结果以及在二维Mesh网络中，路由路径的可能转向。数据包先在x维度上投递，然后在y维度上投递，直至达到目的节点，该路由算法不会出现死锁现象。

　　5  交换技术

　　交换技术是按照某种方式动态地分配传输线路和接口的资源，是影响网络性能，决定交换节点结构的重要技术。NoC中运用的交换技术可分为两类：面向连接的和无连接的。面向连接的交换方式主要有电路交换，无连接的方式主要有存储交换、虚切通和虫孔交换。

　　（1）电路交换（Circuit Switching）是一种面向连接的交换机制。在通信之前，要通过信息头按照路由规则选路，然后建立路径，同时预定所经过路径的信道资源。目的端在成功收到此信息头后将沿原路返回一个应答，源节点收到此应答后便开始传输数据。数据传输之前源节点和目的节点之间建立直接的连接路径，一旦数据开始传输，消息的传输不会阻塞。数据部分在网络中传输时将独占此路径中各段链路的整个带宽，无需做路由选择。

　　（2）存储交换（Store and Forward Switching）是先将数据完全存储，然后进行路南决策，最后再转发到下一节点的一种交换机制。NoC中的存储交换主要以分组为流控单元，每个分组有一个分组头，含有源、目的节点地址以及其它控制信息。路由节点接收到一个分组后，先将整个分组存储在缓存器中，从分组头中获取路由信息由路由器的路南决策单元选择一条输出通道后，置位交叉矩阵中的内部连接，如果下一路由节点中有足够的空间存放此分组，就将此分组转发到下一路由节点。存储交换的优点是通道只在一个数据包需要传输的时候才被占用。

　　（3）虚切通交换（Virtual Cut-throuth Switching）将分组进一步划分为更小的片，并按顺序排好，将所需的路由信息放入第一个片中，在无阻塞的情况下，路由节点收到头片后，从中读取路由信息，然后由路由决策单元负责选路，如果输出通道空闲，则将头片转发出去，后续片紧随头片向前路由，从而在较大程度上缩小了存储交换的时延。由于在任何一个节点上都可能有多条消息被阻塞，每一个节点都要提供能存储所要通过他的数据的存储空间。所以每一个节点都需要较大的存储空间。

　　（4）虫孔交换（Wormhole Switching）是目前NoC中的主流交换机制。它和虚切通交换的思想基本相同，只是二者在发生阻塞时所表现出的行为不同。在虫孔交换中，数据包也被细分成片，以流水的方式在网络上传输，并且允许一个分组由一个片组成。头片中包含路由信息，其他数据片都跟随头片在他确定的路径上流动，就像虫子一样。当头片发生阻塞时，分组中的所有片都将停止前进，头片缓存在当前节点，数据片就地缓存在其后的若干个中间节点中。每个路由节点只需提供一个片大小的缓存资源。虫孔交换对数据包大小和路径长度不敏感，资源占用少，实现代价小，且效率高，适合NoC使用。虫孔交换的示意图如图10所示。

　　虫孔交换结构的处理过程如下：数据包的片段到达虫孔交换结构，存储在输入通道缓存单元中，并进行路由计算。得到路由信息后，数据包提出传输请求，仲裁器根据请求进行带宽资源分配，一旦该数据片被允许传输，它将被交换到目的端口并投递出去，直到数据包的最后一个片段离开交换节点。根据此处理过程，虫孔交换电路的结构如图11所示，由缓存单元、路由计算单元、仲裁请求管理单元、交换分配和交换阵列5部分组成。

　　在VLSI实现中，NoC交换节点多采用流水结构设计，一般流水处理结构分为路由计算、通道分配、交换分配、数据交换和传输等5级。在NoC设计中，总是希望得到良好的网络性能，从交换节点设计角度考虑，减少交换结构的流水处理级数是缩短网络延时的有效方法，流水处理级数越少，数据包通过交换节点的时间就越短。

　　不同的NoC交换技术，对应着不同的网络性能和实现代价，要根据实际要求进行选择。

6  片上网络面临的挑战

　　为提高片上网络的资源单元处理速度，降低通信通路间以及资源单元互连问的通信延迟，片上网络的设计面临以下几方面挑战：

　　（1）任务分配与调度，片上网络将通信任务分配到合适的处理单元，并且尽量以最佳方式为这些任务进行排序，此步骤是典型的多处理器系统的关键设计步骤。

　　（2）网络分配，包括处理单元映射与路径分配。处理单元映射对系统功耗起着决定性的影响，路径分配则是对执行性能产生直接影响。

　　（3）动态网络最佳化路径分配，对静态通信路径分配时，由于对即时性的要求较低，因此只要对现有的最短路径进行确认即可。但对于片上网络的动态通信而言，需要将计算机网络中的动态网络调度算法进行调整，应用到片上网络应用中。

　　7 结束语

　　NoC通讯方式是目前多核系统通讯结构中研究最为广泛的结构，也使得NoC成为当前研究热点，部分大学、研究所以及工业界的研究单位正积极从事NoC研究工作，但是NoC依然面临着许多技术挑战。在实际应用中，应根据系统的实际要求，选择合适的拓扑结构和交换技术，避免一味追求最新的技术而带来其他的问题。