一種指令級動態可重構浮點處理器設計

聶言碩, 張多利, 孟曉飛, 魏 可, 宋宇鯤

(1.合肥工業大學 電子科學與應用物理學院,安徽 合肥 230601; 2.合肥工業大學 教育部IC設計網上合作研究中心,安徽 合肥 230601)

在高密度計算領域,應用程序中存在大量的數據級并行(data level parallelism,DLP),目前單指令多數據流(single instruction multiple data,SIMD)技術常用來提高處理器執行高DLP程序的速度。向量處理器屬于Flynn分類法中SIMD類并行計算機[1],以多處理單元空間并行的方式加速數據密集型應用,但數據訪存開銷大和能耗高是SIMD類處理器的特點,減少數據訪存是SIMD類處理器的一項重要研究工作。

在指令層,運算表達式通常被拆分為若干與基礎指令對應的基礎運算,這些基礎運算產生的中間數據仍需要進行存儲和加載過程,而在硬件中實現復合運算可以減少冗余的中間數據訪存。一種實現復合運算的方式是通過合并多個數據流圖(data flow graph,DFG)創建一個可重構的復合電路[2],但復合電路的通用性較差。復合運算的另一種實現方式是具有高計算吞吐量、高能效和硬件可編程等優點的粗粒度可重構架構(coarse grained reconfigurable architecture,CGRA)。傳統的CGRA以配置流和數據流為驅動[3],基于任務調度可重構陣列的計算,適合執行無控制分支且具有大量指令級并行的程序[4]。

因為本課題組研究的異構多核系統面向高密度計算領域,但其集成的浮點處理器仍有執行控制密集型和非規則尋址模式任務的需求,所以該處理器存在高性能和高適用性的雙重需求。基于這2種需求的折衷,本文設計了一種指令級動態可重構浮點處理器(dynamically reconfigurable floating-point processor,DRFP),該處理器以指令流和數據流為驅動,既能夠從指令流驅動中獲得靈活性,又能夠從數據流驅動中獲得高能效。本文提到的融合指令指靜態層面的融合,即融合指令顯式地指明生產者指令與消費者指令間的數據依賴關系。每條融合指令對應復合運算中的一條基礎運算,實現一條完整流水線路徑(復合功能單元)的若干條融合指令稱為融合指令簇。

1 相關工作

已有CGRA的研究工作集中在整型計算領域,特別是有高密度計算需求的應用領域[5]。傳統的可重構處理器MorphoSys[6]以配置流和數據流為驅動,在軟件層對應用程序優化后提取出用于重構硬件的配置信息。區別于MorphoSys,本文引入了一種基于融合指令的實現方式。

文獻[7]提出了融合指令鏈的概念,鏈中的每條指令只與序列中的下一條指令通信,并且鏈之間不交錯操作,鏈之間通信需要旁路寄存器提供支持。相比于文獻[7],本文使用多條融合指令組成“樹形”結構的融合指令簇,并將指令簇映射至可重構線性陣列,從而具有連續數據流驅動的運算能力。

RGFA[8]是本課題組已有的研究工作,其以指令流為驅動,具備動態重構的能力。相比于RGFA,本文使用較小規模的互連網絡實現了若干基礎功能單元間的直接互連。另外相比于RGFA在軟件層面規避并行執行的路徑間的數據沖突,DRFP能夠在運行時自動地檢測并解決這種數據沖突。

2 DRFP的架構及設計

DRFP的整體結構如圖1所示。

DRFP由指令解析單元(instruction analysis unit,IAU)、指令發射單元(instruction launch unit,ILU)、可重構浮點單元(reconfigurable floating-point unit,RFU)、存儲器管理單元(memory manage unit,MMU)和寄存器文件(REGFILE)5個主要模塊組成,通過數據網絡接口(data net interface,DNI)與多核系統的片上網絡通信,其作為協處理單元與通用處理器(RISC-V)緊耦合。RISC-V是整個處理器的控制核心,主要執行程序中的分支控制和整型計算,浮點計算在DRFP上執行。IAU接收RISC-V發送的重構指令,對部分重構指令進行相關性解析,并將相關的多條指令動態融合。ILU負責指令到配置的動態轉換以及訪存通道的建立。RFU是DRFP的計算核心,由異構的基礎功能單元(basic functional unit,BFU)陣列組成。MMU為RFU提供了4個讀通道和4個寫通道。MMU的地址生成單元(address generating unit,AGU)負責多端口存儲器(MEM)的讀寫,具有連續的數據流讀寫能力。REGFILE包括一些通用寄存器和訪存相關的特殊寄存器等。

2.1 重構指令

DRFP有2種重構指令:一種是普通指令,其不包括指令間的相關性信息,IAU能夠動態地融合多條相關的普通指令;另一種是融合指令,其靜態地指定指令間的相關性。融合指令不會被IAU解析,其與前序指令的相關性信息已在指令中明確指出。分支附近常存在一些運行時才能確定的數據相關關系,融合指令無法靜態地指定這種相關性,動態解析指令相關性的目的是為了彌補這一點。

重構指令的編碼格式如圖2所示。當普通指令或融合指令的某一源或目的操作數為存儲器時,該操作數的尋址地址根據RFGFILE中的某些特殊寄存器確定,這些寄存器能夠提供的信息包括訪存首地址、步進值和訪存次數。如果一條融合指令的源數據來自于前序指令,那么該源數據的sd-type設置為存儲器類型,pin編碼為非0值(pin為0表示該源數據來自于存儲器)。

2.2 可重構浮點單元

浮點計算適用異構陣列。大多數CGRA通常采用同構的可重構單元,每個基礎單元包括一個算術邏輯單元(arithmetic and logic unit,ALU)[5],這種使用同類硬件資源的結構易于實現大型計算的映射[9]。相較于整型計算,浮點計算硬件實現的規模較大,并且各種浮點指令的使用頻率存在很大差異。如果每個基礎單元包括所有的浮點計算功能,那么在資源效率方面不是好的選擇。

互連靈活性決定了異構陣列映射的難易程度,應作為互連網絡設計時主要考慮的技術點。在小型的異構陣列中,因為過往的工作通常采用交叉開關網絡將所有的基礎單元直接互連,但交叉開關網絡的規模隨結點數呈指數式擴張,所以可擴展性較差[5]。

基于互連靈活性和網絡可擴展性的雙重需求,本文設計了一個使用多總線網絡將所有基礎單元直接互連的可重構浮點單元。RFU的結構如圖3所示。SPECfp2006中5種基本浮點算術指令的百分比見表1所列[10]。根據表1中各種指令的使用比例確定RFU內BFU的種類和數量,見表2所列。每個BFU具有一種或多種基礎功能,通過一個總線接口(bus interface,BIf)掛載在多組輸入、輸出總線上,只要通信不相交,每個總線都可建立多個通信。不同BFU的計算延遲各異,數據中轉站(data hub,DHub)用于BFU間的數據同步。DHub在所有BFU間共享,當某個DHub被釋放后,該DHub可被再次使用。RFU使用valid & ready協議實現下游消耗部件與上游生產部件之間的數據握手,使用eof標志數據流的結束,已激活的BFU、DHub和總線在eof有效時釋放。

表1 SPECfp2006中5種基本浮點算術指令百分比

表2 RFU內BFU的種類和數量 單位:個

相較于RGFA所采用的交叉開關網絡,本文中的互連網絡具有較小的規模和可擴展性。同樣實現N個BFU的直接互連,交叉開關網絡需要N條輸出總線和N×N條輸入總線,多總線網絡需要M條輸出總線和M×N條輸入總線,其中M為DHub的個數。本文分析了雷達成像、矩陣求解和空間譜估計等算法,發現通常沒有將表2中所有BFU同時互連在一條或多條流水線路徑中的需求,又由于DHub動態分配的緣故,N/2個DHub就能滿足大多數情況下的互連需求,該種情況下多總線網絡的規模只有交叉開關網絡規模的1/2。

2.3 動態重構

本文提到的動態重構表征的是指令到配置的動態轉換,這個轉換過程有賴于DHub分配表、DHub狀態表、BFU狀態表和訪存通道狀態。

本文硬件層的依賴關系通過DHub分配表構建。每條非路徑終點的融合指令都會被分配一個DHub用于暫存所屬指令的計算結果,該DHub的編號被寫入到DHub分配表寫指針所指向的位置。后續融合指令將根據pin去讀取DHub分配表,從而確定其依賴數據存放的DHub。

特別地,DHub分配表寫指針的行為如下:在路徑起點,寫指針指向首地址;每當分配一個DHub,寫指針向下移動一個位置;在路徑終點,寫指針重新指向首地址;當路徑還未到達終點時,如果分配表的最后一個表項已被使用,那么寫指針重新指向首地址。在理想情況下,如此重復地利用分配表可以實現無限長路徑的構建。

融合指令簇內的指令同樣按指令發射的順序循環編號。當同一簇內存在多個相同編號的指令時,如果指令在編號時不存在約束條件,那么在運行時就有可能構建錯誤的相關關系。指令在編號時應滿足的約束條件如下:所有編號小于等于當前指令編號的上一輪指令已經與簇內已編號或當前編號的指令構建相關關系。

指令到配置的動態轉換由重構控制器管理,在滿足指令發射條件時進行。指令發射條件為:

(1) 當前待發射指令所需的BFU至少有一個空閑。

(2) 如果當前待發射指令不是路徑的終點,那么至少有一個DHub空閑。

(3) 當前空閑的讀通道數大于等于當前待發射指令所需的讀通道數。

(4) 如果當前待發射指令有數據寫回需求,那么至少有一個寫通道處于空閑狀態。

當以上條件都滿足時,在T周期,重構控制器將待發射指令轉換成配置,分配和建立指令所需的數據訪存通道,記錄指令被分配的DHub編號,以及從指令隊列中彈出下一條指令;在T+1周期,配置驅動到RFU的配置總線上(發射指令)以實現1個BFU的重構;在T+2周期BFU開始計算。

任務劃分與RFU的動態重構過程如圖4所示。

因為目前RFU不支持一對多數據通信,所以數據流圖中一對多數據通信的節點為指令簇劃分的邊界。圖4a中類似于“樹形”結構的指令簇1使用了9條融合指令。圖4b中BFU的調度優先級從高到低依次為:BFU1、BFU2、BFU0,BFU3、BFU4;DHub的調度優先級為編號越小優先級越高。圖4b最右側標記了指令發射的時刻。最先重構的Path-1與Path-3同時撤銷,在Path-1之后重構的Path-2先于Path-1撤銷,多條路徑并行執行所牽涉的數據沖突將在下節介紹。

2.4 數據沖突的解決策略

RFU同時執行多條路徑相較于一條路徑能夠提升處理器的性能,但多條路徑同時執行需要解決路徑間的數據沖突。指令發射條件沒有考慮多條路徑在執行時是否存在數據沖突,并且數據沖突也沒有在軟件層規避,如果硬件中也沒有考慮數據沖突的化解,那么多條路徑可能以錯誤的順序訪問同一存儲器地址或寄存器,這會導致計算錯誤,甚至程序崩潰。

多路徑并行執行時的3種數據沖突如圖5所示。

圖5中:Path_n的n為路徑優先級,n越小路徑優先級越高;src為路徑的源數據;dst為路徑的目的數據。RAW沖突,即低優先級路徑正在訪問高優先級路徑未寫回的地址范圍;WAR或WAW沖突,即低優先級路徑正在訪問高優先級路徑未訪問的地址范圍。

本文多路徑亂序執行的數據沖突由各訪存通道根據通道優先級自行地檢測和解決。路徑間的數據沖突實際上是各訪存通道間的數據沖突,只要確定了各訪存通道的優先級,各訪存通道可以明確對同一存儲器地址或寄存器的訪問順序。因為訪存通道優先級與所屬路徑優先級一致,所以本文根據路徑的建立和撤銷情況為每個訪存通道進行動態標識,從而確定各訪存通道的優先級。某一通道優先級動態標識的偽代碼如下:

if this channel is established then

if a full path undo then

priority=complete-path-num-undo-path-num;

else

priority=complete-path-num;

end if

else if a full path undo then

priority=priority-undopri-gt-thispri-num;

else

priority=priority;

end if

初始時刻,通道的priority為0,這代表最高優先級;此后,當該通道建立時,priority需要根據當前存活的完整路徑數和正在撤銷的路徑數確定;當路徑撤銷時,priority需要根據撤銷路徑中路徑優先級大于該通道優先級的路徑數目確定。

RAW沖突在讀通道中檢測和解決,WAR或WAW沖突在寫通道中檢測和解決。當讀通道的訪存地址與寫通道發生RAW沖突時,數據讀取被暫停;當寫通道的訪存地址與讀通道發生WAR沖突或與其他寫通道發生WAW沖突時,數據寫回被暫停。

各訪存通道能夠自行地檢測和解決并行執行的路徑間的數據沖突,從而使得DRFP具有多路徑亂序執行和寫回的能力。

3 實驗與性能測試

DRFP作為主要計算核心集成于異構多核系統芯片上,并在Xilinx Ultrascale系列xcvu440的FPGA芯片上進行了原型驗證,系統可以穩定工作在120 MHz。為了評估DRFP相較于通用處理器的性能,本文將相同的計算任務加載到CPU(R5 3500U)與DRFP上,并在它們之間作頻率歸一化對比。

為了對比不同類型任務在DRFP上的加速效果,本文將多種類型的任務加載到DRFP上,并分別分析它們的加速效果。

矩陣運算的加速效果如圖6所示。任務1～任務7依次為:2個16階矩陣乘、2個32階矩陣乘、32×64矩陣與64×32矩陣乘、2個64階矩陣乘、64×16矩陣協方差、64×64矩陣協方差、256×16矩陣協方差。從圖6可以看出,同屬于計算密集型應用的矩陣乘和協方差在DRFP上可以得到較好的加速。當矩陣規模變大時,加速比增加,這是由于乘累加操作的數據流長度增加對計算流水線有利。32×64矩陣與64×32矩陣乘的加速比與2個64階矩陣乘的加速比一致,協方差計算中64×16矩陣的加速比與64×64矩陣的加速比一致,它們都是由于乘累加的數據流長度沒有變化,僅乘累加次數的變化對加速比沒有影響。

快速傅里葉變換(fast Fourier transform,FFT)被廣泛應用于現代信號處理、數字通信及圖像處理等實時處理領域[11],適合使用專用硬件進行加速。

FFT的加速效果如圖7所示。因為本文可重構硬件的規模較小,FFT算法只能逐級映射到DRFP上,而每一級蝶乘都能使用計算流水線,所以FFT算法仍可以得到較好的加速。

雅克比算法(求矩陣特征值/特征向量)是一種控制復雜度較高的應用,常用于空間譜估計和機器學習中的數據降維。雅可比算法的加速效果如圖8所示。雅克比算法的特點如下:當階數變大時,確定旋轉矩陣的時間占總任務時間的比例減少,旋轉操作的時間占總任務時間的比例相應增加。因為旋轉操作能使用計算流水線,所以當階數較大時,雅克比算法更適合在DRFP上加速。

任務加速效果與尋址規則度的關系如圖9所示。任務1～任務10依次如下:16 384點加、16 384點乘、16 384點復數取模、4 096點點積、4 096點FFT、64階實矩陣乘、64階復矩陣乘、64×16矩陣協方差、多重信號分類(multiple signal classification,MUSIC)[12]算法和32階雅克比。

從圖9可以看出,因為任務的加速效果基本遵循尋址規則度越高加速效果越好的規律,所以尋址規則度越高的應用越適合在DRFP上執行。FFT第1級蝶乘的地址可以使用反向加法器生成,第1級蝶乘也能使用計算流水線。

因為4 096點FFT的數據流長度最小為64,最大為2 048,而64階矩陣運算的數據流長度為64,所以4 096點FFT的尋址規則度較64階矩陣運算高。因為取模運算的開平方只能單路執行,而乘法運算可以兩路并行,所以乘法的加速效果比復數取模好。

以上實驗表明DRFP執行尋址模式規則的計算密集型和數據密集型任務具有較高的性能。為了證明DRFP在兼顧高性能的同時相較于已有工作能更好地適應非規則運算,本文將文獻[8]中的任務映射到DRFP上。同一任務在DRFP與RGFA[8]上的執行周期見表3所列。從表3可以看出,除復乘和包含復乘的FFT之外,DRFP較RGFA具有明顯的性能優勢。特別地,DRFP在兼顧高性能的同時相較于已有工作還能更好地加速雅克比算法(非規則運算)。

表3 同一任務在DRFP和RGFA上的執行周期和加速比

4 結 論

針對高性能計算中存在非規則尋址模式任務的加速需求,本文設計了一種具有動態重構和亂序執行能力的浮點處理器,基于融合指令實現的可重構處理器,以指令流和數據流為驅動,在兼顧高性能的同時相較于已有工作能夠更好地適應非規則運算,實驗結果較好地印證了這一點。