Efficiency evaluation of some compression methods for data transfer between main memory and Intel Xeon Phi coprocessors


  • P.S. Kostenetskiy
  • K.Yu. Besedin


database management systems
data compression
Intel Xeon Phi
LZSS compression
RLE compression
Null Suppression


The need to transfer data through a PCI-E (Peripheral Component Interconnect Express) bus is one of the key characteristics of GPU and multicore coprocessors programming, which is considered as a bottleneck for a number of applications. This paper focuses on evaluating the efficiency of data compression for optimizing the data transfer between main memory and Intel Xeon Phi for database applications. Three compression methods are evaluated: LZSS (Lempel-Ziv-Storer-Szymanski), Null Suppression, and RLE (Run-Length Encoding). An implementation of these methods for Intel Xeon Phi coprocessors is described. It is shown experimentally that these compression methods can be used to increase the efficiency of database processing under certain conditions imposed on the data under treatment. It is also shown that, when a compression method allows one to process data without decompression, such a processing procedure can additionally increase the efficiency of this method.





Section 1. Numerical methods and applications

Author Biographies

P.S. Kostenetskiy

K.Yu. Besedin


  1. Беседин К.Ю., Костенецкий П.С. Моделирование обработки запросов на гибридных вычислительных системах с многоядерными сопроцессорами и графическими ускорителями // Программные системы: теория и приложения. 2014. 5, № 1. 91-110.
  2. Беседин К.Ю., Костенецкий П.С. Применение многоядерных сопроцессоров в параллельных системах баз данных // Тр. Международной научной конференции «Параллельные вычислительные технологии» (ПаВТ’2013). 1-5 апреля 2013 г., Челябинск. Челябинск: Издательский центр ЮУрГУ, 2013. 583.
  3. Костенецкий П.С., Соколинский Л.Б. Моделирование иерархических многопроцессорных систем баз данных // Программирование. 2013. 39, № 1. 13-22.
  4. Костенецкий П.С. Обработка запросов на кластерных вычислительных системах с многоядерными ускорителями // Вестн. Южно-Уральского гос. ун-та. Серия: Вычислительная математика и информатика. 2012. № 2. 59-67.
  5. Костенецкий П.С., Лепихов А.В., Соколинский Л.Б. Технологии параллельных систем баз данных для иерархических многопроцессорных сред // Автоматика и телемеханика. 2007. № 5. 112-125.
  6. Abadi D.J., Madden S.R., Ferreira M.C. Integrating compression and execution in column-oriented database systems // Proc. ACM SIGMOD Int. Conf. on Management of Data. Chicago, USA. June 26-29, 2006. New York: ACM Press, 2006. 671-682.
  7. Abadi D.J., Madden S.R., Hachem N. Column-stores vs. row-stores: how different are they really? // Proc. ACM SIGMOD Int. Conf. on Management of Data. Vancouver, Canada. June 10-12, 2008. New York: ACM Press, 2008. 967-980.
  8. Binnig C., Hildenbrand S., Färber F. Dictionary-based order-preserving string compression for main memory column stores // Proc. ACM SIGMOD Int. Conf. on Management of Data Providence. Rhode Island, USA. June 29-July 2, 2009. New York: ACM Press, 2009. 283-296.
  9. Fang W., He B., Luo Q. Database compression on graphics processors // Proc. 36th Int. Conf. on Very Large Data Bases. Singapore. September 13-17, 2010. Singapore: VLDB Endowment, 2010. 670-680.
  10. Graefe G., Shapiro L.D. Data compression and database performance // Proc. ACM/IEEE-CS Symp. on Applied Computing. Kansas City, USA. April 3-5, 1991. New York: IEEE Press, 1991. 22-27.
  11. Iyer B.R., Wilhite D. Data compression support in databases // Proc. 20th Int. Conf. on Very Large Data Bases. Santiago de Chile, Chile. September 12-15, 1994. San Francisco: Morgan Kaufmann Publ., 1994. 695-704.
  12. Jeffers J., Reinders J. Intel Xeon Phi coprocessor high-performance programming. Waltham: Morgan Kaufmann Publ., 2013.
  13. Kirk D.B., Hwu W.W. Programming massively parallel processors: a hands-on approach. Waltham: Morgan Kaufmann Publ., 2013.
  14. Kostenetskiy P.S., Sokolinsky L.B. Analysis of hierarchical multiprocessor database systems // Proc. 2007 Int. Conf. on High Performance Computing, Networking and Communication Systems (HPCNCS-07). Orlando, USA. July 9-12, 2007. Tallahassee: ISRST, 2007. 245-251.
  15. Ng W.K., Ravishankar C.V. Block-oriented compression techniques for large statistical databases // IEEE Trans. on Knowledge and Data Engineering. 1997. 9, N 2. 314-328.
  16. Ozsoy A., Swany M. CULZSS: LZSS lossless data compression on CUDA // Proc. 2011 IEEE Int. Conf. on Cluster Computing. Washington, D.C., USA. September 26-30, 2011. New York: IEEE Press, 2011. 403-416.
  17. Roth M.A., van Horn S.J. Database compression // ACM SIGMOD Record. 1993. 22, N 3. 31-39.
  18. Storer J.A., Szymanski T.G. Data compression via textual substitution // Journal of the ACM. 1982. 29, N 4. 928-951.
  19. Wu L., Storus M., Cross D. Cs315a: final project CUDA WUDA SHUDA: CUDA compression project. Stanford: Stanford Univ., 2009.