映射和路徑分配是片上網(wǎng)絡(luò)在編譯過程中兩個相輔相成的重要步驟，對系統(tǒng)的通信功耗影響很大。該文針對片上網(wǎng)絡(luò)映射過程中現(xiàn)有路徑分配法尋徑不充分的問題，提出了一種基于列舉的路徑分配算法。該算法通過列舉各通信流的所有合法路徑，對路徑的各種組合方式進(jìn)行充分搜索。同時將路徑分配算法應(yīng)用到禁忌搜索映射算法中，并對映射算法做了改進(jìn)，以適應(yīng)路徑分配算法。仿真結(jié)果表明，基于列舉的路徑分配算法提高了滿足約束的路徑被搜索到的概率，優(yōu)化了映射算法的結(jié)果。
關(guān) 鍵 詞 映射; 片上網(wǎng)絡(luò); 路徑分配; 禁忌搜索

Two important steps, namely mapping and path allocation, are tightly bounded with each other in current network on chip (NoC) compiler technology, and have a large impact on the power consumed during communication. A novel algorithm is proposed for path allocation based on an enumerations scheme which enumerates legal paths of traffic, to search the routing paths combination in the NoC mapping process. The proposed algorithm is embedded to a tabu search mapping algorithm which is modified to adapt the behavior of path allocation. The simulation results show that the probability of finding the correct paths is increased within the bandwidth constraints and the mapping algorithm is optimized.
Key words mapping; network on chip; path allocation; tabu search

規(guī)則二維網(wǎng)孔結(jié)構(gòu)的片上網(wǎng)絡(luò)[1-2] (networks on chip，NoC)以其拓?fù)渑帕幸?guī)整、易于布局布線的優(yōu)勢成為NoC研究領(lǐng)域中比較常用的一種結(jié)構(gòu)。開發(fā)這種結(jié)構(gòu)的NoC，需要把應(yīng)用任務(wù)分配給適合的IP，然后把IP映射到塊中，并為IP之間的通信流分配路徑。如果一段連線分配了過多的通信量，將會引起嚴(yán)重的擁塞，造成實時系統(tǒng)的任務(wù)無法在時限內(nèi)完成。因此，需要把路徑分配嵌入到映射過程中綜合考慮。
現(xiàn)有的映射算法在路徑分配時大部分采用XY路由，如文獻(xiàn)[3]的分支限界算法、文獻(xiàn)[4]的兩步遺傳算法、文獻(xiàn)[5]的NMAP算法等，但XY路由在實際問題中常會出現(xiàn)熱點附近通信擁塞的情況。文獻(xiàn)[6]采用了多條路徑來降低系統(tǒng)的帶寬要求，但數(shù)據(jù)包到達(dá)目的節(jié)點后需要進(jìn)行復(fù)雜的包排序操作。文獻(xiàn)[7]使用的路徑分配算法，使路徑分配過程既有靈活性，又不需增加額外資源，但該算法存在路徑搜索不充分的問題。本文在文獻(xiàn)[7]的路徑分配算法基礎(chǔ)上提出了一種基于列舉的路徑分配方法，能夠?qū)β窂竭M(jìn)行充分搜索。本文還將該路徑分配算法應(yīng)用到禁忌搜索映射算法中，并針對該路徑分配算法對禁忌搜索映射算法做了部分修改，以提高性能時間比。
1 映射和路徑分配問題描述
1.1 映射
映射就是把IP和拓?fù)渲械膲K一一對應(yīng)，同時要滿足某些限制，如帶寬限制。映射的優(yōu)化程度由通信功耗衡量。