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

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

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

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