一种基于片上网络的无死锁路由方法

摘要

本发明揭示了一种基于片上网络的无死锁路由方法，所述方法包括如下步骤：在源节点将数据包复制n份，其中，n≥3；在片上网络中设定n条自源节点至目的节点的不交叉的通道，n份数据包分别在n条通道上传输；n份数据包到达目的节点后再通过表决器得到正确结果，实现了空间上的冗余。本发明提出的基于片上网络的无死锁路由方法，第一次在2D网格的片上网络中提出了一种三条非交叉路径的路由算法，并且严格证明了不会带来死锁问题。可以利用本发明的路由算法来实现空间上的三模冗余，提高系统的可靠性。

主权项

一种基于片上网络的无死锁路由方法，其特征在于，所述方法包括如下步骤：在源节点将数据包复制n份，其中，n≥3；在片上网络中设定n条自源节点至目的节点的不交叉的通道，n份数据包分别在n条通道上传输；n份数据包到达目的节点后再通过表决器得到正确结果，实现空间上的冗余；当n=3时，在片上网络中开设四条虚通道，其中两条分别为XY通道和YX通道，另外两条是红通道和黑通道；具有高可靠性要求的数据包在源节点首先拷贝成三份，其中的两份分别通过XY通道和YX通道向目的节点发包；第三份数据包首先通过源节点的红通道/黑通道发送到与前两条通道不同的相邻节点，再通过XY通道/YX通道发送到距离目的节点为一的节点，必须在源节点与目的节点组成的矩形区域以外，保证与另外两份数据包无交叉路径；再通过黑通道/红通道发送到目的节点；所述XY通道、YX通道、红通道、黑通道的定义是：XY通道：在该虚通道内，数据包的传输采用XY路由策略，就是先沿X方向传输到与目标节点相同的X坐标的节点，再沿Y方向传输到目标节点；YX通道：与XY通道类似，先沿Y方向传输到目标节点相同的Y坐标的节点，再沿X方向传输到目标节点；红通道：每个router节点到它每个相邻的节点都有一对虚通道：一个发出通道和一个接收通道；对每个奇节点来说，它们的发出通道是红通道，对每一个偶节点来说，它们的接收通道是红通道；黑通道：与红通道类似，对每个奇节点来说，它们的接收通道是黑通道，对每一个偶节点来说，它们的发出通道是黑通道。