（通信与信息系统专业论文）skcore的算法实现与vmm验证.pdf

摘要 随着i c 产业的高速发展，以i p 核复用技术和超深亚微米工艺为支撑的系统 芯片( 简称s o c ) 技术，是当前嵌入式电子产品和超级大规模集成电路设计的主 流。芯片的协议变得越来越复杂，规模也越来越庞大，s o c 芯片通常都有数据众 多的输入输出端口并且还需要传递海量的数据。由美国e x a r 公司生产的 p a n t h e r 系列芯片是一款高性能的s o c 芯片，使用该s o g 芯片时，能在不影响 电脑速度的情况下，对海量数据处理的速度能达到使用市场上一般大型软件的 成千上万倍。而在这种百万甚至上千万门级的s o c 设计中，为了保证项目成功， 功能验证消耗了整个设计投入的大约7 0 ，已经成为项目的关键路径。如何解 决芯片的验证效率和验证质量已成为当今芯片设计的当务之急。 本文基于公司项目的实际工作，以p a n t h e r i i 项目中作为核心算法处理的 子系统s k c o r e 为例，首先介绍了数据压缩算法和功能验证的发展现状以及选题 的依据和意义。然后详细介绍了s k c o r e 子系统的组成和算法的基本原理，具体 阐述了s k c o r e 子系统的几个构成模块p p 、引擎流水线和多路分配器，分别介绍 了各个模块的基本构造，并举例阐述了s k c o r e 子系统引擎流水线模块中的主要 算法之1 l z s 压缩算法的基本原理，该算法也是e x a r 公司的专利算法。 然后详细介绍了s k c o r e 子系统各部分的数据结构和压缩算法引擎的实现过程， 给出了使用v e r i l o g 语言实现的各模块最终波形结果。同时，文中也介绍了 s y n o p s y s 公司最新开发的验证方法学v m m 的几个优点，包括v m m 具有的层 次化的验证平台，支持自顶向下和自底向上的方法，使用覆盖率的检测来驱动 验证的执行过程和使用断言的方法等。最后结合s k c o r e 子系统的设计并根据各 模块需要实现的功能，利用高级验证语言s y s t e mv e r i l o g 搭建了验证s k c o r e 子系 统的验证环境，包括验证顶层，场景层，命令层，功能层，信号层和测试层的 实现和具体的调试过程。以覆盖率统计为目标，对验证结果和覆盖率进行分析， 并对验证过程积累的经验和验证结果进行了总结。 关键词：s o c ，e l z s ，v m m 验证方法学，d u t ，验证平台 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 武汉理下大学硕士学位论文 第1 章绪论 当今世界，信息的发展以及人们对信息的需要都爆炸式的增长，而同时相 应的i t 产品和技术又不断地影响和改变人们的观念。从几十年前仅仅依靠电视、 收音机、老式电话等来获取和交流信息的方式，发展到如今以手机为终端的无 线通信网络和强大的计算机网络作为渠道，可以说信息技术已经渗透到世界的 每个角落。而且随着当前微电子及计算机技术的发展，信息资源将被进一步开 发和整合以满足人们对生活的更高层次的需要i l l 。 1 1 选题的依据和意义 随着个人电脑的普及和信息技术的飞速发展，越来越多的软件在电脑上被 装载和应用，这使得人们对于c p u 的处理速度和信息的传输速度的要求变得更 高。s o e 技术作为当今集成电路技术的主流和超大规模集成电路发展的趋势，相 对于传统的集成电路设计的设计流程而言，它更加强调了系统级的协调规划和 优化。 p a n t h e r i i 项目是生产一种旁路读出式的系统集成芯片，它通过p c i e 外设 与p c 机相连，使用这款系统芯片时，c p u 发出的数据请求并不是单通道地穿过 c a c h e ( 高速缓冲存储器) ，而是向c a c h e 和主存同时发出请求，并且，p a n t h e r i i 同时支持加速度存储和网络应用。与当前普通大型具有类似功能的软件相比， 该系统集成芯片在占用很少c p u 的情况下，能够达到很高的性能。p a n t h e r i i 系统芯片的结构图如图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 等模块构成。p c i e 核接收从c p u 传送过来的待处理的数据包，p c i ed m a 模块对这些数据进行读操作，同时根据b l kc m d 的指令信号需要将数据发送 到i l k 模块或p km e r 模块c a b 总线模块中。p km e r 模块中的数据到p k 中 进行网络公匙传输算法的处理，处理完成之后，通过d m a 和p c i e 核将数据传 送出去，p k 是相对独立的一个单元。i l k 模块中的数据传送到c c 0 - c c 8 中进 行出去处理，这里每个c c 都包含两个i l k 接口模块和一个s k 模块。i l k 接口 模块是一个扩展的接口模块，当使用i l k 接口扩展模块之后，如图所示，用来 武汉理工大学硕士学位论文 发送数据的i l k 0 模块可以按照需要把数据发送到i l kd m a 模块中使用外部的 f p g a 对数据信号进行数据，或者也可以把数据直接发送到芯片内部的s k 模块 进行处理。当数据处理完成之后，负责接收数据的i l k l 接口模块接收到这些数 据，通过d m a 和p c i e 核将数据传送出去。c a b 总线接收到的数据通过f l a s h 接口模块将数据传送到f l a s h 模块中进行处理，或者通过g p i o 接口模块将数据 传送到g p i o 模块中进行处理，或者传送到r n g 模块中，产生芯片实现数据处 理过程中需要的随机数，这些随机数通过l 6 4 子系统进行进一步的处理之后， 发送到s k 中被使用。 图1 - 1p a n t h e r ii 系统芯片的结构 由上图可以看出，s k c o r e 是整个p a n t h e r i i 芯片中核心的算法处理模块， 该模块接收来自i l k 0 接口模块的数据，进行处理之后又发送到i l k l 接口模块 之中去。为了实现p a n t h e r i i 芯片中要求的加速c p u 处理数据的功能，在 s k c o r e 中可以进行压缩，加密等各种复杂的算法的处理，并且随着芯片集成度 的提高，模块与模块之间的通信也越来越复杂，所以研究p a n t h e r i i 芯片s k e o r e 2 武汉理工大学硕士学位论文 整个子系统的设计实现是非常具有实际意义的。 另方面来讲，从s o c 设计步骤的顺序上来看，s o c 技术设计的流程是一个 典型的t o p - d o w n - t o p 的流程，其中系统定义和功能模块划分的合理性是作为系 统性能优化的关键。采用h d l 硬件描述语言对s k c o r e 模块作r t l 级的设计实 现完成之后，逐步整合并进行系统级的软件仿真和f p g a 硬件验证，最后将经 过这些功能验证之后的正确的设计进行a s i c 的板图综合1 3 1 。总之，功能验证在 芯片的设计过程中占有了举足轻重的作用，而对于p a n t h e r i i 芯片的核心模块 s k c o r e 进行的功能验证的研究也是十分有必要的。 1 2 国内外的研究现状 1 2 1 压缩算法的研究现状 信息论研究中有一个重要的课题即是对数据进行压缩处理，最早的时候数 据压缩在信息论研究中称为信源编码。数据压缩经过这些年不停的发展，已经 成为了独立的算法研究体系。它研究的主要目的是减少数据占用的存储空间， 研究的主要内容包括数据的转换方法、数据的传输和数据的表示等。 数据压缩技术的定义是利用信源数据所固有的相关性和冗余性，对信源发 送出的信号用以最少的码字来表示，最后达到减少容纳已给出的数据采用结合 信号空间或数据集合【4 】。 通常数据压缩技术的处理过程如图1 - 2 所示： 图1 2 数据压缩技术的处理过程 数据压缩技术主要包括三个步骤：建模表达、二次量化和嫡编码。建模表 达是根据原始数据的特点，在能够重新表达原始数据的前提下，建立一个确定 的数学模型；二次量化是根据已有的数学模型，为了更简洁地利用该模型对原 始数据建模所得到的模型参数，同时因为这些参数可能会具有较高的表示精度， 因此可以将其量化为有限的精度，从而区别对原始信号数字化时的量化；嫡编 码指的是对模型参数的量化表示或消息流重新进行码字分配，以得到尽可能紧 凑的压缩码流【5 1 。 经过数据压缩的处理之后，原始数据称为被压缩后的数据，当被压缩后的 3 武汉理工人学硕士学位论文 数据所占用的存储空间小于原始的数据所占用的存储空间的时候，数据压缩的 目的就实现了。同时，若再需要使用原始数据时，只需经解压缩处理就可以。 从上个世纪4 0 年代初期形成了信息论之后，数学家们就开始对于数据压缩 技术进行了比较系统的研究。当时对于信息论所研究的内容之一是在已知消息 中各符号出现的频率时，设法构造出一种编码技术使消息所占的空间尽可能的 少【5 1 。当时对于数据压缩所进行的研究，与现代计算机中使用的压缩技术具有极 为密切的联系。当时研究的许多算法到现在仍然具有很高的使用价值。六十年 代之后，许多实际系统中已经用到了压缩技术。 1 9 7 7 年以前，数据压缩技术一直是作为一项重要的内容在信息论算法学科 中被研究。其中，一种基于符号频率统计的霍夫曼编码法【7 】具有很好的压缩效果， 这种方法在数据压缩领域一直一来都占有较为重要的位置，并且不断的有以基 本霍夫曼编码方法为基础的霍夫曼改进算法推出。 在数据压缩算法研究的过程中，工程技术人员因为实际项目的需要进行的 工作与数学家们进行的论文研究包括建立信源和数据压缩的数据模型一直在推 动数据压缩技术的发展，同时也由于计算机技术飞速的发展的推进，对数据压 缩算法的研究也开始不仅仅局限于信息论中有关信源编码的范畴，数字图象信 号、语音信号的分析和处理等技术被大量引入到有关的研究领域。1 9 7 7 年，以 色列的两位科学家j a c 3 0 b i v 和a b r a h a ml e m p e l 发表了名为“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 的改进算法l z 7 8 t 引，因为这样两个算法， 数据压缩的研究走向了一个全新的研究阶段。 1 9 8 4 年，t e m rw e l e h 发表的论文“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 ( 高性能数据压缩技术) 描述了对l z 7 8 算法的改进和具体实现技术， l z 7 8 算法也称为l z w l 9 1 算法。目前，无损数据压缩领域中流行的数据压缩方法 多是基于字典的压缩技术。u n i x 系统上的一个实用压缩软件c o m p r e s s 和 w i n d o w s 系统下的压缩软件w i n z i p 和w i n r a r 中所使用的压缩算法都是基于字 典压缩技术的。 1 2 2 功能验证的研究现状 伴随着集成电路的发展和半导体设计规模的逐渐变大，功能验证一步步的 发展起来了。而在半导体技术发展早期，由于设计规模相对比较小，加上当时 4 武汉理工人学硕士学位论文 的技术条件下不存在专用的e d a 工具，所以对于功能验证的这个部分，主要依 靠的是在工程实践过程中的经验和某些针对具体产品的测试。 到了上个世纪七八十年代，专门的硬件描述语言、综合工具以及仿真器等 等的出现，使得半导体的设计规模急剧增大，集成电路的设计效率也有了质的 飞跃。功能验证的设计缺陷，在设计规模的不断增长的过程中，导致了重新流 片或芯片失败的比例提高了很多。 在集成电路的发展中，目前公认的是用h d l 语言作为芯片设计开发语言， 使用的比例占了7 0 ，所以最开始的验证方法是使用h d l 语言进行功能验证， 这种验证方法由于语言本身的描述能力具有很大的局限性。在t e s t b e n c h 的开发 上更高效的是v h d l 0 0 j 语言，因为v h d l 的语言比v e r i l o g h d l 具有更好的文件 接口和更强的抽象描述能力。 但是，在集成电路不断升级开发的过程中，开发人员发现，因为v e f i l o g h d l t l l 】 其独特的p l i 接口能直接和上层的c 语言通信的优点，使得v e r i l o g h d l 语言能 提供高抽象语言接口，并且在很多程度上提高了i c 验证工程师在建造t e s t b e n e h 时的抽象的描述能力，从而，功能验证方法进入了第一个繁荣阶段，并且第一 次出现了成为层次化的验证平台的思想。此时，工业界最成功的验证产品就是 c a d e n c e 公司基于p l i 开发的t e s t b u i l d e r 。这一时期在验证方法学方面最负盛名 的著作就是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 ) 。 半导体设计规模的再一次的飞跃是在上个世纪八十年代末到九十年代中 期，具体因素是随着信息行业的快速发展和i c 制造工艺的不断进步。i c 验证工 程师们感觉到在面对这种新的验证挑战时，之前建立的验证语言和验证方法学 从新的验证的角度来讲都不够高效，这一时期就正式出现了专门用来做验证的 高抽象级的验证高级语言，例如j e d a 、v e r b 、e 语言等。这些验证语言在方法 学上，都具有效率很高的带随机约束的引擎，并且都在朝层次化的方向发展。 这些优点助他们取得了巨大成功，e 语言是最典型的例子。 s o c 技术在上个世纪的九十年代末开始兴起，在系统验证中有更多的软硬 件协同验证和系统建模验证的需要。原有的具有抽象建模能力的特殊语言在芯 片的设计规模成指数发展的情况下，显得非常力不从心。此时，i c 验证工程师 们一致把目光转向了统一的高抽象描述语言。 众所周知目前最成功的编程语言当数c c + + ，并且这也是目前软件开发的主 流语言。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 级别 武汉理工大学硕+ 学位论文 t e s t b e n c h 的工作。在这个时期最好的验证方法学的著作依然来自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 本文的主要工作和论文的组织 本文基于公司项目实际工作，以p a n t h e r i i 项目中的子系统s k e o r e 为例， 研究了子系统的设计实现和基于s y s t e mv e r i l o g 语言的v m m 功能验证仿真，具 体的章节安排如下： 第一章介绍了压缩算法和功能验证的发展现状，从芯片的设计和验证两个 方面阐述了选题的依据和意义。 第二章介绍了s k c o r e 子系统的组成和基本原理，具体阐述了s k c o r e 子系 统中的几个构成模块p p 、引擎流水线和多路分配器，分别介绍了各个模块的基 本构造和实现的原理，举例阐述了s k c o r e 子系统引擎流水线模块中的主要算法 l z s 和e l z s ( 增强型l z s ) 系列压缩算法的基本原理。 第三章在第二章阐述s k c o r e 子系统基本构造和基本算法原理的基础上， 详细介绍了满足s k c o r e 子系统发送和接收数据格式的数据结构的实现和压缩算 法引擎的完整的实现过程，最后给出v e r i l o g 实现的s k c o r e 的波形结果。 第四章首先介绍了v m m 验证方法学的优点，然后根据第三章中设计实现 的s k c o r e 子系统，用s y s t e mv e r i l o g 语言搭建出v m m 验证平台，并且具体阐述 了e l z s 算法引擎的具体调试过程，最后以覆盖率统计为目标，对验证结果和覆 盖率进行分析，并对验证过程积累的经验进行了总结。 第五章总结和展望。对全文工作做一个整体的总结，并且根据这些工作， 思考设计和验证的不足，给出了未来改进的方向。 6 武汉理工人学硕十学位论文 第2 章s k c o r e 的组成和基本原理 s k c o r e 作为p a n t h e r i i 中的一个子系统，主要负责执行单元的数据转换。 s k c o r e 提供了硬件加密、压缩、认证和组合等过程。当s k c o r e 接收到指令的时 候，能将数据进行正确的转换。s k c o r e 是一个巨大的复杂的模块，它包含了很 多硬件算法的引擎，这些引擎使它支持高性能的数据转换，并且具有很好的灵 活性。s k c o r e 的结构如图2 1 所示： tp 0 图2 1s k c o r e 整体结构图， 由上图中可以看出，s k c o r e 包含以下几个子模块： p p ( p a c k e tp r e p r o c e s s ) 模块是接收i l kd m a 子系统中输出的数据流，当 检测到需要的数据包头时，通过同时输入的一些解析数据流的标示符来获取当 前数据总线中输入的信息，解析这些信息并根据x f a c e 协议输出引擎流水线中 需要的数据包。 引擎流水线包含在发动机管道中的许多引擎，如c r c 、l 6 4 、加密、压缩等。 每个数据发动机引擎根据负荷的关系和配置信息，对进来数据包作正确的转换。 多路分配器用来移除后面系统中不需要的标示符，并将数据转换后的数据 和边带信息的结果返回给i l kd m a 子系统。其中边带信息包括哈希结果的边带 信息、压缩的尺寸信息等。 p p 模块发送一个接口数据流准备信号给i l kd m a 子系统，表示s k c o r e 子 系统已经准备好接收i l kd m a 子系统的源信号，此时，i l kd m a 子系统可以 开始发送数据包到s k c o r e 子系统中，p p 模块能够解析用户描述和建立的服从 7 武汉理工人学硕士学位论文 x f a c e 协议的数据流，然后，这些数据流根据需要流进相对应的引擎管道进行 数据包处理，被处理过的数据流最后进入多路分配器模块中，多路分配器模块 删掉不需要的标示符，返回服从x f a c e 协议的输出数据流。最后多路分配器将 这些输出数据流送到i l kd m a 子系统中进行后续处理。 s k c o r e 子系统中对于数据流处理的主要特征是算法引擎和数据包的发送都 是使用流水线操作。算法引擎的流水线操作是把s k c o r e 子系统中的处理数据的 引擎根据一个特定的顺序连接起来，该顺序使数据转换进行优化，这种流水线 的结构使得算法引擎能够在一个通道内完成所有操作，提高了数据处理的速度。 数据包发送使用流水线操作能够在发送数据包阶段提高封包性能，在之前较老 的算法中，下一个封包应该等到前一个完成，但是通过应用数据包流水线操作， 数据包能够即时地在需要的算法引擎空闲的时候进入该引擎处理数据。 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 子系统中接收到源数据，然后解析这些源数据信号， 转换成服从x f a c e 协议的数据流之后，发送给接下来处理数据的流水线引擎。 同时，p p 模块也将其它的标示符信息送入到每个算法引擎的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 模块的数据流程 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 ) 的作用是识别开始发送数据的包头 8 武汉理工人学硕士学位论文 信息，然后锁定包含此信息的数据，并等待即将到来的数据。s r cp p 的逻辑结 构如图2 3 所示。 图2 一s r c p p 的逻辑结构 p 幽( m a i np r o c e s sm o d u l e ) 的作用是利用一个主要的有限状态机来解析 数据包的包头信息，把这些信息改写成一个双字，并插入用户描述标示符。使 得最后输出的数据是接下来引擎流水线中需要的数据流格式。p pm p 模块具体 处理数据过程的状态图如图2 - 4 所示。 图2 _ 4p p m p 模块的状态机 u d b u f ( u s e rd e s c r i p t o r sb u f f e r ) 的作用是缓存用户描述标识符，当数据源 到来的时候，p p m p 模块根据这些描述符插入相应的数据。 9 武汉理工大学硕士学位论文 2 2 引擎流水线 这部分是s k c o r c 的核心算法处理模块，流水线引擎首先接收来自p p 模块发 送的遵行) ( f a c e 协议格式的数据流，然后根据用户需要，分别将这些数据发送 到不同的算法引擎中进行接下来的数据处理，最后将数据传送到多路缓存器模 块之中。流水线引擎的主要结构如图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 引擎流水线的具体结构 s k c o r e 是一种高性能算法加速引擎，它支持灵活的算法和算法组合，不仅 大多数储存和网络的命令可以直接使用，还允许一些组合的指令。它主要包含 c r c 引擎、l z s 和e l z s 算法、g z i p 算法、鉴别算法、加密算法、扩充算法反 扩充算法等。在本篇论文中，我们主要研究的是如何改进的l z 系列算法即 l z s e l z s 。 2 2 1l z 系列算法的基本原理 l z 7 7 算法这是一种基于字典的压缩算法。字典编码方法是以类似查字典 的方式进行编码。这种方法的基本原理是以较长的字符串或经常出现的字母组 合构成字典中的数据项，并且用相应较短的数字或符号作为代码表示。当从源 数据流中读入的数据能与字典中的数据项相匹配，则输出其对应的代码。对基 于字典的编码算法而言，字典的建立与维护是极为重要的问题。只有把字典设 计和构造的合理适用，才能确保释放操作的正确运行和具有较高的压缩比。根 据压缩中使用的字典在构成与维护等方面的特点，可分为静态字典与动态字典。 静态字典【1 4 】在进行压缩之前就已经建立，并且在压缩过程中不会发生变化。 使用静态字典进行数据压缩时，压缩比与字典的构成及所处理的文本内容有着 1 0 武汉理工大学硕十学位论文 十分密切的关系。若要达到较高的压缩比，就必须随时根据源文件的内容调整 字典的构成。而且，为了保证释放算法能够正确执行，该字典必须与压缩后的 文件一起保存或传输，这将增加系统的存储开销，压缩效果受到很大的影响， 特别是对比较小的文件，这种影响将更加突出。 动态字则1 5 1 ( 或称为自适应字典) 不同于静态字典，在进行压缩之初并没有一 个已预先定义的字典，字典是在压缩算法的执行过程中逐步形成的，其基本处 理思想是先分析、处理输入文本，使之成为字典中的短语，然后对照字典，检 查输入数据流中的文本，如果能在字典中找到相匹配的短语，则用短语代替； 若在字典中找不到，直接输出有关内容，同时将其作为新的短语增加到字典中。 l z 7 7 算法的基本处理过程l 1 6 j 比较简单。首先从输入数据流中读取待压缩的 字符串，放入先行缓冲区，然后进行编码。把先行缓冲区中的内容与字典窗口 中的内容进行比较。如果有相匹配的部分，则按规定的格式( 匹配位置，匹配 字符串长度，该字符串后的第一个字符) 用代码表示输入字符串。经匹配、编 码后的数据流从先行缓冲区依次进入到字典窗口中，成为字典的一部分。由于 字典窗口的大小是固定的，因此原有字典中的一部分内容将从窗口的另一端滑 出，类似于用一个固定大小的窗口从输入文本上滑过。因此，l z 7 7 压缩算法又 称为滑动窗压缩【1 7 1 。随着窗口的滑动，字典的内容不断地发生变化，就好像字 典中旧的短语被抛弃，新的短语被加入到字典中，滑动窗口中总保持着最近刚 处理过的文本。 l z 7 7 算法的基本流程【埔j 如下： ( 1 ) 从当前压缩位置开始，考察未编码的数据，并试图在滑动窗口中找出 最长的匹配字符串，如果找到，则进行步骤( 2 ) ，否则进行步骤( 3 ) 。 ( 2 ) 输出三元符号组( o i f , l e n , c ) 。其中o f f 为窗口中匹配字符串相对窗1 ：3 边 界的偏移，l c n 为可匹配的长度，c 为下一个字符。然后将窗口向后滑动l e n + 1 个字符，继续步骤( 1 ) 。 ( 3 ) 输出三元符号组( 0 ，o ，c ) 。其中c 为下一个字符。然后将窗口向后滑 动1 e n + 1 个字符，继续步骤( 1 ) 。 设计三元符号组( o i f , l c n ，c ) 中每个分量的表示方法是达到较好的压缩效果关 键。对于三元组的第一个分量窗口内的偏移【1 9 1 ，通常的经验是，偏移接近窗口 尾部的情况要多于接近窗口头部的情况，这是因为字符串在与其接近的位置较 容易找到匹配串，但对于普通的窗口大小( 例如4 0 9 6 字节) 来说，偏移值基 本还是均匀分布的，我们完全可以用固定的位数来表示它。如果窗口大小为 武汉理t 大学硕士学位论文 4 0 9 6 ，用1 2 位就可以对偏移编码。如果窗口大小为2 0 4 8 ，用1 1 位就可以了。 对于第二个分量字符串长度【2 0 l ，因为在大多数时候不会太大，少数情况下 才会发生大字符串的匹配。显然可以使用一种变长的编码方式来表示该长度值。 通常比较常见的是使用g o l o m b 编码或丫编码。 对三元组的最后一个分量字符c 2 1 1 ，因为分布并无规律可循，只能老老实 实地用8 个二进制位对其编码。 在滑动窗口中查找最长的匹配串，是l z 7 7 算法中的核心问题。l z 7 7 算法 中空间和时间的消耗集中于对匹配串的查找算法。每次滑动窗口之后，都要进 行下一个匹配串的查找，如果查找算法的时间效率在o ( n 2 ) 或者更高，总的算法 时间效率就将达到o ( n 3 ) 。通常有以下几种解决方案： 1 、限制可匹配字符串的最大长度( 例如2 0 个字节) ，将窗口中每一个2 0 字节长的串抽取出来，按照大小顺序组织成二叉有序树。在这样的二叉有序树 中进行字符串的查找，可以提高查找效率效率。同时，空间消耗也不会增大很 多。不足的地方是这种方法对匹配串长度的限制影响了压缩程序对一些具有很 长的匹配串的数据的压缩效果。就平均性能而言，压缩效果还是不错的i 翻。 2 、将窗口中每个长度为3 ( 或2 或4 ) 的字符串建立索引，先在此索引中 匹配，之后对得出的每个可匹配位置进行顺序查找，直到找到最长匹配字符串 田l 。因为长度为3 的字符串可以有2 5 6 3 种情况，我们不可能用静态数组存储 该索引结构。每个索引点之后是该字符串出现的所有位置，我们可以使用单链 表来存储每一个位置。值得注意的是，对一些特殊情况比如a a a a a a 。之类的连续 字串，字符串a a a 有很多连续出现位置，但我们无需对其中的每一个位置都进 行匹配，只要对最左边和最右边的位置操作就可以了。解决的办法是在链表节 点中纪录相同字符连续出现的长度，对连续的出现位置不再建立新的节点。这 种方法可以匹配任意长度的字符串，压缩效果要好一些，但缺点是查找耗时多 于第一种方法。 3 、使用字符树来对窗口内的字符串建立索引，因为字符的取值范围是0 2 5 5 ， 字符树本身的层次不可能太多，3 4 层之下就应该换用其他的数据结构。这种方 法可以作为第二种方法的改进算法出现，可以提高查找速度，缺点是空间的消 耗较多 h i 。 1 2 武汉理工大学硕士学位论文 2 2 2 改进型算法l z s e l z s l z s 算法【2 5 j 将文本窗口中的数据进行了重新组织，采用二叉树数据结构保 存由先行缓冲区进入字典文本窗口的短语。这种算法通过对二叉搜索树中短语 的排序，寻找树中最长的匹配短语所需要的时间再也不是与窗口大小和短语长 度的乘积成正比，而是与窗口大小和短语长度乘积2 的对数值成正比，这将大 大提高l z 7 7 算法的速度。 l z s 对l z 7 7 算法的另一个改进是在输出的代码方面【2 6 1 。由l z 7 7 基本算法 可知，若能在字典中找到与输入文本串相匹配的内容时，这种算法能够取得较 好的压缩效果。但若在字典中找不到与之相匹配短语时，这种处理方法仍要给 出字符的编码。尤其在编码之初，压缩器很难为文件的前十几个或几十个字符 找到匹配的短语，却又不得不用较长的代码来表示这些单个字符，结果编码所 需的字节数远大于字符本身所占的存储空间，这样将在某种程度上抵消压缩的 效果。对此，l z s 作了一些改进，为每个输出的短语使用一位前缀，用来表示 输出的是单个字符还是用偏移量、短语长度表示的短语。这样修改后，就不再 对单个字符进行编码，从而提高了压缩率【2 7 1 。 s k c o r e 子系统支持l z s 算法，压缩引擎模块采用的数据压缩算法描述如下： 以两个字节为最小匹配长度，在当前位置往前的2 0 4 8 个字节区域内，找出从当 前点开始的最长字节串的匹配串，如果在历史区域内有多个匹配串，则按最近 的一个做( 偏移位置，字串长度) 替换，这个( 偏移位置，