本文針對基于可配置處理器的異構多核結構，提出一種新的線程級動態調度模型。此類異構多核系統中每個核分別針對某一應用做指令集擴展，調度器通過線程、處理器核以及指令集間的映射關系，動態調度線程至適合的處理器核，從而在沒有大幅增加芯片面積的前提下，達到與每個核都

1.概述

多核處理器從結構上可以分為同構多核和異構多核兩類。同構多核使用多個相同的處理核，通過并行處理提高系統性能；異構多核使用多個不同的處理核，增加并行性的同時還可針對特定應用做硬件加速，因此具有更好的加速比。不過，由于異構多核的核間指令集存在差異，動態調度較難實現。

本文針對基于可配置處理器的異構多核結構，提出一種新的線程級動態調度模型。此類異構多核系統中每個核分別針對某一應用做指令集擴展，調度器通過線程、處理器核以及指令集間的映射關系，動態調度線程至適合的處理器核，從而在沒有大幅增加芯片面積的前提下，達到與每個核都具有全擴展指令集相近似的加速比，此外該模型還可以有效減少編程模型的復雜度。

2.新模型的數學描述

2.1 現有異構多核分析

同構多核核間無差異，因此動態調度容易實現，而異構多核動態調度可行與否取決于指令集結構設計。現有異構多核指令集結構設計大致可分為三類：

● 指令集完全不同

此類設計中，設計者選擇不同功能導向的處理器核組成異構多核系統，每一種核針對某一類處理都具有較強功能，核之間的指令集存在巨大差異，因此動態調度在此類設計中無法實現，只能通過靜態調度的方式完成任務指派［3］。

● 指令集完全相同

此類設計中，設計者選取具有相同指令集但硬件配置上有所不同的處理器核，組成異構多核系統［2］。

● 指令集部分相同

此類設計中，處理核心是一組可配置處理器，所有的處理核心具有一個公共的指令集，每個核心都可以根據應用增加一些擴展指令，以增強對應用某一方面的處理能力［4］。

2.2. 新模型的數學描述

本文提出的調度模型即針對基于可配置處理器的異構多核。該模型成立基于以下假設，每個核的指令集配置完成于芯片設計階段，芯片一旦生產，任意一個核的指令集配置都不可修改。實際上，動態可配置指令集對芯片面積及功耗都會帶來巨大消耗，因此現在市場上絕大部分可配置處理器都符合上述假設。為描述簡單起見，下文中一個處理器核被稱為core。

首先定義模型中使用的三個集合。

集合 C= {Xi|Xi是系統中某個core}

集合 I={Yi|Yi是系統中某種指令集}

集合 T={Zi|Zi是系統中某個線程}

對于上述集合，存在映射關系

f ：C→∪Ii，Ii.I且Ii≠φ，即任意一個core必然存在一個I的非空子集Im與之對應，其實際意義表示該core可以運行集合Im所包含的指令。根據模型的成立條件，core的指令集在系統運行時不可修改，因此不同core對應的Im可能相同，但是每個core僅對應一個Im，故f是單射，即XIi∈C，Im.I，且Im ≠φ，f（Xi）=Im （式1）類似的。

還存在映射關系g:T→∪Ii，Ii.I且Ii≠φ，即任意一個線程必然存在一個I的非空子集In與之對應，其實際意義表示該線程必須運行在具有指令集In 的處理器上。任意一個時刻每個線程僅有一個In與之對應，此外不同的線程對應的In可能相同，故g也是單射，即Zi∈T，In.I，且In≠φ，g（Zi）=In （式2）根據上述公式，對任意的Xi，可以得到一個Im，任意的Zi，可以得到一個In，則公式（3）成立。

這是模型中的調度函數，當線程所需指令集是core指令集的子集，match（Im，In）值為1，表示線程Zi可以運行在處理器核Xi上。

3. 模型實現

上述模型可以有多種實現方式，本文參考位圖的思想完成其中一種實現。

3.1. 三個集合的確定

考慮常用多核規模，32 種指令集已可滿足指令集種類數量要求，因此該實現將無符號二進制32位整數的每一位對應一種指令集，其最低有效位為20，記為ISA1，最高有效位為231，記為ISA32，若可以運行指令集ISAm，則該無符號整數的第m位為1，故集合I在基于位圖的實現中定義為I={ISAm無符號整數第m-1位為1，1≤m≤32}。

任意I中幾個元素，對其依次做或運算（OR）得到一個新整數，該整數即可表示由這幾個元素構成的I的子集。系統中所有的core具有公共指令集，將此指令集記為ISA1。

系統中每個core具有一個唯一編號，因此集合C= {0， 1， ……， n.1}，n為系統中core的數量。

此外，根據線程的定義，不同的線程不能具有相同的線程句柄，因此T={所有線程句柄}。

3.2. 三個公式的實現

定義一個二維的無符號整數數組cpu_isa_map，數組每行第一個元素為core的編號，第二個元素為I的一個非空子集，表示該core可以運行的所有指令集，最后一行用于循環結束，第一個元素為無窮大（0xFFFFFFFF），第二個元素為空集。以core的編號對該數組遍歷查詢即可實現公式1。圖1為該數組的一個例子。

POSIX線程標準中，每個線程具有pthread_attr_t結構體類型的屬性參數，為了兼容POSIX標準，擴展該結構體，添加一個無符號整數變量runnable_isa，表示該線程可以運行的指令集集合。創建線程時需要顯示設置runnable_isa，如果沒有設置，該變量默認值為公共指令集ISA1，這樣就實現了公式2。

對于公式3，首先根據調度器當前運行的core編號查詢cpu_isa_map獲得core支持的指令集core_isa，然后遍歷線程調度器的就緒線程隊列，將每個線程的runnable_isa屬性與core_isa做與操作（AND），若結果不為0且runnable小于等于core_isa，則說明該core的指令集配置滿足線程所需的運行要求。

即match（Im，In）為1，線程可以被運行，如果所有線程均無法運行在該核上，則返回空指針。圖2為此算法實現，其中HEAD（state）為獲得就緒線程隊列的頭指針，該隊列尾指針的next指針為空指針。至此，模型已經全部實現完畢。

4. 實驗結果

本文使用基于Xtensa處理器組成的異構多核系統，以Motion-JPEG作為測試程序對該模型進行實驗分析。

4.1. 實驗平臺簡介

Xtensa處理器是Tensilica公司推出的一種可配置處理器，該處理器除了具有一組固定的指令集之外，還可以通過TIE功能擴展指令集以加速程序運行。Tensilica公司提供了該處理器基于SystemC的仿真模型。本文的實驗平臺是由3個Xtensa處理器仿真模型組成的異構多核系統，分別記為core0，core1，core2。

本文節選自：中國集成電路

編輯：jq