[發(fā)明專(zhuān)利]一種三維光電混合互連網(wǎng)絡(luò)路由方法

在審

• 申請(qǐng)?zhí)枺?/td>: 201410468103.0
• 申請(qǐng)日: 2014-09-15
• 公開(kāi)（公告）號(hào): CN104348718A
• 公開(kāi)（公告）日: 2015-02-11
• 發(fā)明（設(shè)計(jì)）人: 竇強(qiáng);彭超;竇文華;肖立權(quán);郭龍飛;魯佳;王俊輝;李寶亮;周樂(lè)文;韓崗;錢(qián)悅;蘇醒;任斌;葉進(jìn);覃晨;馮權(quán)友;任雙印;孫家輝;何磊
• 申請(qǐng)（專(zhuān)利權(quán)）人: 中國(guó)人民解放軍國(guó)防科學(xué)技術(shù)大學(xué)
• 主分類(lèi)號(hào): H04L12/705
• 分類(lèi)號(hào): H04L12/705
• 代理公司: 北京匯思誠(chéng)業(yè)知識(shí)產(chǎn)權(quán)代理有限公司 11444
• 代理人: 王剛;龔敏

技術(shù)領(lǐng)域

本發(fā)明涉及高性能計(jì)算機(jī)通信領(lǐng)域，尤其涉及一種三維光電混合互連網(wǎng)絡(luò)路由方法。

背景技術(shù)

當(dāng)前，提高單個(gè)計(jì)算節(jié)點(diǎn)的性能以及互連網(wǎng)絡(luò)的優(yōu)化和改進(jìn)是提高高性能計(jì)算機(jī)性能的兩種有效手段。然而由于高速電信號(hào)的限制，提高單個(gè)處理器的時(shí)鐘頻率和計(jì)算性能已變得非常困難，系統(tǒng)計(jì)算能力的提高主要是通過(guò)將大量處理器互連在一起來(lái)實(shí)現(xiàn)。傳統(tǒng)的電互連網(wǎng)絡(luò)由于其存在帶寬小、延遲大、互連密度小等局限性，成為制約高性能計(jì)算機(jī)性能進(jìn)一步提高的瓶頸之一。以光信號(hào)作為信息載體，相對(duì)于電介質(zhì)具有許多優(yōu)點(diǎn)：較高的時(shí)間、空間帶寬積，高度的并行性和無(wú)干擾性，傳輸和交換光功率損耗小、干擾低等優(yōu)點(diǎn)。

但是，在當(dāng)前技術(shù)條件下，沒(méi)有有效的光緩存器以及可用的全光處理器，對(duì)于一般的報(bào)文交換互連系統(tǒng)，在網(wǎng)絡(luò)節(jié)點(diǎn)中不得不將光信號(hào)轉(zhuǎn)換為電信號(hào)進(jìn)行路由判斷和緩存，這將會(huì)引入額外的傳輸延遲。三維光互連網(wǎng)絡(luò)(Three-Dimensional?Optical?Interconnection?Network，TDOIN)結(jié)構(gòu)的出現(xiàn)，解決了光技術(shù)限制和面向更高維度的互連網(wǎng)絡(luò)。

一個(gè)m*n*p的TDOIN由m*n*p個(gè)節(jié)點(diǎn)組成，每個(gè)節(jié)點(diǎn)可用坐標(biāo)(x,y,z)(x＝0,1,2，…，m-1；y＝0,1,2，…，n-1；z＝0,1,2，…，p-1)表示，每個(gè)節(jié)點(diǎn)包含所述三個(gè)輸入端口，分別為X-方向輸入端口、Y-方向輸入端口和Z-方向輸入端口，三個(gè)輸出端口，分別為X+方向輸出端口、Y+方向輸出端口和Z+方向輸出端口。在TDOIN中，所有節(jié)點(diǎn)都按照時(shí)隙同步模式傳輸數(shù)據(jù)。比如報(bào)文P的數(shù)據(jù)信息的第一位在某個(gè)時(shí)隙開(kāi)始時(shí)刻t1從一個(gè)節(jié)點(diǎn)N1的X+、Y+或Z+端口發(fā)出后，經(jīng)過(guò)一個(gè)時(shí)隙的時(shí)間ΔT，在t1+ΔT時(shí)刻，報(bào)文P的數(shù)據(jù)信息的第一位到達(dá)相鄰的下一個(gè)節(jié)點(diǎn)N2的X-方向、Y-方向或Z-方向端口，同時(shí)，報(bào)文P的最后一位剛從N1發(fā)送出來(lái)，這種按照時(shí)隙同步模式傳輸數(shù)據(jù)的網(wǎng)絡(luò)假定報(bào)文在相鄰節(jié)點(diǎn)間的傳輸時(shí)間等于一個(gè)時(shí)隙。因此，在t1+ΔT時(shí)刻，節(jié)點(diǎn)N1和節(jié)點(diǎn)N2間的光鏈路“充滿”數(shù)據(jù)。然后報(bào)文P的數(shù)據(jù)信息的第一位接著從節(jié)點(diǎn)N2的X+方向、Y+方向或Z+方向端口送出，在t1+2ΔT時(shí)刻，報(bào)文P的第一位到達(dá)節(jié)點(diǎn)N3的X-方向、Y-方向或Z-方向端口，此時(shí)其最后一位到達(dá)節(jié)點(diǎn)N2的輸出端口。這樣，整個(gè)報(bào)文在到達(dá)目的節(jié)點(diǎn)之前將沿著網(wǎng)絡(luò)鏈路流水前進(jìn)。

目前，TDOIN采用的路由算法是XY優(yōu)先路由算法。當(dāng)沒(méi)有沖突發(fā)生時(shí)，數(shù)據(jù)報(bào)文按照XYZ順序路由方式在TDOIN中進(jìn)行路由，即一個(gè)報(bào)文首先沿著X+方向在網(wǎng)絡(luò)中前進(jìn)，當(dāng)?shù)竭_(dá)與目的節(jié)點(diǎn)具有相同X坐標(biāo)的某個(gè)中間節(jié)點(diǎn)之后，再轉(zhuǎn)向Y+方向路由；當(dāng)?shù)竭_(dá)與目的節(jié)點(diǎn)具有相同Y坐標(biāo)的某個(gè)中間節(jié)點(diǎn)之后，再轉(zhuǎn)向Z+方向路由。如果在某個(gè)中間節(jié)點(diǎn)上，從X-方向端口到達(dá)的報(bào)文具有最高的優(yōu)先權(quán)，而從Y-方向端口到達(dá)的報(bào)文比從Z-方向端口到達(dá)的報(bào)文具有更高的優(yōu)先權(quán)，優(yōu)先級(jí)高的方向上的報(bào)文優(yōu)先被發(fā)送出去，優(yōu)先級(jí)低的方向的報(bào)文暫時(shí)緩存在處理單元中。

但是在TDOIN中，由于在XY優(yōu)先路由算法中的處理單元引入了緩存隊(duì)列，Z-方向的報(bào)文需要緩存到節(jié)點(diǎn)中，而緩存隊(duì)列中報(bào)文需要通過(guò)節(jié)點(diǎn)的X+方向的端口向外發(fā)送報(bào)文，當(dāng)X+方向一直存在正在轉(zhuǎn)發(fā)的當(dāng)前報(bào)文時(shí)緩存隊(duì)列中的待發(fā)送緩存報(bào)文會(huì)發(fā)生“死鎖”無(wú)法發(fā)送出去。

發(fā)明內(nèi)容

本發(fā)明的目的在于解決網(wǎng)絡(luò)節(jié)點(diǎn)中待發(fā)送緩存報(bào)文和當(dāng)前報(bào)文同時(shí)轉(zhuǎn)向優(yōu)先級(jí)別最高的輸出方向時(shí)，若該輸出方向一直被當(dāng)前報(bào)文占用，則待發(fā)送緩存報(bào)文不能被發(fā)送出去，就會(huì)出現(xiàn)死鎖問(wèn)題。為解決上述問(wèn)題，本發(fā)明實(shí)施例提供了一種三維光電混合互連網(wǎng)絡(luò)路由方法。

有鑒于此，本發(fā)明提供一種三維光電混合互連網(wǎng)絡(luò)路由方法，可包括：

解析到達(dá)輸入端口的當(dāng)前報(bào)文的目的地址；根據(jù)XY優(yōu)先路由算法以及解析到的所述當(dāng)前報(bào)文的目的地址確定所述當(dāng)前報(bào)文的輸出端口；

若上述確定的所述當(dāng)前報(bào)文的輸出端口是優(yōu)先級(jí)別最高的輸出端口，且有待發(fā)送緩存報(bào)文到達(dá)該輸出端口，則計(jì)算所述當(dāng)前報(bào)文不能被拋棄的概率W，所述W＝當(dāng)前報(bào)文的跳數(shù)/(m*n*p+m*(n+p-2)-2)，所述m為所述當(dāng)前報(bào)文在第一輸出端口方向的總跳數(shù)，所述n為所述當(dāng)前報(bào)文在第二輸出端口方向的總跳數(shù)，所述p為所述當(dāng)前報(bào)文在第三輸出端口方向的總跳數(shù)；

生成隨機(jī)數(shù)R，若所述W小于所述隨機(jī)數(shù)R，拋棄所述當(dāng)前報(bào)文，將所述待發(fā)送緩存報(bào)文送至優(yōu)先級(jí)別最高的輸出端口，所述隨機(jī)數(shù)R的范圍是0<R<1。