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

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

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

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

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