基于BWDSP的字符串與內存處理函數優化①

張仁高, 鄭啟龍, 王向前

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

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

基于BWDSP的字符串與內存處理函數優化①

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

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

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

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

字符串與內存處理函數; BWDSP; 函數優化; 向量化與軟件流水; 特殊指令; 并行性

1 引言

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

2 BWDSP介紹

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

圖1 BWDSP主要體系結構

2.1 BWDSP SIMD指令的特性分析

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

[Macro]Rm = Rn op Rs

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

2.2 BWDSP SIMD寄存器分配策略

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

2.3 通用DSP優化策略

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

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

3 BWDSP優化分析

3.1 特殊指令

雙字尋址指令和sigma指令.

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

第一條指令是讀訪存指令, Un是基地址, Uk是在Un地址基礎上的調整量, Um則是指令執行后基地址Un的修正量. 指令采用雙字節讀數, 故偏移地址為[Un]和[Un+1]、[Un+2Uk]和[Un+2Uk+1]、[Un+2×2Uk]和[Un+2×2Uk+1]、[Un+3×2Uk]和[Un+3×2Uk+1], 將這8個地址的數據依次送到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位定點有符號數分別相加到{x’, y’, z’, t’}Rs寄存器上. 通過sigma指令可以對分散在不同寄存器中值進行收集, 減少了逐一合并計算的時間.

零開銷循環指令.

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

3.2 指令重排技術

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

3.3 軟件流水技術

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

3.3.1 模調度算法

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

3.3.2 模變量擴展

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

3.4 性能分析

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

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

3.4.1 資源限制

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

具體計算方法:

統計循環體內所有運算(取數, 加法, 移位, 超算,寫等)的操作步數, 標記為N. 假設取數操作有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)是衡量體系結構被數據依賴的重復回路所約束的模調度的重要指令. RecMII限制了軟件流水循環體的最小規模, 如果小于這個值, 則會存在數據覆蓋從而導致流水無法完成, RecMII被數據相關圖中的重復回路所約束.

具體計算方式:

根據步長約束計算循環展開的次數p1, 計算循環體內RecMII的最小長度s. 根據寄存器約束計算循環展開的次數p2

計算理論上的循環展開次數p為:

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

3.4.3 計算理論運行時間

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

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

以及統計循環體外執行串行操作的時鐘周期數C.

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

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

4 字符串與內存處理函數

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

4.1 內存拷貝與賦值函數

memcpy, memmove及memset函數的基本實現流程為, 首先判斷拷貝的數據大小是否符合優化的范圍, 逐一拷貝源地址的字符到目的地址.

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

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

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

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

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

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

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

表1 內存拷貝與賦值函數優化效果

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

圖2 向量化和軟件流水優化效果

4.2 字符串拷貝與連接函數

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

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

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

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

表2 字符串拷貝與連接函數優化效果

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

圖3 字符串拷貝與連接函數優化效果

4.3 字符串和內存比較函數

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

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

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

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

表3所示字符串比較和內存比較函數經過第二次優化算法的優化結果, 以內存10000個字作為輸入.

表3 字符串和內存比較函數優化效果

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

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

圖4 memcmp在基本算法和優化算法下的效果

4.4 字符串和內存查找函數

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

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

表4所示字符串和內存查找函數優化結果, 以內存10000個字作為輸入.

表4 字符串和內存查找函數優化效果

5 結束語

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

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

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

3甄揚, 顧乃杰, 葉鴻. 數字信號變換函數在多簇VLIW DSP上的優化. 計算機工程, 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庫優化. 電子技術, 2010,37(10): 27–29. [doi: 10.3969/j.issn.1004-373X.2010.10.009]

12李愷. Glibc庫在龍芯2F上的優化[碩士學位論文]. 合肥: 中國科學技術大學, 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的字符串與內存處理函數優化.計算機系統應用,2017,26(7):167–172. http://www.c-s-a.org.cn/1003-3254/5834.html

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

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