[發明專利]一種用于并行地控制多個處理單元的設備、方法、系統

有效

• 申請號: 201480056629.6
• 申請日: 2014-10-13
• 公開（公告）號: CN105706057B
• 公開（公告）日: 2019-06-18
• 發明（設計）人: T·D·米可維茨;M·穆蘇瓦蒂;S·馬利基
• 申請（專利權）人: 微軟技術許可有限責任公司
• 主分類號: G06F9/50
• 分類號: G06F9/50;G06Q10/04;G06F17/11;H03M13/00
• 代理公司: 上海專利商標事務所有限公司 31100
• 代理人: 胡利鳴

1.一種用于并行地控制多個處理單元(206(1)，206(2))的設備(402)，所述設備(402)包括：

用于處理動態編程問題(102)的第一處理單元(206(1))，所述動態編程問題(102)包括第一和第二階段(104(1)，104(2))，其中第一階段(104(1))的輸出用作對于后續第二階段(104(2))的輸入，并且所述第一和所述第二階段(104(1)，104(2))之間的依賴性在熱帶半環中是線性的；

用于處理所述動態編程問題(102)的第二處理單元(206(2))；以及

與所述第一和所述第二處理單元(206(1)，206(2))通信的存儲器(412A)，所述存儲器(412A)包括：

用于確定所述動態編程問題(102)的第一和第二階段(104(1)，104(2))的階段創建模塊(416)，

用于確定所述第一和所述第二階段(104(1)，104(2))之間的至少一個依賴性的依賴性標識模塊(414)，所述依賴性是第一階段輸出與第二階段輸入的耦合，以及

用于以下的并行執行模塊(420)：

通過將獨立于所述第一階段輸出的所生成的輸入(118)用作所述第二階段輸入來打破所述至少一個依賴性，以及

與所述第一處理單元(206(1))上的所述第一階段(104(1))并行地處理所述第二處理單元(206(2))上的所述第二階段(104(2))，以計算針對所述動態編程問題(102)的解，以及

群集創建模塊(418)，所述群集創建模塊用于將所述第一階段(104(1))與所述動態編程問題(102)的其它階段的第一集(202(3)，202(4))群集(508)在一起來形成第一群集，并將所述第二階段(104(2))與所述動態編程問題(102)的其它階段的第二集(202(5)，202(6))群集在一起來形成第二群集，

其中所述并行執行模塊(420)還與所述第一處理單元(206(1))上的所述第一群集并行地處理所述第二處理單元(206(2))上的所述第二群集，以計算所述解。

2.如權利要求1所述的設備(402)，其特征在于，所述并行執行模塊(420)還標識所述第二群集內的一階段，在該階段中秩收斂到1，以指示基于所述所生成的輸入(118)的所述解是在所述依賴性沒有被打破的情況下計算的。

3.一種用于并行地控制多個處理單元(206(1)，206(2))以處理動態編程問題(102)的方法，所述動態編程問題(102)包括第一和第二階段(104(1)，104(2))，其中第一階段(104(1))的輸出用作對于后續第二階段(104(2))的輸入，并且所述第一和所述第二階段(104(1)，104(2))之間的依賴性在熱帶半環中是線性的，所述方法包括：

使用階段創建模塊(416)來確定(506)所述動態編程問題(102)的第一階段(104(1))和第二階段(104(2))；

使用依賴性標識模塊(414)來標識(504)所述第一和所述第二階段(104(1)，104(2))之間的至少一個依賴性，所述依賴性是第一階段輸出與第二階段輸入的耦合；

使用并行執行模塊(420)來生成(510)要被用作所述第二階段輸入的獨立于所述第一階段輸出的所生成的輸入(118)；

使用所述并行執行模塊(420)來與第一處理單元(206(1))上的所述第一階段(104(1))并行地處理第二處理單元(206(2))上的所述第二階段(104(2))，以計算針對所述動態編程問題(102)的解，其中所述第二處理單元(206(2))使用所述所生成的輸入(118)來計算解；

將所述第一階段(104(1))與所述動態編程問題(102)的其它階段的第一集(202(3)，202(4))群集(508)在一起來形成第一群集，并將所述第二階段(104(2))與所述動態編程問題(102)的其它階段的第二集(202(5)，202(6))群集在一起來形成第二群集；以及

與所述第一處理單元(206(1))上的所述第一群集并行地處理所述第二處理單元(206(2))上的所述第二群集，以計算所述解。