基于統計分析的指令高速緩存優化技術

陳 辰,黃 凱,王鈺博,嚴曉浪

(浙江大學超大規模集成電路設計研究所,杭州310027)

基于統計分析的指令高速緩存優化技術

陳 辰,黃 凱,王鈺博,嚴曉浪

(浙江大學超大規模集成電路設計研究所,杭州310027)

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

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

中文引用格式:陳 辰,黃 凱,王鈺博,等.基于統計分析的指令高速緩存優化技術[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 概述

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

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

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

2 指令高速緩存優化技術

2.1 針對小容量緩存優化的過程排序

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

gprof工具可以產生程序運行時的統計信息,包括相函數互調用次數等。根據緩存塊著色算法,使用gprof信息,構造子函數調用圖對代碼進行排序,如圖1所示,每個節點代表一個子函數,之間的連線權值代表函數相互調用次數。

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

圖1 原始的子函數調用過程

圖2 緩存塊著色算法步驟

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

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

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

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

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

圖3 優化后的函數調用過程

圖4 優化后的緩存塊著色算法步驟

2.2 基于gcov信息的地址段靜態鎖定

在程序執行過程中,可能會出現程序或某個循環的大小大于緩存的情況,這時緩存中的數據將會頻繁地進行替換,當某些頻繁訪問的數據和其他較少訪問的數據發生沖突時,若把頻繁訪問的數據替換出緩存將會導致更多的缺失,容量缺失成為主要制約因素,影響了程序執行性能。

為此,本文采用靜態緩存鎖定來干預緩存替換策略,減少不必要的緩存替換。緩存鎖定機制是將某些數據鎖定在緩存中,當發生緩存沖突時,被鎖定的數據不會被替換,在解除鎖定之前,對這些數據的訪問將總是命中。

為合理選擇需要鎖定的地址段,以達到最大化的優化效果,提出一種通過gcov獲取反饋信息來選擇需要進行緩存鎖定的子函數的技術。

gcov是一種代碼覆蓋率測試程序,可以獲取程序執行的一些統計信息,主要包括:代碼執行次數,分支執行次數,子函數調用返回次數,程序代碼覆蓋率和程序分支覆蓋率。

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

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

設該子函數執行指令總大小與指令大小的比值為:

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

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

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

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

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

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

3 技術實現

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

圖6 采用優化緩存塊著色算法的過程排序流程

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

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

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

圖8 采用3種優化技術的過程排序流程

4 仿真結果分析

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

如圖9、圖10所示,不同優化技術對不同程序的效果不同,例如采用優化的緩存著色算法技術時, SHA1加密算法的效果最好,原因是SHA1程序中, SHA1Final與SHA1Update 2個子函數相互調用次數達到57次,而其他各子函相互調用次數均較少,如表1所示,這2個子函數的相關性遠高于其他子函數,因此,這2個子函數的排序將影響程序運行效率。相比PH算法和原始的著色算法,由于本文系統采用的緩存容量較小,因此本文提出的優化的緩存塊著色算法有較大的優勢,在緩存命中率和程序執行速度上均有提高。而原始的緩存塊著色算法相比PH算法,由于考慮了緩存塊大小等相關因素,比PH算法也有所提高。

圖9 程序優化前后運行時間對比

圖10 程序優化前后緩存命中率對比

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

表1 SHA1 gprof分析結果

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

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

5 結束語

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

[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優化[J].電子學報,2008,36(8):1615-1619.

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

[5] 曾 輝.最小化最壞執行時間的指令緩存鎖定算法[J].武漢大學學報:理學版,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優化中代碼重排技術研究[J].計算機工程與應用,2006,42(7):28-30.

[11] 潘 赟.CK-CPU嵌入式系統開發教程[M].北京:科學出版社,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-),男,碩士研究生,主研方向:數字集成電路設計,緩存優化;黃 凱,副教授、博士;王鈺博,碩士研究生;嚴曉浪,教授。

2013-11-25

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