一種基于龍芯2F的Glibc庫優(yōu)化

精品文檔-下載后可編輯一種基于龍芯2F的Glibc庫優(yōu)化

龍芯2F是中國科學(xué)院計算技術(shù)研究所研制的高性能通用處理器，具有低功耗、低成本以及自主安全的特點，已應(yīng)用于高性能計算和日常生活領(lǐng)域。

龍芯2F主要有以下幾個方面的提高。一是主頻提高30%以上，通過頻率篩選，將有1GHz以上的產(chǎn)品。二是相同頻率下功耗降低40%左右，并增加了很多諸如降頻、溫度傳感器、關(guān)閉L2等功耗管理功能。三是集成了更多的系統(tǒng)功能，除了CPU外，還集成了DDR2內(nèi)存控制器、66MHzPCI/100MHzPCIX控制器、LocalIO控制器、GPIO、中斷控制器、DMA控制器、部分顯示加速等功能，將大幅度降低系統(tǒng)成本。四是封裝更小，龍芯2E的封裝為35mm*35mm,龍芯2F為27mm*27mm.五是可測性設(shè)計（DFT）和可生產(chǎn)性設(shè)計（DFM）有明顯提高，因此可以降低芯片成本。

1Glibc庫介紹

glibc是gnu發(fā)布的libc庫，即c運行庫。glibc是linux系統(tǒng)中層的api,幾乎其它任何運行庫都會依賴于glibc.glibc除了封裝linux操作系統(tǒng)所提供的系統(tǒng)服務(wù)外，它本身也提供了許多其它一些必要功能服務(wù)的實現(xiàn)。由于glibc囊括了幾乎所有的UNIX通行的標準，可以想見其內(nèi)容包羅萬有。而就像其他的UNIX系統(tǒng)一樣，其內(nèi)含的檔案群分散于系統(tǒng)的樹狀目錄結(jié)構(gòu)中，像一個支架一般撐起整個作業(yè)系統(tǒng)。在GNU/Linux系統(tǒng)中，其C函式庫發(fā)展史點出了GNU/Linux演進的幾個重要里程碑，用glibc作為系統(tǒng)的C函式庫，是GNU/Linux演進的一個重要里程碑。

Glibc庫包含兩類函數(shù)，一種是與溝通的系統(tǒng)函數(shù)，它們封裝了系統(tǒng)調(diào)用，對傳入?yún)?shù)進行預(yù)處理之后就轉(zhuǎn)到系統(tǒng)調(diào)用來完成功能，其目的是使得用戶可以方便地使用操作系統(tǒng)提供的服務(wù)。系統(tǒng)調(diào)用接口與Linux操作系統(tǒng)相關(guān)，大部分流程固定，沒有太大優(yōu)化余地，對其不做處理。

C庫中的另一類函數(shù)提供常見的通用功能實現(xiàn)，包括標準輸入輸出控制，字符串處理，正則表達式，字符串加密，查找與排序等。它們提供基本的、與操作系統(tǒng)無關(guān)的功能，其中的部分函數(shù)有一定的計算量，是優(yōu)化工作關(guān)注的部分。

Glibc庫的版本在不斷更新，本文以當前的Glibc2.11版本為基礎(chǔ)進行優(yōu)化。

2龍芯2F體系結(jié)構(gòu)

龍芯2F處理器實現(xiàn)了64位的MIPSⅢ指令集，整數(shù)寄存器和浮點寄存器均為64位，支持o32/n32和n64的ABI類型。除了MIPS標準指令外，龍芯2F還提供了特有的整型計算和浮點計算指令。整型指令包括單條指令對3個寄存器進行操作的乘法、除法以及求模運算，浮點指令包括乘加、開平方等運算。

龍芯2F包含兩級Cache結(jié)構(gòu)，L1Cache數(shù)據(jù)和指令獨立，均為64kB;L2Cache數(shù)據(jù)和指令共享，為512kB.L1cache和L2cache都采用四路組相聯(lián)結(jié)構(gòu)，組內(nèi)采用隨機替換策略，cache行大小均為32字節(jié)。

3Glibc庫的優(yōu)化

根據(jù)對Glibc庫組成的分析，文章對其中的字符串與內(nèi)存處理，數(shù)據(jù)轉(zhuǎn)換，哈希表查找以及加密函數(shù)進行了優(yōu)化，以下各節(jié)分別介紹其優(yōu)化方法和優(yōu)化效果。

3.1字符串與內(nèi)存處理函數(shù)

字符串與內(nèi)存處理函數(shù)組提供了較為豐富的函數(shù)來完成各種操作，包括字符串與內(nèi)存的移動、比較和查找等。兩者的操作通常一一對應(yīng)，因為C語言中的字符串即用一段連續(xù)的內(nèi)存來表示，區(qū)別在于字符串用空字符NULL來表示結(jié)尾，而內(nèi)存塊的結(jié)尾由其大小確定。

對本組函數(shù)進行分析可知，部分函數(shù)之間的實現(xiàn)流程類似，如strlen和strnlen,memcpy和memccpy等。此外某些函數(shù)可通過調(diào)用其它函數(shù)來完成，如strcpy可由strlen與memcpy函數(shù)完成。

由于這一特點，字符串與內(nèi)存處理函數(shù)組的優(yōu)化方法可以相互借鑒，使用的優(yōu)化方法主要包括以下幾種：

優(yōu)化訪存指令。本組函數(shù)的處理流程一般是從一個或兩個內(nèi)存地址開始讀取內(nèi)存并進行相應(yīng)的操作。在讀取過程中考慮內(nèi)存地址的對齊情況及讀取單位，分別使用不同格式的訪存指令。

分塊處理。根據(jù)龍芯2F處理器的寄存器個數(shù)將待處理的字符串或內(nèi)存分塊，以充分利用寄存器進行循環(huán)展開。

匯編實現(xiàn)。本組函數(shù)包含了一些使用頻繁且對系統(tǒng)性能影響較大的函數(shù)，如內(nèi)存拷貝memcpy函數(shù)等，對此類函數(shù)我們使用匯編或內(nèi)嵌匯編來實現(xiàn)，以避免編譯器可能生成低效的代碼。

表l是本組函數(shù)中主要函數(shù)的優(yōu)化效果，以字符串規(guī)?；騼?nèi)存大小512B作為輸入。

3.2數(shù)據(jù)轉(zhuǎn)換函數(shù)

數(shù)據(jù)轉(zhuǎn)換函數(shù)包括字符串轉(zhuǎn)換為整數(shù)和浮點數(shù)。文章分別在每類函數(shù)中取一個例子說明優(yōu)化過程。

字符串轉(zhuǎn)換為整數(shù)包括strtol、strtoul、strtoll等函數(shù)，它們分別解析不同的整數(shù)類型，支持從2到36的轉(zhuǎn)換進制。各函數(shù)實現(xiàn)上不同的地方僅在于不同類型的整數(shù)大小范圍不同，處理流程類似。下面以strtol函數(shù)為例介紹優(yōu)化過程，它的功能為將字符串轉(zhuǎn)換為long型整數(shù)。

Glibc庫中strtol的實現(xiàn)使用普通的逐字節(jié)讀取并計算的方式。我們首先對轉(zhuǎn)換進制分情況處理，對于2的冪次方的進制，如2、4、8、16、32,字符串中的每個數(shù)字在二進制位上沒有關(guān)聯(lián)?？梢詫⑺鼈冎饌€轉(zhuǎn)換成二進制位后填入返回值的相應(yīng)位置，具有較快的轉(zhuǎn)換速度。其次十進制轉(zhuǎn)換是一種常用的情況，也將其單獨列出，可以省去對字母進行判斷。

給定進制后，在該進制下整數(shù)至多有多少位就可以確定。當字符串中的合法數(shù)字個數(shù)超過位數(shù)限制時，直接返回該類型下的值即可。當字符串中的合法數(shù)字小于位數(shù)限制時，可知解析后的結(jié)果不會超過該整數(shù)類型的表示范圍，此時我們將字符串進行分段并對解析進程進行循環(huán)展開。如果合法數(shù)字個數(shù)恰好等于位數(shù)限制，此時解析結(jié)果有超過該類型下值的可能性，首先將小于位數(shù)限制的部分解析完成后，再考慮一位數(shù)字。提前確定解析結(jié)果的范圍可以避免每次循環(huán)內(nèi)都要對是否超出該類型的值進行判斷。

取進制從2到36,字符串的長度從1到該進制下的值進行測試，得到各進制下的優(yōu)化效果如圖1所示，各進制的平均優(yōu)化比率為30.9%.

strtod、strtof、strtold等函數(shù)將字符串轉(zhuǎn)換為浮點數(shù)。我們以strtod函數(shù)為例進行介紹，它將字符串轉(zhuǎn)換為double型浮點數(shù)。

Glibc庫中strtod的實現(xiàn)使用高精度計算。首先遍歷整個字符串，找出其中的整數(shù)、小數(shù)和指數(shù)部分，各個部分分別使用高精度計算解析，再將結(jié)果合并。對于一般的實現(xiàn)來說，各個部分的取值不會太大，此時使用高精度計算時間消耗較大，改進的實現(xiàn)將每個部分再進行分

塊，對每個分塊使用整數(shù)進行解析，實現(xiàn)方式與strtol相同。各個部分的分塊解析完成后，使用一個longdouble類型作為臨時變量合并解析結(jié)果以避免精度丟失，將該變量轉(zhuǎn)換為doulble類型返回。對于strtof函數(shù)，使用double類型作為臨時變量。而對于strtold函數(shù)，使用上述方法無法保證精度，仍采用原始的實現(xiàn)。

由于雙精度浮點數(shù)的有效位數(shù)為16至17位，對字符串長度從1到17進行測試，得到各長度下的優(yōu)化效果如圖2所示，各長度的平均優(yōu)化比率為49.8%.

3.3哈希表查找函數(shù)

Glibc庫中哈希表所包含的關(guān)鍵字和數(shù)據(jù)分別為字符串和內(nèi)存塊，其相關(guān)的函數(shù)包括hcreate,hdestory以及hsearch,分別完成哈希表的創(chuàng)建，銷毀和查找。創(chuàng)建與銷毀操作都是性的，我們對查找操作進行優(yōu)化。

hsearch函數(shù)讀入字符串關(guān)鍵字作為參數(shù)，首先將其映射為整數(shù)關(guān)鍵值，接著使用雙重散列逐個取出元素進行判斷。

Glibc庫中字符串映射為整數(shù)的實現(xiàn)方法為，首先求得字符串的長度作為初值，接著將其不斷左移4位并從末尾到頭部逐個與字符串中的字符相加。該方法需要對字符串進行兩次遍歷，并且當字符串較長時，字符串的長度和進行累加的前幾個字符會被移出而不影響終的映射值。例如對32位的整型數(shù)來說，只有字符串的前8個字符對映射值有影響。

散列表（Hashtable,也叫哈希表），是根據(jù)關(guān)鍵碼值（Keyvalue）而直接進行訪問的數(shù)據(jù)結(jié)構(gòu)。也就是說，它通過把關(guān)鍵碼值映射到表中一個位置來訪問記錄，以加快查找的速度。這個映射函數(shù)叫做散列函數(shù)，存放記錄的數(shù)組叫做散列表。對不同的關(guān)鍵字可能得到同一散列地址，即key1≠key2,而f（key1）=f（key2），這種現(xiàn)象稱沖突。具有相同函數(shù)值的關(guān)鍵字對該散列函數(shù)來說稱做同義詞。綜上所述，根據(jù)散列函數(shù)H（key）和處理沖突的方法將一組關(guān)鍵字映象到一個有限的連續(xù)的地址集（區(qū)間）上，并以關(guān)鍵字在地址集中的"象"作為記錄在表中的存儲位置，這種表便稱為散列表，這一映象過程稱為散列造表或散列，所得的存儲位置稱散列地址。

3.4加密函數(shù)

Glibc庫中的加密函數(shù)為crypt函數(shù)，該函數(shù)單向加密給定的字符串，支持的算法包括MD5、SHA以及DES算法。由于MD5與DES算法的實現(xiàn)流程固定且做了較充分的展開，因此我們主要考慮SHA算法。針對該算法有設(shè)計硬件結(jié)構(gòu)進行的優(yōu)化，而我們的工作從代碼實現(xiàn)角度進行。下面以SHA-256為例說明優(yōu)化過程，其它SHA算法與之類似。

由于龍芯2F只支持小尾端的字符序，因此SHA算法首先將進行運算的字轉(zhuǎn)換為大尾端。原始實現(xiàn)中使用表達式x=（（n《24）|（（n0xff00）《8）|（（n》8）0xff00）|（n》24））進行轉(zhuǎn)換，其中n為無符號的32位整數(shù)。該轉(zhuǎn)換操作總共需要兩次與，四次移位與三次或運算，我們對其

進行改進，采用二分方的思想，使用表達式n1=（n《16）|（n16）和x=（（（n10xff00ff00）gt;8）|（n10xff00ff）《8））。其中計算n1的表達式可以由編譯器編譯為一條循環(huán)移位指令，這樣改進的實現(xiàn)共需要兩次與，三次移位與或運算，省去了移位與兩次或運算。

算法接下來的操作是消息擴散與迭代計算，計算公式分別如圖3和圖4所示。

我們對其計算過程進行層數(shù)為2的循環(huán)展開。對于迭代計算過程，循環(huán)展開之后還可以繼續(xù)進行賦值傳遞優(yōu)化，減少運算量和迭代次數(shù)。循環(huán)展開層數(shù)增加時，循環(huán)次數(shù)減小，但增加了循環(huán)內(nèi)的計算量，寄存器的數(shù)目滿足不了中間結(jié)果的保存，需要讀寫內(nèi)存，反而造成性能的