文獻標識碼： A
DOI：10.16157/j.issn.0258-7998.2016.08.030
中文引用格式： 金世燕，姚遠程，秦明偉. 基于通信鏈路的NoC映射算法[J].電子技術應用，2016，42(8)：121-124.
英文引用格式： Jin Shiyan，Yao Yuancheng，Qin Mingwei. An NoC mapping algorithm based on communication links[J].Application of Electronic Technique，2016，42(8)：121-124.
0 引言
隨著單芯片上集成的IP核數量不斷增加，傳統總線的通信方式已經不能滿足通信的需求，在功耗、可靠性及延遲等方面都面臨著非常嚴峻的挑戰[1]。在這種情況下，新型芯片體系架構就成為亟待研究的方向。新型芯片體系架構片上網絡（Network on Chip，NoC）[2-3]就在這樣的背景下應運而生。通過借鑒計算機網絡技術，引入新的體系結構，從根本上克服了片上系統（System on Chip，SoC）總線架構的種種弊端。總體說來，影響NoC性能的因素主要包括網絡拓撲結構、路由算法以及應用映射等。本文主要研究NoC的應用映射問題，以減少系統的能量及延時消耗，提高系統性能。
目前，很多文獻對NoC映射算法進行了研究，例如，TOSUN S提出了一種映射優化算法[4]，該算法將通信頻繁的任務映射到物理位置接近的網絡節點中，以減少數據包傳輸的距離，但該算法容易陷入局部最優，而難以得到最優解。陳亦鷗等人針對面向實時復雜系統的片上網絡架構及映射技術展開研究[5]，提出了面向實時復雜系統的NoC多目標映射模型。文獻[6]采用了分支定界法實現NoC的映射。文獻[7]提出一個均衡優化時延模型和一種基于Boltzmann-NSGAⅡ的映射算法，時延模型從宏觀鏈路負載和單個節點排隊時延進行優化，避免了傳統NSGAⅡ算法在解決NoC映射問題時容易出現局部最優和種群多樣性的問題。文獻[8]采用多目標自適應免疫算法對NoC映射問題進行研究，旨在減少系統延時和能量消耗。文獻[9]采用多目標免疫算法作為NoC映射算法，有效降低了系統功耗，提高了可靠性。文獻[10]以互連任務之間的通信量作為映射順序優先級的判定標準，提出一種啟發式算法，通信量大的任務先被映射到NoC拓撲中，接著將與已映射任務之間有通信的任務按照通信量大小依次映射至網絡拓撲中，直到應用程序中的所有任務都完成映射為止。由于算法每一次迭代都考慮了已映射任務所有鄰節點的情況，使得算法復雜度極高，達到了O（n5logn），n為任務數量。
本文在文獻[10]的基礎上，提出一種基于通信鏈路的改進映射算法（Improved Mapping Algorithms based on Communication Links，IMACL），IMACL算法通過將通信量較大的任務映射到網絡跳數較近的NoC核上，達到減少系統能耗和延時的目的。但與文獻[10]中的算法不同，IMACL算法不采用逐個搜索的映射方式，而是通過改進的多目標遺傳算法完成映射。實驗通過NoC仿真平臺NIRGAM進行，結果表明，該算法在能耗和延時方面具有較好的優化效果，并降低了算法復雜度，提高了算法收斂速度。
1 映射問題分析
NoC映射的目的是在滿足約束條件（能量、延時最小）的情況下，將給定的任務分配到NoC處理核上。該過程中使用的一些名詞定義如下：
定義1：任務通信圖(Task Communication Graph，TCG)，圖G(T，E)中，ti∈T代表應用中的任務，ei，j∈E代表任務ti與任務tj之間的通信量。實際應用VOPD對應的任務圖如圖1所示。
圖1 VOPD任務圖
定義2：拓撲圖(Topology Graph，TG)，圖T(P，L)中，pi∈P代表網絡拓撲中的處理核，li，j∈L代表核pi與核pj之間的通信鏈路。一個4×4 Mesh結構的拓撲如圖2所示。
圖2 4×4拓撲圖
在本文中，優化目標為系統能耗和延時，采用TERRY T Y在文獻[11]中提出的能量建模方式：
其中，Ebit表示相鄰路由器之間傳輸1 bit數據消耗的能量，ESbit、EBbit、EWbit和ELbit分別代表被處理核消耗的能量、緩存消耗的能量、線路和數據在鏈路中傳輸消耗的能量。網絡較大時，EBbit和EWbit可以忽略，因此能耗模型可表示為：
其中，
代表從pi傳輸1 bit數據到pj的能量消耗，ni，j表示從節點pi到節點pj的最短路徑的路由跳數(曼哈頓距離)。因此，網絡總的能量消耗由式(3)計算：
其中，vi，j表示節點pi與pj之間的通信量。
延時(D)為系統關鍵路徑(從輸入到輸出的最長鏈路)延時，其計算式為：
其中，di，j和qi，j分別表示從節點pi到節點pj的數據傳輸延時和等待延時。
映射過程中，將能耗和延時作為兩個優化目標，即目標函數為：
2 IMACL算法
IMACL算法將TCG中的任務映射到TG處理核上，算法實現過程中，遵循任務與處理核一一對應的原則。IMACL算法的主要思想是將相互之間通信量大的任務映射至路由跳數少的處理核上，以此降低系統的通信能耗和延時。算法以多目標遺傳算法為原型，但避免了傳統的多目標遺傳算法存在的收斂速度慢、易陷入局部最優等缺陷， IMACL算法流程圖如圖3所示。
圖3 IMACL算法流程圖
2.1 種群初始化
遺傳算法的基本單元為染色體，一條染色體代表一種映射方案，傳統的遺傳算法初始種群都是隨機產生一個染色體組，而初始種群的優劣直接影響算法的收斂速度，隨機產生的初始種群可能導致算法收斂過慢。因此，IMACL算法初始種群中的染色體按照通信鏈路的通信量大小來產生，描述如下：
(1)對TCG中的通信鏈路按照通信量進行排序，找到通信量最大的通信鏈路e=(ti，tj)，圖1中通信量最大的通信鏈路e=(t8，t10)；
(2)分別計算任務ti和tj總的通信量，即與任務節點相鄰的通信鏈路通信量的總和，比較任務ti和tj的總通信量，較大的任務即為第一個將被映射的任務，圖1中通信總量較大的任務為t8；
(3)產生一個1~M（處理核對應的編號）之間的隨機數p1，將任務ti和tj中總通信量較大的任務（圖1中為t8）映射至該處理核；
(4)接下來將最大通信量對應鏈路(e=(t8，t10))另一端的任務(圖1中為t10)映射至與p1相鄰的處理核p2上，p2為p1任意一個相鄰位置的處理核；
(5)找出剩余任務與已映射任務之間通信量最大的任務，將該任務映射至與已經映射的任務對應的處理核任意一個相鄰的處理核上；
(6)如果所有任務都映射完成，則得到了一條可用的染色體，否則返回步驟(5)。設種群大小為N。
2.2 遺傳操作
傳統的多目標遺傳算法產生子種群需要進行選擇、交叉和變異3個遺傳操作，但IMACL算法僅僅通過選擇、變異來獲取子種群。其中選擇操作目的是保持種群中的優良基因，而變異操作可以增加種群的多樣性，但同時也存在使種群產生退化的危險，為了保持種群質量和多樣性，IMACL算法讓部分個體參與變異，減小種群退化的概率，具體實現步驟如下：
(1)計算初始種群的目標函數，對計算結果進行非支配排序；
(2)將排在后50%的個體按變異概率pm（為了避免算法陷入局部最優，變異概率相對傳統遺傳操作而言取值較大）進行變異操作。隨機產生一個變異位置，保持染色體變異位置之前的基因不變，按2.1節中的方式找到下一個待映射的任務tnext，將任務tnext映射至新產生的處理核上，直到所有任務映射完成為止；
(3)將父種群與子種群合并，計算新種群的目標函數并進行非支配排序，選擇出序值靠前的N條染色體作為新種群，進入下一代進化；
(4)判斷是否滿足終止條件，若滿足，找出最優解，若不滿足，返回步驟(2)。
2.3 算法復雜度
IMACL算法的主要復雜度體現在初始種群產生、目標函數計算、選擇、變異以及非支配排序上。N表示種群大小，M表示染色體長度，產生初始種群的復雜度為O(NM)，計算目標函數的復雜度為O（NM2），選擇操作的復雜度為O（N/2），變異的復雜度為O（NM/2），非支配排序的復雜度為O（N2）。所以，IMACL算法的總復雜度為上述各步驟復雜度累積和乘以迭代次數，遠遠小于O（M5logM），即算法復雜度低于文獻[10]中的算法。
3 實驗結果及分析
3.1 實驗結果
針對系統能耗和通信延時兩個目標函數，在NIRGAM[12]上進行IMACL算法的仿真實驗。NIRGAM是一個離散獨立、周期精確的NoC仿真器，它能為NoC中路由算法的設計和不同拓撲結構下的應用提供大量的技術支持。仿真針對DVOPD、VOPD、MWD和MEPG-4 4種實際應用程序進行，拓撲結構為常見的2D Mesh結構，采用XY路由算法。實驗中，取種群大小N=60，變異概率pm=0.3，最大進化代數max_gen=200，DVOPD的染色體長度(任務數量)M=32，VOPD的染色體長度M=16，MEPG-4和MWD的染色體長度均為M=12。
為了驗證IMACL算法的性能，每組實驗分別將該算法與傳統多目標遺傳算法（MOGA）、模擬退火算法（SA）得到的映射方案獲得的通信能耗和延時進行對比。4種算法實際應用的通信能耗和延時結果如表1所示，結果比較如圖4所示。
(a)通信能耗實驗結果比較 (b)通信延時實驗結果比較
圖4 實際應用3種算法的實驗結果比較
由表1和圖4可知，IMACL算法與MOGA和SA兩種算法相比，通信能耗和延時優化效果均十分明顯。相較于MOGA，在DVOPD應用中，系統通信能耗減少了49.76%，通信延時減少了53.23%；在VOPD應用中，系統通信能耗減少了29.54%，通信延時減少了32.45%；對于應用MWD，系統通信能耗和延時分別減少了25.93%和28.38%；在MPEG-4應用中，系統通信能耗減少了45.72%，通信延時減少了49.40%。而與SA相比，IMACL算法在DVOPD應用中，系統通信能耗減少了45.93%，通信延時減少了48.50%；在VOPD應用中，系統通信能耗減少了14.40%，通信延時減少了16.22%；對于應用MWD，系統通信能耗和延時分別減少了4.76%和5.36%；在MPEG-4應用中，系統通信能耗減少了43.43%，通信延時減少了44.36%。
從實驗結果可以看出，IMACL算法對于通信鏈路簡單（任務之間通信不頻繁）的應用在能耗和延時兩方面只有較低的提高，但對于通信鏈路復雜（任務之間通信頻繁）的應用則具有明顯的優化效果。
3.2 算法收斂性
IMACL算法與其他兩種算法相比，在通信能耗和延時上均有很大優化效果，圖5為MPEG-4通信能耗的收斂曲線。MPEG-4延時、DVOPD、VOPD以及MWD能耗和延時的收斂曲線與圖5相似。
圖5 通信能耗收斂曲線
由圖5可知，IMACL算法在迭代次數為100時便已進入全局最優，且優化過程中不易陷入局部最優；MOGA算法在迭代次數為50時就進入了局部最優，優化過程中更是多次進入局部最優，而全局最優則是在迭代次數為350代之后。相比而言，IMACL算法具有極好的收斂性。
4 結論
針對系統通信能耗和延時，本文提出一種基于通信鏈路的改進映射算法IMACL解決NoC映射優化問題。算法遵循通信量大的任務映射至物理位置接近的處理核上的原則，以減少任務相互之間通信消耗的能量和延時，從而有效降低了NoC整個系統的能耗和延時。通過NIRGAM平臺的實驗結果表明，在實際應用任務DVOPD中，本文提出的算法相較于傳統多目標遺傳算法的映射優化結果而言，能耗降低了49.76%，通信延時降低了53.23%。而對于通信鏈路較為簡單的VOPD應用，能耗僅有29.54%的降低，通信延時降低了32.45%。在MWD應用中，系統通信能耗和延時則分別減少了25.93%和28.38%。對于應用MPEG-4來說，系統通信能耗和延時分別降低了45.72%和49.40%。與SA相比，IMACL算法在實際應用程序中，能耗與延時性能也具有不同程度的提高。另一方面，IMACL算法降低算法復雜度的同時還具有良好的收斂性。可見本文所提算法對改善NoC映射算法整體性能有著積極意義。
參考文獻
[1] MARCULESCU R，OGRAS U Y，PEH L S，et al.Outstanding research problems in NoC design：system，micro-architecture，and circuit perspectives[J].IEEE Transactions on Computeraided Design of Integrated and Systems，2009，28(1)：3-21.
[2] SALEHI M E，MOHAMMADI S，FAKHRAIE S M，et al.Energy/throughput trade-off in a fully asynchronous NoC for GALS-based MPSoC architectures[C].In Proc.5th International Conference on Design and Technology of Integrated Systems in Nanoscale Era(DTIS)，Hammamet，Tunisia，2010：1-6.
[3] BOGDAN P，MARCULESCU R.Non-stationary traffic analysis and its implications on multicore platform design[J].IEEETransactions on Computer-Aided Design of Integrated Circuits and Systems，2011，30(4)：508-519.
[4] TOSUN S.New heuristic algorithms for energy aware application mapping and routing on mesh-based NoCs[J].Journal of Systems Architecture，2011，57(1)：69-78.
[5] 陳亦鷗.面向實時復雜系統的片上網絡架構及映射技術研究[D].成都：電子科技大學，2013.
[6] Zhou Liyang，Jing Ming’e，Zhong Liulin，et al.Taskbinding based branch-and-bound algorithm for NoCmapping[J].Circuits and Systems，2012，3(3)：648-651.
[7] 易宏波，羅興國.Boltzmann-NSGAⅡ算法的NoC映射研究[J].計算機工程，2012，38(22)：283-286.
[8] SEPU′LVEDA M J，WANG J C，GOGNIAT G，et al.A multi-objective adaptive immune algorithm for multiapplication NoC mapping[J].Analog Integr.Circ.& Sig.Process，2012，73(3)：851-860.
[9] 呂興勝，李光順，吳俊華.基于多目標免疫算法的NoC映射優化[J].計算機工程，2015，41(4)：316-321.
[10] SAHU P K，MANNA K，SHAN T，et al.A constructiveheuristic for application mapping onto mesh based Network-on-Chip[J].Journal of Circuits，Systems，and Computers，2015，24(8)：126-155.
[11] TERRY T Y，LUCA B，GIOVANNI D M.Analysis of power consumption on switch fabrics in network routers[C].In Proc.39th annual Design Automation Conference，New Orleans，USA，2002：524-529.
[12] Nirgam(V2.0)[EB/OL].(2013-12-20)[2016-03-08].http：//nirgam.ecs.soton.ac.uk.