片上网络交换机制的研究

　　1．引言

　　集成电路技术在过去的几十年中得到了飞速的发展，在单一芯片上可集成的晶体管数目遵循着摩尔定律不断增加，片上通信机制也经历了从点对点到总线结构的转变。但是在实际的操作中，总线结构也暴露出了相当多的技术问题，比如，可扩展性差、定时困难、可重用性不佳等，并且也不具备并行通信能力。随着片上器件数目的进一步增加，为了使各部件之间更好的通信，总线结构已经不能胜任，芯片设计者需要寻求一种新的结构来解决片上器件互连的问题。于是，人们纷纷将目光聚焦于运用网络技术来解决芯片中器件互连的问题上，从而使片上网络成为了学术界新的研究热点。

　　对开销和能耗上的严格限制是片上网络与并行计算机、互联网络及计算机网络的最大不同。总的说来，片上网络具有芯片面积受限、低时延、高吞吐和低能耗等技术要求。交换机制是影响这些参数的一个重要因素，笼统的说，它定义了消息在片上网络中传递的方式，并规定了沿输出端口将消息转发出去的时机，其中也包含了对所传输消息格式的规定。路由算法的制定和路由器结构的设计，以及死锁、活锁、饿死等问题都在很大程度上依赖于所选用的交换机制。所以，对片上网络交换机制的分析和研究相当重要。

　　片上网络节点的一般结构如图1所示，资源通过网络接口(RNI)连接到本地路由器上，再由路由器连入网络。网络分界线在网络接口与本地路由器之间，网络部分采用统一的时钟，而资源可以根据功能的不同而采用任意的时钟，网络接口实现两种时钟的协调工作。资源一般通过网络接口以分组的形式将消息注入给网络，在网络中数据的传递形式则由所选用的交换机制而定。

　　片上网络中运用的交换机制主要可以分为两类：面向连接的和无连接的。面向连接的交换机制主要有电路交换，无连接的机制主要有分组交换、虚切通和虫孔交换。本文将分别对这几种交换机制的工作原理进行描述，并对各种交换机制在片上网络中的优缺点进行分析与比较。

　　2．现有片上网络交换机制

　　2.1 电路交换

　　电路交换最早产生于公共交换电话网(PSTN)，是一种面向连接的交换机制。在开始通信之前，一般要通过一个信息头按照一定的路由规则选路，然后建立路径，同时预定所经过路径的信道资源。收端在成功收到这个信息头后将沿原路返回一个应答，发端收到这个应答后便开始传输数据。数据部分在网络中传输时将独占此路径中各段链路的整个带宽，并且不需要再做路由选择。当通信结束后，发端向收端发出终止通信的要求，并沿路拆链，释放对各段链路的使用权。这就是电路交换的主要工作过程，如图2所示，白色区域代表数据。

　　采用面向连接的方式可以保证片上网络一些特定业务的服务质量。在多媒体业务中，消息一般数量较少，但消息较长，所以采用电路交换方式较有优势。因为当消息较长时，数据部分的传输时间远大于路径建立的时间，并且由于独占整个物理带宽，因此可以保证高吞吐和低时延。目前已经提出的片上网络模型，如AEthereal，NOSTRUM和MANGO等都用到了这种面向连接的思想来提供有保障的服务。采用电路交换的另一个好处是不需要在路由节点中添加缓存资源，这可以在很大程度上减小面积。传统电路交换的一个缺点是一条链路只能被一个预留通道的应用所使用，而采用时分复用的虚电路方式可以很好的解决这个问题。这种面向连接的交换机制采用异步通信，很好的解决了片上同步问题。然而对于尽力而为的业务而言，这种面向连接的电路交换并不适用，因为尽力业务中的消息较短，且通信较频繁，建立路径的时间开销将不可容忍，同时也会消耗过多的能量。

　　2.2 分组交换

　　分组交换是先将数据完全存储，然后进行路由决策，最后再转发到下一节点的一种交换机制。它是在片上网络中最早使用的一种交换机制，片上网络中的分组交换主要以分组为流控单位，每个分组的大小可以不等，并且每个分组有一个分组头，存有源节点地址，目的节点地址以及其它一些控制信息。路由节点接收到一个分组后，先将整个分组存储在缓存器中，从分组头中获取所需的路由信息，由路由器的路由决策单元选择一条输出通道后，置位交叉矩阵中的内部连接，如果下一路由节点中有足够的空间存放此分组，就将此分组转发到下一路由节点。其工作原理如图3所示。

 　　从图3中可以看出，分组交换的时延与跳数成正比，因此它无法很好的适应网络规模的扩展。并且在每个路由节点中要提供至少一个分组大小的缓存资源，因此会使芯片面积增加。而且每存储转发一个分组，路由节点中的所有缓存器都要参与工作并消耗能量。同时，如果两节点间传输的是多媒体业务，则一般希望分组之间的顺序不发生变化，且要求较低的抖动范围，而由于每个分组独立路由，不同分组在网络中可能经历不同的路径，因此无法保证收端接收顺序与发送顺序相同，也就是所谓的乱序现象，又由于各分组到达时间无法预测，因此又会产生抖动。所以分组交换不能提供有保证的服务，而只能提供尽力而为的服务。

　　2.3 虚切通交换

　　虚切通交换将分组更进一步划分为更小的微片(flit)，大小通常为若干个比特，并将所有的微片按顺序排好，将所需的路由信息放人第一个微片中(称作头微片，后续微片称为数据微片)。由于路由信息只包含于头微片中，所以路由节点没有必要等整个分组都接收完以后再进行转发。在无阻塞的情况下，路由节点收到头微片后，从中读取路由信息，然后由路由决策单元负责选路，如果输出通道空闲，则将头微片转发出去，后续微片紧随头微片向前路由，从而大大缩小了分组交换的时延。

　　当头微片所请求的输出通道全忙时，头微片就地缓存在中间节点，随后的数据微片也依次前往并缓存在该节点中，如果阻塞的时间足够长，则整个分组的微片都将存放在该中间节点中，因此像分组交换一样，中间节点也要提供至少一个分组大小的缓存资源。

　　虽然运用虚切通和分组交换的路由节点缓存器大小相同，但运用虚切通交换机制的芯片面积要小于运用分组交换的芯片面积。这是因为分组交换需要“整存整取”，所以在路由器中需要加入一个复杂的分组结束探测装置来接收变长度的分组。在没有发生完全阻塞的情况下，虚切通交换只激活一个或几个微片大小的缓存资源，而分组交换要激活全部的缓存资源，因此在吞吐量相同的情况下，虚切通机制的能耗低于分组交换。

　　2.4 虫孔交换

　　虫孔交换是当今片上网络中的主流交换机制。它和虚切通交换的基本思想大体相同，只是二者在发生阻塞时所表现出的行为不同。在虫孔交换中，微片的种类分为头微片，数据微片和尾片，并且允许一个分组只由一个微片组成。

　　当头微片发生阻塞时，分组中的所有微片都将停止前进，也就是说发生阻塞时头微片缓存在当前节点，数据微片就地缓存在其后的若干个中间节点中。每个路由节点只需提供一个微片大小的缓存资源。在无竞争的情况下，虫孔交换和虚切通交换的时延性能基本相同，并且可以通过在每个路由节点适当增加缓存数量来进一步提高吞吐量。优良的时延性能、较小的缓存要求以及大吞吐量是虫孔交换最突出的优点。虫孔交换也有自身的一些缺点，像分组交换一样，虫孔交换也是一种无连接的交换机制，不能运用到消息较长的多媒体应用当中。当发生阻塞时，虫孔交换中的各个微片将会就地阻塞，从而使信道相关性扩展到了多个相邻的节点，并且将大大增加其它分组被阻塞的可能性，因此使死锁问题变得更加复杂，并且在网络负荷较重时，时延将变得不可预测。图4示意了被阻微片导致其它分组无法前进的例子。在图中，分组A的头微片被分组B的数据微片阻挡，导致A的所有微片就地阻塞，从而进一步阻塞了请求2号路由器缓存资源的分组C。可以运用虚信道流控技术缓解上述阻塞问题，在一定程度上提高虫孔交换机制的吞吐量。

　　为了更进一步提高虫孔交换的时延和吞吐性能，研究者针对片上网络的特点又提出了一些改进机制。其中一种较具代表性的方案是在头微片和数据微片的传输期间使用不同的时钟。由于在虫孔交换机制中，只有头微片通过中间节点时才需要进行路由决策，而数据微片只需要简单的跟随前面的微片向前“蠕动”即可，也就是说这两种动作的“节拍”是不相同的。因此可以考虑在头微片传输时使用正常的时钟，而在数据微片传输时使用较短的时钟周期，其机理可用图5加以简单示意。

　　图中上半部分是传统的虫孔交换，下半部分是使用不同时钟的改进的虫孔交换。其中头微片的大小为1，数据微片为4，共经过4段链路，假设头时钟周期是数据时钟的二倍，并在第三段链路时遇到了阻塞。从图中可以看出，改进型的虫孔交换缩短了传输时间。

　　在这种机制中时延的缩短是以牺牲路由节点复杂度为代价的。运用这种交换机制时，路由器需要同时提供两个时钟，并需要添加一个时钟选择器，所以在复杂度、面积和能耗性能方而都会带来负面的影响。

　　还有很多研究者将面向连接的思想、虚信道和虫孔交换结合使用。事实上在当今提出的片上网络模型中多采用这种类似于流水电路交换的综合机制来支持有保证业务，并在多媒体业务中得到了广泛的运用。

　　3．总结

　　面向连接的电路交换可以很好的保证服务质量，在传输消息较长的多媒体信息时可以获得较高的吞吐和较低的时延。现今提出的许多片上网络模型都采用了这种面向连接的机制来提供有保证的服务。但对于尽力服务而言，普遍采用的无连接的交换方式。分组交换以分组为流控单位，在每个路由节点需要将分组完全存储，做出路由判决后再进行转发。此种机制的缺点是所需的缓存器数量较多，影响了芯片的面积。为了进一步提高时延性能，虚切通交换将分组划分为更小的微片。在发生拥塞时，虚切通交换中的所有微片都向前存储到头微片被阻的中间节点中缓存起来。所以虚切通的路由器中也要提供和存储转发相同数量的缓存器。但仿真验证在实现相同吞吐量的情况下，虚切通路由器的面积和能耗性能都优于分组交换。虫孔交换与虚切通交换只在发生拥塞时才表现出不同。在没有阻塞时，两者都可以流水的通过网络。在发生阻塞时，虫孔交换分组中的各个微片均就地阻塞。在虚切通和虫孔交换中，路由器之间传递的是微片，而路由器与网络接口交换的是分组。所以路由节点要负责将分组分割成微片然后注入网络，还要负责将微片从网络中接收，并将微片组合成分组。这两种机制都可以采用虚信道技术来进一步提高乔吐，同时虚信道流控机制还能帮助虫孔交换避免死锁。通过观察这两种机制在阻塞时的行为可以发现，虚切通交换能够更有效的利用网络带宽，因此比虫孔交换具有更高的吞吐量，但是它需要较大的缓存资源。从性能的角度而言应该选用虚切通交换，但是它所需要的缓存资源较大，并且也消耗更多的能量。

　　本文对片上网络中常见的几种交换机制的工作原理进行了详细的分析，并从片上网络特有的限制的角度对这几种交换机制进行了分析与比较，最后对这几种交换机制的优缺点进行了总结。