多核堆棧處理器研究與設計

劉自昂，周永錄，2+，代紅兵，2，劉宏杰，2

(1.云南大學 信息學院，云南 昆明 650500；2.云南大學 云南省高校數字媒體技術重點實驗室，云南 昆明 650223)

0 引 言

Forth語言是一種可交互性開發和易于移植的結構化高級程序設計語言，具有程序小、運行快的特點[1]。Forth語言是以堆棧為核心，所有的操作都基于參數堆棧和返回堆棧，這使得Forth語言在寄存器式處理器上運行會增加的處理器資源消耗，降低Forth程序的運行速度。所以，Forth工程師們開發出了基于堆棧的處理器。堆棧處理器因任務切換快、切換開銷低、資源占用少，可以高效執行Forth程序，并且Forth語言可以為不同硬件平臺快速構建出Forth系統，這些特點使堆棧處理器嵌入式領域取得了成功[2-5]。

在Forth發展的幾十年來出現了多種經典的堆棧處理器，例如，MSL16、EP32、b16[6]、Kalachev實現的Forth軟核[7]等，在嵌入式應用領域里都有良好的表現。隨著嵌入式環境的復雜性日益增高，多任務Forth系統內的實時任務增多，這些實時任務按同優先級時間片輪轉的方式交叉執行[8-10]，在單核堆棧處理器硬件平臺上容易出現低優先級實時任務“餓死”的現象，而多核堆棧處理器可以很大程度上緩解任務“餓死”的問題，因此多核堆棧處理器成為了Forth領域研究的熱點之一。

在國外，GreenArrays公司在2009年后先后推出了GA4、GA32以及GA144片上多計算機芯片，其中，GA144由144個F18A堆棧計算機的二維陣列構成，其指令執行速度高達960億條指令/s，震驚業界[11-13]。在國內，南京航空航天大學何凱成等實現了一個雙核堆棧處理器，該處理器的主核和從核都是其自研的內核，主核負責與其它模塊通信，從核只與主核連接且所有任務都由主核分配，該雙核堆棧處理器的總工作頻率達到了209.8 MHz。

總體上看，國內和國外在多核堆棧處理器的研究上都相對匱乏，目前有據可查的多核堆棧處理器與堆棧片上多處理機僅有上述幾種，它們無論是在原理上還是在體系架構上都存在明顯的不同，其實現及應用也還尚局限于特定的方面。

1 J1堆棧處理器模型

J1是James Bowman等設計的一款基于馮·諾依曼架構的16位單核堆棧處理器模型[14]，其結構如圖1所示。

圖1 J1處理器結構

J1擁有一個參數堆棧D和一個返回堆棧R，這兩種堆棧深度均為32，為方便對堆棧進行操作，James為參數堆棧設置了一個參數堆棧棧頂寄存器T，用來存放參數堆棧棧頂的數據。另外，J1采用雙端口RAM用來存儲Forth系統，每個周期都可以同時讀出一條指令和數據，這種設計方式可以允許J1的訪存操作只需要一個周期即可完成。

J1指令為單周期指令，它具有5種基本指令格式，分別是Literal指令、Jump指令、Conditional Jump指令、Call指令和ALU指令，這幾種指令的結構如圖2所示。其中，ALU指令中有一位剩余空閑保留位，這一位使ALU指令擁有一定的指令擴展能力，但擴展能力十分有限，不能滿足多核環境下對指令的需求。

圖2 J1指令集結構

雖然J1堆棧處理器不支持中斷和異常，不能對突發狀況做出響應，也不支持多任務Forth系統，但是J1的結構簡單，功耗較低且具有較高的性能，適合在它的基礎上設計多核堆棧處理器的內核。

2 L32-MC多核堆棧處理器設計

2.1 L32堆棧處理器模型設計

在J1模型的基礎上，將字長從16位擴展成32位，同時增加了有限狀態機、時間計數器、中斷、指令總線通信模塊、數據總線通信模塊、IO總線通信模塊和臨界資源申請模塊，形成了一種新的32位單核堆棧處理器模型——L32堆棧處理器模型，如圖3所示。

圖3 L32堆棧處理器模型

L32的有限狀態機包括停止態、中斷執行態、普通執行態、訪存態4種狀態，如圖4所示。有限狀態機在停止狀態下，收到時間計數器模塊或內核控制器發來的啟動內核的信號后進入中斷執行態，L32運行中斷服務程序。在中斷執行態下，當中斷服務程序發出內核停止指令時，L32的有限狀態機將進入停止態，此時L32將停止運行。中斷執行態和普通執行態是非常相似的兩個狀態，它們的區別在于中斷執行態是關中斷的普通執行態。當L32處于普通執行態時發生中斷，有限狀態機進入中斷執行態，L32轉入對應的中斷服務程序，中斷服務完畢后，有限狀態機從中斷執行態返回到普通執行態。無論是中斷執行態或者是普通執行態，當L32需要訪問RAM時，有限狀態機進入訪存態，并根據訪問需求向數據、指令或IO總線申請總線使用權，訪問RAM完成后，有限狀態機返回發起總線申請之前的執行態。

圖4 L32堆棧處理器狀態

在L32中，時間計數器模塊用于計時或計數操作，該模塊可以由指令進行控制。在計時完成時，時間計數器會向中斷控制模塊發出中斷信號，中斷控制模塊收到該中斷信號后，立刻使有限狀態機進入中斷執行態。

指令總線通信模塊、數據總線通信模塊和IO總線通信模塊是L32通過指令總線、數據總線和IO總線與其它設備通信的接口。以數據總線通信模塊為例，L32需要訪問RAM中的數據時，數據總線通信模塊使有限狀態機進入訪存態，同時向數據總線發出申請使用信號。數據總線通信模塊獲得數據總線使用權后，將訪存地址通過數據總線送入多端口存儲器中，取得所需數據后，使有限狀態機回到申請數據總線之前的狀態，同時釋放數據總線使用權。指令總線通信模塊和IO總線通信模塊與數據總線通信模塊的通信過程相似。

中斷控制模塊和臨界資源申請模塊在本文2.2部分進行描述。

2.2 L32-MC多核堆棧處理器模型設計

基于L32單核堆棧處理器模型，可以構建出多核堆棧處理器模型L32-MC，其結構如圖5所示。L32-MC多核堆棧處理器模型由多個L32內核、內核控制器、中斷控制器、臨界資源仲裁器、多端口存儲器、數據總線、指令總線、IO總線和外設組等部分構成。

圖5 L32-MC多核堆棧處理器模型

L32-MC多核堆棧處理器模型采用同構內核架構，每個內核都是一個L32單核堆棧處理器，這些L32內核具有完全相同的地位和功能，Forth任務可以在任意一個內核上運行。

L32內核的中斷控制模塊除了響應來自時間計數器模塊的中斷請求，還響應來自中斷控制器的中斷請求。當一個中斷信號到來后，首先保存程序計數器的值(若是核內中斷還會從中斷控制器內獲取中斷服務程序地址)，再將與中斷信號一同到來的中斷服務程序地址送入程序計數器中，使內核轉去執行中斷服務程序，這整個中斷響應過程僅需兩個時鐘周期即可完成。在堆棧深度32時，幾乎所有的Forth任務都不會出現堆棧溢出情況，L32內核的堆棧深度為64，因此L32內核被設計為只能發生一層中斷，即L32內核不支持中斷嵌套。中斷控制器支持16個具有優先級的中斷源，它內有一塊存儲器用來存儲中斷向量表，并提供其它模塊訪問中斷向量表的接口。所有中斷源的中斷服務程序地址都保存在中斷控制器的中斷向量表中，通過Mix指令的中斷功能可以快速修改這些中斷服務程序的地址，使Forth系統在運行時可以對中斷服務程序快速定位和熱更新。當一個中斷源的請求需要被響應時，中斷控制器會通過輪詢的方式選擇一個合適的內核去響應中斷，同時將中斷服務程序的地址送入該內核。

內核控制器是用來控制和存儲處理器中所有L32內核的運行狀態。在內核控制器看來，L32內核的運行狀態只有兩種：運行態和停止態，這兩種狀態都由多任務Forth系統進行控制，當系統中需要更多的內核執行任務時便通過“內核編號”+“內核啟動指令”將停止態的L32內核喚醒，而當系統中只需要較少的內核執行任務時便通過“內核停止指令”將某些運行態的內核停止。

L32內核通過臨界資源申請模塊與臨界資源仲裁器進行通信，這兩個模塊與訪問臨界資源相關的指令配合可以實現各個Forth任務正確訪問臨界資源的功能。本文所述的臨界資源特指Forth系統中一組代表獨享資源數量的系統變量，Forth任務通過臨界資源仲裁器獲得臨界資源的訪問權限才可以改變這些系統變量。當某一個獨享資源的系統變量值為0時，其它任務則不可以訪問該獨享資源。某個Forth任務發出了申請臨界資源訪問權指令時，臨界資源申請模塊向臨界資源仲裁器發出申請信號，臨界資源仲裁器會查詢其內部的狀態存儲器，若狀態存儲器值為0時，表示多任務Forth系統中沒有任務訪問臨界資源，則向申請方發送申請成功信號并修改狀態存儲器值為1，該Forth任務獲得臨界資源訪問權；若狀態存儲器值為1時，表示有其它任務正在訪問臨界資源，則向申請方發送申請失敗信號。釋放臨界資源訪問權時，臨界資源申請模塊向臨界資源仲裁器發出釋放信號，臨界資源仲裁器直接將狀態存儲器值置為0。

2.3 L32-MC指令集設計

L32-MC的指令集沿用參考J1指令集的設計風格，有5種類型的指令，分別是Literal指令、Jump指令、CJump指令、Call指令和Mix指令，每個指令字長均為32位，指令結構如圖6所示。這些指令的操作較為簡單，均可在一個時鐘周期內完成。

圖6 L32-MC指令集結構

指令的第31位為1時表示這條指令為Literal指令，這類指令的0～30位存儲無符號整數，范圍為0～2147483647。Literal指令的功能是將Value送入參數堆棧，并將參數堆棧指針加1。

Jump指令、CJump指令和Call指令的0～28位存儲跳轉目的地址Target，該跳轉地址以字為單位，跳轉范圍為0～1FFFFFFF，尋址方式為直接尋址。

指令的29～31位為011時表示這條指令為Mix指令，這類指令中具有多個位域，每個區域都具有不同的功能，見表1和表2。Mix指令Set位區的功能描述中，tcb寄存器用于存儲Forth任務tcb的首地址，_pc_寄存器用于L32內核進入中斷執行態時存儲當前程序計數器的值，terminal寄存器用于存儲當前Forth任務的任務編號。

表1 Mix指令功能

表2 ALU操作碼及操作

2.4 總線設計

在L32-MC中，數據總線、指令總線和IO總線都采用了Wishbone總線協議。Wishbone總線是一款免費開源的片上總線協議，具有功能強大，復雜度低的特點，它基于主從式架構，擁有高效且規范的信號接口[15，16]。Wishbone總線有多種互聯類型，L32-MC中的Wishbone總線采用共享總線互聯和十字開關互聯。

數據總線用于L32內核與多端口存儲器進行數據上的通信，采用共享總線方式互聯，內部有一個輪詢總線仲裁器。當L32內核需要從多端口存儲器內的RAM讀寫數據時，L32內核中數據總線通信模塊向數據總線申請使用權。數據總線以輪詢的方式對主設備分配數據總線使用權，L32內核的數據總線通信模塊獲得數據總線使用權后，將訪問地址和讀寫標識通過數據總線送入多端口存儲器完成讀寫操作。數據總線的整個操作過程最少需要3個周期。數據總線互聯方式如圖7所示，箭頭虛線表示數據總線仲裁器把數據總線的使用權分配給了L32_0內核。數據總線上所有L32內核為主設備，一個多端口存儲器為從設備。

圖7 數據總線互聯方式

指令總線用于L32內核與多端口存儲器進行指令上的通信，采用共享總線方式互聯，內部有一個輪詢總線仲裁器。指令總線上所有L32內核為主設備，一個多端口存儲器為從設備。L32內核從多端口存儲器內的RAM中獲取指令的操作與通過數據總線從RAM中獲取數據的操作相同。在指令總線中不僅有一套標準的Wishbone信號線用于訪問RAM外，而且為每個L32內核設置了一套用于訪問ROM的專用信號線，每套專用信號線包括一個ROM地址線和ROM數據線。當L32內核不訪問RAM內的指令時，L32內核的指令總線接口會被指令總線內的2路選擇器連接到訪問ROM的信號線。指令總線互聯方式如圖8所示，箭頭虛線表示指令總線的仲裁器把指令總線的使用權分配給了L32_0內核，實線表示內核沒有得到指令總線的使用權時總是與ROM連接。

圖8 指令總線互聯方式

IO總線用于L32內核與外設進行數據上的通信，采用十字開關的方式互聯。IO總線上所有L32內核為主設備，所有外設為從設備。外設分為共享設備和獨占設備，IO總線為每個共享設備都設置了一個輪詢仲裁器，用于對來自L32內核使用申請進行仲裁，而獨占設備則沒有仲裁器，這類設備的使用權通過Forth系統進行分配。L32內核訪問一個共享設備的操作與L32內核通過數據總線訪問RAM的操作相似，在訪問共享設備的過程中需要附帶共享設備的編號，方便IO總線尋找共享設備。Forth任務訪問一個獨占設備前需要在多任務Forth系統中獲取獨占設備的訪問權，然后多任務Forth系統將獲得訪問權的Forth任務編號寫入IO總線內用于存儲獨占設備訪問權的權限存儲器中，每個獨占設備在權限存儲器中都有一塊對應的存儲空間，當一塊存儲空間存儲了一個Forth任務編號時，表示該存儲空間對應的獨占設備被分配給了該Forth任務。在Forth任務訪問獨占設備時，需要將當前Forth任務編號和權限存儲器中對應獨占設備的Forth任務編號進行對比，編號一致時允許該內核訪問申請的獨享設備，編號不一致時不允許訪問。IO總線互聯方式如圖9所示，箭頭虛線表示IO總線內的各個共享外設的仲裁器把設備的使用權分配給了內核，虛線表示運行在該內核上的Forth人物獲得了該獨占外設的使用權。

圖9 IO總線互聯方式

2.5 多端口存儲器設計

一個功能相對完整的32位多任務Forth系統大小約為20 KB左右，完全可以將整個Forth系統放入存儲器之中，因此在本存儲器設計中，未采用從外部存儲器加載Forth系統的形式，而是使用Verilog的系統函數將Forth系統寫入多端口存儲器之中，使整個存儲器模塊復雜性大大降低。作為示意，圖10中給出了雙核模型的存儲器結構。

圖10 雙核L32-MC的多端口存儲器結構

在圖10所示的存儲器結構中有兩個ROM和一個RAM，均采用FPGA雙端口BRAM資源實現。所有ROM大小均為24 KB，地址范圍均是0～17FF；RAM大小為56 KB，地址范圍是1800～4FFF。ROM和RAM存儲器位寬都為32 bit。ROM中存放多任務Forth系統基礎詞的指令和其它必要的數據，RAM則是多任務Forth系統的運行內存。ROM0和RAM的一個端口用作所有L32內核在Forth系統運行中對數據的存取(僅RAM存取，ROM0只讀)，這兩個端口為共享端口，在使用時需要通過數據總線訪問。RAM另一個端口用于所有L32內核讀取RAM中的指令，這個端口為共享端口，在使用時需要通過指令總線訪問。ROM0另一個端口和其它ROM的所有端口用于所有L32內核讀取ROM中的指令，這些端口都為獨享端口，在使用時需要L32內核通過指令總線的專用信號線訪問。每個L32內核都需要占用一個ROM端口，當內核增多后，空閑ROM端口不夠時則需要新增一個ROM。這種ROM設計相當于每個L32內核都有一個獨享的Forth基本系統指令ROM存儲器，L32內核運行Forth基本系統內的程序時都從自己的Forth基本系統指令ROM存儲器中獲取。

3 實驗驗證

L32和L32-MC均采用Verilog HDL進行描述，在Xi-linx XC7A100T FPGA芯片上進行L32單核堆棧處理器和4核、8核的L32-MC多核堆棧處理器的實現，時鐘頻率均為100 MHz，資源使用情況見表3。表中L32-4和L32-8分別代表L32-MC的4核和8核堆棧處理器實現。

表3 FPGA資源使用情況

目前，能夠查詢到的多核堆棧處理器較少，且都未公開具體的實驗數據，也沒有公開處理器源碼及其搭配的Forth系統源碼，故本文所設計的處理器難以與之進行對比與評價。因此，本研究使用自研多任務Forth系統以及測試驗證程序來對L32堆棧處理器和4核、8核的L32-MC堆棧處理器的性能進行驗證測試，并以J1堆棧處理器的性能為基準進行評價。

L32、L32-4和L32-8堆棧處理器運行多任務Forth系統，系統中的多任務調度算法采用多級反饋隊列算法對Forth任務進行調度，J1堆棧處理器則運行單任務Forth系統。在實驗中，J1、L32、L32-4和L32-8的工作頻率均為100 MHz。

為測試驗證L32-MC處理器的任務執行性能，本實驗采用斐波那契數求解、冒泡排序和矩陣乘法3種任務在J1、L32和L32-MC堆棧處理器上運行。斐波那契數任務是使用遞歸的方法求第20個斐波那契數；冒泡排序任務是按從小到大的順序對200個隨機數進行排序；矩陣乘法任務是計算兩個32階矩陣的乘法。為使L32-4和L32-8的各個L32內核都忙碌，在清空多任務Forth系統的所有任務后，分別運行以下測試任務一、二和三。

測試任務一：在J1處理器上，循環執行24次斐波那契數求解任務，得到24次求解任務總執行時間；分別在L32、L32-4和L32-8上，各運行24個斐波那契數求解任務且各任務相互獨立，分別得到24個斐波那契數求解任務總執行時間。

測試任務二：在J1處理器上，循環執行24次冒泡排序任務，取得任務總執行時間；分別在L32、L32-4和L32-8上，各運行24個冒泡排序任務且各任務相互獨立，分別得到任務總執行時間。

測試任務三：在J1處理器上，執行一次兩個32階矩陣乘法任務，得到矩陣乘法的計算時間；分別在L32、L32-4和L32-8上，各運行一個矩陣乘法任務，得到兩個32階矩陣相乘的計算時間，該時間包括各個子任務通信時間。

測試任務一、二和三的總執行時間見表4。

表4 各測試任務執行時間/ms

為測試驗證L32-MC多核處理器的指令執行速度，在Vivado軟件仿真環境下，使L32內核和L32-MC的每個內核上執行一個循環累加任務，不斷獲取每個L32內核運行時的執行時間和執行指令數，再對所獲取的執行指令數求取平均值，可得出L32和L32-MC平均的每秒執行指令數，見表5。

表5 L32-MC平均每秒執行指令數/MIPS

通過表4和表5的實驗數據可知，L32相對于J1的任務執行性能下降了大約20%，指令性能下降0.26%。L32的任務執行性能與多任務Forth的性能有直接關系，由于多任務Forth系統中存在切換任務和時間片大小等原因造成了額外時鐘周期消耗和頻繁的任務切換，直接導致了L32任務執行性能的下降，若多任務Forth系統進一步優化，則L32的任務執行性能會進一步提升；L32處理器在從普通執行態轉換到中斷執行態是需要消耗額外的一個時鐘周期，用于保存當前任務的執行地址，并不執行從多端口存儲器中讀取的指令，造成了指令性能的下降。在功耗方面，L32比J1降低了4%，這是因為FPGA中BRAM資源消耗能源相對較高，而J1處理器無論什么情況下均激活RAM的兩個訪問端口，增加了總體的功耗，而L32針對該問題進行優化，使RAM的兩個端口僅在被需要時進行激活，降低了功耗，另外L32內核使用HDL語言實現時提高了電路的復用性，實現更多功能的同時使用更少的邏輯單元數量，進一步降低了功耗。L32-4在任務執行性能上，相對于J1平均有290%的提升，執行指令性能有395%的提升，功耗僅增加了38%。L32-8在任務執行性能上，相對于J1平均有548%的提升，執行指令性能有791%的提升，功耗僅增加了118%。L32-4和L32-8處理器在執行任務的性能上，均未接近J1的4倍和8倍，原因仍在于多任務Forth系統存在任務切換等必要消耗。在功耗方面，L32-4和L32-8處理器僅增加了L32內核數和存儲器內ROM個數，總線和各類控制器等結構并未改變，所以功耗增加量較少。

上述實驗數據表明了本文在J1堆棧處理器模型的基礎上所設計的L32單核和L32-MC多核堆棧處理器具有更好的綜合性能和功耗表現，滿足高性能低功耗的多核處理器設計目標。

4 結束語

本文以J1堆棧處理器模型為基礎，加入了有限狀態機、中斷、時間計數器等模塊，形成了L32單核堆棧處理器模型。在L32模型的基礎上，對多核結構、指令集、總線、多端口存儲器等方面進行了研究與設計，提出了一種多核堆棧處理器模型L32-MC，在Xilinx XC7A100T FPGA板上實現了該模型4核和8核的堆棧處理器原型，并以100 MHz的時鐘頻率穩定運行。實驗結果表明，L32-MC堆棧處理器的原型機具有良好的綜合性能和功耗表現，為高實時性多核堆棧處理器的研究、設計與應用奠定了良好基礎。