宋奐寰，王樹宗，邵利兵

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

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

宋奐寰，王樹宗，邵利兵

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

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

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

0 引言

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

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

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

1 預(yù)備知識

專用指令集處理器(ASIP)綜合了軟件占優(yōu)和硬件占優(yōu)2類系統(tǒng)的特點(diǎn)，能在微處理器和專用集成電路間進(jìn)行權(quán)衡，提供了嵌入式設(shè)計(jì)的一種良好解決思路;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è)計(jì)單元都要被翻譯為這些RU器件，否則是不可實(shí)現(xiàn)的。粗粒度可重構(gòu)陣列作為協(xié)處理器，嵌入專用指令集處理器，實(shí)現(xiàn)基于粗粒度可重構(gòu)陣列的流水線處理器(見圖1)。

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

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

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

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

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

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

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

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

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

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

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

?

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

2.3 流水線時(shí)鐘周期的計(jì)算

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

上式可改寫為

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

2.4 通信機(jī)制

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

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

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

3 實(shí)驗(yàn)與性能分析

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

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

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

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

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

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

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

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

?

4 結(jié)語

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

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

［1］孫康．可重構(gòu)計(jì)算相關(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］．計(jì)算機(jī)工程與科學(xué)，2009，31(S1)：42－45．

［4］楊君，專用指令集處理器(ASIP)體系結(jié)構(gòu)設(shè)計(jì)研究［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è)計(jì)技術(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ā)實(shí)用教程［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項(xiàng)目資助(613660202);中國博士后科學(xué)基金資助項(xiàng)目(200902668)

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