LZ4相关.rar_lz4_压缩解压下载-pudn.com

<html xmlns="http://www.w3.org/1999/xhtml"> <head> <meta charset="utf-8"> <meta name="generator" content="pdf2htmlEX"> <meta http-equiv="X-UA-Compatible" content="IE=edge,chrome=1"> <link rel="stylesheet" href="https://static.pudn.com/base/css/base.min.css"> <link rel="stylesheet" href="https://static.pudn.com/base/css/fancy.min.css"> <link rel="stylesheet" href="https://static.pudn.com/prod/directory_preview_static/62509d696caf5961920d964e/raw.css"> <script src="https://static.pudn.com/base/js/compatibility.min.js"></script> <script src="https://static.pudn.com/base/js/pdf2htmlEX.min.js"></script> <script> try{ pdf2htmlEX.defaultViewer = new pdf2htmlEX.Viewer({}); }catch(e){} </script> <title></title> </head> <body> <div id="sidebar" style="display: none"> <div id="outline"> </div> </div> <div id="pf1" class="pf w0 h0" data-page-no="1"><div class="pc pc1 w0 h0"><img class="bi x0 y0 w1 h1" alt="" src="https://static.pudn.com/prod/directory_preview_static/62509d696caf5961920d964e/bg1.jpg"><div class="t m0 x1 h2 y1 ff1 fs0 fc0 sc0 ls0 ws0">110 IEEE TRANSACTIONS ON CONSUMER ELECTRONICS, VOL. 64, NO. 1, FEBRUARY 2018</div><div class="t m0 x2 h3 y2 ff1 fs1 fc0 sc0 ls1 ws0">Data Compression Device Based on</div><div class="t m0 x3 h3 y3 ff1 fs1 fc0 sc0 ls1 ws0">Modiﬁed LZ4 Algorithm</div><div class="t m0 x4 h4 y4 ff1 fs2 fc0 sc0 ls1 ws0">Weiqiang Liu, Senior Member, IEEE, Faqiang Mei, Chenghua Wang, Maire O’Neill, Senior Member, IEEE,</div><div class="t m0 x5 h4 y5 ff1 fs2 fc0 sc0 ls1 ws0">and Earl E. Swartzlander, Jr., Life Fellow, IEEE</div><div class="t m0 x6 h5 y6 ff3 fs3 fc0 sc0 ls5 ws0">Abstract—Data compression is commonly used in NAND ﬂash-</div><div class="t m0 x1 h5 y7 ff4 fs3 fc0 sc0 ls1 ws0">based solid state drives (SSDs) to increase their storage perfor-</div><div class="t m0 x1 h5 y8 ff4 fs3 fc0 sc0 ls1 ws0">mance and lifetime as it can reduce the amount of data written to</div><div class="t m0 x1 h5 y9 ff4 fs3 fc0 sc0 ls8 ws0">and read from</div><div class="t m0 x7 h5 ya ff4 fs4 fc0 sc0 ls6 ws0">NAND ﬂash memory. Software-based data com-</div><div class="t m0 x1 h5 yb ff4 fs3 fc0 sc0 ls1 ws0">pression reduces SSD performance signiﬁcantly and, as such,</div><div class="t m0 x1 h5 yc ff4 fs3 fc0 sc0 ls1 ws0">hardware-based data compression designs are required. This</div><div class="t m0 x1 h5 yd ff4 fs3 fc0 sc0 ls5 ws0">paper studies the latest lossless data compression algorithm,</div><div class="t m0 x1 h5 ye ff4 fs3 fc0 sc0 ls5 ws0">i.e., the Lempel-Ziv (LZ)4 algorithm which is one of the fastest</div><div class="t m0 x1 h5 yf ff4 fs3 fc0 sc0 ls1 ws0">compression algorithms reported to date. A data compression</div><div class="t m0 x1 h5 y10 ff4 fs3 fc0 sc0 ls5 ws0">FPGA prototype based on the LZ4 lossless compression algorithm</div><div class="t m0 x1 h5 y11 ff4 fs3 fc0 sc0 ls1 ws0">is studied. The original LZ4 compression algorithm is modiﬁed</div><div class="t m0 x1 h5 y12 ff4 fs3 fc0 sc0 ls8 ws0">for real-time hardware implementation. Two hardware architec-</div><div class="t m0 x1 h5 y13 ff4 fs3 fc0 sc0 ls5 ws0">tures of the modiﬁed LZ4 algorithm (MLZ4) are proposed with</div><div class="t m0 x1 h5 y14 ff4 fs3 fc0 sc0 ls1 ws0">both compressors and decompressors, which are implemented</div><div class="t m0 x1 h5 y15 ff4 fs3 fc0 sc0 ls5 ws0">on an FPGA evaluation kit. The implementation results show</div><div class="t m0 x1 h5 y16 ff4 fs3 fc0 sc0 ls1 ws0">that the proposed compressor architecture can achieve a high</div><div class="t m0 x1 h5 y17 ff4 fs3 fc0 sc0 ls1 ws0">throughput of up to 1.92 Gb/s with a compression ratio of up</div><div class="t m0 x1 h5 y18 ff4 fs3 fc0 sc0 ls1 ws0">to 2.05, which is higher than all previous LZ algorithm designs</div><div class="t m0 x1 h5 y19 ff4 fs3 fc0 sc0 ls1 ws0">implemented on FPGAs. The compression device can be used in</div><div class="t m0 x1 h5 y1a ff4 fs3 fc0 sc0 ls1 ws0">high-end SSDs to further increase their storage performance and</div><div class="t m0 x1 h5 y1b ff4 fs3 fc0 sc0 ls1 ws0">lifetime.</div><div class="t m0 x6 h5 y1c ff3 fs3 fc0 sc0 ls1 ws0">Index Terms—FPGA, lossless compression, Lempel-Ziv (LZ)</div><div class="t m0 x1 h5 y1d ff4 fs3 fc0 sc0 ls5 ws0">algorithms, LZ4, solid-state drives (SSDs).</div><div class="t m0 x8 h6 y1e ff1 fs5 fc0 sc0 ls9 ws0">I. INTRODUCTION</div><div class="t m0 x1 h7 y1f ff4 fs7 fc0 sc0 ls1 ws0">S</div><div class="t m0 x9 h6 y20 ff1 fs5 fc0 sc0 lsb ws0">OLID-STATE drives (SSDs) based on NAND ﬂash mem-</div><div class="t m0 x9 h6 y21 ff1 fs5 fc0 sc0 lsb ws0">ory have become popular in consumer electronic devices</div><div class="t m0 x1 h6 y22 ff1 fs5 fc0 sc0 lsb ws0">such as smart phones, tablet, and desktop systems [1], [2].</div><div class="t m0 x1 h6 y23 ff1 fs5 fc0 sc0 lsb ws0">It is highly desirable to reduce the amount of data in SSDs</div><div class="t m0 x1 h6 y24 ff1 fs5 fc0 sc0 lsf ws0">and the read/write data transmission time to/from SSDs as</div><div class="t m0 x1 h6 y25 ff1 fs5 fc0 sc0 lsb ws0">ﬂash memory has a ﬁnite number of program-erase (P/E)</div><div class="t m0 x1 h6 y26 ff1 fs5 fc0 sc0 lsf ws0">cycles thus limited lifetime [3]. For example, older single-</div><div class="t m0 x1 h6 y27 ff1 fs5 fc0 sc0 lsb ws0">level cell (SLC)</div><div class="t m0 xa h6 y28 ff1 fs6 fc0 sc0 ls10 ws0">NAND-ﬂash memory was able to withstand</div><div class="t m0 x1 h6 y29 ff1 fs5 fc0 sc0 lsf ws0">150 000 P/E cycles, while multilevel cell (MLC) NAND-ﬂash</div><div class="t m0 x1 h6 y2a ff1 fs5 fc0 sc0 lsb ws0">memory using 15–19 nm process technologies wears out after</div><div class="t m0 x1 h6 y2b ff1 fs5 fc0 sc0 ls11 ws0">only 3000 P/E cycles [2], [4]. Furthermore, the performance</div><div class="t m0 xb h8 y2c ff1 fs6 fc0 sc0 ls12 ws0">Manuscript received December 4, 2017; revised February 10, 2018;</div><div class="t m0 x1 h8 y2d ff1 fs6 fc0 sc0 ls1 ws0">accepted February 15, 2018. Date of publication March 2, 2018; date of cur-</div><div class="t m0 x1 h8 y2e ff1 fs6 fc0 sc0 ls12 ws0">rent version March 29, 2018. This work was supported by the Fundamental</div><div class="t m0 x1 h8 y2f ff1 fs6 fc0 sc0 ls12 ws0">Research Funds for the Central Universities China under Grant NS2017024.</div><div class="t m0 x1 h9 y30 ff2 fs6 fc0 sc0 ls12 ws0">(Corresponding author: Weiqiang Liu.)</div><div class="t m0 xb h8 y31 ff1 fs6 fc0 sc0 ls1 ws0">W. Liu, F. Mei, and C. Wang are with the College of Electronic</div><div class="t m0 x1 h8 y32 ff1 fs6 fc0 sc0 ls1 ws0">and Information Engineering, Nanjing University of Aeronautics and</div><div class="t m0 x1 h8 y33 ff1 fs6 fc0 sc0 ls1 ws0">Astronautics, Nanjing 211106, China (e-mail: liuweiqiang@nuaa.edu.cn;</div><div class="t m0 x1 h8 y34 ff1 fs6 fc0 sc0 ls1 ws0">meifaqiang@nuaa.edu.cn; chwang@nuaa.edu.cn).</div><div class="t m0 xb h8 y35 ff1 fs6 fc0 sc0 ls1 ws0">M. O’Neill is with the Center for Secure Information Technologies, Queen’s</div><div class="t m0 x1 h8 y36 ff1 fs6 fc0 sc0 ls13 ws0">University Belfast, Belfast BT3 9DT, U.K. (e-mail: m.oneill@ecit.qub.ac.uk).</div><div class="t m0 xb h8 y37 ff1 fs6 fc0 sc0 ls13 ws0">E. E. Swartzlander is with the Department of Electrical and Computer</div><div class="t m0 x1 h8 y38 ff1 fs6 fc0 sc0 ls1 ws0">Engineering, University of Texas at Austin, Austin, TX 78712 USA (e-mail:</div><div class="t m0 x1 h8 y39 ff1 fs6 fc0 sc0 ls13 ws0">eswartzla@aol.com).</div><div class="t m0 xb h8 y3a ff1 fs6 fc0 sc0 ls1 ws0">Digital Object Identiﬁer 10.1109/TCE.2018.2810480</div><div class="t m0 xc h8 y3b ff1 fs6 fc0 sc0 ls13 ws0">Fig. 1. Typical SSD architecture with data compression acceleration.</div><div class="t m0 xc h6 y3c ff1 fs5 fc0 sc0 lsb ws0">of MLC ﬂash memory is also much slower than that of its</div><div class="t m0 xc h6 y3d ff1 fs5 fc0 sc0 lsb ws0">SLC counterpart. Also, more advanced triple-level cell</div><div class="t m0 xd h8 y3e ff1 fs6 fc0 sc0 lsc ws0">NAND</div><div class="t m0 xc h6 y3f ff1 fs5 fc0 sc0 ls11 ws0">ﬂash memory has an even lower number of P/E cycles [5].</div><div class="t m0 xc h6 y40 ff1 fs5 fc0 sc0 lsf ws0">This problem is expected to worsen with further scaling of</div><div class="t m0 xc h6 y41 ff1 fs5 fc0 sc0 lsf ws0">the semiconductor process. Therefore, to increase the lifetime</div><div class="t m0 xc h6 y42 ff1 fs5 fc0 sc0 lsb ws0">and also the performance of ﬂash-based SSDs, the amount of</div><div class="t m0 xc h6 y43 ff1 fs5 fc0 sc0 lsb ws0">data written to and read from the SSDs should be reduced,</div><div class="t m0 xc h6 y44 ff1 fs5 fc0 sc0 lsb ws0">which can be achieved using data compression. Another ben-</div><div class="t m0 xc h6 y45 ff1 fs5 fc0 sc0 lsb ws0">eﬁt of using lossless data compression in SSDs is to reduce</div><div class="t m0 xc h6 y46 ff1 fs5 fc0 sc0 lsf ws0">the I/O latency.</div><div class="t m0 xe h6 y47 ff1 fs5 fc0 sc0 lsb ws0">Data compression for SSDs has been widely adopted.</div><div class="t m0 xc h6 y48 ff1 fs5 fc0 sc0 lsf ws0">Data compression can be implemented in three layers: 1) the</div><div class="t m0 xc h6 y49 ff1 fs5 fc0 sc0 lsf ws0">application; 2) the ﬁle system; or 3) the ﬁrmware of the stor-</div><div class="t m0 xc h6 y4a ff1 fs5 fc0 sc0 lsb ws0">age device. Most data compression algorithms are adopted in</div><div class="t m0 xc h6 y4b ff1 fs5 fc0 sc0 lsf ws0">the application layer and the ﬁle system using software imple-</div><div class="t m0 xc h6 y4c ff1 fs5 fc0 sc0 lsf ws0">mentation. Software-based data compression can be useful in</div><div class="t m0 xc h6 y4d ff1 fs5 fc0 sc0 lsf ws0">improving the lifetime of SSDs. However, the overall perfor-</div><div class="t m0 xc h6 y4e ff1 fs5 fc0 sc0 lsb ws0">mance of SSDs is reduced signiﬁcantly due to the slow com-</div><div class="t m0 xc h6 y4f ff1 fs5 fc0 sc0 lsb ws0">pression and decompression speed. A recent study [6] based</div><div class="t m0 xc h6 y50 ff1 fs5 fc0 sc0 lsb ws0">on realistic data and systems show that applying data com-</div><div class="t m0 xc h6 y51 ff1 fs5 fc0 sc0 lsf ws0">pression in the ﬁrmware of the SSDs using a data compression</div><div class="t m0 xc h6 y52 ff1 fs5 fc0 sc0 lsb ws0">hardware accelerator is the best approach. A typical SSD archi-</div><div class="t m0 xc h6 y53 ff1 fs5 fc0 sc0 lsf ws0">tecture with data compression acceleration is shown in Fig. 1.</div><div class="t m0 xe h6 y54 ff1 fs5 fc0 sc0 lsb ws0">Although hardware-based compression is required for</div><div class="t m0 xd h8 y55 ff1 fs6 fc0 sc0 lsa ws0">NAND</div><div class="t m0 xc h6 y56 ff1 fs5 fc0 sc0 lsb ws0">ﬂash memory and SSDs, little research has been conducted</div><div class="t m0 xc h6 y57 ff1 fs5 fc0 sc0 lsb ws0">on how to design a high performance hardware compres-</div><div class="t m0 xc h6 y58 ff1 fs5 fc0 sc0 lsb ws0">sion accelerator [7]–[13]. In [6], it was found that for high-</div><div class="t m0 xc h6 y59 ff1 fs5 fc0 sc0 lsb ws0">end SSDs with transaction rates of up to 3K per second,</div><div class="t m0 xc h6 y5a ff1 fs5 fc0 sc0 lsf ws0">compression/decompression rates of above 200 Mb/s (i.e.,</div><div class="t m0 xc h6 y5b ff1 fs5 fc0 sc0 lsf ws0">1.6 Gb/s) are required. However, existing designs are lim-</div><div class="t m0 xc h6 y5c ff1 fs5 fc0 sc0 lsf ws0">ited in performance with compression speeds in the range of</div><div class="t m0 xc h6 y5d ff1 fs5 fc0 sc0 lsb ws0">0.567–1.6 Gb/s [7]–[13], which cannot meet the requirement</div><div class="t m0 xc h6 y5e ff1 fs5 fc0 sc0 lsb ws0">of high-end SSDs.</div><div class="t m0 xe h6 y5f ff1 fs5 fc0 sc0 lsb ws0">In this paper, the design of a hardware accelerator based on</div><div class="t m0 xc h6 y60 ff1 fs5 fc0 sc0 lsf ws0">the latest lossless data compression algorithm, i.e., Lempel-Ziv</div><div class="t m0 xf h8 y61 ff1 fs6 fc0 sc0 ls16 ws0">1558-4127</div><div class="t m0 x10 h8 y62 ff1 fs6 fc0 sc0 ls1 ws0">c</div><div class="t m0 x11 h8 y61 ff5 fs6 fc0 sc0 ls1 ws0"> 2018 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission.</div><div class="t m0 x12 h8 y63 ff1 fs6 fc0 sc0 ls1 ws0">See http://www.ieee.org/publications_standards/publications/rights/index.html for more information.</div><a class="l" rel='nofollow' onclick='return false;'><div class="d m1"></div></a><a class="l" rel='nofollow' onclick='return false;'><div class="d m1"></div></a><a class="l" rel='nofollow' onclick='return false;'><div class="d m1"></div></a><a class="l" rel='nofollow' onclick='return false;'><div class="d m1"></div></a><a class="l" rel='nofollow' onclick='return false;'><div class="d m1"></div></a><a class="l" rel='nofollow' onclick='return false;'><div class="d m1"></div></a><a class="l" rel='nofollow' onclick='return false;'><div class="d m1"></div></a><a class="l" rel='nofollow' onclick='return false;'><div class="d m1"></div></a><a class="l" rel='nofollow' onclick='return false;'><div class="d m1"></div></a><a class="l" rel='nofollow' onclick='return false;'><div class="d m1"></div></a><a class="l" rel='nofollow' onclick='return false;'><div class="d m1"></div></a><a class="l" rel='nofollow' onclick='return false;'><div class="d m1"></div></a><a class="l" rel='nofollow' onclick='return false;'><div class="d m1"></div></a></div><div class="pi" data-data='{"ctm":[1.568627,0.000000,0.000000,1.568627,0.000000,0.000000]}'></div></div> </body> </html>

<div id="pf2" class="pf w0 h0" data-page-no="2"><div class="pc pc2 w0 h0"><img class="bi x0 y0 w1 h1" alt="" src="https://static.pudn.com/prod/directory_preview_static/62509d696caf5961920d964e/bg2.jpg"><div class="t m0 x1 h2 y1 ff1 fs0 fc0 sc0 ls0 ws0">LIU et al.: DATA COMPRESSION DEVICE BASED ON MLZ4 111</div><div class="t m0 x1 h6 y64 ff1 fs5 fc0 sc0 ls1 ws0">(LZ)4 [14] for data compression in high-end SSDs is studied</div><div class="t m0 x1 h6 y65 ff1 fs5 fc0 sc0 lsb ws0">and demonstrated on an FPGA device. The original LZ4 algo-</div><div class="t m0 x1 h6 y66 ff1 fs5 fc0 sc0 lsb ws0">rithm is somewhat difﬁcult to implement in hardware as it</div><div class="t m0 x1 h6 y67 ff1 fs5 fc0 sc0 lsf ws0">was proposed for software implementation. It is not possible</div><div class="t m0 x1 h6 y68 ff1 fs5 fc0 sc0 lsf ws0">to store all the text in calculating the hash. Its output delay is</div><div class="t m0 x1 h6 y69 ff1 fs5 fc0 sc0 lsb ws0">uncertain and the input data is limited by the address width of</div><div class="t m0 x1 h6 y6a ff1 fs5 fc0 sc0 lsb ws0">the hash table. As a result, the LZ4 algorithm has been mod-</div><div class="t m0 x1 h6 y6b ff1 fs5 fc0 sc0 lsb ws0">iﬁed for hardware implementation in this paper to solve these</div><div class="t m0 x1 h6 y6c ff1 fs5 fc0 sc0 lsf ws0">problems. By using the modiﬁed LZ4 algorithm (MLZ4), the</div><div class="t m0 x1 h6 y6d ff1 fs5 fc0 sc0 lsf ws0">hash computation is improved for the compression ratio and</div><div class="t m0 x1 h6 y6e ff1 fs5 fc0 sc0 lsb ws0">low output latency is achieved. The implementation results</div><div class="t m0 x1 h6 y6f ff1 fs5 fc0 sc0 lsb ws0">on an FPGA platform show the proposed MLZ4 architecture</div><div class="t m0 x1 h6 y70 ff1 fs5 fc0 sc0 lsb ws0">and provides the highest throughput performance compared</div><div class="t m0 x1 h6 y71 ff1 fs5 fc0 sc0 lsb ws0">with previous FPGA implementations of LZ algorithms, which</div><div class="t m0 x1 h6 y72 ff1 fs5 fc0 sc0 lsb ws0">makes it suitable for high-end SSDs.</div><div class="t m0 x6 h6 y73 ff1 fs5 fc0 sc0 lsf ws0">This paper is organized as follows. Section II reviews loss-</div><div class="t m0 x1 h6 y74 ff1 fs5 fc0 sc0 lsf ws0">less data compression algorithms and their hardware imple-</div><div class="t m0 x1 h6 y75 ff1 fs5 fc0 sc0 lsf ws0">mentations. The original LZ4 algorithm is also reviewed in</div><div class="t m0 x1 h6 y76 ff1 fs5 fc0 sc0 lsf ws0">this section. Section III presents the modiﬁed LZ4 algorithm.</div><div class="t m0 x1 h6 y77 ff1 fs5 fc0 sc0 lsb ws0">Two hardware architectures of both the MLZ4 compressors</div><div class="t m0 x1 h6 y78 ff1 fs5 fc0 sc0 lsf ws0">and decompressors are proposed in Section IV. A compari-</div><div class="t m0 x1 h6 y79 ff1 fs5 fc0 sc0 lsb ws0">son with other FPGA hardware designs of LZ algorithms is</div><div class="t m0 x1 h6 y7a ff1 fs5 fc0 sc0 lsb ws0">provided in Section V. Section VI concludes this paper.</div><div class="t m0 x13 h6 y7b ff1 fs5 fc0 sc0 ls9 ws0">II. R</div><div class="t m0 x14 h8 y7c ff1 fs6 fc0 sc0 ls19 ws0">EVIEW</div><div class="t m0 x1 ha y7d ff2 fs5 fc0 sc0 lsb ws0">A. Data Compression Algorithms and Implementations</div><div class="t m0 x6 h6 y7e ff1 fs5 fc0 sc0 lsf ws0">There are two main categories of data compression, namely,</div><div class="t m0 x1 h6 y7f ff1 fs5 fc0 sc0 ls1 ws0">lossy and lossless compression [15]. As lossy compression</div><div class="t m0 x1 h6 y80 ff1 fs5 fc0 sc0 lsf ws0">allows loss of accuracy to an acceptable level, it is usually used</div><div class="t m0 x1 h6 y81 ff1 fs5 fc0 sc0 lsf ws0">for multimedia applications where errors can be tolerated [16].</div><div class="t m0 x1 h6 y82 ff1 fs5 fc0 sc0 lsb ws0">Lossless compression can compress and then recover the</div><div class="t m0 x1 h6 y83 ff1 fs5 fc0 sc0 lsf ws0">data from compressed data without loss of information; and</div><div class="t m0 x1 h6 y84 ff1 fs5 fc0 sc0 lsf ws0">it is used for applications where even one single bit differ-</div><div class="t m0 x1 h6 y85 ff1 fs5 fc0 sc0 lsb ws0">ence between the original and reconstructed data cannot be</div><div class="t m0 x1 h6 y86 ff1 fs5 fc0 sc0 lsf ws0">tolerated.</div><div class="t m0 x6 h6 y87 ff1 fs5 fc0 sc0 lsb ws0">The applications of lossless data compression have been</div><div class="t m0 x1 h6 y88 ff1 fs5 fc0 sc0 lsb ws0">increasing signiﬁcantly due to both the demand for increased</div><div class="t m0 x1 h6 y89 ff1 fs5 fc0 sc0 lsb ws0">bandwidth [17], [18] and the need to improve storage</div><div class="t m0 x1 h6 y8a ff1 fs5 fc0 sc0 lsb ws0">capacity [3]. Lossless data compression has been successfully</div><div class="t m0 x1 h6 y8b ff1 fs5 fc0 sc0 lsf ws0">deployed in storage systems including tapes, hard disk drives,</div><div class="t m0 x1 h6 y8c ff1 fs5 fc0 sc0 lsf ws0">SSDs, ﬁle servers, and storage area networks.</div><div class="t m0 x6 h6 y8d ff1 fs5 fc0 sc0 lsf ws0">Lossless data compression can be achieved using two dif-</div><div class="t m0 x1 h6 y8e ff1 fs5 fc0 sc0 lsf ws0">ferent approaches: 1) statistical model-based compression such</div><div class="t m0 x1 h6 y8f ff1 fs5 fc0 sc0 ls11 ws0">as Huffman coding [19] and 2) dictionary-based compression</div><div class="t m0 x1 h6 y90 ff1 fs5 fc0 sc0 lsf ws0">including the LZ algorithms [20], [21]. The LZ algorithms</div><div class="t m0 x1 h6 y91 ff1 fs5 fc0 sc0 lsb ws0">belong to adaptive dictionary-based techniques, which are</div><div class="t m0 x1 h6 y92 ff1 fs5 fc0 sc0 lsf ws0">the most popular lossless compression algorithms when prior</div><div class="t m0 x1 h6 y93 ff1 fs5 fc0 sc0 lsf ws0">statistical characteristics of the data are unknown. The LZ</div><div class="t m0 x1 h6 y94 ff1 fs5 fc0 sc0 lsb ws0">algorithms have been adopted by many compression format</div><div class="t m0 x1 h6 y95 ff1 fs5 fc0 sc0 lsb ws0">standards such as Zip, GNU zip, and Zlib [22].</div><div class="t m0 x6 h6 y96 ff1 fs5 fc0 sc0 lsb ws0">LZ algorithms were proposed by Ziv and Lempel in</div><div class="t m0 x1 h6 y97 ff1 fs5 fc0 sc0 ls15 ws0">1977 [20] and 1978 [21] in their two landmark papers. These</div><div class="t m0 x1 h6 y98 ff1 fs5 fc0 sc0 lsb ws0">papers presented two different approaches. The approach</div><div class="t m0 x1 h6 y99 ff1 fs5 fc0 sc0 lsb ws0">based on the 1977 paper is referred to as the LZ77 (or</div><div class="t m0 x1 h6 y9a ff1 fs5 fc0 sc0 lsb ws0">LZ1) family which includes LZ77, LZRW [23], LZSS [24],</div><div class="t m0 x1 h6 y9b ff1 fs5 fc0 sc0 lsf ws0">LZ-Markov chain algorithm (LZMA) [11], etc. LZ77 algo-</div><div class="t m0 x1 h6 y9c ff1 fs5 fc0 sc0 lsb ws0">rithms use a sliding window to examine the input sequence.</div><div class="t m0 xc h8 y9d ff1 fs6 fc0 sc0 ls1 ws0">Fig. 2. Data format of an LZ4 sequence.</div><div class="t m0 xc h6 y9e ff1 fs5 fc0 sc0 lsb ws0">Its principle is to ﬁnd whether the sequence being compressed</div><div class="t m0 xc h6 y9f ff1 fs5 fc0 sc0 lsf ws0">appears in the previously input data. If so, a pointer is used to</div><div class="t m0 xc h6 ya0 ff1 fs5 fc0 sc0 lsf ws0">point to the repeated strings. The dictionary refers to a portion</div><div class="t m0 xc h6 ya1 ff1 fs5 fc0 sc0 ls11 ws0">of the previously encoded sequence. The approaches based on</div><div class="t m0 xc h6 ya2 ff1 fs5 fc0 sc0 ls11 ws0">the 1978 paper are known as the LZ78 (or LZ2) family which</div><div class="t m0 xc h6 ya3 ff1 fs5 fc0 sc0 ls11 ws0">includes LZ78, LZW [25], etc. LZ78 algorithms create a dic-</div><div class="t m0 xc h6 ya4 ff1 fs5 fc0 sc0 lsb ws0">tionary of phrases from the input data. When a match with</div><div class="t m0 xc h6 ya5 ff1 fs5 fc0 sc0 lsb ws0">the phrases that have appeared in the dictionary occurs, the</div><div class="t m0 xc h6 ya6 ff1 fs5 fc0 sc0 lsb ws0">encoder will output the phrase’s index in the dictionary rather</div><div class="t m0 xc h6 ya7 ff1 fs5 fc0 sc0 ls1 ws0">than the phrase itself.</div><div class="t m0 xe h6 ya8 ff1 fs5 fc0 sc0 lsf ws0">Collet [14] proposed the LZ4 algorithm in 2011 [13], which</div><div class="t m0 xc h6 ya9 ff1 fs5 fc0 sc0 lsb ws0">is a variant of LZ77. The compression speed of a LZ4 soft-</div><div class="t m0 xc h6 yaa ff1 fs5 fc0 sc0 lsf ws0">ware implementation is shown to be fastest among the LZ</div><div class="t m0 xc h6 yab ff1 fs5 fc0 sc0 lsf ws0">algorithms. However, there is little research conducted on the</div><div class="t m0 xc h6 yac ff1 fs5 fc0 sc0 lsb ws0">hardware implementation of LZ4 as it is much younger than</div><div class="t m0 xc h6 yad ff1 fs5 fc0 sc0 lsf ws0">other LZ algorithms. Hardware designs of lossless data com-</div><div class="t m0 xc h6 yae ff1 fs5 fc0 sc0 lsf ws0">pression algorithms are receiving increase attention due to</div><div class="t m0 xc h6 yaf ff1 fs5 fc0 sc0 lsb ws0">the exponential expansion in network communication and</div><div class="t m0 xc h6 yb0 ff1 fs5 fc0 sc0 lsb ws0">data storage. FPGA implementations of LZ algorithms such as</div><div class="t m0 xc h6 yb1 ff1 fs5 fc0 sc0 lsb ws0">LZRW3 [12], LZW [8], [10], the LZMA [11], and LZ4 [13]</div><div class="t m0 xc h6 yb2 ff1 fs5 fc0 sc0 lsf ws0">have been proposed to meet real-time requirements. Thus, it is</div><div class="t m0 xc h6 yb3 ff1 fs5 fc0 sc0 lsf ws0">necessary to study hardware architectures of LZ4 in order to</div><div class="t m0 xc h6 yb4 ff1 fs5 fc0 sc0 lsb ws0">explore its performance for consumer electronic applications</div><div class="t m0 xc h6 yb5 ff1 fs5 fc0 sc0 lsb ws0">such as SSDs.</div><div class="t m0 xc ha yb6 ff2 fs5 fc0 sc0 lsb ws0">B. Review of the LZ4 Algorithm</div><div class="t m0 xe h6 yb7 ff1 fs5 fc0 sc0 lsf ws0">This section reviews the LZ4 algorithm. Its data format and</div><div class="t m0 xc h6 yb8 ff1 fs5 fc0 sc0 lsb ws0">data ﬂow are introduced. The shortcomings of the original</div><div class="t m0 xc h6 yb9 ff1 fs5 fc0 sc0 lsf ws0">LZ4 algorithm and data format are also discussed.</div><div class="t m0 xe h6 yba ff1 fs5 fc0 sc0 lsb ws0">LZ4 was initially deﬁned as a form of compressed data for-</div><div class="t m0 xc h6 ybb ff1 fs5 fc0 sc0 lsb ws0">mat. Compressed data ﬁles are composed of LZ4 sequences</div><div class="t m0 xc h6 ybc ff1 fs5 fc0 sc0 lsb ws0">that include a token, literal length, offset, and match length</div><div class="t m0 xc h6 ybd ff1 fs5 fc0 sc0 lsb ws0">as shown in Fig. 2. The token is used to indicate the length</div><div class="t m0 xc h6 ybe ff1 fs5 fc0 sc0 lsb ws0">of unmatched and matched characters. The literal length indi-</div><div class="t m0 xc h6 ybf ff1 fs5 fc0 sc0 lsb ws0">cates the length of uncompressed data and its value is equal to</div><div class="t m0 xc h6 yc0 ff1 fs5 fc0 sc0 lsb ws0">the value of the length of uncompressed data minus 15. The</div><div class="t m0 xc h6 yc1 ff1 fs5 fc0 sc0 lsf ws0">uncompressed data is stored as literals in the LZ4 sequence and</div><div class="t m0 xc h6 yc2 ff1 fs5 fc0 sc0 lsb ws0">it is copied from the original data. When the input data ﬁnds</div><div class="t m0 xc h6 yc3 ff1 fs5 fc0 sc0 lsb ws0">data that appeared before via searching, this data will be com-</div><div class="t m0 xc h6 yc4 ff1 fs5 fc0 sc0 lsb ws0">pressed. The value of the offset indicates the address of the</div><div class="t m0 xc h6 yc5 ff1 fs5 fc0 sc0 lsb ws0">current data minus the address of the prior data. Match length</div><div class="t m0 xc h6 yc6 ff1 fs5 fc0 sc0 ls11 ws0">means the length of the matching data.</div><div class="t m0 xe h6 yc7 ff1 fs5 fc0 sc0 lsb ws0">The operation of the LZ4 algorithm is mainly divided into</div><div class="t m0 xc h6 yc8 ff1 fs5 fc0 sc0 lsf ws0">the following ﬁve steps [14]: 1) hash computation; 2) match-</div><div class="t m0 xc h6 yc9 ff1 fs5 fc0 sc0 ls15 ws0">ing; 3) backward matching; 4) parameter calculation; and</div><div class="t m0 xc h6 yca ff1 fs5 fc0 sc0 lsb ws0">5) data output, which is shown in Fig. 3.</div><div class="t m0 x15 h6 ycb ff1 fs5 fc0 sc0 ls9 ws0">III. M</div><div class="t m0 x16 h6 ycc ff1 fs6 fc0 sc0 ls10 ws0">ODIFIED LZ4 ALGORITHM</div><div class="t m0 xe h6 ycd ff1 fs5 fc0 sc0 lsf ws0">An improved data format is proposed in this section along</div><div class="t m0 xc h6 yce ff1 fs5 fc0 sc0 lsf ws0">with an improved algorithm to solve the defects in the original</div><div class="t m0 xc h6 ycf ff1 fs5 fc0 sc0 lsb ws0">LZ4 algorithm.</div><a class="l" rel='nofollow' onclick='return false;'><div class="d m1"></div></a><a class="l" rel='nofollow' onclick='return false;'><div class="d m1"></div></a><a class="l" rel='nofollow' onclick='return false;'><div class="d m1"></div></a><a class="l" rel='nofollow' onclick='return false;'><div class="d m1"></div></a><a class="l" rel='nofollow' onclick='return false;'><div class="d m1"></div></a><a class="l" rel='nofollow' onclick='return false;'><div class="d m1"></div></a><a class="l" rel='nofollow' onclick='return false;'><div class="d m1"></div></a><a class="l" rel='nofollow' onclick='return false;'><div class="d m1"></div></a><a class="l" rel='nofollow' onclick='return false;'><div class="d m1"></div></a><a class="l" rel='nofollow' onclick='return false;'><div class="d m1"></div></a><a class="l" rel='nofollow' onclick='return false;'><div class="d m1"></div></a><a class="l" rel='nofollow' onclick='return false;'><div class="d m1"></div></a><a class="l" rel='nofollow' onclick='return false;'><div class="d m1"></div></a><a class="l" rel='nofollow' onclick='return false;'><div class="d m1"></div></a><a class="l" rel='nofollow' onclick='return false;'><div class="d m1"></div></a><a class="l" rel='nofollow' onclick='return false;'><div class="d m1"></div></a><a class="l" rel='nofollow' onclick='return false;'><div class="d m1"></div></a><a class="l" rel='nofollow' onclick='return false;'><div class="d m1"></div></a><a class="l" rel='nofollow' onclick='return false;'><div class="d m1"></div></a><a class="l" rel='nofollow' onclick='return false;'><div class="d m1"></div></a><a class="l" rel='nofollow' onclick='return false;'><div class="d m1"></div></a><a class="l" rel='nofollow' onclick='return false;'><div class="d m1"></div></a><a class="l" rel='nofollow' onclick='return false;'><div class="d m1"></div></a><a class="l" rel='nofollow' onclick='return false;'><div class="d m1"></div></a><a class="l" rel='nofollow' onclick='return false;'><div class="d m1"></div></a><a class="l" rel='nofollow' onclick='return false;'><div class="d m1"></div></a></div><div class="pi" data-data='{"ctm":[1.568627,0.000000,0.000000,1.568627,0.000000,0.000000]}'></div></div>