[發明專利]圖數據劃分方法及裝置

有效

• 申請號: 201610101409.1
• 申請日: 2016-02-24
• 公開（公告）號: CN105787020B
• 公開（公告）日: 2019-05-21
• 發明（設計）人: 武永衛;章明星;陳康;鄭緯民
• 申請（專利權）人: 鄞州浙江清華長三角研究院創新中心
• 主分類號: G06F16/2458
• 分類號: G06F16/2458
• 代理公司: 北京清亦華知識產權代理事務所(普通合伙) 11201
• 代理人: 張大威

1.一種圖數據劃分方法，其特征在于，包括以下步驟：

根據圖定義的數據和計算模型UPPS對算法進行建模；

通過二維數據劃分方法對所述建模中的數據進行劃分，并獲取劃分后冗余度最小的數據；

根據估測公式估測確定最佳的第三維層數；以及

根據所述冗余度最小的數據對所述第三維層數的每一層進行劃分，獲得數據的分布方式；

其中，所述計算模型UPPS具體包括：

在一張數據圖作為基本的操作單元，區分不可以劃分的數據DShare和可以劃分的數據DColle，其中DColle為一個長度為SC的向量；

提供4種操作類型，分別為：Update、Push、Pull和Sink，其中，所述Update的操作為獲取每個圖的點或邊并對所述每個圖的所有數據進行更新，所述Push的操作為用源點和邊的數據更新匯點，所述Pull的操作為用匯點和邊的數據更新源點，所述Sink的操作為用源點和匯點的數據更新邊；

所述根據估測公式估測確定最佳的第三維層數具體包括：

根據所述計算模型UPPS中的4種操作類型確定每一層通訊量的估測公式；

根據所述估測公式確定每一層的最終通訊量，選擇通訊量最小的作為所述第三維層數。

2.如權利要求1所述的圖數據劃分方法，其特征在于，所述二維數據劃分方法包括：點劃分、邊劃分和復合劃分。

3.如權利要求1所述的圖數據劃分方法，其特征在于，根據所述冗余度最小的數據對所述第三維層數的每一層進行劃分，獲得數據的分布方式具體包括：

所述冗余度最小的數據對應的計算節點劃分為第三維層數組；

所述第三維層數組中的每一組計算節點負責維護所述第三維層數中的一層。

4.一種圖數據劃分裝置，其特征在于，包括：

處理模塊，用于根據圖定義的數據和計算模型UPPS對算法進行建模；

第一劃分模塊，用于通過二維數據劃分方法對所述建模中的數據進行劃分；

獲取模塊，用于獲取所述第一劃分模塊劃分后冗余度最小的數據；

確定模塊，用于根據估測公式估測確定最佳的第三維層數；以及

第二劃分模塊，用于根據所述冗余度最小的數據對所述第三維層數的每一層進行劃分，獲得數據的分布方式；

其中，所述計算模型UPPS具體包括：

在一張數據圖作為基本的操作單元，區分不可以劃分的數據DShare和可以劃分的數據DColle，其中DColle為一個長度為SC的向量；

提供4種操作類型，分別為：Update、Push、Pull和Sink，其中，所述Update的操作為獲取每個圖的點或邊并對所述每個圖的所有數據進行更新，所述Push的操作為用源點和邊的數據更新匯點，所述Pull的操作為用匯點和邊的數據更新源點，所述Sink的操作為用源點和匯點的數據更新邊；

所述確定模塊具體包括：

第一確定單元，用于根據所述計算模型UPPS中的4種操作類型確定每一層通訊量的估測公式；

第二確定單元，用于根據所述估測公式確定每一層的最終通訊量；

選擇單元，用于選擇通訊量最小的作為所述第三維層數。

5.如權利要求4所述的圖數據劃分裝置，其特征在于，所述二維數據劃分方法包括：點劃分、邊劃分和復合劃分。

6.如權利要求4所述的圖數據劃分裝置，其特征在于，所述第二劃分模塊具體包括：

劃分單元，用于所述冗余度最小的數據對應的計算節點劃分為第三維層數組；

維護單元，用于所述第三維層數組中的每一組計算節點負責維護所述第三維層數中的一層。