[發明專利]一種高能效協同圖計算方法及裝置

在審

• 申請號: 202210525819.4
• 申請日: 2022-05-12
• 公開（公告）號: CN114817648A
• 公開（公告）日: 2022-07-29
• 發明（設計）人: 張宇;趙進;沈千格;姜新宇;余輝;齊豪;楊赟;李仕俊;廖小飛;金海
• 申請（專利權）人: 華中科技大學
• 主分類號: G06F16/901
• 分類號: G06F16/901;G06F15/78
• 代理公司: 北京之于行知識產權代理有限公司 11767
• 代理人: 侯越玲

1.一種高能效協同圖計算裝置，其特征在于，至少包括：

依賴路徑預取單元(3)：被配置為接收活躍頂點信息，并且從循環隊列中活躍頂點開始沿依賴路徑預取圖分區的邊；和

直接依賴管理單元(5)：被配置為將核心依賴路徑上首尾頂點間的依賴關系轉換為直接依賴。

2.根據權利要求1所述的高能效協同圖計算裝置，其特征在于，所述直接依賴管理單元(5)還被配置為：

在動態圖處理過程中，基于圖結構的變化獲取已失效的依賴索引，并且將所述已失效的依賴索引刪除以更新依賴索引。

3.根據權利要求1～2任一項所述的高能效協同圖計算裝置，其特征在于，所述依賴路徑預取單元(3)從活躍頂點開始沿依賴路徑預取圖分區的邊的方式至少包括：

在加速器初始化的情況下，以四段流水線形式完成邊的預取，并且將獲取的邊以及與邊對應的一對頂點的狀態輸出到FIFO邊緩沖區以供處理器內核進行訪問處理。

4.根據權利要求1～3任一項所述的高能效協同圖計算裝置，其特征在于，所述依賴路徑預取單元(3)以四段流水線形式完成邊的預取的方式至少包括：

若棧為空，則從循環隊列中獲取一個活躍頂點，并且將其壓棧；

從偏移數組獲取棧頂頂點的出邊起始/結束偏移；

根據所述棧頂頂點的未訪問邊獲取未訪問鄰居頂點的ID，并將其中一個鄰居頂點壓棧；

從頂點狀態數組獲取相關頂點的狀態，將邊以及與邊對應的一對頂點的狀態輸出到FIFO邊緩沖區；若棧頂頂點屬于頂點集合H^m，則棧頂頂點出棧，并且將其插入循環隊列作為新的活躍頂點；若無法從棧頂頂點的鄰居中獲取到圖分區G^m中的未訪問頂點，則棧頂頂點出棧。

5.根據權利要求1～4任一項所述的高能效協同圖計算裝置，其特征在于，所述直接依賴管理單元(5)將核心依賴路徑上首尾頂點間的依賴關系轉換為直接依賴關系的公式至少表示為：

其中s_j、s_i表示頂點j、i的狀態值，μ、ξ表示常數參數。

6.根據權利要求1～5任一項所述的高能效協同圖計算裝置，其特征在于，所述直接依賴管理單元(5)將核心依賴路徑上首尾頂點間的依賴關系轉換為直接依賴的方式至少包括：

在第一次完成對核心依賴路徑l的處理時，將其首尾頂點的編號j、i以及第一狀態值s_j、s_i保存至直接依賴索引數組，并且將索引標識flag設置為I；其中，所述核心依賴路徑l為首尾頂點都屬于頂點集H^m的路徑；

在第二次完成對路徑l的處理時，獲得首尾頂點的第二狀態值s′_j、s′_i，將所述第二狀態值s′_j、s′_i和第一狀態值s_j、s_i代入直接依賴關系的公式，計算常數參數μ、ξ的值，

將所述常數參數μ和ξ的值保存至直接依賴索引數組，并將索引標識flag設置為A。

7.根據權利要求1～6任一項所述的高能效協同圖計算裝置，其特征在于，所述裝置還包括片上緩存單元(4)，

所述片上緩存單元(4)與所述直接依賴管理單元(5)建立數據連接關系，

所述直接依賴管理單元(5)通過內存哈希表來構建頂點ID與直接依賴索引地址間的映射關系，并且在所述片上緩存單元(4)建立緩存哈希表，其中，

所述直接依賴管理單元(5)按照定制化的插入策略和/或替換策略將內存哈希表中被頻繁訪問的表項與產生沖突的表項緩存至所述片上緩存單元(4)。