張麗鵬，于 東，胡 毅

1(中國科學(xué)院 沈陽計(jì)算技術(shù)研究所，沈陽 110168)

2(中國科學(xué)院大學(xué)，北京 100049)

3(沈陽高精數(shù)控智能技術(shù)股份有限公司，沈陽 110168)E-mail:lipzhang_hn@outlook.com

1 引 言

數(shù)控系統(tǒng)技術(shù)是機(jī)械制造和控制相結(jié)合的產(chǎn)物，是當(dāng)今高端裝備制造業(yè)的核心技術(shù)之一.數(shù)控(numerical control，NC)機(jī)床特別是高檔數(shù)控機(jī)床是國際裝備制造業(yè)競(jìng)爭(zhēng)的熱點(diǎn)領(lǐng)域[1].隨著計(jì)算機(jī)信息技術(shù)的發(fā)展，多核處理技術(shù)成為了新的趨勢(shì)，這對(duì)數(shù)控技術(shù)提出了新的要求.目前，基于嵌入式芯片的數(shù)控系統(tǒng)仍較多采用單核處理器平臺(tái)，在這種情況下，通過多核平臺(tái)來解決單核遇到的問題具有重要的現(xiàn)實(shí)意義.

同構(gòu)多核處理器是采用多個(gè)相同結(jié)構(gòu)的核心組成的芯片，每個(gè)核心的功能完全相同，地位完全相等，沒有層級(jí)之分[2].各個(gè)核心執(zhí)行相同或相似的任務(wù)，整個(gè)芯片作為一個(gè)統(tǒng)一的結(jié)構(gòu)對(duì)外提供服務(wù)，以滿足提高性能、實(shí)現(xiàn)負(fù)載均衡的需求.

結(jié)合多核處理器系統(tǒng)結(jié)構(gòu)的特征，文獻(xiàn)[3]針對(duì)嵌入式多核處理器資源有限特點(diǎn)，采用整數(shù)線性規(guī)劃方法對(duì)軟件流水中負(fù)載、通信與內(nèi)存開銷建立模型，提出了一種基于軟件流水的任務(wù)調(diào)度方法以實(shí)現(xiàn)負(fù)載均衡及通信、內(nèi)存開銷的優(yōu)化.文獻(xiàn)[4]將系統(tǒng)中的所有可用核分組，將共享高速緩存的多個(gè)核作為一個(gè)簇集，采用簇間獨(dú)立調(diào)度、簇內(nèi)統(tǒng)一調(diào)度的混合調(diào)度策略，并利用核間中斷信號(hào)來同步任務(wù)處理過程.文獻(xiàn)[5]以最小化任務(wù)集的執(zhí)行跨度為目標(biāo)，提出一種基于改進(jìn)蟻群算法的多核任務(wù)分配與調(diào)度算法.文獻(xiàn)[6]通過對(duì)粒子群算法適應(yīng)度函數(shù)調(diào)整,提出一種基于粒子群算法的多核調(diào)度算法.文獻(xiàn)[7]提出一種種群均衡遺傳算法(BPGA)，將任務(wù)節(jié)點(diǎn)在處理器核上隨機(jī)分配而任務(wù)節(jié)點(diǎn)數(shù)均衡分配.上述文獻(xiàn)提出的任務(wù)調(diào)度策略具有一定的普適性，但算法實(shí)現(xiàn)的復(fù)雜性相對(duì)較高，實(shí)用性不強(qiáng).

本文在以上研究成果的基礎(chǔ)上，以負(fù)載均衡性為目標(biāo)，首先取合適的滑動(dòng)窗口值，將待執(zhí)行的任務(wù)序列以滑動(dòng)窗口大小進(jìn)行分批處理.文末對(duì)比實(shí)驗(yàn)表明了算法較好的滿足了系統(tǒng)的負(fù)載均衡并且有較好的執(zhí)行效率.

2 任務(wù)分配模型

2.1 相關(guān)理論

多核處理器上的任務(wù)分配與調(diào)度業(yè)已證明是NP-完全問題[8].通常的做法是使用啟發(fā)式算法或遺傳算法、模擬退火等優(yōu)化求解算法尋其近似解.文獻(xiàn)[9]提出RADG算法來消除迭代內(nèi)的數(shù)據(jù)依賴性，該算法通過重定時(shí)技術(shù)將周期相關(guān)的依賴任務(wù)圖轉(zhuǎn)換為一組獨(dú)立的任務(wù).經(jīng)過算法處理后所有的任務(wù)在迭代內(nèi)都不存在數(shù)據(jù)依賴關(guān)系，這樣就對(duì)任務(wù)順序的調(diào)整提供了可能.本文以此理論研究為基礎(chǔ)，為實(shí)驗(yàn)簡(jiǎn)單，假定任務(wù)之間不存在數(shù)據(jù)依賴關(guān)系，提出基于滑動(dòng)窗口的多核數(shù)控系統(tǒng)任務(wù)調(diào)度策略.

cpu負(fù)載是指在一段時(shí)間內(nèi)正在使用和等待使用cpu的平均任務(wù)數(shù),文獻(xiàn)[10]中采用一段時(shí)間間隔內(nèi)所有任務(wù)的執(zhí)行時(shí)間表示.本文引用并改進(jìn)了這個(gè)思想，將cpu的負(fù)載表示為:

(1)

按照負(fù)載計(jì)算公式(1),時(shí)間間隔取本次任務(wù)分配完成的時(shí)間與上一次任務(wù)分配完成的時(shí)間之差,理想狀態(tài)下每個(gè)內(nèi)核的負(fù)載為0.7,本文實(shí)驗(yàn)在同構(gòu)4核心處理器上進(jìn)行,因此可以認(rèn)為當(dāng)系統(tǒng)負(fù)載達(dá)到3以上時(shí)即為負(fù)載超標(biāo),應(yīng)考慮適當(dāng)降低滑動(dòng)窗口大小提高系統(tǒng)吞吐量.

2.2 任務(wù)分配模型

圖1描述了任務(wù)分配過程,考慮在某一小段時(shí)間內(nèi),設(shè)同構(gòu)多核處理器的核心數(shù)為m,記為C={c1,c2,…,cm}.待分配進(jìn)程P中有n個(gè)線程任務(wù),記為P={tr1,tr2,…,trn}，其中m>0,n>m.

圖1 任務(wù)分配模型

由于是同構(gòu)處理器，同一任務(wù)在不同核心上的執(zhí)行時(shí)間認(rèn)為是相同的，則每個(gè)任務(wù)在各相應(yīng)核心上的執(zhí)行時(shí)間可以表示為T={t1,t2,…,tn}.取滑動(dòng)窗口值為w，w<=n.則該滑動(dòng)窗口內(nèi)任務(wù)在各相應(yīng)核心上的執(zhí)行時(shí)間可表示為矩陣E，該矩陣有w/m行,m列.

令sum1,sum2,…,summ分別表示矩陣E中每一列的列和,則sum1,sum2,…,summ分別表示分配在核心1,2,…,m上的線程執(zhí)行完成所用時(shí)長.為使負(fù)載均衡，問題可轉(zhuǎn)化為尋求在m個(gè)核心上分配任務(wù)的策略，使得summax與summin差值最小.即:

min(summax-summin)

(2)

3 任務(wù)分配算法

3.1 算法思想

在任務(wù)執(zhí)行調(diào)度之前，首先進(jìn)行任務(wù)序列的預(yù)處理，以系統(tǒng)的實(shí)時(shí)負(fù)載為依據(jù)采用大小合適的滑動(dòng)窗口限制每輪任務(wù)的分配量，將滑動(dòng)窗口中的任務(wù)隊(duì)列設(shè)為多核心訪問的公共資源.對(duì)任務(wù)隊(duì)列依序取滑動(dòng)窗口大小的前兩份,記為首列和次列.首先對(duì)兩個(gè)任務(wù)隊(duì)列進(jìn)行不同的預(yù)處理,過程為鏈?zhǔn)綒w并排序過程的改進(jìn),排好序的首列基于優(yōu)先級(jí)由大到小、運(yùn)行時(shí)間由大到小排列，而次列則基于優(yōu)先級(jí)由大到小、運(yùn)行時(shí)間由小到大排列.基于此,在任務(wù)分配時(shí)分別選擇已排序的首列和次列的當(dāng)前列表頭部的任務(wù)作為復(fù)合任務(wù)分配給輪到的核心.首次分配任務(wù)時(shí)的核心得到的復(fù)合任務(wù)將是優(yōu)先級(jí)最高執(zhí)行時(shí)間最長的任務(wù)與優(yōu)先級(jí)最高執(zhí)行時(shí)間最短的任務(wù),下一個(gè)核心得到的任務(wù)將分別是任務(wù)隊(duì)列剩余任務(wù)中優(yōu)先級(jí)最高執(zhí)行時(shí)間最長的任務(wù)與優(yōu)先級(jí)最高執(zhí)行時(shí)間最短任務(wù)的復(fù)合,以此類推,直到本輪滑動(dòng)窗口中的任務(wù)分配完畢,計(jì)算當(dāng)前的系統(tǒng)負(fù)載,更新滑動(dòng)窗口值.整體處理流程如圖2所示.

圖2 算法執(zhí)行流程圖

3.2 任務(wù)預(yù)處理

將任務(wù)隊(duì)列看作有序的結(jié)構(gòu)，首先依次取任務(wù)隊(duì)列中前w個(gè)任務(wù)作為首列Task1,次列Task2.基于鏈?zhǔn)綒w并排序過程的改進(jìn)，分別對(duì)兩任務(wù)隊(duì)列進(jìn)行排序,算法整體時(shí)間復(fù)雜度為O(nlogn),空間復(fù)雜度為O(1).

主要數(shù)據(jù)結(jié)構(gòu)說明:

struct task_struct{

……

long etm;

long pro;

struct task_struct *next;

……

}

在數(shù)據(jù)結(jié)構(gòu)task_struct中，屬性etm表示該任務(wù)執(zhí)行時(shí)間計(jì)數(shù)或運(yùn)行時(shí)間片，pro表示任務(wù)運(yùn)行優(yōu)先級(jí)數(shù),越大優(yōu)先級(jí)越高.

過程詳圖如圖3,流程中newHead表示該次迭代中需合并部分的后半部鏈表的頭部,內(nèi)部循環(huán)每次迭代中①處剪斷需要合并的前半段,②處剪斷需要合并的后半段,lastHead在合并前指向后半段開始的位置,合并后指向下一輪將要從哪個(gè)位置合并.

圖3 預(yù)處理算法執(zhí)行流程圖

過程merge()為合并兩個(gè)隊(duì)列的核心處理流程，實(shí)現(xiàn)對(duì)首列及隊(duì)列按照不同需求的分割，排序及合并.對(duì)原始隊(duì)列Task按照任務(wù)優(yōu)先級(jí)降序，運(yùn)行時(shí)間降序排序.Task.pro、Task.etm分別代表任務(wù)的優(yōu)先級(jí)與執(zhí)行時(shí)長.對(duì)于次列Task2的處理流程于此基本一致,所不同的是需將流程merge()中循環(huán)體內(nèi)的條件“>”改為“<=”.如此得到的兩隊(duì)列即可進(jìn)行任務(wù)的復(fù)合并進(jìn)一步進(jìn)行任務(wù)分配.過程見圖4.

圖4 歸并過程執(zhí)行流程圖

上述兩個(gè)過程完成了按滑動(dòng)窗口值依次取任務(wù)task1，task2并已按照預(yù)設(shè)要求排序，是后續(xù)步驟的基礎(chǔ).為使任務(wù)隊(duì)列在指定核心上分配，并使得分配任務(wù)后在滑動(dòng)窗口內(nèi)所有任務(wù)在執(zhí)行期間每個(gè)處理器核心的負(fù)載相對(duì)均衡.需要繼續(xù)對(duì)上述得到的任務(wù)隊(duì)列進(jìn)行任務(wù)的兩兩復(fù)合.在這里需要利用Linux系統(tǒng)在多核計(jì)算機(jī)上對(duì)處理器核心的親緣性，即綁定進(jìn)行/線程到指定處理器核心上執(zhí)行，在本文中使用c語言頭文件sched.h中的sched_setaffinity系統(tǒng)調(diào)用的方式.對(duì)于復(fù)合后任務(wù)的執(zhí)行情況，默認(rèn)情況是先執(zhí)行task.etm較大的.算法流程如圖5所示.

圖5 復(fù)合與分配任務(wù)算法流程圖

過程adjust_()計(jì)算處理器當(dāng)前負(fù)載，據(jù)此動(dòng)態(tài)調(diào)整滑動(dòng)窗口值w,防止任務(wù)的阻塞,提高的系統(tǒng)實(shí)時(shí)吞吐量.

w值的確定借鑒了TCP中擁塞控制機(jī)制[11],采用慢開始和擁塞避免算法,開始時(shí)將w值設(shè)置為處理器核心數(shù)用以探測(cè),隨之由小到大逐漸增大滑動(dòng)窗口,即每經(jīng)過一輪處理,w值加倍.當(dāng)系統(tǒng)的負(fù)載達(dá)到2時(shí),采用擁塞避免機(jī)制,線性增大w值.當(dāng)系統(tǒng)負(fù)載達(dá)到3時(shí),重置w值為最小值.流程如圖6所示.

圖6 調(diào)整窗口值程序流程圖

4 實(shí)驗(yàn)驗(yàn)證與結(jié)果分析

實(shí)驗(yàn)環(huán)境：飛凌公司研發(fā)的搭載i.MX6處理器的同構(gòu)4核心ARM開發(fā)板,Linux版本號(hào)位3.05.如圖7所示.實(shí)驗(yàn)采取隨機(jī)任務(wù)圖作為任務(wù)調(diào)度與分配的測(cè)試任務(wù)集.

圖7 多核ARM開發(fā)板

各次實(shí)驗(yàn)中隨機(jī)生成八百萬任務(wù)數(shù)據(jù),進(jìn)行多次實(shí)驗(yàn)后隨機(jī)取5次實(shí)驗(yàn)結(jié)果測(cè)得各個(gè)核心的負(fù)載百分比情況如表1所示.結(jié)果表明本文提出算法對(duì)于系統(tǒng)的負(fù)載均衡性測(cè)試有較好的實(shí)驗(yàn)結(jié)果.

表1 各核心負(fù)載情況

對(duì)文獻(xiàn)[7]中提出的BPGA算法進(jìn)行對(duì)比，設(shè)定處理器數(shù)為1，處理器核心數(shù)固定為4，雜交與變異概率分別仍為0.8、0.4，種群規(guī)模為100，算法最大迭代次數(shù)1000.隨機(jī)取10次實(shí)驗(yàn)執(zhí)行時(shí)長對(duì)比,其結(jié)果如圖8所示,計(jì)算所取10次實(shí)驗(yàn)結(jié)果的平均執(zhí)行效率較前者提高了11.96%.

圖8 執(zhí)行時(shí)間對(duì)比圖

分析原因可能在于種群規(guī)模與迭代次數(shù)過大的設(shè)置使算法收斂時(shí)間過長，為增加對(duì)比性，更改BPGA算法參數(shù)，設(shè)定種群規(guī)模為50，最大迭代次數(shù)800，其實(shí)驗(yàn)對(duì)比結(jié)果如圖9.

圖9 執(zhí)行時(shí)間對(duì)比圖

計(jì)算所取10次隨機(jī)實(shí)驗(yàn)結(jié)果的平均執(zhí)行效率,本文算法較前者提高了11.27%.主要原因在于BPGA算法在尋找最優(yōu)解時(shí)的頻繁迭代使得任務(wù)執(zhí)行時(shí)間較長.實(shí)驗(yàn)結(jié)果表明，本文算法能夠較好的滿足多核系統(tǒng)處理器的負(fù)載均衡性，同時(shí)在執(zhí)行效率上有良好的表現(xiàn).

5 結(jié)束語

本文在前人研究的基礎(chǔ)上,針對(duì)同構(gòu)多核數(shù)控系統(tǒng),研究并實(shí)現(xiàn)了多核任務(wù)調(diào)度算法,在任務(wù)預(yù)處理階段,采用滑動(dòng)窗口動(dòng)態(tài)調(diào)控任務(wù)序列大小以避免任務(wù)阻塞,在任務(wù)分配之前對(duì)任務(wù)隊(duì)列進(jìn)行復(fù)制、排序并復(fù)合.最后實(shí)驗(yàn)結(jié)果表明本文算法較好的滿足了負(fù)載的均衡性,同時(shí)又有較好的執(zhí)行效率.

本文存在的問題是任務(wù)數(shù)據(jù)為隨機(jī)生成,具有正態(tài)分布的特征，對(duì)于數(shù)據(jù)類別分布不穩(wěn)定、極端的任務(wù)集未能驗(yàn)證.下一步將在實(shí)際生成環(huán)境中進(jìn)行測(cè)試.