片上網絡通信死鎖避免方法、路由器及通信網絡的製作方法

2023-06-11 00:18:36

片上網絡通信死鎖避免方法、路由器及通信網絡的製作方法
【專利摘要】本發明公開了一種片上網絡通信死鎖避免方法、路由器及通信網絡，通過網絡分層的方法來減少網絡中多個多播分組發生多播死鎖的概率，在單個通信子網內，多播分組最多發往2個輸出埠，多播分組間產生多播死鎖概率大大降低。另一方面當多播樹建立過程中形成死鎖時，緩存發生死鎖的多播分組，同時改變其他多播分組傳輸路徑為水平方向，促使網絡從死鎖中恢復過來。本發明具有通信效率較高，且路由器結構簡單、設計面積低的優點。
【專利說明】片上網絡通信死鎖避免方法、路由器及通信網絡
【技術領域】
[0001]本發明涉及網絡通信【技術領域】，特別涉及一種基於樹的片上網絡通信死鎖避免方法、路由器及通信網絡。
[0002]
【背景技術】
[0003]隨著集成電路工藝的發展，矽片上集成數十億電晶體已成為現實，處理器步入多核時代。多核處理器將多個智慧財產權(IP, Intellectual Property)核集成在同一塊晶片上構成片上系統(SoC, System on Chip)。由於總線結構技術成熟易實現，片上系統基本都採用總線結構實現IP核之間的通信。然而隨著IP核數目的增加，總線結構資源利用率低、時鐘同步困難、時鐘樹功耗大、可擴展性差、可重用性差等缺點也越發突出。為了克服
總線的不足，一種新型片上通信模式-片上網絡(NoC, Network on Chip)應運而生。片
上網絡將計算機網絡中的並行通信思想引入到片上系統設計中。路由器之間通過點到點雙工鏈路互連組成並行通信網絡；IP核通過網絡接口接入到網絡中；IP核之間通過並行通信網絡實現數據傳輸。片上網絡的出現有效的增加了片上系統帶寬、降低面積與功耗的開銷、提升了重用設計的水平、降低了設計複雜度。
[0004]應用的發展使得多播通信以及廣播通信在片上系統當中變得越來越普遍。例如在緩存一致性存儲系統當中，系統共享緩存當中的數據信息需要與IP核私有緩存當中的數據保持一致，當共享緩存當中的數據變化時就需要向各個相關IP核發送緩存一致性請求。在該系統當中，多播通信的比例高達12.4%。然而傳統的片上網絡設計當中往往只考慮單播通信，很少考慮多播通信。這是由於多播通信的引入使得片上通信關係變得更加複雜，多播通信的比例以及一個源節點對應的目的節點數目(目的節點集)的增加會大大增加網絡通信量，而有限的片上網絡資源使得網絡更加容易飽和。另外，多播目的節點集合的變化也會使得網絡更加容易出現網絡流量不均衡、平均鏈路利用率低下等問題。因此，如果直接將傳統的單播片上網絡運用於多播通信，網絡性能將急劇下降。但是，與多次單播的通信方式相t匕，採用多播通信方式能夠大幅提高網絡的通信性能，降低系統功耗。因此，設計一種能較好地支持片上多播通信的片上網絡是很有必要的。
[0005]目前主要有兩種常見的多播路由方式實現多播通信:基於路徑的路由方式和基於樹的路由方式。在基於路徑的路由方式中，多播分組以一種最節省網絡帶寬資源的方式依次訪問各個目的節點。源節點在發送數據之前需要將多個目的節點地址依照訪問的順序依次排列。這種方式會佔用較多的資源並帶來較大的排序時延，而片上網絡有著更為嚴格的面積時延約束，採用這種實現方式並不現實。在基於樹的多播通信方式中，多播分組根據多個目的節點地址將沿著儘可能遠的共同路徑進行傳播，並在通往不同目的節點集的信道分支節點處複製多播分組並轉發出去，直至轉發到各個目的節點，可以生成從源節點到多個目的節點的具有最短路徑、最小開銷的多播樹。這種方式能夠減少多播分組在網絡當中的複製次數和相同數據對網絡資源的競爭，從而減少網絡流量，避免網絡擁塞。但是，由於在多播分組的傳輸過程中，需要建立一棵從源節點到各個目的節點的多播樹，當多個多播分組需要使用相同的網絡資源，在佔用部分資源的同時請求其他多播分組佔用的資源時會形成較為嚴重的多播死鎖。如何解決基於樹的多播通信中複雜的多播死鎖成為設計多播片上網絡的關鍵。
[0006]使用基於樹的多播通信方式主要有兩種實現方案:1、在數據傳輸之前建立從源節點到目的節點的多播樹，數據傳輸之後再將建立的多播樹釋放；在該方法在多播樹的建立階段會消耗較大的時延，並且維持較大的針對各個多播樹的查找表也會消耗較大的緩存空間，並且也迴避了多播樹建立過程中產生的多播死鎖問題；2、使用單虛信道蟲孔交換的方式，多播分組順著頭微片建立的通道順序傳輸；多播分組之間通過標號的形式進行區分，分組標號在中間路由器傳輸時進行更新。但是，由於標號的有限性該方案只能緩解多播死鎖，不能避免死鎖的產生。
[0007]
【發明內容】

[0008]本發明提出一種基於樹的片上網絡通信死鎖避免方法、路由器及通信網絡，目的在於解決使用單虛信道蟲孔交換方式實現基於樹的多播通信中如何避免死鎖出現的問題。
[0009]根據本發明的第一方面，本發明提供一種片上網絡通信死鎖避免方法，包括:
定義片上網絡的規模為N*M的拓撲結構，由N*M個路由器組成；以網絡左下角路由器為原點，水平向右為X軸正方向，豎直向上為y軸正方向；其中，N為網絡X軸路由器數量，Μ為網絡y軸路由器數量，N和Μ的取值都是正整數；
路由器根據其在通信網絡中位置的不同使用唯一且連續的標號，標號為自然數，從位於原點的路由器開始沿著X軸正方向或者負方向順序遞增，到達邊界路由器後沿y軸正方向遞增一次後繼續在X軸方向遞增，到第N*M個路由器結束；
通信網絡由向上通信子網和向下通信子網組成，向上通信子網通過分組數據的方式傳輸通信數據，其中目標路由器的標號大於數據所在路由器的標號；向下通信子網通過分組數據的方式傳輸通信數據，其中目標路由器的標號小於數據所在路由器的標號；分組數據由頭微片、體微片和尾微片組成，所述頭微片表示分組數據開始，包括虛信道號和目標地址；所述體微片表示所需傳輸的數據載荷；所述尾微片表示分組數據結束；
當源路由器接受來自本地輸入埠的包含頭微片的分組數據後，提取目的路由器信息，根據目的路由器標號與源路由器標號的大小判斷分組數據要發往的通信子網；在中間路由器，分組數據從水平輸入埠或垂直輸入埠輸入後，根據頭微片所攜帶的虛信道號存入相應的虛信道，並且提取目的地址；中間路由器提取目的地址後根據路由算法確定該頭微片所在的分組數據要發往的輸出埠，從而傳輸分組數據到達目的地址。
[0010]根據本發明的第二方面，本發明提供一種應用本發明第一方面提供方法的路由器，包括上子路由器和下子路由器；
上子路由器用於處理網絡中向上傳輸的數據流量；
下子路由器用於處理網絡中向下傳輸的數據流量；
上子路由器或下子路由器都由輸入埠模塊、開關仲裁器、交叉開關和輸出埠模塊組成；輸入埠模塊由水平方向輸入埠模塊、豎直方向輸入埠模塊和本地方向輸入埠模塊組成，用於緩存數據信息，控制數據輸出埠方向，和向開關仲裁發送輸出請求；
開關仲裁器用於解決多個輸入埠虛信道對單個輸出埠的競爭；
交叉開關用於從輸入埠模塊到輸出埠模塊的數據通路；
輸出埠模塊由水平方向輸出埠模塊，豎直方向輸出埠模塊和輸出非本地數據埠模塊組成，用於為分組分配一個可用的下一路由器輸入虛信道，同時對輸出數據更新。
[0011]根據本發明的第三方面，本發明提供一種應用本發明第二方面提供的路由器的通信網絡，由至少兩個路由器組成，其特徵在於:
上子路由器相互信號連接構成向上通信子網，連接方式為區域網、廣域網或城域網；下子路由器相互信號連接構成向下通信子網，連接方式為區域網、廣域網或城域網。
[0012]本發明通過網絡分層的方法來減少網絡中多個分組數據發生死鎖的概率，由於在源路由器，分組數據流量根據其流量目的路由器與源路由器的位置關係分為向上傳輸的流量和向下傳輸的流量。在單個通信子網內，分組數據最多發往2個輸出埠，分組數據間產生多播死鎖概率大大降低。
[0013]
【專利附圖】

【附圖說明】
[0014]圖1為本發明實施例的片上通信網絡系統示意圖；
圖2為本發明實施例的片上網絡路由器中傳輸分組的格式；
圖3為本發明實施例的子路由器結構；
圖4為本發明實施例的路由算法流程圖。
[0015]
【具體實施方式】
[0016]下面通過【具體實施方式】結合附圖對本發明作進一步詳細說明。
[0017]本實施例採用4*4網絡拓撲結構，請參考圖1。在其他實施方式中，只要採用N*M的網絡拓撲結構即可，其中N、M都是正整數，而且N與Μ之間沒有大小限制，可以相同，亦可以不同，如3*8，7*5，11*1等。網絡中多播通信採用基於樹的方式，使用蟲孔交換的方式實現。多播分組之間通過標號的形式進行區分，標號的編排規則為:以網絡左下角路由器為原點，水平向右為X軸正方向，豎直向上為y軸正方向；路由器根據其在通信網絡中位置的不同使用唯一的自然數標號，優選為唯一且連續的自然數標號，如0、1、2、3 ;從位於原點的路由器開始沿著X軸正方向或者負方向順序遞增，到達邊界路由器後沿y軸正方向遞增一次後繼續在X軸方向遞增，到第N*M個路由器結束。譬如在圖1的4*4網絡拓撲結構中，第一行的標號沿X軸正方向依次為0、1、2、3，到達第一行的邊界路由器3後沿y軸正方向遞增一次，沿X軸負方向依次標號為4、5、6、7，到達第二行的邊界路由器7後沿y軸正方向遞增一次，沿X軸正方向依次標號為8、9、10、11，以此類推。這裡的第一行、第二行等僅是為了方便說明，不具有實質意義。
[0018]每個路由器均由上子路由器和下子路由器組成，上子路由器用於向上傳輸數據，下子路由器用於向下傳輸數據。所有上子路由器相互連接組成向上通信子網，在該通信子網中僅允許傳輸目的路由器節點標號大於數據所在路由器節點標號的數據。所有下子路由器相互連接組成向下通信子網，在該通信子網中僅允許傳輸目的路由器節點標號小於數據所在路由器節點標號的數據。路由器之間的連接可通過區域網(LAN)連接或廣域網(WAN)連接等。由於路由器採用S形的標號方式，網絡中存在4種不同的路由器，分別是I型向左傳輸子路由器，I型向右傳輸子路由器，II型向左傳輸子路由器，II型向右傳輸子路由器。這些子路由器在傳輸方向上存在差別，在結構上可以是完全相同，或者埠數量存在差別。也因此可以得知，屬於同一通信子網的子路由器在相鄰行X軸方向上通信方向相反，譬如圖1中第一行的I型向左傳輸子路由器與第二行的I型向右傳輸子路由器同屬於向上通信子網，但是I型向右傳輸子路由器的傳輸方向只能是沿X軸正方向，I型向左傳輸子路由器的傳輸方向只能是沿X軸負方向。現有技術中，多個多播分組在其通信過程中需要佔用不同的通信鏈路及埠，從而導致多播死鎖。而本發明通過網絡分層的方法，使得多播分組在傳輸過程中在同一路由器節點最多佔用2個相鄰方向輸出埠，從而大大降低多播死鎖發生的概率。採用將一個路由器分解為兩個子路由器的設計方法，一方面減少了死鎖發生的概率，另一方面也縮小了路由器設計面積。
[0019]在採用蟲孔路由技術的網絡中，分組數據被切分為若干微片，請參照圖2，單個分組數據由頭微片、體微片及尾微片組成。頭微片包含微片類型、虛信道號、源地址、目的地址等數據，數量為k個，k的取值為正整數，例如1、2、3等；體微片包含微片類型、虛信道號、載荷等數據；尾微片包含微片類型、虛信道號、載荷等數據。在本實施例中，所有微片大小為32位數據。在其他實施方式中，微片大小亦可以為其他位數的數據，譬如64位數據或是128位數據。在本實施例的頭微片中，32位數據分別是2位的微片類型域、2位虛信道號域、4位源地址域、4位目的地址域，剩餘的20位用於後續擴展。在其他的實施方式中，32位數據可以採取不同的位數劃分，譬如32位數據分別是1位的微片類型域、2位虛信道號域、4位源地址域、4位目的地址域，剩餘的21位用於後續擴展。採用不同數值來表明微片類型，在本實施例中，當微片類型為10時表示該微片為頭微片，當微片類型為11時表示體微片，當微片類型為01時表示尾微片。在其他實施方式中，微片類型亦可以用其他數字代替，只要頭微片、體微片、尾微片分別採用不同的數字表示即可，譬如可以採用當微片類型為01時表示該微片為頭微片，當微片類型為02時表示體微片，當微片類型為03時表示尾微片。由於片上網絡採用虛信道的設計方法，需要專門的數據位來區分數據傳輸所使用的虛信道號，2位的虛信道號域可用於區分4個虛信道。4位源地址域和4位目的地址域分別用於傳輸分組從哪一源節點出發，要到達哪一目的節點。4位地址的表示方法為節點標號的二進位。體微片及尾微片格式一樣，分別是2位微片類型域、2位虛信道號域、28位數據載荷。其中，數據載荷即為分組所需傳輸的數據信息。
[0020]參照圖3，子路由器由輸入埠模塊、開關仲裁器、死鎖控制模塊、交叉開關和輸出埠模塊組成。輸入埠模塊用於緩存相鄰路由器節點發來的數據信息，控制數據輸出埠方向，並向開關仲裁發送輸出請求，由水平輸入埠 101、垂直輸入埠 102和本地輸入埠 103組成；開關仲裁器用於解決多個輸入埠虛信道對單個輸出埠的競爭；死鎖控制模塊用於檢測多播死鎖及死鎖發生時緩存發生阻塞的多播分組，控制其他輸入埠多播路由方式，同時與其他路由器進行交互；交叉開關提供從輸入埠模塊到輸出埠模塊的數據通路；輸出埠模塊用於為頭微片分配一個可用的下一路由器輸入虛信道，同時對輸出數據更新，由水平輸出埠 201、垂直輸出埠 202、本地輸出埠 203、204組成。
[0021]採用將一個路由器分解為兩個子路由器的設計方法，與現有不採用子路由器的設計方法相比，在交叉開關及開關仲裁的設計方面大大降低了設計規模。為了降低網絡發生阻塞的概率，輸入埠模塊設計有4個虛信道，採用子路由器的設計方法也能明顯降低輸入輸出埠模塊的虛信道管理開銷。另外，相比經典虛信道路由器，子路由器的設計並沒有使用虛信道仲裁模塊來進行虛信道的管理，當頭微片輸入到子路由器輸入埠時，如果有空閒的虛信道則允許該頭微片輸出，並在輸出埠處隨機地分配一個空閒的下一節點虛信道。移除傳統設計方法中龐大的虛信道仲裁模塊也從另一方面減少了子路由器的設計面積。
[0022]死鎖控制模塊具有三方面的作用，分別是檢測、控制和恢復。首先它監視各輸入埠虛信道緩存的空滿狀態，如果路由器一個方向的輸出埠虛信道被一個緩存為空的輸入埠佔用同時被另一個緩存為滿的輸入埠虛信道請求，控制模塊開始計時，計時達一定的時間時認為在該路由器節點發生多播死鎖。該判斷的依據是:若路由器發生多播死鎖，佔用輸出埠虛信道的多播分組由於在多播路徑的樹形分支處因多播死鎖不能傳輸，而在本地路由器其已經佔用輸出虛信道可以傳輸，所以該輸入虛信道會產生指示緩存為空的信號；而同時另一爭用該輸出虛信道的多播分組在本地無法獲得輸出虛信道發生阻塞，所以該輸入埠在本地路由器會產生緩存已滿的指示信號。當這兩個條件發生並等待一段時間，譬如60ms，之後即可判斷在本地節點發送多播死鎖。
[0023]死鎖控制模塊通過專用的死鎖控制線與其他路由器交互，告知網絡中有路由器發生多播死鎖，收到該控制信息的路由器向其他相鄰的路由器節點轉發該控制信息的同時改變正在請求虛信道的多播分組的路由方式為水平方向，並進行計時。通過這種方式可以避免多播死鎖進一步惡化。死鎖控制模塊在與其他路由器交互的同時使用專用緩存將阻塞的多播分組緩存下來。計時時間到之後，存儲於死鎖控制模塊專用緩存的多播分組以正常方式進行路由轉發，各個路由器計時達到一定時間以後也恢復正常的路由方式進行通信。計時時間可以是出廠設置，或是用戶自行設置。
[0024]為了防止多播分組在輸出路由器時產生多播輸出死鎖，針對每一非本地輸入埠方向都有一個對應的發往本地的輸出埠方向。
[0025]多播分組在網絡中傳輸遵循如下步驟:
源路由器接受來自本地輸入埠的頭微片後首先提取其要發往的目的路由器信息，根據其要發往的目的路由器標號與源路由器標號的大小判斷該頭微片要發往上通信子網或者發往下通信子網；
在中間路由器，各個頭微片從輸入埠輸入後首先根據其自身攜帶的虛信道號存入對應的虛信道。路由模塊提取目的地址後根據路由算法確定該頭微片要發往的輸出埠，並且該輸出埠方向會被記錄下來以利於後續體微片及尾微片的傳輸，接著該頭微片向開關仲裁器發送仲裁請求，當仲裁請求被允許時頭微片經交叉開關從輸入埠輸出至輸出埠。屬於同一多播分組的頭微片從輸入埠輸出時都會記錄其發往的輸出埠，以這種方式多播分組在中間路由器節點形成多播樹結構；
體微片及尾微片緊跟頭微片傳輸。當多個頭微片在中間路由器發往不同的輸出埠方向時，體微片及尾微片從輸入埠輸入後根據各個頭微片輸出時記錄的輸出埠方向向開關仲裁器發送仲裁請求，只有在該微片向所需的所有輸出埠方向發送的請求都被允許時才能進行下一個微片的仲裁請求。當該微片僅有部分方向的請求被允許時，想被允許的輸出埠方向發送一份微片的拷貝，開關仲裁在下一階段繼續進行該微片剩餘輸出埠方向的請求，直到所有輸出方向的請求都被允許，這時輸入埠中存儲的數據被釋放掉。
[0026]尾微片經過每一路由器節點後，釋放分組佔用的虛信道以及記錄的輸出埠方向等信息，多播分組傳輸過程結束。
[0027]由於本發明不需要建立從源節點到目的節點的固定傳輸鏈路，該方案不會產生基於建鏈的多播片上網絡所具有的建鏈時延；另外，相比普通蟲孔交換，在本發明中子路由器的設計過程中採用虛信道的設計方法，增加了多播通信效率，提高了時延吞吐性能。特別地，單播分組格式與多播分組格式一致，只是單播分組僅包含一個頭微片，即k固定為1，因此本發明所設計的片上網絡對於單播通信亦具有較好的兼容性。單播分組在該片上網絡系統中的傳輸過程與經典虛信道路由器傳輸過程一致。
[0028]圖4為頭微片在各個子路由器中傳輸的路由算法，具體步驟為:
S401:查看當前頭微片所在的輸入埠是否為本地輸入埠，如果不是則執行步驟S403，如果是則執行步驟S402 ；
S402:比較當前路由器節點標號與目的路由器節點標號大小，如果該微片不屬於當前子路由器所在的通信子網，則丟棄該微片；
如果屬於則執行步驟S404 ；
5403:如果當前路由器節點即為該頭微片的目的路由器節點，則選擇屬於該微片所在輸入埠的本地輸出埠，執行步驟S406 ；
5404:在當前路由器節點非邊界節點的情況下，如果目的路由器節點與當前路由器節點位於同一行或者位於當前路由器節點所在列的X軸輸出方向一側的下一行，或者該頭微片上次向1軸方向請求計時已滿，則選擇X軸輸出埠，執行步驟S406 ；
如果非以上情況則執行步驟S405 ；
5405:如果子路由器所在X軸方向輸出埠未使用的虛信道比y軸方向輸出埠未使用的虛信道少，或者子路由器位於邊界節點上，則選擇y軸方向輸出埠，執行步驟S406 ；
5406:返回該頭微片輸出埠方向。
[0029]使用該路由算法，當路由器部分輸出埠虛信道阻塞時可以選擇較為空閒的輸出埠輸出。另外比較重要的是，當頭微片要發往y軸方向的輸出埠時，如果發明該方向輸出埠長時間未得到響應，則可判斷該頭微片可能與屬於其他分組的頭微片發生多播死鎖，該頭微片可以改向X軸方向輸出埠輸出。由於多播分組在該路由器節點僅有X軸方向的輸出路徑，不會與其他多播分組傳輸衝突，這樣可以徹底避免多播死鎖的形成。
[0030]以上內容是結合具體的實施方式對本發明所作的進一步詳細說明，不能認定本發明的具體實施只局限於這些說明。對於本發明所屬【技術領域】的普通技術人員來說，在不脫離本發明構思的前提下，還可以做出若干簡單推演或替換。
【權利要求】
1.一種片上通信網絡死鎖避免方法，其特徵在於:定義片上通信網絡的規模為N*M的拓撲結構，由N*M個路由器組成；以通信網絡左下角路由器為原點，水平向右為X軸正方向，豎直向上為y軸正方向；所述N為通信網絡X軸路由器數量，所述Μ為通信網絡y軸路由器數量，其中N和Μ的取值都是正整數；所述路由器根據其在通信網絡中位置的不同使用唯一的標號，所述標號為自然數，從位於原點的路由器開始沿著X軸正方向或者負方向順序遞增，到達邊界路由器後沿1軸正方向遞增一次後繼續在X軸方向遞增，到第Ν*Μ個路由器結束；所述通信網絡由向上通信子網和向下通信子網組成，所述向上通信子網通過分組數據的方式傳輸通信數據，其中目標路由器的標號大於數據所在路由器的標號；所述向下通信子網通過分組數據的方式傳輸通信數據，其中目標路由器的標號小於數據所在路由器的標號；所述分組數據由頭微片、體微片和尾微片組成，所述頭微片表示分組數據開始，包括虛信道號和目標地址，數量為k個，k的取值為正整數；所述體微片表示所需傳輸的數據載荷；所述尾微片表示分組數據結束； 當源路由器接受來自輸入埠的分組數據後，從分組數據的頭微片中提取目的路由器信息，根據目的路由器標號與源路由器標號的大小判斷分組數據要發往的通信子網；在中間路由器，分組數據從輸入埠輸入後，根據頭微片所攜帶的虛信道號存入相應的虛信道，並且提取目的地址；中間路由器提取目的地址後根據路由算法確定該頭微片所在的分組數據要發往的輸出埠，從而傳輸分組數據到達目的地址。
2.根據權利要求1所述方法，其特徵在於:在所述中間路由器提取目的地址後根據路由算法確定該頭微片所在的分組數據要發往的輸出埠之後，所述尾微片經過每個子路由器節點時，在向所需輸出的所有輸出埠都發送一份拷貝之後，釋放分組數據佔用的虛信道。
3.根據權利要求2所述的方法，其特徵在於:所述路由算法步驟為:S1:查看當前頭微片所在的輸入埠是否為本地輸入埠，如果不是則執行步驟S3，如果是則執行步驟S2 ；S2:比較當前路由器節點標號與目的路由器節點標號大小，如果該微片不屬於當前子路由器所在的通信子網，則丟棄該微片；如果屬於則執行步驟S4;S3:如果當前路由器節點即為該頭微片的目的路由器節點，則選擇屬於該微片所在輸入埠的本地輸出埠，執行步驟S6 ；54:在當前路由器節點非邊界節點的情況下，如果目的路由器節點與當前路由器節點位於同一行或者位於當前路由器節點所在列的X軸輸出方向一側的下一行，或者該頭微片上次向y軸方向請求計時已滿，貝1J選擇X軸輸出埠，執行步驟S6 ；如果非以上情況則執行步驟S5 ；55:如果子路由器所在X軸方向輸出埠未使用的虛信道比1軸方向輸出埠未使用的虛信道少，或者子路由器位於邊界節點上，則選擇y軸方向輸出埠，執行步驟S6 ；56:返回該頭微片輸出埠方向。
4.根據權利要求3所述的方法，其特徵在於:當所述頭微片在片上網絡傳輸數據過程中形成死鎖，該頭微片所在路由器的死鎖控制模塊將該頭微片存儲專用緩存中，同時向通信網絡中的其他路由器發出第一指令，所述第一指令為在傳輸分組時使用X軸方向唯一的路徑進行傳輸；在特定時間之後，該頭微片所在路由器的死鎖控制模塊向通信網絡中的其他路由器發出第二指令，所述第二指令為取消在傳輸分組時使用X軸方向唯一的路徑進行傳輸；所述死鎖控制模塊是用於降低死鎖形成後對網絡傳輸分組數據的影響。
5.根據權利要求4所述方法，其特徵在於:所述死鎖控制模塊還用於檢測死鎖是否形成，具體包括:所述死鎖控制模塊監視各輸入埠虛信道緩存的空滿狀態，如果子路由器一個方向的輸出埠虛信道被一個緩存為空的輸入埠虛信道佔用同時被另一個緩存為滿的輸入埠虛信道請求，則開始計時，當計時超過預設值時，認為在該路由器節點發生多播死鎖。
6.一種實現權利要求1所述片上通信網絡死鎖避免方法的路由器，其特徵在於:包括上子路由器和下子路由器；所述上子路由器用於處理通信網絡中向上傳輸的數據流量；所述下子路由器用於處理通信網絡中向下傳輸的數據流量；所述上子路由器或下子路由 器都由輸入埠、開關仲裁器、交叉開關和輸出埠組成；所述輸入埠由水平方向輸入埠、豎直方向輸入埠和本地方向輸入埠組成，用於緩存數據信息，控制數據輸出埠方向，和向開關仲裁發送輸出請求，與開關仲裁器信號連接，與交叉開關硬體連接；所述開關仲裁器用於解決多個輸入埠虛信道對單個輸出埠的競爭，與輸入埠模塊信號連接；所述交叉開關用於從輸入埠到輸出埠的數據通路，與輸入埠、輸出埠分別硬體連接；所述輸出埠由水平方向輸出埠，豎直方向輸出埠和輸出非本地數據埠組成，用於為分組分配一個可用的下一路由器輸入虛信道，同時對輸出數據更新，與交叉開關硬體連接。
7.根據權利要求6所述的路由器，其特徵在於:所述上子路由器和下子路由器還包括死鎖控制模塊，所述死鎖控制模塊用於降低死鎖形成後對網絡傳輸分組數據的影響，與輸入埠信號連接。
8.根據權利要求7所述的路由器，其特徵在於:所述死鎖控制模塊還用於檢測死鎖是否形成，具體包括:所述死鎖控制模塊監視各輸入埠虛信道緩存的空滿狀態，如果子路由器一個方向的輸出埠虛信道被一個緩存為空的輸入埠虛信道佔用同時被另一個緩存為滿的輸入埠虛信道請求，則開始計時，當計時超過預設值時，認為在該路由器發生多播死鎖。
9.一種應用權利要求6-8任一項所述路由器組成的通信網絡，所述路由器至少兩個，其特徵在於:所述上子路由器相互信號連接構成向上通信子網，連接方式為區域網、廣域網或城域網；所述下子路由器相互信號連接構成向下通信子網，連接方式為區域網、廣域網或城域網。
【文檔編號】G06F15/173GK103729331SQ201310618876
【公開日】2014年4月16日 申請日期:2013年11月26日 優先權日:2013年11月26日
【發明者】鄭國海, 顧華璽, 朱鍵, 王錚, 付希松 申請人:西安電子科技大學, 香港中文大學深圳研究院