基于BWDSP的字符串與內存處理函數(shù)優(yōu)化①

張仁高, 鄭啟龍, 王向前

1(中國科學技術大學 計算機科學與技術學院, 合肥 230027)

2(中國電子科技集團公司第三十八研究所, 合肥 230088)

基于BWDSP的字符串與內存處理函數(shù)優(yōu)化①

張仁高1, 鄭啟龍1, 王向前2

1(中國科學技術大學 計算機科學與技術學院, 合肥 230027)

2(中國電子科技集團公司第三十八研究所, 合肥 230088)

面向BWDSP的體系結構分析了字符串與內存處理函數(shù)匯編優(yōu)化方法, 基于向量化與軟件流水的優(yōu)化技術,通過利用高效訪存指令、能夠提升循環(huán)執(zhí)行效率的零開銷循環(huán)機制、指令重排技術, 結合具體功能函數(shù)的循環(huán)特性, 展開針對字符串與內存處理函數(shù)的指令級并行性挖掘. 實驗結果表明, 這些庫函數(shù)的優(yōu)化效率能夠達到硬件平臺提供函數(shù)性能理論運行時間的1.5倍以下,對BWDSP平臺整體性能提升具有重要意義.

字符串與內存處理函數(shù); BWDSP; 函數(shù)優(yōu)化; 向量化與軟件流水; 特殊指令; 并行性

1 引言

字符串與內存處理函數(shù)是最基本的庫函數(shù), 它對上層函數(shù)的調用與處理提供了強大的接口調用. 這些函數(shù)使用較為頻繁, 經(jīng)編譯系統(tǒng)直接生成的代碼性能并不高, 有必要從匯編層面優(yōu)化其性能. 本文主要對字符串與內存處理函數(shù)進行匯編優(yōu)化, 提高其的執(zhí)行效率.

2 BWDSP介紹

BWDSP是一款16發(fā)射, 7級流水線, 4簇結構的處理器. 四個簇分別標號為X, Y, Z, T. 每個簇有64個寄存器, 4個乘法器, 8個ALU和4個特殊功能單元. 簇與簇之間采用簇間傳輸總線通信. BWDSP還采用了常見的AGU結構用來加速訪存, 內存訪問必須經(jīng)過AGU單元.AGU(Address Generation Unit)是用作訪存地址計算特殊單元, BWDSP的load/store的地址操作數(shù)必須使用AGU中地址寄存器. 使用獨立的AGU計算, 表示訪存地址可以降低處理器設計的復雜度. BWDSP的體系結構支持多種訪存模式, 支持零開銷循環(huán)、向量化執(zhí)行等, 其主要體系結構[1]如圖1所示.

圖1 BWDSP主要體系結構

2.1 BWDSP SIMD指令的特性分析

BWDSP計算指令的通用格式如下[1]:

[Macro]Rm = Rn op Rs

Macro是執(zhí)行宏的代號, op是操作, 符號“||”連接多個可并行指令, 比如: xRm=Rn+Rs是Scalar指令, 表示在X宏上執(zhí)行整數(shù)加法操作, xyztRm=Rn+Rs是SIMD指令, 表示在XYZT四個宏上同事執(zhí)行整數(shù)加法操作, 等于xRm=Rn+Rs||yRm=Rn+Rs||zRm=Rn+Rs||tRm=Rn+Rs.

2.2 BWDSP SIMD寄存器分配策略

BWDSP的編譯器OCC是以Open64為基礎開發(fā)的,Open64編譯器的寄存器分配分為兩類: 全局寄存器分配(GRA)和局部寄存器分配(LRA). 全局寄存器分配在一個函數(shù)范圍內, 為活躍范圍超出一個基本塊的LR分配寄存器; 局部寄存器分配在一個基本范圍內, 為只活躍在基本塊內部的LR分配寄存器.

2.3 通用DSP優(yōu)化策略

使用循環(huán)計數(shù)器是通用DSP軟件流水代碼的優(yōu)化方法. 最有效的軟件流水循環(huán)一般按遞減形式對循環(huán)進行計數(shù). 通常即使源代碼中沒有按這種形式編寫, 編譯器也能轉換成遞減形式.

DSP的指令流水線存在著不可避免的阻塞現(xiàn)象,MAC單元指令也一樣. 盡管在硬件設計時已經(jīng)采用了專用模塊來減少阻塞, 但有些阻塞是不可避免的, 從程序優(yōu)化的角度來說, 可以充分利用指令流水線阻塞現(xiàn)象, 通過重排指令流水線上的指令, 消除阻塞, 以使得程序的運行時間縮短, 從而達到優(yōu)化的目的.

3 BWDSP優(yōu)化分析

3.1 特殊指令

雙字尋址指令和sigma指令.

雙字尋址指令功能是在1個時鐘周期內讀取多個字, 進一步減少函數(shù)的訪存次數(shù)[2]. 指令形式如下:

第一條指令是讀訪存指令, Un是基地址, Uk是在Un地址基礎上的調整量, Um則是指令執(zhí)行后基地址Un的修正量. 指令采用雙字節(jié)讀數(shù), 故偏移地址為[Un]和[Un+1]、[Un+2Uk]和[Un+2Uk+1]、[Un+2×2Uk]和[Un+2×2Uk+1]、[Un+3×2Uk]和[Un+3×2Uk+1], 將這8個地址的數(shù)據(jù)依次送到4個宏里的同名寄存器{x, y, z, t}Rs:s+1. 第二條指令是寫存儲指令.

sigma指令的功能是歸并四個簇上的值, 指令格式如下[1]:

{x’, y’, z’, t’}Rs = sigma{x, y, z, t}Rm

將{x, y, z, t}Rm中32位定點有符號數(shù)分別相加到{x’, y’, z’, t’}Rs寄存器上. 通過sigma指令可以對分散在不同寄存器中值進行收集, 減少了逐一合并計算的時間.

零開銷循環(huán)指令.

零開銷循環(huán)[2]是通過硬件實現(xiàn)一種加速循環(huán)執(zhí)行的方法. BWDSP硬件提供零開銷循環(huán)指令, 其指令集中LC0和LC1指令專門用于零開銷循環(huán), 指令形式為“if LCx B label”. 程序的循環(huán)往往需要大量的條件判斷和跳轉. 普通跳轉指令需要判斷比較, 同時要對于控制條件進行累加, 這樣的跳轉指令判斷需要占用多個周期.零開銷循環(huán)指令相比于普通跳轉指令而言只需占用1個時鐘周期. 以零開銷循環(huán)控制循環(huán)體的長度, 可使優(yōu)化后的匯編函數(shù)性能可以得到顯著提升.

3.2 指令重排技術

BWDSP可同時支持執(zhí)行16條指令, 即一個執(zhí)行擁有十六個執(zhí)行槽. 通過指令重排技術調節(jié)指令次序來減少流水線的空轉和等待時間. 通過手動優(yōu)化, 避免BWDSP中16路發(fā)射和亂序執(zhí)行的特性使得指令調度變得復雜. 若經(jīng)過指令重排無法將每個執(zhí)行16個指令槽填滿, 根據(jù)BWDSP 16路特性, 可以通過簡單的使用空操作填充指令槽, 這樣使得流水線按照較為理想的狀態(tài)發(fā)射指令[3].

3.3 軟件流水技術

軟件流水是一種強大的循環(huán)調度技術, 允許指令跨迭代的移動實現(xiàn)循環(huán)迭代的重疊執(zhí)行, 通過發(fā)掘循環(huán)的不同迭代的各部分之間的指令間并行性, 使這些指令并行地執(zhí)行. BWDSP體系架構上的軟件流水, 采用模調度算法[4,5]和模變量擴展算法[6]思想實現(xiàn)軟件流水匯編代碼.

3.3.1 模調度算法

模調度是軟件流水調度的核心算法, 它獲取核心循環(huán)體基本塊信息, 結合目標體系硬件資源生成模資源約束表MRT并計算出資源限制(ResII), 且根據(jù)指令相關依賴圖計算出依賴限制(RecII), 模調度的最小啟動II從開始進行調度, 如果調度不成功則增加II再次進行循環(huán)調度, 直到找到一個滿足資源和依賴約束的合適II[7,8]. 啟動間距II是衡量軟件流水效率的重要指標;展開因子是影響循環(huán)展開(loop unrolling)的主要因素.資源限制(ResMII)和依賴限制(RecMII)是決定啟動間隔II和展開因子[9,10]的主要因素. 其中ResMII的計算是先把一個循環(huán)體對應需要的資源需求列表計算出來, 通過簡單的累加得到; 然后把所需的每種資源數(shù)量除以體系結構提供的資源數(shù)量, 該值最大就作為ResMII.RecMII則是依賴圖形成各個環(huán)中延遲除以環(huán)跨越迭代距離的最大值[10]. 模調度算法的優(yōu)點是以固定的間隔啟動每個迭代的調度, 有助于減少寄存器的壓力.

3.3.2 模變量擴展

在軟件流水執(zhí)行過程中, 不同循環(huán)體重疊地執(zhí)行.每次迭代中對同一個變量用相同寄存器變量存放, 則迭代之間就會相互有影響, BWDSP并不支持IA64體系結構下的旋轉寄存器, 模變量擴展通過識別那些在每次迭代開始處重新定義的變量, 利用寄存器重命名技術, 使得每次迭代對同一變量的引用指向一個不同的位置, 彼此之間不沖突.

3.4 性能分析

BWDSP匯編函數(shù)庫主要采用循環(huán)展開和軟件流水的優(yōu)化方案. 只有當循環(huán)體可向量化時, 才能運行循環(huán)展開和軟件流水操作.

循環(huán)展開能夠增加參與運算的個數(shù), 減少循環(huán)的重復次數(shù). 展開后的循環(huán)體包含更多的指令, 可以使調度部件更加自由地挑選不相關的指令并行執(zhí)行.

3.4.1 資源限制

資源限制(ResMII)考慮了體系結構中可用資源的數(shù)量, 是衡量被硬件所約束的模調度的重要指標. 受體系結構中可用硬件資源數(shù)量的約束, 在計算理論運行時間是需要考慮循環(huán)體內各種運算操作在各類運算部件上的分配情況.

具體計算方法:

統(tǒng)計循環(huán)體內所有運算(取數(shù), 加法, 移位, 超算,寫等)的操作步數(shù), 標記為N. 假設取數(shù)操作有N1步, 加法操作有N2步, 乘法操作有N3步, 移位操作有N4步, 超算操作有N5步, 寫操作有N6步, 且劃分共有:

劃分各類操作至相應的操作部件, 即加法操作分配至加法器, 乘法操作分配至乘法器等.

例如:

在BWDSP104x中共存在16個slot(一般情況下N步操作分配于12個slot中), 8個ALU, 8個MUL, 4個SHIFT,1個SPU, 3次讀寫.

則資源限制的最小理論周期:

3.4.2 依賴限制

依賴限制(RecMII)是衡量體系結構被數(shù)據(jù)依賴的重復回路所約束的模調度的重要指令. RecMII限制了軟件流水循環(huán)體的最小規(guī)模, 如果小于這個值, 則會存在數(shù)據(jù)覆蓋從而導致流水無法完成, RecMII被數(shù)據(jù)相關圖中的重復回路所約束.

具體計算方式:

根據(jù)步長約束計算循環(huán)展開的次數(shù)p1, 計算循環(huán)體內RecMII的最小長度s. 根據(jù)寄存器約束計算循環(huán)展開的次數(shù)p2

計算理論上的循環(huán)展開次數(shù)p為:

計算依賴限制理論運行時間最小周期:

3.4.3 計算理論運行時間

資源限制和依賴限制共同確定了指令的最小規(guī)模.在依賴限制的流水計算中, 還需要考慮寄存器的上限,即是否會因為循環(huán)體過大而產(chǎn)生寄存器不夠用的問題.

假設輸入向量長度的長度為num的函數(shù), 要得到可向量化時匯編語言版庫函數(shù)的理論運行時間, 還需綜合考慮資源限制和依賴限制, 計算在完全流水條件下完成一組循環(huán)體內所有操作的最小理論運行時間R_cycle為:

以及統(tǒng)計循環(huán)體外執(zhí)行串行操作的時鐘周期數(shù)C.

計算匯編語言版函數(shù)理論運行時間L_cycle為:

對于每個可向量化的函數(shù), 當數(shù)據(jù)規(guī)模達到一定程度時, 理應滿足運行時間小于匯編版函數(shù)理論運行時間的1.5倍.

4 字符串與內存處理函數(shù)

在庫函數(shù)中字符串與內存處理函數(shù)存在大量的循環(huán)體與向量化, 是主要的優(yōu)化對象, 其主要可以分為以下幾種: 內存拷貝和賦值函數(shù), 字符串拷貝與連接函數(shù),字符串與內存比較函數(shù), 字符串與內存查找函數(shù). 字符串與內存的操作通常一一對應, 區(qū)別在于字符串用空字符NULL來表示結尾, 而內存塊則明確給出長度[11].

4.1 內存拷貝與賦值函數(shù)

memcpy, memmove及memset函數(shù)的基本實現(xiàn)流程為, 首先判斷拷貝的數(shù)據(jù)大小是否符合優(yōu)化的范圍, 逐一拷貝源地址的字符到目的地址.

BWDSP為保證在源地址與目的地址的字符交疊時能夠正確的復制, memmove在拷貝過程中需添加一個臨時拷貝區(qū)域. Memcpy直接從源地址內存進行拷貝.memset為目的地址內存賦予特定值.

以memcpy函數(shù)為例, 函數(shù)功能是復制目的地址的字符到源地址, 通過平臺支持的雙字尋址指令中的讀取指令讀取目的地址的字符, 再利用存儲指令存儲讀取的字符到源地址, 并且通過零開銷循環(huán)指控制程序循環(huán)長度.

memcpy向量化的匯編代碼如下所示:

由計算結果可得, 該循環(huán)體在一個迭代的過程中,所需資源為2個slot(2/8), 1個branch(1/1), memread為(1/2), memwrite為(1/2). 訪存資源利用率在一個迭代4個周期中的利用率為50%, 資源ALU利用率為25%.

匯編代碼的性能仍然有提高效率和優(yōu)化的空間,可通過軟件流水填補循環(huán)體中的指令之間的空缺周期方式進行優(yōu)化, 使指令得到重排, 不同流水線可以同時執(zhí)行, 避免了空閑周期的存在, 有效地提升了循環(huán)體性能. 軟件流水匯編核心代碼如下所示:

對于memcpy函數(shù)中的主要片段, 該循環(huán)體在一個迭代周期中所需資源為1個slot(1/8), 1個branch(1/1),memread為(1/2), memwrite為(1/2), ResMII為1,RecMII為1, II為1. 優(yōu)化后的匯編代碼在1個周期的情況下即可完成向量化一次迭代所完成的任務, 同時平臺硬件資源利用率明顯得到提升.

表1所示內存拷貝與賦值函數(shù)優(yōu)化結果, 以內存10000個字作為測試數(shù)據(jù), 得到各個函數(shù)所運行的時鐘周期數(shù). 優(yōu)化率是優(yōu)化后的周期數(shù)與優(yōu)化前函數(shù)的周期數(shù)之比.

表1 內存拷貝與賦值函數(shù)優(yōu)化效果

向量化與軟件流水優(yōu)化下的memcpy函數(shù)在字符長度從1000字～10000字的優(yōu)化效果如圖2所示.

圖2 向量化和軟件流水優(yōu)化效果

4.2 字符串拷貝與連接函數(shù)

strcat和strncat逐字符進行比較直到目標字符串的末尾, 再將源字符串的字符拷貝到目標字符串上. 對于后面的拷貝操作仿照內存賦值函數(shù)進行拷貝.

strcpy和strncpy函數(shù)相比于字符串連接函數(shù), 在拷貝過程中需比較目的字符串的結尾字符.

函數(shù)都需要判斷字符結尾的字符, 執(zhí)行過程中需要的比較語句是必不可少的, 比較語句所占的周期很大, 利用指令重排技術可以進一步提高效率.

表2所示字符串拷貝與連接函數(shù)函數(shù)優(yōu)化結果, 以內存10000個字作為輸入.

表2 字符串拷貝與連接函數(shù)優(yōu)化效果

字符串拷貝與連接函數(shù)在字符長度為10000個字下向量化相比于軟件流水取得加速比的收益如圖3所示.

圖3 字符串拷貝與連接函數(shù)優(yōu)化效果

4.3 字符串和內存比較函數(shù)

Strcmp和memcmp需要同時訪問兩個字符串或兩內存并對讀取的字符進行比較. 函數(shù)算法流程是先逐字讀取兩個字符串到寄存器中, 接著對寄存器中字符進行比較, 如果相等, 通過移位調整字符串位置再進行比較, 否則退出.

字符串比較需要考慮字符長度問題以及所比較的范圍, 在拷貝過程中還要找出不同的字符. 采取的方案是每次批量讀取字符進行比較, 如果不相等, 則返回比較結果. 如果該部分子串相等, 則繼續(xù)比較下一批量字符[12]. 這種逐批量讀取的方式避免了逐字遍歷一個很長的字符串浪費的時間. 在BWDSP中, 寄存器的讀取內存的長度最大可為8個字的長度, 為了達到讀取與比較的字符串長度一致, 采用一次批量讀取的長度是8個字. 比較過程建立了兩種比較方式.

第一種在判斷長度的同時比較兩個字符串的不同字符, 并將兩個不同的字符返回. 此種方式, 主要思想是對所讀取的源字符串或內存的8個字和目的字符串或內存8個字一一作比較. 同時使用指令重排技術把指令放在同一個執(zhí)行, 讓指令能夠達到并行的最大程度..

第二種比較方式把比較字符作互相做&操作, &操作的結果與0比較, 判斷是否相等. 這樣我們可以把第一種方式的多條比較語句優(yōu)化成簡單比較語句, 這種算法相對于第一種減少了每次比較的過程. 同時在比較過程中, 使用BWDSP本身自帶的指令sigma, 將不同字符比較的結果收集到一個臨時寄存器中, 將多條比較語句優(yōu)化成單條比較語句進行判斷, 大大減少了比較過程中損耗的時間. 此種方式支持BWDSP的指令,使比較結果更加簡便.

表3所示字符串比較和內存比較函數(shù)經(jīng)過第二次優(yōu)化算法的優(yōu)化結果, 以內存10000個字作為輸入.

表3 字符串和內存比較函數(shù)優(yōu)化效果

第一次優(yōu)化算法和第二次優(yōu)化算法以函數(shù)為memcmp為例, 內存中都以最后一個字符不同為標準.

Memcmp函數(shù)在內存長度為1000字～12000字的長度下基本算法和優(yōu)化算法的比較下得到的優(yōu)化效果如圖4所示.

圖4 memcmp在基本算法和優(yōu)化算法下的效果

4.4 字符串和內存查找函數(shù)

Memchr及strchr都是查找字符串中的特定字符, 并將該字符的地址返回. 函數(shù)的流程是逐個字符與目標字符進行比較, 直至找到該字符.

查找函數(shù)同樣由于擁有大量的比較操作, 其優(yōu)化過程與字符串和內存比較函數(shù)類似.

表4所示字符串和內存查找函數(shù)優(yōu)化結果, 以內存10000個字作為輸入.

表4 字符串和內存查找函數(shù)優(yōu)化效果

5 結束語

BWDSP是一款針對高性能計算領域設計的32位靜態(tài)數(shù)字處理器, 本文針對BWDSP體系結構, 利用其自帶指令及硬件等相關結構, 在其平臺上對字符串與內存處理函數(shù)的進行優(yōu)化, 實現(xiàn)了相關函數(shù)匯編代碼,經(jīng)過最后的實驗結果分析可以知道, 匯編函數(shù)的優(yōu)化效果可以提升函數(shù)的性能.

1CETC38. BWDSP100軟件用戶手冊. 合肥: 中國電子科技集團第三十八研究所, 2011: 1–2.

2甄揚. 基于多核VLIW DSP的數(shù)字信號變換函數(shù)并行優(yōu)化[碩士學位論文]. 合肥: 中國科學技術大學, 2015.

3甄揚, 顧乃杰, 葉鴻. 數(shù)字信號變換函數(shù)在多簇VLIW DSP上的優(yōu)化. 計算機工程, 2016, 42(3): 47–52.

4Rau BR. Iterative module scheduling: An algorithm for software pipelining loops. Proc. of the 27th Annual International Symposium on Microarchitecture. San Jose,CA, USA. 1994. 63–74.

5Kim W, Yoo D, Park H, et al. SCC based modulo scheduling for coarse-grained reconfigurable processors. Proc. of International Conference on Field-Programmable Technology.Seoul, Korea. 2012. 321–328.

6Lam MS. Software pipelining: An effective scheduling technique for VLIW machines. Proc. of the SIGPLAN’88 Conference on Language Design and lmplementatlon.Atlanta, Georgia, USA. 1988. 318–328.

7林海波. 基于EPIC體系結構的軟件流水技術研究[博士學位論文]. 北京: 清華大學, 2003.

8王向前, 鄭啟龍, 洪一. 分簇結構模調度框架研究. 中國科學技術大學學報, 2016, 46(2): 104–112.

9Hiroyuki S, Teruhiko Y. Characteristics of loop unrolling effect: Software pipelining and memory latency hiding.Innovative Architecture for Future Generation High-Performance Processors and Systems. Maui, HI, USA. 2001.63–72.

10Yoshida T, Sato H. Characteristics extraction of loop unrolling and its modeling. Solid-State Electronics, 1989,32(1): 65–68. [doi: 10.1016/0038-1101(89)90049-X]

11李愷 翁玉萍. 基于龍芯2F的Glibc庫優(yōu)化. 電子技術, 2010,37(10): 27–29. [doi: 10.3969/j.issn.1004-373X.2010.10.009]

12李愷. Glibc庫在龍芯2F上的優(yōu)化[碩士學位論文]. 合肥: 中國科學技術大學, 2010.

Optimization of String and Memory Functions Based on BWDSP

ZHANG Ren-Gao1, ZHENG Qi-Long1, WANG Xiang-Qian2

1(School of Computer Science and Technology, University of Science and Technology of China, Hefei 230027, China)
2(No.38 Research Institute, China Electronics Technology Group Corporation, Hefei 230088, China)

For architecture of BWDSP, this paper analyzes the implementation of the optimizations, based on vectorization and software pipelining of parallel optimization technique, including special memory access instruction,zero-overhead looping instruction of improving efficiency in the loop, Instruction-level Parallelism(ILP), combined with the specific function of loop characteristics, expansion for the string and memory function of instruction level parallel mining. The experimental results show that the optimization rates of most functions of the theory have a running time of 1.5 times on hardware platform, which is of great importance to enhance the platform performance of BWDSP.

string and memory functions; BWDSP; optimization of function; vectorization and software pipelining; special instruction; parallelism

張仁高,鄭啟龍,王向前.基于BWDSP的字符串與內存處理函數(shù)優(yōu)化.計算機系統(tǒng)應用,2017,26(7):167–172. http://www.c-s-a.org.cn/1003-3254/5834.html

國家核高基重大專項(2012ZX01034001-001)

2016-11-19; 收到修改稿時間: 2016-11-24