[發明專利]依賴性問題的有效率的并行計算

有效

• 申請號: 200980126852.2
• 申請日: 2009-06-30
• 公開（公告）號: CN102089752A
• 公開（公告）日: 2011-06-08
• 發明（設計）人: S·密茨拉希;U·泰;T·本-戴維
• 申請（專利權）人: 洛克泰克科技有限公司
• 主分類號: G06F15/16
• 分類號: G06F15/16
• 代理公司: 北京北翔知識產權代理有限公司 11285
• 代理人: 徐燕;楊勇

相關申請的交叉參引

本申請要求下列申請的權益：提交于2008年7月10日的美國臨時專利申請61/079,461；提交于2008年8月7日的美國臨時專利申請61/086,803；提交于2008年11月3日的美國臨時專利申請61/110,676；提交于2009年6月10日的美國臨時專利申請61/185,589；以及提交于2009年6月10日的美國臨時專利申請61/185,609。上述文獻的公開內容均通過參引方式納入本文。

技術領域

本發明主要涉及并行計算，且具體涉及用于在并行處理器上執行依賴性問題的方法和系統。

背景技術

并行處理技術廣泛地用于執行各種計算任務。在邏輯設計仿真領域，例如，Cadambi等人在2002年6月10日至14日路易斯安那州新奧爾良市舉辦的第三十九屆IEEE?ACM?Design?Automation?Conference(DAC?2002)的學報的570-575頁發表的“A?Fast，Inexpensive?and?Scalable?Hardware?Acceleration?Technique?for?Functional?Simulation”中描述了一種基于超長指令字(VLIW)處理器的仿真加速器，該文獻以參引方式納入本文。使用超長指令字處理器的邏輯仿真的多個方面也在下列文獻中進行了論述：美國專利7,444,276，以及美國專利申請公布2007/0219771，2007/0150702，2007/0129926，2007/0129924，2007/0074000，2007/0073999和2007/0073528，以上公開內容均以參引方式納入本文。

發明內容

本發明的一個實施方案提供了一種計算方法，包括：

接受計算任務的定義，該計算任務包括具有執行依賴性的多個原子處理元(PE)，每個執行依賴性規定了在執行一個相應的第二PE之前要執行一個相應的第一PE；

編譯所述計算任務以用于在多處理器設備上并發地執行，所述多處理器設備包括多個處理器，所述多個處理器通過在一個包括第二數量的執行序列的調用數據結構中不與執行依賴性沖突地布置所述PE而能夠同時地執行第一數量的PE，所述第二數量大于1且不超過所述第一數量；以及

調用所述多處理器設備以運行軟件代碼，所述軟件代碼響應于所述調用數據結構而并行地執行所述執行序列，以產生所述計算任務的結果。

在某些實施方案中，計算任務包括對一個設計進行驗證的任務。或者，所述計算任務可包括信號處理任務、圖像處理任務、包處理任務和/或糾錯編碼(ECC)任務。在所公開的一個實施方案中，多處理器設備包括圖形處理單元(GPU)。在另一個實施方案中，多處理器設備包括數字信號處理器和/或多核中央處理單元(CPU)。

在一個實施方案中，編譯所述計算任務包括將每個執行序列中的PE分組成PE組(PEG)。在另一個實施方案中，多處理器設備根據內建調度策略調度所述PE以用于由多個處理器執行，且其中調用所述多處理器設備包括使得所述多處理器設備并行地執行第二數量的執行序列，如同布置在執行數據結構中，而與所述內建調度策略無關。在另一個實施方案中，多處理器被分成組布置，每個組都被指派以執行提供給所述多處理器設備的一個或多個線程塊，且其中調用所述多處理器設備包括提供每個執行序列作為待要被所述組中的一個組內的處理器執行的一個相應的線程塊。在一個實施方案中，所述每個組中的所述處理器訪問一個相應的共享存儲器，且其中編譯所述計算任務包括使得一個給定執行序列中的PE通過被指派以執行該給定執行序列的一組處理器的共享存儲器來交換數據。

在另一個實施方案中，將PE布置在調用數據結構中包括：最小化最長執行序列的長度同時不超過所述第一數量且不與所述執行依賴性相沖突。在又一個實施方案中，一個給定執行依賴性規定了使驅PE將在受驅PE之前被執行，且其中將所述PE布置在所述調用數據結構中包括：在給定執行序列中將受驅PE放置在使驅PE之后。在另一個實施方案中，一個給定執行依賴性規定了使驅PE將在受驅PE之前執行，且其中將所述PE布置在所述調用數據結構中包括：在第一執行序列中放置使驅PE，在不同于所述第一執行序列的第二執行序列中放置受驅PE，并且向所述第二執行序列中插入一個同步元，所述同步元暫停所述第二執行序列的執行直到給定的所述使驅PE完全被執行為止。