关键字 |
基于字典的压缩,压缩位掩码,RLE压缩,压缩比特流,现场可编程门阵列(FPGA)。 |
介绍 |
现场可编程阵列(FPGA)大门在记忆存储配置比特流在容量和带宽通常是有限的。随着FPGA可重构系统中常用和特定于应用程序的集成电路(ASIC),配置内存成为一个关键因素在决定IP核的数量,一个系统可以配置和重新配置的延迟。比特流压缩算法解决内存约束问题通过降低比特流的大小和增加减压加速器由简单的解码逻辑解码速度。但很少有其他的算法快速高效的压缩比和压缩。图1显示了典型的压缩FPGA bitstreamreconfiguration . .解压缩硬件解码和传输压缩比特从内存配置硬件,然后转移到可配置逻辑块(CLB)的记忆。压缩比是度量常用来衡量有效性的压缩技术,定义为在方程1 - 1。 |
![图像](//www.cheescube.com/articles-images/IJAREEIE-660-e001.gif) |
RELARED工作 |
有无数的压缩算法,可用于压缩比特流配置。这些技术可以分为两类基于如何利用冗余:特定的压缩和通用的比特流压缩格式。第一类压缩技术的利用当地的冗余配置一个或多个比特流读回数据和存储执行异(XOR)操作的差异。这些算法要求FPGA部分重新配置和帧回读功能的支持。锅等。[4]使用帧重新排序没有回读功能的FPGA。在这个技术框架重新排序,这样后续帧配置之间的相似性是最大值。连续帧之间的差异然后编码使用基于霍夫曼运行长度编码或降落区压缩。另一种方法提出了在同一篇文章中组织和读取配置框架。组织的框架,这样压缩比特流包含最小数量的差异向量和最大回读配置帧从而减少显著压缩帧。如此复杂的编码方案倾向于产生优秀的压缩比。However, decompression is a major bottleneck and is not addressed by Pan et al. [4].In sum, the compression technique in [4] achieves significant compression but incursfdrastic decompression overhead. On the other hand the approaches in second category [1] [9] try to maintain decompression overhead in an acceptable range but compromises on compression efficiency. Our technique tries to consider decompression bottleneck and overhead during the compression of bitstreams. The compression parametersare chosen such that compressed bitstreams are decode friendly while maintaining a goodcompression ratio. Fig. 2 shows our decode-aware bitstream compressionframework.Onthe compression side, FPGA configuration bitstream is analyzed for selection of profitable dictionary entries and bitmask patterns. The compressed bitstream is then generated using bitmask-based compression and run length encoding (RLE). Next, our decodeaware placement algorithm is employed to place the compressed bitstream in the memory for efficient decompression. During run-time, the compressed bitstream is transmitted from the memory to the decompression engine, and the original configuration bitstream is produced by decompression. |
算法1概述了四个重要的步骤在我们decode-aware压缩框架(图1所示):1)位掩码的选择;2)字典选择;3)integratedRLE压缩;和4)decode-aware放置。输入比特流首先划分为一个符号序列长度。然后位掩码模式和用于选择bitmask-based压缩字典条目。接下来,使用位掩码和RLE压缩符号序列。我们使用相同的算法来执行bitmask-based压缩。RLE压缩算法在我们还讨论了在以后的章节。最后,我们把压缩比特流到解码友好布局在内存中使用位置的算法。 |
![图像](//www.cheescube.com/articles-images/IJAREEIE-660-a001.jpg) |
基于字典的压缩 |
本节描述了现有的基于字典的方法并分析了它们的局限性。首先,我们描述的标准基于字典的方法。接下来,我们描述现有技术提高标准方法通过考虑不匹配(汉明距离)。最后,我们最近执行的详细成本效益分析方法而言,他们可以产生多少重复模式不匹配。这一分析的基础我们的技术最大化使用位掩码的重复模式。 |
基于字典的方法: |
词典code-compression技术提供压缩效率以及快速减压机制。基本思想是利用常见的指令序列通过使用一个字典。重复出现替换为一个码字指向的索引字典包含模式。压缩程序由两个码字的和未压缩的指令。图3显示了一个示例基于字典的压缩使用一个简单的程序的二进制代码。二进制由十8 b模式,即。,a total of 80 b. The dictionary has two 8-b entries. The compressed program requires 62 b, and the dictionary requires 16 b. In this case, the CR is 97.5%. This example shows a variable-length encoding. As a result, there are several factors that may need to be included in the computation of the CR, such as byte alignments for branch targets and the address-mapping table. |
图3演示了一个简单的基于字典的压缩与所有单词在字典和部分的单词在字典有限。获得最佳压缩比一个直观的方法是评估所有可能的单词长度的值(w)和字典大小(d)。这种算法将非多项式时间达到有效的参数组合。译码器的最大限制的速度是它可以处理的比特数。在这方面,最喜欢LZ78压缩方法通过其变体LZW广为人知,明显的优势是能够阅读整个输入单词,单词具有相同的编码长度。然而,同样的技术缺点的动态生成和维护字典的内容。解决方案的目标速度和简单计算是使用一个统计词典,根据整个比特流的内容和整个减压。与霍夫曼字典,没有明确的方法可以创建这样一个字典以最优的方式(至少不是作者的知识),但比特流的特点做出选择一个简单的。特别是,由于零的符号出现的概率高,编码方案退化成有点水平的RLE少量修改。 |
基于位掩码的压缩 |
Bitmask-based压缩是一种增强基于字典的压缩方案,可以帮助我们得到更多的匹配模式。在基于字典的压缩,每个向量压缩只有完全匹配一个字典条目。如图5所示,我们可以压缩到6个数据条目使用基于位掩码的压缩。压缩数据如下表示。这些向量匹配与3位直接被压缩。第一位代表是否被压缩(使用0)(使用1)。第二位表示是否使用位掩码(0)使用压缩(使用1)。最后一点表示字典索引。数据压缩使用位掩码需要7位。前两位,和之前一样,表示如果数据压缩,数据是否压缩使用位掩码。接下来的两位指示位掩码的位置,其次是两位表明位掩码的模式。例如,最后数据矢量图5中使用位掩码被压缩。 The bitmask position is 11, which indicates the fourth even bit position from left. For this case, we have assumed fixed bitmasks, which are always employed on even-bit positions and hence only 2 bits are sufficient to represent the four positions in a 8-bit data. The last bit gives the dictionary index. The bitmask XORed with the dictionary entry produces the original data. In this example, the compression efficiency is 27.5%, based on the following formula expressed as percentage: |
因为现有的方法不能处理不关心(“X”),在这个例子中,我们已经取代了由1都不关心。注意,我们可以用0已经取代了都不关心。在这种情况下,它将导致更糟糕的压缩效率为2.5%。更好的压缩效率可以通过有选择地取代不关心“0”或“1”,而不是取代所有的0 (1)。这是一个重大挑战识别选择性替代产生最好的压缩效率。 |
运行长度编码压缩的单词 |
比特流的配置通常包含连续重复序列。虽然bitmask-based压缩编码等模式使用相同的重复压缩的话,建议在运行长度编码序列可能产生更好的压缩效果。有趣的是,代表这样的编码不需要额外的比特。注意,0位掩码值是从未使用过,因为这个值意味着它是一个精确匹配,使用零位掩码编码。使用这个作为一种特殊的标记,可以在不改变代码格式编码这些重复bitmask-basedcompression.Fig。5说明了bitmask-based RLE。输入包含单词“00000000”重复五次。在正常bitmask-based压缩这些话将压缩重复压缩的话,而我们的方法取代这样的重复使用“00”的位掩码。在这个例子中,第一次出现将编码和往常一样,而剩下的4重复使用RLE编码。重复编码的位掩码数量抵消和字典比特组合在一起。 In this example, the bitmask offset is “10”and dictionary index is “0”. Therefore, the number of repetition will be “100” (i.e., 4 ).The compressed words are run length encoded only if the RLE yields a shorter code length than the original bitmask encoding. In other words, if there are r repetitions of code with length and the number of bits required to encode them using RLE is bits, RLE is used only if bits. Since RLE is performed independently, the bit savings calculation during dictionary selection should be modified accordingly to model the effect of RLE. |
行程长度的硬件 |
游程硬件图7所示。它由一个寄存器来保存当前地址输出;向下计数器计算长度;一个加法器,将偏移量添加到前面的值;和mux之间做出选择之前的值添加到抵消和新基值。mux选择基址寄存器的输出时,减法计数器等于零。当一个新的码字到达时,基值写入地址寄存器同时downcounter长度是写入。 |
减压引擎 |
减压引擎是一个硬件组件用于解码压缩配置比特流和饲料的未压缩比特流在fpga配置单元。正如前面所讨论的那样,一个解压缩引擎通常有两部分:缓冲电路来缓冲和对齐代码获取内存,而解码器执行减压操作生成原始符号。自从解码器在之前的文献研究,我们实现我们的位掩码和基于RLE解码器的设计成功的方式。 |
减压引擎结构8位内存图7所示。“左移器组装缓冲数组”(ABLSA)是用来替换原来的“缓冲桶移器”(BBS)。ABLSA的基本工作原理是使用一组左移位寄存器来缓冲两比特流分开。由于代码长度bitmask-based压缩是唯一由前两位代码(压缩,是位蒙面旗帜),我们可以很容易地获得通过检查代码的长度的比特流CS和BS。然后,移位寄存器(或PT流)持有部分代码的确定是基于代码的二进制表示的长度。最后,原始代码组装装配缓冲和美联储的位掩码或RLE解码器。当一些移器为空,这是保证加载正确的解压缩算法。 |
压缩效率 |
我们测量了压缩效率使用所需的时间重新配置一个压缩比特流,减压的资源使用和最大工作频率引擎。重新配置时间计算使用该产品所需要的周期数的解码压缩比特流和操作时钟速度。我们注意到,我们的方法可以在更高的频率和只占60%面积相比原始bitmask-based减压引擎。因为我们的方法有相同的位掩码的译码电路,improvementis由于ABLSA作为我们的预期。withprevious技术相比,我们的方法实现了几乎相同的操作速度快,面积少,也实现了15%的-20%更好的压缩,这意味着我们可以减压更多配置信息在相同的时间。 |
仿真结果和讨论 |
答:仿真结果基于字典的压缩 |
![图像](//www.cheescube.com/articles-images/IJAREEIE-660-g008.gif) |
压实扫描链网络,在这一节中提到的,减少了扫描深度扫描链,降低了测试成本。然后将基于字典的压缩方案与压实扫描链网络实现高压缩比和快速应用程序时间。 |
仿真结果基于字典的压缩 |
![图像](//www.cheescube.com/articles-images/IJAREEIE-660-g009.gif) |
这里已经被压缩的位流转换为原来的大小对减压引擎。这里所示的仿真结果证明原始数据从压缩数据检索。 |
c位掩码压缩和解压缩的仿真结果 |
![图像](//www.cheescube.com/articles-images/IJAREEIE-660-g010.gif) |
这已经开发使用一个有效的测试数据压缩算法使用的位掩码。压缩代码存储信息关于面具的类型,位置和面具的面具模式本身。面具可以应用在不同的地方在一个向量和所需的比特数表示的位置在面具的类型而异。 |
d .仿真结果的RLE压缩 |
![图像](//www.cheescube.com/articles-images/IJAREEIE-660-g011.gif) |
行程长度编码的一种变体完全符合要求的地址压缩。一系列的地址与一个共同的偏移可以压缩成一个码字的形式基础,抵消和长度。 |
e .基于RLE压缩的仿真结果 |
![图像](//www.cheescube.com/articles-images/IJAREEIE-660-g012.gif) |
这一策略使用一个更密集的压缩算法。它试图重新排序的地址数据对最优方式。由于地址必须解压和除了发送数据,我们的减压策略使用的地址和数据总线发送解压码字。 |
结论 |
现有的压缩算法提供良好的压缩与慢压缩或快速减压压缩效率为代价的。在本文中,我们提出了一个decoding-aware压缩技术,试图获得最好的压缩和快速压缩性能。我们还利用运行长度编码的连续重复模式有效结合bitmask-based压缩进一步提高压缩比和压缩效率。我们的实验结果证明了我们的技术提高了10%到15%的压缩比而减压引擎能够检索压缩数据没有任何损失。配置时间减少了15%到20%,相比之下最著名的减压加速器。在未来,我们打算调查更多的放置算法兼容其他压缩技术如霍夫曼编码、Goulomb编码和算术编码。 |
表乍一看 |
![Click Here 表的图标](//www.cheescube.com/articles-images/table-icon.gif) |
表1 |
|
|
数据乍一看 |
![Click Here 图1](//www.cheescube.com/articles-images/IJAREEIE-660-g001.gif) |
![Click Here 图2](//www.cheescube.com/articles-images/IJAREEIE-660-g002.gif) |
![Click Here 图3](//www.cheescube.com/articles-images/IJAREEIE-660-g003.gif) |
![Click Here 图4](//www.cheescube.com/articles-images/IJAREEIE-660-g004.gif) |
图1 |
图2 |
图3 |
图4 |
![Click Here 图5](//www.cheescube.com/articles-images/IJAREEIE-660-g005.gif) |
![Click Here 图6](//www.cheescube.com/articles-images/IJAREEIE-660-g006.gif) |
![Click Here 图7](//www.cheescube.com/articles-images/IJAREEIE-660-g007.gif) |
![Click Here 图8](//www.cheescube.com/articles-images/IJAREEIE-660-g008.gif) |
图5 |
图6 |
图7 |
图8 |
![Click Here 图19](//www.cheescube.com/articles-images/IJAREEIE-660-g009.gif) |
![Click Here 图10](//www.cheescube.com/articles-images/IJAREEIE-660-g010.gif) |
![Click Here 图11](//www.cheescube.com/articles-images/IJAREEIE-660-g011.gif) |
![Click Here 图12](//www.cheescube.com/articles-images/IJAREEIE-660-g012.gif) |
图9 |
图10 |
图11 |
图12 |
|
|
引用 |
- 潘j . H。,Mitra.T.,and WongW. F.,“Configuration bitstream compression for dynamically reconfigurable FPGAs,” in Proc. Int. Conf.Compute.-Aided Des.,pp.766–773,2004.
- 豪。,and Wilson W. D.,“Run length compression techniques for FPGA configurations,” in Proc. IEEE Symp. Field- Program.CustomCompute. Mach., pp. 286–287,1999.
- Dandalis。,and PrasannaV.K.,“Configuration compression for FPGA-based embedded systems,” IEEE Trans. Very Large ScaleIntegr. (VLSI) Syst., vol. 13, no. 12, pp. 1394–1398, Dec. 2005.
- KochD。,BeckhoffC., and TeichJ.,“Bitstream decompression for high speed FPGA configuration from slow memories,” in Proc. Int. Conf.Field-Program. Technol., 2007, pp. 161–168.
- SeongS。,and MishraP.,“Bitmask-based code compression for embedded systems,” IEEE Trans. Compute.-Aided Des. Integr. CircuitsSyst., vol. 27, no. 4, pp. 673–685, Apr. 2008.
- 豪。莉斯。,and. SchwabenE. , “Configuration compression for the Xilinx XC6200 FPGA,” IEEE Trans. Compute.- Aided Des. Integr. CircuitsSyst., vol. 18, no. 8, pp. 1107–1113, Aug. 1999.
- KhuA。,“Xilinx FPGA configuration data compression and decompression,” WP152 ed. Xilinx, San Jose, CA, 2001.
- WirthlinM.J。,and HutchingsB.L,“Sequencing Run-Time Reconfigured Hardware with Software”, ACM/SIGDA InternationalSymposium on Field-Programmable GateArrays, pp. 122-128, 1996.
|