基于RISC-V GCC編譯器的指令延遲調(diào)度

余曉江 羅欣

（西華師范大學(xué) 四川省南充市 637000）

1 引言

2014年加州大學(xué)伯克利分校（University of Cal-I fornia at Berkeley, 以下簡稱 UCB）的研究人員Krste Asa-novic、Andrew Waterman、Yunsup Lee 設(shè) 計(jì) 并 發(fā) 布 了RISC-V 指 令 集 架 構(gòu)[1]。RISC-V 基于精簡指令集計(jì)算（RISC）原理構(gòu)建的開放RISC-V 指令集架構(gòu)（RISC-V instruction set architecture 簡稱RISC-V ISA）[2]。RISC-V 指令集架構(gòu)采用的是精簡指令集，同時(shí)有著非常良好的可擴(kuò)展性，并且RISC-V 生態(tài)系統(tǒng)迅速的發(fā)展，促進(jìn)了這種新型的RISC-V ISA 在各大處理器設(shè)計(jì)中得到應(yīng)用。RISC-V 開源自由協(xié)議受到個(gè)人、科研團(tuán)隊(duì)以及商業(yè)公司的青睞，各大公司紛紛加入RISC-V 聯(lián)盟，如蜂鳥、中科院計(jì)算所、英偉達(dá)、華為、谷歌、阿里巴巴等等[3][4][5]。

大多數(shù)早期超標(biāo)量處理器[6]都是順序執(zhí)行，RISC-V 處理器設(shè)計(jì)初期均采用單發(fā)射順序執(zhí)行的流水線工藝[7]。

流水線技術(shù)之所以能提高性能，其本質(zhì)是利用了時(shí)間上的并行性，讓原本應(yīng)該先后執(zhí)行的指令在時(shí)間上一定程度的并行起來，然而這樣也會(huì)帶來一些沖突和矛盾，進(jìn)而可能引發(fā)錯(cuò)誤，這種情況就被稱為流水線冒險(xiǎn)。數(shù)據(jù)冒險(xiǎn)是流水線冒險(xiǎn)中最常見的一種，數(shù)據(jù)冒險(xiǎn)是指令所需要的數(shù)據(jù)矛盾，如果一條指令需要某個(gè)數(shù)據(jù)而該數(shù)據(jù)正在被之前的指令操作，那這條指令就無法執(zhí)行，就導(dǎo)致了數(shù)據(jù)冒險(xiǎn)。針對流水線冒險(xiǎn)其中一種解決方案是使用流水線停頓來延遲下一條指令。從而避免流水線冒險(xiǎn)帶來的程序執(zhí)行錯(cuò)誤。

在傳統(tǒng)處理器設(shè)計(jì)中，流水線借助于一個(gè)執(zhí)行單元隊(duì)列，讓暫未滿足各類資源的指令在此等待一定周期，或者采用流水線停頓技術(shù)(stall)讓整個(gè)流水線上相關(guān)的資源均陷于一定周期的等待狀態(tài)，直至問題解除[8][9]。等待的周期主要取決于兩個(gè)因素：前驅(qū)指令的執(zhí)行開銷、以及當(dāng)前指令所需硬件資源。而這些恰恰是編譯器靜態(tài)指令調(diào)度策略中的核心影響因素。因此，如果借助于靜態(tài)調(diào)度策略，為當(dāng)前指令去權(quán)衡計(jì)算它需要等待的時(shí)間，適當(dāng)調(diào)整指令的位置，在指令排布過程中拉長它和前驅(qū)的距離，我們就能保證它在正確的時(shí)間完成譯碼以及到達(dá)執(zhí)行功能部件。

綜上所述，雖然成熟的處理器大部分使用動(dòng)態(tài)調(diào)度來避免流水線冒險(xiǎn)，但是基于RISC-V 指令集的處理器目前尚未成熟，都處在研究設(shè)計(jì)階段，所以使用RISC-V ISA 的處理器研發(fā)時(shí)，為縮短研發(fā)周期和研發(fā)成本。靜態(tài)調(diào)度是解決流水線冒險(xiǎn)最有效的方法。本文提出一種面向RISC-V 處理器的指令調(diào)度技術(shù)——指令延遲調(diào)度技術(shù)，用于向RISC-V 處理器研究提供一種實(shí)用、有效的軟件解決方案。在RISC-V 處理器研發(fā)處于萌芽期的大背景下，編譯器延遲調(diào)度技術(shù)是一種實(shí)用、有效的途徑，使編譯器的研發(fā)不受硬件時(shí)序控制設(shè)計(jì)與驗(yàn)證的約束，直接在具有基本執(zhí)行功能的FPGA 或者軟件模擬器上進(jìn)行研發(fā)，從而使軟件研發(fā)與處理器研發(fā)同步前行。

2 指令延遲調(diào)度技術(shù)

本文提出一種基于RISC-V 處理器的編譯器調(diào)度技術(shù)——指令延遲調(diào)度技術(shù)，它通過一個(gè)保守的資源開銷評估模型對當(dāng)前指令的正確發(fā)射時(shí)間進(jìn)行評估。通過指令的靜態(tài)調(diào)度對流水線上的指令到達(dá)執(zhí)行部件的時(shí)刻進(jìn)行干涉，從而有效避免由于指令提前到達(dá)執(zhí)行部件所引發(fā)的流水線冒險(xiǎn)。指令延遲調(diào)度技術(shù)是一種實(shí)用、有效的軟件解決方案，使核心軟件可以與處理器設(shè)計(jì)同期同步開展。優(yōu)化后的表調(diào)度分析算法能夠準(zhǔn)確地記錄每一個(gè)基本塊中指令流中需要插入延遲指令的位置和數(shù)量。通過本地延遲指令生成算法，生成占用拍數(shù)但又不做任何操作的NOP 指令[10]。指令延遲調(diào)度技術(shù)根據(jù)表調(diào)度算法計(jì)算出的數(shù)據(jù)對表調(diào)度之后的指令流進(jìn)行再次調(diào)度，使每一拍都有指令發(fā)射，從而避免流水線冒險(xiǎn)帶來的執(zhí)行錯(cuò)誤。經(jīng)過指令延遲調(diào)度的程序在處理器上不需要進(jìn)行動(dòng)態(tài)調(diào)度即可正確高效的執(zhí)行。為了不影響編譯器的功能模塊和方便進(jìn)行對比測試。將指令延遲調(diào)度封裝在編譯選項(xiàng)-fsched-delay 中，在編譯時(shí)，通過使用編譯選項(xiàng)-fsched-delay 來控制編譯器使用指令延遲調(diào)度技術(shù)。

（1）表調(diào)度分析算法。要對表調(diào)度后的RTL 進(jìn)行指令延遲調(diào)度，需要優(yōu)化表調(diào)度的分析算法。通過指令調(diào)度數(shù)據(jù)流DUMP 算法的輸出數(shù)據(jù)流，直觀的顯示了指令信息。RTL 中間表示階段所有指令是由一個(gè)結(jié)構(gòu)體存儲(chǔ)即INSN。要對指令進(jìn)行延遲調(diào)度，首先需要了解表調(diào)度的調(diào)度原理，如圖1 所示。指令I(lǐng)NSN 已提交到計(jì)劃中，從“Ready”列表移動(dòng)到“Scheduled”列表。當(dāng)發(fā)生這種情況時(shí)，“Pending”列表中的INSN 滿足其依賴關(guān)系并移動(dòng)到“Ready”列表或“Queued”集合，具體取決于是否已經(jīng)有足夠的時(shí)間使其準(zhǔn)備就緒；隨著時(shí)間的推移，準(zhǔn)備就緒的INSN 從“Queued”移動(dòng)到“Ready”列表；“Pending”列表（P）是未安排的INSN_FORW_DEPS 中的INSN，即準(zhǔn)備好，排隊(duì)和掛起的INSN?！癚ueued”集合（Q）由變量insn_queue 實(shí)現(xiàn)?！癛eady”列表（R）由變量ready 和n_ready 實(shí)現(xiàn)?！癝cheduled”列表（S）是由此傳遞構(gòu)建的新INSN 鏈。當(dāng)選擇最好的調(diào)度INSN 時(shí)，轉(zhuǎn)換（R-＞ S）在schedule_block 的調(diào)度循環(huán)中實(shí)現(xiàn)。當(dāng)INSN 從就緒列表移動(dòng)到調(diào)度列表時(shí)，轉(zhuǎn)換（P-＞ R 和P-＞ Q）在schedule_insn 中實(shí)現(xiàn)。隨著時(shí)間的推移或引入停頓，轉(zhuǎn)換（Q-＞ R）在queue_to_insn 中實(shí)現(xiàn)。為了減小對編譯器的影響，對表調(diào)度分析算法進(jìn)行優(yōu)化，計(jì)算出延遲調(diào)度的相關(guān)信息并記錄保存，傳遞到指令延遲調(diào)度中。

圖1：編譯器指令調(diào)度數(shù)據(jù)流對比

圖2：編譯器編譯出的匯編碼對比

圖3：指令延遲調(diào)度技術(shù)優(yōu)化后的編譯器與官方編譯器編譯SPEC2017 Benchmarks 的耗時(shí)對比圖

（2）延遲指令生成算法。由于指令流里的指令是由源碼翻譯過來的，從一開始轉(zhuǎn)換到RTL 時(shí)，就生成了雙向鏈表，經(jīng)過表調(diào)度時(shí)，指令隊(duì)列進(jìn)行指令調(diào)度后依然是一個(gè)雙向鏈表。那么在進(jìn)行延遲調(diào)度時(shí)，要在雙向鏈表中插入延遲指令NOP。就要對雙向鏈表進(jìn)行維護(hù)。每一條指令都有一個(gè)前驅(qū)和后繼，當(dāng)前指令、前驅(qū)指令和后繼指令都是相互依賴的。當(dāng)insn 需要延遲時(shí)，首先就要斷開雙向鏈表prev 和insn，將nop 指令放在prev 和insn 之間。把insn的前驅(qū)設(shè)置為nop，prev 的后繼修改為nop，并把nop 的前驅(qū)設(shè)置為prev，后繼為insn。根據(jù)機(jī)器模型獲取nop 指令的RTL 結(jié)構(gòu),設(shè)置nop 指令所屬的基本塊為insn 的基本塊。

（3）指令延遲調(diào)度算法。指令延遲調(diào)度算法根據(jù)表調(diào)度分析算法記錄并傳遞來的數(shù)據(jù)使用延遲指令生成算法在需要延遲的指令前插入足夠的空操作指令NOP 來占用無指令的拍數(shù)。為盡量避免對編譯器其他功能的影響，我們選擇在編譯器表調(diào)度完成之后，RTL 翻譯成匯編碼之前，進(jìn)行指令延遲調(diào)度。首先判斷是否在編譯時(shí)使用了-fsched-delay 編譯選項(xiàng)，以下所有操作都是在使用-fscheddelay編譯選項(xiàng)的情況下實(shí)現(xiàn)。接著判斷當(dāng)前是否屬于最后一次調(diào)度，即前面說的重載后調(diào)度（after reload）。當(dāng)兩個(gè)條件同時(shí)滿足時(shí)，對當(dāng)前基本快中已經(jīng)調(diào)度好的指令流進(jìn)行遍歷，尋找需要延遲的指令。當(dāng)遍歷到INSN 的編號(hào)INSN_UID 為表調(diào)度分析算法傳來數(shù)據(jù)中的INSN_UID 時(shí)，即這條INSN 需要在發(fā)射前插入NOP 延遲，根據(jù)數(shù)據(jù)中記錄的延遲拍數(shù)循環(huán)插入NOP 指令。調(diào)用延遲指令生成算法進(jìn)行指令生成。最后對指令在調(diào)度過程中的LUID 進(jìn)行維護(hù)，以保證調(diào)度過程中每一條指令在調(diào)度過程中都有唯一的識(shí)別ID。

3 實(shí)驗(yàn)結(jié)果與分析

（1）指令延遲調(diào)度技術(shù)是通過靜態(tài)調(diào)度中使用停頓避免流水線冒險(xiǎn)帶來的執(zhí)行錯(cuò)誤，經(jīng)過應(yīng)用該技術(shù)的RISC-V GCC 編譯器編譯程序時(shí)，使用-fsched-verbose=n 編譯選項(xiàng)可輸出指令調(diào)度過程，能夠直觀的看到指令延遲調(diào)度的結(jié)果，如圖1 所示。

另一方面，指令延遲調(diào)度技術(shù)在靜態(tài)調(diào)度中完成了空拍指令的填充，生成的匯編碼中會(huì)明確顯示NOP 在相應(yīng)的位置，如圖2 所示。

經(jīng)過如圖1 和圖2 的試驗(yàn)驗(yàn)證，指令延遲調(diào)度技術(shù)能夠在指定拍數(shù)處填充NOP 指令，并且正確的生成對應(yīng)的匯編碼，來延遲下一條指令。編譯器的性能是在對編譯器改進(jìn)后的綜合評估，主要通過編譯時(shí)間來進(jìn)行比較，使SPEC2017 作為測試用例，測試了使用指令延遲調(diào)度技術(shù)的RISC-V GCC 編譯器編譯時(shí)間。實(shí)驗(yàn)編譯器運(yùn)行環(huán)境為：32 核Intel Xeon E7-4809 主頻2.00GHz 的CPU，64 位ubuntu14.04 系統(tǒng)，一級(jí)指令/數(shù)據(jù)Cache 各32K，二級(jí)Cache256K。實(shí)驗(yàn)結(jié)果如圖3 所示。

圖3 中分別使用指令延遲調(diào)度技術(shù)優(yōu)化后的RISC-V GCC 編譯器和官方RISC-V GCC 編譯器在相同條件下編譯SPEC2017 中使用C 語言編寫的Benchmarks，由圖可見，優(yōu)化后的編譯器和原編譯器編譯相同Benchmarks 耗時(shí)相差不超過1s，實(shí)驗(yàn)證明，指令延遲調(diào)度技術(shù)對RISC-V GCC 的性能影響很小，達(dá)到了設(shè)計(jì)初期最小化編譯器影響的要求。為了驗(yàn)證優(yōu)化后的編譯器編譯出的程序可以正確的在RISC-V 處理器上運(yùn)行，以stream 作為測試程序，分別在超導(dǎo)模擬器和火苗原型系統(tǒng)上測試通過，能夠正確的執(zhí)行完成。超導(dǎo)v1 版本模擬器：位模式32 位，譯指隊(duì)列大小151，一級(jí)Cache128byte，二級(jí)Cache32K，寄存器個(gè)數(shù)16?；鹈缭拖到y(tǒng)：4 核Labeled RISC-V 系統(tǒng)，100 MHz rocket 核心， 16KB L1 Icache, 16KB L1 Dcache， 2MB L2 cache，16GB DDR4 SO-DIMMs，Linux 4.6.2 內(nèi)核。

4 結(jié)束語

指令調(diào)度在編譯器中是非常關(guān)鍵的環(huán)節(jié)，指令延遲調(diào)度技術(shù)是RISC-V GCC 編譯器在RTL 一級(jí)的指令調(diào)度優(yōu)化，在RISC-V 處理器研發(fā)過程中作為編譯器輔助有著重要作用，尤其是在超導(dǎo)計(jì)算機(jī)研究中作為編譯器優(yōu)化研究意義重大。本文通過對RISC-V GCC 編譯器的改進(jìn)和優(yōu)化，為進(jìn)一步研究和優(yōu)化RSIC-V GCC 奠定了編譯器基礎(chǔ)，更為快速研究新型的RISC-V 指令集架構(gòu)處理器起著重要的推動(dòng)作用。