基于改進量子遺傳算法的片上網絡多目標映射技術

張保崗 韓國棟 湯先拓

(信息工程大學 河南 鄭州 450002)

0 引 言

片上系統(System on Chip，SoC)隨著超大規模集成電路的快速發展也在不斷改進，內部總線結構的通信系統早已經不能滿足需要，片上網絡[2](Network on Chip，NoC)逐漸成為SoC內部通信系統的主流設計[1]。隨著單位芯片上處理單元(Processing elements，PE)集成數量越來越多，在快速高效低時延和穩定性上對NoC的要求也越來越高，能耗、低時延和穩定性也逐漸成為限制芯片發展的重要因素。NoC發展迅速，極大地推進了芯片的發展，其能耗和時延是SoC研究設計最重要的指標。片上網絡映射作為NoC設計的重要一維，其低功耗和低時延的優化設計實現影響著整個片上網絡性能表現[3]。

如何在系統條件約束下，在現有NoC拓撲結構和路由的基礎上，將任務節點按照一定規則有效地映射到片上網絡各個處理單元上，盡可能減少總的信息交互功耗并在較低的時延內實現是NoC技術研究的一個熱點。隨著芯片PE數量的增加，需要處理的應用越來越多也越復雜，傳統的遍歷比較窮舉求最優解的方法早已經不適合，目前智能啟發式算法在該領域逐步展現其優越性和實用性，也是近年來NoC映射技術研究的熱點。

1 相關工作

基于啟發式算法的NoC映射技術有很多，在低功耗和多目標方面的相關研究成果也有很多，如文獻[4]提出一種基于混合量子遺傳算法的新型片上低功耗映射方法，結合自適應旋轉角度調整策略，量子比特交叉變異操作和群體突變思想，并在每次迭代中選擇具有一定概率的初始解，以防止算法停滯。文獻[5]利用任務節點通信量大小劃分優先級，得到若干較優初始解集；利用離散粒子群算法的快速搜索能力迅速靠近最優解；利用遺傳操作中的選擇和變異防止算法掉入局部較優解陷阱，以較少的迭代次數完成最優解的尋找。文獻[6]結合了禁忌搜索，主要優化離散粒子群，用禁忌列表防止群粒子重復搜索，使得NoC的總體通信延遲和能耗最小化。文獻[7]提出一種優化快速最近鄰啟發算法ONMAP，最小化NoC通信消耗并可以映射實時嵌入式應用程序，某種程度上實現了動態映射效果。文獻[8]提出了一種新的基于遺傳的超啟發式算法作為核心算法，由于該算法可以在映射過程中自動選擇合適的算子，因此可以顯著提高收斂速度并表現出優異的穩定性，用于共同優化片上網絡的能耗和通信延遲。

上述有關研究成果對NoC低功耗低時延等多目標映射方面有很大的推進作用，但依然有可優化的空間，大多算法都是在通信帶寬滿足需要不會出現擁堵現象的情況下實現的。隨著人們對任務功能需求的提高，NoC部分節點鏈路很可能會出現擁堵。本文在考慮擁堵的情況下設計多目標評估模型，在充分理解量子遺傳算法(Quantum Genetic Algorithm，QGA)優缺點的基礎上[9]，結合應用任務和2D Mesh拓撲結構NoC的特點，設計一種改進的量子遺傳算法(Modified Quantum Genetic Algorithm，MQGA)來實現NoC低功耗低時延等多目標映射。

2 問題定義和模型描述

2.1 問題定義

定義1應用任務圖(Application Task Graph，ATG)如圖1(a)所示，它是一個帶通信權重的有向圖。該應用有8個任務節點，有10條相關鏈路，含有數字的圓圈代表相應的任務節點ti，從任務節點ti到tj的通信量記為Vti,t2，圖中Vt1,t2=40，方向從t1到t2。

定義2結構特征圖(Architecture Characteristic Graph，ARCG)如圖1(b)所示，是由各個帶處理單元的交換節點相互連接，可以實現雙向通信的有向圖。圖1(b)為典型的3×3的Mesh拓撲結構，含有數字的圓圈代表相關交換節點si，每個交換節點都有一個處理單元pi與之對應。兩個處理單元pi、pj之間的曼哈頓距離為Mpi,pj，對于Mesh結構一般為兩個資源節點所經歷最少交換節點數減1。

(a) 應用任務圖ATG (b) 結構特征圖ARCG圖1 映射流程圖

2.2 NoC映射

片上網絡映射就是將給定的ATG，按一定的順序分配到ARCG中，任務節點與處理單元一一對應，為處理單元通過NoC完成相應的處理任務做準備。映射結果要正確執行，需要保證結構特征圖的處理節點數量大于任務圖中的任務節點數，即：

Size(ATG)≤Size(ARCG)

(1)

任務節點數量為m的ATG要映射到n×n的2D Mesh上，需要滿足m≤n2。m個任務節點參與映射就有n2！/(n2-m)！個映射結果，合理的映射結果可以更好地利用現有處理資源來完成相應的應用任務，比如快速、低功耗等。如何找到一個較好的低功耗低時延映射結果是本文所要解決的主要問題。

2.3 功耗模型

片上網絡功耗模型中單位比特數據在兩個相鄰處理單元之間傳遞消耗的能量Ebit為：

Ebit=ESbit+EBbit+EWbit+ELbit

(2)

式中：ESbit為單位比特在交換節點的能量消耗；EBbit、EWbit為單位比特在緩存區和處理單元與相應交換節點之間鏈路消耗的能量；ELbit是單位比特在兩個處理單元之間鏈路傳輸消耗的能量。由于EBbit、EWbit遠遠小于ESbit和ELbit，所以公式可以簡化為：

Ebit=ESbit+ELbit

(3)

因此，單位比特從處理單元pi到pj所消耗的能量為：

(4)

對于n×n規則2D Mesh拓撲結構的NoC來說，令N=n×n，則任務節點數為m的任務圖映射到結構特征圖后所消耗的總能耗ENoC為：

(5)

由功耗模型可知，任務節點映射到的處理節點不同，最終完成任務需要消耗的能耗也不盡相同。由式(4)-式(5)可知，要減少片上網絡的總功耗，關鍵在于降低映射結果的總通信權重的曼哈頓距離。

2.4 時延模型

映射后處理應用程序所需時間如下[5]：

(6)

式中：TL、TS分別為單位比特數據在無阻塞情況下，流經單位鏈路和單個交換節點所需要的時間；TW為鏈路有阻塞時的總時間延遲。從式(6)可看出，映射完成后NoC的時間消耗一方面與總的通信曼哈頓距離有關，另一方面受傳遞路徑阻塞延遲TW的影響。阻塞出現一般為某些鏈路和交換節點可以提供的帶寬不能滿足需要。為減少阻塞，需要通信鏈路負載均衡，故TW可以用鏈路平均負載方差來衡量：

(7)

式中：Fi,Fj為鏈路i、j的負載量；L為NoC總鏈路數(兩個相鄰交換節點之間的鏈路為一個單位鏈路)，且FNoC越大TW亦越大。NoC的總延時和負載方差之間的關系為：

TW=FNoC×b

(8)

式中：b視為某一常數。

2.5 多目標優化模型

由線性加權和法得多目標優化函數為:

min{a×TNoC×c+(1-a)×ENoC}

(9)

式中：a為線性加權系數，取0～1之間任一實數，為1時只考慮時延；為0時只考慮能耗。c為某個常數，為了更好地與ENoC融合便于進行量化比較，c值可以設為通信帶寬。通過NoC映射的功耗和時耗公式可以看到，TNoC在無阻塞時的時間消耗和能耗成正比，執行一個應用能耗越低則耗時也較短；有阻塞時時間消耗就和能耗成反比。所以，要想獲得時間能耗等的多目標優化，就需要負載均衡防止擁塞的情況下盡可能降低功耗，通過負載均衡也可以減少NoC通信熱點的出現，提高通信可靠性穩定性。

3 基于改進量子遺傳算法的映射技術

量子遺傳算法具有適應性強、種群規模小、種群多樣性、強大的全局搜索能力以及具備較強的勘探能力等特點，在很多領域得到廣泛的應用。

3.1 解結構

如圖1中ARCG結構是一個典型的3×3 Mesh的NoC，本文只考慮2D Mesh結構的NoC，n×n的Mesh結構有n2個處理單元，每個處理單元在NoC中位置不同，分別有2、3、4條物理鏈路將各個處理單元連接起來，實現相互之間的通信。對于量子遺傳算法，每個種群個體都代表一個映射結果。

將2D Mesh中的處理單元從左到右、從上至下進行升序排序，如圖2所示，從P1到P9，每個處理單元都有一個唯一的數字編號，對于圖中3×3 Mesh結構的，最大編號為9。將圖1中的任務節點映射到該NoC中，由于任務節點數量為6，則有9!/(9-8)!=362 880個映射結果，其中映射結果a、b對應映射位置信息Pa={1,4,5,2,3,7,8,9}、Pb={1,5,9,2,3,7,4,6}為兩個有效的映射結果即有效解，只要對應位置信息為8個不大于9的不相同整數，都是一個有效解。

(a) 映射a (b) 映射b (c) 映射結果圖2 映射結果圖

3.2 初始解構造

遺傳算法和量子遺傳算法的初始解集大多是隨機產生的，當種群規模比較大時進化效率很低，為了提高收斂速度，結合NoC的結構特點，按照相關鏈路數量和通信量大小雙重標準對任務節點優先排序，優先級高的優先選擇映射位置，構建一個較優初始解集，將大大提升種群進化效率。

構建較優初始解集步驟如下：

1) 統計各個任務節點相關鏈路數量RLnum和相關通信總量:

(10)

以圖1中ATG為例，優先級定級如表1所示。

表1 任務節點優先級定級

2) 優先考慮任務節點相關鏈路數量，數量越多，優先級越高；數量相同時，考慮任務節點相關通信總量，通信總量越高的優先級越高。

3) 優先級高的優先在對應的ARCG中選擇合適的位置放置，再放置與它相關的任務節點，相關任務節點有多個時優先級越高的優先放置。

4) 剩余少量節點可以隨機放置，產生初始解集。

如圖3所示，以圖1中的ATG和ARCG為例，任務節點3有4個相關鏈路，則最先映射，對應ARCG中位置5剛好有4個相關物理鏈路，則任務節點3放置在位置5；與任務節點3有關系的任務節點2、4、5、7按照表1中的優先級放置，則依次放置節點4、7、2、5；最后考慮第三梯隊的放置，優先放置與任務節點4相關的鏈路，其中3、5已經確定位置，則就近放置1即可，其他同理放置，直至所有任務節點全部放置在ARCG中。由于放置任務節點4時有4個位置可以選擇，任務節點4確定后任務節點3有3個位置可以選擇，進而產生很多可能的較優解。

圖3 較優初始解集構造

以上是對于3×3 Mesh的NoC，如果是4×4 Mesh，第一個任務節點就有4個映射位置可供選擇，8個任務節點放置到16個映射位置中，結構冗余很大，一般隨機確定第一個任務節點的位置，然后按照上述方法構造較優初始解集。如果初始解集需求較大時可以通過變更第一個任務節點位置來獲取更多的較優初始解。

3.3 量子遺傳算法原理

量子遺傳算法利用量子多態特性，用概率幅對染色體進行編碼，然后通過量子旋轉門調整概率幅進化種群來尋找最優解，具體可在文獻[9]中了解相關原理。

QGA引入量子比特，一個量子比特是兩個基態的任一線性組合如下：

|φ〉=α|0〉+β|1〉

(11)

式中:α、β為兩個基態|0〉、|1〉對應的概率幅，表示量子態|φ〉被觀察為基態的相應概率，且滿足：

(12)

一對復數定義一個量子位，用概率幅對染色體進行編碼，則長度為m的量子染色體可表示為：

(13)

QGA通過量子旋轉門實現種群的進化，即替代原遺傳算法的選擇、交叉、變異操作，使得遺傳算法的進化實現更簡單。量子旋轉門更新方式為：

(14)

3.4 改進量子遺傳算法的實現

QGA具有全局搜索能力強、收斂速度快、個體數目少易于進化計算且不容易陷入“早熟”陷阱等優點。不同于變異操作，量子變異操作通過選擇改變變異位的概率幅，利用量子糾纏特性，只需要采用單點變異就能防止遺傳早熟現象出現。QGA改進策略(MQGA)如圖4所示。

圖4 MQGA策略圖

MQGA流程如下：

1) 初始化總群Q(t)，結合Mesh拓撲結構特點采用前面講到的新方法生成初始種群Q(t0)，含有N個量子編碼的染色體。

2) 對Q(t0)進行一次測量并進行適應度評估，得到該種群的最優個體解Bgtj(t0)，并做好相應記錄。

3) 判斷計算過程是否滿足結束條件，滿足則退出，否則繼續計算。

4) 量子旋轉門操作得到下一代種群Q(t1)。

5) 對Q(t1)種群進行一次適應度計算，得到最優個體解Bgtj(t1)，并做好相應記錄。

6) 返回步驟3)進行下一次迭代。

4 實 驗

4.1 實驗環境

1) 仿真平臺。實驗在Linux環境下用C++完成映射算法程序等相關源代碼的編寫，采用2D NoC仿真軟件Noxim作為仿真軟件，在Ubuntu 16.04操作系統下實現。硬件環境采用CPU為第八代Intel Core i7-8550U，最高睿頻4.0 GHz，內存16 GB DDR4雙通道的微型計算機。

2) ARCG拓撲結構和路由選擇。2D Mesh拓撲結構結構規則、實現容易、布線簡單、便于拓展，是常用的NoC拓撲結構，對于映射算法研究非常合適。該實驗選用2D Mesh拓撲結構，根據實驗需要有4×4、5×5、6×6三種規模的Mesh拓撲。路由算法采用容易理解和實現的XY路由算法，也是NoC主流路由算法。

3) 應用任務圖的選擇。為了體現QGA算法對各種實際應用的有效性，并便于與同類算法作對比分析，實驗采用典型的實際應用任務圖VOPD、MPEG-4、263Enc、263Dec[13]。4種應用任務圖結構不同，任務節點數和通信總量也不盡相同，詳細特征屬性見表2。

表2 應用任務屬性

4) 實驗結果計算方式。由于芯片生產工藝的不同，不同芯片的Mesh結構相鄰處理單元之間傳遞信息的能耗和時延也不相同。為了便于評估映射結果的功耗和時延，考慮到Mesh結構的規則對稱性，實驗計算時將相鄰兩個處理單元之間的距離視為一個曼哈頓距離M，每M通信傳遞消耗1個能量單元，時延時間按式(9)進行同一量化。由于智能算法有一定的隨機性，為確保實驗結果準確性，每種應用任務圖在同一規模的Mesh結構特征圖下分別運行10次，然后取10次結果的平均值。

4.2 多目標線性加權系數a的選取

a的選擇主要由鏈路帶寬的高低和處理任務通信量的大小等決定。以4×4規模的NoC為例，由于VOPD、MPEG-4通信量比263Enc尤其是263Dec大很多倍，對前兩個可能會出現擁堵的帶寬在運行263Enc、263Dec時不會發生擁堵。所以實驗時鏈路帶寬根據處理任務通信量的多少進行變化，保證存在一定擁堵的可能性，該實驗取平均鏈路負載的5倍。VOPD、MPEG-4鏈路帶寬相近，可放在同一圖中對比，在不同a取值下的實驗結果如圖5所示。

(a) VOPD與MPEG-4

(b) 263Dec

(c) 263Enc圖5 4×4不同應用MQGA能耗隨a值變化圖

通過4種應用能耗曲線可以看出，在不考慮時延時能耗都會偏高，在過于考慮時延時反而造成能耗的大量提升，在實驗設定的帶寬下，a值取0.3附近時效果比較好，能耗相對較低。

VOPD在不同規模的Mesh結構隨a值變化對比圖如圖6所示。隨著NoC結構規模的擴大，處理應用能耗整體會有不少提升，因為規模變大后，鏈路帶寬降低，擁堵更嚴重；a值的調節在前期比較顯著，最低能耗的a值會減小，說明NoC規模越大，a值的合理取值應該越小。

圖6 VOPD不同規模MQGA能耗隨a值變化圖

4.3 能耗對比

對比不同算法時設置a值為0.3，在4×4規模的Mesh結構下，與GA[10]、AGA[11]、DPSOGA[5]、HQGA[4]4種算法作對比。為了同框便于直觀顯示，以4種應用任務映射結果能耗對另外4種算法的能耗降低百分比如圖7所示。

圖7 能耗降低條形圖

可以看出，MQGA在相同運行環境下比GA、AGA有更大的提升,相比較新的DPSOGA和HQGA也有不少提升，說明MQGA搜索精度更精確。例如對VOPD應用來說，MQGA比早期的GA提升25.4%，比AGA提升10.4%，比近兩年的DPSOGA也提升4.1%，即使同樣采用量子編碼的HQGA也有提升了1.6%；對263Dec應用時候提升更多，即使對比較新的DPSOGA也提升了13.2%，比HQGA提升了5.8%。

4.4 收斂速度對比

MQGA在具有較快收斂特性的QGA基礎上，結合NoC應用映射特點，進一步優化初始解集，使得MQGA收斂速度更快。在同一環境平臺下5種算法處理VOPD應用任務能耗隨遺傳迭代次數收斂情況如圖8所示。MQGA的收斂速度是最快的，最早的GA迭代到收斂需要150次左右，同樣情況下MQGA 30次迭代就可以達到收斂，而且收斂精度遠遠高于GA。對于同樣適用較優初始解集的DPSOGA，MQGA的初始解集質量更高，收斂速度也更快。對于同樣改進QGA的HQGA，由于初始解集更優秀，收斂速度大大提升，收斂精度也有提高。可以看出，GA結合量子編碼會很大程度地提升收斂速度。

圖8 5種算法收斂走勢圖

5 結 語

本文在考慮擁堵的情況下利用線性加權和負載均衡的辦法設計了NoC多目標映射評估模型，不僅可以實現低功耗低時延，也同時提高了系統穩定性和可靠性，結合NoC映射特點改進了量子遺傳算法。實驗結果表明，MQGA在相關算法比較中效果顯著，大大提升了NoC映射算法的收斂速度，并進一步提升了搜索精度。算法實現時量子遺傳編碼比較復雜，編碼解碼速度慢，后續研究可以圍繞編碼問題進一步優化。隨著應用任務越來越復雜，片上網絡規模的擴大，較優初始解集的產生也需要合適的算法方可更好實現。