面向機器學習的高性能SIMT處理器cache的設計與實現

許曉燕 李 濤 孫 哲 邢立冬

(西安郵電大學電子工程學院 陜西 西安 710121)

0 引 言

隨著大數據時代的到來，機器學習已經應用到人類生活的各個方面。機器學習的本質是基于互聯網的海量數據以及系統強大的并行運算能力，讓機器自主模擬人類學習的過程，通過不斷“學習”數據來做出智能決策行為[1]。為了解決機器學習中大數據、并行運算需求，本文基于SIMT架構進行設計。SIMT概念首先被GPU制造商NVIDIA在產品微架構中提出[2]。2006年11月，NVIDIA在其Tesla GPU架構中提出了一條指令同時驅動多個不相關線程的SIMT處理方式[3]。隨后不久，ATI公司在2007年推出了采用類似處理架構的TeraScale引擎，及相關產品R600 GPU芯片[4]。SIMT架構具有多個執行流程[3]，可以利用多線程隱藏存儲延時，減少取指、取數開銷，而且執行時不需要將數據湊成合適的矢量長度，便可以進行運算，更有利于適應機器學習處理大規模數據的要求。

本文基于自主研發的SIMT架構進行設計，為了解決SIMT處理器與主存速度不匹配問題[5]，設計使用cache來改善它們之間的性能。目前cache設計有普林斯頓、哈佛兩種結構。普林斯頓結構將指令cache與數據cache統一存放，哈佛結構將指令cache和數據cache分開存放[6]。哈佛結構相對普林斯頓結構有利于解決指令和數據沖突的問題，便于指令cache與數據cache的并行執行，方便對指令cache和數據cache的優化，因此cache設計中普遍使用哈佛結構。本設計采用哈佛結構，并根據指令cache、數據cache的局部性和連續性[7]，為指令cache、數據cache設置不同的參數；根據設計需求為cache設計了可配置的替換算法，包括輪詢、LFU(least frequently used)、LRU(Least Recently Used)和專用的偽LRU替換算法。本文重點介紹基于自主研發的SIMT架構的cache設計與實現。

1 SIMT處理器架構

該SIMT處理器最多可以包含4個區塊，每個區塊可以執行相同或不同的程序；每個區塊包含8個warp,最多可以有8個warp都處于激活狀態，但每次只有一個warp可以執行，同一個區塊中的warp執行相同的程序；每個warp包含8個PE,可以通過線程真假控制PE的執行，每個PE執行相同的指令。運行程序可以通過配置區塊個數、warp個數、初始pc、初始寄存器、替換算法有效地控制程序的執行。

該SIMT架構由8個PE(Processing element),1個VPU(Vector processing unit),1個MMU(Memory management unit)和1個AXI總線接口四部分組成。PE主要用于完成各類運算，VPU主要用于完成取指、譯碼、warp調度功能，MMU主要用于與處理器相關的指令、數據的存取，AXI總線接口用于實現AXI總線與MMU模塊的交互。其中MMU包含分開的指令cache、數據cache、共享ram和mem_ctrl模塊。icache模塊主要滿足流水線對指令訪問的需求，dcache模塊主要滿足流水線對數據訪問的需求，mem_ctrl模塊主要負責SIMT處理器的訪存請求，data_ram用于8個PE共享數據的訪存。SIMT整體架構如圖1所示。

圖1 SIMT整體架構

2 基于SIMT處理器cache設計

2.1 指令cache結構設計

指令cache用于接收通過mem_ctrl模塊透傳過來的由取指單元傳送的請求信號，用于觀察所需的指令是否在對應的RAM中，若是，則將對應的指令輸出給取指模塊，否則向總線接口模塊發出對應的請求信號，總線接口模塊返回對應的指令時，填充對應的RAM,同時在填充完畢時，將對應的指令輸出。指令cache分為cache的存儲模塊，控制模塊、替換算法模塊三部分。指令cache的整體結構如圖2所示。

圖2 指令cache整體結構

2.1.1存儲模塊

存儲模塊用于存儲可供處理器運行的指令和標志。根據SIMT設計需求，指令cache大小設計為8 KW(32 KB),采用16路組相聯，行大小為128字節。由于指令cache采用16路組相聯，本設計將存儲矩陣設計為16塊指令存儲體和16塊指令TAG存儲體，它們各自都具有相同的結構。其中，指令存儲體每塊大小為2 KB(分成4行，每行有512個字節)，總共為32 KB。指令TAG存儲體每塊分成4行，每行有22位。根據給定指令cache的各個參數，可以確定地址的8～0為地址偏移位；地址的10～9為地址的索引位；地址的31～11為tag位。訪問地址組成如圖3所示。

圖3 訪問地址組成

inst_ram在實際存儲時，將同一路的數據存儲于同一個RAM中，并且將行內偏移地址與索引統一編址。用index位來選擇cache的行索引，用offset位來選擇行內的偏移。每行存儲128條指令，共4行，每個inst_ram深度為512。

tag_ram中的tag位用來記錄每行在主存中的位置，tag另一個作用就是與SIMT處理器發出的請求指令的地址進行比較，來確定當前cache行中的指令是不是處理器所需要的指令，使用tag存儲體中的高21位表示。tag_ram中的第0位作為有效位用來記錄當前cache行中的指令是否有效，每行都有一個有效信號，每個tag_ram深度為4。

2.1.2控制模塊

icache控制模塊用于控制整個icache的執行，實現cache的三級流水，同時接收取指模塊的請求，最終輸出對應的指令、對應指令的pc值、warp號碼、sign標記(標記jump、call、retn指令)。

第一級流水線：根據mem_ctrl模塊透傳過來的塊號，從對應的4個基地址中選擇對應的值，然后將該值與對應pc值相加，即為所需指令的地址。同時根據控制信號(rd_en)和地址的2～10位，從16路inst_ram中分別取出對應地址的指令；根據控制信號(rd_en)和地址的9～10位，從16路tag_ram中分別取出對應地址的tag。判斷新進來的指令與前一個指令是否在同一行(line)，并將對應的地址寄存，用于下一級指令命中的判斷。同時將對應的pc值、warp號碼、sign標記寄存輸出。

第二級流水線：當控制信號(en_tag)為1，首先判斷第一級流水線傳過來的line是否為1，若為1，則第二級流水線輸出的miss(未命中)信號、hit(命中)信號以及命中的路數與寄存的結果相同；否則，根據第一級傳過來的addr(地址)和16個tag,將addr中的tag位與16路tag中的tag位分別進行比較，同時判斷tag中的valid位是否為1。若其中有一組比較結果相同并且對應的valid位為1，則hit,輸出命中信號，命中的路數(set)。若上述比較結果都為0，則miss,向mem_ctrl模塊輸出miss信號，暫停指令請求，同時保存對應miss地址。當通過總線接口模塊取回對應的128條指令時，將miss信號改為hit,繼續流水線的執行；同時寄存第一級流水線輸出的指令、pc值、warp號碼、sign標記。

第三級流水線：根據第二級流水線輸出的hit、set和miss信號。若miss則向總線接口模塊發出請求信號和地址。miss時，當通過總線接口模塊取回對應的指令時，將取回的第二級流水線寄存地址的對應位置的指令寄存，寄存信號為miss_inst;若line為1，同時將第一級流水線寄存地址的對應位置的指令寄存，寄存信號為line_miss_inst。同時將取回的指令填充到替換算法指定的對應路的inst_ram中，更新對應的tag_ram。若填充滿，下一時刻將miss_inst輸出；若line為1，將line_miss_inst輸出；其他情況，hit為1時直接將命中路對應的指令輸出。輸出指令時，將對應指令的valid、pc值、warp號碼、sign標記同時輸出。圖4為icache控制模塊結構圖。

圖4 icache控制模塊結構圖

2.1.3替換算法模塊

輪詢替換算法:算法為每一行設置一個4位的替換計數器，每次替換時選取替換計數器指定的cache行，替換后替換計數值加1，當計數器計到最大值時從0開始重新計數，命中時不改變計數器的值。

最不經常使用算法(LFU算法):算法需要為每行提供64位寄存器用來存放16路計數器的值，其中3～0位對應第0路計數器的值，7～4對應第1路計數器的值，依此類推，初始寄存器64位的值設置為64’h0123456789abcdef。當miss時找到計數器中值為0的值，即為所需替換的路數，同時將其他路計數器值減1，替換路計數器值變為15。命中時，將命中路計數器值變為15，其他路計數器比命中路計數器值小的不變，大的則將計數器的值減1。

最近最少使用算法(LRU算法):算法需要為每行提供64位寄存器用來存放16路計數器的值，其中3～0位對應第0路計數器的值，7～4對應第1路計數器的值，依此類推，初始寄存器64位的值設置為64’h0123456789abcdef。當miss時找到計數器中值為15的值，即為所需替換的路數，同時將其他路計數器值加1，替換路計數器值變為0。命中時，將命中路計數器值變為0，其他路計數器比命中路計數器值大的不變，小的則將計數器的值加1。

專用偽LRU替換算法：算法將局部性原理與LRU替換算法相結合，使用18位來存儲標志位(lru_val)的值。因為采用16路組相聯，設計時將對應的16路分為4組，0～3路為第一組，4～7路為第二組，8～b路為第三組，c～f路為第四組。將lru_val中的18位分為3部分，17～12位用于表示選擇哪一組，11～8位表示選擇對應組內的后兩路還是前兩路，7～0位用于選擇16路中相鄰兩路中的哪一路。對應位為0表示前者相對后者最近最少使用。

(1) 12位表示第一組相對第二組是否最近最少使用，13位代表第一組相對第三組是否最近最少使用，14位代表第一組相對第四組是否最近最少使用，15位代表第二組相對第三組是否最近最少使用，16位代表第二組相對第四組是否最近最少使用，17位代表第三組相對第四組是否最近最少使用。

(2) 8位代表第一組中的后兩路相對前兩路是否最近最少使用，9位代表第二組中的后兩路相對前兩路是否最近最少使用，10位代表第三組中的后兩路相對前兩路是否最近最少使用，11位代表第四組中的后兩路相對前兩路是否最近最少使用。

(3) 0位代表0路相對1路是否最近最少使用，1位代表2路相對3路是否最近最少使用，2位代表4路相對5路是否最近最少使用，3位代表6路相對7路是否最近最少使用，4位代表8路相對9路是否最近最少使用，5位代表10路相對11路是否最近最少使用，6位代表12路相對13路是否最近最少使用，7位代表14路相對15路是否最近最少使用。

若命中，并且line為1，則不需要改變lru_val的值，若不在同一行，則根據命中的路數以及寄存的lru_val的值，更新lru_val。若miss,則根據當前lru_val的值判斷需要替換的路數，同時更新lru_val的值。

2.2 數據cache結構設計

數據cache用于接收通過mem_ctrl模塊透傳由ldst模塊傳過來的請求信號，用于觀察所需的數據是否在對應的RAM中，若是，則將對應的數據輸出給ldst模塊，否則，向總線接口模塊發出對應的請求信號，待總線接口模塊返回對應的數據時，填充對應的RAM。填充完畢時，將對應的數據輸出。數據cache大小設計為32 KB,采用4路組相聯，行大小為8字。因此地址的4～0位為偏移位，12～5位為索引位，31～13為tag位。

數據cache與指令cache采用相同的結構，使用3級流水線，實現數據cache功能，滿足處理器取數請求。數據cache替換算法采用與指令cache類似的可配置的替換算法，輪詢替換算法使用2位計數器；LFU、LRU使用8位寄存器的值；專用偽LRU替換算法在設計時只需要3位的標志位(lru_val)即可。第0位表示第0路相對第1路是否最近最少使用，第1位表示第2路相對第3路是否最近最少使用，第2位代表后兩路相對前兩路是否最近最少使用。若命中并且line為1不改變標志的值；若line不為1，改變標志位的值；若miss改變標志位的值，同時根據當前標志位的值，找到需要替換的路數。

3 實驗結果及分析

3.1 功能驗證

對于整體cache的驗證，主要從下面幾方面入手:

(1) 分析取指、ldst模塊可能出現的各種情況，列舉各種情況的不同組合，按照列舉出來的不同情況，使用VCS工具對指令cache。數據cache分別進行功能驗證，觀察icache、dcache功能是否正確；

(2) 將指令cache、數據cache添加進MMU中，使用VCS工具進行仿真，觀察整體MMU功能是否正確；

(3) 將MMU模塊嵌進整體架構中，使用vivado工具，通過測試不同的程序，檢查cache功能是否滿足處理器的要求。

圖5為使用8個warp、8個PE執行矩陣乘例子抓取的部分指令cache的仿真波形圖。初始tag_ram中的值為0，則icache發出miss信號，等到接收到總線接口模塊傳輸的128條指令時，將對應的指令輸出。若對應請求的指令在同一行時，根據流水線思想，一拍即可以輸出一個對應的指令、pc值、warp號碼、sign標記。根據抓取的波形，顯示指令cache滿足設計需求。

圖5 指令cache仿真波形圖

圖6為使用8個warp、8個PE執行矩陣乘例子抓取的部分數據cache的仿真波形圖。初始tag_ram中的值為0，則dcache發出miss信號，等到接收到總線接口模塊傳輸的8個數據時，將對應的數據輸出。若對應請求的數據在同一行時，根據流水線思想，一拍即可以輸出一個對應的數據。根據抓取的波形，顯示數據cache滿足設計需求。

圖6 數據cache仿真波形圖

3.2 性能分析

該cache結構采用Xilinx公司virtex ultrascale系列的xcvu440-flga2892-2-e FPGA芯片對設計進行綜合，該cache的最大工作速度可達307 MHz,滿足處理器設計要求。指令cache最大時延為2.923 ns,數據cache最大時延為3.258 ns。整體cache具體器件占用情況如表1所示。

表1 cache具體器件占用情況

3.3 FPGA驗證

該SIMT處理器使用Xilinx公司virtex ultrascale系列的Dual VU Prodigy Logic Module開發板進行測試。搭建FPGA驗證平臺時，將pcie2axi橋作為AXI總線的一個主機，連接到AXI總線的m1端口，SIMT處理器在進行信息配置時作為AXI總線的一個從機，連接到AXI總線的s2端口，SIMT處理器執行時作為AXI總線的一個主機，連接到AXI總線的m2端口，異步轉換核(DW_axi_x2x)作為AXI總線的一個從機，連接到AXI總線的s1端口。

進行FPGA驗證時，首先由PC機輸出對應的指令、數據、配置信息，通過pcie2axi橋將對應的指令、數據、配置信息傳輸到AXI2to2總線上，SIMT處理器通過AXI2to2總線的s2端口，將對應的配置信息傳輸到SIMT處理器，異步轉換核通過AXI2to2總線的s1端口將對應的指令、數據傳輸到ddr4,并且匹配ddr4與AXI總線的速率。將對應的指令、數據、配置信息傳輸完成后，啟動SIMT處理器的執行。當SIMT處理器icache、dcache發生缺失時，通過AXI總線的m2端口，在讀地址通道上輸出對應的請求信號、地址、控制信息，讀數據通道接收到對應的數據時，將對應的數據傳輸到SIMT處理器，繼續缺失數據、指令的執行。對應的程序執行完成后，SIMT處理器將對應的結果通過m2的寫地址通道、寫數據通道傳輸到ddr4。最終通過控制PC機讀取相應地址的值，在PC機上觀察程序執行的最終結果，可以判斷SIMT處理器執行是否正確。圖7為搭建的FPGA驗證平臺。

圖7 FPGA驗證平臺

通過在FPGA上測試排序、找最大值、矩陣乘、卷積、循環、解線性方程、畫線、頂點染色、FFT等例子，并觀察PC機上打印的結果，表明該cache設計正確，滿足SIMT處理器設計要求。其中以矩陣乘為例，該程序使用4個warp、4個PE進行矩陣乘運算。圖8為矩陣點積圖。

圖8 矩陣點積圖

將計算的結果轉換為16進制數據，分別為1e、46、32、3c、46、ae、72、8c、32、72、54、64、3c、8c、64、78,通過與PC機上打印結果相比較，表明該SIMT處理器設計正確，滿足程序設計要求。圖9為PC機上打印結果。

圖9 PC機打印結果

4 結 語

為了進一步提高處理器性能，從而滿足機器學習處理大數據、大吞吐量等要求，本文在基于自主研發的SIMT處理器的基礎上設計了指令cache、數據cache,滿足SIMT處理器的指令、數據讀取要求。設計可配置的替換算法，使用VCS工具進行仿真，驗證功能的正確性；并通過vivado綜合，結果表明該cache整體性能達到307 MHz,指令cache最大時延為2.923 ns,數據cache最大時延為3.258 ns,滿足SIMT處理器的性能要求，緩解了主存與處理器的差距。現已將該cache設計應用到SIMT處理器中，在FPGA上通過測試不同的程序對SIMT處理器進行驗證，驗證結果顯示該cache設計正確，同時滿足SIMT處理器要求。