基于子集最優分配辦法的片上系統優化*

張婉橋，陳　鑫，夏　歡（南京航空航天大學 電子信息工程學院，江蘇 南京 210016）

基于子集最優分配辦法的片上系統優化*

張婉橋，陳鑫，夏歡
（南京航空航天大學 電子信息工程學院，江蘇 南京 210016）

在片上系統高速發展的今天，尋求高性能低功耗的設計架構是目前的最大需求。為了滿足對架構愈發嚴格的要求，提出一套簡單有效的片上系統優化方法。該方法通過優化算法將關聯性強的設備放置在同一條總線上來降低轉接橋的通信量，進而減小整個系統的延遲，得到高性能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數據量。

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，X?A，Y?B且|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）所示。

當a和b互換之后，整個系統的外部通信量為T′，如式（6）所示。

于是a和b互換之后系統的外部通信量的下降為：

2.2系統算法優化

通過下面的步驟對系統進行優化。

（1）先計算S集合中的每個元素的D值；

（2）選取ai∈A，bj∈B，使得相應的 g1為最大值；

（4）重復步驟（2），直到所有的元素都被提取出來，最后會得到一系列的（′，′），（′，′），（′，′），…，（′），分別對應g1，g2，g3，…，gn。很明顯注意到有一部分gi＜0。則將X和Y兩個子集交換后整個系統外部通信量降低了。于是在這里需要確定k值來確保為最大值。注意到，當 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）所示。

設備優化前的排布如圖1（a）所示，最優排列如圖 1 （b）所示。

圖1　系統架構化優實例

在第二節中提到過，轉接橋傳遞的事件權重越小，則代表通過轉接橋的數據總量就越小，相應地整個系統的事件傳輸的延遲時間也就越少。

但是當設備的個數增加時，窮舉算法的時間復雜度呈指數方式增長，所以窮舉算法不可取。然而采用該算法的時間復雜度為n2log n，并且隨著設備數的增長，算法的運行時間如圖2所示。由此可見該算法具有靈活高效性。

4　結論

越來越多的實踐和研究表明，SoC系統級設計在整個SoC設計中占有非常重要的地位。本文在著力于解決SoC架構的優化問題，通過對系統問題規范的模型化，提出一種架構優化的方法。該方法通過動態分析可以優化SoC的系統設計，并且方法靈活，不拘于軟件，實施起來相對簡單。為驗證算法的可行性，本文設置了5個模塊組成的總線系統，實驗結果證實該算法可以快速有效地減小系統通信的延遲周期，得到高性能SoC架構。

圖2　算法時間復雜度探究

［1］PINTO A，CARLONI L P，SANGIOVANNI-VINCENTELLI A L.A methodology for constraint-driven synthesis of onchip 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.

圖7　滿載時輸入電壓和電流波形

4　結論

本文對UCC3818A工作原理進行了簡要的分析；闡述了外圍電路中關鍵元器件的參數的設計方法。結合UCC3818A的內部特性，對電路中電壓環、電流環、乘法器等主要功能電路進行了理論設計。制作了600 W的APFC模塊并對其理論設計進行了驗證。結果表明，該模塊特性可以滿足PF要求在0.9以上的電動觀光車充電器的要求。如果采用更高耐壓的器件，將輔助電源的輸入置于APFC的輸出，可以避免本模塊中因輔助電源引起PF值丟失，從而可以得到更高的PF值。

參考文獻

［1］萬輝，張捍東，黃丹.有源功率因數校正控制技術現狀與發展［J］.電工電氣，2013（3）：1.

［2］賁洪奇，張繼紅，劉桂花，等.開關電源中的有源功率因數校正技術［M］.北京：機械工業出版社，2010.

［3］UCC3817A/18A Bicmos PFC［EB/OL］.（2009-3-26）［2014-10-02］.http：//www.ti.com.cn/cn/lit/ds/symlink/ucc3818a.pdf.

［4］王建飛，付純菲.基于UCC3818大功率APFC電源設計［J］.變頻器世界，2013（8）：52.

［5］王居德，趙恒飛，劉穎力，等.鐵硅鋁磁芯升壓電感的設計［J］.磁性材料及器件，2011（8）：53-54.

（收稿日期：2014-10-21）

作者簡介：

張興（1987-），通信作者，男，碩士研究生，主要研究方向：LED驅動、大功率鉛酸電池充電器。E-mail：alexpowera@163.com。

秦會斌（1961-），男，博士，教授，博士生導師，主要研究方向：新型電子材料與器件、抗 EMI技術。

郭石磊（1984-），男，碩士研究生，主要研究方向：大功率逆變電源。

An optimal allocation of subsets methodology for system-on-chip architectures

Zhang Wanqiao，Chen Xin，Xia Huan
（School of Electronic and Information Engineering，Nanjing University of Aeronautics and Astronautics，Nanjing 210016，China）

Nowadays，with the fast developing system-on-chip（SoC）technology，the essential requirements for structure design lie in high performance and low power consumption.In order to meet these increasingly urgent requirements，this paper proposed a simple system optimization method for SoC.By placing the highly relevance devices on the same bus to decrease the communication traffic between the transfer bridges.Therefore，the communication delay of the overall system is reduced，and achieve the high performance.For the sake of the practicability of the proposed method，this paper established a proposed SoC system.By comparing the improved system and the traditional one，the communication delay has been reduced obviously.

System-on-Chip（SoC）；system optimization；an optimal allocation of subsets；communication architectures

TN47

A

1674-7720（2015）06-0026-03

2014-10-24）

張婉橋（1989-），女，碩士研究生，主要研究方向：數字集成電路設計。

陳鑫（1982-），男，博士，副教授，主要研究方向：數模混合電路。

夏歡（1989-），男，碩士研究生，主要研究方向：數字集成電路設計。

國家自然科學基金（ 61106029 ）