片上網(wǎng)絡(luò)異構(gòu)多核系統(tǒng)任務(wù)調(diào)度與映射

楊鵬飛,王泉

(西安電子科技大學(xué)計(jì)算機(jī)學(xué)院,710071,西安)

?

片上網(wǎng)絡(luò)異構(gòu)多核系統(tǒng)任務(wù)調(diào)度與映射

楊鵬飛,王泉

(西安電子科技大學(xué)計(jì)算機(jī)學(xué)院,710071,西安)

針對傳統(tǒng)任務(wù)模型包含有效信息少,任務(wù)調(diào)度算法效率低、效果差的問題,設(shè)計(jì)了新的任務(wù)模型,提出了一種改進(jìn)的粒子群算法(optimized particle swarm optimization, oPSO)。新模型增加了對任務(wù)類型及任務(wù)間遷移成本、計(jì)算單元類型及其運(yùn)行成本等特性的描述。通過分析任務(wù)調(diào)度問題的需求,制定了oPSO算法的編解碼方案,設(shè)定了算法各個(gè)關(guān)鍵部分參數(shù)及計(jì)算方法,并解決了粒子群算法(PSO)在任務(wù)調(diào)度前期收斂速度過快、后期易陷入局部最優(yōu)的問題。在不同任務(wù)規(guī)模下分別對遺傳算法(GA)、PSO以及oPSO算法進(jìn)行調(diào)度仿真對比,當(dāng)IP核數(shù)目為100左右時(shí),oPSO算法較GA算法和PSO算法運(yùn)行時(shí)間至少縮短10%,系統(tǒng)功耗至少降低15%,實(shí)驗(yàn)結(jié)果表明:oPSO算法調(diào)度效果明顯優(yōu)于其他算法,且各節(jié)點(diǎn)上功耗更為均衡,適用于解決任務(wù)調(diào)度問題。

多核系統(tǒng);片上網(wǎng)絡(luò);任務(wù)劃分;IP映射

利用片上網(wǎng)絡(luò)連接的系統(tǒng)級芯片(system-on-chip, SOC)成為新一代復(fù)雜計(jì)算體系結(jié)構(gòu)的必然選擇[1],但是也給系統(tǒng)設(shè)計(jì)帶來很多新的問題與挑戰(zhàn),任務(wù)的調(diào)度映射問題成為研究重點(diǎn),決定了任務(wù)在體系結(jié)構(gòu)上的實(shí)現(xiàn)方式、處理性能和效率。調(diào)度問題的通用解決思路是將任務(wù)抽象成某種形式的模型來設(shè)計(jì)調(diào)度算法,根據(jù)子任務(wù)之間的信息,以整個(gè)系統(tǒng)運(yùn)行時(shí)間最短為目標(biāo)對任務(wù)進(jìn)行分配與調(diào)度[2-4],這其中涉及任務(wù)模型的設(shè)計(jì)以及調(diào)度算法的選擇應(yīng)用兩個(gè)關(guān)鍵部分。

任務(wù)模型方面,最為普遍的是有向無環(huán)圖(directed acyclic graph, DAG)模型。DAG模型將任務(wù)間的關(guān)系簡單抽象為前后調(diào)用關(guān)系、數(shù)據(jù)通信量以及其在不同計(jì)算單元上的運(yùn)算時(shí)間,而任務(wù)間的相互依賴關(guān)系復(fù)雜,其他影響因素例如任務(wù)類型、其對應(yīng)的計(jì)算單元的種類、子任務(wù)在不同計(jì)算單元上的運(yùn)行成本等,DAG模型并沒有全面包含,且模型較少地考慮任務(wù)在不同計(jì)算單元間的遷移成本。

調(diào)度算法方面,從進(jìn)行調(diào)度決策的時(shí)機(jī)來看,可以分為靜態(tài)調(diào)度和動態(tài)調(diào)度。靜態(tài)任務(wù)調(diào)度是由編譯器在編譯時(shí)進(jìn)行調(diào)度決策。例如基于列表的算法(list-based)[3-4]、聚類算法[5-7]和基于副本的算法(duplication based algorithms)[6-7]。靜態(tài)調(diào)度模型有一些缺點(diǎn),如模型只是基于對處理器間通信和執(zhí)行時(shí)間的近似估計(jì),會產(chǎn)生不好的調(diào)度結(jié)果。動態(tài)任務(wù)調(diào)度是根據(jù)系統(tǒng)中實(shí)際任務(wù)運(yùn)行時(shí)的情況實(shí)時(shí)將其調(diào)度到相應(yīng)的計(jì)算單元上執(zhí)行,并滿足系統(tǒng)所要求的各項(xiàng)約束指標(biāo),例如基于遺傳算法[8]和蟻群[9-10]的啟發(fā)式任務(wù)調(diào)度、基于任務(wù)池庫的動態(tài)調(diào)度算法[11]、粒子群優(yōu)化算法(particle swarm optimization,PSO)[12]以及基于實(shí)時(shí)性約束的動態(tài)調(diào)度算法[13]等。在實(shí)際應(yīng)用中,這些算法本身的問題容易導(dǎo)致運(yùn)行過程中產(chǎn)生種種弊端。例如遺傳算法參數(shù)較多、編程實(shí)現(xiàn)比較復(fù)雜,且易陷入局部最優(yōu);蟻群算法前期不能很好地覆蓋全部集合;粒子群優(yōu)化算法較遺傳算法更加方便高效,但是其初期收斂速度過快,易陷入局部最優(yōu),后期的局部搜索能力較差,收斂速度緩慢。以上種種問題導(dǎo)致應(yīng)用傳統(tǒng)算法進(jìn)行調(diào)度計(jì)算都會導(dǎo)致結(jié)果與最優(yōu)值間存在差距。

此外,目前的調(diào)度算法多數(shù)較少或者沒有綜合考慮功耗均衡、資源占用等其他因素,沒有考慮片上網(wǎng)絡(luò)拓?fù)涞漠悩?gòu)性,且大多忽略任務(wù)間的通信延時(shí),算法的實(shí)用性較差。在項(xiàng)目組之前的研究中,針對片上網(wǎng)絡(luò)規(guī)模大,片上可調(diào)用資源相對任務(wù)規(guī)模有較大盈余的情況,將調(diào)度方案分為任務(wù)劃分與調(diào)度和IP映射兩個(gè)部分完成[14],但是IP映射算法在片上網(wǎng)絡(luò)規(guī)模不大,任務(wù)運(yùn)行需調(diào)用全部片上資源的情況下成為多余運(yùn)算,浪費(fèi)了系統(tǒng)資源。

本文重新設(shè)計(jì)了任務(wù)模型,使其能真實(shí)反映子任務(wù)間調(diào)度與制約關(guān)系。適應(yīng)性的設(shè)計(jì)改進(jìn)粒子群優(yōu)化算法,使其適用于異構(gòu)多核任務(wù)調(diào)度映射問題,并克服了算法本身容易陷入局部最優(yōu)、后期局部搜索能力差的缺陷。利用其將一個(gè)大的任務(wù)按照通信量及調(diào)用關(guān)系分割成數(shù)個(gè)具有高并行性、粒度大小合適的子任務(wù),結(jié)合任務(wù)性質(zhì)分配到相應(yīng)的計(jì)算單元上,在任務(wù)執(zhí)行時(shí)間短、占用系統(tǒng)資源少、功耗均衡的前提下,進(jìn)一步降低整個(gè)系統(tǒng)的通信延時(shí)。

1 相關(guān)模型

算法設(shè)計(jì)了兩個(gè)模型,任務(wù)調(diào)度模型和通信核圖。任務(wù)調(diào)度模型將任務(wù)抽象為一個(gè)五元組

ODAG=(V,E,S,U,C)

(1)

式中:V表示任務(wù)節(jié)點(diǎn)集,即頂點(diǎn)v∈V表示一個(gè)子任務(wù);E表示邊集,邊eij∈E表示任務(wù)vi到vj存在數(shù)據(jù)通信,方向表示數(shù)據(jù)傳遞方向;S表示任務(wù)類型,其與計(jì)算單元的類型對應(yīng),即任務(wù)只能被分配到與之類型匹配的計(jì)算單元上執(zhí)行,可以通過矩陣D={da,b}表示,元素da,b=∞表示任務(wù)va不適宜在計(jì)算單元pb上執(zhí)行,da,b=t表示va可以在pb上執(zhí)行,執(zhí)行時(shí)間為t。元素Ur∈U表示第r種計(jì)算單元的單位時(shí)間運(yùn)行成本。元素Cij∈C表示子任務(wù)vi通過邊eij到vj的遷移成本,當(dāng)vi到vj分配到同一個(gè)計(jì)算單元上時(shí),Cij為0。

子任務(wù)映射到計(jì)算單元上,會形成具有通信關(guān)系的通信核圖,可以抽象為一個(gè)三元組

CDAG=(P,R,T)

(2)

式中:P表示通信核圖中的計(jì)算單元集合,其中頂點(diǎn)pη(r)∈P,η是計(jì)算單元的唯一識別編碼,r為類型編碼;R表示邊集,邊rxy∈R表示計(jì)算單元px與py之間存在數(shù)據(jù)交換;T為計(jì)算單元間的通信開銷,Txy表示計(jì)算單元px與py之間的通信總量。

2 調(diào)度算法

粒子群算法不能直接用于解決任務(wù)調(diào)度映射問題,必須進(jìn)行適應(yīng)性的優(yōu)化設(shè)計(jì)。

2.1 編解碼

子任務(wù)和計(jì)算單元的數(shù)目經(jīng)常是不同的,設(shè)一個(gè)任務(wù)中包含N個(gè)子任務(wù),系統(tǒng)中有M個(gè)可利用的計(jì)算單元,這些計(jì)算單元可分為m種,按子任務(wù)數(shù)與計(jì)算單元數(shù)的大小關(guān)系,編碼分為以下3種情況。

(1)計(jì)算單元數(shù)等于子任務(wù)數(shù)。粒子編碼長度等于子任務(wù)數(shù),假設(shè)N=M=10,粒子(2,3,5,1,10,8,6,9,7,4)即是一個(gè)可行的調(diào)度方案,見表1。

表1 M等于N時(shí)編碼示例

(2)計(jì)算單元數(shù)大于子任務(wù)數(shù)。粒子編碼長度等于計(jì)算單元的數(shù)目,編碼時(shí)首先添加M-N個(gè)虛擬子任務(wù),這些子任務(wù)在任意計(jì)算單元上的執(zhí)行時(shí)間均為0,它們與其他N個(gè)子任務(wù)間的通信量為0。假設(shè)M=10、N=6,粒子編碼示例見表2。

表2 M大于N時(shí)編碼示例

(3)計(jì)算單元數(shù)小于子任務(wù)數(shù)。首先采用線性聚簇的思想,將通信量大且能在同一個(gè)計(jì)算單元上執(zhí)行的子任務(wù)合并,直到合并后的子任務(wù)數(shù)等于計(jì)算單元數(shù)。對于ODAG,首先將所有子任務(wù)中相鄰的有通信關(guān)系且其對應(yīng)計(jì)算單元類型有交集的子任務(wù)按照通信量的大小排序,然后按照通信量,從大到小進(jìn)行合并,直到子任務(wù)數(shù)等于計(jì)算單元數(shù)。假設(shè)M=6、N=10,粒子編碼示例見表3。

表3 M小于N時(shí)編碼示例

通過以上處理,計(jì)算單元數(shù)等于子任務(wù)數(shù),編碼方式等同于第一種描述情況。

解碼方面,算法結(jié)束后,會得到一個(gè)最優(yōu)的計(jì)算單元序列,每個(gè)計(jì)算單元所在的位置序列即代表其需要執(zhí)行的子任務(wù)編號。對于計(jì)算單元數(shù)目大于子任務(wù)數(shù)的情況,由于虛擬子任務(wù)是不占用運(yùn)算資源和通信資源的,所以運(yùn)行虛擬子任務(wù)的計(jì)算單元實(shí)際是不被調(diào)用的;對于計(jì)算單元數(shù)小于子任務(wù)數(shù)的情況,計(jì)算單元的位置序列對應(yīng)的是合并后的子任務(wù)編號,只需將合并后的子任務(wù)編號與合并前的編號對應(yīng)起來,即可實(shí)現(xiàn)解碼操作。

由前面的問題模型可知,每個(gè)子任務(wù)在不同計(jì)算單元上的執(zhí)行時(shí)間是已知的,每個(gè)計(jì)算單元上任務(wù)運(yùn)行的時(shí)間為

(3)

式中:Ti,x表示子任務(wù)vi在第x個(gè)計(jì)算單元上的運(yùn)行時(shí)間;q表示分配到第x個(gè)計(jì)算單元上的子任務(wù)的數(shù)目。用k表示此次調(diào)度算法中可調(diào)用的計(jì)算單元的總數(shù)目,則任務(wù)總完成時(shí)間為

(4)

完成任務(wù)的總運(yùn)行成本為

(5)

假設(shè)分配到第x個(gè)計(jì)算單元上的任務(wù)集合為Vx,分配到第y個(gè)計(jì)算單元上的任務(wù)集合為Vy,則計(jì)算單元px與py之間的任務(wù)遷移成本為

(6)

整個(gè)任務(wù)的遷移成本為

(7)

拓?fù)渖?計(jì)算單元px與py的通信成本為

(8)

式中:Txy是px與py之間的通信總量;D(L(px),L(py))是px與py在拓?fù)渖系挠成湮恢弥g的曼哈頓距離。

2.2 初始化及適應(yīng)度函數(shù)

設(shè)種群規(guī)模為S、子任務(wù)數(shù)為N、計(jì)算單元的總數(shù)為M、計(jì)算單元種類數(shù)為m,則種群的初始化描述為:隨機(jī)產(chǎn)生S個(gè)粒子,第s個(gè)粒子的位置由向量xs=(xs1,xs2,…,xsn)表示,其中1≤s≤S,1≤n≤N,xsn(1≤xsn≤M)表示在第s個(gè)粒子中任務(wù)s被分配到第xsn個(gè)計(jì)算單元上運(yùn)行;粒子速度由向量vs=(vs1,vs2,…,vsn)表示,其中1≤s≤S,1≤n≤N,-M≤vsn≤M。時(shí)間的適應(yīng)度函數(shù)為

(9)

(10)

(11)

(12)

算法選擇總適應(yīng)度高的粒子,為進(jìn)化出下一代優(yōu)秀的粒子提供優(yōu)良基礎(chǔ)。α、β和δ為權(quán)重系數(shù),表示在粒子選擇時(shí)更側(cè)重于哪方面的性能。

2.3 位置及速度更新

(13)

(14)

式中:w用來控制粒子歷史速度對當(dāng)前速度的影響程度,對于平衡算法全局與局部搜索能力有很大作用。w較大時(shí)算法具有較強(qiáng)的全局搜索能力,w較小時(shí)算法有利于局部搜索,采用如下線性遞減慣性權(quán)重

w(g)=ws(ws-we)(G-g)/G

(15)

式中:ws、we分別為初始慣性權(quán)重和迭代至最大次數(shù)G時(shí)的慣性權(quán)重。w隨著迭代次數(shù)變化,使得算法在開始時(shí)搜索較大區(qū)域,較快地確定最優(yōu)解的大致位置,之后粒子速度減慢,開始細(xì)致的局部搜索,避免算法陷入局部最優(yōu)出現(xiàn)早熟現(xiàn)象,并在迭代后期仍然能夠保持較強(qiáng)的搜索能力,提高了算法性能。

2.4 算法流程

步驟1 按照上文描述,對粒子群位置和速度進(jìn)行隨機(jī)初始化;

步驟2 計(jì)算每個(gè)粒子的適應(yīng)度F,設(shè)置粒子的Bp和Ba;

步驟3 如果Bp和Ba在多次迭代中始終保持不變,或者算法達(dá)到最大迭代次數(shù),輸出最優(yōu)解,算法結(jié)束,否則轉(zhuǎn)至步驟4;

步驟4 對每個(gè)粒子根據(jù)式(13)、(14)更新粒子的速度和位置;

步驟5 轉(zhuǎn)至步驟3。

3 對比實(shí)驗(yàn)及分析

本文從兩方面對所設(shè)計(jì)的調(diào)度映射方案進(jìn)行對比和評價(jià),一是算法本身的執(zhí)行速度,通過對相同規(guī)模的任務(wù)分別按照遺傳算法(genetic algorithm,GA)、PSO算法及本文改進(jìn)的粒子群算法(optimized particle swarm optimization,oPSO)進(jìn)行運(yùn)算。這部分在Matlab2012b上完成,軟件環(huán)境是惠普的Z800工作站,CPU為Xeon E5530,主頻為2.4 GHz,內(nèi)存為8 GB,操作系統(tǒng)為64位Windows XP系統(tǒng),實(shí)驗(yàn)中所需不同規(guī)模的任務(wù)由任務(wù)產(chǎn)生工具(task graph for free, TGFF)[15]產(chǎn)生,粒子數(shù)S設(shè)置為100,迭代次數(shù)均為200次,群體最優(yōu)值的停滯代數(shù)設(shè)為5,α、β和δ均設(shè)置為1,加速因子c1=c2=2,不同任務(wù)規(guī)模下算法運(yùn)行時(shí)間t對比如圖1所示。

圖1 算法執(zhí)行時(shí)間對比

當(dāng)任務(wù)規(guī)模較小時(shí),oPSO相比PSO算法優(yōu)勢不大,運(yùn)行時(shí)間甚至?xí)源笥赑SO算法,這是因?yàn)閛PSO在進(jìn)行粒子更新操作時(shí)多了對權(quán)值w的更新計(jì)算,增加了運(yùn)算步驟和運(yùn)行時(shí)間,算法優(yōu)勢隨任務(wù)規(guī)模的擴(kuò)大逐漸明顯。我們統(tǒng)計(jì)了200次迭代中得到最優(yōu)解的次數(shù),GA算法是43次,PSO算法是69次,而oPSO算法能達(dá)到131次,運(yùn)算結(jié)果明顯優(yōu)于其他兩種算法。

對比不同映射結(jié)果在運(yùn)行過程中產(chǎn)生的包平均延時(shí)L和系統(tǒng)功耗W。實(shí)驗(yàn)運(yùn)行平臺參數(shù)同上,片上網(wǎng)絡(luò)拓?fù)洳捎贸Ｓ玫腗esh結(jié)構(gòu),路由算法使用XY路由算法,對比結(jié)果如圖2所示,當(dāng)任務(wù)規(guī)模較小時(shí),3種算法調(diào)度效果性能差異不大,隨著任務(wù)規(guī)模不斷擴(kuò)大(子任務(wù)數(shù)為100時(shí)),無論是包平均延時(shí)還是系統(tǒng)功耗,oPSO算法的調(diào)度效果都要明顯優(yōu)于其他兩種算法。

同時(shí),實(shí)驗(yàn)記錄了片上網(wǎng)絡(luò)上每個(gè)交換節(jié)點(diǎn)處的功率情況,圖3是節(jié)點(diǎn)規(guī)模為100的情況下,分別執(zhí)行3種算法時(shí)各個(gè)節(jié)點(diǎn)上的功率分布,可以看到,oPSO算法能將任務(wù)較為均衡地映射在整個(gè)系統(tǒng)上,不會出現(xiàn)過度繁忙或空閑的節(jié)點(diǎn)或區(qū)域,功耗較為均衡。

4 結(jié) 論

本文分析了片上網(wǎng)絡(luò)系統(tǒng)任務(wù)調(diào)度映射中的關(guān)鍵問題,設(shè)計(jì)了新任務(wù)模型,使其能夠更加真實(shí)地反映子任務(wù)間的制約關(guān)系;以單位時(shí)間運(yùn)行成本作為衡量標(biāo)準(zhǔn),算法調(diào)度結(jié)果更加高效、 實(shí)用;

調(diào)度目標(biāo)

A:時(shí)鐘周期(a)包平均延時(shí)對比

(b)系統(tǒng)功耗對比圖2 算法執(zhí)行效果對比

(a)GA算法節(jié)點(diǎn)功率分布

(b)PSO算法節(jié)點(diǎn)功率分布

(c)oPSO算法節(jié)點(diǎn)功率分布圖3 交換節(jié)點(diǎn)上的功率分布比較

不僅考慮任務(wù)總的完成時(shí)間,同時(shí)也考慮時(shí)間成本和資源成本,從而達(dá)到系統(tǒng)性能的綜合優(yōu)化;改進(jìn)了PSO算法,使其適于解決大規(guī)模任務(wù)調(diào)度問題,克服了算法前期搜素過快,容易出現(xiàn)早熟現(xiàn)象,后期搜索能力下降,易陷入局部最優(yōu)的缺點(diǎn)。

[1]ADDO-QUAYE C.Thermal-aware mapping and placement for 3-D NoC designs [C]∥Proceedings of the 2005 IEEE International SOC Conference.Piscataway, NJ, USA: IEEE, 2005: 25-28.

[2]SINGH A K, WU Jigang, PRAKASH A, et al.Mapping algorithms for NoC-based heterogeneous MPSoC platforms [C]∥Proceedings of the 12th Euromicro Conference on Digital System Design, Architectures, Methods and Tools.Piscataway, NJ, USA: IEEE, 2009: 133-140.

[3]TOPCUOGLU H, HARIRI S, WU Minyou.Performance-effective and low-complexity task scheduling for heterogeneous computing [J].IEEE Transactions on Parallel and Distributed Systems, 2002, 13(3): 260-274.

[4]DAOUD M I, KHARMA N.Efficient compile-time task scheduling for heterogeneous distributed computing systems [C]∥Proceedings of the 12th International Conference on Parallel and Distributed Systems.Piscataway, NJ, USA: IEEE Computer Society, 2006: 1-9.

[5]WU Minyou, GAJSKI D D.Hypertool: a programming aid for message-passing systems [J].IEEE Transactions on Parallel and Distributed Systems, 1990, 1(3): 330-343.

[6]CHUNG Y C, RANKA S.Applications and performance analysis of a compile-time optimization approach for list scheduling algorithms on distributed memory multiprocessors [C]∥Proceedings of the Supercomputing ’92.Piscataway, NJ, USA: IEEE, 1992: 512-521.

[7]ANMAD I, KWORK Y K.A new approach to scheduling parallel programs using task duplication [C]∥Proceedings of the International Conference on Parallel Processing.Piscataway, NJ, USA: IEEE, 1994: 47-51.

[8]SAYUTI M N S M, INDRUSIAK L S.Real-time low-power task mapping in networks-on-chip [C]∥Proceedings of the 2013 IEEE Computer Society Annual Symposium on VLSI.Piscataway, NJ, USA: IEEE, 2013: 14-19.

[9]FERRANDI F, LANZI P L, PILATO C, et al.Ant colony heuristic for mapping and scheduling tasks and communications on heterogeneous embedded systems [J].IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2010, 29(6): 911-924.

[10]SILVA L, NEDJAH N, MOURELLE L.ACO approach in static routing for network-on-chips with 3D mesh topology [C]∥Proceedings of the 2013 IEEE 4th Latin American Symposium on Circuits and Systems.Piscataway, NJ, USA: IEEE, 2013: 1-4.

[11]HOFFMANN R, RAUBE T.Dynamic task scheduling and load balancing on cell processors [C]∥Proceedings of the 2010 18th Euromicro International Conference on Parallel, Distributed and Network-Based Processing.Piscataway, NJ, USA: IEEE Computer Society, 2010: 205-212.

[12]SIDHU M S, THULASIRAMAN P.A load-rebalance PSO heuristic for task matching in heterogeneous computing systems [C]∥Proceedings of the 2013 IEEE Symposium on Swarm Intelligence.Piscataway, NJ, USA: IEEE, 2013: 180-187.

[13]AMOLD O, FETTWEIS G.Power aware heterogeneous MPSoC with dynamic task scheduling and increased data locality for multiple applications [C]∥Proceedings of the 2010 International Conference on Embedded Computer Systems.Piscataway, NJ, USA: IEEE, 2010: 110-117.

[14]YANG Pengfei, WANG Quan.Effective task scheduling and IP mapping algorithm for heterogeneous NoC-based MPSoC [J].Mathematical Problems in Engineering, 2014, 2014: 202748.

[15]DICK R P, RHODES D L, WOLF W.TGFF: task graphs for free [C]∥Proceedings of the 6th International Workshop on Hardware/Software Codesign.Piscataway, NJ, USA: IEEE Computer Society, 1998: 97-101.

(編輯 武紅江)

An Effective Scheduling and Mapping Algorithm of Tasks for Heterogeneous NoC-Based MPSoC

YANG Pengfei, WANG Quan

(School of Computer, Xidian University, Xi’an 710071, China)

A new task model is designed and an optimized particle swarm optimization (oPSO) algorithm is proposed to solve the problem that the traditional task DAG model contains less information and the existing task scheduling algorithms based on the model are of inefficiency.The new model adds the description of task type and some real inter-task relations such as transfer cost of the task, the type of processing element (PE) and its running cost.After the requirements of task scheduling and mapping are analyzed, a new scheme of coding and decoding is formulated, key parameters of the algorithm and their calculation are proposed, and the shortcomings of the particle swarm optimization algorithm such as poor local search capacity in the early period and being easily trapped into local optima in the late period of the algorithm are overcome.Simulations and comparisons with the GA and PSO algorithms under different IP scales show that when the number of IPs is about 100, the execution time and the power consumption of the oPSO algorithm reduce at least 10% and 15%, respectively, the scheduling effect of oPSO is much better than those of other algorithms, and the energy consumption on each IPs is balanced.Thus it can be concluded that the proposed algorithm is applicable for the solution of task scheduling.

multiprocessor system-on-chip; network on chip; task scheduling; IP mapping

2014-10-21。 作者簡介:楊鵬飛(1985—),男,博士生;王泉(通信作者),男,教授,博士生導(dǎo)師。 基金項(xiàng)目:國家自然科學(xué)基金資助項(xiàng)目(61474087)。

時(shí)間:2015-04-29

http:∥www.cnki.net/kcms/detail/61.1069.T.20150429.1437.002.html

10.7652/xjtuxb201506012

TN409

A

0253-987X(2015)06-0072-05