[發(fā)明專利]一種用于并行地控制多個處理單元的設(shè)備、方法、系統(tǒng)

有效

• 申請?zhí)枺?/td>: 201480056629.6
• 申請日: 2014-10-13
• 公開（公告）號: CN105706057B
• 公開（公告）日: 2019-06-18
• 發(fā)明（設(shè)計）人: T·D·米可維茨;M·穆蘇瓦蒂;S·馬利基
• 申請（專利權(quán)）人: 微軟技術(shù)許可有限責(zé)任公司
• 主分類號: G06F9/50
• 分類號: G06F9/50;G06Q10/04;G06F17/11;H03M13/00
• 代理公司: 上海專利商標(biāo)事務(wù)所有限公司 31100
• 代理人: 胡利鳴

本文中描述的技術(shù)和/或系統(tǒng)通過以下來實現(xiàn)跨各階段和/或各群集的動態(tài)編程問題的并行處理：打破各階段和/或各群集之間的依賴性。例如，技術(shù)和/或系統(tǒng)可標(biāo)識動態(tài)編程問題的子問題之間的依賴性并將子問題分組到各階段中。各技術(shù)和/或系統(tǒng)還可將各階段分組到群集中(例如，要并行地處理的至少兩個群集)。由此，各技術(shù)和/或系統(tǒng)生成要使用的一個或多個解而非實際解，使得動態(tài)編程問題可跨各階段和/或各群集被并行地處理。

技術(shù)領(lǐng)域

本公開涉及跨各階段和/或各群集的動態(tài)編程問題的并行處理。

背景技術(shù)

動態(tài)編程算法被用于解決真實世界應(yīng)用中的各種問題。例如，動態(tài)編程算法可被用在文本串匹配、基因組學(xué)、基因定序、圖像處理、信號處理、語音識別、經(jīng)濟(jì)學(xué)和金融中。動態(tài)編程問題可包括多個子問題并且該動態(tài)編程問題的最優(yōu)解可從由針對各個子問題的最優(yōu)解構(gòu)造而成。傳統(tǒng)地，對動態(tài)編程問題的并行處理受到子問題之間依賴性的限制。例如，如果后續(xù)子問題依賴于前一子問題中計算出的解，則設(shè)備不能并行地處理該兩個子問題。相反，計算后續(xù)子問題的解被延遲，直到對前一子問題的解被計算出并被傳遞到后續(xù)子問題。

發(fā)明內(nèi)容

本文中描述的各技術(shù)和/或系統(tǒng)通過以下來實現(xiàn)跨各階段和/或各群集的對動態(tài)編程問題的并行處理：打破各階段和/或各群集之間的依賴性。例如，各技術(shù)和/或系統(tǒng)可標(biāo)識動態(tài)編程問題的子問題之間的依賴性并將子問題分組到各階段中。各技術(shù)和/或系統(tǒng)還可確定要被并行處理的階段分組(例如，一階段分組也可被稱為群集)。由此，各技術(shù)和/或系統(tǒng)生成要使用的一個或多個解而非實際解，使得動態(tài)編程問題可跨各階段和/或各群集被并行地處理。

附圖說明

參考附圖來描述具體實施方式。在附圖中，附圖標(biāo)記最左邊的數(shù)字標(biāo)識該附圖標(biāo)記首次出現(xiàn)的附圖。在不同附圖中使用相同的附圖標(biāo)記指示相似或相同的項。

圖1示出根據(jù)各實施例的具有包括多個階段的子問題的動態(tài)編程問題的示例圖。

圖2示出根據(jù)各實施例的具有可被并行處理的階段分組的動態(tài)編程問題的示例圖。

圖3示出根據(jù)各實施例的示例動態(tài)編程算法的各階段。

圖4示出根據(jù)各實施例的描述被配置成實現(xiàn)跨各階段的并行動態(tài)編程的設(shè)備的組件的示例環(huán)境。

圖5示出根據(jù)各實施例的跨各階段和/或各群集來并行處理動態(tài)編程問題的示例過程。

圖6示出根據(jù)各實施例的將最長公共子序列(LCS)問題的子問題分組成各階段中的示例圖。

具體實施方式

本文中描述的各技術(shù)和/或系統(tǒng)實現(xiàn)對動態(tài)編程問題跨各階段的并行處理。響應(yīng)于接收或標(biāo)識供處理(例如，要被求解)的動態(tài)編程問題，各技術(shù)和/或系統(tǒng)確定該動態(tài)編程問題的多個階段。每個階段包括一個或多個子問題并且每個階段由至少一個依賴性分隔，如本文中進(jìn)一步討論的。例如，對后續(xù)階段的處理可依賴于在前一階段的處理期間計算或運算出的至少一個解(例如，值)。因此，如本文中討論的，兩個階段之間的依賴性可以是從一個階段(例如，前一階段)提供到下一階段(例如，后續(xù)階段)的實際計算的解，使得下一階段中的子問題可使用實際計算的解來計算或運算另一解。例如，來自前一階段的實際計算的解可以是一值，后續(xù)階段中的子問題在一等式中使用該值來計算另一解。

本文中討論的各技術(shù)和/或系統(tǒng)能夠通過生成解(例如，任意生成的解，諸如隨機(jī)生成的值)來實現(xiàn)跨各階段的并行動態(tài)編程并通過使用所生成的解而非在前一階段中產(chǎn)生的實際計算的解來發(fā)起對一階段(例如，后續(xù)階段)的并行處理。換言之，各技術(shù)和/或系統(tǒng)使用所生成的解來替代仍待計算的實際解，使得對后續(xù)階段的處理可被發(fā)起，而不必等待前一階段計算實際計算的解并且不必等待前一階段將實際計算的解傳遞到后續(xù)階段。因此，各技術(shù)和/或系統(tǒng)能夠消除或打破階段之間的依賴性并通過使用所生成的解而非實際計算的解來實現(xiàn)跨各階段的對動態(tài)編程問題的并行處理。