本文針對(duì)基于可配置處理器的異構(gòu)多核結(jié)構(gòu)，提出一種新的線(xiàn)程級(jí)動(dòng)態(tài)調(diào)度模型。此類(lèi)異構(gòu)多核系統(tǒng)中每個(gè)核分別針對(duì)某一應(yīng)用做指令集擴(kuò)展，調(diào)度器通過(guò)線(xiàn)程、處理器核以及指令集間的映射關(guān)系，動(dòng)態(tài)調(diào)度線(xiàn)程至適合的處理器核，從而在沒(méi)有大幅增加芯片面積的前提下，達(dá)到與每個(gè)核都

1.概述

多核處理器從結(jié)構(gòu)上可以分為同構(gòu)多核和異構(gòu)多核兩類(lèi)。同構(gòu)多核使用多個(gè)相同的處理核，通過(guò)并行處理提高系統(tǒng)性能；異構(gòu)多核使用多個(gè)不同的處理核，增加并行性的同時(shí)還可針對(duì)特定應(yīng)用做硬件加速，因此具有更好的加速比。不過(guò)，由于異構(gòu)多核的核間指令集存在差異，動(dòng)態(tài)調(diào)度較難實(shí)現(xiàn)。

本文針對(duì)基于可配置處理器的異構(gòu)多核結(jié)構(gòu)，提出一種新的線(xiàn)程級(jí)動(dòng)態(tài)調(diào)度模型。此類(lèi)異構(gòu)多核系統(tǒng)中每個(gè)核分別針對(duì)某一應(yīng)用做指令集擴(kuò)展，調(diào)度器通過(guò)線(xiàn)程、處理器核以及指令集間的映射關(guān)系，動(dòng)態(tài)調(diào)度線(xiàn)程至適合的處理器核，從而在沒(méi)有大幅增加芯片面積的前提下，達(dá)到與每個(gè)核都具有全擴(kuò)展指令集相近似的加速比，此外該模型還可以有效減少編程模型的復(fù)雜度。

2.新模型的數(shù)學(xué)描述

2.1 現(xiàn)有異構(gòu)多核分析

同構(gòu)多核核間無(wú)差異，因此動(dòng)態(tài)調(diào)度容易實(shí)現(xiàn)，而異構(gòu)多核動(dòng)態(tài)調(diào)度可行與否取決于指令集結(jié)構(gòu)設(shè)計(jì)。現(xiàn)有異構(gòu)多核指令集結(jié)構(gòu)設(shè)計(jì)大致可分為三類(lèi)：

● 指令集完全不同

此類(lèi)設(shè)計(jì)中，設(shè)計(jì)者選擇不同功能導(dǎo)向的處理器核組成異構(gòu)多核系統(tǒng)，每一種核針對(duì)某一類(lèi)處理都具有較強(qiáng)功能，核之間的指令集存在巨大差異，因此動(dòng)態(tài)調(diào)度在此類(lèi)設(shè)計(jì)中無(wú)法實(shí)現(xiàn)，只能通過(guò)靜態(tài)調(diào)度的方式完成任務(wù)指派［3］。

● 指令集完全相同

此類(lèi)設(shè)計(jì)中，設(shè)計(jì)者選取具有相同指令集但硬件配置上有所不同的處理器核，組成異構(gòu)多核系統(tǒng)［2］。

● 指令集部分相同

此類(lèi)設(shè)計(jì)中，處理核心是一組可配置處理器，所有的處理核心具有一個(gè)公共的指令集，每個(gè)核心都可以根據(jù)應(yīng)用增加一些擴(kuò)展指令，以增強(qiáng)對(duì)應(yīng)用某一方面的處理能力［4］。

2.2. 新模型的數(shù)學(xué)描述

本文提出的調(diào)度模型即針對(duì)基于可配置處理器的異構(gòu)多核。該模型成立基于以下假設(shè)，每個(gè)核的指令集配置完成于芯片設(shè)計(jì)階段，芯片一旦生產(chǎn)，任意一個(gè)核的指令集配置都不可修改。實(shí)際上，動(dòng)態(tài)可配置指令集對(duì)芯片面積及功耗都會(huì)帶來(lái)巨大消耗，因此現(xiàn)在市場(chǎng)上絕大部分可配置處理器都符合上述假設(shè)。為描述簡(jiǎn)單起見(jiàn)，下文中一個(gè)處理器核被稱(chēng)為core。

首先定義模型中使用的三個(gè)集合。

集合 C= {Xi|Xi是系統(tǒng)中某個(gè)core}

集合 I={Yi|Yi是系統(tǒng)中某種指令集}

集合 T={Zi|Zi是系統(tǒng)中某個(gè)線(xiàn)程}

對(duì)于上述集合，存在映射關(guān)系

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

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

這是模型中的調(diào)度函數(shù)，當(dāng)線(xiàn)程所需指令集是core指令集的子集，match（Im，In）值為1，表示線(xiàn)程Zi可以運(yùn)行在處理器核Xi上。

3. 模型實(shí)現(xiàn)

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

3.1. 三個(gè)集合的確定

考慮常用多核規(guī)模，32 種指令集已可滿(mǎn)足指令集種類(lèi)數(shù)量要求，因此該實(shí)現(xiàn)將無(wú)符號(hào)二進(jìn)制32位整數(shù)的每一位對(duì)應(yīng)一種指令集，其最低有效位為20，記為ISA1，最高有效位為231，記為ISA32，若可以運(yùn)行指令集ISAm，則該無(wú)符號(hào)整數(shù)的第m位為1，故集合I在基于位圖的實(shí)現(xiàn)中定義為I={ISAm無(wú)符號(hào)整數(shù)第m-1位為1，1≤m≤32}。

任意I中幾個(gè)元素，對(duì)其依次做或運(yùn)算（OR）得到一個(gè)新整數(shù)，該整數(shù)即可表示由這幾個(gè)元素構(gòu)成的I的子集。系統(tǒng)中所有的core具有公共指令集，將此指令集記為ISA1。

系統(tǒng)中每個(gè)core具有一個(gè)唯一編號(hào)，因此集合C= {0， 1， ……， n.1}，n為系統(tǒng)中core的數(shù)量。

此外，根據(jù)線(xiàn)程的定義，不同的線(xiàn)程不能具有相同的線(xiàn)程句柄，因此T={所有線(xiàn)程句柄}。

3.2. 三個(gè)公式的實(shí)現(xiàn)

定義一個(gè)二維的無(wú)符號(hào)整數(shù)數(shù)組cpu_isa_map，數(shù)組每行第一個(gè)元素為core的編號(hào)，第二個(gè)元素為I的一個(gè)非空子集，表示該core可以運(yùn)行的所有指令集，最后一行用于循環(huán)結(jié)束，第一個(gè)元素為無(wú)窮大（0xFFFFFFFF），第二個(gè)元素為空集。以core的編號(hào)對(duì)該數(shù)組遍歷查詢(xún)即可實(shí)現(xiàn)公式1。圖1為該數(shù)組的一個(gè)例子。

POSIX線(xiàn)程標(biāo)準(zhǔn)中，每個(gè)線(xiàn)程具有pthread_attr_t結(jié)構(gòu)體類(lèi)型的屬性參數(shù)，為了兼容POSIX標(biāo)準(zhǔn)，擴(kuò)展該結(jié)構(gòu)體，添加一個(gè)無(wú)符號(hào)整數(shù)變量runnable_isa，表示該線(xiàn)程可以運(yùn)行的指令集集合。創(chuàng)建線(xiàn)程時(shí)需要顯示設(shè)置runnable_isa，如果沒(méi)有設(shè)置，該變量默認(rèn)值為公共指令集ISA1，這樣就實(shí)現(xiàn)了公式2。

對(duì)于公式3，首先根據(jù)調(diào)度器當(dāng)前運(yùn)行的core編號(hào)查詢(xún)cpu_isa_map獲得core支持的指令集core_isa，然后遍歷線(xiàn)程調(diào)度器的就緒線(xiàn)程隊(duì)列，將每個(gè)線(xiàn)程的runnable_isa屬性與core_isa做與操作（AND），若結(jié)果不為0且runnable小于等于core_isa，則說(shuō)明該core的指令集配置滿(mǎn)足線(xiàn)程所需的運(yùn)行要求。

即match（Im，In）為1，線(xiàn)程可以被運(yùn)行，如果所有線(xiàn)程均無(wú)法運(yùn)行在該核上，則返回空指針。圖2為此算法實(shí)現(xiàn)，其中HEAD（state）為獲得就緒線(xiàn)程隊(duì)列的頭指針，該隊(duì)列尾指針的next指針為空指針。至此，模型已經(jīng)全部實(shí)現(xiàn)完畢。

4. 實(shí)驗(yàn)結(jié)果

本文使用基于Xtensa處理器組成的異構(gòu)多核系統(tǒng)，以Motion-JPEG作為測(cè)試程序?qū)υ撃Ｐ瓦M(jìn)行實(shí)驗(yàn)分析。

4.1. 實(shí)驗(yàn)平臺(tái)簡(jiǎn)介

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

本文節(jié)選自：中國(guó)集成電路

編輯：jq