（電子科學(xué)與技術(shù)專業(yè)論文）面向性能優(yōu)化的壓縮cache技術(shù)研究.pdf

國防科學(xué)技術(shù)大學(xué)研究生院博士學(xué)位論文 別，并將其記錄到一個錯誤記錄表m r t ( m i s t i i r - e c o r dt a b l e ) 中，然后根據(jù)此 記錄表對l r u 替換錯誤進(jìn)行及時糾正。模擬實(shí)驗(yàn)表明，m l r u c 能有效地改善 l 2 壓縮c a c h e 的替換行為，減少l 2 壓縮c a c h e 的失效率。 4 研究了壓縮c a c h e 技術(shù)對多線程處理器性能的影響，并通過模擬實(shí)驗(yàn)驗(yàn)證 了u c c h 結(jié)構(gòu)能夠改善多線程處理器的性能。由于多線程處理器中有多個同時運(yùn) 行的線程共享整個片內(nèi)c a c h e 層次結(jié)構(gòu)，破壞了從l l 數(shù)據(jù)c 礎(chǔ)倫到l 2c a c h e 的數(shù) 據(jù)局部性，增大了c a c h e 失效率，并使l 1 l 2 主存之間的總線傳輸帶寬壓力顯著增 長，因此，雖然多線程處理器降低了對訪存延遲的敏感性，但卻顯著增加了對c a c h e 層次結(jié)構(gòu)的容量以及訪問帶寬的敏感性。由于u c c h 結(jié)構(gòu)能夠顯著增加l 1 數(shù)據(jù) c a c h e 和l 2c a c h e 的有效容量，同時由于在l 1 l 2 主存之間直接以壓縮格式傳輸數(shù) 據(jù)，能顯著降低l l - l 2 主存之間的總線傳輸帶寬需求，因此u c c h 結(jié)構(gòu)能夠改善 s m t 處理器的訪存性能。 主題詞：s f p c 壓縮算法，壓縮c a c h e ，部分c a c h e 行預(yù)取，壓縮c a c h e 替換 策略，s m t ，m l r u c 替換策略 第i i 頁 國防科學(xué)技術(shù)大學(xué)研究生院博士學(xué)位論文 a b s t r a c t s m c e 劬o v a t i o n si nc m o st e c h i l o l o g ) ri nr e c e n ty e a r sh a v el e dt 0 耐o 咖a n c e g a pk 帆瞎e np r o c e s s o r 觚dm e m o 哆w i d e l l i n g ，m o d e mp f o c e s s o f su o n eo rm o f e l e v e l so fo n c l l i pc a c h e st 0a l l e v ia ：t et h ee v e r i n c r e a s i n gp r e s s u r eo fm e m o 哆a c c e s s e s i n a d d i t i 嗎舔也ec 螂d e i l s 蚵硫r e a l s i n g ，c 螂m u l t i 即c e s s o r s ( m p ) 觚dm u l t i 缸e a d 魄 似t ) a r eb e c o m i n gm 2 l i n s 缸e a i i la r c l l i t e c 加r e so fc u n e n tp r o c e s s o rd e s i g n t h eb o t l l a r c l l i t e c t u r e sc a i lg r e a t l yi i l l p r o v ep r o c e s s o rp e 墑珊a n c ea n dt t l r o 咖u tb ye x p l o i ! t i i 瑪 b o t l lm r e a d 一1 e v e l 鋤dh 1 舭t i o n - l e v e lp a r a l l e l i s r 瑪b 毗m e 粵o w i l l gm e m o 巧a c c e s s d e m a r l di nm p m te n v i l - o 伽n tc h a l l e i 培et 1 1 et 王l r o u g h p u ta b i l 塒o f 廿1 e i ri n e m o 巧 s u b s y s t e m t h ep r o c e s s o rd e s i g n e r 咖_ l s td e t e m l i n em et r a d e o f fb e t 、) v nc o r e s 鋤d c a c h e si 1 1a 缸x e da r e ab u d g e ts o 也a tn e 弛【e rc o r e sn o rc a c h e si s 也eo i l l yp e 雨粼e b o t t l e n e c k c o m p r e s s e dc a c h et e c l l n o l o 影c 趾c l l a i l g e 也e 砌e o f fb e 押e e nc o r e s 觚d c a c l l e sa 1 1 da 1 1 0 wad e s i 口w h e r em o r eo m c l 卸a r e ai sa l l o c a t e dt op r o c e s s o rc o f e ss i i l c e o n - c k pc a c h ec o m p r e s s i o nc 觚i i l c 麟et l l ee 廊c t i v ec a c h es i z e 塒也o u ts i 鰣6 c 鋤t l y i n c r e 硒i i 培i t sa r e a 赳l da v o i ds o r n em i s s e s u 0 n l m a t e l y ，c a c l l ec o m p r e s s i o na l s oh 嬲a n e g a t i v cs i d ee f i f e c t ，s i n c ec o m p r e s s e dc a c h el i i l e sl m ，et ob cd e c o m p r e s db e f 0 r e b e i i 塢u s e db yp r o c e s s o r t h i s l e a n sm a ts t o r i n gc o m p r e s s e dl i i l e si i l c r e a s e sc a c h e 脅 l a t e n c y s ot h i sp a p e rr e a r c h e do nt 1 1 ec o m p r e s s e dc a c h et e c l l n o l o g yf o rp e r f o n 】姐n c e o p t i l l l i z a t i o n t h em e t h o d s ，s u 盤舔o p t i m i 咖gc o m p s s e dc a c h el i i e r a r c h y ，s i n l p l i 母試g c o m l ) r e s s e da l g o r i n l i i l 趾d 婦p r o 譏n gc a c h er e p l a c e m e n tp o l i c ye t c w e r ep r o p o s e dt 0 i m p r o v ep e 0 m 啪c eo fc o m p r e s s e dc h e t h em a i l lc o n t r i b u t i o n so ft h i sp 叩e ra r e 舔 f o l l o 、s ： 1 w 池s i i n p l i 矽i n gm ef r e q u e n tp a 他mc o m p r e s s i o n ( f p c ) a l g o r i t h i i l ，w m c h u s e db yl 2c a c h ec o m p r e s s i o 瑪觚dd i v i d i n gt l l ed e c o l p r e s s i o np r o c e s so f c o n l p r e s s e dc a c h el i i l ei i l t ot w os t a g e s ，、v ep r o p o s e dan o v e ld e c o l n p r e s s i o n p r o c e s so fl 2c o m p r e 豁e dc a c h e l i n eb a s e d0 ns i i n p l ef r e q u e n tp a t t e m c o n l p r e s s i o n ( s - f p c ) a l g o r i n 1 1 1 ep r o p o s e ds c h e r n e c a i id e c r e a s el 2 d e c o m p r e s s e dl a t e n c ylc y c l e 鋤ds u p p o r tc o n l p r e s s i n gl ld a 協(xié)c a c h ed a t a w ee v a l u a t e dt l l es c h e i n eb ys 婦u l a t i o ne x p e r h e n t s 趾dd e s c r i b e d 吐l e h a r d 、硼埴ei i l l p l e m e n t a t i o no f 也ec o m p r e s s i o ns c h e m ei i ld e t a i l 2 w ep r o p o s e dau i l i f i e dc o n l p r e s s e dc a c l l e1 1 i e r a r c l l y c c h ) m a tu s e sa u n i f i e dc o m p f e s s i o na l g 嘶t l 皿i i lb o t l ll 1d - c a c h e 鋤dl 2c a c h e ，c 2 l l l e d s i m p l ef r e q u e n tp a 嗆mc o m l ) r e s s i o n ( s - f p c ) u c c hc a i li n c r e a t h ec a c h e c a p a c 時o fl 1d c a c h e 觚dl 2c a c h e 謝t l l o u ta i l ys a c r i f i c eo f t l l el 1c a c h e a c c e s sl a t e n c y t h el a y o u to fc o m p r e s s e dd a t ai nl ld a t ac a c h eo fu c c h c n a b l e sp a n i a lc a c h el i n ep r e f e t c h i n g 觚dd o e sn o ti n 仃o d u c ep r e f l e t c hb u f f e r s o ri n c r e a c a c h ep o l l u t i o na i l dm 鋤。巧仃a m c t h ee x p e 血n e n ts h o w su c c h 第i i i 頁 國防科學(xué)技術(shù)大學(xué)研究生院博士學(xué)位論文 c a nd i s t i i l c t l yi i i l p r o v et ：h cp e r f o m 砌c e 3 w e p r o p o s e dan o v e lm 礎(chǔ)f i e d l r ur 印l a c e m e n tp o l i c yf o rc o m p r e s dc a c h e 。 ( m l r u - c ) m l l w - cr e p l a c e m e mp o l i c yu s e se x 仃at a g si i lc o m p r c s s e dc a c h e t oc o n s t n l c tas h a d o wt a gs t n l c t ，w m c hb eu s e dt 0i d e m i 母a i l dr c l c o r dt h e i i l i s t a k er e p l a c e m e mi 1 1l r u p o l i c y t h e 面s t a k er e p l a c e m e 鵬i 1 1l r up o l i c y r e c o r d e db ys h a d o wt a gs 咖c tw o u l db es t o r e di nm i m 婦r e c o r dt a b l e ( m r n l em l r u c 、o u l dc o n e c ta 艙m i s t 2 d 汜r e p l a c e m e n td e c i s i o n a c c o r d i i 培t ot h ei i l i s t a 】k er e p l a c e m e n tr e c o r di 1 1mr 1 t h ee x p e r i i i l e n ts h o w s l a tm l r u cc a ne v i d e n t l yd e c r e a s el 2c o n l p r e s s e dc a c h en l i s sr a t e 4 w ep r o p o s e du s i i l gc o i n p r e s s e dc a c h et e c l l i l o l o g ) ，t o 卸r o v em l l l t i 吐l r e a d i n g p r o c e s s o rp e r f 0 冊a j l c e b e c a u s e l ei l a t al o c a l i t vo fl1d c a c h ea n dl 2c a c h e i sh 1 1 n e db y 蛐g(shù) o n 出pc a c h eh i 眈眥h yb e m e e nt l l i e a d s ，m tt e c h n o l g y d i s 墻t l yi r l c r e a s e st h ec a c h ei n i s s 瑚l t e 鋤dm e m o r y 仃a 伍c t h ed e m a l l d sf o r c a c h ec a p c i 鑼鋤1 d 紕b u sb 鋤d 、) l r i i b e t w e e nl e v e l so fc a c h = c si r k r e a s e a p p a r e n t l y b e c a u s eo l l ru c c hs c h e r n ec a ni r l c r e a s ec 印a c 塒o fl ld c a c h e 趾dl 2c a c h ea n dd e c r e a s e 血s sr a 滄o fb o t l ll 1d c a c h ea n dl 2c a c h e d i s t h l c t l y ，i tc 鋤a l l e v i a t et 1 1 el1 - l 2 i 瑚i i lm e m o 珂b a l l d 慚d 也d e m 弛da n d i m p r o v em ep e r f o n n a n c eo fm tp 】0 c e s s o r k e yw 0 r d s ：s - f p c ，c o m p r e s s e dc a c h e ，p a r t i a ic a c h el i n ep r e f e t c h i n g ， c o m p r e s s e dc a c h er e p i a c e m e n tp o c y ，s m t ，m l r u - c r e p l a c e m e n tp o “c y 第i v 頁 國防科學(xué)技術(shù)大學(xué)研究生院博士學(xué)位論文 表目錄 表2 1 常見模式壓縮( f p c ) 編碼1 7 表2 2c a c h e 重疊壓縮的常見值編碼2 4 表3 1s f p c 壓縮編碼3 l 表3 2 基準(zhǔn)處理器配置4 7 表4 1l 2 壓縮c h e 在l r u 、m l 烈j c 、o p t 替換策略下的失效率6 9 表5 1s m i 處理器的基本配置8 1 表5 2 多線程工作負(fù)載8 2 第l v 頁 國防科學(xué)技術(shù)大學(xué)研究生院博士學(xué)位論文 圖目錄 圖1 11 9 8 0 年以來存儲器和c p u 性能隨時間而提高的情況( 以1 9 8 0 年時的性能為 基準(zhǔn)) ：! 圖1 2c a c h e 子塊大小對內(nèi)部碎片的影響。7 圖2 1 動態(tài)常見值字典結(jié)構(gòu)1 6 圖2 2m x t 系統(tǒng)中的l 3c a c h e 行通過c t t 映射到物理的壓縮存儲行。1 8 圖2 3h a l l n o r 的i i c c 壓縮c a c h e 結(jié)構(gòu)19 圖2 4e k m a i l 的基于f p c 編碼的壓縮主存的尋址方式正文內(nèi)容2 1 圖2 5 面向低功耗的常見值壓縮l 1 數(shù)據(jù)c a c h e 結(jié)構(gòu)2 2 圖2 6 面向高性能的常見值壓縮l l 數(shù)據(jù)c a c h e 結(jié)構(gòu)。2 3 圖2 7c a c h e 重疊壓縮存儲結(jié)構(gòu)一2 4 圖2 8p p u j 撒的l 1 壓縮c a c h e 的壓縮數(shù)據(jù)布局2 5 圖3 1 砧艙設(shè)計(jì)的f p c 壓縮c a c h e 層次結(jié)構(gòu)2 9 圖3 2a 1 a a 設(shè)計(jì)的f p c 壓縮c a c h e 的解壓縮流水線結(jié)構(gòu)2 9 圖3 3 各種常見模式在測試程序引用中的分布31 圖3 4s f p c ，f p c ，x r l ，b r c l 的平均壓縮率3 3 圖3 5 壓縮c a c h e 層次結(jié)構(gòu)3 4 圖3 6l 1 壓縮數(shù)據(jù)c a c h e 數(shù)據(jù)存放格式3 5 圖3 7l 1 壓縮數(shù)據(jù)c a c h e 結(jié)構(gòu)3 6 圖3 8l 1 壓縮數(shù)據(jù)c a c h e 的訪問流程3 7 圖3 9l 2 壓縮c a c h e 的數(shù)據(jù)存放格式3 8 圖3 1 0l 1c h e 的解壓縮器4 0 圖3 1 ll 1 數(shù)據(jù)c a c h e 的壓縮器4 1 圖3 1 2l 2 到l l 壓縮c a c l l e 行拆分流水線4 3 圖3 1 3l 2 到l 1 壓縮c a c h e 行拆分流水線第一站由前綴計(jì)算壓縮字長度模塊4 4 圖3 1 4 拆分流水線第二站4 4 圖3 1 5l l 數(shù)據(jù)c a c h e 有效容量隨c a c h e 行尺寸變化時的改變4 9 圖3 1 6 四種不同配置下基準(zhǔn)處理器l l 數(shù)據(jù)c a c h e 失效率相對于b c 配置的比較5 0 圖3 1 7 四種不同配置下基準(zhǔn)處理器l 2c a c h e 失效率相對于b c 配置的比較。5 0 圖3 1 8 四種不同配置下基準(zhǔn)處理器性能( i p c ) 相對于b c 配置的比較5 0 圖4 1 一個存儲引用序列的實(shí)例5 4 圖4 2圖4 1 的引用序列分別在傳統(tǒng)c a c h e 的l r u 與o p t 替換策略下的c a c h e 行為 ! ；! ； 第v 頁 國防科學(xué)技術(shù)大學(xué)研究生院博士學(xué)位論文 圖4 3 壓縮c a c h e 替換行為的描述5 8 圖4 4l i 替換錯誤探測機(jī)制的結(jié)構(gòu)。6 0 圖4 5l r u 壓縮c a c h e 行為仿真器6 4 圖4 6o p t 壓縮c a c h e 行為仿真器6 6 圖4 7 壓縮c a c h e 替換策略仿真系統(tǒng)結(jié)構(gòu)圖6 7 圖4 8l 2 壓縮c a c h e 在l r u 、m l r u c 、o p t 替換策略下失效率相對于l r u 的比較 6 9 圖5 1 指令發(fā)射槽的利用情況7 5 圖5 2s m 與c 中啟動新線程后對l 2c a c h e 訪存壓力的變化情況( 來自【8 2 】) 7 8 圖5 3 模擬的多線程處理器壓縮c a c h e 層次結(jié)構(gòu)8 0 圖5 4 四種c a c h e 配置在不同工作負(fù)載下的性能( i p c ) 比較。8 3 圖5 5 四種c a c h e 配置在不同工作負(fù)載下l ld c a c h e 的失效率相對于b c 配置的比較 8 z i 圖5 6 四種c a c h e 配置在不同工作負(fù)載下l 2c a c h e 的失效率相對于b c 配置的比較8 4 圖5 7 四種配置下，l 1 l 2c a c h e 之間的總線占用率相對于基本配置的比較8 5 圖5 8 四種c a c h e 配置下，l 2c a c h e 與主存之間訪問帶寬需求與b c 的比較8 6 第v l 頁 獨(dú)創(chuàng)性聲明 本人聲明所呈交的學(xué)位論文是我本人在導(dǎo)師指導(dǎo)下進(jìn)行的研究工作及 取得的研究成果。盡我所知，除了文中特別加以標(biāo)注和致謝的地方外，論 文中不包含其他入已經(jīng)發(fā)表和撰寫過的研究成果，也不包含為獲得國防科 學(xué)技術(shù)大學(xué)或其它教育機(jī)構(gòu)的學(xué)位或證書而使用過的材料。與我一同工作 的同志對本文研究所做的任何貢獻(xiàn)，均已在論文中作了明確的說明并表示 謝意。 學(xué)位論文題目：亙自性能籩絲鮑匡緝曼地呈撞苤巫究 學(xué)位論文作者簽名： 翌耋b 聾日期：z 叫年午月“日 學(xué)位論文版權(quán)使用授權(quán)書 本人完全了解國防科學(xué)技術(shù)大學(xué)有關(guān)保留、使用學(xué)位論文的規(guī)定。本 人授權(quán)國防科學(xué)技術(shù)大學(xué)可以保留并向國家有關(guān)部門或機(jī)構(gòu)送交論文的 復(fù)印件和電子文檔，允許論文被查閱和借閱；可以將學(xué)位論文的全部或部 分內(nèi)容編入有關(guān)數(shù)據(jù)庫并進(jìn)行檢索，可以采用影印、縮印或掃描等復(fù)制手 段保存、匯編學(xué)位論文。 ( 保密學(xué)位論文在解密后適用本授權(quán)書。) 學(xué)位論文題目：亟囪性能岱他的匡纏咝叢撞薟硒究 學(xué)位論文作者簽名： 里墨叢釜日j 朝：卅年牛月二5 日 作者指導(dǎo)教師簽名： ；幺紅絲 r 期：枷7 年p 月形日 國防科學(xué)技術(shù)大學(xué)研究生院博士學(xué)位論文 第一章緒論 為填補(bǔ)處理器與主存在速度上的巨大差異，現(xiàn)代計(jì)算機(jī)系統(tǒng)一般都在處理器 內(nèi)核與主存之間設(shè)置一級或多級快速小容量的c a c h e ，形成層次式訪存結(jié)構(gòu)，利用 局部性原理來改進(jìn)系統(tǒng)的訪存性能。因此，提高c a c h e 的性能對于提升整個計(jì)算機(jī) 系統(tǒng)的性能有著重要的意義。 c a c h e 的性能與它的容量、訪問延遲和帶寬、c a c h e 行大小，相聯(lián)度、替換策 略等結(jié)構(gòu)參數(shù)【1 9 】有關(guān)，同時程序本身的局部性也對c a c h e 性能的發(fā)揮起著重要的作 用。隨著多線程技術(shù)的出現(xiàn)，處理器內(nèi)核雖然對訪存延遲的容忍度有了很大提高， 但同時也要求更大的c a c h e 容量和訪問帶寬。壓縮c a c h e 是一種利用數(shù)據(jù)壓縮方法 保存c a c h e 數(shù)據(jù)的技術(shù)，它能夠在不顯著增加c h e 面積的情況下顯著提高它的有 效容量、降低失效率，減少存儲層次間的數(shù)據(jù)交換。 本文研究了利用壓縮c a c h c 技術(shù)改善處理器性能的方法，對壓縮c a c h e 的壓縮 編碼算法以及層次結(jié)構(gòu)的設(shè)計(jì)實(shí)現(xiàn)，壓縮c a c h e 替換策略的優(yōu)化，以及利用壓縮 c a c h e 技術(shù)改善多線程處理器的訪存性能展開了深入研究。 本章的組織結(jié)構(gòu)如下：1 1 節(jié)介紹了壓縮c a c h e 技術(shù)的研究背景與意義：1 2 節(jié) 介紹了面向性能優(yōu)化的壓縮c a c h e 技術(shù)所面臨的幾個問題；1 3 節(jié)結(jié)合壓縮c a c h e 的性能估算公式給出本文對壓縮c a c h e 性能進(jìn)行優(yōu)化的方法；1 4 節(jié)敘述了本文的 主要工作；1 5 節(jié)給出本文的組織結(jié)構(gòu)。 1 1 1 存儲墻問題 1 1 研究背景和意義 存儲器是計(jì)算機(jī)系統(tǒng)的核心部件之一，它的性能好壞直接影響到整個計(jì)算機(jī) 系統(tǒng)的性能。如何平衡存儲器系統(tǒng)的容量、速度和價格，始終是計(jì)算機(jī)體系結(jié)構(gòu) 設(shè)計(jì)的關(guān)鍵問題之一。但是，在計(jì)算機(jī)系統(tǒng)中，處理器與存儲器性能的提升并不 同步。隨著半導(dǎo)體工藝水平的發(fā)展以及處理器微體系結(jié)構(gòu)技術(shù)的進(jìn)步，處理器時 鐘頻率增長的速度遠(yuǎn)遠(yuǎn)超過了存儲器訪問周期縮短的速度，這導(dǎo)致兩者之間的性 能差距越來越大。如圖1 1 i l 】所示，在1 9 8 0 年至1 9 8 6 年間，處理器的性能以每年 3 5 的速度遞增，而從1 9 8 7 年開始，處理器的性能則是以每年6 0 的速度遞增。而 存儲器性能提高的速度卻相對慢很多。例如，d r a m 的訪問速度每年大約只提高7 。 因此，兩者的差距每年都在以大約5 0 的速度增加，從而產(chǎn)生了“存儲墻”問題。另 外，隨著處理器中i l p 開發(fā)技術(shù)的不斷發(fā)展，對存儲器性能的要求也隨之增強(qiáng)。 由于在每個時鐘周期，處理器需要同時執(zhí)行多條指令，這就要求存儲器能夠及時 第l 頁 國防科學(xué)技術(shù)大學(xué)研究生院博士學(xué)位論文 向計(jì)算內(nèi)核提供更多的指令和數(shù)據(jù)。為此，現(xiàn)代微體系結(jié)構(gòu)設(shè)計(jì)者普遍采用在處 理器片內(nèi)設(shè)置一級或多級c a c h e ，利用程序的局部性原理來解決這一問題。 毋$ 毋毋毋孝尊霉害毋竄霉毋葶零擎露霉窖拿葶爺荸毋零孝 圖l ，l1 9 8 0 年以來存儲器和c p u 性能隨時問而提高的情況( 以1 9 踮年時的性能為基準(zhǔn)) c a c h e 是位于處理器內(nèi)核與主存之間的一級或多級速度快、容量較小的高速緩 沖存儲器，它與主存一道形成層次式訪存結(jié)構(gòu)，以便減少具有高延遲開銷的主存 訪問次數(shù)，提高系統(tǒng)性能。在使用c a c h e 訪存結(jié)構(gòu)的基礎(chǔ)上，一些微體系結(jié)構(gòu)技術(shù) 也被應(yīng)用于緩解t 存儲墻問題：如存儲前瞻1 2 ，3 】、亂序執(zhí)行【2 眙1 】技術(shù)通過提前調(diào)度 訪存指令，或者將訪存指令與其它有用指令的執(zhí)行相重疊來隱藏訪存指令的延遲； 預(yù)取h ，5 ，6 ，7 ，8 、線程級前瞻和多線程執(zhí)行i l o ，1 2 ，1 3 t 1 4 ，15 1 、r l 麟虹a d 執(zhí)行1 1 6 ，1 7 j 等技術(shù)則通 過增加訪存操作的并行性來緩解訪存延遲對性能的影響；值預(yù)測【ls 】技術(shù)則通過預(yù) 測l o a d 指令載入的值，并在驗(yàn)證正確后提交來減少訪存延遲。上述這些消解或屏 蔽訪存延遲的技術(shù)都能有效的減少系統(tǒng)的平均訪存延遲，但是，除亂序執(zhí)行技術(shù) 以外，這些技術(shù)都會產(chǎn)生許多無效的訪存操作，從而加重系統(tǒng)存儲訪問的帶寬壓 力。更直接地隱藏訪存延遲的方法就是增加c a c h e 容量，這種方法的實(shí)質(zhì)就是把更 多有用的數(shù)據(jù)存放到處理器附近，從而減少c a c h e 失效，降低處理器的平均訪問延 遲，但是這種方法會顯著增加芯片的面積。 壓縮c a c h e 技術(shù)通過對c a c h e 中的數(shù)據(jù)進(jìn)行壓縮存放，能夠在不顯著增加c a c h e 面積的條件下，顯著增加c a c h e 的有效容量，從而減少c a c h e 失效，降低平均訪存 延遲。與其它緩解“存儲墻”問題的技術(shù)相比，壓縮c a c h e 技術(shù)不會增加系統(tǒng)訪存帶 寬需求，這對于目前面向吞吐率的計(jì)算機(jī)系統(tǒng)很有吸引力。 1 1 2p i n 帶寬瓶頸 目前，隨著在線事務(wù)處理、b 搜索與瀏覽、電子商務(wù)等應(yīng)用的不斷涌現(xiàn)、普 第2 頁 輯= k 嘶 一c 擴(kuò)?呶能畔 攀一 p 舌舅毫 恍m 、，。， 國防科學(xué)技術(shù)大學(xué)研究生院博士學(xué)位論文 及與發(fā)展，這些面向高吞吐率的多線程應(yīng)用越來越依賴于能同時運(yùn)行多個線程的 高性能處理器。而隨著微處理器的主頻進(jìn)入g h z 時代，單純依靠提高主頻來改善 處理器性能的方式已經(jīng)漸趨于飽和f 2 羽，處理器性能的提高將更多地依賴于更好地 開發(fā)程序中存在的各種并行性( 包括指令級和線程級并行性) 此外，隨著半導(dǎo) 體工藝水平的提高，單個芯片上的晶體管數(shù)量不斷地增加，使得將多個處理器內(nèi) 核集成到一個芯片的單芯片多處理器( c l l i pm u l t i p r o c e s s o rc m p ，簡稱多核) 技術(shù)， 以及一個處理器內(nèi)核集成多個執(zhí)行線程的多線程( m u l t i t h r e a d i n g ，m t ) 技術(shù)成為 可能。與傳統(tǒng)的超標(biāo)量超長指令字處理器僅僅開發(fā)單個程序內(nèi)細(xì)粒度的指令級并 行( i l p ) 不同，多核多線程處理器同時還開發(fā)工作負(fù)載中存在的粗粒度的線程級并 行性( n 鵬a d l e v e lp a r a l l e l i s m ，t l p ) 。t i j 的開發(fā)極大地提高了系統(tǒng)的計(jì)算吞吐率， 因此，在可預(yù)見的將來，多核多線程處理器，甚至基于多線程內(nèi)核的多核處理器 將成為未來微處理器結(jié)構(gòu)的主流。 多核多線程處理器的使用顯著增加了對片外p i n 帶寬的需求，因?yàn)? 1 j 的開 發(fā)增加了片間以及處理器存儲器之間的通信需求。但是，p i n 帶寬的增長速度也遠(yuǎn) 低于片內(nèi)傳輸管性能的增長速度。根據(jù)2 0 0 4i t r sr o 礎(chǔ)n 叩的報掣】，在未來的 1 5 年內(nèi)，每個芯片可用的p i n 的數(shù)量以每年大約1 1 的速度增長，這遠(yuǎn)遠(yuǎn)低于片 內(nèi)器件數(shù)量2 6 的年增長率。這意味著片內(nèi)處理器計(jì)算能力的增長速度遠(yuǎn)遠(yuǎn)高于 片外通信能力的增長速度。另外每個p i i l 的封裝成本以每年5 的速度降低，遠(yuǎn)低 于p i i l 數(shù)量的年增長率，這意味著芯片的封裝成本也以每年5 的增長率增加。緩 解p i n 帶寬瓶頸有賴于提高片內(nèi)c a c h e 的性能。壓縮c a c h e 技術(shù)通過增加c a c h e 的 有效容量，降低失效率來減少處理器與片外存儲器的數(shù)據(jù)交換需求。另外，如果 處理器多個存儲層次能夠以統(tǒng)一的壓縮編碼方式保存數(shù)據(jù)，則這些層次間的數(shù)據(jù) 交換就能直接以壓縮格式進(jìn)行傳送，從而顯著降低各存儲層次間數(shù)據(jù)交換帶寬的 需求，這對于緩解p i i l 帶寬瓶頸問題也有重要的意義。 1 1 3 計(jì)算能力與訪存能力的平衡設(shè)計(jì) 在設(shè)計(jì)面向多線程應(yīng)用的處理器的過程中，一個很重要的問題就是如何在一 個有限的芯片面積下，正確地權(quán)衡處理器內(nèi)核與片內(nèi)c a c h e 所占用芯片面積的比 例。是應(yīng)該增加處理器內(nèi)核的數(shù)量或者提供更多的器件資源給計(jì)算內(nèi)核，以獲得 更高的計(jì)算能力，還是應(yīng)該增加片內(nèi)c a c h e 的面積，獲得更大的片內(nèi)存儲容量，從 而得到更高的訪存能力，使任何一種能力都不會單獨(dú)成為制約系統(tǒng)性能的瓶頸。 顯然，采用壓縮c a c h e 技術(shù)能夠使這種權(quán)衡更多的向提高計(jì)算能力傾斜。因?yàn)?，?縮c a c h e 技術(shù)能夠在不顯著增加c a c h e 占用面積的情況下，顯著地增加c a c h e 的有 效容量和訪問帶寬。 第3 頁 國防科學(xué)技術(shù)大學(xué)研究生院博士學(xué)位論文 目前，支持多線程的處理器結(jié)構(gòu)主要有多核( m p ) 結(jié)構(gòu)和多線程( m d 結(jié)構(gòu)兩 種。在多核處理器中，每個處理器內(nèi)核都有自己私有的l 1 指令和數(shù)據(jù)c a c h e ，多 個處理器內(nèi)核共享片內(nèi)二級c a c h e 。如果將壓縮c a c h e 技術(shù)應(yīng)用到l 2c a c h e ，就可 以使芯片內(nèi)留出更多面積來集成更多的處理器內(nèi)核，從而提高多核處理器的計(jì)算 能力，增加它的計(jì)算吞吐率。對于多線程處理器，由于有多個線程共享l 1c a c h e ， 使l 1 數(shù)據(jù)c a c h e 中數(shù)據(jù)的局部性變差，導(dǎo)致l 1 數(shù)據(jù)c a c h e 失效率顯著增加。這造 成m t 結(jié)構(gòu)相對于m p 結(jié)構(gòu)而言，對l 2c a c h e 的訪問量急劇增加【2 3 j ，可能使l l 與 l 2c a c h e 之間的存儲帶寬成為影響處理器性能的瓶頸。因此，如果能將壓縮c a c h e 技術(shù)同時應(yīng)用于多線程處理器中的l 1 數(shù)據(jù)c a c h e 與l 2c a c h e ，且使用統(tǒng)一的壓縮 編碼，則這兩級c a c h e 就能夠以壓縮格式交換數(shù)據(jù)。這對于減少多個線程之間相互 干擾造成的c a c h e 容量資源沖突，以及l(fā) 1 - l 2c a c h e 之間的總線帶寬資源沖突，緩 解多線程處理器對l 2c a c h e 訪問壓力增大的問題將很有益處。 1 2 面向性能優(yōu)化的壓縮c a c h e 技術(shù)引入的幾個問題 1 2 1 幾個相關(guān)術(shù)語 茲鐳醐就是把輸入數(shù)據(jù)( 源流或原始數(shù)據(jù)) 轉(zhuǎn)變?yōu)榱硪环N占用空間較少 的數(shù)據(jù)( 輸出流或壓縮數(shù)據(jù)) 的過程。 壓鰳嬲數(shù)據(jù)壓縮過程需要提供一個從原始數(shù)據(jù)到壓縮數(shù)據(jù)的映射關(guān)系， 這種映射關(guān)系稱為壓縮編碼。因此數(shù)據(jù)的壓縮過程又稱為數(shù)據(jù)的編碼過程，從壓 縮數(shù)據(jù)還原到原始數(shù)據(jù)也需要利用壓縮編碼對壓縮數(shù)據(jù)進(jìn)行反向映射，故解壓縮 過程又稱為解碼過程。 壓旃密在本文中，壓縮率被定義為原始數(shù)據(jù)大小與壓縮數(shù)據(jù)大小的比值。 因此，壓縮率越大，則數(shù)據(jù)的壓縮效果就越好。 勖幽p 織在傳統(tǒng)c a c h e 中，c a c h e 是按照方進(jìn)行管理的。c a c h e 和主存頁面均 被分割成若干個大小相同的數(shù)據(jù)行，信息被以予多為單位調(diào)入c a c h e 。在壓縮c a c h e 中，一個物理c a c h e 行可能保存在傳統(tǒng)c a c h e 中原本由多個c a c h e 行保存的信息。 為避免歧義，在本文中，如無特殊說明，壓縮c a c h e 中的一個c a c h e 行仍是指數(shù)據(jù) 未被壓縮前，一個c a c h e 行的數(shù)據(jù)所代表的信息單位。 薦黼主存頁面中的數(shù)據(jù)行，它所代表的信息單位與c a c h e 行相同。 q 幽p 子贊：c a c h e 子塊是壓縮c a c h e 為壓縮數(shù)據(jù)的存放分配存儲單元的最小 基本單位。由于數(shù)據(jù)的可壓縮性能不是固定的，因此，一個c a c h e 行會隨著c a c h e 行中數(shù)據(jù)可壓縮性能的變化在壓縮c a c h e 中占用不同數(shù)量的c a c h e 子塊，也就是說 第4 頁 國防科學(xué)技術(shù)大學(xué)研究生院博士學(xué)位論文 壓縮c a c h e 為每個c a c h e 行分配的存儲單元數(shù)目必須是c a c h e 子塊大小的整數(shù)倍。 薦豬子獒：與c a c h e 子塊的含義類似，存儲子塊是主存為壓縮數(shù)據(jù)的存放分配 存儲單元的最小基本單位。一個存儲行隨其可壓縮性能的不同也將被分配數(shù)量不 等的存儲子塊。 壓嶄黻是指在一次壓縮過程中，輸入數(shù)據(jù)流從開始到結(jié)束所跨越的數(shù)據(jù) 塊的大小。在壓縮存儲結(jié)構(gòu)中，壓縮粒度一般是固定的。例如，壓縮c a c h e 通常以 一個c a c h e 行作為壓縮粒度，而有些壓縮主存系統(tǒng)則往往以一個主存頁面作為壓縮 粒度。 1 2 2 面向性能優(yōu)化的壓縮c a c h e 技術(shù)引入的幾個問題 性能一直是微處理器體系結(jié)構(gòu)設(shè)計(jì)者追求的一個主要目標(biāo)，而處理器的訪存 性能是影響處理器性能的一個重要因素。近年來，有很多研究組開始研究片內(nèi)c a c h e 與主存的存儲壓縮系統(tǒng)來緩解處理器、主存以及硬盤【2 5 l 之間巨大的性能差異所帶 來的負(fù)面影響，提高存儲系統(tǒng)的性能或者降低存儲系統(tǒng)的能量消耗瞄】。利用壓縮 c a c h e 技術(shù)提升系統(tǒng)性能的基本原理就在于：通過壓縮c a c h e 中的數(shù)據(jù)，能夠顯著 增加c a c h e 的有效容量，降低c a c h e 失效，從而可以降低處理器的平均訪存延遲， 降低存儲層次間數(shù)據(jù)交換的訪問帶寬需求。但是，將壓縮技術(shù)引入存儲層次結(jié)構(gòu) 也帶來了新的問題。這些問題主要包括存儲訪問命中延遲增加，存儲管理的元數(shù) 據(jù)開銷增大，c a c h e 替換行為復(fù)雜化等。 1 2 2 1 存儲訪問命中延遲增加 由于處理器在進(jìn)行計(jì)算時使用的是非壓縮的原始數(shù)據(jù)，因此它在訪問壓縮 c a c h e 并返回?cái)?shù)據(jù)以后，需要首先對數(shù)據(jù)進(jìn)行解壓縮。這樣，解壓縮延遲就成為c a c h e 命中延遲的一部分，從而造成c a c h e 命中延遲增加。當(dāng)壓縮c a c h e 通過增加有效容 量，減少c a c h e 失效所能帶來的好處不足以抵償壓縮c a c h e 命中延遲增加帶來的開 銷時，系統(tǒng)的實(shí)際性能會下降。為此，我們需要謹(jǐn)慎分析并評估壓縮技術(shù)的各環(huán) 節(jié)對于存儲系統(tǒng)性能的影響。 壓縮存儲系統(tǒng)中數(shù)據(jù)的解壓縮延遲開銷分為兩個部分：一部分是壓縮數(shù)據(jù)的 尋址延遲，尋址延遲開銷的大小與壓縮存儲系統(tǒng)中數(shù)據(jù)的存放布局方式緊密相關(guān)。 由于數(shù)據(jù)的可壓縮性能不是固定的，相同尺寸的不同原始數(shù)據(jù)在壓縮后將占用不 同大小的存儲空間，這必然導(dǎo)致壓縮存儲系統(tǒng)中數(shù)據(jù)存放的實(shí)際物理地址與傳統(tǒng) 存儲系統(tǒng)中數(shù)據(jù)存放的物理地址有很大的差異，從而使壓縮數(shù)據(jù)無法像傳統(tǒng)存儲 系統(tǒng)中那樣可以進(jìn)行直接地隨機(jī)尋址。因此，對比傳統(tǒng)的存儲系統(tǒng)，壓縮存儲系 統(tǒng)的數(shù)據(jù)尋址過程有額外的延遲開銷，這部分額外的尋址延遲開銷成為解壓縮延 遲的一個重要組成部分。解壓縮延遲的另外一部分開銷是對已尋址的壓縮數(shù)據(jù)進(jìn) 第5 頁 國防科學(xué)技術(shù)大學(xué)研究生院博士學(xué)位論文 行解壓縮操作的延遲，解壓縮操作延遲開銷的大小與壓縮算法的壓縮編碼復(fù)雜程 度以及壓縮粒度有關(guān)。一般來講，壓縮粒度越大，壓縮編碼算法越復(fù)雜，則解壓 縮操作的延遲就越大。 因此，為減少壓縮c a c h e 中存儲訪問的命中延遲，降低數(shù)據(jù)的解壓縮延遲開銷， 需要對壓縮數(shù)據(jù)的存放進(jìn)行合理布局，以簡化尋址；同時盡可能采用簡單的壓縮 編碼算法，合理確定壓縮粒度，以加速解碼過程。 1 2 2 2 存儲管理的元數(shù)據(jù)開銷增加 在存儲系統(tǒng)中，用于管理數(shù)據(jù)的存儲以及尋址訪問所需要付出的各種硬件存 儲單元的開銷，我們稱為元數(shù)據(jù)開銷。例如，在傳統(tǒng)c a c h e 結(jié)構(gòu)中，t a g 陣列的開 銷，就是一種元數(shù)據(jù)開銷。與傳統(tǒng)c a c h e 不同，由于壓縮c a c h e 中每個c a c h e 行的 可壓縮性能不盡相同而導(dǎo)致它們可能占用不同的物理存儲空間。因此，在壓縮c a c h e 中，為每一個c a c h e 行分配存儲空間是通過給它們分配不同數(shù)目的c a c h e 子塊來實(shí) 現(xiàn)的。壓縮c a c h e 中的每一個物理c a c h e 行可能容納了多個c a c h e 行的信息量。為 了對這些c a c h e 行進(jìn)行尋址、訪問并解壓縮，壓縮c a c h e 中需要添加額外的元數(shù)據(jù) 來對這些c a c h e 行所使用的c a c h e 子塊進(jìn)行管理，從而導(dǎo)致壓縮c a c h e 中用于數(shù)據(jù) 管理的元數(shù)據(jù)開銷增加。 存儲管理元數(shù)據(jù)開銷的增加反映了實(shí)現(xiàn)壓縮c a c h e 技術(shù)所需要付出的空間成 本。一般來說，c a c h e 子塊尺寸越大，則每個物理c a c h e 行容納的c a c h e 子塊數(shù)目 就越少，管理這些c a c h e 子塊的元數(shù)據(jù)開銷就越小；相反，若c a c h e 子塊尺寸越小， 則每個物理c a c h e 行容納的c a c h e 子塊就越多，管理這些c a c h e 子塊的元數(shù)據(jù)開銷 就越大。因此，從減少元數(shù)據(jù)開銷的角度出發(fā)，壓縮c a c h e 應(yīng)該使用較大的c a c h e 子塊。但是，當(dāng)c a c h e 子塊變大以后，會導(dǎo)致c a c h e 子塊中的內(nèi)部碎片開銷增加， 降低壓縮技術(shù)的空間效率。圖1 2 說明了當(dāng)c a c h e 子塊尺寸分別設(shè)定為c a c h e 行大 小的一半和1 4 時，c a c h e 行在不同壓縮率情況下，所分配的c a c h e 子塊數(shù)量以及 c a c h e 子塊內(nèi)部碎片所占的比例。顯然，從增加壓縮技術(shù)的空間效率來說，應(yīng)選用 較小的c a c h e 子塊。因此，在進(jìn)行壓縮c a c h e 設(shè)計(jì)時，