面向全分布式VLIW結(jié)構(gòu)的部分互連研究

摘要：隨著VLSI技術(shù)的發(fā)展，傳統(tǒng)的采用了全互連網(wǎng)絡(luò)的全分布式超長指令字結(jié)構(gòu)的功能單元通信開銷，成為制約著處理器頻率增加和規(guī)模擴大的瓶頸.在分析應(yīng)用程序特征的基礎(chǔ)上，利用定義的5種通信模式提出了多種全分布式超長指令字部分互連結(jié)構(gòu)，分析了由全互連結(jié)構(gòu)變?yōu)椴糠只ミB結(jié)構(gòu)通信方式上的改變，并完成了功能單元指派和通信調(diào)度等相關(guān)的編譯調(diào)整.模型分析和實驗數(shù)據(jù)表明，相比全互連結(jié)構(gòu)，部分互連結(jié)構(gòu)在程序性能些微降低的情況下，面積、功耗等資源開銷大幅減少，并呈現(xiàn)出良好的可擴展性.

關(guān)鍵詞：超長指令字；全互連；部分互連；可擴展性

中圖分類號：TP393 文獻標(biāo)識碼：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

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

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

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

1 程序特征分析

目標(biāo)應(yīng)用程序特征的分析，對于體系結(jié)構(gòu)的設(shè)計具有重要的指導(dǎo)意義.本節(jié)基于全互連網(wǎng)絡(luò)結(jié)構(gòu)來分析目標(biāo)應(yīng)用對互連網(wǎng)絡(luò)的實際使用情況.媒體程序具有可觀的ILP，是VLIW結(jié)構(gòu)的典型應(yīng)用，首先選取此類應(yīng)用的程序特征來研究VLIW功能單元互連網(wǎng)絡(luò)的結(jié)構(gòu)，具有典型意義.

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

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

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

由此我們認為，比起全互連結(jié)構(gòu)，較低通信能力的部分互連結(jié)構(gòu)具有一定的合理性和競爭力.設(shè)計合理的部分互連結(jié)構(gòu)，在保證性能相當(dāng)?shù)那闆r下，可以有效地降低面積、延遲和能耗，同時，預(yù)期具有良好的可擴展性.

2 部分互連結(jié)構(gòu)

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

2.1 部分互連形式

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

2.2 部分互連結(jié)構(gòu)下的通信

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

2.3 部分互連的編譯支持

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

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

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

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

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

3.1 分析模型

3.1.1 面積模型

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

4 結(jié) 論

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

參考文獻

[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.