[發明專利]基于網絡拓撲結構的超級計算機大數據處理能力測試方法

有效

• 申請號: 202011093055.3
• 申請日: 2020-10-13
• 公開（公告）號: CN112165405B
• 公開（公告）日: 2022-04-22
• 發明（設計）人: 甘新標;龔春葉;楊博;陳旭光;肖調杰;譚雯
• 申請（專利權）人: 中國人民解放軍國防科技大學
• 主分類號: H04L41/0823
• 分類號: H04L41/0823;H04L41/14;H04L41/12;H04L43/0817
• 代理公司: 湖南企企衛知識產權代理有限公司 43257
• 代理人: 任合明

1.一種基于網絡拓撲結構的超級計算機大數據處理能力測試方法，其特征在于包括以下步驟：

第一步、圖生成，方法是：采用Kronecker圖生成器生成隨機圖結構G＝(V,E)，V為頂點集合，N_V為V中頂點個數，N_V為正整數；E為邊集合，N_E為E中包含邊的條數，N_E為正整數；使用v_i表示G中編號為i的頂點，使用頂點對(v_i,v_j)表示頂點i到頂點j的邊，(v_i,v_j)∈E，0≤i≤N_V-1，0≤j≤N_V-1，i和j均為正整數；

第二步、圖存儲變換，方法是：構建存儲圖G的鄰接矩陣A，A_ij＝0表示頂點i與頂點j之間沒有邊，A_ij＝1表示頂點i與頂點j之間有邊；

第三步、根據被測超級計算機系統胖樹網絡結構確定N叉樹拓撲結構模型，N為2的整數次冪；Q+2層的胖樹網絡由根交換機、Q層節點交換機、葉交換機組成，根交換機的網絡接口上連接第1層節點交換機，第q層節點交換機的網絡接口上連接第q+1層節點交換機，1≤q≤Q-1，第Q層節點交換機的網絡接口連接葉交換機；葉交換機的端口連接被測超級計算機系統的高性能結點，圖G的頂點存儲在高性能結點上；Q由超級計算機系統高性能結點總數M的值和N的值共同確定，操作符表示向上取整；胖樹網絡中的根交換機、節點交換機、葉交換機采用相同的交換機NRM，NRM包含1個網絡進口，N個網絡出口；根據被測超級計算機系統胖樹網絡結構確定N叉樹拓撲結構模型的方法為：根交換機的網絡進口備用；第q層節點交換機的N^q個網絡進口與第q－1層節點交換機的網絡出口相連，第q層節點交換機的共N×N^q個網絡出口分別與第q+1層節點交換機的網絡進口相連；q等于1時，第q－1層節點交換機指根交換機；第Q層節點交換機的N×N^Q個網絡出口分別與N×N^Q個葉交換機相連，葉交換機的網絡出口與超級計算機系統高性能結點相連；N叉樹最多可連接N^(Q+2)個超級計算機高性能結點；

第四步、按照N叉樹拓撲結構模型將圖G的頂點重新分布到被測超級計算機的高性能計算結點上，得到與N叉樹拓撲結構模型相適應的匹配樹，方法是：

4.1.查詢被測超級計算機系統體系結構文件，獲取被測超級計算機系統的網絡拓撲結構，獲得每個葉交換機連接被測超級計算機系統高性能結點的有效端口數cn；

4.2.從G中隨機選擇一個頂點v作為匹配樹的樹根頂點；

4.3.令匹配樹的當前根頂點Cur＝v；

4.4.令變量cn'＝cn-1；

4.5.依據有效端口數cn，將與v存在邊關聯的cn'個頂點分布至v所屬的葉交換機路由范圍內，即當前根頂點與關聯的cn'個頂點屬于同一葉交換機葉路由范圍，若與當前根頂點Cur相關聯的頂點數大于cn，選擇邏輯編號相近的cn'個頂點分布至Cur所屬的葉交換機路由范圍內的高性能結點上；若與Cur相關聯的頂點數小于cn，選取與Cur沒有邊關聯但邏輯編號相近的頂點補齊，具體步驟如下：

4.5.1.定義變量i＝0；

4.5.2.初始化已分布集合采用S存儲匹配樹，初始化待分布集合

4.5.3.初始化葉交換機集合R＝{r₁,r₂,…,r_p,…,r_nr}，nr為被測超級計算機中的葉交換機總數，r_p是被測超級計算機中的第p個葉交換機，1≤p≤nr；

4.5.4.初始化臨時端口數port＝cn，初始化端口剩余變量Δcn＝cn；

4.5.5.初始化當前根頂點Cur的有效關聯頂點數cpn＝0；

4.5.6.令變量j＝i；

4.5.7.若從R中任意選取一個葉交換機，令為當前葉交換機r_p；

否則，令R＝{r₁,r₂,…,r_p,…,r_nr}；

4.5.8.從R中刪除當前葉交換機，即，R＝R-{r_p}；

4.5.9.從V選取頂點v_i，并令為當前根頂點Cur＝v_i，將Cur的頂點相關信息分布至當前葉交換機r_p路由范圍內的高性能計算結點；

4.5.10.令port＝port-1；

4.5.11.將已完成分布處理的Cur加入已分布集合S，即，令S＝S+{v_i}；cpn＝cpn+1，Δcn＝Δcn-1；

4.5.12.令j＝j+1；

4.5.13.若j≤N_V-1，轉4.5.14，否則，轉4.5.24；

4.5.14.若Δcn＞0，說明當前葉交換機r_p關聯頂點數小于cn，轉4.5.15；否則，關聯頂點數大于cn，轉4.5.20；

4.5.15.遍歷G的鄰接矩陣A，查詢與Cur關聯的頂點v_j，即判斷A_ij＝1是否成立，若成立，轉4.5.16；若不成立，令S_d＝S_d+{v_j}，轉4.5.12繼續查找關聯頂點；

4.5.16.若Δcn＞0，將頂點v_j分布至當前葉交換機r_p路由范圍內的高性能計算節點，令S＝S+{v_i}，轉4.5.17；否則，關聯頂點數大于cn，轉4.5.20；

4.5.17.令cpn＝cpn+1，Δcn＝Δcn-1；

4.5.18.若Δcn＞0，轉4.5.19；否則，與Cur存在邊關聯的頂點數大于cn，轉4.5.20；

4.5.19.若cpn≤cn，轉4.5.12，繼續查找Cur的關聯頂點；否則，Cur的關聯頂點數大于cn，轉4.5.20；

4.5.20.與Cur關聯的頂點數大于cn，按以下方法進行處理：將S_d中與v_i編號最近的頂點v_j取出并分布至與當前葉交換機r_p路由范圍內的高性能計算節點，令Δcn＝Δcn-1，S_d＝S_d-{v_j}；

4.5.21.若Δcn＞0成立，轉4.5.22；否則，轉4.5.23；

4.5.22.將v_j加入集合S，即，S＝S+{v_j}；

4.5.23.令port＝port-1；

4.5.24.若port＜Δcn，當前交換有效端口還沒有用完，轉4.5.19，否則，當前根節點Cur分布完畢，轉4.5.25，繼續分布G中的剩余頂點；

4.5.25.令i＝i+1；

4.5.26.若i≤N_V-1成立，轉4.5.5，否則，G中的所有頂點均已分布，轉第五步；

第五步、根據匹配樹對圖G進行BFS搜索，具體方法如下：

5.1.數據結構定義，具體方法如下：

5.1.1.定義未被訪問的頂點集合V_ns＝V；

5.1.2.定義BFS搜索的頂點中間集合D-tmp＝V_ns；

5.1.3.定義分布后中間集合Deg-tmp＝S，依據“將與當前根頂點Cur存在邊關聯的cn'個頂點分布至Cur所屬的葉交換機路由范圍內”的原則，當前根頂點Cur與cn'個頂點之間大概率存在邊關聯，以當前根頂點Cur與cn'個頂點為基礎，依據第三步構造的N叉樹拓撲結構模型將圖頂點分布至高性能計算結點上；

5.1.4.定義被訪問過的頂點集合

5.1.5.定義當前層頂點集合

5.1.6.定義當前層子節點集合

5.1.7.定義頂點v_i的子節點集合

5.1.8.在V中隨機選定一個頂點v_r作為樹根節點，即源頂點，

r＝0,1,…,N_V-1；

5.1.9.令樹根節點v_r的子節點集合的集合Son_r中的元素是集合；

5.1.10.將v_r加入已被訪問過的頂點集合V_s中，即令V_s＝V_s+{V_r}；

5.1.11.將頂點v_r加入當前頂點集合Cur中，即令Cur＝Cur+{V_r}；

5.2.循環遍歷，一次循環輸出一棵生成樹，循環64次，輸出64棵生成樹，具體方法如下：

5.2.1.定義循環變量k＝0，定義變量m＝0；

5.2.2.獲取系統時刻t₁；

5.2.3.若k＜64，轉5.2.4；否則，轉第六步；

5.2.4.同層遍歷，利用度數高的頂點存在邊關聯的概率也高的特點，遍歷搜索Cur中節點的子節點，具體方法如下：

令

5.2.4.1.若執行5.2.4.3，否則，本層搜索完成，轉5.2.5，對下一層進行遍歷；

5.2.4.2.在Cur中任取一個頂點v_i，記為當前根節點v_cs，cs＝0,1,…,N_V；

5.2.4.3.從Cur中刪除v_cs，即令Cur＝Cur-{v_cs}；

5.2.4.4.若執行5.2.4.6，否則，當前根節點v_cs搜索完畢，轉5.2.4.16；

5.2.4.5.從未被訪問的頂點集合V_ns中刪除當前根節點v_cs，即V_ns＝V_ns-{v_cs}；

5.2.4.6.從Deg-tmp中選擇一個頂點，令為v_j；

5.2.4.7.查詢鄰接矩陣A，若A_ij＝1，表示頂點v_i與頂點v_j之間有邊，執行5.2.4.9，否則，轉5.2.4.11；

5.2.4.8.從集合Deg-tmp中刪除已有邊關聯的頂點，即Deg-tmp＝Deg-tmp-{v_j}；

5.2.4.9.若v_j∈V_ns，將頂點v_j從V_ns中刪除，即V_ns＝V_ns-{v_j}，直接轉5.2.4.11；否則，說明不需要從V_ns中刪除，轉5.2.4.12；

5.2.4.10.更新當前根節點v_cs，即，Son_i＝Son_i+{v_j}；

5.2.4.11.更新當前層的子節點集合L-Son，即令L-Son＝L-Son+{v_j}；5.2.4.12.將當前根節點的子節點集合以集合元素的形式加入Son_r中，即Son_r＝Son_r+{Son_i}；

5.2.4.13.變量m＝m+1；

5.2.4.14.將頂點v_j從V_ns中刪除，即令V_ns＝V_ns-{v_j}；

5.2.4.15.若轉5.2.4.5，否則，所有未被訪問過的頂點遍歷完畢，轉5.2.4.17；

5.2.4.16.從當前頂點集合Cur中刪除前根節點v_cs，即令Cur＝Cur-{v_cs}；5.2.4.17.轉5.2.4.1；

5.2.5.層間遍歷，具體方法如下：

5.2.5.1.重置當前頂點集合Cur，即令

5.2.5.2.將當前層子節點集合L-Son賦值給當前頂點集合Cur，即令Cur＝L-Son；

5.2.5.3.獲取系統時刻t₂；

5.2.5.4.記錄第k次啟發式遍歷搜索的時間t＝t₂-t₁；

5.2.6.輸出樹根節點集合Son_r，Son_r即為第k輪循環以頂點v_r作為樹根節點的BFS的生成樹root_k-r；

5.2.7.計算當前生成樹root_k-r的BFS遍歷測試性能值

5.2.8.k＝k+1，轉5.2.3；

第六步、計算圖測試性能的評價值，即64棵生成樹的BFS遍歷測試性能值平均值獲得測試結果， TEPS值越高表明超級計算機的大規模圖處理能力越強，Graph500排名也越靠前，同時也反映了該超級計算機越適合與大數據處理；

第七步、結束。

2.如權利要求1所述的一種基于網絡拓撲結構的超級計算機大數據處理能力測試方法，其特征在于所述N＝2或N＝8。