Abstract
In order to treat BigData efficiently, the communication speed of the inter or the intra data path equipped on high performance computing systems that needs to treat BigData management has been reaching to very high speed. In spite of fast increasing of the BigData, the implementation of the data communication path has become complex due to the electrical difficulties such as noises, crosstalks and reflections of the high speed data connection via a single cupper-based physical wire. This paper proposes a novel hardware solution to implement it by applying a stream-based data compression algorithm called the LCA-DLT. The compression algorithm is able to treat continuous data stream without exchanging the symbol lookup table among the compressor and the decompressor. The algorithm includes a dynamic frequency management of data patterns. The management is implemented by a dynamic histogram creation optimized for hardware implementation. When the dedicated communication protocol is combined with the LCA-DLT, it supports remote data migration among the computing systems. This paper describes the algorithm design and its hardware implementation of the LCA-DLT, and also shows the compression performance including the required hardware resources.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Apostolico, A., Lonardi, S.: Off-line compression by greedy textual substitution. Proc. IEEE 88(11), 1733–1744 (2000)
Grossi, R., Gupta, A., Vitter, J.S.: High-order Entropy-compressed Text Indexes. In: Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms / SODA 2003, pp. 841–850. ACM (2003)
Jacobson, G.: Space-efficient static trees and graphs. In: Proceedings of 30th IEEE Annual Symposium on Foundations of Computer Science, pp. 549–554. IEEE (1989)
Karp, R.M., Shenker, S., Papadimitriou, C.H.: A simple algorithm for finding frequent elements in streams and bags. ACM Trans. Database Syst. 28(1), 51–55 (2003)
Kieffer, J., Hui Yang, E.: Grammar-based codes: a new class of universallossless source codes. IEEE Trans. Inf. Theor. 46(3), 737–754 (2000)
Kuon, I., Rose, J.: Measuring the gap between FPGAs and ASICs. IEEE Trans. Comput. Aided Des. Integr. Circ. Syst. 26(2), 203–215 (2007)
Larsson, N., Moffat, A.: Offline dictionary-based compression. In: Proceedings of Data Compression Conference (DCC 1999), pp. 296–305. IEEE, March 1999
Manku, G.S., Motwani, R.: Approximate frequency counts over data streams. In: Proceedings of the 28th International Conference on Very Large Data Bases, pp. 346–357. VLDB Endowment (2002)
Maruyama, S., Sakamoto, H., Takeda, M.: An online algorithm for lightweight grammar-based compression. Algorithms 5(2), 214–235 (2012)
Metwally, A., Agrawal, D., Abbadi, A.E.: An integrated efficient solution for computing frequent and top-k elements in data streams. ACM Trans. Database Syst. 31(3), 1095–1133 (2006)
Nevill-Manning, C.G., Witten, I.H.: Identifying hierarchical structure in sequences: A linear-time algorithm. J. Artif. Intell. Res. 7(1), 67–82 (1997)
Vitter, J.S.: Design and analysis of dynamic huffman codes. J. ACM 34(4), 825–845 (1987)
Yamagiwa, S., Aoki, K., Wada, K.: Performance enhancement of inter-cluster communication with software-based data compression in link layer. Proc. IASTED PDCS 2005, 325–332 (2005)
Ziv, J., Lempel, A.: A universal algorithm for sequential data compression. IEEE Trans. Inf. Theor. 23(3), 337–343 (1977)
Ziv, J., Lempel, A.: Compression of individual sequences via variable-rate coding. IEEE Trans. Inf. Theor. 24(5), 530–536 (1978)
Acknowledgment
This work is partially supported by JSPS KAKENHI Grant Number 15H02674, 26280088 and JST CREST.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer International Publishing Switzerland
About this paper
Cite this paper
Yamagiwa, S., Marumo, K., Sakamoto, H. (2016). Stream-Based Lossless Data Compression Hardware Using Adaptive Frequency Table Management. In: Zhan, J., Han, R., Zicari, R. (eds) Big Data Benchmarks, Performance Optimization, and Emerging Hardware. BPOE 2015. Lecture Notes in Computer Science(), vol 9495. Springer, Cham. https://doi.org/10.1007/978-3-319-29006-5_11
Download citation
DOI: https://doi.org/10.1007/978-3-319-29006-5_11
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-29005-8
Online ISBN: 978-3-319-29006-5
eBook Packages: Computer ScienceComputer Science (R0)