[發明專利]針對演進圖形分配全局邊緣ID

有效

• 申請號: 201580063517.8
• 申請日: 2015-10-12
• 公開（公告）號: CN107004011B
• 公開（公告）日: 2021-08-03
• 發明（設計）人: X·朱;T·L·維爾克;B·凱勒;S-C·陳;K·達塔
• 申請（專利權）人: 英特爾公司
• 主分類號: G06F16/901
• 分類號: G06F16/901
• 代理公司: 永新專利商標代理有限公司 72002
• 代理人: 劉瑜;王英

1.一種利用圖形處理關系數據的方法，用于針對演進圖形計算全局邊緣ID，包括：

針對包括多個頂點和多個邊緣的演進圖形選擇塊大小，其中所述邊緣是對應于所述頂點的實際關系數據的視覺表示；

針對所述演進圖形計算塊ID，其中，計算所述塊ID包括：

創建表示所述演進圖形的表，其中，所述表包括所選擇的塊大小的單元格、表示源頂點ID的y軸、以及表示目標頂點ID的x軸；以及

當新的頂點被添加到所述演進圖形時，在針對所述表的新行中的單元格計算塊ID之前針對所述表的新列中的單元格計算塊ID；以及

針對所述演進圖形基于所述源頂點ID、所述目標頂點ID、以及針對每個邊緣所位于的塊的所述塊ID來計算全局邊緣ID。

2.根據權利要求1所述的方法，其中，在針對所述表的新行中的單元格計算塊ID之前針對所述表的新列中的單元格計算塊ID包括：

當新的頂點被添加到所述演進圖形時添加新列；

針對所述新列中的單元格計算塊ID；

一旦已經針對所述新列中的所述單元格計算塊ID，則添加新行；以及

針對所述新行中的單元格計算塊ID。

3.根據權利要求2所述的方法，包括當新的頂點被不斷地添加到所述演進圖形時重復權利要求2所述的方法。

4.根據權利要求1或2中任一項所述的方法，包括在遞歸函數中計算所述塊ID。

5.根據權利要求4所述的方法，其中，在所述遞歸函數中計算所述塊ID包括，基于每個單元格的源頂點ID和針對所述表中的最后的對角線單元格所計算的塊ID，針對所述表的新列中的每個單元格計算所述塊ID。

6.根據權利要求4所述的方法，其中，在所述遞歸函數中計算所述塊ID包括，基于每個單元格的目標頂點ID和針對所述表中的最后的對角線單元格右側的單元格所計算的塊ID，針對所述表的新行中的每個單元格計算所述塊ID。

7.根據權利要求1所述的方法，包括在針對所述表的新列中的單元格計算塊ID之前針對所述表的新行中的單元格計算塊ID。

8.根據權利要求7所述的方法，其中，在針對所述表的新列中的單元格計算塊ID之前針對所述表的新行中的單元格計算塊ID包括：

當新的頂點被添加到所述演進圖形時添加新行；

針對所述新行中的單元格計算塊ID；

一旦已經針對所述新行中的所述單元格計算塊ID，則添加新列；以及

針對所述新列中的單元格計算塊ID。

9.根據權利要求8所述的方法，包括當新的頂點被不斷地添加到所述演進圖形時重復權利要求8所述的方法。

10.根據權利要求1或7中任一項所述的方法，包括高速緩存針對每個對角線單元格和所述表中每個對角線單元格右側的單元格的塊ID。

11.根據權利要求1或7中任一項所述的方法，包括通過以下操作針對所述演進圖形計算增量頁面排序：

使用靜態算法在第一處理窗口中計算頁面排序值；

將所計算的頁面排序值保存為所述第一處理窗口的圖形狀態；

利用先前處理窗口的頁面排序值來初始化每個處理窗口處的頂點值；

如果新的邊緣被添加而所述新的邊緣的源頂點值在先前處理窗口中已經存在，則在當前處理窗口的第一次迭代中，將從所述先前處理窗口接收的所述源頂點的所有更新快速轉發到目標頂點；

對于所有其它類型的邊緣，如果所述邊緣的源頂點值不存在，則計算所述源頂點值在當前迭代與先前迭代之間的變化，并將所述源頂點值的變化發送到目標頂點；

繼續此過程，直到已經針對所有頂點計算頂點值；以及

針對所述演進圖形將所述頂點值保存為增量頁面排序值。