宋奐寰，王樹宗，邵利兵

(海軍工程大學(xué)兵器工程系，湖北 武漢 430033)

基于可重構(gòu)計算技術(shù)的ASIP設(shè)計與實現(xiàn)

宋奐寰，王樹宗，邵利兵

(海軍工程大學(xué)兵器工程系，湖北 武漢 430033)

為了加速計算密集或數(shù)據(jù)密集類算法，設(shè)計了Kahn線程定義的虛擬指令，以及嵌入式粗粒度可重構(gòu)陣列流水線處理器的體系結(jié)構(gòu)。通過指令流水線設(shè)計，實現(xiàn)虛擬指令的并行執(zhí)行，將指令級并行擴展為線程級并行。系統(tǒng)運行時，采用訂閱/發(fā)布機制作為可重構(gòu)陣列的通信機制，利用可重構(gòu)系統(tǒng)可重復(fù)配置的特點，提高了系統(tǒng)的計算效率。通過仿真實驗驗證了基于可重構(gòu)計算技術(shù)的流水線處理器結(jié)構(gòu)的有效性。

可重構(gòu)計算;粗粒度可重構(gòu)陣列;循環(huán)指令流水線;訂閱/發(fā)布機制

0 引言

可重構(gòu)計算兼顧定制計算的高效性與通用計算的靈活性，是一種新型的時空域計算模式。在可重構(gòu)計算系統(tǒng)中，通過硬件的時域復(fù)用完成復(fù)雜的功能定制和系統(tǒng)任務(wù)。通過設(shè)計合理的重構(gòu)粒度，可以提高硬件的計算能力［1］。

文獻［2］介紹一種粗粒度可重構(gòu)多核協(xié)處理器體系結(jié)構(gòu)，用于加速計算密集或數(shù)據(jù)密集類算法。在該結(jié)構(gòu)中采用具有猜測執(zhí)行機制的循環(huán)自動流水線技術(shù)，將流水線并行執(zhí)行和數(shù)據(jù)驅(qū)動執(zhí)行緊密結(jié)合。采用以循環(huán)程序為單位的固定指令多數(shù)據(jù)流執(zhí)行模式，在循環(huán)執(zhí)行期間，每個單元固定執(zhí)行一種指令，配置信息量減少，支持快速動態(tài)重構(gòu)。設(shè)計了多種特殊數(shù)據(jù)傳遞指令，如非平衡數(shù)據(jù)復(fù)制指令、數(shù)據(jù)選擇指令等，充分利用循環(huán)迭代內(nèi)部、循環(huán)迭代間的數(shù)據(jù)相關(guān)，開發(fā)數(shù)據(jù)重用性，減少對存儲器帶寬的需求。文獻［3］提出了一種數(shù)據(jù)驅(qū)動處理器陣列結(jié)構(gòu)，該結(jié)構(gòu)能有效平衡存儲和計算，適合用于在FPGA上實現(xiàn)高性能的算法加速。

本文設(shè)計了循環(huán)指令流水線和循環(huán)算數(shù)流水線，以數(shù)據(jù)驅(qū)動的方式填充和排空循環(huán)流水線。通過Kahn進程定義的虛擬指令使流水線在嵌入式可重構(gòu)陣列上自動運行。利用可重構(gòu)系統(tǒng)的通信網(wǎng)絡(luò)具有可配置的特點，采用訂閱/發(fā)布通訊機制，靈活地改變網(wǎng)絡(luò)的拓撲結(jié)構(gòu)。

1 預(yù)備知識

專用指令集處理器(ASIP)綜合了軟件占優(yōu)和硬件占優(yōu)2類系統(tǒng)的特點，能在微處理器和專用集成電路間進行權(quán)衡，提供了嵌入式設(shè)計的一種良好解決思路;ASIP可通過定制獲得需要的功能，成為通用處理器和ASIC的替代者［4－5］。粗粒度可重構(gòu)陣列采用 FPGAs或其他可編程硬件，可配置邏輯塊(CLB)是FPGA內(nèi)的基本邏輯單元。若干個功能部件CLB有規(guī)則地組成FPGA邏輯單元陣列結(jié)構(gòu)，形成一個可配置處理單元(RU)，以完成用戶指定的邏輯功能。粗粒度可重構(gòu)陣列以RU為一個可配置單位，RU是硬件向用戶提供的最小編程接口。所有建立在粗粒度可重構(gòu)陣列之上的設(shè)計單元都要被翻譯為這些RU器件，否則是不可實現(xiàn)的。粗粒度可重構(gòu)陣列作為協(xié)處理器，嵌入專用指令集處理器，實現(xiàn)基于粗粒度可重構(gòu)陣列的流水線處理器(見圖1)。

粗粒度可重構(gòu)陣列作為主控處理器的協(xié)處理器，主控處理器用于執(zhí)行控制可重構(gòu)邏輯或執(zhí)行不能被加速執(zhí)行的編程代碼，粗粒度可重構(gòu)陣列作為主控處理器數(shù)據(jù)通道中定制的功能單元使用。當(dāng)主控處理器遇到密集型計算時，向粗粒度可重構(gòu)陣列定制可配置處理單元。可配置處理單元分為用于循環(huán)控制和存儲訪問控制的MPE和用于計算任務(wù)的CPE。處理單元與互聯(lián)網(wǎng)絡(luò)上的路由器相連。接口控制器是連接主控處理器、外部主存儲器和粗粒度可重構(gòu)陣列處理器的橋梁，用于粗粒度可重構(gòu)陣列加載配置信息、以DMA方式在外部主存儲器和內(nèi)部數(shù)據(jù)存儲器之間加載數(shù)據(jù)或讀取結(jié)果，或是主控制處理器向粗粒度可重構(gòu)陣列發(fā)送啟動命令及查詢運行狀態(tài)。

為了最大限度地利用可重構(gòu)硬件，粗粒度可重構(gòu)陣列上的密集型計算必須具備重復(fù)計算的特點，即對于多組輸入數(shù)據(jù)執(zhí)行的操作是相同的，因此本文引進流水線作為粗粒度可重構(gòu)陣列上的任務(wù)單元。

2 粗粒度可重構(gòu)陣列上的流水線

流水線處理器是當(dāng)前指令集處理器設(shè)計中廣泛應(yīng)用的技術(shù)［6］。流水線就是將一個操作分解為一些小規(guī)模的基本操作，并且在基本操作之間增加適當(dāng)?shù)募拇嫫鳎鸦静僮鳟a(chǎn)生的中間值存放在這些寄存器中，并在下一個時鐘周期內(nèi)繼續(xù)運算。在流水線處理器設(shè)計中，要流水化的運算就是每個指令周期所要進行的工作。流水線設(shè)計的主要任務(wù)可以看做是將邏輯指令周期映射到物理機器周期。換句話說，就是將指令周期所對應(yīng)的運算分成一個子運算的序列，由流水線的各段運行。流水線的類型主要分為指令流水線和算術(shù)流水線2種。

2.1 指令流水線設(shè)計

圖1 基于粗粒度可重構(gòu)陣列的流水線處理器Fig．1 Pipeline processor based on coarse-grained reconfigurable array

一個典型的指令周期按功能可以劃分為取址(IF)、譯碼(ID)、取操作數(shù)(OF)、執(zhí)行(EX)和存儲(OS)等5個基本運算分量。指令流水線的設(shè)計任務(wù)是將以上運算分量進行劃分或組合，使模塊執(zhí)行時間均衡，以平衡指令流執(zhí)行時間。指令流水線重復(fù)處理的指令具有不同的指令類型：算數(shù)操作(ALU)、數(shù)據(jù)移動(LOAD、STORE)和指令定序(BRANCH)。統(tǒng)一不同的指令類型，將不同資源需求有效地整合到1條指令流水線中去，使得這條流水線適合于所有的指令類型。整合的目標(biāo)是盡量減少流水線所需要的資源數(shù)，同時盡量提高流水線中所有資源的利用率，整合后的TYP指令流水線［6］如圖2所示。

圖2 TYP指令流水線Fig．2 TYP instruction pipeline

專用指令集處理器根據(jù)指令的相關(guān)性，在可重構(gòu)陣列上定制指令流水線，只要程序計數(shù)器PC所指向的指令地址不為空，就會有指令不斷填充TYP指令流水線。用虛擬指令描述TYP指令流水線的行為，如表1所示。指令流水線所訪問的存儲體采用分層結(jié)構(gòu)，即ALU寄存器、I－cache(專用于存放指令)、D－cache(專用于存放數(shù)據(jù))、外部主存儲器。ALU寄存器、I－cache和D－cache只有1個端口，因此在1個時鐘周期內(nèi)，只能對其執(zhí)行讀(LD)或?qū)?ST)指令之一。多端口的主存儲器在1個時鐘周期內(nèi)即可進行讀操作又可進行寫操作，因此除了執(zhí)行LD和ST指令之外，還可執(zhí)行MM指令。

2.2 算術(shù)流水線設(shè)計

當(dāng)指令流水線ID段解析到循環(huán)體程序時，可以通過流水線向量化算法［7］，將串行執(zhí)行的循環(huán)體展開成可并行執(zhí)行的程序段，然后根據(jù)數(shù)據(jù)流圖，為粗粒度可重構(gòu)陣列定制循環(huán)算術(shù)流水線功能單元。只要循環(huán)未結(jié)束，就會有數(shù)據(jù)不斷填充算術(shù)流水線。用虛擬指令描述算術(shù)指令流水線的行為，如表2所示。

?

表1和表2的虛擬指令有很多是相同的，采用Kahn進程［8］實現(xiàn)這些虛擬指令。將這些虛擬指令映射到基于嵌入式粗粒度可重構(gòu)陣列的流水線處理器中：①LD指令和ST指令根據(jù)接口地址Address_in和Address_out的地址格式在MPE中訪問不同的存儲體;②流水線啟動(G)/關(guān)閉(E)指令、F指令和G與數(shù)據(jù)存儲體緊密相關(guān)，因此它們集中在MPE中實現(xiàn);③用于算術(shù)和邏輯運算的Compute指令集中在CPE中實現(xiàn);④Jump指令根據(jù)給出的地址，更新I－cache的內(nèi)容和程序計數(shù)器PC的值，因為Jump指令與存儲體密切相關(guān)，所以在MPE中實現(xiàn);⑤F，Join與J指令分別采用CPE提供的邏輯運算O=I?L：R和O=L op R來實現(xiàn)。

2.3 流水線時鐘周期的計算

時鐘是流水線執(zhí)行的控制器，也是流水線深度的決定因素之一。流水線的時鐘周期也叫機器周期。流水線的每一級是由1組組合邏輯電路F和1個寄存器組成。在實現(xiàn)過程中，為減少信號的傳輸延遲和節(jié)約邏輯資源，這個寄存器通常由CLB單元中的觸發(fā)器D實現(xiàn)。定義TM為通過F的最大傳輸延遲，即通過最長信號路徑的延遲;Tm為通過F的最小傳輸延遲，即通過最短信號路徑的延遲;TD為正確建立時鐘信號所需要的額外時間，包括必要的建立和保持時間，以保證正確的鎖存，同時還包括可能的時鐘扭曲，即到達不同觸發(fā)器的時鐘沿的最大時差。假設(shè)1組信號X1自T1時刻作用在流水線某一級的輸入端，那么F的輸出最遲將在T1+TM時刻有效，要保證D的正確鎖存，F(xiàn)的輸出信號在T1+TM+TD時刻必須仍然有效。當(dāng)?shù)?組信號X2自T2時刻作用在F的輸入端時，最快只要到T2+Tm時刻就能傳到鎖存器L。要保證第2組信號不覆蓋第1組信號，必須滿足公式［9］：

上式可改寫為

其中：T2－T1為最短時鐘周期。因此流水線的時鐘周期T必須比TM－Tm+TD大，最大時鐘頻率不能超過1/T。

2.4 通信機制

訂閱/發(fā)布通信機制由生產(chǎn)者、消費者和事件通知服務(wù)組成［9］。生產(chǎn)者和消費者分別是對產(chǎn)生事件對象和消費事件對象的統(tǒng)稱，事件通知服務(wù)即通常意義上的訂閱/發(fā)布中間件。消費者以訂閱的方式向事件通知服務(wù)注冊，表達對特定事件的興趣，生產(chǎn)者發(fā)布事件到事件通知服務(wù)，并將生產(chǎn)的數(shù)據(jù)送到數(shù)據(jù)池中。事件通知服務(wù)充當(dāng)生產(chǎn)者和消費者的中介，負責(zé)訂閱的管理，根據(jù)訂閱過濾事件，并以通知的形式發(fā)送事件到感興趣的消費者，消費者收到通知后，從數(shù)據(jù)池中取出所需的數(shù)據(jù)，如圖3所示。

圖3 訂閱/發(fā)布通信模型示例Fig．3 Examples of communication model

核即是訂閱/發(fā)布機制的生產(chǎn)者/消費者。由于訂閱/發(fā)布系統(tǒng)具有松耦合、匿名、多對多通信和可擴展的特點，符合粗粒度可重構(gòu)陣列的通信網(wǎng)絡(luò)是可配置的要求，因此是基于嵌入式粗粒度可重構(gòu)陣列的流水線處理器體系結(jié)構(gòu)理想的通信模式。數(shù)據(jù)存儲體(塊RAM，觸發(fā)器，用于數(shù)據(jù)存儲的查找表)充當(dāng)數(shù)據(jù)池的角色。粗粒度可重構(gòu)陣列內(nèi)嵌有數(shù)字時鐘管理模塊。將時鐘頻率不同的設(shè)計劃分到不同的時鐘區(qū)域，通過異步FIFO以及雙口RAM為不同的時鐘區(qū)域建立不同的數(shù)據(jù)池，設(shè)計轉(zhuǎn)發(fā)器實現(xiàn)不同數(shù)據(jù)池間數(shù)據(jù)的傳輸，這樣可避免信號直接跨越不同的時鐘域并在一定程度上化解流水線相關(guān)。Xilinx提供了片上RAM，特別是大量的塊RAM，可以配置成雙口RAM或ROM，它們存儲量大、速度快且不占邏輯資源［10］。將這些塊RAM資源以數(shù)據(jù)池的形式分配給時鐘頻率相同的可配置的處理單元，當(dāng)某個核所需的初始數(shù)據(jù)在數(shù)據(jù)池中被初始化后，該核自動被啟動執(zhí)行。若干個核同時配置到粗粒度可重構(gòu)陣列空間，就形成了循環(huán)流水的自動執(zhí)行，提高了數(shù)據(jù)的吞吐率和并發(fā)程序的執(zhí)行效率。

3 實驗與性能分析

基于可重構(gòu)計算技術(shù)的ASIP的軟件實驗環(huán)境包括 Modelsim SE 6.5， Simulink， Xilinx System Generator(系統(tǒng)生成環(huán)境)和Xilinx ISE 9.1i(系統(tǒng)綜合環(huán)境)，硬件實驗環(huán)境包括Xilinx公司的大容量FPGA芯片 Virtex4xc4vsx35-10ff668，32MB SDRAM和PCI橋。

首先，通過PCI橋?qū)PGA芯片與主控處理器相連，SDRAM與FPGA間有64位數(shù)據(jù)通路。該實驗平臺能運行應(yīng)用程序并提供時鐘準確的運行結(jié)果。其次，用Verilog硬件描述語言實現(xiàn)粗粒度可重構(gòu)陣列的體系結(jié)構(gòu)。用模塊實現(xiàn)自定義的IP核(MPE核、CPE核)，用雙口RAM實現(xiàn)1個系統(tǒng)周期同時讀出2個數(shù)據(jù)。

用本文提出的思想，在嵌入式粗粒度可重構(gòu)陣列的流水線處理器實驗平臺上實現(xiàn)邊界檢測算法，過程如下：

步驟1 在流水線處理器上執(zhí)行高級語言程序。高級語言程序的每一條語句依次通過圖2所示的TYP流水線。當(dāng)解碼得到的指令為循環(huán)指令時，進入步驟2。

步驟2 將循環(huán)程序轉(zhuǎn)換成用虛擬指令表示的偽代碼。將循環(huán)程序利用表1和表2所示的虛擬指令轉(zhuǎn)換成偽代碼。

步驟3 畫出虛擬指令表示的偽代碼數(shù)據(jù)流圖。

步驟4 使用Simulink，Xilinx System Generator以及IP核實現(xiàn)步驟3的數(shù)據(jù)流圖。由于該段程序不存在流水線相關(guān)，所以這個3級流水線使系統(tǒng)的吞吐率提高了3倍;利用粗粒度可重構(gòu)陣列上的塊RAM，有效地緩解了讀取存儲器的瓶頸問題。

步驟5 利用Xilinx ISE進行設(shè)計綜合。由主控處理器通過PCI總線寫入FPGA芯片，最終邊界檢測算法在基于可重構(gòu)計算技術(shù)的ASIP上運行，循環(huán)流水線占用FPGA資源情況如表3所示，可見基于可重構(gòu)計算技術(shù)的ASIP設(shè)計方法在計算速度和占用資源方面的有效性。

?

4 結(jié)語

本文的創(chuàng)新點有：將可重構(gòu)計算技術(shù)應(yīng)用于ASIP實現(xiàn)集成電路的定制;在可重構(gòu)陣列上引入流水線技術(shù)，實現(xiàn)指令的并行執(zhí)行;采用訂閱/發(fā)布通信機制實現(xiàn)并行任務(wù)間的通信。具體方法有：采用Kahn進程定義虛擬指令，在專用指令集處理器上執(zhí)行。通過虛擬指令在循環(huán)流水線上的并行執(zhí)行實現(xiàn)了Kahn進程的并行執(zhí)行。粗粒度可重構(gòu)陣列既可以執(zhí)行循環(huán)算術(shù)流水線，執(zhí)行數(shù)據(jù)密集或計算密集類算法，又可以執(zhí)行循環(huán)指令流水線，執(zhí)行指令的取指、譯碼、取操作數(shù)、執(zhí)行和存儲等操作。體系結(jié)構(gòu)采用模塊化設(shè)計，為循環(huán)流水線設(shè)計的可配置處理單元是最小的資源分配單位，采用多種可配置指令，實現(xiàn)了虛擬指令的功能。訂閱/發(fā)布通訊機制使得分布在粗粒度可重構(gòu)陣列之上的各個處理單元擁有靈活的拓撲網(wǎng)絡(luò)結(jié)構(gòu)和共享的數(shù)據(jù)池，當(dāng)某處理單元所需的數(shù)據(jù)準備完畢后，由數(shù)據(jù)驅(qū)動流水線自動執(zhí)行。實驗結(jié)果驗證了基于可重構(gòu)技術(shù)的ASIP方法的可行性與有效性。

圖4 使用Simulink，Xilinx System Generator實現(xiàn)數(shù)據(jù)流圖的仿真程序Fig．4 Simulation program of data flow diagram in Simulink，Xilinx System Generator environment

［1］孫康．可重構(gòu)計算相關(guān)技術(shù)研究［D］．杭州：浙江大學(xué)，2007．

［2］竇勇，鄔貴明，等．支持循環(huán)自動流水線的粗粒度可重構(gòu)陣列體系結(jié)構(gòu)［J］．中國科學(xué)，2008，38(4)：579 －591．

［3］鄔貴明，竇勇，等．面向數(shù)據(jù)驅(qū)動處理器陣列的自動綜合［J］．計算機工程與科學(xué)，2009，31(S1)：42－45．

［4］楊君，專用指令集處理器(ASIP)體系結(jié)構(gòu)設(shè)計研究［D］．合肥：中國科技大學(xué)，2006．

［5］KEUTZER K，MALIK，S，NEWTON A R．From ASIC to ASIP：the next design discontinuity［C］．Proceedings of the 2002 IEEE International Conference on Computer Design：VLSI in Computers and Processors，2002.84 －90．

［6］SHEN J P，LIPASTI M H．現(xiàn)代處理器設(shè)計技術(shù)［M］．北京：電子工業(yè)出版社，2004.24－61．

［7］WEINHARDT M，LUK W．Pipeline vectorization［J］．IEEE Transactions on computer-aided design of integrated circuits and systems，2001，20(2)：234 －248．

［8］KAHN G．The semantics of a simple language for parallel programming［C］．Proceedings of the IFIP Congress，North-Holland，1974.471－475．

［9］施東材．基于對等網(wǎng)絡(luò)的語義發(fā)布/訂閱系統(tǒng)的關(guān)鍵技術(shù)研究［D］．杭州：浙江大學(xué)，2007．

［10］田耘，徐文波．Xilinx FPGA開發(fā)實用教程［M］．北京：清華大學(xué)出版社，2008.3－105．

Design and realize for ASIP based on reconfigurable computing

SONG Huan-huan，WANG Shu-zong，SHAO Li-bing
(Department of Weapon Engineering，Naval University of Engineering，Wuhan，430033，China)

In order to accelerate algorithm of computation-intensive and data-intensive，virtual instructions designed by Kahn thread and pipeline processor for embedded coarse-grained reconfigurable array are introduced．Instruction-level parallelism is extended to contain thread-level parallelism by design of instruction pipeline．Communication of reconfigurable array adopts subscribe/published mechanism．Finally，the simulation result validates the architecture of pipeline processor．

reconfigurable computing;ASIP;cycle pipline;subscribe/published mechanism

TP314

A

1672－7649(2012)05－0078－05

10.3404/j.issn.1672－7649.2012.05.018

2011－08－08;

2011－09－06

國防973項目資助(613660202);中國博士后科學(xué)基金資助項目(200902668)

宋奐寰(1983－)，女，博士研究生，從事可重構(gòu)技術(shù)與故障處理研究。