基于統(tǒng)計分析的指令高速緩存優(yōu)化技術(shù)

陳 辰,黃 凱,王鈺博,嚴(yán)曉浪

(浙江大學(xué)超大規(guī)模集成電路設(shè)計研究所,杭州310027)

基于統(tǒng)計分析的指令高速緩存優(yōu)化技術(shù)

陳 辰,黃 凱,王鈺博,嚴(yán)曉浪

(浙江大學(xué)超大規(guī)模集成電路設(shè)計研究所,杭州310027)

針對現(xiàn)有高速緩存技術(shù)計算方法復(fù)雜、適用性差的問題,提出基于統(tǒng)計分析的指令高速緩存優(yōu)化技術(shù)。采用GUN覆蓋率分析工具和性能分析工具對代碼進(jìn)行靜態(tài)分析,降低優(yōu)化過程中的計算復(fù)雜度。在軟件代碼方面,通過優(yōu)化的緩存塊著色算法、地址段靜態(tài)鎖定、代碼段選擇性不緩存等技術(shù),提高指令高速緩存的讀取效率。給出緩存鎖定選擇排序公式,用于判斷代碼段是否鎖定或不緩存,有效增加指令高速緩存的利用效率。實驗結(jié)果表明,該優(yōu)化技術(shù)能使程序執(zhí)行時間平均減少8%,緩存命中率平均提高23%。

高速緩存;優(yōu)化的緩存塊著色算法;過程排序;緩存鎖定;選擇性不緩存;緩存鎖定選擇排序

中文引用格式:陳 辰,黃 凱,王鈺博,等.基于統(tǒng)計分析的指令高速緩存優(yōu)化技術(shù)[J].計算機(jī)工程,2014, 40(10):76-80,85.

英文引用格式:Chen Chen,Huang Kai,Wang Yubo,et al.Instruction High-speed Cache Optimization Techniques Based on Statistic Analysis[J].Computer Engineering,2014,40(10):76-80,85.

1 概述

隨著集成電路制造工藝的進(jìn)步,處理器性能快速增長。根據(jù)摩爾定律[1],處理器速度每18個月就增加一倍,而存儲器性能的增長速度卻遠(yuǎn)遠(yuǎn)落后。位于存儲器和處理器之間的高速緩存可以有效緩解這個問題。處理器在運行中需要不斷地從外部獲取指令,因此,指令緩存讀取命中率對處理器性能有著重大影響[2]。在嵌入式系統(tǒng)中,由于緩存容量較小,影響尤為顯著,因此如何提高指令高速緩存的命中率,減少緩存缺失是提高系統(tǒng)整體性能的關(guān)鍵環(huán)節(jié)。

文獻(xiàn)[3]采用拆分循環(huán)過程,避免程序循環(huán)體大小大于緩存容量,并且采取了適當(dāng)壓縮代碼的方法進(jìn)行緩存優(yōu)化,這種方法能提高程序局部性及緩存命中率。文獻(xiàn)[4]提出動態(tài)DDP排序算法,在代碼段設(shè)置一個用來放置被調(diào)用的過程新代碼區(qū)域,按照調(diào)用的先后次序?qū)⑦^程放置在新代碼區(qū)域中。該方法雖然取得較好效果,但需要額外的代碼儲存空間。文獻(xiàn)[5]提出一種最小化最壞執(zhí)行時間的指令緩存鎖定算法,通過對任務(wù)最壞執(zhí)行時間的分析,選擇部分函數(shù)在編譯時鎖定到緩存中。文獻(xiàn)[6]提出了PH算法,該算法中的過程排序方法使用“最近最優(yōu)”原則,將頻繁互相調(diào)用的代碼放置在臨近位置,即每次選擇過程調(diào)用圖中調(diào)用頻率最高的2個節(jié)點,將它們合并成新的節(jié)點,重復(fù)處理,直到所有過程都處理完畢。PH算法中的過程排序方法可以減少產(chǎn)生緩存沖突的可能性,但是沒有將緩存大小、程序大小、緩存塊大小考慮在內(nèi),不具備通用靈活性。緩存塊著色算法[7]考慮了緩存大小、緩存塊大小等架構(gòu)特點,但依舊沒有考慮過程的大小,在子函數(shù)大小接近或大于緩存大小時,優(yōu)化效果不佳。

針對現(xiàn)有方法的不足,本文提出基于統(tǒng)計分析方法的指令高速緩存優(yōu)化技術(shù),主要創(chuàng)新點如下: (1)采用GUN覆蓋率分析工具(gcov)[8]和GNU性能分析工具(gprof)[9]在本地平臺中對程序進(jìn)行靜態(tài)分析,分析步驟簡便、運行速度快、信息獲取直觀;(2)針對低性能CPU的緩存容量較小、子函數(shù)大小接近或大于緩存容量的情況,對緩存塊著色算法進(jìn)行優(yōu)化,提出了優(yōu)化的緩存塊著色算法,提高了代碼局部性,減少了緩存沖突缺失;(3)提出2種采用gcov信息的指令高速緩存軟件優(yōu)化技術(shù),即緩存鎖定和選擇性不緩存技術(shù),并提出用于計算選擇鎖定或不可緩存代碼段的緩存鎖定選擇排序(Cache Locking Selection Sorting,CLSS)公式。

2 指令高速緩存優(yōu)化技術(shù)

2.1 針對小容量緩存優(yōu)化的過程排序

過程排序技術(shù)是指通過編譯器、連接器或者其他編譯工具,根據(jù)一定規(guī)則來改變代碼排列次序,以提高指令高速緩存命中率的技術(shù)[10]。它通過改變代碼原始排序,將頻繁互相調(diào)用的代碼段放置到相鄰或互不沖突的地址段上,降低了他們之間發(fā)生緩存映射沖突的概率,以減少指令高速緩存的沖突缺失、提高程序局部性。

gprof工具可以產(chǎn)生程序運行時的統(tǒng)計信息,包括相函數(shù)互調(diào)用次數(shù)等。根據(jù)緩存塊著色算法,使用gprof信息,構(gòu)造子函數(shù)調(diào)用圖對代碼進(jìn)行排序,如圖1所示,每個節(jié)點代表一個子函數(shù),之間的連線權(quán)值代表函數(shù)相互調(diào)用次數(shù)。

如圖2所示,將整個指令存儲器劃分為以緩存大小為單位的區(qū)間,假設(shè)緩存大小等于4個緩存塊的大小。不同區(qū)間的同種顏色的緩存塊中的數(shù)據(jù)會發(fā)生緩存沖突。

圖1 原始的子函數(shù)調(diào)用過程

圖2 緩存塊著色算法步驟

根據(jù)反匯編Obj文件,計算出程序大小,假設(shè)子函數(shù)A,B,F的大小各占用1個緩存塊,C,D各占用2個緩存塊,E占用4個緩存塊。

首先選取權(quán)值最大的一條邊CE,但由于E的大小與緩存大小相近,不論如何放置都會和其他子函數(shù)產(chǎn)生沖突,因此E最后進(jìn)行放置。先選取除CE外權(quán)值最大的邊AB,將AB放置到圖2步驟1所示位置。緊接著,選取BC。此處要保證B和C不發(fā)生沖突,所以,放置C時需要考慮B在緩存中的位置,選擇與B不同的緩存塊存放位置進(jìn)行放置。隨后,選取CD,D也需要和C處于不同的緩存塊位置。之后,將調(diào)用頻率最小的F插空放入序列中。最后,放入超過緩存大小的子函數(shù)E。

從圖2可以看出,由于子函數(shù)E體積大于緩存容量,因此不論如何放置,均會與其他子函數(shù)產(chǎn)生緩存沖突。

緩存塊著色算法適用于緩存大小較大、子函數(shù)均小于緩存容量的情況,但在多數(shù)低成本低性能CPU設(shè)計中,緩存容量較小,就會出現(xiàn)子函數(shù)大于緩存容量的情況。針對這一情況,提出了優(yōu)化的緩存塊著色算法,該算法將較大的子函數(shù)進(jìn)行拆分。同樣采用之前的程序,將較大的子函數(shù)E拆分為EA和EB,各占用2個緩存塊,新的子函數(shù)調(diào)用圖如圖3所示。經(jīng)過拆分子函數(shù)E后,可使子函數(shù)E一同進(jìn)入過程排序和放置的過程,放置過程如圖4所示。

對比圖2和圖4可以看出,圖2中子函數(shù)E與C發(fā)生了緩存沖突,而它們的調(diào)用次數(shù)高達(dá)80次。在圖4中,A和EA發(fā)生了緩存沖突,它們的互相調(diào)用次數(shù)僅有20次,顯然效果好于優(yōu)化前。采用優(yōu)化的過程排序方法,能進(jìn)一步細(xì)化子函數(shù)存儲位置,相比原算法更加減少了緩存沖突。

圖3 優(yōu)化后的函數(shù)調(diào)用過程

圖4 優(yōu)化后的緩存塊著色算法步驟

2.2 基于gcov信息的地址段靜態(tài)鎖定

在程序執(zhí)行過程中,可能會出現(xiàn)程序或某個循環(huán)的大小大于緩存的情況,這時緩存中的數(shù)據(jù)將會頻繁地進(jìn)行替換,當(dāng)某些頻繁訪問的數(shù)據(jù)和其他較少訪問的數(shù)據(jù)發(fā)生沖突時,若把頻繁訪問的數(shù)據(jù)替換出緩存將會導(dǎo)致更多的缺失,容量缺失成為主要制約因素,影響了程序執(zhí)行性能。

為此,本文采用靜態(tài)緩存鎖定來干預(yù)緩存替換策略,減少不必要的緩存替換。緩存鎖定機(jī)制是將某些數(shù)據(jù)鎖定在緩存中,當(dāng)發(fā)生緩存沖突時,被鎖定的數(shù)據(jù)不會被替換,在解除鎖定之前,對這些數(shù)據(jù)的訪問將總是命中。

為合理選擇需要鎖定的地址段,以達(dá)到最大化的優(yōu)化效果,提出一種通過gcov獲取反饋信息來選擇需要進(jìn)行緩存鎖定的子函數(shù)的技術(shù)。

gcov是一種代碼覆蓋率測試程序,可以獲取程序執(zhí)行的一些統(tǒng)計信息,主要包括:代碼執(zhí)行次數(shù),分支執(zhí)行次數(shù),子函數(shù)調(diào)用返回次數(shù),程序代碼覆蓋率和程序分支覆蓋率。

由于地址段靜態(tài)鎖定的目的是為了減少容量缺失,因此需要從容量不足而造成緩存替換的情況來分析那些子函數(shù)需要進(jìn)行鎖定。最簡單的方法就是尋找執(zhí)行次數(shù)最多的子函數(shù),對其進(jìn)行鎖定。但是,會出現(xiàn)有些子函數(shù)執(zhí)行次數(shù)雖不多,但其中包含大量循環(huán)的情況,必須加以考慮,對循環(huán)執(zhí)行次數(shù)多的子函數(shù)也進(jìn)行鎖定。因此,提出緩存鎖定選擇排序(Cache Locking Selection Sorting,CLSS)公式,對判斷子函數(shù)是否需要鎖定進(jìn)行量化排序。

記某個子函數(shù)中第N個循環(huán)分支LN的執(zhí)行次數(shù)為KN次,該子函數(shù)運行次數(shù)為J次,循環(huán)分支代碼覆蓋率為CN,子函數(shù)代碼覆蓋率為CALL,將這些數(shù)據(jù)帶入反匯編生成的Obj文件中,即可計算出匯編代碼的覆蓋率CN′、CALL′,和經(jīng)過編譯器編譯后,該子函數(shù)的匯編代碼所占空間大小SALL,此循環(huán)分支的匯編代碼大小SN,則此子函數(shù)執(zhí)行指令總大小λ為:

設(shè)該子函數(shù)執(zhí)行指令總大小與指令大小的比值為:

式(1)、式(2)主要通過子函數(shù)執(zhí)行次數(shù)、循環(huán)分支執(zhí)行次數(shù)、在仿真平臺中編譯后的代碼大小及代碼覆蓋率來計算該子函數(shù)指令對緩存替換的影響,CLSS值越大,則說明在程序執(zhí)行過程中,該子函數(shù)指令循環(huán)次數(shù)越多,執(zhí)行次數(shù)越多,該代碼局部性越好,需要將這些指令執(zhí)行系數(shù)大的子函數(shù)進(jìn)行鎖定操作。根據(jù)式(1)、式(2)中的各個參數(shù),可以計算出程序中每個子函數(shù)的CLSS值,由此可以選擇CLSS值最大的子函數(shù)進(jìn)行緩存鎖定。

2.3 基于gcov信息的代碼段選擇性不緩存

與采用地址段靜態(tài)鎖定技術(shù)的原因一樣,采用代碼段選擇性不緩存的原因也是為了降低由于緩存容量不足而造成的容量缺失。在指令存儲器中劃出一部分區(qū)域,使得儲存在該區(qū)域的代碼均不通過高速緩存,由CPU直接進(jìn)行讀取,如圖5所示,通過將部分使用頻率較低的代碼段置于存儲器的不可緩存區(qū)域,從而減少緩存不必要的替換。

圖5 代碼選擇性不緩存的判斷

根據(jù)CLSS計算對每個子函數(shù)進(jìn)行排序后,選出CLSS值最小的幾個子函數(shù),即運行次數(shù)少、循環(huán)少、替換次數(shù)少的子函數(shù),編譯時在linker文件中將其放入Flash的不可緩存區(qū)域中,從而使其不進(jìn)入Flash緩存進(jìn)行替換。

采用此技術(shù)在提升緩存命中率上優(yōu)點顯著,由于總體進(jìn)入緩存的代碼量減少,因此緩存容量缺失及許多不必要的緩存替換大大減少,多次運行的指令高速緩存效率大幅提高,緩存命中率較大提升。

3 技術(shù)實現(xiàn)

采用優(yōu)化的緩存塊著色算法進(jìn)行過程排序的流程如圖6所示,獲得GCC編譯并反匯編后的Obj文件,就可以計算每個子函數(shù)的指令大小,對于子函數(shù)大小大于緩存容量大小的1/2的函數(shù),對它們進(jìn)行拆分,拆分成若干個較小的子函數(shù)。當(dāng)所有的子函數(shù)都小于緩存容量大小的1/2后,通過gprof工具獲取函數(shù)調(diào)用信息,繪制函數(shù)調(diào)用圖,并用優(yōu)化的緩存塊著色算法進(jìn)行排序和放置。最后在link文件中根據(jù)算法結(jié)果調(diào)整函數(shù)放置位置和順序。

圖6 采用優(yōu)化緩存塊著色算法的過程排序流程

采用緩存鎖定或選擇性不緩存技術(shù)進(jìn)行過程排序的流程如圖7所示,GCC編譯后,通過gcov分析和反匯編文件中獲取計算CLSS所需要的循環(huán)分支執(zhí)行次數(shù)、子函數(shù)運行次數(shù)、匯編代碼的覆蓋率、經(jīng)子函數(shù)的匯編代碼所占空間大小、此循環(huán)分支的匯編代碼大小等信息。計算CLSS后,即可選擇CLSS值最大的子函數(shù)進(jìn)行緩存鎖定,或?qū)LSS值最小的子函數(shù)放置到不緩存區(qū)域中。若采用緩存鎖定,則配置寄存器,將需要鎖定的地址進(jìn)行鎖定操作。

圖7 采用緩存鎖定或選擇性不緩存的過程排序流程

若同時使用上述3種優(yōu)化技術(shù),則需要同時進(jìn)行g(shù)cov和gprof分析。如圖8所示,首先進(jìn)行過程排序技術(shù)中的函數(shù)拆分步驟,所有子函數(shù)大小都符合要求后,進(jìn)行CLSS的計算,然后將不需要緩存的子函數(shù)剔除,剩余需要緩存的子函數(shù)進(jìn)行優(yōu)化的緩存塊著色算法排序,最后在link文件中調(diào)整放置地址和順序,并配置寄存器,將需要鎖定的地址進(jìn)行鎖定操作。

圖8 采用3種優(yōu)化技術(shù)的過程排序流程

4 仿真結(jié)果分析

本文所采用的實驗平臺基于杭州中天微系統(tǒng)公司的CK803低成本、低功耗32位嵌入式處理器[11],采用高速緩存來加速指令Flash的訪問,CPU緩存容量為512 Byte,塊大小為8 Byte。指令存儲器Flash選用GSMC GRA_FLS2P5M28DA[12],大小320 KB,讀取位寬為32 bit。本文采用循環(huán)運行的Dhrystone、MD5加密算法、SHA1加密算法和Base64算法作為測試基準(zhǔn)程序。

如圖9、圖10所示,不同優(yōu)化技術(shù)對不同程序的效果不同,例如采用優(yōu)化的緩存著色算法技術(shù)時, SHA1加密算法的效果最好,原因是SHA1程序中, SHA1Final與SHA1Update 2個子函數(shù)相互調(diào)用次數(shù)達(dá)到57次,而其他各子函相互調(diào)用次數(shù)均較少,如表1所示,這2個子函數(shù)的相關(guān)性遠(yuǎn)高于其他子函數(shù),因此,這2個子函數(shù)的排序?qū)⒂绊懗绦蜻\行效率。相比PH算法和原始的著色算法,由于本文系統(tǒng)采用的緩存容量較小,因此本文提出的優(yōu)化的緩存塊著色算法有較大的優(yōu)勢,在緩存命中率和程序執(zhí)行速度上均有提高。而原始的緩存塊著色算法相比PH算法,由于考慮了緩存塊大小等相關(guān)因素,比PH算法也有所提高。

圖9 程序優(yōu)化前后運行時間對比

圖10 程序優(yōu)化前后緩存命中率對比

采用緩存鎖定優(yōu)化技術(shù)時,Dhrystone的效果最好,該技術(shù)針對子函數(shù)中循環(huán)大小接近或大于緩存大小的大循環(huán)時效果最好,能有效減少大循環(huán)中不斷的緩存替換。在本文提出的這3種技術(shù)中,此技術(shù)對程序性能提升優(yōu)化效果最好。

表1 SHA1 gprof分析結(jié)果

選擇性不緩存法在提高運行效率方面效果不如前2種技術(shù)好,但在提高緩存命中率方面效果比較明顯。如表2所示,在MD5程序采用此技術(shù)優(yōu)化后,緩存讀請求次數(shù)減少了47%,但命中數(shù)提高了16%,命中率提高了40%,主要原因是在MD5程序中,MD5 Transform子函數(shù)中的代碼全都只執(zhí)行一次,且無循環(huán),此子函數(shù)代碼量很大,CLSS值為1,將其存入不緩存區(qū)域后,減少了大量不必要的緩存替換。

表2 MD5采用選擇性不緩存時的緩存命中率對比

5 結(jié)束語

本文提出了多種指令高速緩存的優(yōu)化技術(shù),包括優(yōu)化的緩存塊著色算法、地址段靜態(tài)鎖定、代碼段選擇性不緩存等技術(shù),從軟件代碼方面顯著提高了指令高速緩存讀取效率。本文還給出緩存鎖定選擇排序(CLSS)公式,用于選擇代碼段鎖定或不緩存,并在CK803原型平臺中加以實現(xiàn)。實驗結(jié)果證明,采用上述優(yōu)化技術(shù)可降低程序初次分析時的復(fù)雜程度,減少了優(yōu)化所需的時間,并且能有效地提高指令高速緩存命中率,改善程序執(zhí)行性能。每個測試基準(zhǔn)程序在選擇了優(yōu)化效果最佳的一種優(yōu)化方案后,可根據(jù)程序運行結(jié)果計算出:運行時間平均能減少8%,緩存命中率平均能提高23%。后續(xù)研究將針對基本塊進(jìn)行優(yōu)化,將本文的優(yōu)化技術(shù)應(yīng)用到細(xì)粒度的軟件優(yōu)化中。

[1] Moore G E.Cramming More Components onto Integrated Circuits[J].Electronics,1965,38(8):114-117.

[2] Hennessy J L,Patterson D A.Computer Architecture:A QuantitativeApproach[M].Amsterdam,Holland: Elsevier,2012.

[3] 宋立鋒,戴青云.H.264實時編碼的指令Cache優(yōu)化[J].電子學(xué)報,2008,36(8):1615-1619.

[4] Scales D J.EfficientDynamic Procedure Placement [Z].1998.

[5] 曾 輝.最小化最壞執(zhí)行時間的指令緩存鎖定算法[J].武漢大學(xué)學(xué)報:理學(xué)版,2010,56(6):697-703.

[6] Pettis K,Hansen R C,Davidson J W.Profile Guided Code Positioning[J].ACM SIGPLAN Notices,2004,39 (4):398-411.

[7] Hashemi A H,Kaeli D R,Calder B.Efficient Procedure Mapping Using CacheLineColoring[J].ACM SIGPLAN Notices,1997,32(5):171-182.

[8] Han Yiming.Application Performance Evaluation on Different Compiler Optimizations[J].Advances in Computer Science and Its Applications,2013,2(3):410-415.

[9] Mishra A,Garg K,Asati A R,et al.Hardware Software Co-design Using Profiling and Clustering[C]// Proceedings of 2012 International Conference on Communication,Information&Computing Technology.[S.l.]: IEEE Press,2012:1-4.

[10] 張定飛,趙克佳,黃 春.指令Cache優(yōu)化中代碼重排技術(shù)研究[J].計算機(jī)工程與應(yīng)用,2006,42(7):28-30.

[11] 潘 赟.CK-CPU嵌入式系統(tǒng)開發(fā)教程[M].北京:科學(xué)出版社,2011.

[12] GSMC Embedded Flash IP Datasheet(ESF2-130E 320Kx8 E-Flash IP(FLS2P5M28DA))[EB/OL].(2012-05-03). http://sso.gracesemi.com/domino/servlet/GetCVSFile.

編輯 陸燕菲

Instruction High-speed Cache Optimization Techniques Based on Statistic Analysis

CHEN Chen,HUANG Kai,WANG Yu-bo,YAN Xiao-lang
(Institute of VLSI Design,Zhejiang University,Hangzhou 310027,China)

Aiming at the problem that existing cache technology has computational complexity and poor applicability, instruction cache optimization techniques based on statistic analysis by using GNU coverage analysis tool and performance analysis tools are proposed.It uses optimization techniques,including optimized cache line coloring algorithm,static use of cache locking and code selectively non-caching,can significantly improve the efficiency of instruction cache reading. Also a Cache Locking Selection Sorting(CLSS)is proposed to evaluate the code segment which can be locked or noncached.Simulations show that these techniques make the program running time reduced by 8%,and make the cache hit rate increased by 23%.

high-speed cache;optimized cache block coloring algorithm;process sorting;cache locking;selective no cache;Cache Locking Selection Sorting(CLSS)

1000-3428(2014)10-0076-05

A

TP301

10.3969/j.issn.1000-3428.2014.10.015

陳 辰(1988-),男,碩士研究生,主研方向:數(shù)字集成電路設(shè)計,緩存優(yōu)化;黃 凱,副教授、博士;王鈺博,碩士研究生;嚴(yán)曉浪,教授。

2013-11-25

2013-12-19E-mail:373144881@qq.com