Hardware Decompression Techniques for FPGA-Based Embedded Systems

ABSTRACT

In this work, we present hardware decompression accelerators for widening the bottleneck between slow nonvolatile memories on the one side and high-speed FPGA configuration interfaces and fast softcore CPUs on the other side. We discuss different compression algorithms suitable for a hardware accelerated decompression on FPGAs as well as on CPLDs. The algorithms will be investigated with respect to the achievable compression ratio, throughput, and hardware overhead. This leads to various decompressor implementations with one capable to decompress at high data rates of up to 400 megabytes per second under optimal conditions while only requiring slightly more than a hundred lookup tables. We will evaluate how these decompressors perform on configuration bitstreams for different FPGAs as well as for softcore CPU binaries.

REFERENCES

• 1: Altera Inc. 2007a. Enhanced configuration devices (EPC4, EPC8 & EPC16) data sheet.
• 2: Altera Inc. 2007b. Alera devices. www.altera.com/products/devices/dev-index.jsp.
• 3: Bobda, C., Majer, M., Ahmadinia, A., Haller, T., Linarth, A., and Teich, J. 2005. Increasing the flexibility in FPGA-Based reconfigurable platforms: The Erlangen slot machine. In Proceedings of the Conference on Field-Programmable Technology (FPT). 37--42.
• 4: Andreas Dandalis , Viktor K. Prasanna, Configuration compression for FPGA-based embedded systems, Proceedings of the 2001 ACM/SIGDA ninth international symposium on Field programmable gate arrays, p.173-182, February 2001, Monterey, California, United States [doi>10.1145/360276.360342]
• 5: Department of Computer Science 12. Bitstream Compression Benchmark http://www.reconets.de/bitstreamcompression/.
• 6: Scott Hauck , William D. Wilson, Runlength Compression Techniques for FPGA Configurations, Proceedings of the Seventh Annual IEEE Symposium on Field-Programmable Custom Computing Machines, p.286, April 21-23, 1999
• 7: Heun, V. 2003. Grund legende Algorithmen. Vieweg.
• 8: Hübner, M., Ullman, M., Weissel, F., and Becker, J. 2004. Real-time configuration code decompression for dynamic FPGA self-reconfigurations. In Proceedings of the 11th Reconfigurable Architectures Workshop (RAW’04).
• 9: Hübner, M., Ullman, M., Weissel, F., and Becker, J. 2005. Real-time configuration code decompression for dynamic FPGA self-reconfiguration: Evaluation and implementation. EURASIP J. Embed. Syst. 1, 11.
• 10: Huffman, D. A. 1952. A method for the construction of minimum-redundancy codes. Proc. IRE 40, 9, 1098--1101.
• 11: Dirk Koch , Jürgen Teich, Platform-independent methodology for partial reconfiguration, Proceedings of the 1st conference on Computing frontiers, April 14-16, 2004, Ischia, Italy [doi>10.1145/977091.977148]
• 12: Koch, D., Beckhoff, C., and Teich, J. 2007. Bitstream decompression for high speed FPGA configuration from slow memories. In Proceedings of International Conference on Field-Programmable Technology (ICFPT’07). IEEE, 161--168.
• 13: Koch, D., Körber, M., and Teich, J. 2006. Searching RC5-Keys with distributed reconfigurable computing. In Proceedings of International Conference on Engineering of Reconfigurable Systems and Algorithms (ERSA’06). CSREA Press, 42--48.
• 14: Zhiyuan Li , Scott Hauck, Don't Care discovery for FPGA configuration compression, Proceedings of the 1999 ACM/SIGDA seventh international symposium on Field programmable gate arrays, p.91-98, February 21-23, 1999, Monterey, California, United States [doi>10.1145/296399.296435]
• 15: Zhiyuan Li , Scott Hauck, Configuration Compression for Virtex FPGAs, Proceedings of the the 9th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, p.147-159, April 29-May 02, 2001 [doi>10.1109/FCCM.2001.19]
• 16: OpenCores. Opencores homepage. http://www.opencores.org.
• 17: Lei He , T. Mitra , Weng-Fai Wong, Configuration bitstream compression for dynamically reconfigurable FPGAs, Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design, p.766-773, November 07-11, 2004 [doi>10.1109/ICCAD.2004.1382679]
• 18: David Salomon, Data Compression, SpringerVerlag, 2004
• 19: James A. Storer , Thomas G. Szymanski, Data compression via textual substitution, Journal of the ACM (JACM), v.29 n.4, p.928-951, Oct. 1982 [doi>10.1145/322344.322346]
• 20: Wetekam, G. and Lutz, B. 2005. Hardware-Implementierung einer 3D-Huffman-Decodierung für dynamische Volumendaten. In Proceedings of the Hardware for Visual Computing Workshop.
• 21: Xilinx Inc. 2005. Virtex-II Platform FPGA User Guide. Xilinx.
• 22: Xilinx Inc. 2007a. Xilinx: Silicon devices. www.xilinx.com/products/silicon_solutions/.
• 23: Xilinx Inc. 2007b. Platform flash in-system programmable configuration PROMs.
• 24: Ziv, J. and Lempel, A. 1977. A universal algorithm for sequential data compression. IEEE Trans. Inform. Theory 23, 3, 337--343.

INDEX TERMS

Primary Classification:
  E. Data
  E.4 CODING AND INFORMATION THEORY
      Subjects: Data compaction and compression

General Terms:
Algorithms, Experimentation

Keywords:
Bitstream, configuration, reconfigurable computing