面向嵌入式異構多核上執行動態分配指令的方法

2023-10-11 15:52:04 1

專利名稱：面向嵌入式異構多核上執行動態分配指令的方法
技術領域：
本發明涉及的是一種計算機技術領域的方法，具體是一種面向嵌入式異構多核上 執行動態分配指令的方法。
背景技術：
近幾年來，由於人們對計算能力的要求越來越高，CPU的處理能力也需要進一步提 高。最初，提高CPU的性能主要是通過提高主頻和前端總線頻率以及擴大緩存來實現。但 是，提高主頻對CPU功耗及散熱的問題提出了很大的挑戰，單純擴大緩存也需要增加成本， 單核心處理器的發展已經達到一個極限。為了進一步提高CPU的處理能力，多核處理器技 術逐漸進入市場。從2006年以來，Intel和AMD等公司分別發布了雙核、四核等多核處理 器。隨著多核處理器全線進入市場，計算機多核時代已經來臨。在單晶片內集成多個微處理器核，可以完全並行地執行程序代碼，在不提升工作 頻率的情況下，不但可以提高處理性能，而且很好地解決了功耗的問題，成為未來處理器的 發展方向。但是，單純增加微處理器內核的數量並不能理想地提高CPU的處理能力，在增強 處理器的並行處理能力方面，最重要的還是程序本身的並行化，但大多數程序的串行執行 部分仍會阻礙處理性能的提升。一般認為，在這種同構多核的處理器架構中，4-8個內核可 能是多核處理器能夠獲得較好性能提升效果的極限。為了進一步提高CPU的處理能力，出現了一種異構處理器架構，即在一個晶片內 集成多個異構的處理器核。在這種架構中，不同的處理器核對於特定應用能夠發揮更高的 處理效能(考慮性能、功耗、工藝及成本等因素)，比如有的核心擅長處理浮點運算，而有的 內核擅長信號處理等工作。充分利用異構多核的功能差異性，能夠更加充分地滿足不同領 域不同應用的需求。由IBM、索尼和東芝等聯手打造的晶片Cell正是這種異構處理器的 典範，它是一枚擁有9個硬體核心的多核處理器。在Cell晶片中，只有一個是IBM標準的 Power處理器，其餘8個內核都是為處理圖像而專門設計的、用於浮點運算的協處理器。其 中，主處理器的主要職能就是負責任務的分配，實際的浮點運算工作都是由協處理器來完 成。由於Cell中的協處理器只負責浮點運算任務，所需的運算規則非常簡單，對應的電路 邏輯同樣如此，只要CPU運行頻率足夠高，Cell就能夠獲得驚人的浮點效能。目前，異構多核處理器主要有三類，根據指令集的差異，有指令集完全相同但硬體 配置不同、指令集完全不同以及部分指令集核心相同等種類。其中對於有通用指令集核心 的異構多核處理器，其各自不同的部分設計為擴展的指令集，適合於處理不同需求的應用。 為了跟上異構多核處理器的發展步伐，在面向異構多核處理器時需要設計更先進的編譯系 統及運行時處理方法，包括程序設計語言、編譯模型及運行庫的設計等。在這方面，主要的 工作集中在任務調度策略和線程級並行的優化上。現有的任務的靜態調度主要有兩種方法一種是在編譯期將不同的代碼編譯成適 合不同的處理核執行的二進位代碼；另一種是在運行時連結不同處理核的運行庫。這兩種 方法都是靜態地將任務指派到特定的處理核上執行，因此要求程序在編寫時就考慮不同核的異構性，編程人員必須對異構核有充分地了解。另外該方法沒有考慮到異構多核的負載 均衡和功耗等問題，任務的不當分配可能會使程序的執行時間增加，而負載均衡等信息需 要在運行時才能知道。從現有技術文獻的檢索發現，為了克服這種編程的複雜度和運行時問題，出現了 線程級動態調度方法，現有的這種方法對任務進行不同粒度的線程劃分，使得不同的線程 能夠並行地執行在不同的核心上，進而提高了執行效率。但是該方法需要考慮數據依賴性， 實際上很難將串行執行的程序劃分成並行執行的多線程任務，另外由於不同線程的數據依 賴性，還需要考慮數據同步及緩存一致性等問題，可能會使線程調度變得更加複雜，導致程 序的性能進一步下降。

發明內容
本發明的目的在於克服現有技術中的上述不足，提供一種面向嵌入式異構多核上 執行動態分配指令的方法。本發明根據系統多核的處理能力及負載情況等因素動態地分配 指令到各異構多核上執行，從而彌補了靜態調度的不能動態分配資源的不足，也降低了動 態線程劃分的複雜性，從而進一步提高了程序在異構多核上的執行效率。本發明是通過以下技術方案實現的，本發明包括以下步驟第一步，在載入二進位代碼程序的過程中，對二進位代碼程序進行劃分處理，得到 若干基本塊。所述的劃分處理，是將第i條入口指令與第i+Ι條跳轉指令間的程序作為第i+1 個基本塊，其中0 ^ i，入口指令是跳轉指令轉到的指令或緊跟跳轉指令後的指令。第二步，分別對每個基本塊進行選擇處理，得到執行每個基本塊的目標處理核。所述的選擇處理，包括以下步驟2. 1)得到與第i個基本塊中的第j條指令A具有同等功能的指令Α* ；2. 2)得到所有處理指令A或指令A*的處理核A，進而得到同時處理第i個基本塊 中每條指令的處理核集合I ；2. 3)根據ρ = 1/N，得到處理核集合I中每個處理核執行每條指令的執行性能，並 將每個處理核執行每條指令的執行性能相加，得到該集合中每個處理核執行第i個基本塊 的平均性能，其中P是處理器執行指令的執行性能，N是該處理器執行該指令所需的指令 周期數；2. 4)根據η = P/L，得到每個處理核的性能負載比，其中m是性能負載比，L是該 處理核的運行負載，P是該處理核執行第i個基本塊的平均性能；2. 5)從處理核集合I中選出性能負載比最大的處理核作為第i個基本塊的目標處理核。第三步，對第二步得到的目標處理核相應的基本塊進行翻譯處理，得到在該目標 處理核上翻譯後的二進位代碼。所述的翻譯處理，包括以下步驟3. 1)當高速緩存中存在已翻譯至該目標處理核的二進位代碼時，直接執行3. 3)； 否則，執行3. 2)後再執行3. 3)；3. 2)將該基本塊動態的翻譯成該目標處理核處理時對應的二進位代碼；
3. 3)當二進位代碼與正在執行的前序基本塊存在數據依賴性時，執行3. 4)後再 執行3. 5)；否則，直接執行3. 5)；3. 4)前序基本塊執行結束後，得到相應的處理核上的執行結果，當前序基本塊被 分配到其它處理核上執行時，則切換系統上下文；3. 5)在該目標處理核上執行該基本塊對應的二進位代碼。第四步，統計各基本塊的執行頻率，將執行頻率大於閾值T的基本塊標記為熱點 基本塊，並把熱點基本塊翻譯後的二進位代碼緩存至高速緩存中。第五步，返回第二步，進行下一個基本塊的動態調度。與現有技術相比，本發明的有益效果是無需充分了解異構多核的指令特徵，編譯 器也因此獲得了平臺透明性，不需要針對不同的體系架構編寫程序或編譯不同的二進位代 碼。同時，該方法在具有通用指令集的異構多核系統中，發揮動態指令調度的功能，根據系 統多核的處理能力及負載情況等因素動態地分配指令到各異構多核上執行，從而彌補了靜 態調度的不能動態分配資源的不足，也降低了動態線程劃分的複雜性，從而進一步提高了 程序在異構多核上的執行效率。本方法不需要進行線程劃分，在無數據依賴的情況下能夠 最大程度地並行，因此降低了大約15%的線程同步開銷。


圖1是實施例的方法流程示意圖。
具體實施例方式以下結合附圖對本發明的方法進一步描述本實施例在以本發明技術方案為前提 下進行實施，給出了詳細的實施方式和具體的操作過程，但本發明的保護範圍不限於下述 的實施例。實施例如圖1所示，本實施例包括以下步驟第一步，在載入二進位代碼程序的過程中，對二進位代碼程序進行劃分處理，得到 若干基本塊。所述的劃分處理，是將第i條入口指令與第i+Ι條跳轉指令間的程序作為第i+1 個基本塊，其中0 ^ i，入口指令是跳轉指令轉到的指令或緊跟跳轉指令後的指令。本實施例中根據二進位程序代碼的跳轉指令，定義基本塊的入口指令和出口指 令，每一個基本塊是一組順序執行的指令序列，入口指令到出口指令間的指令代碼劃分為 一個基本塊。基本塊的入口指令為基本塊的第一條指令，即跳轉指令之後的指令或跳轉到 的指令，出口指令為其它基本塊入口指令的上一條指令或跳轉指令。不同的基本塊之間保 持前後偏序關係。第二步，分別對每個基本塊進行選擇處理，得到執行每個基本塊的目標處理核。所述的選擇處理，包括以下步驟2. 1)得到與第i個基本塊中的第j條指令A具有同等功能的指令Α* ；2. 2)得到所有處理指令A或指令A*的處理核A，進而得到同時處理第i個基本塊 中每條指令的處理核集合I ；
2. 3)根據ρ = 1/N,得到處理核集合I中每個處理核執行每條指令的執行性能，並 將每個處理核執行每條指令的執行性能相加，得到該集合中每個處理核執行第i個基本塊 的平均性能，其中P是處理器執行指令的執行性能，N是該處理器執行該指令所需的指令 周期數；2. 4)根據η = P/L，得到每個處理核的性能負載比，其中m是性能負載比，L是該 處理核的運行負載，P是該處理核執行第i個基本塊的平均性能；2. 5)從處理核集合I中選出性能負載比最大的處理核作為第i個基本塊的目標處理核。第三步，對第二步得到的目標處理核相應的基本塊進行翻譯處理，得到在該目標 處理核上翻譯後的二進位代碼。所述的翻譯處理，包括以下步驟3. 1)當高速緩存中存在已翻譯至該目標處理核的二進位代碼時，直接執行3. 3)； 否則，執行3. 2)後再執行3. 3)；3. 2)將該基本塊動態的翻譯成該目標處理核處理時對應的二進位代碼；3. 3)當二進位代碼與正在執行的前序基本塊存在數據依賴性時，執行3. 4)後再 執行3. 5)；否則，直接執行3. 5)；3. 4)前序基本塊執行結束後，得到相應的處理核上的執行結果，當前序基本塊被 分配到其它處理核上執行時，則切換系統上下文；3. 5)在該目標處理核上執行該基本塊對應的二進位代碼。本實施例中利用二進位翻譯技術將原二進位代碼映射到目標處理核的指令，存在 兩種情況一種情況是指令映射到目標處理核的指令的結構類似，它們存在一一對應關係， 並能完成同樣的功能；另一種情況是目標處理核上擁有一條或一組更有優勢的指令具備與 原基本塊中一組指令等價的功能，比如Intel的AVX(高級矢量擴展指令集)。翻譯後的指 令或指令組擁有更高的執行效率或功耗比。第四步，統計各基本塊的執行頻率，將執行頻率大於閾值T的基本塊標記為熱點 基本塊，並把熱點基本塊翻譯後的二進位代碼緩存至高速緩存中。本實施例能直接從高速緩存中取出頻繁執行的代碼，從而大大降低了代碼翻譯映 射的開銷。第五步，返回第二步，進行下一個基本塊的動態調度。本實施例在指令級動態優化的過程中，目標處理核的選擇、二進位指令的翻譯映 射以及處理核上代碼的執行組成流水線結構，明顯降低了指令分配到異構多核的切換開 銷，與動態線程級調度方法相比，本方法不需要進行線程劃分，在無數據依賴的情況下能夠 最大程度地並行，因此降低了大約15%的線程同步開銷。另外，採用高速緩存翻譯後的目標 處理核代碼，進一步降低了開銷，提升了系統性能，在一種具有DSP處理核的晶片上進行視 頻壓縮例程運算，平均達到了 1.8倍的加速比。
權利要求
一種面向嵌入式異構多核上執行動態分配指令的方法，其特徵在於，包括以下步驟第一步，在載入二進位代碼程序的過程中，對二進位代碼程序進行劃分處理，得到若干基本塊；第二步，分別對每個基本塊進行選擇處理，得到執行每個基本塊的目標處理核；第三步，對第二步得到的目標處理核相應的基本塊進行翻譯處理，得到在該目標處理核上翻譯後的二進位代碼；第四步，統計各基本塊的執行頻率，將執行頻率大於閾值T的基本塊標記為熱點基本塊，並把熱點基本塊翻譯後的二進位代碼緩存至高速緩存中；第五步，返回第二步，進行下一個基本塊的動態調度。
2.根據權利要求1所述的面向嵌入式異構多核上執行動態分配指令的方法，其特徵 是，第一步中所述的劃分處理，是將第i條入口指令與第i+Ι條跳轉指令間的程序作為第 i+1個基本塊，其中0 ^ i，入口指令是跳轉指令轉到的指令或緊跟跳轉指令後的指令。
3.根據權利要求1所述的面向嵌入式異構多核上執行動態分配指令的方法，其特徵 是，第二步中所述的選擇處理，包括以下步驟(2. 1)得到與第i個基本塊中的第j條指令A具有同等功能的指令Α* ； 2. 2)得到所有處理指令A或指令A*的處理核A，進而得到同時處理第i個基本塊中每 條指令的處理核集合I ；(2. 3)根據ρ = 1/N，得到處理核集合I中每個處理核執行每條指令的執行性能，並將每 個處理核執行每條指令的執行性能相加，得到該集合中每個處理核執行第i個基本塊的平 均性能，其中P是處理器執行指令的執行性能，N是該處理器執行該指令所需的指令周期 數；(2. 4)根據η = P/L，得到每個處理核的性能負載比，其中η是性能負載比，L是該處理 核的運行負載，P是該處理核執行第i個基本塊的平均性能；(2.5)從處理核集合I中選出性能負載比最大的處理核作為第i個基本塊的目標處理核。
4.根據權利要求1所述的面向嵌入式異構多核上執行動態分配指令的方法，其特徵 是，第三步中所述的翻譯處理，包括以下步驟(3.1)當高速緩存中存在已翻譯至該目標處理核的二進位代碼時，直接執行3.3)；否 則，執行3. 2)後再執行3. 3)；(3. 2)將該基本塊動態的翻譯成該目標處理核處理時對應的二進位代碼； 3.3)當二進位代碼與正在執行的前序基本塊存在數據依賴性時，執行3. 4)後再執行 (3.5)；否則，直接執行3. 5)；(3. 4)前序基本塊執行結束後，得到相應的處理核上的執行結果，當前序基本塊被分配 到其它處理核上執行時，則切換系統上下文；(3. 5)在該目標處理核上執行該基本塊對應的二進位代碼。
全文摘要
一種計算機技術領域的面向嵌入式異構多核上執行動態分配指令的方法，包括以下步驟對二進位代碼程序進行劃分處理，得到若干基本塊；分別對每個基本塊進行選擇處理，得到執行每個基本塊的目標處理核；對得到的目標處理核相應的基本塊進行翻譯處理，得到在該目標處理核上翻譯後的二進位代碼；統計各基本塊的執行頻率，將執行頻率大於閾值T的基本塊標記為熱點基本塊，並把熱點基本塊翻譯後的二進位代碼緩存至高速緩存中。本發明根據系統多核的處理能力及負載情況等因素動態地分配指令到各異構多核上執行，從而彌補了靜態調度的不能動態分配資源的不足，也降低了動態線程劃分的複雜性，從而進一步提高了程序在異構多核上的執行效率。
文檔編號G06F15/16GK101923492SQ20101025126
公開日2010年12月22日 申請日期2010年8月11日 優先權日2010年8月11日
發明者伍倩, 唐飛龍, 婁林, 朱寅, 沈耀, 過敏意, 馬曦 申請人:上海交通大學