摘 要： 在片上系統高速發展的今天，尋求高性能低功耗的設計架構是目前的最大需求。為了滿足對架構愈發嚴格的要求，提出一套簡單有效的片上系統優化方法。該方法通過優化算法將關聯性強的設備放置在同一條總線上來降低轉接橋的通信量，進而減小整個系統的延遲，得到高性能SoC架構。為驗證該方法的可行性，最后建立一個SoC系統進行驗證。該SoC系統經過優化后，系統事件傳輸的延遲時間明顯減少。
關鍵詞： 片上系統；系統優化；子集最優；通信模型
0 引言
隨著片上系統System-on-Chip（SoC）的發展，業界開始追求在性能、功耗、成本三者之間的最佳平衡點。高性能SoC已成為IC界的焦點。
針對該問題，PINTO A等人對設備的接口和相應總線布局布線進行重新設計，使得系統的通信不同于之前的點對點通信方式[1]。PANDEY S等人則致力于找到相對高效的總線位寬與總線數目[2-3]，其方法是在綜合時對總線上設備接口的緩沖寬度與深度進行權衡，進而提出一種時間離散的馬爾科夫鏈。
在集成電路設計的系統架構研究主要從軟件調度和硬件拓撲兩個方面進行。其中，軟件調度主要是通過對處理器指令調度的重新規劃來提升各個處理器之間的通信流程。如Wang Yi重新安排事件調度[4]。參考文獻[5]選用的是多層總線的模式。這個方向的研究還有在網格環境下[6]與群組架構下的[7]。
本文針對目前硬件拓撲方法實現復雜的問題，提出一套簡單有效的優化辦法，將側重點放在系統總線之間設備的關聯性上，通過優化算法將關聯性強的設備放置在同一條總線上來降低轉接橋的通信量，進而減小整個系統延遲。
1 系統建模
在系統模型中，每個設備作為一個頂點，設備之間的任務量用對應的權重值表示。該權重值代表兩個設備之間的通信量。若任意兩個設備Ci和Cj之間存在通信則通過相應的有向線段來表示，如（Ci，Cj）對應的權重值Weight（見式（1）），表示在事件傳輸過程中由設備Ci向Cj設備總共發送大小為Weight數據量。
Weight=Avg.size×trans.num（1）
2 系統優化
2.1 系統通信量定義
首先，假設設備總數為偶數。即設備集合S總共有2n個元素，則設備之間的通信矩陣為C=｛cij｝，i，j=1，…，2n且cii為0。i和j在這里分別代表著系統中任意兩個設備。cij表示（Ci，Cj）和（Cj，Ci）的權重和，且cij為非負值，于是可以看出矩陣C為對稱矩陣。
從而降低T的值，也就降低轉接橋需要承載的通信量。假設存在子集X和Y，XA，YB且|X|=|Y|≤n/2，所以該算法重點是從A和B集合中分別確定要交換的X和Y的子集。
假設a∈A，則a與A集合的通信量定義為內部通信量Ia，a與B集合的通信量定義為外部通信量Ea，則：
同樣地，假設存在b∈B，則外部通信量與內部通信量之差Dz=Ez-Iz，其中z∈S。并且假設t為整個集合S中除去與a和b有關的外部通信量總和，則整個系統的外部通信量如式（5）所示。
T=t+Ea+Eb-Cab（5）
當a和b互換之后，整個系統的外部通信量為T′，如式（6）所示。
T′=t+Ia+Ib+Cab（6）
于是a和b互換之后系統的外部通信量的下降為：
decline=T-T′=Da+Db-2Cab（7）
2.2 系統算法優化
通過下面的步驟對系統進行優化。
（1）先計算S集合中的每個元素的D值；
（2）選取ai∈A，bj∈B，使得相應的g1為最大值；
（3）假設在步驟（2）得到一對最大值對應為a1′和b1′，接下來計算除去這兩個元素剩下元素的D值，即范圍分別變為A-{a1′}和B-{b1′}。此時的D值可以通過下面的兩式來計算：
注意到有一部分gi<0。則將X和Y兩個子集交換后整個系統外部通信量降低了gi=G。于是在這里需要確定k值來確保gi=G為最大值。注意到，當gk+1≤0時便找到G的最大值所對應的k值，若滿足k>0就表示交換X和Y兩個子集就會使得外部通信量降為最低，同時也表明該轉接橋的通信量已經達到局部最大優化值。
以X和Y兩個子集交換之后重新組合的A′或B′集合為準，在其內部進行子集劃分，繼續從步驟（1）開始新的循環，直到優化完系統的每個轉接橋。
特殊情況可以適當地補充空元素z，即z元素的Iz=0且Ez=0。補充完之后繼續使用前面算法對元素的分布進行優化。
3 實驗實例
為證明算法的可行性，以圖1所示系統為例。如圖1（a）所示，有a、b、c、d、e總共5個設備，參考第1節的建模。其系統對應的通信矩陣如式（11）所示。
C= 0 10 5 20 3510 0 5 0 0 5 5 0 0 2520 0 0 0 535 0 25 5 0（11）
設備優化前的排布如圖1（a）所示，最優排列如圖1（b）所示。
在第二節中提到過，轉接橋傳遞的事件權重越小，則代表通過轉接橋的數據總量就越小，相應地整個系統的事件傳輸的延遲時間也就越少。
但是當設備的個數增加時，窮舉算法的時間復雜度呈指數方式增長，所以窮舉算法不可取。然而采用該算法的時間復雜度為n2logn，并且隨著設備數的增長，算法的運行時間如圖2所示。由此可見該算法具有靈活高效性。
4 結論
越來越多的實踐和研究表明，SoC系統級設計在整個SoC設計中占有非常重要的地位。本文在著力于解決SoC架構的優化問題，通過對系統問題規范的模型化，提出一種架構優化的方法。該方法通過動態分析可以優化SoC的系統設計，并且方法靈活，不拘于軟件，實施起來相對簡單。為驗證算法的可行性，本文設置了5個模塊組成的總線系統，實驗結果證實該算法可以快速有效地減小系統通信的延遲周期，得到高性能SoC架構。
參考文獻
[1] PINTO A， CARLONI L P， SANGIOVANNI-VINCENTELLI A L. A methodology for constraint-driven synthesis of on-chip communications[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems， 2009， 28（3）：364 -377.
[2] PANDEY S， GLESNER M， MUHLHAUSER M. On-chip communication topology synthesis for shared multi-bus based architecture[C]. 2005 International Conference on Field Programmable Logic and Applications， IEEE， 2005：374-379.
[3] PANDEY S， ZIMMER H， GLESNER M， et al. High level hardware/software communication estimation in shared memory architecture[C]. IEEE International Symposium on Circuits and Systems， ISCAS 2005， IEEE，2005，1：37-40.
[4] Wang Yi， Liu Duo， Qin Zhiwei， et al. Optimally removing intercore communication overhead for streaming applications on MPSoCs[J]. IEEE Transactions on Computers， 2013， 62（2）：336-350.
[5] HSIU P， HSIEH C， LEE D， et al. Multilayer bus optimization for real-time embedded systems[J]. IEEE Transactions on Computers， 2012，61（11）：1638-1650.
[6] Zhu Qian， AGRAWAL G. Resource allocation for distributed streaming applications[C]. ICPP ′08. 37th International Conference on Parallel Processing， IEEE， 2008：414-421.
[7] Qun Xu C， Xue C J， Hu B C， et al. Computation and data transfer co-scheduling for interconnection bus minimization[C]. Design Automation Conference， ASP-DAC 2009. Asia and South Pacific， IEEE， 2009：311-316.