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

有效

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

1.一種計算方法，包括：

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

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

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

2.根據權利要求1所述的方法，其中所述計算任務包括對一個設計進行驗證的任務。

3.根據權利要求1所述的方法，其中所述計算任務包括下列之一：信號處理任務、圖像處理任務、包處理任務和糾錯編碼(ECC)任務。

4.根據權利要求1所述的方法，其中所述多處理器設備包括圖形處理單元(GPU)。

5.根據權利要求1所述的方法，其中所述多處理器設備包括選自由下列組成的一組類型中的至少一個設備類型：數字信號處理器和多核中央處理單元(CPU)。

6.根據權利要求1所述的方法，其中編譯所述計算任務包括將每個執行序列中的PE分組成PE組(PEG)。

7.根據權利要求1所述的方法，其中所述多處理器設備根據內建調度策略調度所述PE以用于由所述多個處理器執行，且其中調用所述多處理器設備包括使得所述多處理器設備并行地執行所述第二數量的執行序列，如同布置在執行數據結構中，而與所述內建調度策略無關。

8.根據權利要求1-7中任一所述的方法，其中所述多處理器被分成組布置，每個組都被指派以執行提供給所述多處理器設備的一個或多個線程塊，且其中調用所述多處理器設備包括提供每個執行序列作為待要被所述組中的一個組內的處理器執行的一個相應的線程塊。

9.根據權利要求8所述的方法，其中所述每個組中的所述處理器訪問一個相應的共享存儲器，且其中編譯所述計算任務包括使得一個給定執行序列中的PE通過被指派以執行該給定執行序列的一組處理器的共享存儲器來交換數據。

10.根據權利要求1-7中任一所述的方法，其中將所述PE布置在所述調用數據結構中包括：最小化最長執行序列的長度同時不超過所述第一數量且不與所述執行依賴性相沖突。

11.根據權利要求1-7中任一所述的方法，其中一個給定執行依賴性規定了使驅PE將在受驅PE之前被執行，且其中將所述PE布置在所述調用數據結構中包括：在給定執行序列中將所述受驅PE放置在所述使驅PE之后。

12.根據權利要求1-7中任一所述的方法，其中一個給定執行依賴性規定了使驅PE將在受驅PE之前執行，且其中將所述PE布置在所述調用數據結構中包括：在第一執行序列中放置所述使驅PE，在不同于所述第一執行序列的第二執行序列中放置所述受驅PE，并且向所述第二執行序列中插入一個同步元，該同步元暫停所述第二執行序列的執行直到給定的所述使驅PE完全被執行為止。

13.根據權利要求1-7中任一所述的方法，其中編譯所述計算任務包括從所述計算任務提取多個非循環子圖，并且編譯所述多個非循環子圖以產生相應的多個調用數據結構。

14.根據權利要求1-7中任一所述的方法，其中將所述PE布置在所述調用數據結構中包括：定義一個順序，按此順序選擇所述PE以放置在所述執行序列中，且按此順序用所述PE填充所述執行序列。

15.根據權利要求14所述的方法，其中所述定義一個順序包括，為每個PE：

確定通向所述PE的一個最長的執行依賴性鏈的第一長度；

確定始自所述給定PE的一個最長的執行依賴性鏈的第二長度；

基于所述第一長度和所述第二長度，確定一個分配區間——其包括沿著所述執行序列的PE的可能的位置；以及

以所述分配區間的相應的長度的升序來排列所述PE。

16.根據權利要求15所述的方法，其中填充所述執行序列包括，將每個PE放置在所述執行序列中之一的相應的分配區間之內。