微代码全局压缩的最新动向及其初步评价

继 Fisher提出微代码全局压缩的路径调度法后, 1983年以来又出现了 Tree,ITSC,SRDAG及GDDG等四种新的全局压缩方法。本文介绍上述各方法的基本原理,并在采用实际微代码进行试验的基础上进行初步评价。     

微代码全局压缩的实现及初步评价

Fisher 1979年提出的路经调度法被认为是微代码全局压缩最有希望的方法。本文叙述此法的实现及用几种复杂微代码序列进行实验的情况,对局部压缩、手工压缩及全局压缩的结果进行分析比较,并提出对全局压缩的改进意见。     

采用专家系统技术的微代码全局压缩实现研究

将顺序的微操作序列压缩成微指令这一微代码压缩问题本质上是在一定限制条件下的搜索问题,本文介绍一个用于微代码压缩的专家系统,其目的在于充分利用实际微代码中各种启发因素,以提高压缩效益。该系统以PROLOG语言在PCS68000上实现并采用了修改的路径调度法。文中对所得结果与传统方法作了分析与比较并探讨了今后的发展。     

顺序扫描实现程序并行化

提出扩展选择调度,统一处理循环和非循环代码,对它们不加区分但却分别产生软件流水和全局压缩的效果;程序并行化不需要分层简化,只要顺序扫描一遍即可.该方法打破了有环调度和无环调度的界限,是一种基于一般图而不是路径或有向无环图的全局调度算法.它从一个全新的角度来看待多重循环,通过恰当地计算可用集合和活变量集合,实现了多重循环的直接调度,对任意控制流程序都是适用的.     

面向星载计算机的双重索引数据压缩方法

随着星载计算机系统功能的日益复杂,程序规模也在快速扩大.在存储资源极其受限的背景下,需要稳定、有效的代码压缩功能来保障星载软件的正常存储与运行.混合压缩算法是目前无损数据压缩的主流算法,具有压缩率高、代码规模和计算资源需求大的特点.然而,在航天星载计算机等嵌入式系统中,由于其运行环境特殊,需要较高的可靠性和抗干扰能力,无法实现混合压缩算法应有的效果.同时,单一压缩模型压缩率较低.针对以上问题,在LZ77算法代码体积和内存消耗优势的基础上提出了改进方法:为压缩过程设计一种新的匹配记录表以存储高价值数据索引来辅助压缩,实现了原算法局部性优势与高价值数据全局分布的互补,更大程度上减少了数据冗余;结合动态填充、变长编码等进一步优化编码结构,降低存储需求;最终,设计并实现了一种更加适合航天嵌入式环境的无损数据压缩算法(LZRC).实验结果表明:(1)新算法在比LZ77算法代码体积仅多出3.5 KB的条件下,对软件代码的平均压缩比提高了17%;(2)新算法的运行内存需求仅为混合压缩算法的12%,代码体积也减少了84%,更加适合星载计算机系统.     

基于大字典的LZW压缩算法的降熵改进

在分析压缩算法LZW的基础上,针对LZW算法在字典规模增大时出现的压缩后数据平均信息熵快速增大的不足,提出一种改进的压缩算法。利用数据中普遍存在的空间相关性,在保存大字典的同时缩小每次压缩实际使用的字典范围,以此减小压缩后数据的信息熵。给出改进算法与LZW压缩算法的性能对比,实验结果表明改进算法在减小压缩后数据的信息熵方面取得了2%~16.9%的优化。     

微码自动压缩模型与算法

本文给出一种基于新的微操作和微指令描述的微码压缩算法，算法独立于目标微结构，将局部压缩与全局压缩结合在一起，降低了微码压缩的复杂波，可生成高效的微码。     

基于集群机并行绘制的三角形条带压缩

提出一个适用于集群机并行绘制的三角形条带数据压缩框架--视点连贯性的分片条带压缩(VCPSC),有效地克服了传统几何数据压缩算法存在的问题.VCPSC包括3步核心算法:基于空间和法向连贯性分片方法;基于同心圆全局路径控制的三角形单条带化;ETSC三角形条带压缩算法.通过把每个压缩的三角形条带映射为一个支持随机存取的虚拟三角形,VCPSC实现了几何模型压缩域的基于视点的归属判断和分片随机存取.实验结果表明:VCPSC有效地改善了集群机绘制性能.     

一种改进的小波变换图像压缩算法

针对图像的数据量的相对庞大、传输速度慢的问题,需要一种很好的压缩算法,既能以较少的失真率对图像进行压缩,又能使压缩的过程相对迅速,以满足当今网络应用的需求。通过研究两种已有的小波变换图像压缩算法的算法思想及算法流程,找出它们的特性及存在的不足,并通过对小波变换后的图像的不同频域子带的小波树进行分类,采用适合的压缩算法对各部分进行压缩,使图像的整体压缩效果得到提高,同时也降低了压缩过程的复杂度。实验结果表明,改进的小波变换图像压缩算法在压缩效果和压缩效率上都优于两种已有的小波变换图像压缩算法。这个分类压缩的方法能够有效地提高图像的压缩效果,也降低了算法的复杂度。     

代码变形的增强LZMA算法

为了使LZMA压缩算法满足代码变形所要求的文件可执行性与保密性,并进一步提升压缩效果,提出了在加密、分块并行、字典搜索策略、输出元组及加壳等五个方面的增强方法,设计了一个基于增强LZMA算法的代码变形系统模型。根据增强LZMA算法的保密性、压缩效果以及对文件可执行性影响的实验结果表明,该算法有很好的应用效果。     

具有时间约束的微代码压缩问题

微程序机器中的时间约束关系将使微代码压缩问题复杂化并影响压缩结果,这是一个重要的实际问题,但迄今尚无很好的解决办法.本文在对具有时间约束的微代码压缩问题进行系统分析的基础上,提出一个通用的启发式CAS方法,初步实验表明CAS方法的调度成功率及压缩结果均优于现有其它方法.     

基于多实体的矢量数据压缩改进算法

矢量数据压缩在地形环境仿真、制图综合、GIS等研究中具有重要作用,对增加移动设备的存储能力和提高矢量数据的网络传输效率来说是一项很重要的工作。根据动态规划算法理论、Douglas-Peucker算法和矢量数据的特点,提出了基于动态规划算法的矢量数据压缩的模型和改进方法,通过一条参考路径构造一条带形成最小误差搜索范围,同时条带宽度可自适应调整。并将单一实体的优化压缩算法扩展为基于多实体的压缩算法,解决了图层压缩的全局优化问题。实验结果表明,该方法具有较高的效率,能够得到较小的压缩误差。     

微代码压缩问题

微代码压缩是固件工程的重要内容之一,近十年来发展很快。本文对微代码压缩的理论描述,各种局部及全局压缩方法进行了综述,并提出了对今后发展方向的看法。     

一种优化的多Agent相关任务并行调度算法

讨论了在多Agent系统中多组作业的并行调度问题，提出了一个描述多组作业推进速度的指标——调度效率和一种优化的多Agent相关任务并行调度算法——多Agent相关任务均衡 压缩调度算法(MADTBCSA)。以调度效率作为调度的标准，通过追求多组作业的均衡推进，来达到有效利用Agent时间的目的，同时利用静态压缩算法，进一步压缩调度长度，提高了Agent的利用率。     

浅谈LZW压缩算法

介绍ＬＺＷ压缩算法，此算法是一种对字节流的压缩算法，其原理是用一种代码来表示数据中的串重复现象，从而达到压缩的目的。     

循环体间相关问题及改进的URPR软件流水方法

本文首先在理论上分析了循环体间相关对软件流水的影响.提出了一个由循环本身性质决定的充分必要条件并证明了满足此条件的循环是可限制的,否则是不可限制的;其次我们证明了任意不可限制的循环展开K次后即可转换为可限制循环,K取决于循环本身的性质;最后给出了循环预处理算法和一个新的循环体压缩算法.实验结果表明,这两个算法可使URPR算法对任意循环都能得到最优时间效益并保持了良好的空间效益及低的计算复杂性.     

RWM&DEWS数据二次压缩算法研究

对柑橘实时水分监控与旱情预警系统中的数据参数进行拟合分析,在探讨SDT和LZW 2种压缩算法的基础上,提出一种二次压缩算法:第1次压缩采用基于SDT算法思想的甲均值方法;第2次压缩采用改进的LZW算法实现.对压缩效果进行测试,仿真实验证明,在相同的硬件和软件环境下,该算法能实时、高效地压缩数据.     

基于分区的Elias-Fano-Golomb-Rice倒排索引压缩算法

基于分区的Elias-Fano算法被应用于倒排索引压缩,显示出良好的空间压缩性能。本文证明了Golomb-Rice算法的压缩性能优于Elias-Fano算法。结合基于分区的Elias-Fano算法中“分区”思想,提出一种基于分区的Elias-Fano-Golomb-Rice倒排索引压缩算法。实验结果表明,与其他倒排索引压缩算法相比,基于分区的Elias-Fano-Golomb-Rice倒排索引压缩算法有更好的压缩性能。     

配送实时调度管理系统中最短路径的双队列算法及其JAVA实现

文章采用J2EE技术和改进的Dijkstra双队列算法研究了面向第三方物流的实时动态配送调度管理系统,文中简介了该系统的功能和结构,详述了配送调度模块中采用的求解两点间最短路径的双队列图形增长算法的流程和数据结构,文中给出了改进算法的JAVA实现方法和核心流程代码。     

一种抗压缩的矢量地图水印算法

对Douglas-Peucker矢量图压缩算法存在的不足进行改进,在此基础上提出一种抗压缩的矢量地图水印算法。该算法选择矢量地图的顶点坐标作为水印载体,采用改进的Douglas-Peucker算法对冗余顶点进行压缩,利用压缩后的顶点数据嵌入水印。实验结果表明,该水印算法具有较好的抗压缩效果。