三维片上网络架构方法

摘要

本发明提出了一种三维片上网络架构方法，其网络结构由水平面方向的De Bruijn图网络和垂直方向的柱状结构组成的三维网络，网络中的节点，大部分是由处理单元和路由单元两种功能模块组成(甲类节点)且处理单元与路由单元(Router)是通过数据单向连线连接，其余是只有交换单元(乙类节点)；本方法充分发挥De Bruijn图的优势，首先设计出最简循环路径算法，然后基于最简循环路径算法再设计出简短移位路由算法和最短移位路由算法，利用所设计出的路由算法使数据传输的平均跳数少，网络延时小，吞吐率，再利用DeBruijn图可容错的特点设计出了避免阻塞的数据传输方法，提高了数据传输的可靠性，并且在节点中将处理单元与路由单元直接连接，因此又减数了数据传输环节。

主权项

三维片上网络架构方法，包括网络拓扑结构、网络节点的组成和路由计算方法，有的网络节点是甲类，其余的网络节点是乙类，所述的甲类节点是由处理单元和路由单元构成，所述的乙类节点只有交换单元，网络拓扑结构由水平方向网络和垂直方向网络构成三维网络，其特点在于：由路由单元和处理单元组成的甲类节点中的路由单元与处理单元之间有单向数据线连接；网络拓扑结构由水平方向网络和垂直方向网络构成，水平方向的节点连接网络采用De Bruijn拓扑结构，垂直方向由M个柱状结构组成，M是水平面上的节点数，每个柱状结构是由每层水平网络上水平编号相同的甲类节点与某一层中的乙类节点连接在一起而成的星型网络，垂直方向的每个柱状结构有且只有一个乙类节点，即网络中每个甲类节点都与一个且只与一个乙类节点相连接，一个乙类节点将与N个甲类节点连接,N是水平面的层数；数据包传递过程如下：步骤A、源节点处理单元的数据包首先传递到源节点路由单元里；步骤B、源节点路由单元判断目标节点与源节点的水平编号是否相同，如果相同，直接进入步骤D，否则，则先进入步骤C；步骤C、源节点路由单元利用路由计算方法计算出从源节点到与目标节点有相同水平编号且与源节点具有相同Z坐标的中转节点的路由路径，然后数据包通过该路由传递到中转节点的路由单元，中转节点与目标节点在同一个柱状结构里，所述的Z坐标的取值就是水平面的次序，第i水平面的节点的Z坐标就是i；步骤D、数据包从源节点或步骤C中所述的中转节点传递到与源节点或中转节点同在一个柱状结构里的交换单元，然后再从交换单元直接传递到目标节点的处理单元；路由计算方法是简短移位路由算法或最短移位路由算法，其中所述的简短移位路由算法为：先分别利用左最简移位路径算法和右最简移位路径算法计算出左路径和右路径，然后在左路径和右路径两者之间选择出最短的路径作为最终计算所得到的路径；所述的左最简移位路径算法为：步骤1、将源节点的水平编号用m位比特的二进制数代替，设一个水平面的节点数为K，K的取值是2的幂次方，则m＝log2K，取H＝m‑1，F＝m；步骤2、将源节点的水平编号的低H位与目标节点的水平编号的高H位比较进行比较，如果不相同且H＞＝2，则将H＝H‑1，然后重复本步，否则，命源节点的水平编号为新编号，取F＝H+1，并进入步骤3；步骤3、将新编号的二进制数从低向高移动一位，并将原来的最高位丢弃，移动后的编号的最低位由目标节点的水平编号中的第F高位补充得到新编号，记录该次的编号，取F＝F+1；步骤4、重复步骤3所述过程m‑H‑1次；步骤5、将步骤3和步骤4所记录的所有编号按照记录的前后顺序构成了从源节点到目标节点的左路径；所述的右最简移位路径算法具体步骤如下：步骤6、将水平编号用m位比特的二进制数代替，设一个水平面的节点数为K，K的取值是2的幂次方，则m＝log2K；取H＝m‑1，F＝m； 步骤7、将源节点的水平编号的高H位与目标节点的水平编号的低H位进行比较，如果不相同且H＞＝2，则取H＝H‑1，然后重复本步，否则，命源节点的水平编号为新编号，F＝H+1，进入步骤8；步骤8、将新编号从高向低移动一位，并将原来的最低位丢弃，移动后的编号的最高位由目标节点的水平编号中的第F低位补充得到新编号，记录该次的编号，取F＝F+1；步骤9、重复步骤8所述过程m‑H‑1次；步骤10、将步骤8和步骤9所记录的所有编号按照记录的前后顺序构成从源节点到目标节点的右路径；所述的最短移位路由算法过程如下：1)、采用左最简移位路径算法和右最简移位路径算法分别算出源节点到目标节点之间左路径和右路径，如果左路径或右路径的跳数小于等于2，转入5)，否则，将n＝2，k＝1，进入2)；2)、分别将n条路径中的第k跳的终点为新的源节点，再采用最简移位法计算出n条左路径和n条右路径，在每条路径前面分别加上各自新的源节点到源节点之间的路径部分，即成为从源节点开始到目标节点的2n条路由，如2n条路径中的某条路由的跳数为小于等于k+2，则转入5)，否则转入3)；3)、判断k是否小于m，如果k小于m，转入4，否则转入5)；4)、将n＝2n，k＝k+1；转入2)；5)、选择所有路由中最短的路径作为数据传输路由；其中：m是地址的二进制数的长度。