来 耀,荆明娥

(复旦大学 专用集成电路与系统国家重点实验室，上海 201203)

片上网络(Networks-on-Chip, NoC)是片上系统(System on a Chip, SoC)重要的硬件形式之一，其将片上系统的结点以网络的形式相连．片上网络路由算法是指从一个结点发送数据包到另一个或多个指定的结点而选择其网络上的传输路径的算法．好的路由算法不仅需要考虑使单个数据包的传输延时最短，还要考虑整个片上网络工作的整体延时，并且需要一定的防拥塞、防死锁和容错机制．

片上网络的路由算法从其路由结果的决策地点来分，可分为源路由和分布式路由[1]．分布式路由是指路由的下一步决策是根据当前数据包所在的路由结点完成，因此整个路由决策是由数据包所经过的所有结点共同决定的．而源路由是指路由的决策在数据的发送结点(即源结点)已经全部完成，该路由决策将附加在数据包的头部，中间的传输结点根据数据包的路由信息决定下一步的发送结点．对于分布式路由，一般途经的结点只做出下一步的路由决策，因此只需考察其周围结点的状况，因此分布式路由一般更易于硬件实现，但缺少决策的宏观性．对源路由而言，源结点一般需要得到整个网络的信息再产生路由决策，可以做出较为宏观的决策．

在源路由算法中，最著名的是链路状态算法(NoC-LS)算法[1]，其思想是每个片上网络的结点都存储一份整个网络上的状态信息(链路延时、故障等)．当需要进行路由决策……