[發(fā)明專利]一種適用于指導關聯(lián)算法并行化的分析方法、系統(tǒng)及裝置

有效

• 申請?zhí)枺?/td>: 201710899051.6
• 申請日: 2017-09-28
• 公開（公告）號: CN107818040B
• 公開（公告）日: 2021-09-21
• 發(fā)明（設計）人: 趙淦森;張海明;王欣明;莊序填;蔡斯凱;李振宇;李勝龍;林成創(chuàng);唐華;龐雄文
• 申請（專利權）人: 華南師范大學;廣東蔚海數(shù)問大數(shù)據(jù)科技有限公司
• 主分類號: G06F11/34
• 分類號: G06F11/34
• 代理公司: 廣州嘉權專利商標事務所有限公司 44205
• 代理人: 胡輝

本發(fā)明公開了一種適用于指導關聯(lián)算法并行化的分析方法、系統(tǒng)及裝置，方法包括：根據(jù)預設的SDGOT模型優(yōu)化原則，對關聯(lián)算法進行并行化優(yōu)化處理，得到并行計算模型；對優(yōu)化后的并行計算模型進行并行計算，并進行并行化迭代優(yōu)化，得到并行化算法模型；對并行化算法模型進行性能分析。本發(fā)明利用優(yōu)化設計的SDGOT模型提供的時間成本函數(shù)對并行架構內部開銷如數(shù)據(jù)加載、任務排隊和數(shù)據(jù)通信開銷進行形式化描述，彌補了以往分析并行算法時不能量化這幾類開銷的不足，解決了算法在并行計算過程中的并行架構內部開銷的量化問題。本發(fā)明可廣泛應用于并行分析技術中。

技術領域

本發(fā)明涉及并行分析技術領域，尤其涉及一種適用于指導關聯(lián)算法并行化的分析方法、系統(tǒng)及裝置。

背景技術

現(xiàn)有的DOT模型的不足之處在于：(1)假設資源是無限的，缺乏現(xiàn)實意義，沒有對運行時間成本等進行說明；(2)沒有對全局訪問數(shù)據(jù)做矩陣形式化描述；

而P-DOT模型的不足之處在于：(a)在時間成本描述上沒有考慮因處理器有限帶來的任務排隊開銷；(b)在迭代算法計算過程中的計算節(jié)點作為資源調整單位粒度過大，且不夠實時靈活。

現(xiàn)在的關聯(lián)算法并行化缺乏指導模型，且缺乏并行架構內部開銷的形式化描述和分析，即網(wǎng)絡通信開銷、數(shù)據(jù)及任務加載開銷等。

發(fā)明內容

為了解決上述技術問題，本發(fā)明的目的是提供一種描述更全面，適用于指導關聯(lián)算法并行化的分析方法、系統(tǒng)及裝置。

本發(fā)明所采取的技術方案是：

一種適用于指導關聯(lián)算法并行化的分析方法，包括以下步驟：

根據(jù)預設的SDGOT模型優(yōu)化原則，對關聯(lián)算法進行并行化優(yōu)化處理，得到并行計算模型；

對優(yōu)化后的并行計算模型進行并行計算，并進行并行化迭代優(yōu)化，得到并行化算法模型；

對并行化算法模型進行性能分析。

作為所述的一種適用于指導關聯(lián)算法并行化的分析方法的進一步改進，還包括以下步驟：

根據(jù)性能分析的結果，判斷其是否滿足預設的要求，若是，則不再進行優(yōu)化計算；反之，則再次對并行化算法模型進行迭代優(yōu)化。

作為所述的一種適用于指導關聯(lián)算法并行化的分析方法的進一步改進，所述的根據(jù)預設的SDGOT模型優(yōu)化原則，對關聯(lián)算法進行并行化優(yōu)化處理，這一步驟具體包括：

根據(jù)預設的SDGOT模型優(yōu)化原則的矩陣表達形式，判斷關聯(lián)算法中是否有不必要的數(shù)據(jù)掃描或重復操作，若是，則按照DOT模型所給策略進行合并；

判斷關聯(lián)算法中是否存在迭代場景，若是，則按照P-DOT模型所給的策略，對不同迭代階段的問題規(guī)模，動態(tài)調整分區(qū)數(shù)目；

判斷關聯(lián)算法中是否存在全局訪問數(shù)據(jù)，若是，則根據(jù)數(shù)據(jù)大小或計算復雜度對其進行分布式緩存或廣播操作，得到并行計算模型。

作為所述的一種適用于指導關聯(lián)算法并行化的分析方法的進一步改進，所述的對并行化算法模型進行性能分析，這一步驟具體包括：

根據(jù)并行化算法模型，計算總計算復雜度和總通信復雜度；

根據(jù)總計算復雜度和總通信復雜度，計算得到時間成本函數(shù)；

根據(jù)時間成本函數(shù)，計算模型效率、問題規(guī)模和額外開銷時間。

作為所述的一種適用于指導關聯(lián)算法并行化的分析方法的進一步改進，進行分布式緩存后得到的并行計算模型為：

進行廣播操作后得到的并行計算模型為：