異構(gòu)MPSoC下基于貪心和模擬退火算法的軟硬件劃分方法研究.pdf

1、異構(gòu)MPSoC集成了不同類(lèi)型的處理器內(nèi)核的優(yōu)點(diǎn)，被認(rèn)為是高性能嵌入式計(jì)算平臺(tái)未來(lái)的發(fā)展趨勢(shì)。此種架構(gòu)的嵌入式系統(tǒng)的設(shè)計(jì)包含了硬件設(shè)計(jì)和軟件設(shè)計(jì)兩個(gè)方面的內(nèi)容，當(dāng)前比較流行的設(shè)計(jì)方法是對(duì)軟件和硬件同時(shí)進(jìn)行設(shè)計(jì)，即軟硬件協(xié)同設(shè)計(jì)。相關(guān)研究表明，任務(wù)的軟硬件劃分是軟硬件協(xié)同設(shè)計(jì)過(guò)程中最為關(guān)鍵的一步，對(duì)軟硬件劃分問(wèn)題的研究已成為國(guó)內(nèi)外研究的熱點(diǎn)。因此，如何設(shè)計(jì)高性能的軟硬件劃分算法受到了研究者的廣泛關(guān)注。
　　 在軟硬件劃分算法的研究中

2、，常用貪心算法和模擬退火算法來(lái)對(duì)解空間進(jìn)行尋優(yōu)。貪心算法具有較低的計(jì)算復(fù)雜度，但只能獲得局部最優(yōu)解。模擬退火算法在理論上可以搜索到全局最優(yōu)解，但算法的收斂速度相對(duì)較慢。本文針對(duì)雙路軟硬件劃分系統(tǒng)模型的特點(diǎn)，借鑒求解0-1背包問(wèn)題的相關(guān)算法思想，基于模擬退火算法的全局尋優(yōu)特性，研究一種融合貪心算法和模擬退火算法的軟硬件劃分方法，用以提高在硬件資源約束下的算法收斂速度和解質(zhì)量。具體工作如下:
　　 針對(duì)傳統(tǒng)的基于貪心算法的預(yù)劃分算法

3、忽略通信代價(jià)，導(dǎo)致預(yù)劃分后得到的解的質(zhì)量不高的問(wèn)題，本文在分析了通信代價(jià)對(duì)軟硬件劃分結(jié)果的影響的基礎(chǔ)上，結(jié)合0-1背包問(wèn)題的解決方法，提出了一種改進(jìn)的基于貪心算法的預(yù)劃分算法。首先基于傳統(tǒng)預(yù)劃分算法得到一個(gè)初始解;然后把通信代價(jià)引入軟硬件劃分系統(tǒng)模型中，在此初始解的基礎(chǔ)上，利用價(jià)值變化量與空間變化量的比值，對(duì)背包內(nèi)外的物品再一次進(jìn)行取舍。對(duì)算法復(fù)雜度的分析表明，該算法在不提高計(jì)算復(fù)雜度的情況下，得到了更好的預(yù)劃分效果。
　　 針

4、對(duì)模擬退火算法在進(jìn)行全局尋優(yōu)時(shí)收斂速度較慢的問(wèn)題，本文對(duì)模擬退火算法的算法收斂條件進(jìn)行分析，并結(jié)合模擬退火算法計(jì)算復(fù)雜度主要由內(nèi)外兩層循環(huán)構(gòu)成的特點(diǎn)，提出了一種基于改進(jìn)的模擬退火算法的全局尋優(yōu)算法。首先對(duì)算法的擾動(dòng)模型進(jìn)行改進(jìn)，改進(jìn)后的模型增大了擾動(dòng)距離取2和3的概率，減少了內(nèi)層循環(huán)的計(jì)算復(fù)雜度;然后設(shè)計(jì)了一種新的代價(jià)函數(shù)，提高了算法對(duì)解空間的搜索效率，使得算法可以盡快找到最優(yōu)解，有效減少了外層循環(huán)次數(shù)。
　　 為了驗(yàn)證上述算法