（通信與信息系統(tǒng)專業(yè)論文）skcore的算法實(shí)現(xiàn)與vmm驗(yàn)證.pdf

摘要 隨著i c 產(chǎn)業(yè)的高速發(fā)展，以i p 核復(fù)用技術(shù)和超深亞微米工藝為支撐的系統(tǒng) 芯片( 簡(jiǎn)稱s o c ) 技術(shù)，是當(dāng)前嵌入式電子產(chǎn)品和超級(jí)大規(guī)模集成電路設(shè)計(jì)的主 流。芯片的協(xié)議變得越來越復(fù)雜，規(guī)模也越來越龐大，s o c 芯片通常都有數(shù)據(jù)眾 多的輸入輸出端口并且還需要傳遞海量的數(shù)據(jù)。由美國e x a r 公司生產(chǎn)的 p a n t h e r 系列芯片是一款高性能的s o c 芯片，使用該s o g 芯片時(shí)，能在不影響 電腦速度的情況下，對(duì)海量數(shù)據(jù)處理的速度能達(dá)到使用市場(chǎng)上一般大型軟件的 成千上萬倍。而在這種百萬甚至上千萬門級(jí)的s o c 設(shè)計(jì)中，為了保證項(xiàng)目成功， 功能驗(yàn)證消耗了整個(gè)設(shè)計(jì)投入的大約7 0 ，已經(jīng)成為項(xiàng)目的關(guān)鍵路徑。如何解 決芯片的驗(yàn)證效率和驗(yàn)證質(zhì)量已成為當(dāng)今芯片設(shè)計(jì)的當(dāng)務(wù)之急。 本文基于公司項(xiàng)目的實(shí)際工作，以p a n t h e r i i 項(xiàng)目中作為核心算法處理的 子系統(tǒng)s k c o r e 為例，首先介紹了數(shù)據(jù)壓縮算法和功能驗(yàn)證的發(fā)展現(xiàn)狀以及選題 的依據(jù)和意義。然后詳細(xì)介紹了s k c o r e 子系統(tǒng)的組成和算法的基本原理，具體 闡述了s k c o r e 子系統(tǒng)的幾個(gè)構(gòu)成模塊p p 、引擎流水線和多路分配器，分別介紹 了各個(gè)模塊的基本構(gòu)造，并舉例闡述了s k c o r e 子系統(tǒng)引擎流水線模塊中的主要 算法之1 l z s 壓縮算法的基本原理，該算法也是e x a r 公司的專利算法。 然后詳細(xì)介紹了s k c o r e 子系統(tǒng)各部分的數(shù)據(jù)結(jié)構(gòu)和壓縮算法引擎的實(shí)現(xiàn)過程， 給出了使用v e r i l o g 語言實(shí)現(xiàn)的各模塊最終波形結(jié)果。同時(shí)，文中也介紹了 s y n o p s y s 公司最新開發(fā)的驗(yàn)證方法學(xué)v m m 的幾個(gè)優(yōu)點(diǎn)，包括v m m 具有的層 次化的驗(yàn)證平臺(tái)，支持自頂向下和自底向上的方法，使用覆蓋率的檢測(cè)來驅(qū)動(dòng) 驗(yàn)證的執(zhí)行過程和使用斷言的方法等。最后結(jié)合s k c o r e 子系統(tǒng)的設(shè)計(jì)并根據(jù)各 模塊需要實(shí)現(xiàn)的功能，利用高級(jí)驗(yàn)證語言s y s t e mv e r i l o g 搭建了驗(yàn)證s k c o r e 子系 統(tǒng)的驗(yàn)證環(huán)境，包括驗(yàn)證頂層，場(chǎng)景層，命令層，功能層，信號(hào)層和測(cè)試層的 實(shí)現(xiàn)和具體的調(diào)試過程。以覆蓋率統(tǒng)計(jì)為目標(biāo)，對(duì)驗(yàn)證結(jié)果和覆蓋率進(jìn)行分析， 并對(duì)驗(yàn)證過程積累的經(jīng)驗(yàn)和驗(yàn)證結(jié)果進(jìn)行了總結(jié)。 關(guān)鍵詞：s o c ，e l z s ，v m m 驗(yàn)證方法學(xué)，d u t ，驗(yàn)證平臺(tái) a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to fi ci n d u s t r y , s y s t e m o n - c h i pt e c h n o l o g yw h i c hi s m u l t i p l e x i n go fi pc o r e sa n du l t r a - d e e ps u b - m i c r o nt e c h n o l o g yf o rt h es u p p o r t ，i st h e c u r r e n tm a i n s t r e a mo fe m b e d d e de l e c t r o n i cp r o d u c td e s i g na n ds u p e rl s i t h ec h i p a g r e e m e n th a sb e c o m ei n c r e a s i n g l yc o m p l e x ，a n dt h es c a l ei sg e t t i n gh u g e ，s o cc h i p u s u a l l yn e e d st oh a v eal a r g en u m b e ro fd a t ai n p u ta n do u t p u tp o r t s ，a n dt r a n s m i s s i o n o fv a s ta m o u n t so fd a t a p a n t h e rs e r i e ss o cc h i pp r o d u c e db yt h eu n i t e ds t a t e se x a r c o r p o r a t i o ni sah i l g hp e r f o r m a n c e ，i nt h ec a s ed o e sn o ta f f e c tt h ec o m p u t e rs p e e d ，f o r m a s s i v ed a t ap r o c e s s i n gs p e e do fl a r g es o f t w a r eo nt h em a r k e tt h o u s a n d so ft i m e s i n s u c ham i l l i o no re v e n10m i l l i o ng a t ea s i cd e s i g n , i no r d e rt oe n s u r et h es u c c e s so f t h ep r o j e c t , f u n c t i o n a lv e r i f i c a t i o nc o n s u m e sa b o u t7 0 o ft h ee n t i r ed e s i g ni n p 咄 t h i sh a sb e c o m et h ep r o j e c t sc r i t i c a lp a t h h o wt os o l v et h ev e r i f i c a t i o np r o c e s sa n d v a l i d a t i o no fq u a l i t yo ft h ec h i ph a sb e c o m ea l lu r g e n tt a s ko ft o d a y sc h i pd e s i g n b a s e do nt h ea c t u a lp r o j e c t sw o r ko f c o m p a n y , i nt h ec a s eo ft h es u b s y s t e mo f c o r ea l g o r i t h mp r o c e s s i n g ，w h i c hu s e di np a n t h e r i ip r o j e c t f i r s td e s c r i b e dt h e b a s i sa n ds i g n i f i c a n c eo ft h ef u n c t i o n a lv e r i f i c a t i o no ft h ed e v e l o p m e n ta sw e l la s t o p i c s ，t h e nd e s c r i b e di nd e t a i lt h ec o m p o s i t i o na n dt h eb a s i cp r i n c i p l e so ft h e s k c o r es u b s y s t e m ，s p e c i f i c a l l ya d d r e s s e ds e v e r a ls k c o r et h eb u i l d i n gb l o c k so fap p e n g i n ea s s e m b l yl i n ea n dd e m u l t i p l e x e r , i n t r o d u c e st h e b a s i cs t r u c t u r eo fe a c hm o d u l e a n dt h er e a l i z a t i o no ft h ep r i n c i p l e ，i l l u s t r a t e ss k c o r ea l g o r i t h mi sa l s oe x a r c o m p a n y sp a t e n t e da l g o r i t h m s - 一l z s e r i e s i m p r o v e dt h e b a s i cp r i n c i p l eo ft h e c o m p r e s s i o na l g o r i t h m t h i sp a p e rd e t a i l st h ev a r i o u sp a r t so ft h ed a t as t r u c t u r ea n d r t li m p l e m e n t a t i o np r o c e s s ，a n db a s e do ns p e c i f i cp r i n c i p l e sa n dm e t h o d so fe a c h m o d u l e ，l e a r nt h ev m mv e r i f i c a t i o nm e t h o db a s e do nt h e l a t e s td e v e l o p m e n to f s y n o p s y s ，i n e ，f i r s ta n a l y z e st h es h o r t c o m i n g so ft h ec o n v e n t i o n a li cv e r i f i c a t i o n , t h e ni ns i m p l et e r m st h ea d v a n t a g e so f t h es y s t e mv e r i l o ga sav e r i f i c a t i o nl a n g u s a g e ， s p e c i f i c a l l ya d d r e s s e dt h ev m m v e r i f i c a t i o nm e t h o d o l o g y d e s c r i b e sh o wt ou s et h e a d v a n c e dv e r i f i c a t i o nl a n g u a g e s ，b a s i cv e r i f i c a t i o nl i b r a r ya n dm a t u r ev e r i f i c a t i o n m o d e l ，r a p i d l ye s t a b l i s h m e n to fr a n d o m l yg e n e r a t e dt e s tv e c t o r s ，v e c t o rs c e n ec a nb e u m o d u l a t e d , a n dc o l l e c t i o nc o v e r a g ev e r i f i c a t i o ns y s t e m f i n a l l y 、 ，i t l lt h ed e s i g no f s k c o r es u b s y s t e m ，a n di na c c o r d a n c e 謝t ht h en e e dt oi m p l e m e n tt h ef u n c t i o n a l i t yo f e a c hm o d u l e ，s t r u c t u r e sv a l i d a t i o ne n v i r o n m e n tf o rv e r i f i e ds k c o r es u b s y s t e m u s et h eh i g h - l e v e lv e r i f i c a t i o nl a n g u a g es y s t e mv e r i l o g ，i i l c l u d i n gt h ei m p l e m e n t a t i o n a n dd e b u g g i n gp r o c e s so fv e r i f i c a t i o nt o p l a y e r , s c e n e l a y e r , c o m m a n dl a y e r , f u n c t i o n a ll a y e r , t h es i g n a ll a y e ra n dt e s tl a y e r f i n a l l y , f o rt h et a r g e to f c o v e r a g e s t a t i s t i c s ，a n a l y z e dt ot h ev e r i f i e d r c s u l i sa n dc o v e r a g e ，a n dg o tas u m m a r yo ft h e e x p e r i e n c ea c c u m u l a t e db yt h ev a l i d a t i o np r o c e s sa n dt h ev e r i f i e dr e s u l t s k e y w o r d s ：s o c ，e l z s , v m m v a l i d a t i o nm e t h o d o l o g y ，d u t ，v a l i d a t i o np l a t f o r m i i i 武漢理下大學(xué)碩士學(xué)位論文 第1 章緒論 當(dāng)今世界，信息的發(fā)展以及人們對(duì)信息的需要都爆炸式的增長(zhǎng)，而同時(shí)相 應(yīng)的i t 產(chǎn)品和技術(shù)又不斷地影響和改變?nèi)藗兊挠^念。從幾十年前僅僅依靠電視、 收音機(jī)、老式電話等來獲取和交流信息的方式，發(fā)展到如今以手機(jī)為終端的無 線通信網(wǎng)絡(luò)和強(qiáng)大的計(jì)算機(jī)網(wǎng)絡(luò)作為渠道，可以說信息技術(shù)已經(jīng)滲透到世界的 每個(gè)角落。而且隨著當(dāng)前微電子及計(jì)算機(jī)技術(shù)的發(fā)展，信息資源將被進(jìn)一步開 發(fā)和整合以滿足人們對(duì)生活的更高層次的需要i l l 。 1 1 選題的依據(jù)和意義 隨著個(gè)人電腦的普及和信息技術(shù)的飛速發(fā)展，越來越多的軟件在電腦上被 裝載和應(yīng)用，這使得人們對(duì)于c p u 的處理速度和信息的傳輸速度的要求變得更 高。s o e 技術(shù)作為當(dāng)今集成電路技術(shù)的主流和超大規(guī)模集成電路發(fā)展的趨勢(shì)，相 對(duì)于傳統(tǒng)的集成電路設(shè)計(jì)的設(shè)計(jì)流程而言，它更加強(qiáng)調(diào)了系統(tǒng)級(jí)的協(xié)調(diào)規(guī)劃和 優(yōu)化。 p a n t h e r i i 項(xiàng)目是生產(chǎn)一種旁路讀出式的系統(tǒng)集成芯片，它通過p c i e 外設(shè) 與p c 機(jī)相連，使用這款系統(tǒng)芯片時(shí)，c p u 發(fā)出的數(shù)據(jù)請(qǐng)求并不是單通道地穿過 c a c h e ( 高速緩沖存儲(chǔ)器) ，而是向c a c h e 和主存同時(shí)發(fā)出請(qǐng)求，并且，p a n t h e r i i 同時(shí)支持加速度存儲(chǔ)和網(wǎng)絡(luò)應(yīng)用。與當(dāng)前普通大型具有類似功能的軟件相比， 該系統(tǒng)集成芯片在占用很少c p u 的情況下，能夠達(dá)到很高的性能。p a n t h e r i i 系統(tǒng)芯片的結(jié)構(gòu)圖如圖1 - 1 所示： 由圖中可以看出，p a n t h e r i i 主要由p c i e 核、p c d m a 、i l k 、p k 、s k ， l 6 4 等模塊構(gòu)成。p c i e 核接收從c p u 傳送過來的待處理的數(shù)據(jù)包，p c i ed m a 模塊對(duì)這些數(shù)據(jù)進(jìn)行讀操作，同時(shí)根據(jù)b l kc m d 的指令信號(hào)需要將數(shù)據(jù)發(fā)送 到i l k 模塊或p km e r 模塊c a b 總線模塊中。p km e r 模塊中的數(shù)據(jù)到p k 中 進(jìn)行網(wǎng)絡(luò)公匙傳輸算法的處理，處理完成之后，通過d m a 和p c i e 核將數(shù)據(jù)傳 送出去，p k 是相對(duì)獨(dú)立的一個(gè)單元。i l k 模塊中的數(shù)據(jù)傳送到c c 0 - c c 8 中進(jìn) 行出去處理，這里每個(gè)c c 都包含兩個(gè)i l k 接口模塊和一個(gè)s k 模塊。i l k 接口 模塊是一個(gè)擴(kuò)展的接口模塊，當(dāng)使用i l k 接口擴(kuò)展模塊之后，如圖所示，用來 武漢理工大學(xué)碩士學(xué)位論文 發(fā)送數(shù)據(jù)的i l k 0 模塊可以按照需要把數(shù)據(jù)發(fā)送到i l kd m a 模塊中使用外部的 f p g a 對(duì)數(shù)據(jù)信號(hào)進(jìn)行數(shù)據(jù)，或者也可以把數(shù)據(jù)直接發(fā)送到芯片內(nèi)部的s k 模塊 進(jìn)行處理。當(dāng)數(shù)據(jù)處理完成之后，負(fù)責(zé)接收數(shù)據(jù)的i l k l 接口模塊接收到這些數(shù) 據(jù)，通過d m a 和p c i e 核將數(shù)據(jù)傳送出去。c a b 總線接收到的數(shù)據(jù)通過f l a s h 接口模塊將數(shù)據(jù)傳送到f l a s h 模塊中進(jìn)行處理，或者通過g p i o 接口模塊將數(shù)據(jù) 傳送到g p i o 模塊中進(jìn)行處理，或者傳送到r n g 模塊中，產(chǎn)生芯片實(shí)現(xiàn)數(shù)據(jù)處 理過程中需要的隨機(jī)數(shù)，這些隨機(jī)數(shù)通過l 6 4 子系統(tǒng)進(jìn)行進(jìn)一步的處理之后， 發(fā)送到s k 中被使用。 圖1 - 1p a n t h e r ii 系統(tǒng)芯片的結(jié)構(gòu) 由上圖可以看出，s k c o r e 是整個(gè)p a n t h e r i i 芯片中核心的算法處理模塊， 該模塊接收來自i l k 0 接口模塊的數(shù)據(jù)，進(jìn)行處理之后又發(fā)送到i l k l 接口模塊 之中去。為了實(shí)現(xiàn)p a n t h e r i i 芯片中要求的加速c p u 處理數(shù)據(jù)的功能，在 s k c o r e 中可以進(jìn)行壓縮，加密等各種復(fù)雜的算法的處理，并且隨著芯片集成度 的提高，模塊與模塊之間的通信也越來越復(fù)雜，所以研究p a n t h e r i i 芯片s k e o r e 2 武漢理工大學(xué)碩士學(xué)位論文 整個(gè)子系統(tǒng)的設(shè)計(jì)實(shí)現(xiàn)是非常具有實(shí)際意義的。 另方面來講，從s o c 設(shè)計(jì)步驟的順序上來看，s o c 技術(shù)設(shè)計(jì)的流程是一個(gè) 典型的t o p - d o w n - t o p 的流程，其中系統(tǒng)定義和功能模塊劃分的合理性是作為系 統(tǒng)性能優(yōu)化的關(guān)鍵。采用h d l 硬件描述語言對(duì)s k c o r e 模塊作r t l 級(jí)的設(shè)計(jì)實(shí) 現(xiàn)完成之后，逐步整合并進(jìn)行系統(tǒng)級(jí)的軟件仿真和f p g a 硬件驗(yàn)證，最后將經(jīng) 過這些功能驗(yàn)證之后的正確的設(shè)計(jì)進(jìn)行a s i c 的板圖綜合1 3 1 。總之，功能驗(yàn)證在 芯片的設(shè)計(jì)過程中占有了舉足輕重的作用，而對(duì)于p a n t h e r i i 芯片的核心模塊 s k c o r e 進(jìn)行的功能驗(yàn)證的研究也是十分有必要的。 1 2 國內(nèi)外的研究現(xiàn)狀 1 2 1 壓縮算法的研究現(xiàn)狀 信息論研究中有一個(gè)重要的課題即是對(duì)數(shù)據(jù)進(jìn)行壓縮處理，最早的時(shí)候數(shù) 據(jù)壓縮在信息論研究中稱為信源編碼。數(shù)據(jù)壓縮經(jīng)過這些年不停的發(fā)展，已經(jīng) 成為了獨(dú)立的算法研究體系。它研究的主要目的是減少數(shù)據(jù)占用的存儲(chǔ)空間， 研究的主要內(nèi)容包括數(shù)據(jù)的轉(zhuǎn)換方法、數(shù)據(jù)的傳輸和數(shù)據(jù)的表示等。 數(shù)據(jù)壓縮技術(shù)的定義是利用信源數(shù)據(jù)所固有的相關(guān)性和冗余性，對(duì)信源發(fā) 送出的信號(hào)用以最少的碼字來表示，最后達(dá)到減少容納已給出的數(shù)據(jù)采用結(jié)合 信號(hào)空間或數(shù)據(jù)集合【4 】。 通常數(shù)據(jù)壓縮技術(shù)的處理過程如圖1 - 2 所示： 圖1 2 數(shù)據(jù)壓縮技術(shù)的處理過程 數(shù)據(jù)壓縮技術(shù)主要包括三個(gè)步驟：建模表達(dá)、二次量化和嫡編碼。建模表 達(dá)是根據(jù)原始數(shù)據(jù)的特點(diǎn)，在能夠重新表達(dá)原始數(shù)據(jù)的前提下，建立一個(gè)確定 的數(shù)學(xué)模型；二次量化是根據(jù)已有的數(shù)學(xué)模型，為了更簡(jiǎn)潔地利用該模型對(duì)原 始數(shù)據(jù)建模所得到的模型參數(shù)，同時(shí)因?yàn)檫@些參數(shù)可能會(huì)具有較高的表示精度， 因此可以將其量化為有限的精度，從而區(qū)別對(duì)原始信號(hào)數(shù)字化時(shí)的量化；嫡編 碼指的是對(duì)模型參數(shù)的量化表示或消息流重新進(jìn)行碼字分配，以得到盡可能緊 湊的壓縮碼流【5 1 。 經(jīng)過數(shù)據(jù)壓縮的處理之后，原始數(shù)據(jù)稱為被壓縮后的數(shù)據(jù)，當(dāng)被壓縮后的 3 武漢理工人學(xué)碩士學(xué)位論文 數(shù)據(jù)所占用的存儲(chǔ)空間小于原始的數(shù)據(jù)所占用的存儲(chǔ)空間的時(shí)候，數(shù)據(jù)壓縮的 目的就實(shí)現(xiàn)了。同時(shí)，若再需要使用原始數(shù)據(jù)時(shí)，只需經(jīng)解壓縮處理就可以。 從上個(gè)世紀(jì)4 0 年代初期形成了信息論之后，數(shù)學(xué)家們就開始對(duì)于數(shù)據(jù)壓縮 技術(shù)進(jìn)行了比較系統(tǒng)的研究。當(dāng)時(shí)對(duì)于信息論所研究的內(nèi)容之一是在已知消息 中各符號(hào)出現(xiàn)的頻率時(shí)，設(shè)法構(gòu)造出一種編碼技術(shù)使消息所占的空間盡可能的 少【5 1 。當(dāng)時(shí)對(duì)于數(shù)據(jù)壓縮所進(jìn)行的研究，與現(xiàn)代計(jì)算機(jī)中使用的壓縮技術(shù)具有極 為密切的聯(lián)系。當(dāng)時(shí)研究的許多算法到現(xiàn)在仍然具有很高的使用價(jià)值。六十年 代之后，許多實(shí)際系統(tǒng)中已經(jīng)用到了壓縮技術(shù)。 1 9 7 7 年以前，數(shù)據(jù)壓縮技術(shù)一直是作為一項(xiàng)重要的內(nèi)容在信息論算法學(xué)科 中被研究。其中，一種基于符號(hào)頻率統(tǒng)計(jì)的霍夫曼編碼法【7 】具有很好的壓縮效果， 這種方法在數(shù)據(jù)壓縮領(lǐng)域一直一來都占有較為重要的位置，并且不斷的有以基 本霍夫曼編碼方法為基礎(chǔ)的霍夫曼改進(jìn)算法推出。 在數(shù)據(jù)壓縮算法研究的過程中，工程技術(shù)人員因?yàn)閷?shí)際項(xiàng)目的需要進(jìn)行的 工作與數(shù)學(xué)家們進(jìn)行的論文研究包括建立信源和數(shù)據(jù)壓縮的數(shù)據(jù)模型一直在推 動(dòng)數(shù)據(jù)壓縮技術(shù)的發(fā)展，同時(shí)也由于計(jì)算機(jī)技術(shù)飛速的發(fā)展的推進(jìn)，對(duì)數(shù)據(jù)壓 縮算法的研究也開始不僅僅局限于信息論中有關(guān)信源編碼的范疇，數(shù)字圖象信 號(hào)、語音信號(hào)的分析和處理等技術(shù)被大量引入到有關(guān)的研究領(lǐng)域。1 9 7 7 年，以 色列的兩位科學(xué)家j a c 3 0 b i v 和a b r a h a ml e m p e l 發(fā)表了名為“a u n i v e r s a la l g o d t h m f o rs e q u e n t i a ld a t ac o m p r e s s i o n ，提出了一種不同以往的基于字典的壓縮方法 l z 7 7 t 7 1 ，幾年之后，他們又提出了l z 7 7 的改進(jìn)算法l z 7 8 t 引，因?yàn)檫@樣兩個(gè)算法， 數(shù)據(jù)壓縮的研究走向了一個(gè)全新的研究階段。 1 9 8 4 年，t e m rw e l e h 發(fā)表的論文“at e c h n i q u ef o rh i g hp e r f o r m a n c ed a t a c o m p r e s s i o n ( 高性能數(shù)據(jù)壓縮技術(shù)) 描述了對(duì)l z 7 8 算法的改進(jìn)和具體實(shí)現(xiàn)技術(shù)， l z 7 8 算法也稱為l z w l 9 1 算法。目前，無損數(shù)據(jù)壓縮領(lǐng)域中流行的數(shù)據(jù)壓縮方法 多是基于字典的壓縮技術(shù)。u n i x 系統(tǒng)上的一個(gè)實(shí)用壓縮軟件c o m p r e s s 和 w i n d o w s 系統(tǒng)下的壓縮軟件w i n z i p 和w i n r a r 中所使用的壓縮算法都是基于字 典壓縮技術(shù)的。 1 2 2 功能驗(yàn)證的研究現(xiàn)狀 伴隨著集成電路的發(fā)展和半導(dǎo)體設(shè)計(jì)規(guī)模的逐漸變大，功能驗(yàn)證一步步的 發(fā)展起來了。而在半導(dǎo)體技術(shù)發(fā)展早期，由于設(shè)計(jì)規(guī)模相對(duì)比較小，加上當(dāng)時(shí) 4 武漢理工人學(xué)碩士學(xué)位論文 的技術(shù)條件下不存在專用的e d a 工具，所以對(duì)于功能驗(yàn)證的這個(gè)部分，主要依 靠的是在工程實(shí)踐過程中的經(jīng)驗(yàn)和某些針對(duì)具體產(chǎn)品的測(cè)試。 到了上個(gè)世紀(jì)七八十年代，專門的硬件描述語言、綜合工具以及仿真器等 等的出現(xiàn)，使得半導(dǎo)體的設(shè)計(jì)規(guī)模急劇增大，集成電路的設(shè)計(jì)效率也有了質(zhì)的 飛躍。功能驗(yàn)證的設(shè)計(jì)缺陷，在設(shè)計(jì)規(guī)模的不斷增長(zhǎng)的過程中，導(dǎo)致了重新流 片或芯片失敗的比例提高了很多。 在集成電路的發(fā)展中，目前公認(rèn)的是用h d l 語言作為芯片設(shè)計(jì)開發(fā)語言， 使用的比例占了7 0 ，所以最開始的驗(yàn)證方法是使用h d l 語言進(jìn)行功能驗(yàn)證， 這種驗(yàn)證方法由于語言本身的描述能力具有很大的局限性。在t e s t b e n c h 的開發(fā) 上更高效的是v h d l 0 0 j 語言，因?yàn)関 h d l 的語言比v e r i l o g h d l 具有更好的文件 接口和更強(qiáng)的抽象描述能力。 但是，在集成電路不斷升級(jí)開發(fā)的過程中，開發(fā)人員發(fā)現(xiàn)，因?yàn)関 e f i l o g h d l t l l 】 其獨(dú)特的p l i 接口能直接和上層的c 語言通信的優(yōu)點(diǎn)，使得v e r i l o g h d l 語言能 提供高抽象語言接口，并且在很多程度上提高了i c 驗(yàn)證工程師在建造t e s t b e n e h 時(shí)的抽象的描述能力，從而，功能驗(yàn)證方法進(jìn)入了第一個(gè)繁榮階段，并且第一 次出現(xiàn)了成為層次化的驗(yàn)證平臺(tái)的思想。此時(shí)，工業(yè)界最成功的驗(yàn)證產(chǎn)品就是 c a d e n c e 公司基于p l i 開發(fā)的t e s t b u i l d e r 。這一時(shí)期在驗(yàn)證方法學(xué)方面最負(fù)盛名 的著作就是j a n i c kb e r g e r o n 的( w r i t i n gt e s t b e n c h e s - f u n c t i o n a lv e r i f i c a t i o i lo f m o d e l s ) 。 半導(dǎo)體設(shè)計(jì)規(guī)模的再一次的飛躍是在上個(gè)世紀(jì)八十年代末到九十年代中 期，具體因素是隨著信息行業(yè)的快速發(fā)展和i c 制造工藝的不斷進(jìn)步。i c 驗(yàn)證工 程師們感覺到在面對(duì)這種新的驗(yàn)證挑戰(zhàn)時(shí)，之前建立的驗(yàn)證語言和驗(yàn)證方法學(xué) 從新的驗(yàn)證的角度來講都不夠高效，這一時(shí)期就正式出現(xiàn)了專門用來做驗(yàn)證的 高抽象級(jí)的驗(yàn)證高級(jí)語言，例如j e d a 、v e r b 、e 語言等。這些驗(yàn)證語言在方法 學(xué)上，都具有效率很高的帶隨機(jī)約束的引擎，并且都在朝層次化的方向發(fā)展。 這些優(yōu)點(diǎn)助他們?nèi)〉昧司薮蟪晒?，e 語言是最典型的例子。 s o c 技術(shù)在上個(gè)世紀(jì)的九十年代末開始興起，在系統(tǒng)驗(yàn)證中有更多的軟硬 件協(xié)同驗(yàn)證和系統(tǒng)建模驗(yàn)證的需要。原有的具有抽象建模能力的特殊語言在芯 片的設(shè)計(jì)規(guī)模成指數(shù)發(fā)展的情況下，顯得非常力不從心。此時(shí)，i c 驗(yàn)證工程師 們一致把目光轉(zhuǎn)向了統(tǒng)一的高抽象描述語言。 眾所周知目前最成功的編程語言當(dāng)數(shù)c c + + ，并且這也是目前軟件開發(fā)的主 流語言。s y s t e m v e r i l o g 1 2 】具有的a s s e r t i o n 的特性使它更適合搭建一些r t l 級(jí)別 武漢理工大學(xué)碩+ 學(xué)位論文 t e s t b e n c h 的工作。在這個(gè)時(shí)期最好的驗(yàn)證方法學(xué)的著作依然來自j a n i c k b e r g e r o n ，即他和a r m 公司合作完成的( v e r i f i c a t i o nm e t h o d o l o g ym a n u a lf o r s y s t e mv e d l o g ) ) 。 1 3 本文的主要工作和論文的組織 本文基于公司項(xiàng)目實(shí)際工作，以p a n t h e r i i 項(xiàng)目中的子系統(tǒng)s k e o r e 為例， 研究了子系統(tǒng)的設(shè)計(jì)實(shí)現(xiàn)和基于s y s t e mv e r i l o g 語言的v m m 功能驗(yàn)證仿真，具 體的章節(jié)安排如下： 第一章介紹了壓縮算法和功能驗(yàn)證的發(fā)展現(xiàn)狀，從芯片的設(shè)計(jì)和驗(yàn)證兩個(gè) 方面闡述了選題的依據(jù)和意義。 第二章介紹了s k c o r e 子系統(tǒng)的組成和基本原理，具體闡述了s k c o r e 子系 統(tǒng)中的幾個(gè)構(gòu)成模塊p p 、引擎流水線和多路分配器，分別介紹了各個(gè)模塊的基 本構(gòu)造和實(shí)現(xiàn)的原理，舉例闡述了s k c o r e 子系統(tǒng)引擎流水線模塊中的主要算法 l z s 和e l z s ( 增強(qiáng)型l z s ) 系列壓縮算法的基本原理。 第三章在第二章闡述s k c o r e 子系統(tǒng)基本構(gòu)造和基本算法原理的基礎(chǔ)上， 詳細(xì)介紹了滿足s k c o r e 子系統(tǒng)發(fā)送和接收數(shù)據(jù)格式的數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)和壓縮算 法引擎的完整的實(shí)現(xiàn)過程，最后給出v e r i l o g 實(shí)現(xiàn)的s k c o r e 的波形結(jié)果。 第四章首先介紹了v m m 驗(yàn)證方法學(xué)的優(yōu)點(diǎn)，然后根據(jù)第三章中設(shè)計(jì)實(shí)現(xiàn) 的s k c o r e 子系統(tǒng)，用s y s t e mv e r i l o g 語言搭建出v m m 驗(yàn)證平臺(tái)，并且具體闡述 了e l z s 算法引擎的具體調(diào)試過程，最后以覆蓋率統(tǒng)計(jì)為目標(biāo)，對(duì)驗(yàn)證結(jié)果和覆 蓋率進(jìn)行分析，并對(duì)驗(yàn)證過程積累的經(jīng)驗(yàn)進(jìn)行了總結(jié)。 第五章總結(jié)和展望。對(duì)全文工作做一個(gè)整體的總結(jié)，并且根據(jù)這些工作， 思考設(shè)計(jì)和驗(yàn)證的不足，給出了未來改進(jìn)的方向。 6 武漢理工人學(xué)碩十學(xué)位論文 第2 章s k c o r e 的組成和基本原理 s k c o r e 作為p a n t h e r i i 中的一個(gè)子系統(tǒng)，主要負(fù)責(zé)執(zhí)行單元的數(shù)據(jù)轉(zhuǎn)換。 s k c o r e 提供了硬件加密、壓縮、認(rèn)證和組合等過程。當(dāng)s k c o r e 接收到指令的時(shí) 候，能將數(shù)據(jù)進(jìn)行正確的轉(zhuǎn)換。s k c o r e 是一個(gè)巨大的復(fù)雜的模塊，它包含了很 多硬件算法的引擎，這些引擎使它支持高性能的數(shù)據(jù)轉(zhuǎn)換，并且具有很好的靈 活性。s k c o r e 的結(jié)構(gòu)如圖2 1 所示： tp 0 圖2 1s k c o r e 整體結(jié)構(gòu)圖， 由上圖中可以看出，s k c o r e 包含以下幾個(gè)子模塊： p p ( p a c k e tp r e p r o c e s s ) 模塊是接收i l kd m a 子系統(tǒng)中輸出的數(shù)據(jù)流，當(dāng) 檢測(cè)到需要的數(shù)據(jù)包頭時(shí)，通過同時(shí)輸入的一些解析數(shù)據(jù)流的標(biāo)示符來獲取當(dāng) 前數(shù)據(jù)總線中輸入的信息，解析這些信息并根據(jù)x f a c e 協(xié)議輸出引擎流水線中 需要的數(shù)據(jù)包。 引擎流水線包含在發(fā)動(dòng)機(jī)管道中的許多引擎，如c r c 、l 6 4 、加密、壓縮等。 每個(gè)數(shù)據(jù)發(fā)動(dòng)機(jī)引擎根據(jù)負(fù)荷的關(guān)系和配置信息，對(duì)進(jìn)來數(shù)據(jù)包作正確的轉(zhuǎn)換。 多路分配器用來移除后面系統(tǒng)中不需要的標(biāo)示符，并將數(shù)據(jù)轉(zhuǎn)換后的數(shù)據(jù) 和邊帶信息的結(jié)果返回給i l kd m a 子系統(tǒng)。其中邊帶信息包括哈希結(jié)果的邊帶 信息、壓縮的尺寸信息等。 p p 模塊發(fā)送一個(gè)接口數(shù)據(jù)流準(zhǔn)備信號(hào)給i l kd m a 子系統(tǒng)，表示s k c o r e 子 系統(tǒng)已經(jīng)準(zhǔn)備好接收i l kd m a 子系統(tǒng)的源信號(hào)，此時(shí)，i l kd m a 子系統(tǒng)可以 開始發(fā)送數(shù)據(jù)包到s k c o r e 子系統(tǒng)中，p p 模塊能夠解析用戶描述和建立的服從 7 武漢理工人學(xué)碩士學(xué)位論文 x f a c e 協(xié)議的數(shù)據(jù)流，然后，這些數(shù)據(jù)流根據(jù)需要流進(jìn)相對(duì)應(yīng)的引擎管道進(jìn)行 數(shù)據(jù)包處理，被處理過的數(shù)據(jù)流最后進(jìn)入多路分配器模塊中，多路分配器模塊 刪掉不需要的標(biāo)示符，返回服從x f a c e 協(xié)議的輸出數(shù)據(jù)流。最后多路分配器將 這些輸出數(shù)據(jù)流送到i l kd m a 子系統(tǒng)中進(jìn)行后續(xù)處理。 s k c o r e 子系統(tǒng)中對(duì)于數(shù)據(jù)流處理的主要特征是算法引擎和數(shù)據(jù)包的發(fā)送都 是使用流水線操作。算法引擎的流水線操作是把s k c o r e 子系統(tǒng)中的處理數(shù)據(jù)的 引擎根據(jù)一個(gè)特定的順序連接起來，該順序使數(shù)據(jù)轉(zhuǎn)換進(jìn)行優(yōu)化，這種流水線 的結(jié)構(gòu)使得算法引擎能夠在一個(gè)通道內(nèi)完成所有操作，提高了數(shù)據(jù)處理的速度。 數(shù)據(jù)包發(fā)送使用流水線操作能夠在發(fā)送數(shù)據(jù)包階段提高封包性能，在之前較老 的算法中，下一個(gè)封包應(yīng)該等到前一個(gè)完成，但是通過應(yīng)用數(shù)據(jù)包流水線操作， 數(shù)據(jù)包能夠即時(shí)地在需要的算法引擎空閑的時(shí)候進(jìn)入該引擎處理數(shù)據(jù)。 2 1p p ( p a c k e t p r e - - p r o c e s s ) p p 模塊從i l kd m a 子系統(tǒng)中接收到源數(shù)據(jù)，然后解析這些源數(shù)據(jù)信號(hào)， 轉(zhuǎn)換成服從x f a c e 協(xié)議的數(shù)據(jù)流之后，發(fā)送給接下來處理數(shù)據(jù)的流水線引擎。 同時(shí)，p p 模塊也將其它的標(biāo)示符信息送入到每個(gè)算法引擎的f i f o 中。具體過 程如圖2 - 2 所示。 s r c 翼 i l k d m a p o d a t a 31 ：0 】 e o pb c a a t 1 ：0 1 叉f a c e 圖2 2p p 模塊的數(shù)據(jù)流程 s r c p p ( s o u r c ep op r e p r o c e s sm o d u l e ) 的作用是識(shí)別開始發(fā)送數(shù)據(jù)的包頭 8 武漢理工人學(xué)碩士學(xué)位論文 信息，然后鎖定包含此信息的數(shù)據(jù)，并等待即將到來的數(shù)據(jù)。s r cp p 的邏輯結(jié) 構(gòu)如圖2 3 所示。 圖2 一s r c p p 的邏輯結(jié)構(gòu) p 幽( m a i np r o c e s sm o d u l e ) 的作用是利用一個(gè)主要的有限狀態(tài)機(jī)來解析 數(shù)據(jù)包的包頭信息，把這些信息改寫成一個(gè)雙字，并插入用戶描述標(biāo)示符。使 得最后輸出的數(shù)據(jù)是接下來引擎流水線中需要的數(shù)據(jù)流格式。p pm p 模塊具體 處理數(shù)據(jù)過程的狀態(tài)圖如圖2 - 4 所示。 圖2 _ 4p p m p 模塊的狀態(tài)機(jī) u d b u f ( u s e rd e s c r i p t o r sb u f f e r ) 的作用是緩存用戶描述標(biāo)識(shí)符，當(dāng)數(shù)據(jù)源 到來的時(shí)候，p p m p 模塊根據(jù)這些描述符插入相應(yīng)的數(shù)據(jù)。 9 武漢理工大學(xué)碩士學(xué)位論文 2 2 引擎流水線 這部分是s k c o r c 的核心算法處理模塊，流水線引擎首先接收來自p p 模塊發(fā) 送的遵行) ( f a c e 協(xié)議格式的數(shù)據(jù)流，然后根據(jù)用戶需要，分別將這些數(shù)據(jù)發(fā)送 到不同的算法引擎中進(jìn)行接下來的數(shù)據(jù)處理，最后將數(shù)據(jù)傳送到多路緩存器模 塊之中。流水線引擎的主要結(jié)構(gòu)如圖2 。5 所示。 舅南，_ l l ! i 赫l ! i ! i 二_ ! ! 釜衲曩量疊曲! 苧! 晌 ：= 。一= ： = = ! = = = = _ ： c = = _ 一，= = 。? ： 薯? = 一- _ 一一i - _ 一? j _ i ；- ：二= = i 一 ， ， ，t， f a # ”1r j 、西 4a ，- ： 孫， 。fj 。y i ，i 。 “ 。，w 二r 。，十，7 。+ + tp ，。；，n 。一- 。f ：i j _ or f 二r ? c 二? of - j 。 ； ? 壹苧! 蔓? 氅 i j _ ；一 ，矗7 。辦x v - i 一了 ：_ ”+。羔一 二- 蟹峰袖， “”。 曼二：一。 簍” 2 2 2 。二! i ：曩t ， 。 。ii ：。東7 ， ， m 。 、， 圖2 5 引擎流水線的具體結(jié)構(gòu) s k c o r e 是一種高性能算法加速引擎，它支持靈活的算法和算法組合，不僅 大多數(shù)儲(chǔ)存和網(wǎng)絡(luò)的命令可以直接使用，還允許一些組合的指令。它主要包含 c r c 引擎、l z s 和e l z s 算法、g z i p 算法、鑒別算法、加密算法、擴(kuò)充算法反 擴(kuò)充算法等。在本篇論文中，我們主要研究的是如何改進(jìn)的l z 系列算法即 l z s e l z s 。 2 2 1l z 系列算法的基本原理 l z 7 7 算法這是一種基于字典的壓縮算法。字典編碼方法是以類似查字典 的方式進(jìn)行編碼。這種方法的基本原理是以較長(zhǎng)的字符串或經(jīng)常出現(xiàn)的字母組 合構(gòu)成字典中的數(shù)據(jù)項(xiàng)，并且用相應(yīng)較短的數(shù)字或符號(hào)作為代碼表示。當(dāng)從源 數(shù)據(jù)流中讀入的數(shù)據(jù)能與字典中的數(shù)據(jù)項(xiàng)相匹配，則輸出其對(duì)應(yīng)的代碼。對(duì)基 于字典的編碼算法而言，字典的建立與維護(hù)是極為重要的問題。只有把字典設(shè) 計(jì)和構(gòu)造的合理適用，才能確保釋放操作的正確運(yùn)行和具有較高的壓縮比。根 據(jù)壓縮中使用的字典在構(gòu)成與維護(hù)等方面的特點(diǎn)，可分為靜態(tài)字典與動(dòng)態(tài)字典。 靜態(tài)字典【1 4 】在進(jìn)行壓縮之前就已經(jīng)建立，并且在壓縮過程中不會(huì)發(fā)生變化。 使用靜態(tài)字典進(jìn)行數(shù)據(jù)壓縮時(shí)，壓縮比與字典的構(gòu)成及所處理的文本內(nèi)容有著 1 0 武漢理工大學(xué)碩十學(xué)位論文 十分密切的關(guān)系。若要達(dá)到較高的壓縮比，就必須隨時(shí)根據(jù)源文件的內(nèi)容調(diào)整 字典的構(gòu)成。而且，為了保證釋放算法能夠正確執(zhí)行，該字典必須與壓縮后的 文件一起保存或傳輸，這將增加系統(tǒng)的存儲(chǔ)開銷，壓縮效果受到很大的影響， 特別是對(duì)比較小的文件，這種影響將更加突出。 動(dòng)態(tài)字則1 5 1 ( 或稱為自適應(yīng)字典) 不同于靜態(tài)字典，在進(jìn)行壓縮之初并沒有一 個(gè)已預(yù)先定義的字典，字典是在壓縮算法的執(zhí)行過程中逐步形成的，其基本處 理思想是先分析、處理輸入文本，使之成為字典中的短語，然后對(duì)照字典，檢 查輸入數(shù)據(jù)流中的文本，如果能在字典中找到相匹配的短語，則用短語代替； 若在字典中找不到，直接輸出有關(guān)內(nèi)容，同時(shí)將其作為新的短語增加到字典中。 l z 7 7 算法的基本處理過程l 1 6 j 比較簡(jiǎn)單。首先從輸入數(shù)據(jù)流中讀取待壓縮的 字符串，放入先行緩沖區(qū)，然后進(jìn)行編碼。把先行緩沖區(qū)中的內(nèi)容與字典窗口 中的內(nèi)容進(jìn)行比較。如果有相匹配的部分，則按規(guī)定的格式( 匹配位置，匹配 字符串長(zhǎng)度，該字符串后的第一個(gè)字符) 用代碼表示輸入字符串。經(jīng)匹配、編 碼后的數(shù)據(jù)流從先行緩沖區(qū)依次進(jìn)入到字典窗口中，成為字典的一部分。由于 字典窗口的大小是固定的，因此原有字典中的一部分內(nèi)容將從窗口的另一端滑 出，類似于用一個(gè)固定大小的窗口從輸入文本上滑過。因此，l z 7 7 壓縮算法又 稱為滑動(dòng)窗壓縮【1 7 1 。隨著窗口的滑動(dòng)，字典的內(nèi)容不斷地發(fā)生變化，就好像字 典中舊的短語被拋棄，新的短語被加入到字典中，滑動(dòng)窗口中總保持著最近剛 處理過的文本。 l z 7 7 算法的基本流程【埔j 如下： ( 1 ) 從當(dāng)前壓縮位置開始，考察未編碼的數(shù)據(jù)，并試圖在滑動(dòng)窗口中找出 最長(zhǎng)的匹配字符串，如果找到，則進(jìn)行步驟( 2 ) ，否則進(jìn)行步驟( 3 ) 。 ( 2 ) 輸出三元符號(hào)組( o i f , l e n , c ) 。其中o f f 為窗口中匹配字符串相對(duì)窗1 ：3 邊 界的偏移，l c n 為可匹配的長(zhǎng)度，c 為下一個(gè)字符。然后將窗口向后滑動(dòng)l e n + 1 個(gè)字符，繼續(xù)步驟( 1 ) 。 ( 3 ) 輸出三元符號(hào)組( 0 ，o ，c ) 。其中c 為下一個(gè)字符。然后將窗口向后滑 動(dòng)1 e n + 1 個(gè)字符，繼續(xù)步驟( 1 ) 。 設(shè)計(jì)三元符號(hào)組( o i f , l c n ，c ) 中每個(gè)分量的表示方法是達(dá)到較好的壓縮效果關(guān) 鍵。對(duì)于三元組的第一個(gè)分量窗口內(nèi)的偏移【1 9 1 ，通常的經(jīng)驗(yàn)是，偏移接近窗口 尾部的情況要多于接近窗口頭部的情況，這是因?yàn)樽址谂c其接近的位置較 容易找到匹配串，但對(duì)于普通的窗口大小( 例如4 0 9 6 字節(jié)) 來說，偏移值基 本還是均勻分布的，我們完全可以用固定的位數(shù)來表示它。如果窗口大小為 武漢理t 大學(xué)碩士學(xué)位論文 4 0 9 6 ，用1 2 位就可以對(duì)偏移編碼。如果窗口大小為2 0 4 8 ，用1 1 位就可以了。 對(duì)于第二個(gè)分量字符串長(zhǎng)度【2 0 l ，因?yàn)樵诖蠖鄶?shù)時(shí)候不會(huì)太大，少數(shù)情況下 才會(huì)發(fā)生大字符串的匹配。顯然可以使用一種變長(zhǎng)的編碼方式來表示該長(zhǎng)度值。 通常比較常見的是使用g o l o m b 編碼或丫編碼。 對(duì)三元組的最后一個(gè)分量字符c 2 1 1 ，因?yàn)榉植疾o規(guī)律可循，只能老老實(shí) 實(shí)地用8 個(gè)二進(jìn)制位對(duì)其編碼。 在滑動(dòng)窗口中查找最長(zhǎng)的匹配串，是l z 7 7 算法中的核心問題。l z 7 7 算法 中空間和時(shí)間的消耗集中于對(duì)匹配串的查找算法。每次滑動(dòng)窗口之后，都要進(jìn) 行下一個(gè)匹配串的查找，如果查找算法的時(shí)間效率在o ( n 2 ) 或者更高，總的算法 時(shí)間效率就將達(dá)到o ( n 3 ) 。通常有以下幾種解決方案： 1 、限制可匹配字符串的最大長(zhǎng)度( 例如2 0 個(gè)字節(jié)) ，將窗口中每一個(gè)2 0 字節(jié)長(zhǎng)的串抽取出來，按照大小順序組織成二叉有序樹。在這樣的二叉有序樹 中進(jìn)行字符串的查找，可以提高查找效率效率。同時(shí)，空間消耗也不會(huì)增大很 多。不足的地方是這種方法對(duì)匹配串長(zhǎng)度的限制影響了壓縮程序?qū)σ恍┚哂泻?長(zhǎng)的匹配串的數(shù)據(jù)的壓縮效果。就平均性能而言，壓縮效果還是不錯(cuò)的i 翻。 2 、將窗口中每個(gè)長(zhǎng)度為3 ( 或2 或4 ) 的字符串建立索引，先在此索引中 匹配，之后對(duì)得出的每個(gè)可匹配位置進(jìn)行順序查找，直到找到最長(zhǎng)匹配字符串 田l 。因?yàn)殚L(zhǎng)度為3 的字符串可以有2 5 6 3 種情況，我們不可能用靜態(tài)數(shù)組存儲(chǔ) 該索引結(jié)構(gòu)。每個(gè)索引點(diǎn)之后是該字符串出現(xiàn)的所有位置，我們可以使用單鏈 表來存儲(chǔ)每一個(gè)位置。值得注意的是，對(duì)一些特殊情況比如a a a a a a 。之類的連續(xù) 字串，字符串a(chǎn) a a 有很多連續(xù)出現(xiàn)位置，但我們無需對(duì)其中的每一個(gè)位置都進(jìn) 行匹配，只要對(duì)最左邊和最右邊的位置操作就可以了。解決的辦法是在鏈表節(jié) 點(diǎn)中紀(jì)錄相同字符連續(xù)出現(xiàn)的長(zhǎng)度，對(duì)連續(xù)的出現(xiàn)位置不再建立新的節(jié)點(diǎn)。這 種方法可以匹配任意長(zhǎng)度的字符串，壓縮效果要好一些，但缺點(diǎn)是查找耗時(shí)多 于第一種方法。 3 、使用字符樹來對(duì)窗口內(nèi)的字符串建立索引，因?yàn)樽址娜≈捣秶? 2 5 5 ， 字符樹本身的層次不可能太多，3 4 層之下就應(yīng)該換用其他的數(shù)據(jù)結(jié)構(gòu)。這種方 法可以作為第二種方法的改進(jìn)算法出現(xiàn)，可以提高查找速度，缺點(diǎn)是空間的消 耗較多 h i 。 1 2 武漢理工大學(xué)碩士學(xué)位論文 2 2 2 改進(jìn)型算法l z s e l z s l z s 算法【2 5 j 將文本窗口中的數(shù)據(jù)進(jìn)行了重新組織，采用二叉樹數(shù)據(jù)結(jié)構(gòu)保 存由先行緩沖區(qū)進(jìn)入字典文本窗口的短語。這種算法通過對(duì)二叉搜索樹中短語 的排序，尋找樹中最長(zhǎng)的匹配短語所需要的時(shí)間再也不是與窗口大小和短語長(zhǎng) 度的乘積成正比，而是與窗口大小和短語長(zhǎng)度乘積2 的對(duì)數(shù)值成正比，這將大 大提高l z 7 7 算法的速度。 l z s 對(duì)l z 7 7 算法的另一個(gè)改進(jìn)是在輸出的代碼方面【2 6 1 。由l z 7 7 基本算法 可知，若能在字典中找到與輸入文本串相匹配的內(nèi)容時(shí)，這種算法能夠取得較 好的壓縮效果。但若在字典中找不到與之相匹配短語時(shí)，這種處理方法仍要給 出字符的編碼。尤其在編碼之初，壓縮器很難為文件的前十幾個(gè)或幾十個(gè)字符 找到匹配的短語，卻又不得不用較長(zhǎng)的代碼來表示這些單個(gè)字符，結(jié)果編碼所 需的字節(jié)數(shù)遠(yuǎn)大于字符本身所占的存儲(chǔ)空間，這樣將在某種程度上抵消壓縮的 效果。對(duì)此，l z s 作了一些改進(jìn)，為每個(gè)輸出的短語使用一位前綴，用來表示 輸出的是單個(gè)字符還是用偏移量、短語長(zhǎng)度表示的短語。這樣修改后，就不再 對(duì)單個(gè)字符進(jìn)行編碼，從而提高了壓縮率【2 7 1 。 s k c o r e 子系統(tǒng)支持l z s 算法，壓縮引擎模塊采用的數(shù)據(jù)壓縮算法描述如下： 以兩個(gè)字節(jié)為最小匹配長(zhǎng)度，在當(dāng)前位置往前的2 0 4 8 個(gè)字節(jié)區(qū)域內(nèi)，找出從當(dāng) 前點(diǎn)開始的最長(zhǎng)字節(jié)串的匹配串，如果在歷史區(qū)域內(nèi)有多個(gè)匹配串，則按最近 的一個(gè)做( 偏移位置，字串長(zhǎng)度) 替換，這個(gè)( 偏移位置，