【摘要】：隨著科技的發(fā)展與新技術(shù)的出現(xiàn),多處理器片上系統(tǒng)(MPSoC)現(xiàn)在越來越多地被用于設(shè)計新興的復(fù)雜嵌入式系統(tǒng)。設(shè)計人員需要在考慮各種因素的情況下將處理器上的任務(wù)以合理的調(diào)度順序分配給相應(yīng)的處理器進行處理來滿足時間以及計算資源和能源資源的限制要求,在提高企業(yè)經(jīng)濟效益的同時節(jié)約開發(fā)成本。眾所周知,由于處理器單位時間內(nèi)的能量消耗和處理器的處理速度正相關(guān),導(dǎo)致時間成本和能源消耗成為兩個相互沖突目標(biāo),我們需要盡可能同時優(yōu)化這兩個目標(biāo)。目前,多目標(biāo)優(yōu)化問題受到各界研究人員的廣泛關(guān)注。任務(wù)的映射和調(diào)度逐漸成為研究人員關(guān)注的重要問題之一。為了滿足資源匱乏情況下MPSoC系統(tǒng)中完成時間最小化(makespan)和負載(workload)盡可能平衡的要求,本文提出了一個統(tǒng)一的整數(shù)規(guī)劃模型來找到滿足條件的任務(wù)調(diào)度和映射的解決方案。該模型考慮了計算和通信成本,并且能夠應(yīng)用動態(tài)電源管理DPM(dynamic power management)進行能源優(yōu)化。為了盡可能有效逼近最優(yōu)化問題的帕累托(Pareto)前沿,我們通過對問題進行特定的初始化并集成Pareto局部搜索到多目標(biāo)進化算法過程中,提出了一種基于進化算法的多目標(biāo)混合算法(MOHA)。進化算法引用優(yōu)勝劣汰原理,通過模擬生物進化過程中的基因表達過程,選擇優(yōu)秀的基因片段(目標(biāo)值更優(yōu)),過濾掉劣質(zhì)的基因片段(目標(biāo)值較劣),最終得到近似最優(yōu)解。局部搜索則是解決最優(yōu)化問題的一種啟發(fā)式算法,由于多目標(biāo)芯片調(diào)度問題是一個NP-hard問題,完備算法的時間復(fù)雜度往往不能滿足現(xiàn)實生活中的要求,而局部搜索是一種近似算法,它采用時間換精度的思想大大減少算法搜索到無窮接近最優(yōu)解所需要的時間。在最后的實驗階段,本文選擇了現(xiàn)實工業(yè)界中幾個經(jīng)典的基準(zhǔn)樣例對算法進行性能評估和比較實驗。在多個基準(zhǔn)樣例的測試結(jié)果中表明,該算法比傳統(tǒng)的NSGA-Ⅱ算法更優(yōu)秀。
【學(xué)位授予單位】：東北師范大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2018
【分類號】：TP18;TN47
【圖文】：

有限的任務(wù)集合，T→N 代表每個任務(wù)要完成的工作量，E T×T 用一組 c 值代表一組優(yōu)先關(guān)系，E→N 代表每一組任務(wù)之間需要傳送的數(shù)據(jù)量。如果一組任務(wù)之間沒有明確定義的傳送數(shù)據(jù)量，那么它們的通信消費為 0。如圖 3-1（a）所示，一共有四個任務(wù)，每一個都被記錄所需要完成的工作量。四個任務(wù)分別需要完成的工作量是 2，6，8，4。有三條邊表明了需要傳輸數(shù)據(jù)的數(shù)據(jù)量，如圖所示，任務(wù) 2 需要任務(wù) 1 傳輸?shù)臄?shù)據(jù)，數(shù)據(jù)量為 3，并且它的執(zhí)行依賴任務(wù) 1。同理，任務(wù) 2 是任務(wù) 4 的前置任務(wù)，他們之間需要傳輸?shù)臄?shù)據(jù)量為 1，任務(wù) 3 是任務(wù) 4的前置任務(wù)，需要傳輸?shù)臄?shù)據(jù)量為 5。由其下兩個映射可以看出，第一個映射中工作負載是均衡的，它的完工時間在第一次迭代和第二次迭代過程中分別是 20和 30。另外一個映射在工作負載不均衡的情況下，完工時間在第一次迭代和第二次迭代過程中分別是 12 和 24。

和最小的工作量，有：= （21）工作量距離越小，在極端的情況下的差異較小，相比于工作距離大的配置更優(yōu)秀。 在上面的例子中，我們有 = 6和 = 7。所以第一種配置比第二種優(yōu)秀。3.3 多目標(biāo)混合算法為了獲得大規(guī)模系統(tǒng)的帕累托最優(yōu)前沿解集，我們基于 NSGA-II 算法結(jié)合局部搜索算法提出了多目標(biāo)混合算法（MOHA），在初始化和演化過程中具有與目標(biāo)相關(guān)啟發(fā)式擴展。圖 3-2(a)顯示了映射和調(diào)度問題的染色體編碼。每個染色體都包含一組映射任務(wù)和分配的處理器的計劃執(zhí)行順序，這些順序與一般用于映射優(yōu)化的常規(guī)編碼不同。因此，我們需要額外的指針來分離屬于各個處理器的任務(wù)。

【參考文獻】

相關(guān)期刊論文 前2條

1 張福威;李軍;孟品超;姜志俠;李延忠;;多目標(biāo)進化算法綜述[J];長春理工大學(xué)學(xué)報(自然科學(xué)版);2012年03期

2 公茂果;焦李成;楊咚咚;馬文萍;;進化多目標(biāo)優(yōu)化算法研究[J];軟件學(xué)報;2009年02期

本文編號：2719520