片上網絡拓撲結構的重構方法及系統的製作方法
2023-04-30 15:17:06 2
片上網絡拓撲結構的重構方法及系統的製作方法
【專利摘要】本發明提出一種片上網絡拓撲結構的重構方法，包括以下步驟：根據片上網絡的初始拓撲結構建立有向圖，其中，有向圖中每個節點為初始拓撲結構中每個運算單元，運算單元包括正常運算單元、出錯運算單元和備用運算單元；在有向圖中增加一個超級源點和一個超級匯點，其中，超級源點指向出錯運算單元，備用運算單元指向超級匯點；應用最大流算法對有向圖進行求解得到最大流量和每一條修復路徑，其中，最大流量表示可以被修復的出錯運算單元的數量；根據修復路徑得到片上網絡的虛擬拓撲結構以對完成對片上網絡拓撲結構的重構。本發明實施例的方法具有修復率高、硬體成本低、網絡吞吐率高和延時低的優點。本發明還提供了一種片上網絡拓撲結構的重構系統。
【專利說明】片上網絡拓撲結構的重構方法及系統
【技術領域】
[0001]本發明涉及集成電路【技術領域】，特別涉及一種片上網絡拓撲結構的重構方法及系統。
【背景技術】
[0002]隨著電路集成度的提高，產生了 SoC(System-on-Chip片上系統)。由於傳統的總線結構可拓展性差、帶寬有限，無法滿足多核間通信需求，成為了片上系統技術發展的一個瓶頸。為了解決總線結構的不足，NoC(Network-on-chip片上網絡)技術被推向晶片設計的前沿。片上網絡的核心思想是將計算機網絡技術移植到晶片設計中來，用網絡結構取代傳統的總線結構，片上網絡實現了通信與計算的分離，在系統的擴展性、帶寬及片上系統整體設計方面有極好的表現，目前已逐漸成為片上總線之外的一種新型通信結構。然而隨著SoC集成度的提高，由於片上網絡中IPdntellectual Property)核和鏈路的故障率增加必然導致NoC整體性能的下降，可靠性降低。因此NoC容錯設計非常重要。
[0003]另外，元件產生錯誤的原因有很多，如電遷移、硬體老化、邊緣效應、串擾、耦合噪聲等。根據錯誤發生的時間和頻率，可分為以下三種類型:永久性錯誤、間歇性錯誤和暫時性錯誤。針對不同的錯誤類型，可以在硬體結構、路由算法、傳輸機制、數據包格式等方面進行容錯。假設有一組PE (Processing Element,運算單元)，一部分可以正常工作,一部分有錯誤，如何通過重新配置PE之間的通信連接、用冗餘PE取代出錯PE，得到一個功能正確的NoC系統是目前需要解決的問題。由於晶片上硬體資源有限，因此需要儘可能提高修復率，同時降低代價，如重構時間的增加、拓撲結構的改變、面積的增加、吞吐率的降低和延遲的增加等。目前已經存在一些提升片上網絡可靠性的拓撲結構重構方法，如平移修復(ChangY C，Chiu C Tj Lin S Y，Liu C K.0n the design and analysis of fault tolerant NoCarchitecture using spare routers.ASP-DAC2011:431-436)、交換修復(Kang U，ChungH，Heo S，et al.8Gb3-DDDR3DRAM using through-siIicon-via technology.Journal ofSolid-State Circuits (JSSC)，2010:111-119)、RRCS (L.Zhang，Y.Han，H.Li，and X.Li，「Afault tolerance mechanism in chip many-core processors，，，in J.Tsinghua Scienceand Technology, Jul.2007，vol.12，n0.SI，pp.169 - 174.)等。但是這些方法有的修復率低，有的重構時間長。
【發明內容】
[0004]本發明旨在至少在一定程度上解決上述相關技術中的技術問題之一。
[0005]為此，本發明的一個目的在於提出一種片上網絡拓撲結構的重構方法，該方法具有修復率高、硬體成本低、網絡吞吐率高和延時低的優點。
[0006]本發明的另一個目的在於提供一種片上網絡拓撲結構的重構系統。
[0007]為了實現上述目的，本發明第一方面的實施例提出了一種片上網絡拓撲結構的重構方法，包括以下步驟:根據片上網絡的初始拓撲結構建立有向圖，其中，所述有向圖中每個節點為所述初始拓撲結構中每個運算單元，所述運算單元包括正常運算單元、出錯運算單元和備用運算單元；在所述有向圖中增加一個超級源點和一個超級匯點，其中，所述超級源點指向所述出錯運算單元，所述備用運算單元指向所述超級匯點；應用最大流算法對所述有向圖進行求解以得到最大流量和每一條修復路徑，其中，所述最大流量表示可以被修復的出錯運算單元的數量；根據所述修復路徑得到所述片上網絡的虛擬拓撲結構以對完成對所述片上網絡拓撲結構的重構。
[0008]根據本發明實施例的片上網絡拓撲結構的重構方法，首先根據片上網絡的初始拓撲結構建立有向圖，並在有向圖中增加一個超級源點和一個超級匯點，進一步應用最大流算法對有向圖進行求解以得到最大流量和每一條修復路徑，最後根據修復路徑得到片上網絡的虛擬拓撲結構以對完成對片上網絡拓撲結構的重構。換言之，即本發明的方法採用冗餘硬體和動態重構的方式來提高系統的可靠性，容錯類型集中在解決永久性錯誤上，具有修復率高、重構時間短、硬體成本低的優點，同時保持很高的網絡吞吐率和低延時，此外，無論物理拓撲結構如何，該方法重構產生一致的虛擬拓撲結構，減小了作業系統在不同的拓撲結構上優化並行程序時的負擔。
[0009]另外，根據本發明上述實施例的片上網絡拓撲結構的重構方法還可以具有如下附加的技術特徵:
[0010]在一些示例中，所述出錯運算單元通過對所述片上網絡的拓撲結構進行測試得到。
[0011]在一些示例中，還包括:如果所述可以被修復的出錯運算單元的數量不等於所述出錯運算單元的數量，則判定存在不能被修復的出錯運算單元。
[0012]本發明第二方面的實施例提供了一種片上網絡拓撲結構的重構系統，包括:包括:建立模塊，用於根據片上網絡的初始拓撲結構建立有向圖，其中，所述有向圖中每個節點為所述初始拓撲結構中每個運算單元，所述運算單元包括正常運算單元、出錯運算單元和備用運算單元，並在所述有向圖中增加一個超級源點和一個超級匯點，其中，所述超級源點指向所述出錯運算單元，所述備用運算單元指向所述超級匯點；計算模塊，用於應用最大流算法對所述有向圖進行求解以得到最大流量和每一條修復路徑，其中，所述最大流量表示可以被修復的出錯運算單元的數量；重構模塊，用於根據所述修復路徑得到所述片上網絡的虛擬拓撲結構以對完成對所述片上網絡拓撲結構的重構。
[0013]根據本發明實施例的片上網絡拓撲結構的重構系統，根據片上網絡的初始拓撲結構建立有向圖，並在有向圖中增加一個超級源點和一個超級匯點，進一步應用最大流算法對有向圖進行求解以得到最大流量和每一條修復路徑，最後根據修復路徑得到片上網絡的虛擬拓撲結構以對完成對片上網絡拓撲結構的重構。換言之，該系統採用冗餘硬體和動態重構的方式來提高系統的可靠性，容錯類型集中在解決永久性錯誤上，具有修復率高、重構時間短、硬體成本低的優點，同時保持很高的網絡吞吐率和低延時，此外，無論物理拓撲結構如何，該系統重構產生一致的虛擬拓撲結構，減小了作業系統在不同的拓撲結構上優化並行程序時的負擔。
[0014]另外，根據本發明上述實施例的片上網絡拓撲結構的重構系統還可以具有如下附加的技術特徵:
[0015]在一些示例中，所述出錯運算單元通過對所述片上網絡的拓撲結構進行測試得到。
[0016]在一些示例中，還包括:判斷模塊，用於如果所述可以被修復的出錯運算單元的數量不等於所述出錯運算單元的數量，則判定存在不能被修復的出錯運算單元。
[0017]本發明的附加方面和優點將在下面的描述中部分給出，部分將從下面的描述中變得明顯，或通過本發明的實踐了解到。
【專利附圖】
【附圖說明】
[0018]本發明的上述和/或附加的方面和優點從結合下面附圖對實施例的描述中將變得明顯和容易理解，其中:
[0019]圖1是根據本發明一個實施例的片上網絡拓撲結構的重構方法的流程圖；
[0020]圖2是根據本發明一個實施例的出錯後可能出現的拓撲結構示意圖；
[0021]圖3是根據本發明一個實施例的一些有關參考拓撲結構、物理拓撲結構和虛擬拓撲結構的示意圖；
[0022]圖4是根據本發明一個實施例的通過修復路徑和重構得到虛擬拓撲結構的示意圖；
[0023]圖5是根據本發明一個實施例的用最大流算法確定修復路徑的示意圖；
[0024]圖6是根據本發明一個實施例的不能完全修復的出錯模式示意圖；以及
[0025]圖7是根據本發明一個實施例的片上網絡拓撲結構的重構系統的結構框圖。
【具體實施方式】
[0026]下面詳細描述本發明的實施例，所述實施例的示例在附圖中示出，其中自始至終相同或類似的標號表示相同或類似的元件或具有相同或類似功能的元件。下面通過參考附圖描述的實施例是示例性的，僅用於解釋本發明，而不能理解為對本發明的限制。
[0027]以下結合附圖描述根據本發明實施例的片上網絡拓撲結構的重構方法及系統。
[0028]圖1是根據本發明一個實施例的片上網絡拓撲結構的重構方法的流程圖。如圖1所示，根據本發明一個實施例的片上網絡拓撲結構的重構方法，包括以下步驟:
[0029]步驟SIOI，根據片上網絡的初始拓撲結構建立有向圖，其中，有向圖中每個節點為初始拓撲結構中每個運算單元，運算單元包括正常運算單元、出錯運算單元和備用運算單元。其中，在本發明的一個實施例中，該出錯運算單元可通過對片上網絡的拓撲結構進行測試得到。
[0030]步驟S102，在有向圖中增加一個超級源點和一個超級匯點，其中，超級源點指向出錯運算單元，備用運算單元指向超級匯點。
[0031]步驟S103，應用最大流算法對有向圖進行求解以得到最大流量和每一條修復路徑，其中，最大流量表示可以被修復的出錯運算單元的數量。
[0032]步驟S104，根據修復路徑得到片上網絡的虛擬拓撲結構以對完成對片上網絡拓撲結構的重構。
[0033]綜上所述，作為一個具體例子，換言之，在上述方法中，首先將網絡結構看作一個有向圖，並增加一個超級源點，指向所有出錯的PE(運算單元)，增加一個超級匯點，所有備用PE都指向該匯點。每個節點和每條邊的容量限制設為「I」。對此單源點單匯點的網絡求解最大流，其中，最大流量等於可以被修復的出錯PE數目。每一條單位流對應於從出錯PE到備用PE的修復路徑。根據修復路徑，可以得到重構後的虛擬拓撲結構。
[0034]進一步地，在本發明的一個實施例中，該方法還包括:如果上述可以被修復的出錯運算單元的數量不等於出錯運算單元的數量，則判定存在不能被修復的出錯運算單元。也就是說在當前出錯模式下，不能找到一組包含所有出錯PE的修復路徑。
[0035]作為一個具體地示例，以下結合圖2-6，對本發明上述實施例的方法進行更為具體、詳細地描述。
[0036]首先介紹物理拓撲結構和虛擬拓撲結構。具體而言，在重構過程中，拓撲結構是一個重要的因素。由於事先不知道出錯PE (運算單元)的位置，當出錯PE被備用PE(運算單元)代替時，得到的拓撲結構可能變得不規則，並導致性能降低。例如圖2(a)是一個4X4的二維網格結構，即預期得到的目標設計。假設增加一列備用PE來提高晶片的可靠性，如圖2中(b)所示，即晶片上的實際情況。當出錯PE被備用PE代替時，如圖2中(c)和圖2中(d)所示，不同的晶片可能得到不同的拓撲結構，而這些拓撲結構可能和期望得到的結構也不同。這樣導致作業系統在不同的拓撲結構上優化並行程序時負擔會很重。
[0037]結合圖2和圖3,參考拓撲結構(Reference Topology)被定義為希望得到的拓撲結構。例如圖2中(a)就是一個4X4 二維網格的參考拓撲結構。圖3中(a)中有4個備用PE和4個出錯PE，出錯PE分別是2號、7號、8號和19號。物理拓撲結構(PhysicalTopology)是正常工作的PE所組成的結構，如圖3中(b)所示。儘管物理拓撲結構和參考拓撲結構不同，但是這些PE仍然可以構成一個4X4的處理器。在新得到的晶片中，每一個PE都被認為與其周圍的PE虛擬相連。因此重構得到的拓撲結構就被定義為虛擬拓撲結構(Virtual Topology)。圖3中(c)是一個4X4 二維網格虛擬拓撲結構的例子。在圖3中(c)中，3號、6號、9號和1 3號是12號PE的4個虛擬相鄰點，13號PE被虛擬認為位於12號PE的下方，儘管在物理上它們是左右相鄰的。雖然9號PE與12號PE實際相距3步，但是在虛擬拓撲結構中認為它們是相鄰的。對作業系統和其它應用程式來說，無論實際物理拓撲結構如何，虛擬拓撲結構都是相同的。這樣作業系統可以更容易地優化並行程序和分配任務。
[0038]假設位於(X，y)的非備用PE出錯了，在一個有效的修複方案中，該PE的功能被位於(X』，y』 )的正常工作PE所替代。更確切地說，(X』，y』 )的PE在重構的網絡中被重新編號為(x，y)。原本發往(x，y)的數據包將會發送到Ge』，y』)。出錯PE重新編號的過程是在重構時完成的。由於只改變了編號，而路由策略沒有發生變化，所以在運行時沒有額外的開銷。這樣數據包就通過NoC發送到邏輯上相鄰的節點。當(x，y)的PE被(x』，y』)的PE取代後，(x』，y』)的PE接著由(x』』，y』』)的PE所取代，直到這一取代過程以一個備用PE作為終點。這一替代過程中的有序序列(x, y), (x，，y，)，(χ』』，y』』)…就被定義為修復路徑。這是一個在邏輯上用備用PE取代出錯PE的序列。而一旦確定了修復路徑，每個PE的虛擬相鄰節點就可以確定，這樣就可以得到虛擬拓撲結構。
[0039]圖4給出了一個例子描述修復路徑和重構得到的虛擬拓撲結構的過程。如圖4所示，圖4中(a)的頂部有三個集中的出錯PE，分別由三條不相交的修復路徑連接至備用PE上。3號PE有錯，其由4號PE代替，4號PE由5號備用PE代替。這樣，原本應發送至3號PE的數據包將會發送給4號PE。舉個例子，在原來的拓撲結構中，如果數據要從9號PE發送到3號PE，傳輸路徑應該是9-8-3。但是在重構後的拓撲結構中，傳輸路徑是10-9-4，因為9號PE被10號PE所代替，8號PE由9號PE代替，3號PE由4號PE代替。這表明原始拓撲中的每個PE在虛擬拓撲結構中都被重新編號。這一映射過程通過查找表來完成，查找表儲存在每個路由器中。重構控制器計算出修復路徑後，將新的坐標分配給每個PE。進一步地，找到出錯PE後，為了修復該錯誤，修復路徑必須以出錯PE為起點，以一個備用PE為終點。由於數據包只能通過NoC傳送給物理相鄰節點，因此修復路徑上的PE序列必須在物理上相連，也就是說修復路徑必須連續。如果有網絡中有多條修復路徑，這些路徑不能相交。因為在虛擬拓撲結構中，每個PE只能映射到一個坐標上，路徑相交意味著該交點處的PE將被映射到兩個坐標上，所以不允許這種情況出現。在一些示例中，一組修復路徑必須滿足以下條件:每條修復路徑是連續的；該修復路徑組必須涵蓋所有出錯的非冗餘PE ;以及每條修復路徑不能相交。
[0040]另外，作為一個具體地例子，以下對上述涉及到的最大流算法進行簡單描述。具體而言，最大流算法可以分析一個網絡是否可以完全修復，以及如果可以修復，如何得到修復路徑。如果網絡中所有出錯PE都可以修復，MF(最大流算法)將生成一組修復路徑；如果不能完全修復，MF會生成一組可以最大限度修復出錯PE的修復路徑。生成一組不相交且連續的修復路徑的問題可以轉化為最大流問題。
[0041]進一步地，修復路徑和MF算法之間的關係如圖5所示。將網格看作一個有向圖，每一條修復路徑可以看作是從出錯PE到備用PE的單位流。這樣就變成了一個多源點多匯點的最大流問題。每個節點和每條邊的容量限制設為「1」，這樣保證在修復路徑中每個節點和每條邊最多只能出現一次。增加一個超級源點，指向所有出錯的PE，增加一個超級匯點，所有備用PE都指向該匯點。此時形成了一個單源點單匯點的網絡。由於每條修復路徑都是由源點到匯點的單位流，因此該網絡的最大流量就等於可以被修復的出錯PE數目。如果所有出錯PE都可以找到修復路徑，即所有出錯PE都可修復，此時網絡的最大流量等於出錯PE總數。這樣，NoC拓撲結構重構問題就轉化為了圖論中的最大流問題。
[0042]結合圖5中(a)和圖5中(b)所示，例如一個網格可以用有向圖G(V，E)來表示，V是該網絡中節點的集合，E是邊的集合，F是出錯節點的集合。每個節點代表一個PE和相應的路由器，而連接兩個節點的有向邊就是路由器之間的鏈路。每條邊和每個節點的容量都是I。該問題的數學描述方法如下:
[0043]1.節點集合定義為N' =VU {S，T}，S是源點，T是匯點。
[0044]2.連接V』中的節點的邊集合E如下定義:
[0045]I)對於網格中每一對相鄰節點(i, j)，定義兩條邊i — j和j — i ;
[0046]2)對於每一個備用節點u e V，定義邊u — T ;
[0047]3)對於每一個出錯節點u GF，定義邊S— U。
[0048]3.定義每條邊的容量為I。
[0049]4.定義每個節點的容量為I。
[0050]5.對上面構建的圖,求解最大流問題。
[0051]求解上述問題，將會得到該圖的最大流量以及每一條流。圖的最大流量表示有多少出錯PE可以被修復，每一條流代表一條修復路徑。根據修復路徑，可以得到虛擬拓撲結構，如圖4中(b)所示。每個PE的映射編號都存儲在路由器中，在運行時調用。另一方面，如果最大流量不等於出錯PE的數目，這表明有一些錯誤不能被修復。也就是說在當前出錯模式下，不能找到一組包含所有出錯PE的修復路徑。圖6給出了一個不能完全修復的出錯模式。圖6中有6個出錯PE和6個備用PE。其中一個備用PE是錯誤的。在這個模式裡，只有3個錯誤可以被修復，修復路徑也畫在圖6中。
[0052]綜上所示，作為一個具體示例，本發明上述實施例的方法的工作流程可以簡述如下:
[0053]步驟1:檢測網絡中錯誤。其中，錯誤的檢測可以有多種方式，如製造時測試、內建自測、周期性的在線測試等。
[0054]步驟2:更新錯誤信息。具體而言，一旦檢測出錯誤，關於哪些是出錯PE、哪些是備用PE的信息都存在一個集中的拓撲結構重構控制器中。
[0055]步驟3:將NoC拓撲結構重構問題轉化為最大流問題，求解得到修復後的虛擬拓撲結構。換言之，將網絡結構看作一個有向圖，增加一個超級源點，指向所有出錯的PE，增加一個超級匯點，所有備用PE都指向該匯點。每個節點和每條邊的容量限制設為「I」。對此單源點單匯點的網絡求解最大流。最大流量等於可以被修復的出錯PE數目。每一條單位流對應於從出錯PE到備用PE的修復路徑。根據修復路徑，可以得到重構後的虛擬拓撲結構。
[0056]步驟4:更改路由表。根據虛擬拓撲結構，對每一個路由器和PE重新編號，使NoC按照虛擬拓撲結構傳輸數據。
[0057]步驟5:程序繼續執行。
[0058]根據本發明實施例的片上網絡拓撲結構的重構方法，首先根據片上網絡的初始拓撲結構建立有向圖，並在有向圖中增加一個超級源點和一個超級匯點，進一步應用最大流算法對有向圖進行求解以得到最大流量和每一條修復路徑，最後根據修復路徑得到片上網絡的虛擬拓撲結構以對完成對片上網絡拓撲結構的重構。換言之，即本發明的方法採用冗餘硬體和動態重構的方式來提高系統的可靠性，容錯類型集中在解決永久性錯誤上，具有修復率高、重構時間短、硬體成本低的優點，同時保持很高的網絡吞吐率和低延時，此外，無論物理拓撲結構如何，該方法重構產生一致的虛擬拓撲結構，減小了作業系統在不同的拓撲結構上優化並行程序時的負擔。
[0059]本發明還提供了一種片上網絡拓撲結構的重構系統。
[0060]圖7是根據本發明一個實施例的片上網絡拓撲結構的重構系統的結構框圖。如圖7所示，根據本發明一個實施例的片上網絡拓撲結構的重構系統700，包括:建立模塊710、計算模塊720和重構模塊730。
[0061]具體而言，建立模塊710用於根據片上網絡的初始拓撲結構建立有向圖，其中，有向圖中每個節點為初始拓撲結構中每個運算單元，運算單元包括正常運算單元、出錯運算單元和備用運算單元，並在有向圖中增加一個超級源點和一個超級匯點，其中，超級源點指向出錯運算單元，備用運算單元指向超級匯點。其中，在本發明的一個實施例中，出錯運算單元可通過對片上網絡的拓撲結構進行測試得到。
[0062]計算模塊720用於應用最大流算法對有向圖進行求解以得到最大流量和每一條修復路徑，其中，最大流量表示可以被修復的出錯運算單元的數量。
[0063]重構模塊730用於根據修復路徑得到片上網絡的虛擬拓撲結構以對完成對片上網絡拓撲結構的重構。[0064]綜上所述，作為一個具體例子，換言之，上述系統700的工作原理簡述為:首先將網絡結構看作一個有向圖，並增加一個超級源點，指向所有出錯的PE(運算單元)，增加一個超級匯點，所有備用PE都指向該匯點。每個節點和每條邊的容量限制設為「I」。對此單源點單匯點的網絡求解最大流，其中，最大流量等於可以被修復的出錯PE數目。每一條單位流對應於從出錯PE到備用PE的修復路徑。根據修復路徑，可以得到重構後的虛擬拓撲結構。
[0065]進一步地，在本發明的一個實施例中，該片上網絡拓撲結構的重構系統700還包括判斷模塊740 (圖中未示出)。判斷模塊740用於在如果可以被修復的出錯運算單元的數量不等於出錯運算單元的數量時，判定存在不能被修復的出錯運算單元。也就是說在當前出錯模式下，不能找到一組包含所有出錯PE的修復路徑。
[0066]關於本發明實施例的片上網絡拓撲結構的重構系統700的更為詳細、具體地示例性描述，可參見本發明上述結合圖2-6對片上網絡拓撲結構的重構方法的描述部分，此處為減少冗餘，不再贅述。
[0067]根據本發明實施例的片上網絡拓撲結構的重構系統，根據片上網絡的初始拓撲結構建立有向圖，並在有向圖中增加一個超級源點和一個超級匯點，進一步應用最大流算法對有向圖進行求解以得到最大流量和每一條修復路徑，最後根據修復路徑得到片上網絡的虛擬拓撲結構以對完成對片上網絡拓撲結構的重構。換言之，該系統採用冗餘硬體和動態重構的方式來提高系統的可靠性，容錯類型集中在解決永久性錯誤上，具有修復率高、重構時間短、硬體成本低的優點，同時保持很高的網絡吞吐率和低延時，此外，無論物理拓撲結構如何，該系統重構產生一致的虛擬拓撲結構，減小了作業系統在不同的拓撲結構上優化並行程序時的負擔。
[0068]在本發明的描述中，需要理解的是，術語「中心」、「縱向」、「橫向」、「長度」、「寬度」、「厚度」、「上」、「下」、「前」、「後」、「左」、「右」、「豎直」、「水平」、「頂」、「底」 「內」、「外」、「順時
針」、「逆時針」、「軸向」、「徑向」、「周向」等指示的方位或位置關係為基於附圖所示的方位或位置關係，僅是為了便於描述本發明和簡化描述，而不是指示或暗示所指的裝置或元件必須具有特定的方位、以特定的方位構造和操作，因此不能理解為對本發明的限制。
[0069]此外，術語「第一」、「第二」僅用於描述目的，而不能理解為指示或暗示相對重要性或者隱含指明所指示的技術特徵的數量。由此，限定有「第一」、「第二」的特徵可以明示或者隱含地包括至少一個該特徵。在本發明的描述中，「多個」的含義是至少兩個，例如兩個，三個等，除非另有明確具體的限定。
[0070]在本發明中，除非另有明確的規定和限定，術語「安裝」、「相連」、「連接」、「固定」等術語應做廣義理解，例如，可以是固定連接，也可以是可拆卸連接，或成一體；可以是機械連接，也可以是電連接；可以是直接相連，也可以通過中間媒介間接相連，可以是兩個元件內部的連通或兩個元件的相互作用關係，除非另有明確的限定。對於本領域的普通技術人員而言，可以根據具體情況理解上述術語在本發明中的具體含義。
[0071]在本發明中，除非另有明確的規定和限定，第一特徵在第二特徵「上」或「下」可以是第一和第二特徵直接接觸，或第一和第二特徵通過中間媒介間接接觸。而且，第一特徵在第二特徵「之上」、「上方」和「上面」可是第一特徵在第二特徵正上方或斜上方，或僅僅表示第一特徵水平高度高於第二特徵。第一特徵在第二特徵「之下」、「下方」和「下面」可以是第一特徵在第二特徵正下方或斜下方，或僅僅表示第一特徵水平高度小於第二特徵。
[0072]在本說明書的描述中，參考術語「一個實施例」、「一些實施例」、「示例」、「具體示例」、或「一些示例」等的描述意指結合該實施例或示例描述的具體特徵、結構、材料或者特點包含於本發明的至少一個實施例或示例中。在本說明書中，對上述術語的示意性表述不必須針對的是相同的實施例或示例。而且，描述的具體特徵、結構、材料或者特點可以在任一個或多個實施例或示例中以合適的方式結合。此外，在不相互矛盾的情況下，本領域的技術人員可以將本說明書中描述的不同實施例或示例以及不同實施例或示例的特徵進行結合和組合。
[0073]儘管上面已經示出和描述了本發明的實施例，可以理解的是，上述實施例是示例性的，不能理解為對本發明的限制，本領域的普通技術人員在本發明的範圍內可以對上述實施例進行變化、修改、替換和變型。
【權利要求】
1.一種片上網絡拓撲結構的重構方法，其特徵在於，包括以下步驟: 根據片上網絡的初始拓撲結構建立有向圖，其中，所述有向圖中每個節點為所述初始拓撲結構中每個運算單元，所述運算單元包括正常運算單元、出錯運算單元和備用運算單元; 在所述有向圖中增加一個超級源點和一個超級匯點，其中，所述超級源點指向所述出錯運算單元，所述備用運算單元指向所述超級匯點； 應用最大流算法對所述有向圖進行求解以得到最大流量和每一條修復路徑，其中，所述最大流量表示可以被修復的出錯運算單元的數量； 根據所述修復路徑得到所述片上網絡的虛擬拓撲結構以對完成對所述片上網絡拓撲結構的重構。
2.根據權利要求1所述的方法，其特徵在於，其中，所述出錯運算單元通過對所述片上網絡的拓撲結構進行測試得到。
3.根據權利要求1所述的方法，其特徵在於，還包括: 如果所述可以被修復的出錯運算單元的數量不等於所述出錯運算單元的數量，則判定存在不能被修復的出錯運算單元。
4.一種片上網絡拓撲結構的重構系統，其特徵在於，包括: 建立模塊，用於根據片上網絡的初始拓撲結構建立有向圖，其中，所述有向圖中每個節點為所述初始拓撲結構中每個運算單元，所述運算單元包括正常運算單元、出錯運算單元和備用運算單元，並在所述有向圖中增加一個超級源點和一個超級匯點，其中，所述超級源點指向所述出錯運算單元，所述備用運算單元指向所述超級匯點； 計算模塊，用於應用最大流算法對所述有向圖進行求解以得到最大流量和每一條修復路徑，其中，所述最大流量表示可以被修復的出錯運算單元的數量； 重構模塊，用於根據所述修復路徑得到所述片上網絡的虛擬拓撲結構以對完成對所述片上網絡拓撲結構的重構。
5.根據權利要求4所述的系統，其特徵在於，其中，所述出錯運算單元通過對所述片上網絡的拓撲結構進行測試得到。
6.根據權利要求4所述的系統，其特徵在於，還包括:判斷模塊，用於如果所述可以被修復的出錯運算單元的數量不等於所述出錯運算單元的數量，則判定存在不能被修復的出錯運算單元。
【文檔編號】H04L12/931GK103986672SQ201410222922
【公開日】2014年8月13日 申請日期:2014年5月23日 優先權日:2014年5月23日
【發明者】任彧, 劉雷波, 陳繼強, 尹首一, 魏少軍 申請人:清華大學