[發(fā)明專利]利用基于向量估計的圖分割的計算裝置的數(shù)據(jù)流編程

有效

• 申請?zhí)枺?/td>: 201611271687.8
• 申請日: 2016-11-24
• 公開（公告）號: CN106919380B
• 公開（公告）日: 2020-06-16
• 發(fā)明（設(shè)計）人: L·J·孫;V·R·托溫科雷
• 申請（專利權(quán)）人: 英特爾公司
• 主分類號: G06F8/34
• 分類號: G06F8/34
• 代理公司: 中國專利代理(香港)有限公司 72001
• 代理人: 李嘯;付曼

1.一種計算裝置，配備為支持?jǐn)?shù)據(jù)流編程，包括：

一個或多個計算處理器；以及

譜圖分割器，用于在所述一個或多個計算處理器上操作以將與程序關(guān)聯(lián)的數(shù)據(jù)流圖分割為多個子圖；

其中所述譜圖分割器包括：

向量估計器，用于生成一個或多個估計向量，以將所述數(shù)據(jù)流圖分割為所述多個子圖；以及

群集確定器，用于：

基于所述一個或多個估計向量定義多維空間；以及

聚類所述數(shù)據(jù)流圖的節(jié)點以形成所述多維空間中的所述多個子圖；

并且其中所述多個子圖用于所述程序的分析或調(diào)試，且所述程序用于對所述計算裝置或另一計算裝置編程以執(zhí)行任務(wù)。

2.如權(quán)利要求1所述的計算裝置，其中所述向量估計器用于通過生成描述所述數(shù)據(jù)流圖的拉普拉斯矩陣的本征向量而生成所述一個或多個估計向量。

3.如權(quán)利要求2所述的計算裝置，其中所述向量估計器用于通過最小化由描述的函數(shù)而生成本征向量作為向量，其中為所述數(shù)據(jù)流圖中的頂點的數(shù)量并且為常量。

4.如權(quán)利要求3所述的計算裝置，其中所述函數(shù)的最小化包括對所述函數(shù)執(zhí)行梯度下降。

5.如權(quán)利要求3所述的計算裝置，其中所述常量的值至少部分基于所述數(shù)據(jù)流圖的度并且為所述數(shù)據(jù)流圖的度的倒數(shù)。

6.如權(quán)利要求3所述的計算裝置，其中生成本征向量包括在最小化所述函數(shù)之前將所述向量的一個坐標(biāo)設(shè)置為0。

7.如權(quán)利要求6所述的計算裝置，其中生成本征向量包括：在最小化所述函數(shù)之后將已被設(shè)置為0的坐標(biāo)設(shè)置為其坐標(biāo)鄰居的均值。

8.如權(quán)利要求1-7的任一項所述的計算裝置，其中所述群集確定器用于通過執(zhí)行均值聚類過程而將所述數(shù)據(jù)流圖的節(jié)點聚類以形成所述多個子圖。

9.如權(quán)利要求1-7的任一項所述的計算裝置，其中所述譜圖分割器進一步包括質(zhì)量度量確定器，用于對給定所述數(shù)據(jù)流圖的節(jié)點的聚類確定用于所述節(jié)點的聚類的一個或多個質(zhì)量度量。

10.如權(quán)利要求9所述的計算裝置，其中所述質(zhì)量度量確定器用于確定用于所述節(jié)點的聚類的模塊化度量或群集路徑長度度量。

11.如權(quán)利要求9所述的計算裝置，其中所述譜圖分割器進一步包括細(xì)化控制器，用于至少部分地基于所述一個或多個質(zhì)量度量而使得估計向量的生成和所述數(shù)據(jù)流圖的節(jié)點的聚類重復(fù)進行。

12.如權(quán)利要求11所述的計算裝置，其中所述細(xì)化控制器用于使所述數(shù)據(jù)流圖的節(jié)點聚類為由于生成附加的估計向量而增加的數(shù)量的群集。

13.如權(quán)利要求1-7的任一項所述的計算裝置，進一步包括分割器選擇器，用于在利用所述譜圖分割器或所述裝置的一個或多個其他圖分割器之間選擇。

14.如權(quán)利要求13所述的裝置，其中所述分割器選擇器用于至少部分地基于所述數(shù)據(jù)流圖的尺寸或為由所述譜圖分割器生成的一個或多個聚類確定的一個或多個質(zhì)量度量而進行選擇。

15.如權(quán)利要求13所述的裝置，其中所述分割器選擇器用于在所述譜圖分割器和邊緣中心化分割器之間選擇。