• <tr id="yyy80"></tr>
  • <sup id="yyy80"></sup>
  • <tfoot id="yyy80"><noscript id="yyy80"></noscript></tfoot>
  • 99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看 ?

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

    2015-12-27 02:15:25楊鵬飛王泉
    關(guān)鍵詞:任務(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ù)洳捎贸S玫腗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

    猜你喜歡
    任務(wù)調(diào)度編碼粒子
    基于SAR-SIFT和快速稀疏編碼的合成孔徑雷達(dá)圖像配準(zhǔn)
    《全元詩》未編碼疑難字考辨十五則
    子帶編碼在圖像壓縮編碼中的應(yīng)用
    電子制作(2019年22期)2020-01-14 03:16:24
    基于改進(jìn)NSGA-Ⅱ算法的協(xié)同制造任務(wù)調(diào)度研究
    基于時(shí)間負(fù)載均衡蟻群算法的云任務(wù)調(diào)度優(yōu)化
    Genome and healthcare
    基于粒子群優(yōu)化的橋式起重機(jī)模糊PID控制
    基于粒子群優(yōu)化極點(diǎn)配置的空燃比輸出反饋控制
    云計(jì)算環(huán)境中任務(wù)調(diào)度策略
    云計(jì)算中基于進(jìn)化算法的任務(wù)調(diào)度策略
    精品国产乱码久久久久久男人| 国产精品 国内视频| 欧美国产精品va在线观看不卡| a在线观看视频网站| 搡老岳熟女国产| netflix在线观看网站| 亚洲国产精品成人综合色| 亚洲中文字幕一区二区三区有码在线看 | 久久中文字幕人妻熟女| 欧美日本视频| 国产视频内射| 国产午夜精品久久久久久| 国产黄片美女视频| 午夜日韩欧美国产| 国产熟女午夜一区二区三区| АⅤ资源中文在线天堂| 亚洲熟女毛片儿| 午夜免费鲁丝| av在线播放免费不卡| 自线自在国产av| 亚洲一区二区三区色噜噜| 日韩欧美国产一区二区入口| 女人被狂操c到高潮| a在线观看视频网站| 19禁男女啪啪无遮挡网站| 99在线人妻在线中文字幕| 久久久精品欧美日韩精品| 日韩三级视频一区二区三区| 国产欧美日韩精品亚洲av| 久久热在线av| 欧美大码av| 黑人操中国人逼视频| 日本熟妇午夜| 黄色成人免费大全| 国产精品一区二区精品视频观看| 国产成人欧美| 成人国产一区最新在线观看| 国产精品久久久久久亚洲av鲁大| av欧美777| 天堂√8在线中文| 91av网站免费观看| 91国产中文字幕| bbb黄色大片| 成人亚洲精品av一区二区| 欧美久久黑人一区二区| 午夜日韩欧美国产| 国产99白浆流出| ponron亚洲| 午夜福利在线在线| 午夜福利高清视频| 国产午夜福利久久久久久| 日韩欧美 国产精品| 精品高清国产在线一区| 国产免费av片在线观看野外av| 久久中文字幕人妻熟女| 国产av又大| 可以免费在线观看a视频的电影网站| 国产激情偷乱视频一区二区| 50天的宝宝边吃奶边哭怎么回事| 亚洲自偷自拍图片 自拍| 搞女人的毛片| 国产精品99久久99久久久不卡| 女人爽到高潮嗷嗷叫在线视频| 熟女电影av网| 美女国产高潮福利片在线看| 不卡一级毛片| 美女午夜性视频免费| 久久国产精品男人的天堂亚洲| 1024香蕉在线观看| 国产私拍福利视频在线观看| 久久久水蜜桃国产精品网| 两个人视频免费观看高清| 国产成人av教育| 日韩欧美一区二区三区在线观看| 天天躁狠狠躁夜夜躁狠狠躁| 韩国精品一区二区三区| 午夜福利高清视频| 999久久久国产精品视频| 国产精品综合久久久久久久免费| 亚洲国产日韩欧美精品在线观看 | 一区二区三区精品91| 最近在线观看免费完整版| 欧美中文日本在线观看视频| 老司机午夜福利在线观看视频| 成人18禁高潮啪啪吃奶动态图| 免费一级毛片在线播放高清视频| 岛国在线观看网站| 亚洲国产高清在线一区二区三 | 亚洲成av片中文字幕在线观看| 国产亚洲精品第一综合不卡| 变态另类成人亚洲欧美熟女| 亚洲精品国产一区二区精华液| 精品日产1卡2卡| 亚洲第一欧美日韩一区二区三区| 夜夜夜夜夜久久久久| 亚洲五月天丁香| 一本一本综合久久| 一边摸一边抽搐一进一小说| 丝袜美腿诱惑在线| 亚洲精华国产精华精| 国产精华一区二区三区| 天堂√8在线中文| 国产欧美日韩精品亚洲av| 少妇粗大呻吟视频| 欧美日韩精品网址| 一本大道久久a久久精品| 搞女人的毛片| 熟妇人妻久久中文字幕3abv| 久久青草综合色| 日韩大尺度精品在线看网址| 最新在线观看一区二区三区| 三级毛片av免费| 成人亚洲精品av一区二区| 成人国语在线视频| 99热这里只有精品一区 | 欧美亚洲日本最大视频资源| 亚洲国产毛片av蜜桃av| 亚洲久久久国产精品| 宅男免费午夜| av欧美777| 亚洲精品美女久久久久99蜜臀| 亚洲成人国产一区在线观看| 国产精品二区激情视频| 亚洲 欧美 日韩 在线 免费| 亚洲一区二区三区不卡视频| 特大巨黑吊av在线直播 | 亚洲中文字幕一区二区三区有码在线看 | 日本免费一区二区三区高清不卡| 一级黄色大片毛片| 搡老熟女国产l中国老女人| 国产黄片美女视频| 午夜福利在线在线| 欧美日本亚洲视频在线播放| 婷婷六月久久综合丁香| 久久人人精品亚洲av| 丰满的人妻完整版| 亚洲在线自拍视频| 老司机深夜福利视频在线观看| 国产爱豆传媒在线观看 | 国语自产精品视频在线第100页| 欧美亚洲日本最大视频资源| 久久精品人妻少妇| 日韩欧美 国产精品| 国产av在哪里看| 午夜福利欧美成人| 啦啦啦免费观看视频1| 亚洲精品一区av在线观看| 亚洲熟女毛片儿| 美女国产高潮福利片在线看| 妹子高潮喷水视频| 国产精品影院久久| 男人舔女人下体高潮全视频| 亚洲成av片中文字幕在线观看| АⅤ资源中文在线天堂| 久久中文字幕人妻熟女| 51午夜福利影视在线观看| 精品国产乱码久久久久久男人| 久久天躁狠狠躁夜夜2o2o| 桃红色精品国产亚洲av| 日本一区二区免费在线视频| 久久这里只有精品19| 亚洲欧美激情综合另类| 精品欧美一区二区三区在线| 日韩欧美在线二视频| 欧美色欧美亚洲另类二区| 欧洲精品卡2卡3卡4卡5卡区| 国产激情久久老熟女| 观看免费一级毛片| netflix在线观看网站| 成人精品一区二区免费| 可以在线观看的亚洲视频| 最好的美女福利视频网| 国产私拍福利视频在线观看| 中国美女看黄片| 午夜成年电影在线免费观看| 色婷婷久久久亚洲欧美| 亚洲国产欧美日韩在线播放| 国产欧美日韩一区二区三| 一本久久中文字幕| 一卡2卡三卡四卡精品乱码亚洲| 欧美乱码精品一区二区三区| 一级黄色大片毛片| 免费看a级黄色片| 免费在线观看完整版高清| 亚洲国产精品成人综合色| 久久久精品国产亚洲av高清涩受| 亚洲欧美日韩高清在线视频| 日韩中文字幕欧美一区二区| 久久精品aⅴ一区二区三区四区| 久久久精品欧美日韩精品| 日韩高清综合在线| www国产在线视频色| 可以在线观看毛片的网站| 亚洲va日本ⅴa欧美va伊人久久| 日本黄色视频三级网站网址| 久久久久亚洲av毛片大全| av在线天堂中文字幕| 欧美乱妇无乱码| 亚洲免费av在线视频| 日韩大尺度精品在线看网址| 欧美精品亚洲一区二区| 动漫黄色视频在线观看| 一区福利在线观看| 亚洲无线在线观看| 欧美激情高清一区二区三区| 国产成人精品久久二区二区91| 精品欧美国产一区二区三| 99久久精品国产亚洲精品| 正在播放国产对白刺激| 国产精品电影一区二区三区| 中文字幕av电影在线播放| 精品久久久久久久人妻蜜臀av| 老司机深夜福利视频在线观看| 日本免费一区二区三区高清不卡| 午夜福利欧美成人| 亚洲性夜色夜夜综合| 黄片小视频在线播放| 久久中文字幕一级| or卡值多少钱| 最近最新中文字幕大全免费视频| 青草久久国产| 18禁黄网站禁片午夜丰满| 91麻豆av在线| 亚洲av电影不卡..在线观看| 亚洲专区字幕在线| 午夜a级毛片| 久久久久久久久久黄片| 亚洲精品国产精品久久久不卡| 成年人黄色毛片网站| 精品久久久久久久久久久久久 | 国产aⅴ精品一区二区三区波| 女人爽到高潮嗷嗷叫在线视频| 午夜福利18| 俄罗斯特黄特色一大片| 久久久国产成人精品二区| 国产亚洲精品av在线| 亚洲精品在线观看二区| 俄罗斯特黄特色一大片| 国产成人av教育| 精品国产国语对白av| 国产三级在线视频| 日本a在线网址| 美女扒开内裤让男人捅视频| 亚洲色图av天堂| 日韩欧美三级三区| 国产精品美女特级片免费视频播放器 | 欧美日韩精品网址| 亚洲精品在线美女| videosex国产| 欧美日韩亚洲国产一区二区在线观看| 精品卡一卡二卡四卡免费| 欧美黑人精品巨大| 国产欧美日韩一区二区精品| 波多野结衣巨乳人妻| 18禁黄网站禁片免费观看直播| 人成视频在线观看免费观看| 一卡2卡三卡四卡精品乱码亚洲| 免费在线观看视频国产中文字幕亚洲| 久久人人精品亚洲av| 日韩av在线大香蕉| 在线看三级毛片| 色综合欧美亚洲国产小说| 欧美日本视频| 亚洲国产毛片av蜜桃av| 亚洲国产欧洲综合997久久, | 一区福利在线观看| 极品教师在线免费播放| 国产熟女午夜一区二区三区| 精品久久久久久久人妻蜜臀av| 欧美又色又爽又黄视频| 久久人妻福利社区极品人妻图片| 熟女少妇亚洲综合色aaa.| 亚洲中文字幕日韩| 国产av不卡久久| 久99久视频精品免费| av电影中文网址| 国产精品香港三级国产av潘金莲| 亚洲精品久久国产高清桃花| 精品第一国产精品| 999久久久精品免费观看国产| 亚洲熟妇中文字幕五十中出| 国产麻豆成人av免费视频| 夜夜躁狠狠躁天天躁| 国产成+人综合+亚洲专区| 999久久久精品免费观看国产| 999久久久国产精品视频| 精品国产一区二区三区四区第35| 亚洲av美国av| 亚洲三区欧美一区| 成人一区二区视频在线观看| 午夜日韩欧美国产| 日韩精品中文字幕看吧| 搞女人的毛片| 亚洲午夜精品一区,二区,三区| 中文字幕精品免费在线观看视频| 9191精品国产免费久久| 99国产精品一区二区三区| 亚洲一区二区三区不卡视频| 精品久久久久久久人妻蜜臀av| 婷婷亚洲欧美| 人人妻,人人澡人人爽秒播| 久久久国产精品麻豆| 亚洲国产精品成人综合色| 99riav亚洲国产免费| 法律面前人人平等表现在哪些方面| 国产亚洲欧美精品永久| 欧美绝顶高潮抽搐喷水| 成人国产综合亚洲| 亚洲 国产 在线| 亚洲精品美女久久久久99蜜臀| 桃红色精品国产亚洲av| 在线av久久热| 久久精品国产综合久久久| 亚洲成人久久性| 两个人免费观看高清视频| 精品国产乱码久久久久久男人| 国产精品美女特级片免费视频播放器 | 老司机午夜十八禁免费视频| 日韩大尺度精品在线看网址| av天堂在线播放| 亚洲一码二码三码区别大吗| 色综合欧美亚洲国产小说| 亚洲专区国产一区二区| 午夜福利一区二区在线看| a级毛片在线看网站| 国产高清videossex| 日韩av在线大香蕉| 中文字幕人妻熟女乱码| 成人欧美大片| 男人舔奶头视频| 搡老妇女老女人老熟妇| 成年女人毛片免费观看观看9| 精品国产国语对白av| 91成人精品电影| 精品免费久久久久久久清纯| 久久人妻av系列| 18禁观看日本| 免费观看人在逋| 国产激情久久老熟女| 午夜两性在线视频| 露出奶头的视频| 人人妻人人澡人人看| 日韩欧美 国产精品| 国产成年人精品一区二区| 成人国语在线视频| 少妇 在线观看| 国产精品自产拍在线观看55亚洲| 九色国产91popny在线| 男男h啪啪无遮挡| 老熟妇仑乱视频hdxx| 国产精品自产拍在线观看55亚洲| 久99久视频精品免费| 久久伊人香网站| 欧美三级亚洲精品| 999久久久国产精品视频| 欧美一区二区精品小视频在线| 欧美日韩中文字幕国产精品一区二区三区| 亚洲成av人片免费观看| 黄色片一级片一级黄色片| 国产伦一二天堂av在线观看| 欧美黑人精品巨大| 欧美乱妇无乱码| 真人做人爱边吃奶动态| av中文乱码字幕在线| 亚洲av第一区精品v没综合| 日本一本二区三区精品| 此物有八面人人有两片| www.999成人在线观看| 人人妻人人澡人人看| 欧美性长视频在线观看| 亚洲精品美女久久av网站| 少妇的丰满在线观看| 免费无遮挡裸体视频| 19禁男女啪啪无遮挡网站| 夜夜夜夜夜久久久久| 欧美不卡视频在线免费观看 | 国产午夜福利久久久久久| 国产精品久久久人人做人人爽| 久久精品成人免费网站| 最新美女视频免费是黄的| 亚洲精品国产区一区二| АⅤ资源中文在线天堂| bbb黄色大片| 一本综合久久免费| 色综合亚洲欧美另类图片| 午夜激情福利司机影院| 天天一区二区日本电影三级| 十八禁网站免费在线| 精品久久久久久成人av| 一级a爱视频在线免费观看| 国产又色又爽无遮挡免费看| 青草久久国产| 欧美最黄视频在线播放免费| 午夜免费成人在线视频| 十八禁人妻一区二区| 欧美日本视频| 在线免费观看的www视频| 最新在线观看一区二区三区| 一级黄色大片毛片| 久久久精品欧美日韩精品| 国产人伦9x9x在线观看| www.自偷自拍.com| 欧美zozozo另类| 精品久久久久久久久久免费视频| 亚洲国产毛片av蜜桃av| 俺也久久电影网| 亚洲av片天天在线观看| 久久精品夜夜夜夜夜久久蜜豆 | 国内揄拍国产精品人妻在线 | 老司机午夜福利在线观看视频| 在线十欧美十亚洲十日本专区| 国产av一区二区精品久久| 在线观看日韩欧美| 99久久国产精品久久久| 麻豆一二三区av精品| 国产精品香港三级国产av潘金莲| 1024视频免费在线观看| 好看av亚洲va欧美ⅴa在| 免费电影在线观看免费观看| 免费在线观看成人毛片| 亚洲av成人一区二区三| 久久精品国产清高在天天线| 欧美黄色淫秽网站| 夜夜看夜夜爽夜夜摸| 叶爱在线成人免费视频播放| 我的亚洲天堂| 91麻豆精品激情在线观看国产| 精品午夜福利视频在线观看一区| 人人妻人人澡欧美一区二区| 国产成人av教育| 91在线观看av| 99在线人妻在线中文字幕| 久9热在线精品视频| 大香蕉久久成人网| 香蕉久久夜色| 久久精品国产清高在天天线| 久久精品成人免费网站| 亚洲av中文字字幕乱码综合 | 岛国视频午夜一区免费看| 亚洲av熟女| 中文在线观看免费www的网站 | 国产一区二区三区视频了| 亚洲aⅴ乱码一区二区在线播放 | 国产精品 欧美亚洲| 国产一区二区三区视频了| 免费女性裸体啪啪无遮挡网站| 人人澡人人妻人| 久久久久国内视频| 人妻丰满熟妇av一区二区三区| 日韩精品免费视频一区二区三区| 欧美色视频一区免费| 国产亚洲精品av在线| 欧美午夜高清在线| 免费在线观看黄色视频的| 久久国产精品影院| 91av网站免费观看| 欧美中文日本在线观看视频| 国产99白浆流出| 视频区欧美日本亚洲| 午夜成年电影在线免费观看| 精品电影一区二区在线| 夜夜爽天天搞| 亚洲av片天天在线观看| 他把我摸到了高潮在线观看| av福利片在线| 亚洲午夜精品一区,二区,三区| 啦啦啦 在线观看视频| 久久久久国产一级毛片高清牌| 老熟妇仑乱视频hdxx| 日韩高清综合在线| 国产伦在线观看视频一区| 国产一区二区在线av高清观看| 一卡2卡三卡四卡精品乱码亚洲| 999精品在线视频| 久久久久国内视频| 日本熟妇午夜| 十八禁网站免费在线| 一卡2卡三卡四卡精品乱码亚洲| 12—13女人毛片做爰片一| 午夜免费激情av| 熟妇人妻久久中文字幕3abv| 亚洲国产欧洲综合997久久, | 村上凉子中文字幕在线| 久久精品成人免费网站| 亚洲国产精品合色在线| 99国产综合亚洲精品| 真人做人爱边吃奶动态| 国产欧美日韩精品亚洲av| 制服人妻中文乱码| 国产私拍福利视频在线观看| 亚洲男人的天堂狠狠| 此物有八面人人有两片| 1024手机看黄色片| 婷婷亚洲欧美| 日韩欧美免费精品| 国产成人精品久久二区二区免费| 亚洲精品美女久久av网站| 99精品在免费线老司机午夜| 亚洲国产欧洲综合997久久, | www日本黄色视频网| 成人国语在线视频| 丝袜在线中文字幕| 免费av毛片视频| 在线观看日韩欧美| av天堂在线播放| 精品一区二区三区四区五区乱码| 97人妻精品一区二区三区麻豆 | 成年免费大片在线观看| 亚洲精品国产区一区二| 免费在线观看黄色视频的| 人人妻,人人澡人人爽秒播| 老司机午夜福利在线观看视频| 久热这里只有精品99| 国产又黄又爽又无遮挡在线| 黄色女人牲交| 久久久久精品国产欧美久久久| 国产精品,欧美在线| xxx96com| 天堂√8在线中文| 国产精品野战在线观看| 亚洲性夜色夜夜综合| 久久精品亚洲精品国产色婷小说| 性色av乱码一区二区三区2| 欧美绝顶高潮抽搐喷水| 日韩视频一区二区在线观看| 亚洲中文日韩欧美视频| 亚洲狠狠婷婷综合久久图片| 午夜日韩欧美国产| av天堂在线播放| 国产真实乱freesex| 免费在线观看影片大全网站| 可以在线观看的亚洲视频| 成人av一区二区三区在线看| 国产av又大| 久久久久久九九精品二区国产 | 国产v大片淫在线免费观看| 午夜福利欧美成人| www.精华液| 欧美午夜高清在线| 精品一区二区三区av网在线观看| 99精品欧美一区二区三区四区| 观看免费一级毛片| www.999成人在线观看| 日日摸夜夜添夜夜添小说| 女性生殖器流出的白浆| 亚洲国产欧美网| 亚洲狠狠婷婷综合久久图片| 欧美 亚洲 国产 日韩一| 国产高清有码在线观看视频 | 午夜日韩欧美国产| 丝袜美腿诱惑在线| 欧美乱色亚洲激情| 日韩av在线大香蕉| www日本在线高清视频| 亚洲aⅴ乱码一区二区在线播放 | 999久久久国产精品视频| 两人在一起打扑克的视频| 日韩欧美一区视频在线观看| 亚洲av中文字字幕乱码综合 | 欧美+亚洲+日韩+国产| 99热这里只有精品一区 | 亚洲精品在线观看二区| 最新美女视频免费是黄的| 中文字幕另类日韩欧美亚洲嫩草| 麻豆久久精品国产亚洲av| 欧美日韩亚洲国产一区二区在线观看| 女生性感内裤真人,穿戴方法视频| 熟妇人妻久久中文字幕3abv| 亚洲一卡2卡3卡4卡5卡精品中文| 国产一区在线观看成人免费| 真人做人爱边吃奶动态| 在线观看午夜福利视频| 午夜影院日韩av| 高潮久久久久久久久久久不卡| 久久久久久久精品吃奶| 亚洲av成人不卡在线观看播放网| 国产又黄又爽又无遮挡在线| 久久久国产精品麻豆| 国产精品乱码一区二三区的特点| 久久亚洲真实| 999久久久精品免费观看国产| 精品国产一区二区三区四区第35| 免费在线观看亚洲国产| 亚洲自拍偷在线| 人妻久久中文字幕网| 久久精品国产亚洲av香蕉五月| 法律面前人人平等表现在哪些方面| 久久99热这里只有精品18| 黑人欧美特级aaaaaa片| 国产一卡二卡三卡精品| 精品第一国产精品| 久久中文看片网| 久久草成人影院| 欧美午夜高清在线| 免费一级毛片在线播放高清视频| 少妇被粗大的猛进出69影院| 欧美另类亚洲清纯唯美| 久久久久久久久久黄片| 男女那种视频在线观看| 精华霜和精华液先用哪个| 性欧美人与动物交配| 巨乳人妻的诱惑在线观看| 国产区一区二久久| 无遮挡黄片免费观看| www.熟女人妻精品国产| 国产蜜桃级精品一区二区三区| 成人18禁在线播放| 免费av毛片视频| 亚洲欧美日韩高清在线视频| 免费高清视频大片| 啦啦啦韩国在线观看视频| 琪琪午夜伦伦电影理论片6080| 久久 成人 亚洲| 亚洲九九香蕉| 亚洲精品一卡2卡三卡4卡5卡|