基于關(guān)鍵任務(wù)的容錯(cuò)片上網(wǎng)絡(luò)映射算法研究.pdf

1、NoC映射算法是片上網(wǎng)絡(luò)研究的熱點(diǎn)內(nèi)容。目前，半導(dǎo)體工藝特征尺寸的降低以及芯片集成度的提高不斷推動(dòng)著NoC的復(fù)雜度和性能的提升，同時(shí)對(duì)NoC的可靠性映射帶來了更大的考驗(yàn)和挑戰(zhàn)。為了保障應(yīng)用程序映射的可靠性，NoC容錯(cuò)技術(shù)成為NoC研究中的一個(gè)重要方面。本文提出了一個(gè)基于關(guān)鍵任務(wù)的容錯(cuò)片上網(wǎng)絡(luò)映射算法FTMA-CTs，該算法不僅能夠提高映射過程可靠性，而且還能降低系統(tǒng)總能耗。
　　FTMA-CTs映射算法將映射過程分為虛擬拓?fù)涞轿锢?/p>

2、拓?fù)涞挠成潆A段和任務(wù)圖到虛擬拓?fù)涞挠成潆A段。其中，在虛擬拓?fù)涞轿锢硗負(fù)涞挠成潆A段，本文采用了匈牙利算法來解決虛擬核到物理核的一對(duì)一映射問題。在任務(wù)圖到虛擬拓?fù)涞挠成潆A段，首先把基于節(jié)點(diǎn)的任務(wù)圖轉(zhuǎn)化為基于節(jié)點(diǎn)和邊的加強(qiáng)型任務(wù)圖，然后根據(jù)路徑延時(shí)和系統(tǒng)延時(shí)，找到任務(wù)圖中的關(guān)鍵路徑，進(jìn)一步找到關(guān)鍵任務(wù)。再把帶有關(guān)鍵任務(wù)的任務(wù)圖進(jìn)行分簇，本文采用親密度傳播聚類算法進(jìn)行分簇。在把分簇之后的任務(wù)圖映射到虛擬拓?fù)涞倪^程中，采用改進(jìn)的分支限界算法，該算

3、法在原有的分支限界算法的基礎(chǔ)上增加兩個(gè)界限，通過這兩個(gè)界限繼續(xù)對(duì)分支樹進(jìn)行剪枝，從而進(jìn)一步減少可行解的數(shù)目，最終利用這種改進(jìn)的分支限界算法能夠高效快速的得出一個(gè)較優(yōu)的映射方案。
　　最后，對(duì)Nirgam仿真器進(jìn)行改造，進(jìn)行能耗的仿真評(píng)估。通過與Zhang等人提出的退火法和Yue等人提出的基于冗余核的貪婪算法進(jìn)行比較，分析FTMA-CTs映射算法的性能。結(jié)果證明FTMA-CTs映射算法不僅能夠提高應(yīng)用程序映射的可靠性，而且還能降低尋