（电路与系统专业论文）基于变长指令编码的代码压缩技术的研究.pdf

浙江大学硕士学位论文 摘要 随着嵌入式技术的发展，嵌入式系统将更广泛地应用于人类生活的方方面 面。在内存容量不足的嵌入式系统领域，软件开发技术面临新的挑战，如何减 小代码大小、提高代码的效率，成为当前一个活跃的研究领域，因此，代码压 缩技术是未来嵌入式发展的关键技术之一。 本文先从嵌入式系统入手，分析了嵌入式系统及软件的应用特点，从而引 出代码压缩问题。在对代码压缩和数据压缩比较和分析的基础上，得出了代码 压缩的度量标准。接着分析了变长编码对代码压缩所带来的问题，包括代码可 压缩的范围的减少和指令边界未知所导致的3 个方面的问题。在此基础上我们 提出了一种基于传统字典的压缩方案，利用了指令集结构中未使用的编码空间 来对码字进行编码，并解决了由于变长指令字所导致的问题。本文对我们所设 计的码字的编码方案、用于解压的流水线结构和分支跳转表( b a t ) 等具体设 计细节都做了详尽地叙述。 为了验证设计方案的正确性，我们设计了针对c r l 6 c 流水线的周期精准 的仿真器，并应用所设计的压缩方法对m i b e n c h 基准测试程序中4 个程序和1 个常用的开源应用软件g z i p 进行了压缩实验，并获得了8 5 1 的压缩比，为了 进行对比，分别把b a t 的大小限制为5 1 2 、1 0 2 4 和2 0 4 8 个条目，并计算了在 周期内搜寻b a t 所需要的时间总开销，并对实验结果进行了分析和总结。 关键词：嵌入式系统代码压缩字典压缩 浙江大学硕士学位论文 a b s t r a c t w i t ht h ed e v e l o p m e n to fe m b e d d e dt e c h n o l o g y , e m b e d d e ds y s t e mw i l l b ea p p l i e dm o r ew i d e l yi ne v e r ya s p e c t so fh u m a nl i f e i nt h ef i e l do f e m b e d d e ds y s t e m ，s o f t w a r ed e v e l o p m e n tf a c e sn e w c h a l l e n g e sa n dh o w t os h o r t e nt h ec o d e sa n di m p r o v et h ee f f i c i e n c yh a sb e c o m e p r o b l e m so f c o n c e mi nr e c e n ty e a r s ，a sb e i n ga na c t i v er e s e a r c hf i e l d t h u s ，c o d e c o m p r e s s i o nt e c h n o l o g yw i l lb eo n eo ft h ek e yt e c h n o l o g i e sf o rf u t u r e e m b e d d e dd e v e l o p m e n t f i r s t ，w ea n a l y s i st h ef e a t u r e so fe m b e d d e ds y s t e ma n dt h ee m b e d d e d s o f t w a r ei no r d e rt or a i s et h e c o m p r e s s i o np r o b l e m b a s e do nt h e c o m p a r i s o n a n d a n a l y s i s b e t w e e nd a t a c o m p r e s s i o n a n dc o d e c o m p r e s s i o n ，w es u m m a r i z es o m ec r i t e r i o n sf o rc o d ec o m p r e s s i o n t h e n w ed i s c u s st h ec h a l l e n g e sp o s e db yt h ev a r i a b l el e n g t hm a c h i n e s a f t e r t h i s ，w ep r e s e n tac o m p r e s s i o ns c h e m eb a s e do nd i c t i o n a r yw h i c h u t i l i z e su n u s e de n c o d i n gs p a c eo fa ni n s t r u c t i o ns e ta r c h i t e c t u r et o e n c o d ec o d e w o r d s ，s oa st os o l v et h ep r o b l e md u et ov a r i a b l el e n g t h i n s t r u c t i o n s a l s ot h ep i p e l i n ea r c h i t e c t u r ef o rd e c o m p r e s s i o na n d b r a n c ha d d r e s st a b l e ( b a t ) h a v ea l s ob ep r e s e n t e da tl a r g e i no r d e rt ov e r i f yt h es c h e m e ，w eu s eac y c l ea c c u r a t es i m u l a t o rf o rt h e c r16 cp i p e l i n ea n dt e s to u rs c h e m eo n4b e n c h m a r k si nm i b e n c ha n d o n eo p e ns o u r c ea p p l i c a t i o ns o f t w a r en a m e dg z i p ，a n dg a i n8 5 4 c o m p r e s s i o nr a t i o w er e s t r i c tt h es i z eo ft h eb a tt o512 ，10 2 4a n d2 0 4 8 t oc a l c u l a t et h et i m eo v e r h e a di n c u r r e df o rs e a r c h i n gt h eb a t f i n a l l y w em a k er e s e a r c ho nt h er e s u l to fc o m p r e s s i o n e x p e r i m e n ta n d s u m m a r i z ei t k e y w o r d s ：e m b e d d e ds y s t e m c o d e c o m p r e s s i o nd i c t i o n a r y b a s e d c o m p r e s s i o n i i 浙江大学硕士学位论文 第1 章绪论 1 1 课题研究背景 1 1 1 嵌入式系统发展现状 2 0 世纪9 0 年代后期以a r m 系列3 2 位嵌入式处理器为代表的嵌入式技术， 在移动消费类产品上得到了广泛的应用。全世界大约有4 0 家半导体公司购买了 a r mc o r ei p 核。2 0 0 4 年基于f p g a 的嵌入式系统e d a 平台n e x a r 2 0 0 4 的推 出标志着用软核i p 设计客户专用s o c 已开始进入到广泛普及的阶段。f p g a 在全球开始大规模应用。 w s t s 统计出，2 0 0 5 年全球m c u 市场达到1 2 5 亿美元，而d s p 市场达 8 4 亿美元【。其中发展较快的是嵌入式d s p 市场，它已无处不在，市场规模已 接近通用d s p 的两倍，且增长速度强劲。通用d s p 的主要市场在于通信应用， 而嵌入式d s p 应用则更广泛，包括d v d 播放器、机顶盒、音视频接收设备、 m p 3 播放器、数码相机和汽车电子等。从数量上来说，全球现在每年交付使用 的嵌入式芯片约为4 0 0 亿片。随着后p c 时代的来临，消费电子成为了推动半导 体行业发展的主要动力，而在消费电子中，3 2 位嵌入式c p u 居主导地位，因为 、其在性能和功耗及价格方面具有优势嘲。 随着城市信息化和行业信息化的持续深入，嵌入式软件已广泛应用于网络 通信、消费电子、医疗电子、国防电子、工业控制、安防系统、电力系统和交 通系统等领域。中国嵌入式软件的产业规模已超过1 0 0 0 亿元人民币，而到2 0 0 8 年中国嵌入式软件市场规模将达到5 5 0 亿元。发展嵌入式系统产业成为我国信 息产业由“中国制造”向“中国创造”的突破口，成为我国信息产业增长方式 由粗放型向集约型转变，实现可持续发展的重要途径。随着嵌入式技术的发展， 嵌入式系统将更广泛地应用于人类生活的方方面面。 浙江大学硕士学位论文 1 1 2 什么是嵌入式系统 嵌入式系统是以应用为中心，以计算机技术为基础，并且软硬件可裁剪， 适用于应用系统对功能、可靠性、成本、体积、功耗有严格要求的专用计算机 系统【3 l 。它一般由嵌入式微处理器、外围硬件设备、嵌入式操作系统以及用户 的应用程序等四个部分组成，用于实现对其他设备的控制、监视或管理等功能。 嵌入式系统的核心是嵌入式微处理器，嵌入式微处理器一般就具备以下4 个特点： ( 1 ) 通常只执行特定功能，这一点与一般桌上型办公设备或数据库系统有 很大区别。 ( 2 ) 以微电脑与周边器件构成核心，其规模可在大范围内变化，如从8 0 5 1 芯片到x 8 6 芯片。 ( 3 ) 严格的时序和稳定性要求，这是因为在机器控制的大型系统中，程序 运行稍有差错则可能使得整个系统失去控制，甚至酿成灾害。 ( 4 ) 全自动操作循环。 1 1 3 嵌入式软件的特点及发展趋势 嵌入式软件与嵌入式系统是密不可分的，它是实现嵌入式系统功能的关键。 通常具有以下特点【4 】： 1 、嵌入式软件具有独特的实用性。嵌入式软件是为嵌入式系统服务的，这 就要求它与外部硬件和设备联系紧密。嵌入式系统以应用为中心，嵌入式软件 是应用系统，根据应用需求定向开发，面向产业、面向市场，需要特定的行业 经验。每种嵌入式软件都有自己独特的应用环境和实用价值。 2 、嵌入式软件应有灵活的适用性。嵌入式软件通常可以认为是一种模块化 软件，它应该能非常方便灵活的运用到各种嵌入式系统中，而不能破坏或更改 一2 一 浙江大学硕上学位论文 原有的系统特性和功能。首先它要小巧，不能占用大量资源；其次要使用灵活， 应尽量优化配置，减小对系统的整体继承性，升级更换灵活方便。 嵌入式软件产业发展迅猛，已成为软件体系的重要组成部分。嵌入式系统 产品正不断渗透各个行业，嵌入式软件作为包含在这些硬件产品中的特殊软件 形态，其产业增幅不断加大，而且在整个软件产业的比重同趋提高。 新一轮汽车、通讯、信息电器、医疗、军事等行业的巨大的智能化装备需 求拉动了嵌入式软件及系统的发展。同传统的通用计算机系统不同，嵌入式系 统面向特定应用领域，根据应用需求定制开发，并随着智能化产品的普遍需求 渗透到各行各业。随着硬件技术的不断革新，硬件平台的处理能力不断增强， 硬件成本不断下降，嵌入式软件已成为产品的数字化改造、智能化增值的关键 性、带动性技术。 1 2 代码压缩 从本质上讲，代码压缩是数据压缩的一种，但是，数据压缩与代码压缩却 有着各自的特点。科学家在研究中发现，大多数信息的表达都存在着一定的冗 余度，而数据压缩即通过去除源文件的原始数据中的冗余度来压缩数据。它是 把输入数据流( 源流或原始数据) 转变为另一种较小的数据流( 输出流或压缩 流) 的过程【5 】。数据压缩的方法很多，它们基于不同的理念，适合不同的数据 类型，产生不同的效果，但是原理都是相同的。 代码压缩通过对代码进行重编码，减小输出字符序列。常用的编码算法有： h u f f m a n 编码旧、a r i t h m e t i c 编码”、d i c t i o n a r y _ b a s e d 编码8 1 等代码压缩是 建立在输人字符序列的静态统计信息基础之上的，因而大多数代码压缩方法包 含模型和编码器解码器两个部分。 一3 一 浙江大学硕士学位论文 1 2 1 基本概念 算起来，数据压缩的起源要比计算机的起源早得多，数据压缩技术在计算 机技术的萌芽时期就已经被提上了议事日程，有关信息如何被高效存储和传递 的话题不断被军事科学家、数学家、电子学家讨论来、讨论去。终于，随着信 息论的产生和发展，数据压缩也由热门话题演变成了真正的技术。 1 2 1 1 数据的冗余性 数据之所以能够压缩是基本原始信源的数据存在着很大的冗余度。信息熵 是指一组数据所携带的信息量。它一般定义为： 一l h = 一p flog ：p ， j ，一 f = 0 其中n 为数据类数或码元个数，p i 为码元y i 发生的概率。由定义，为使 单数据量d 接近于或等于h ，应设： 尸，b ( y ，) 式( 1 2 ) 其中b ( v i ) 是分配给码元y i 的比特数，理论上应取b ( y i ) = 一l 0 9 2p i 实际上 在应用中很难估计出 p o ，p l ，p n 1 。因此一般取 b ( y o ) = b ( y - ) = = b ( y 一t ) 式( 1 3 ) 例如，英文字母编码码元长为7 比特，即 b ( y 。) = b ( y - ) = b ( y n 一) i - 7 4 一 式( 1 4 ) 一 = j 浙江大学硕上学位论文 这样所得的d 必然大于h ，由此带来的冗余我们称为信息熵冗余或编码冗 余。数据压缩就是去掉信号数据的冗余性。数据压缩常常又称为数据信源编码， 或简称为数据编码。与此对应，数据压缩的逆过程称为数据解压缩，也称为数 据信源解码，或简称为数据解码 9 1 。 1 2 1 2 统计模型与字典模型 我们明白，要压缩一条信息，首先要分析清楚信息中每个符号出现的概率。 不同的压缩程序通过不同的方法确定符号的出现概率，对符号的概率计算得越 准确，也就越容易得到好的压缩效果。在压缩程序中，用来处理输入信息，计 算符号的概率并决定输出哪个或哪些代码的模块叫做模型。 我们可以预先扫描文件中的所有字符，统计出每个字符出现的概率，这种 方法在压缩术语里叫做“静态统计模型”。但是，不同的文件中，字符有不同的 分布概率，我们要么先花上大量的时间统计我们要压缩的所有文件中的字符概 率，要么为每一个单独的文件保存一份概率表以备解压缩时需要。糟糕的是， 不但扫描文件要消耗大量时间，而且保存一份概率表也使压缩后的文件增大了 不少。所以，在实际应用中，“静态统计模型”应用的很少。 真正的压缩程序中使用的大多是一种叫“自适应模型【1 0 】”的东西。自适应模 型可以说是一台具有学习功能的自动机l 。它在信息被输入之前对信息内容一 无所知并假定每个字符的出现概率均等，随着字符不断被输入和编码，统计并 纪录已经出现过的字符的概率并将这些概率应用于对后续字符的编码。也就是 说，自适应模型在压缩开始时压缩效果并不理想，但随着压缩的进行，他会越 来越接近字符概率的准确值，并达到理想的压缩效果。自适应模型还可以适应 输入信息中字符分布的突然变化，可以适应不同的文件中的字符分布而不需要 保存概率表。 上面提到的模型可以统称为“统计模型，【1 2 】，因为他们都是基于对每个字符出 现次数的统计得到字符概率的。另一大类模型叫做“字典模型”。实际上，当我 一5 一 浙江大学硕士学位论文 们在生活中提到“工行”这个词的时候，我们都知道其意思是指“中国工商银行”， 类似的例子还有不少，但共同的前提是我们心中都有一本约定俗成的缩写字典。 字典模型也是如此，它并不直接计算字符出现的概率，而是使用一本字典，随 着输入信息的读入，模型找出输入信息在字典中匹配的最长的字符串，然后输 出该字符串在字典中的索引信息。匹配越长，压缩效果越好。事实上，字典模 型本质上仍然是基于对字符概率的计算的，只不过，字典模型使用整个字符串 的匹配代替了对某一字符重复次数的统计。可以证明，字典模型得到的压缩效 果仍然无法突破熵的极限。 当然，对通用的压缩程序来说，保存一本大字典所需的空间仍然是无法让 人忍受的，况且，任何一本预先定义的字典都无法适应不同文件中数据的变化 情况。对了，字典模型也有相应的“自适应”方案。我们可以随着信息的不断输 入，从已经输入的信息中建立合适的字典，并不断更新这本字典，以适应数据 的不断变化。 1 2 2 代码压缩的特点 一般来说，代码压缩的对象是一个应用程序，通常其数据量比较小，这一 特点对于嵌入式代码而言尤其突出，而且，程序的解压缩过程是伴随着程序的 执行过程实时进行的。由于程序的执行过程并不是顺利完成，指令流的变化要 求代码解压缩过程可以从任意点开始。并且，代码压缩通常被处理器的取指与 译码部件限制为“字节对齐方式。程序的压缩相对于普通的数据压缩有一个 很大的优势，那就是在程序语义不变的前提下可以通过重新组织指令以获得等 价的程序。对于高级语言编写的程序，可以通过编译器的辅助对程序进行优化， 生成更加适合压缩的程序代码，这样可以提高代码压缩的效率 1 2 3 压缩的度量标准 1 2 3 1 压缩因子( c o m p r e s s i o nf a c t o r ) 压缩因子【1 3 】定义为原始数据与压缩后数据的大小比值。压缩因子的值大于 一6 一 浙江大学硕士学位论文 1 表示压缩，反之则表示扩展即出现了所谓的“负压缩 。如果压缩因子为1 5 就意味着压缩后的数据大小占原始数据的6 6 7 。 一= 1 2 3 2 压缩比( c o m p r e s s i o nr a t i o ) 式( 1 5 ) 压缩率是压缩因子的倒数，即定义为压缩后数据大小与原始数 据大小的比值。 压缩因子= 淼 一7 一 式( 1 6 ) 浙江大学硕士学位论文 第2 章代码压缩技术 2 1 代码压缩的研究背景 近年来，随着网络技术的迅猛发展、嵌人式系统的渗透，代码大小问题重 新引起了人们的重视。如何减小代码大小、提高代码的效率，成为近年来学术 界和产业界关注的问题。在嵌人式系统、无线网络应用领域，由价格、重量、 能源消耗等因素决定，硬件资源尤其是内存仍然宝贵。采用减小内存容量、缩 减缓存大小等方法降低成本往往导致系统性能下降。如何设计占用内存较小的 软件因而成为一个关键问题。减小代码大小，一方面可以腾出有限的内存空间 以满足其他应用对内存的需求，降低系统的成本；另一方面，减小代码大小、 缩小内存空间意味着降低能耗，这也是嵌入式系统需要解决的一个重要问题。 事实上，已有一些压缩方法用于减小代码大小，如将j a v a 程序的c l a s s 文件打 包成j a r 格式，或使用一些通用工具软件如g z i p 和g z i p 等打包、解包程序。 白2 0 世纪8 0 年代面向对象软件开发技术兴起至今，工程化的软件开发思 想深人人心。人们注重软件产品的开发周期以及软件的复杂度、可靠性、重用 性等。在此思想指导下，各种有利于软件快速、有效开发的技术和工具不断涌 现，如现在软件开发中广泛使用构件、模板以及由第三方提供代码库等技术。 为了达到较高的代码复用性，这些构件或代码库要考虑各种可能出现的情况， 并进行编码。而实际上，使用代码库或构件的程序，需要的可能只是其中一部 分代码，代码库或构件给程序带来了大量的冗余代码，造成软件代码量过大。 因此，在内存容量不足的嵌入式系统领域，软件开发技术面临新的挑战，代码 压缩技术也变得越来越重要，成为当前一个活跃的研究领域。 总之，嵌入式系统不但需要不断提高自身计算能力以适应更高水平计算领 域的需求，为用户提供更多更好的功能，而且在成本、体积、功耗等多方面受 到制约。因而，代码压缩技术是未来嵌入式发展的关键技术之一。 一8 一 浙江大学硕士学位论文 代码压缩方法主要分为两类：扩展指令集技术与压缩技术。扩展指令集技 术多为处理器厂商所使用，由于他们推动着处理器与编译器的设计与发展，因 此扩展指令集并开发相应的处理器和编译器是处理器厂商获得更好的代码密度 的主要手段。压缩技术主要是将代码压缩看作是一种数据压缩的问题，通过数 据压缩算法减小程序代码的冗余度，从而达到压缩代码的目的。 以下就压缩技术和指令扩展技术进行介绍 2 2 压缩技术研究现状 对于嵌入式软件而言，代码尺寸是越小越好。压缩代码以适应受到成本或 空间限制的存储子系统已经成为嵌入式系统开发的一项重要事务。删、i b m 、 m i p s 、以及a r c 等嵌入式处理器厂商也注意到了对于代码压缩技术的需求， 都推出了针对自己产品的降低存储器占用的压缩技术，以下将对这几种架构中 代码压缩技术的实现进行简要地介绍【1 4 】。 易于使用的a r m 的t h u m b 技术 我们先从a r m 的代码压缩方案( t h u m b ) 讲起，因为其使用广泛、有很 好的支持，是一个典型处理器代码压缩方案，并相当简洁、有效。t h u m b 实际 上是添加到a r m 的标准r i s c 指令集之上的独立指令集。在你的代码中，你可 以通过一条模式切换指令在这两种指令集之间进行切换。t h u m b 指令集架构 ( i n s t r u c t i o ns e ta r c h i t e c t u r e ，i s a ) 是由大约36 条16 位指令组成，仅 靠这些指令是完成不了太多任务的，但t h u m b 指令集包括了基本的加法、减 法、循环移位以及跳转指令。通过使用这些较短的指令替换a r m 标准的32 位指令，可以将某些代码的规模减小大约2 0 3 0 。 但有一些问题需要引起注意，具体如下：首先，t h u m b 代码和标准a r m 代码不能混杂使用，必须显式地在两种模式间进行切换，就好像t h u m b 是一套 完全不同的指令集( 实际上也是) 。这迫使程序员将所有的16 位代码与32 位 代码分开并隔离到独立的模块中。其次，由于t h u m b 是经过简化和精简的指 一9 一 浙江大学硕士学位论文 令集架构，在t h u m b 模式中无法完成所有你希望的工作。t h u m b 模式无法进 行诸如处理中断、长跳转、原子存储器( a t o m i cm e m o r y ) 操作，或协处理器操 作等。t h u m b 有限的指令意味着仅对基本的算术和逻辑操作有用，其他的任何 工作必须使用a r m 的标准3 2 位指令集来完成。t h u m b 的限制不仅表现在指令 集上，当处于t h u m b 模式中，a r m 处理器将仅有8 个寄存器( 而不是1 6 个) ， 这些寄存器无法像标准模式下a r m 代码那样进行条件执行和移位或循环移位 操作。在标准a r m 代码和t h u m b 代码间进行参数传递并不困难，只要将参数 放到堆栈中或通过处理器的前8 个寄存器就可。从标准模式到t h u m b 模式之 间的来回切换也要消耗时间，而且还要增加代码。此外，还需要几十个前导 ( p r e a m b l e ) 以及后同步指令( p o s t a m b l e ) 来组织指针并清空c p u 的流水线。 如果在t h u m b 模式中运行的代码小于几十条指令，就不值得为之付出这样的开 销。最后，t h u m b 还对于性能有着少许的影响。通常，使用t h u m b 指令对代 码进行压缩会导致代码运行速度降低大约15 ，这主要是由于在1 6 位模式和 3 2 位模式间切换所引起的。t h u m b 指令还不如3 2 位的标准指令灵活，因此， 和3 2 位代码相比，常常需要更多的指令来完成同样的工作。从积极的一方面来 说，由于其指令长度只有3 2 位指令集的一半，t h u m b 使得缓存的使用效率更 高【1 5 】。 p o w e r p c 的c o d e p a c k 技术 值得提前说明的是i b m 的c o d e p a c k 方法是各种代码压缩技术中最复杂的 1 1 6 1 。c o d e p a c k 系统是真正对运行代码进行压缩，就好像在p o w e r p c 软件中运 行w i n z i p 。c o d e p a c k 会分析并压缩整个程序，生成的用户代码必须在运行中 解压缩并执行压缩版本。尽管很复杂，c o d e p a c k 和其它技术一样提供2o 3 0 的空间节省。c o d e p a c k 是一项很有吸引力的技术。在使用该技术时，只须 和平常一样使用标准工具编译嵌入式p o w e r p c 代码就行，c o d e p a c k 甚至对已 有的代码也能使用( 无论有没有源代码) 。在将代码写入rom 或装入磁盘之前， 运行c o d e p a c k 压缩工具对代码进行压缩。压缩工具会分析代码指令的分布并 生成一对专门针对这个程序代码的键值。当运行压缩后的代码时，拥有 一10 浙江大学硕士学位论文 c o d e p a c k 功能的处理器使用这一对键值来在运行中解开压缩的代码，就好像直 接运行压缩后的代码。解压缩会对处理器的流水线产生很小的延迟，但是其影 响被取指延迟以及其它延迟所掩盖。对于绝大多数应用，c o d e p a c k 带来的性能 影响是可以忽略的。但是，c o d e p a c k 还有一些其它的影响。由于每一个压缩的 程序都有其单独的压缩键值，c o d e p a c k 本质上既是压缩系统也是加密系统。没 有键值，无论你自己还是其它任何人都无法运行相应的程序。如果丢失了或者 未获得相应的键值，压缩后的程序只是一堆无用的乱码，这也意味着压缩后的 p o w e r p c 程序不是二进制代码兼容的。除非同时包括其解压缩键值，否则无法 轻易地和其它系统交换压缩后的程序。这会使嵌入式系统软件的现场分配稍微 有些复杂。另外，c o d ep a c k 为每个程序生成两个键值是因为指令的高1 6 位 和低1 6 位是分别进行压缩的。i b m 的工程师发现每一条p o w e r p c 指令的高半 字( 操作码就在其中) 和低半字( 其内容通常为操作数、偏移量或掩码) 的分 布频度是不一样的。对它们分别使用不同的压缩算法会使压缩效果比仅使用任 何单一算法要好，这就是c o d ep a c k 对程序所做的事。 m i p s 处理器的m i p s l 6 e 指令集 理解了t h u m b 技术后，m i p s l 6 e 就没什么新奇的了。一些m i p s 处理器中 增加了另外的1 6 位指令集，与a r m 系统非常类似。m i p s l 6 e 指令集包括了一 组1 6 位的标准m i p s 算法、逻辑以及跳转指令的简化版本。其使用和t h u m b 一样，也需要在标准模式和m i p s l 6 e 模式之间来回切换，这也将导致付出时间 和增加代码的开销。除非能在“压缩”模式上运行相当长时间，否则没有必要 进行模式切换。其代码压缩效率和a r m 差不多，对于多数程序而言，也是2 0 到3 0 。m i p s l 6 e 和t h u m b 都不能对代码进行真正的压缩，它们只是对部 分指令提供了可替换的操作码，而且所得到的压缩比是依赖于短操作码和长操 作码的总长度的比值【1 7 】 t h u m b - - 2 技术 浙江大学硕上学位论文 t h t u n b 一2 并不是t h u m b 的升级，相反，它是另起炉灶，并且可以完全代替 t h u m b 和原先的a r m 指令集。总的来说，t h u m b 2 提供的代码压缩效率要略差， 但其性能损失也较小。为了做到这一点，a r m 需要在其操作码映射中找到一个 突破口，他们在b l 指令( 跳转并连接指令，是t h u m b 和a r m 模式之间切换的指 令) 中找到了需要的突破口。在原有的指令集中，b l 指令有一些位没有使用， 这些原先未定义的位给全新的指令集提供了切换入口。t h u m b 一2 最大的特点在于 它是一套完整的指令集，程序无需切换回“标准”3 2 位a r m 模式，原先t h u m b 模式的限制再也没有了。程序现在可以处理中断、设置m m u 、管理缓存，和真 正的微处理器并没什么不同。t h u m b 2 还是需要损失一定的性能。尽管无模式切 换开销，与标准a r m 代码相比，它还是要花费多一些的指令来完成特定的任务。 对于a r m 处理器而言，这些额外的指令( 以及额外的周期) 会使速度降低大约 1 5 2 0 。未来的a r m 处理器最终将只运行t h u m b 2 代码。由于它用一套单一 的更多压缩指令的指令集有效地取代了a r m 和t h u m b 指令集，为什么不会最终 彻底取代它们呢? 但问题是a r m 的软件兼容性怎么办? 直到现在，所有的a r m 处理器( 除了i n t e l 的x s c a l e ) 都是二进制兼容。尽管支持t h u m b 2 的新型处理器 将能运行现有的a r m 和t h u m b 代码，但反之则不行。当t h u m b 2 广泛推广后， 它将创建一套单独但等价的软件库。t h u m b 一2 内核技术将为多种嵌入式应用产品 提供更高的性能、更低的功耗和更短的代码长度。t h u m b 一2 内核技术具有对现有 软件和开发工具链的完全兼容性。a r mt h u m b 一2 内核技术进一步改良了代码密度， 也带来了更优化的性能。a r m 的t h u m b - 2 新技术，将能为嵌入式应用产品提供更合 理的功耗性能，从而为其合作伙伴们在注重成本的嵌入式应用系统开发中提供了 强大的发展潜能。新的t h u m b - 2 内核技术以先进的a r mt h u m b 代码压缩技术为基 础，延续了超高的代码压缩性能并可与现有的a r m 技术方案完全兼容，同时提高 了压缩代码的性能和功耗利用率。t h u m b - 2 内核技术为嵌入式软件应用产品提供 了最佳的代码密度，能更合理有效地使用存储器。尤其对于靠近处理器内核的高 速存储器而言，这至关重要。对它的高效利用，即使只节省一小部分内存，也将 大大提高系统的性能，大幅降低功耗。 a r c 的a r c o m p a c t 技术 一1 2 一 浙江大学硕士学位论文 a r ci n t e r n a t i o n a l 公司又采用了另外的代码压缩方法。因为a r c t a n g e n 处理器有用户可定义的指令集，a r c ( 及其用户) 可以对指令集进行随心所欲的 修改。作为a r c o m p a c t ，a r c 公司决定加入一组1 6 位的指令来改进其处理器的代 码密度。而a r c o m p a c t 与t h u m b 以及m i p s l 6 e 的区别在于可以将1 6 位代码和 3 2 位代码任意混杂。由于没有模式切换，代码中任意分布的少许1 6 位指令无 须为之付出什么开销。 在任何可能的情况下，a r c 的编译器的默认配置会产生1 6 位操作( 为了强 制编译器生成3 2 位代码或与旧的处理器保持兼容，你可以关掉这个功能) 。 a r c 可以混合不同长度代码而不必付出相应的开销，是因为其指令架构要 比a r m 和m i p s 新。那些r i s c 架构的指令集包括p o w e r p c 在指令字中没有指明 指令长度的位。诸如a r c 或t e n s i l i c a 的新伪r i s c 架构，以及像x 8 6 和6 8 k 旧的架构拥有这些位。无论是出于无意还是远见，变长度指令架构因为更紧凑 的代码而具优势n 引。 m i n i - s u b r o u t i n e 技术 s t a nyl i a o 等人提出了一种在软件级别支持代码压缩与解压缩的方法。 他们找出程序代码中相同的指令序列，称之为m i n i - s u b r o u t i n e ，进而建立字 典对这样的指令序列进行索引，最后用一条类似调用子程序的指令来代替被索 引的指令序列。这样，原来的程序由未压缩部分和索引调用指令组成n 9 1 。 m i n i s u b r o u t i n e 的方法最大的优点在于他是一种软件级别上的压缩方案，在 各种流行的处理器上均可以使用，且不需要任何额外的硬件代价。 m i n i s u b r o u t i n e 的方法需要找出重复出现的一组指令序列以获得较好的压缩 率，且每组中指令序列数目愈多压缩率就越大。 一1 3 浙江大学硕士学位论文 2 3 扩展指令集技术 在一些软件说明书中你经常可以看到这样的话：“支持p 4 ，专门针对s s e 优化”。将这样的程序运行在p 4 上时，往往会得到更好的性能。那么什么是s s e 呢? s s e 的意思是数据流单指令多数据扩展指令集( s t r e a m i n gs i m d e x t e n s i o n s ) ，它是早先的s i m d 的扩展。 s i 肋 s i m d ( s i n g l ei n s t r u c t i o nm u l t i p l ed a t a ) 是指单指令多数据的运算方 式，这种技术可以使一条指令同时应用于多个数据集，这种处理方式显然在对 不同数据进行同一操作时非常有用。一个简单的例子就是，我们需要把平面空 间的圆转换成3 d 空间的圆( 由多个三角形构成) ，这其中需要大量的三角形计 算，并且其中的多个三角形运算都是一些重复性运算，使用浮点s i m d 指令显然 就可以通过名为衍生计算的算法加快整个运算完成的速度，而在原来如果仅通 过f p u 浮点单元运算的话，所有数据都需要进行逐个计算，从而大大浪费了 c p u 资源。 那么很早以前的4 8 6 或者第一代p e n t i u m 处理器又是如何工作的呢? 原理 其实非常简单。在处理器内部有很多用于存储二进制数据的寄存器。你可以计 算两个寄存器中的数据，使用第三个寄存器比较他们运算的结果。如果结果大 于第三个寄存器，那么数据就会被验证有效，随即进行后面的处理。但是这也 引出了很多问题，处理器在同一时刻仅仅能进行一个指令操作。在此之前，还 要计算出这些必要的操作指令。虽然在一个c p u 中有着数百万的a l u ( 逻辑运算 器) ，但它并不会使运算的过程加快，在同一时刻仅仅有一个a l u 是工作的， 其他的a l u 都在等待着运算的结果。此后，i n t e l 的设计师们决定要让c p u 在 同一时刻至少处理2 条以上的指令。这就是x 8 6 体系架构上的第一个s i m d 扩 展指令集删x _ 1 4 浙江大学硕十学位论文 m m x 在同一时刻不仅仅可以处理1 对信号，而是至少可以处理4 对信号。 这些运算可以是减法、乘法和其他一些逻辑运算。在进行运算的时候，每个寄 存器都是独立的。这种技术可以使c p u 在相同频率下，有惊人的性能提升。如 果要适应更为精确的科学计算的需要。在处理器中的寄存器不必做相应的修改， 只需要联合几个寄存器，就可以进行更精密的计算。但这是以牺牲性能为代价 的。在同一时刻只能计算一对高精度的数据。尽管m m x 如此优越，但在当时几 乎没有得到众多软件开发人员的支持。 1 9 9 7 年i n t e l 在p e n t i u mm m x 处理器中首次使用了m m x 多媒体指令集，不 过当时m m x 指令集仅具有整数s i m d 运算，因此在以浮点运算为主的程序时m m x 指令集是没有办法起到任何加速作用的。而第一个支持使用浮点s i m d 指令的指 令集是a m d 在k 6 - 2 处理器中开始使用的3 d n o w l 指令集。随后出现的s s e 多媒 体指令集其实同3 d n o w ! 类似。只是增加了对浮点数据的处理。随着技术的发展， a m d 又推出了增强型3 d n o w ! 指令集，i n t e l 也在推出p e n t i u m4 处理器的时候 嵌入了性能更强的s s e 2 指令集。但无论怎样以上的多媒体指令集就是为了符合 s i m d 处理而推出的，最终目的就是提高c p u 在进行重复运算的时候获得更高的 效率。 当然，要想通过这种方式提升处理器的性能，软件支持s i m d 是必不可少的。 c p u 不能在不同数据处理过程中，使用同种类型的寄存器。这就意味着，需要 由程序员告诉c p u 在何时、何种情况下使用m m x 寄存器存储和处理数据。数据 在内存中被分类，确定它们将存储在何种类型的寄存器中。软件开发人员更可 以使用s i m d 优化编译器来优化他们的程序。编译器会尽可能的使用一条s i m d 扩展指令来代替几条繁琐的常规指令。在使用编译器前，程序员必须遵循某些 s i m d 的规范来编写程序，这样才能更好的使用编译器优化程序。 m m x 扩展指令集早已成为p c 体系中一项重要的标准。m m x 的意思是多媒体 扩展指令集( m u l t im e d i ae x t e n s i o n ) 。这些扩展指令主要用于处理多媒体数 据、图象、和声音。 一1 5 浙江大学硕士学位论文 在支持m m x 的处理器中，会有8 个特殊的m m x 寄存器，每个寄存器能存储 6 4 b i t ( 8 b y t e ) 的数据。m m x 仅仅可以处理整数数据。支持1 、2 、4 、8 b y t e 的 数据包。即一个m m x 寄存器能够存储8 、4 、2 、1 个指令。 在删x 寄存器中存储的数据可以进行加法、减法、乘法运算。而其他的指 令常常出现在多媒体应用程序中。例如，不加载溢出数据结果，算术平均数计 算和逻辑操作等等。其中逻辑操作包括：与( a n d ) 、或( o r ) 、非( n o t ) 、异或( x o r ) 等等。虽然在m m x 中数据操作与指令操作并没有明确的分界线，但是许多指令 能够被更快的执行。另一方面，m m x 程序要求手工优化源代码。c p u 厂商几乎没 有提供专门的编译器。例如，各种音频格式的编码通常会为m m x 做优化。这些 编码方式与m m x 兼容的很好。通常，程序员编写支持m m x 的优化代码所花费的 时间，要占据整个软件开发的很大一部分。但这样却恰恰使程序变得非常简练。 s s e 2 的整数指令 它由完全不同的两个部分组成。这两部分是s s e 和m m x 指令集的拓展。前 者用来处理实数数据。后者负责处理整数数据。与m m x 相比，s s e 2 的寄存器要 大了一倍。s s e 2 的每个寄存器可以存储1 6 条指令。这意味着，在使用专门针 对s s e 2 的优化应用程序后，性能会有双倍的提升。并且已经经过m m x 优化的 应用程序，只要稍作改动就可以使用s s e 2 加速程序的运行。 遗憾的是a t h l o nx p 并不支持s s e 2 。早在p 4 刚刚推出的时候，很多应用 程序未曾得到s s e 2 的专门优化，再加上p 4 的种种缺陷，它的性能很难超越具 有先进的e v 6 总线的a t h l o nx p 。然而很明显，当应用程序进行了s s e 2 的优化 以后，在p 4 平台上运行要快于h t h l o nx p 平台。 我们应该承认，在s s e 2 中引入m m x 技术是非常可喜的。虽然专门为m m x 优化的程序并不多，但是这些程序优化后的表现都非常出色。我们也要提一下 i n t e l 给软件开发商提供的免费的s s e 2 优化函数库。这个函数库中提供很多典 型的编译代码，它为p 4 的普及可以说起到了至关重要的作用。 一1 6 浙江大学硕士学位论文 s s e 从p e n t i u mi i i 开始i n t e l 在自己的处理器产品中就加入了s s e 指令集。 但s s e 的全盛时期却是在p 4 发布之后。支持s s e 技术的处理器在性能上有了很 大的提高。 s s e 更倾向于真正的数据处理。这样的数据经常用于几何计算的过程中。 如3 d 图形软件，3 d 游戏，类似于3 d s t u d i o m a x 的编辑软件等等。此后3 d 加 速卡开始支持硬件级别的材质和纹理处理，这使得在运行像q u a k e 那样的3 d 游戏时，对于c p u 的整数运算性能要求并不是很高了。由于3 d 模型越来越细 腻，场面越来越宏大。人们对于处理器的浮点运算性能日趋强烈。例如在浮点 矩阵中，c p u 需要完成大量的浮点矢量乘法运算。 由于s s e 扩展指令集的出现，在标准的x 8 7 寄存器中，处理器又多了8 个 新的1 2 8 b i t 位宽的寄存器。每一个寄存器都可以存储4 个3 2 b i t 位宽的浮点数 据。 这就允许处理器可以在同一时刻处理4 条存储在寄存器中的指令。处理器 可以同时对8 个数据进行减法、乘法、除法操作。也可以对4 个数进行平方和 开方运算，取他们的精确值和近似值。对这些寄存器中的数据可以进行排序或 打乱的操作，可以将一个寄存器中的数据转移到另一个寄存器中。但数据迁移 的速度并不会加快，这就需要在使用s s e 指令集处理数据之前，最好先对要处 理器的数据进行预处理。总之程序员可以很自由的操作这些寄存器中的数据。 在p 4 中处理一条s s e 指令所花费的时间等同于处理一条普通指令。这意味 着运行优化后的应用程序可以带来近乎4 倍的性能提升。这要归功于使用了更 大位宽的寄存器。但你要注意并不是所有的程序都可以针对s s e 做出行之有效 的优化。一个优化的经典例子是当在4 维坐标系中计算4 维矩阵乘法，处理器 可以轻易获得4 倍速的性能提升。 一1 7 浙江大学硕士学位论文 首先，使用s s e 指令集