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

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

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