面向全分布式VLIW結構的部分互連研究

摘要：隨著VLSI技術的發展，傳統的采用了全互連網絡的全分布式超長指令字結構的功能單元通信開銷，成為制約著處理器頻率增加和規模擴大的瓶頸.在分析應用程序特征的基礎上，利用定義的5種通信模式提出了多種全分布式超長指令字部分互連結構，分析了由全互連結構變為部分互連結構通信方式上的改變，并完成了功能單元指派和通信調度等相關的編譯調整.模型分析和實驗數據表明，相比全互連結構，部分互連結構在程序性能些微降低的情況下，面積、功耗等資源開銷大幅減少，并呈現出良好的可擴展性.

關鍵詞：超長指令字；全互連；部分互連；可擴展性

中圖分類號：TP393 文獻標識碼：A

Research on Partial-connected Crossbar

for Full-distributed VLIW Architecture

SHI Zi-long， YANG Qian-ming， WEN Mei， ZHANG Chun-yuan， WU Nan， QIAO Yu-ran

（College of Computer， National Univ of Defense Technology， Changsha， Hunan 410073， China）

Abstract： With the development of VLSI technology， the communication overhead of functional units of the full-connected network for full-distributed VLIW has become a bottleneck restricting the increase in processor frequency and scale. Based on the analysis on the characteristics of the application and 5 defined communication models， a variety of partial-connected architectures for fully-distributed VLIW were presented. The difference between partial-connected and full-connected architectures was analyzed and the related compilation modulation was accomplished， especially function unit designation and communication scheduling. Model analysis and experimental data show that， compared with full-connected architecture， partial-connected architecture can substantially reduce area and power consumption and resource overhead， and gain considerable scalability， while program performance is slightly lower.

Key words： VLIW； full-connected； partial-connected； scalability

應用的極度膨脹對計算性能的追求是永無止境的，也推進了嵌入式技術的高速發展.但近年來，VLSI技術進入納米級工藝時，繼續縮小器件尺寸遇到了前所未有的阻力.另外，由于亞閾值電流影響[1]，過去幾十年用于實現“立方”能量縮放（每器件的能量按器件基本特征尺寸減少的三次方縮減）不變的現場縮放方法也走到了終點.此外，線資源愈趨昂貴，在0.13 nm工藝下，將一個64位數據在片上全局傳輸的功耗是執行一個64位浮點操作功耗的20倍^[2].能效方面，典型嵌入式應用的需求開始突破100 Mops/mW，甚至達到1 000 Mops/mW.總的來說，在現代VLSI技術下，計算單元相對廉價而計算單元之間的通訊較昂貴，同時整個芯片面臨著嚴重的功耗問題，在設計處理器體系結構時，必須加以仔細而慎重的考慮.

超長指令字（VLIW）技術通過編譯來開發指令級并行（ILP），使得硬件實現非常簡單，是一種公認的高性能、低功耗的體系結構技術，在現代高性能嵌入式處理器中得到了廣泛應用[3-5].典型VLIW含有大量的功能單元，需要同時訪問大量的寄存器.為了減小寄存器的面積，并減少寄存器的訪問延遲，人們通常將這個寄存器分塊，形成多個簇（cluster）[6]，每個cluster內部的功能單元共享一個寄存器，cluster之間通過特定的通信機制進行通信.如果更進一步，每個cluster只含有一個功能單元，就形成了全分布式的結構（fully-distributed）[7].全分布式結構下，功能單元間通常以全互連的形式進行通信.通行的全互連結構為VLIW功能單元之間的通信提供了較多的靈活性，但當寄存器的面積、能耗和訪問延遲降低之后，功能單元之間的通信開銷（硬件資源、功耗等）比例顯著增加，成為VLIW處理器頻率和規模增加的瓶頸[8].隨著應用中展現出的越來越多的ILP[9]，VLIW中勢必集成更多的功能單元，互連結構的問題將會變得更加嚴重[10].基于此，本文進行了全分布式VLIW結構下功能單元部分互連結構的研究.

本文結構如下：第1節基于定義的5種通信模式，分析了媒體應用在全分布式VLIW結構下的程序特征；第2節提出了幾種部分互連結構，并介紹了相關編譯支持；第3節提出了針對部分互連的面積、功耗的分析模型，并進行了性能相關的實驗分析；最后總結全文.

1 程序特征分析

目標應用程序特征的分析，對于體系結構的設計具有重要的指導意義.本節基于全互連網絡結構來分析目標應用對互連網絡的實際使用情況.媒體程序具有可觀的ILP，是VLIW結構的典型應用，首先選取此類應用的程序特征來研究VLIW功能單元互連網絡的結構，具有典型意義.

基于全互連結構的全分布式VLIW如圖1所示，每個功能單元通過兩個本地寄存器組提供操作數，功能單元的運算結果輸出到各自的總線，每根總線可供應給所有的寄存器組.這種全互連結構的優點是每個寄存器組可從任一功能單元的輸出中選擇其中之一作為輸入，具有最大的靈活性和理論上最高的帶寬.但是由于每根輸出總線都需要驅動所有的寄存器組，因此走線較長，需要較大的驅動能力，能耗較大，同時還存在選擇器的開銷.

由于不是每個功能單元的結果都同時供應給所有其他功能單元的，以此為區分， 我們定義5種通信模式.1to1：表示功能單元的結果只供應給1個功能單元；1to2：表示功能單元的結果供應給2個功能單元；1to3：表示功能單元的結果供應給3個功能單元；1to4：表示功能單元的結果供應給4個功能單元；other：表示功能單元的結果供給超過4個的功能單元.

利用斯坦福大學提供的Iscd編譯器^[11]，本文統計了典型媒體應用對全互連網絡的通信模式的比例分布情況.圖2為8路VLIW結構下的結果，分析4路、6路VLIW可以得到相同的比例趨勢：對于具有典型意義的媒體應用來說，其通信模式主要分布在1to1和1to2兩種情況下，亦即是功能單元的結果通常供應給1個或2個功能單元.可見，全互連結構雖然提供了理論上最大的通信帶寬，但實際應用的通信需求卻無法將其有效利用.

由此我們認為，比起全互連結構，較低通信能力的部分互連結構具有一定的合理性和競爭力.設計合理的部分互連結構，在保證性能相當的情況下，可以有效地降低面積、延遲和能耗，同時，預期具有良好的可擴展性.

2 部分互連結構

與全互連結構不同，在部分互連結構中，功能單元的輸出只供應給部分的功能單元.這樣，ALU的扇出減少，連接寄存器組的多個選擇器的規模較小、延遲降低、面積功耗減少.圖3給出了部分互連的示意形式.

2.1 部分互連形式

全互連結構只有唯一確定的形式，但部分互連結構可以有多種不同的具體形式.鑒于實現的難易程度和編譯的效率，本文主要探索了拓撲上具有對稱性的部分互連網絡.參考第1節中定義的5種通信模式，我們主要研究如圖4所示的4種互連網絡.“1to2”：如圖4（a）所示，每個功能單元的結果供應給相鄰的2個功能單元（含自身）；“1to3”：如圖4（b）所示，每個功能單元的結果供應給相鄰的3個功能單元（含自身）； “1to4”：如圖4（c）所示，每個功能單元的結構供應給相鄰的4個功能單元（含自身）；“Grouping”：如圖4（d）所示，將功能單元分組，在組內采用全互連，組間通過相鄰的兩個功能單元實現互連.本文主要分析兩種情況：g3（3個功能單元為一組）和g4（4個功能單元為一組）.

2.2 部分互連結構下的通信

在全互連結構下，每個功能單元的輸出可以同時供應給所有的功能單元，因此可以同任何其他功能單元進行直接的通信.但是在部分互連結構下，這種通信需要通過“第三方”進行，圖5顯示了這一通信過程.圖中功能單元ALU1與ALU2直接互連，功能單元ALU2和ALU3直接互連，但是功能單元ALU1和ALU3沒有直接互連，那么當ALU1和ALU3需要通信時（圖中變量b），則可以通過ALU2（第三方）來進行，首先ALU1將變量b寫入ALU2的寄存器，然后ALU2執行copy操作將變量b放在其輸出總線上，最后ALU3從該總線上讀入變量b.

2.3 部分互連的編譯支持

文獻[12]給出了采用全互連的全分布式VLIW結構的核心級編譯調度方法，與本文研究的采用部分互連的全分布式VLIW結構有很大相似之處，因此本文的通信調度和編譯基于此設計.

VLIW指令調度過程將每個操作分配到不同的功能單元上，并指定它到合適的節拍（cycle）流出.由于硬件結構的改變，編譯器要著重考慮功能單元的選擇和通信調度.

功能單元指派：一個操作往往可以選擇在多個功能單元上執行，在部分互連條件下，必須謹慎考慮將哪個操作分派到哪個功能單元上執行，因為有的功能單元之間不能直接通信.編譯器采用一個啟發式規則對所有能夠執行該操作的功能單元進行優先級排序，編譯器首先嘗試將操作分派給通信代價低的功能單元，接著嘗試將操作分派給具有較低利用率的功能單元，最后嘗試將操作分派給最近最少使用的功能單元.編譯器將這三步嘗試的結果加權生成一個權重值，功能單元的權重值越小，優先級越高.

通信調度：編譯器調度算法如圖6所示.編譯器采用一個啟發式的方法選擇操作，然后把它分派到合適的功能單元上并調度到第一個可能流出的最早cycle.編譯器將操作分派到一個可用功能單元上，然后嘗試通信調度.若通信調度成功，則操作調度結束.若通信調度失敗，則編譯器將操作分派到另一個可用功能單元上，或者將操作推遲到下一個可用cycle流出，直到成功為止.

此調度基于操作驅動，而非cycle驅動.操作驅動選擇一個操作并把它調度到有可能流出的最早的cycle，而cycle驅動在推進到下一個cycle之前，在當前cycle調度盡可能多的操作.針對共享互連體系結構，在采用通信調度后，基于操作驅動的調度器比基于cycle驅動的調度器效果好，因為它能保證在關鍵路徑上的操作之間的通信被優先調度.例如，對于處于關鍵路徑上的兩個操作o1和o2之間的通信，使用cycle驅動時，調度器調度o1，然后在推進到下一cycle前在當前cycle調度盡可能多的操作.這些額外的操作可能會占用形成關鍵路徑上通信的有效路由所需的互連資源，而當在下一cycle調度o2時，通信調度可能不得不插入copy操作延遲o2.調度在第二個cycle上的其他操作有可能占用所有的能執行copy操作的功能單元，使得o2進一步被延遲.而使用操作驅動時，因為o2不依賴于其他任何操作，在調度完o1后的下一個cycle可以立即調度o2，這個順序使得通信調度能為這兩者之間的通信分配一個有效的路由.

3.1 分析模型

3.1.1 面積模型

互連結構的面積由互連線的面積和多路選擇器的面積組成.多路選擇器的面積由構成選擇器的2-to-1選擇器的數目決定，對于n個輸入的選擇器，其總的二選一選擇器的數目為n-1.所以選擇器的總面積如下：

4 結 論

本文針對全分布式VLIW結構下功能單元互連面臨的硬件開銷、可擴展性和能耗等問題，從目標應用的具體程序特征出發，定義了5種通信模式，提出了4種代表性的對稱式部分互連結構，并深入分析了各種部分互連結構對面積、功耗和程序性能的影響.實驗結果表明，相比于全互連網絡，在性能只有些微下降的情況下，部分互連結構可以顯著地降低硬件開銷和能量開銷.同時，隨著VLIW規模的擴大，部分互連結構將展現出良好的可擴展性.

參考文獻

[1] KOGGE P， BERGMAN K， BORKAR S， et al. ExaScale computing study： technology challenges in achieving exascale systems[R]. DARPA IPTO， U.S. Government， AFRL Contract Number FA8650-07-C-7724， 2008.9.

[2] KHAILANY B. The VLSI implementation and evaluation of area and energy efficient streaming media processors [D]. Palo Alto，CA： Stanford University， 2003.

[3] DOLLARHIDE A W， RUTLEDGE T， WEINGER M B， et al. Use of a handheld computer application for voluntary medication event reporting by inpatient nurses and physicians [J]. Journal of General Internal Medicine， 2008， 23（4）： 418-422.

[4] KUUSILINNA K， CHANG C， AMMER M J， et al. Designing BEE： a hardware emulation engine for signal processing in low-power wireless applications [J]. EURASIP Journal on Applied Signal Processing， 2003（1）： 502-513.

[5] MOORE G E. Excerpts from a conversation with Gordon Moore： Moore’s Law [R]. Santa Clara， California： Intel Corporation， 2005.

[6] TURLEY J， HAKKARAINEN H. TI’s new ‘C6x DSP screams at 1，600 MIPS [J]. Microprocessor Report， 1997， 11（2）： 14-17.

[7] RIXNER S， DALLY W J， KHAILANY B， et al. Register organization for media processing[C]//Proceedings of the 6th International Symposium on High-Performance Computer Architecture. New York： IEEE， 2000： 375-386.

[8] BALASUBRAMONIAN R， MURALIMANOHAR N， RAMANI K， et al. Microarchitectural wire management for performance and power in partitioned architectures [C]// Proceedings of the 11th International Symposium on High-Performance Computer Architecture. Washington， DC： IEEE Computer Society， 2005： 28-39.

[9] LAPINSKII V S， JACOME M F， DE VECIANA G A. Cluster assignment for high performance embedded VLIW processors [J]. ACM Transactions on Design Automation of Electronic Systems， 2002， 7（3）： 430-454.

[10]DE MAN H. Ambient intelligence： giga-scale dreams and nano-scale realities [C]// Proceedings of 2005 IEEE International Solid-State Circuits Conference. New York： IEEE， 2005： 29-35.

[11]MATTSON P， KAPASI U， OWENS J， et al. Imagine programming system user’s guide [R/OL]. Stanford， CA：CVA Group， Stanford University， 2002[2002-05-11]. http：//cva.stanford.edu/classes/ee482s/docs/ips_user.pdf.

[12]MATTSON P， DALLY W J， RIXNER S， et al. Communication scheduling [C]//Proceedings of the 9th International Conference on Architectural Support for Programming Languages and Operating Systems. New York： ACM， 2000： 82-92.

[13]WHO M， SEO S， LEE H， et al. The next generation challenge for software defined radio [C]//Proceedings of the 7th International Conference on Systems， Architectures， Modeling， and Simulation. Berlin， Heidelberg： Springer-Verlag， 2007： 343-354.

[14]DAVIS M E. Space based radar moving target detection challenges [C]//Proceedings of IEEE RADAR Conference. New York： IEEE， 2002： 143-147.

[15]FARSIU S， ROBINSON D， ELND M， et al. Advances and challenges in super-resolution [J]. International Journal of Imaging Systems and Technology， 2004， 14（2）： 47-57.

[16]ALLAN A， CASE C， CHANG C S， et al. International technology roadmap for semiconductors： 2008 update [R]. International Roadmap Committee， 2008.

[17]ARM INC. TSMC 65nm CLN65GPLUS RVT Process 1.0-Volt 12-Track Advantage Standard cell library v2.1 Databook [R]. Cambridge， England， United Kingdom： ARM Inc， 2009.