[發明專利]用于實現代碼劃分和在異構處理器內核上執行的高效有向非循環圖模式匹配

有效

• 申請號: 201480045480.1
• 申請日: 2014-08-11
• 公開（公告）號: CN105474172B
• 公開（公告）日: 2018-11-09
• 發明（設計）人: D·杜拉蒂;M·金;C·維克
• 申請（專利權）人: 高通股份有限公司
• 主分類號: G06F8/41
• 分類號: G06F8/41
• 代理公司: 永新專利商標代理有限公司 72002
• 代理人: 張揚;王英

用于自動地確定如何對應用程序進行劃分和卸載，用于由移動設備內的通用應用處理器和輔助處理器(例如，DSP、GPU等等)執行的方法、設備和系統。移動設備可以基于有向非循環圖(DAG)的模式匹配來確定應用代碼中最適合于在輔助處理器上執行的部分。特別地，移動設備可以識別代碼中的(特別是代碼的數據流程圖中的)一種或多種模式，將每一種識別的代碼模式與已知當在輔助處理器(例如，DSP)上執行時具有某種利益的預定義的圖形模式進行比較。移動設備可以確定在輔助處理器上執行代碼的部分的開銷和/或利益，并且可以對具有與輔助處理器有關的低開銷和/或高利益的部分進行卸載。

技術領域

概括地說，本公開內容涉及計算設備，并且更具體地，涉及用于實現代碼劃分和在異構處理器內核上執行的高效有向非循環圖模式匹配。

背景技術

移動電子設備(例如，蜂窩電話、手表、頭戴式耳機、遠程控制等等)與以往任何時候相比變得更加復雜，并且現在通常包括多個處理器、片上系統(SoC)、以及允許移動設備用戶在其移動設備上執行復雜的和功率密集的軟件應用(例如，視頻流、視頻處理等等)的其它資源。隨著復雜度和功耗的增加，更好地利用移動設備的資源和能力的新的和改進的處理技術正在開始涌現。

這些新興的技術包括能夠對被設計用于在通用應用處理器上執行的代碼進行編譯，使得該代碼適合于在諸如數字信號處理器(或DSP)之類的輔助處理器上執行的系統。特別地，應用程序可以被劃分成單元或塊，并且可以基于所識別的不同的處理部件(例如，DSP、圖形處理單元或GPU等等)的效率/能力來將單元/塊分布到該不同的處理部件。這使得主或中央處理單元(CPU)或應用處理器將其操作中的一些操作卸載到輔助處理器，以節省功率和/或改善性能。

但是，確定應用程序如何被劃分以及哪些部分最適合于在輔助處理器上執行，經常是困難的設計任務。也就是說，只要存在用于識別并且將給定的代碼段劃分成非常適合于在不同類型的內核或處理單元中執行的部件的有效方式，將操作卸載到輔助處理器就可以改善移動設備的性能和功耗特性。

現有的技術可以利用不同的技術來識別和/或處理代碼。一些技術可以利用自動代碼劃分，并且可以通過程序依賴圖來表示應用代碼，用于使用固有的并行性和已知的通信開銷來對代碼進行劃分。這些技術沒有利用可能已知對特定的處理單元(諸如數字信號處理器(DSP))有益的預定義的模式。其它技術可以檢測代碼(或二進制)內的慣用語法(idiom)(或者已知的/預定義的指令集)，并且利用硬件輔助指令(即，復雜指令集計算或“CISC”指令)來取代慣用語法。這些技術通常只可以處理有限的粒度(大部分是直線型的指令)和簡單的模式，諸如精確的模式或者有限的自由度。另外，存在用于發現重復代碼和使用高級源代碼來檢測克隆的某些技術。此外，圖模式匹配已經被用在數據庫系統中。

存在使用指令選擇算法的其它技術，所述指令選擇算法利用樹型模式匹配來調整代碼以包括低開銷指令。特別地，自底向上的重寫系統(或BURS)算法可以被用來通過迭代地匹配與輸入代碼(例如，應用、例程等等)有關的輸入樹內的各個子樹以便發現最佳開銷指令集(即，覆蓋整棵樹并且還提供最低開銷/最高利益的指令的組合)，來確定針對輸入代碼的最佳指令集。基于模式匹配，可以生成用于在計算設備上執行的新的、改進的指令集。

但是，當對使用基于圖形表示的復雜的代碼的部分進行卸載時，已知的技術可能是不適合的。換言之，現有的技術可能不使用代碼的有向非循環表示進行匹配來識別用于異構多核或分布式系統的最佳卸載方式的編譯器后端解決方案。

發明內容