基於dag節點最優路徑的多模型並行調度方法及裝置製造方法

2023-05-27 17:04:16 1

基於dag節點最優路徑的多模型並行調度方法及裝置製造方法
【專利摘要】本發明提供一種基於DAG節點最優路徑的多模型並行調度方法及裝置，其中的方法包括：根據各模型之間的關係創建基於各模型關係的DAG圖；根據基於路徑探測的最優路徑分析算法將DAG圖拆分為調度序列集合；其中，在調度序列集合中包括多個並行調度的序列；將調度序列集合中的所有並行調度的序列存儲為第一鄰接矩陣；將第一鄰接矩陣映射成鄰接表；根據鄰接表並行運行調度序列集合中的各個序列。利用本發明提供的基於DAG節點最優路徑的多模型並行調度方法及裝置，能夠解決現有拆分方法中複雜度高、運行時間長的問題；還能夠充分利用系統資源，有效縮短多模型的調度運行時間。
【專利說明】基於DAG節點最優路徑的多模型並行調度方法及裝置

【技術領域】
[0001] 本發明涉及模型調度【技術領域】，更為具體地，涉及一種基於DAG節點最優路徑的 多模型並行調度方法及裝置。

【背景技術】
[0002] 複雜產品的設計和運行過程中，往往涉及不同種類、不同複雜度、相互關聯的多種 模型，多模型的調度方法直接影響產品運行的可行性和時效性。多模型調度方法主要是利 用DAG圖（Directed Acyclic Graph,有向無環圖）描述模型間的前驅後繼關係，在DAG圖 中，DAG的節點代表模型，DAG的邊代表模型間的依賴關係。
[0003] 圖1為模型系統的DAG圖，由圖1可以看出，DAG圖描述了多個模型及其相互間的 依賴關係。其中，圓形左側數據代表節點序號，1?10代表參與調度的10個模型，圓形右側 的數據代表模型執行時間，有向線段代表模型間的依賴關係，後繼節點必須在其前驅節點 執打完成後才可以執打。
[0004] 在通常的多模型調度方法中，模型是串行執行的，調度周期長，不能充分發揮多核 處理器和分布式環境下的並行優勢，浪費系統資源。
[0005] 為了實現多模型的並行調度，一般將DAG圖拆分為可並行調度的序列。現有的被 廣泛使用的DAG圖拆分方法是In-tree方法，即根據DAG圖中各個節點的出度和入度，將 DAG圖轉換成In-tree結構，然後分析In-tree結構中包含的所有路徑，找到可並行調度的 序列。但是，該In-tree方法需要對所有節點、In-tree所有路徑進行分析，計算複雜度高、 運行時間長，嚴重影響系統的運行效率。
[0006] 因此，需要一種全新的基於DAG節點最優路徑的多模型並行調度方法，以充分發 揮多核處理器和分布式環境下的並行優勢，避免浪費系統資源，提高系統的運行效率。


【發明內容】

[0007] 鑑於上述問題，本發明的目的是提供一種基於DAG節點最優路徑的多模型並行調 度方法及裝置，以解決現有的多模型並行調度方法中，調度周期長，不能充分發揮多核處理 器和分布式環境下的並行優勢，浪費系統資源的問題。
[0008] 本發明提供的基於DAG節點最優路徑的多模型並行調度方法，包括：
[0009] 根據各|吳型之間的關係創建基於各|吳型關係的DAG圖；
[0010] 根據基於路徑探測的最優路徑分析算法將DAG圖拆分為調度序列集合；其中，在 調度序列集合中包括多個並行調度的序列；
[0011] 將調度序列集合中的所有並行調度的序列存儲為第一鄰接矩陣；
[0012] 將第一鄰接矩陣映射成鄰接表；
[0013] 根據鄰接表並行運行調度序列集合中的各個序列。
[0014] 本發明提供的基於DAG節點最優路徑的多模型並行調度裝置，包括：
[0015] DAG圖創建單元，用於根據各模型之間的關係創建基於各模型關係的DAG圖；
[0016] DAG圖拆分單元，用於根據基於路徑探測的最優路徑分析算法將DAG圖拆分為調 度序列集合；其中，在調度序列集合中包括多個並行調度的序列；
[0017] 序列存儲單元，用於將調度序列集合中的所有並行調度的序列存儲為第一鄰接矩 陣；
[0018] 矩陣映射單元，用於將第一鄰接矩陣映射成鄰接表；
[0019] 序列運行單元，用於根據鄰接表並行運行調度序列集合中的各個序列。
[0020] 利用上述根據本發明提供的基於DAG節點最優路徑的多模型並行調度方法及裝 置，能夠將DAG圖拆分可並行調度的序列，解決現有拆分方法中複雜度高、運行時間長的問 題；同時針對現有最優路徑分析方法的不足，提出一種基於路徑探測的最優路徑分析算法； 另外，根據子路徑判斷的實際需求，提出了一種基於統一存儲的路徑子路徑判斷方法，結合 上述兩個方面能夠充分利用系統資源，並且有效縮短多模型的調度運行時間。
[0021] 為了實現上述以及相關目的，本發明的一個或多個方面包括後面將詳細說明並在 權利要求中特別指出的特徵。下面的說明以及附圖詳細說明了本發明的某些示例性方面。 然而，這些方面指示的僅僅是可使用本發明的原理的各種方式中的一些方式。此外，本發明 旨在包括所有這些方面以及它們的等同物。

【專利附圖】

【附圖說明】
[0022] 通過參考以下結合附圖的說明及權利要求書的內容，並且隨著對本發明的更全面 理解，本發明的其它目的及結果將更加明白及易於理解。在附圖中：
[0023] 圖1為模型系統的DAG圖；
[0024] 圖2為根據本發明實施例的基於DAG節點最優路徑的多模型並行調度方法的流程 示意圖；
[0025] 圖3為根據本發明實施例的基於節點最優路徑的DAG圖拆分方法的流程示意圖；
[0026] 圖4為根據本發明實施例的基於路徑探測的最優路徑分析算法的流程示意圖；
[0027] 圖5為根據本發明實施例的子路徑判斷方法流程示意圖；
[0028] 圖6為根據本發明實施例的基於DAG節點最短路徑並行調度結果圖；
[0029] 圖7為根據本發明實施例的基於DAG節點最優路徑的多模型並行調度裝置的結構 示意圖；
[0030] 圖8為根據本發明實施例的基於DAG節點最優路徑的多模型並行調度裝置的一個

【具體實施方式】的結構示意圖。
[0031] 在所有附圖中相同的標號指示相似或相應的特徵或功能。

【具體實施方式】
[0032] 在下面的描述中，出於說明的目的，為了提供對一個或多個實施例的全面理解，闡 述了許多具體細節。然而，很明顯，也可以在沒有這些具體細節的情況下實現這些實施例。 在其它例子中，為了便於描述一個或多個實施例，公知的結構和設備以方框圖的形式示出。
[0033] 針對現有的多模型調度方法中DAG圖拆分方法複雜度高、運行時間長，系統運行 效率低的問題，本發明提出一種基於DAG節點最優路徑的多模型並行調度解決方案，採用 基於路徑探測的最優路徑分析算法將DAG圖拆分可並行調度的序列，再將可並行調度的序 列存儲為鄰接矩陣的形式，對鄰接矩陣進行映射轉化成鄰接表，最後將可並行調度的序列 以鄰接表的形式並行運行各個序列。
[0034] 需要說明的是，上述節點的最優路徑指的是起始節點到該節點的最短路徑。
[0035] 以下將結合附圖對本發明的具體實施例進行詳細描述。
[0036] 圖2示出了根據本發明實施例的基於DAG節點最優路徑的多模型並行調度方法的 流程。
[0037] 如圖2所示，本發明實施例提供的基於DAG節點最優路徑的多模型並行調度方法， 包括：
[0038] 步驟S201 :根據各模型之間的關係創建基於各模型關係的DAG圖。
[0039] 其中，DAG圖是有向無環圖，用來描述各個模型間的前驅後繼關係，DAG圖中的第 一個節點為起始節點，最後一個節點為終止節點，起始節點和終止節點間的節點為中間節 點，以圖1為例，如果當前節點為節點2,則節點1為節點2的前驅節點，節點3、節點4、節點 5、節點6為節點2的後繼節點，其它節點的前驅節點和後繼節點同理。
[0040] 步驟S202 :根據基於路徑探測的最優路徑分析算法將DAG圖拆分為調度序列集 合；其中，在調度序列集合中包括多個並行調度的序列。
[0041] 根據基於路徑探測的最優路徑分析算法將DAG圖拆分為調度序列集合具體的過 程為：採用最優路徑分析算法按照從終止節點到起始節點的順序查找每個中間節點的最優 路徑，並將每個中間節點的最優路徑加入調度序列集合；每個中間節點的最優路徑分別對 應一個序列，多個並行調度的序列至少包括兩個序列。
[0042] 其中，在採用基於路徑探測的最優路徑分析算法查找每個中間節點的最優路徑的 過程中，對起始節點與每個中間節點間的路徑進行雙向探測，過濾掉起始節點與每個中間 節點之間不存在通路的節點，並保留起始節點和每個中間節點間之間最短的路徑作為每個 中間節點的最優路徑加入到調度序列集合中。
[0043] 作為一個【具體實施方式】，在將每個中間節點的最優路徑加入調度序列集合之前， 判斷每個中間節點的最優路徑是否為調度序列集合中最優路徑的子路徑；如果是，此中間 節點的最優路徑不加入所述調度序列集合；如果否，將此中間節點的最優路徑加入所述調 度序列集合。
[0044] 需要說明的是，調度序列集合為一個大的空間，用來存儲可並行調度的序列，因 此，在拆分DAG圖的過程中，將DAG圖拆分為一個調度序列集合，下文中提到的其它集合也 為一個。
[0045] 步驟S203 :將調度序列集合中的所有並行調度的序列存儲為第一鄰接矩陣。
[0046] 由於多個並行調度的序列分別對應一個中間節點的最優路徑，將多個並行調度的 序列存儲為第一鄰接矩陣就是將多個中間節點的最優路徑以鄰接矩陣的形式存儲。
[0047] 步驟S204 :將第一鄰接矩陣映射成鄰接表。
[0048] 最終以鄰接表的形式存儲多個中間節點的最優路徑，有利於系統的運行。
[0049] 步驟S205 :根據鄰接表並行運行調度序列集合中的各個序列。
[0050] 實際上運行的是與各個序列相對應的最優路徑，也就是可並行調度的最優路徑。
[0051] 上述步驟為實現本發明實施例提供的基於DAG節點最優路徑的多模型並行調度 方法所採取的數據處理步驟，其中，本發明實施的主要細節在於DAG圖的拆分方法和拆分 DAG圖用到的最優路徑分析算法，以及在拆分過程中涉及到的子路徑判斷方法，下面分別對 這三個方面進行詳細地說明。
[0052] 一、DAG圖的拆分方法
[0053] 為了解決現有的DAG圖拆分方法中計算複雜度高、運行時間長，系統運行效率低 的問題，本發明實施例採用最優路徑分析算法將DAG圖拆分為調度序列集合，也就是將DAG 圖拆分為多個可並行調度的序列，每個序列為一個中間節點的最優路徑，最後執行的就是 可並行調度的多個中間節點的最優路徑。
[0054] 圖3示出了根據本發明實施例的基於節點最優路徑的DAG圖拆分方法的流程，如 圖3所示，本發明實施例提供的基於節點最優路徑的DAG圖拆分方法包括：
[0055] 步驟S301 :初始化當前節點集合、已完成節點集合與調度序列集合。
[0056] 初始化當前節點集合的目的是為了在內存中創建一個空間用來存儲將要進行最 優路徑計算的節點，初始化已完成節點集合的目的同樣是為了在內存中創建一個空間，用 來存儲經過計算的最優路徑的節點；而初始化調度序列集合的目的則是為了在內存中創建 一個存儲節點的最優路徑的空間。
[0057] 步驟S302 :輸入DAG圖。
[0058] 在創建DAG圖後，將DAG圖輸入到內存中，用於對DAG圖進彳丁拆分DAG圖內存中可 以用多種形式存儲，例如列表或矩陣等等。
[0059] 步驟S303 :將終止節點加入當前節點集合。
[0060] 在本發明的實施例中，採用從終止節點向起始節點的順序計算每個中間節點的最 優路徑，由於在計算每個中間節點的最優路徑的過程中，需要對每個中間節點的最優路徑 進行是否存在子路徑的判斷，也就是說一個中間節點的最優路徑是否為其後繼節點的最優 路徑的子路徑，如果是，該中間節點的最優路徑是不需要加入調度序列集合的，此時只需要 將該中間節點的後繼節點的最優路徑加入調度序列集合即可，由於按照從起始節點到終止 節點的順序不能判斷出一個中間節點的最優路徑是否為其後繼節點的最優路徑的子路徑， 此時需要計算所有到達該後繼節點的路徑，比較所有到達該後繼節點的路徑後才能獲得該 後繼節點的最優路徑，這樣會增大計算量和複雜度，而採用從終止節點到起始節點的順序 計算每個中間節點的最優路徑時，在計算出一個中間節點的後繼節點的最優路徑後自然而 然的能卻確定出該中間節點的最優路徑是否為其後繼節點的最優路徑的子路徑，能夠避免 不必要的計算，降低計算量和複雜度。
[0061] 步驟S304 :採用基於路徑探測的最優路徑分析算法查找當前節點集合中節點的 所有前驅節點的最優路徑。
[0062] 最優路徑分析算法將在下文做詳細說明，在計算節點的所有前驅節點的最優路徑 的過程中，是依次對每個前驅節點計算最優路徑，其計算的順序可以是隨機的，也可以是根 據每個模型的編號按照一定的順序進行計算。
[0063] 從此步驟S304到步驟S307為一個while循環，滿足該循環的條件為當前節點集 合中節點有前驅節點，如果當前節點集合匯總節點沒有前驅節點，則跳出該循環。
[0064] 步驟S305 :判斷從步驟S304中計算出的最優路徑是否為調度序列集合中的某個 節點的最優路徑的子路徑，如果是，執行步驟S307 ;如果否，執行步驟S306。
[0065] 判斷子路徑的方法將在下文做詳細說明。
[0066] 步驟S306 :將從步驟S304中計算出的最優路徑加入調度序列集合。
[0067] 其中，每一條最優路徑相當於一個可並行調度的序列。
[0068] 步驟S307 :將當前節點集合中的節點移至已完成節點集合，並將節點的前驅節點 加入當前節點集合。
[0069] 步驟S308 :獲得調度序列集合。
[0070] 調度序列集合中包括多個可並行調度的最優路徑。
[0071] 為了更清楚的說明上述流程，結合圖1，首先將終止節點10加入當前節點集合，查 找終止節點10的所有前驅節點的最優路徑（也就是節點7、8、9的最優路徑），將終止節點 10加入已完成節點集合，並將終止節點10的前驅節點7、8、9加入當前節點集合，再查找節 點7、8、9的前驅節點的最優路徑（也就是節點3、4、5、6的最優路徑）一直循環到起始節點 1位置，由於節點1沒有前驅節點，跳出該循環，最後得到一個調度序列集合。
[0072] 另外，由於在查找到所有中間節點的最優路徑後自然而然的能確定出終止節點的 最優路徑，因此本發明實施例中沒有查找終止節點的最優路徑。
[0073] 二、最優路徑分析算法
[0074] Di jkstra算法是目如已知理論上最完善的算法，也是多數系統解決最短路徑問題 採用的理論基礎。然而，在實際應用中，使用Di jkstra算法求解最短路徑將會耗費大量的 存儲空間和計算時間，因此必須根據具體的應用對其進行優化。
[0075] 綜合分析種種對Dijkstra算法的優化方法，可將其歸為兩大類：對存儲空間的優 化和對計算時間的優化。在存儲空間方面出現了鍊表數組、最大鄰接點數等優化的存儲結 構。在計算時間方面主要有限制搜索區域、啟發式搜索、雙向搜索、分層搜索等方法。然而 這些方法的核心思想仍然是窮舉一個問題解空間的部分或所有的可能情況，從而求出問題 的解的一種方法。
[0076] 為了解決上述問題，本發明提供一種基於路徑探測的最優路徑分析算法，用探測 程序對起點和終點間的節點和路段進行雙向探測，過濾掉與起始節點和終止節點間不存在 通路的節點，在探測的過程中實時更新最優路徑集合，最終輸出最優路徑，該算法通過探測 捨去了不必要的計算，提高了算法的運行效率。
[0077] 圖4示出了根據本發明實施例的基於路徑探測的最優路徑分析算法的流程，如圖 4所示，本發明實施例提供的基於路徑探測的最優路徑分析算法包括 ：
[0078] 步驟S401 :初始化起始節點集合、終止節點集合與最優路徑集合。
[0079] 目的是分別建立三個空間，分別用於存儲起始節點、終止節點與最優路徑。
[0080] 步驟S402 :輸入DAG圖。
[0081] 在創建完DAG圖後，將DAG圖輸入到內存。
[0082] 步驟S403 :將起始節點加入起始節點集合、終止節點加入終止節點集合。
[0083] 步驟S404 :探測起始節點集合中節點的後繼節點與終止節點集合中節點的前驅 節點間的路徑是否存在通路，如果存在，執行步驟S405 ;如果不存在，執行步驟S406。
[0084] 其中，如果起始節點集合中節點包括多個後繼節點，終止節點集合的中節點包括 多個前驅節點，則將每個前驅節點分別作為終止節點，依次探測與起始節點的後續節點間 是否存在通路。
[0085] 步驟S405 :保留距離最短的路徑，更新最優路徑集合，並將該前驅節點加入終止 節點集合，後續節點加入起始節點集合。
[0086] 其中，保留距離最短的路徑為每個終止節點與起始節點的後續節點間最短的路 徑，將其作為每個終止節點的最優路徑加入最優路徑集合。
[0087] 步驟S406 :過濾掉與起點節點和終止節點間不存在通路的節點。
[0088] 步驟S407 :判斷起始節點是否為終止節點，如果是，執行步驟S408 ;如果否，返回 步驟S404。
[0089] 如果起始節點和終止節點為同一節點，也就是一個節點既是後繼節點又是前驅節 點，則認為起始節點為終止節點，結合圖1，節點3既是節點2的後繼節點又是節點8的前驅 節點，在探測節點3的最優路徑時，將節點3作為新的起始節點，同時節點3又作為新的終 止節點，所以起始節點為終止節點。
[0090] 還有另外一種情況，如果圖1中的節點10不是終止節點，節點10還有一個後續節 點，這種情況下，節點3是節點8的前驅節點，節點8是節點3的後繼節點，由於節點3和節 點8之間沒有節點，節點3和節點8之間的路徑距離是確定的，因此再將節點3作為起始節 點、節點8作為終止節點時可以認為起始節點3為終止節點8。
[0091] 步驟S408 :獲得最優路徑集合。
[0092] 獲得的最優路徑集合包括各個中間節點最優路徑。
[0093] 由步驟S401?步驟S408可以看出，在探測一個中間節點的最優路徑的過程中，會 探測到其所有前驅節點的最優路徑，這些前驅節點的最優路徑需要進行子路徑的判斷，如 果前驅節點的最優路徑不為調度序列集合中任一條最優路徑的子路徑，則將這些前驅節點 的最優路徑加入到調度序列集合中，從實質上來說，最優路徑集合相當於調度序列集合，每 一條最優路徑相當於可並行調度的序列，多條最優路徑加入到最優路徑集合就是多個可並 行調度的序列加入到調度序列集合。
[0094] 三、子路徑判斷方法
[0095] 在將每個中間節點的最優路徑加入到最優路徑集合（也就是調度序列集合）之 前，需要判斷是否為最優路徑集合中任一條最優路徑的子路徑，在判斷某一條最優路徑是 否為最優路徑集合中某一條最優路徑的子路徑的過程中，由於最優路徑集合中可能包含多 個最優路徑，未加入最優路徑集合的最優路徑需要與最優路徑集合中所有最優路徑進行對 比分析，效率較低。為了解決該問題，本發明實施例提出一種統一存儲的方式，將最優路徑 集合中的最優路徑存入鄰接矩陣，最優路徑中所有存在通路的兩節點存1，不存在通路的兩 個節點存0,同理，非最優路徑集合內的最優路徑存入另一鄰接矩陣。如果非最優路徑集合 內的最優路徑的鄰接矩陣是最優路徑集合中的鄰接矩陣的子矩陣，那麼該最優路徑是其中 某一條最優路徑的子路徑。
[0096] 圖5示出了根據本發明實施例的子路徑判斷方法流程，如圖5所示，本發明實施例 提供的子路徑判斷方法包括：
[0097] 步驟S501 :輸入最優路徑集合與非最優路徑集合內的最優路徑。
[0098] 在將某個中間節點的最優路徑加入最優路徑集合之前，判斷此中間節點的最優路 徑是否為最優路徑集合中某個最優路徑的子路徑，此時需要將最優路徑集合與該中間節點 的最優路徑輸入到內存中用於判斷。
[0099] 步驟S502 :對最優路徑集合進行統一存儲，存入第三鄰接矩陣，再將非最優路徑 集合內的最優路徑存入第二鄰接矩陣。
[0100] 再將最優路徑集合存入第三鄰接矩陣時，最優路徑中所有存在通路的兩節點存1， 不存在通路的兩個節點存0,非最優路徑集合內的最優路徑同理存入第二鄰接矩陣。
[0101] 步驟S503 :判斷第二鄰接矩陣是否為第三鄰接矩陣的子矩陣；如果是，執行步驟 S504 ;如果否，執行步驟S505。
[0102] 步驟S504 :非最優路徑集合內的最優路徑為最優路徑集合中某個最優路徑的子 路徑。
[0103] 步驟S505 :非最優路徑集合內的最優路徑不為最優路徑集合中某個最優路徑的 子路徑。
[0104] 在判斷出非最優路徑集合內的最優路徑不為最優路徑集合中某個最優路徑的子 路徑後，將非最優路徑集合內的最優路徑加入最優路徑集合也就是調度序列集合。
[0105] 上述方法和流程詳細說明了本發明實施例提供的基於DAG節點最優路徑的多模 型並行調度方法，以圖1為例，執行上述流程得到可並行執行的序列如表1所示： 「01061 表〗可並行調庠的序列

【權利要求】
1. 一種基於DAG節點最優路徑的多模型並行調度方法，包括： 根據各1?型之間的關係創建基於各1?型關係的DAG圖； 根據基於路徑探測的最優路徑分析算法將所述DAG圖拆分為調度序列集合；其中，在 所述調度序列集合中包括多個並行調度的序列； 將所述調度序列集合中的所有並行調度的序列存儲為第一鄰接矩陣； 將所述第一鄰接矩陣映射成鄰接表； 根據所述鄰接表並行運行所述調度序列集合中的各個序列。
2. 如權利要求1所述的基於DAG節點最優路徑的多模型並行調度方法，其中，所述DAG 圖包括起始節點、終止節點和至少兩個中間節點； 在根據基於路徑探測的最優路徑分析算法將所述DAG圖拆分為調度序列集合的過程 中，採用最優路徑分析算法按照從所述終止節點到所述起始節點的順序查找每個中間節點 的最優路徑，並將每個中間節點的最優路徑加入所述調度序列集合；其中，每個中間節點的 最優路徑分別對應一個序列。
3. 如權利要求2所述的基於DAG節點最優路徑的多模型並行調度方法，其中，在根據基 於路徑探測的最優路徑分析算法查找每個中間節點的最優路徑的過程中， 對所述起始節點與每個中間節點間的路徑進行雙向探測，過濾掉所述起始節點與每個 中間節點之間不存在通路的節點，並保留所述起始節點和每個中間節點間之間最短的路徑 作為每個中間節點的最優路徑加入所述調度序列集合。
4. 如權利要求3所述的基於DAG節點最優路徑的多模型並行調度方法，其中，在將每個 中間節點的最優路徑加入所述調度序列集合之前， 判斷每個中間節點的最優路徑是否為所述調度序列集合中最優路徑的子路徑；如果 是，此中間節點的最優路徑不加入所述調度序列集合；如果否，將此中間節點的最優路徑加 入所述調度序列集合。
5. 如權利要求4所述的基於DAG節點最優路徑的多模型並行調度方法，其中，在判斷每 個中間節點的最優路徑是否為所述調度序列集合中最優路徑的子路徑的過程中， 將每個中間節點的最優路徑分別存入第二鄰接矩陣，再將所述調度序列集合中的所有 最優路徑存入第三鄰接矩陣，判斷所述第二鄰接矩陣是否為所述第三鄰接矩陣的子矩陣； 如果是，存入所述第二鄰接矩陣中的中間節點的最優路徑為所述調度序列集合中最優路徑 的子路徑；如果否，存入所述第二鄰接矩陣中的中間節點的最優路徑不為所述調度序列集 合中最優路徑的子路徑。
6. -種基於DAG節點最優路徑的多模型並行調度裝置，包括： DAG圖創建單元，用於根據各模型之間的關係創建基於各模型關係的DAG圖； DAG圖拆分單元，用於根據基於路徑探測的最優路徑分析算法將所述DAG圖拆分為調 度序列集合；其中，在所述調度序列集合中包括多個並行調度的序列； 序列存儲單元，用於將調度序列集合中的所有並行調度的序列存儲為第一鄰接矩陣； 矩陣映射單元，用於將所述第一鄰接矩陣映射成鄰接表； 序列運行單元，用於根據所述鄰接表並行運行所述調度序列集合中的各個序列。
7. 如權利要求6所述的基於DAG節點最優路徑的多模型並行調度裝置，其中， 所述DAG圖包括起始節點、終止節點和至少兩個中間節點；以及 所述DAG圖拆分單元包括： 最優路徑查找模塊，用於採用基於路徑探測的最優路徑分析算法按照從所述終止節點 到所述起始節點的順序查找每個中間節點的最優路徑； 最優路徑加入模塊，用於將每個中間節點的最優路徑加入所述調度序列集合；其中，每 個中間節點的最優路徑分別對應一個序列。
8. 如權利要求7所述的基於DAG節點最優路徑的多模型並行調度裝置，其中，在根據基 於路徑探測的最優路徑分析算法查找每個中間節點的最優路徑的過程中， 所述最優路徑查找模塊對所述起始節點與每個中間節點間的路徑進行雙向探測，過濾 掉所述起始節點與每個中間節點之間不存在通路的節點，並保留所述起始節點和每個中間 節點間之間最短的路徑作為每個中間節點的最優路徑加入所述調度序列集合。
9. 如權利要求8所述的基於DAG節點最優路徑的多模型並行調度裝置，其中， 所述裝置進一步包括子路徑判斷單元，用於在將每個中間節點的最優路徑加入所述調 度序列集合之前，判斷每個中間節點的最優路徑是否為所述調度序列集合中最優路徑的子 路徑；如果是，此中間節點的最優路徑不加入所述調度序列集合；如果否，將此中間節點的 最優路徑加入所述調度序列集合。
10. 如權利要求9所述的基於DAG節點最優路徑的多模型並行調度裝置，其中，在所述 子路徑判斷單元包括： 第二鄰接矩陣存入模塊，用於將每個中間節點的最優路徑分別存入第二鄰接矩陣； 第三鄰接矩陣存入模塊，用於將所述調度序列集合中的所有最優路徑存入第三鄰接矩 陣； 子矩陣判斷模塊，用於判斷所述第二鄰接矩陣是否為所述第三鄰接矩陣的子矩陣；如 果是，所述子路徑判斷單元判斷存入所述第二鄰接矩陣中的中間節點的最優路徑為所述調 度序列集合中最優路徑的子路徑；如果否，所述子路徑判斷單判斷存入所述第二鄰接矩陣 中的中間節點的最優路徑不為所述調度序列集合中最優路徑的子路徑。
【文檔編號】G06F9/50GK104239137SQ201410415590
【公開日】2014年12月24日 申請日期:2014年8月21日 優先權日:2014年8月21日
【發明者】徐麗麗, 張騫, 趙廣斌, 張珠華 申請人:東軟集團股份有限公司