A Bi-objective Optimization Framework for Heterogeneous CPU/GPU Query Plans

• Autorzy: Przymus P. , Kaczmarski K. , Stencel K.

Identyfikatory

DOI

10.3233/FI-2014-1136

• Języki publikacji: EN

Abstrakty

EN

Graphics Processing Units (GPU) have significantly more applications than just rendering images. They are also used in general-purpose computing to solve problems that can benefit from massive parallel processing. However, there are tasks that either hardly suit GPU or fit GPU only partially. The latter class is the focus of this paper. We elaborate on hybrid CPU/GPU computation and build optimization methods that seek the equilibrium between these two computation platforms. The method is based on heuristic search for bi-objective Pareto optimal execution plans in presence of multiple concurrent queries. The underlying model mimics the commodity market where devices are producers and queries are consumers. The value of resources of computing devices is controlled by supply-and-demand laws. Our model of the optimization criteria allows finding solutions of problems not yet addressed in heterogeneous query processing. Furthermore, it also offers lower time complexity and higher accuracy than other methods.

Słowa kluczowe

EN

heterogeneous environment; graphics processing unit; GPU; compute unified device architecture; CUDA; query processing

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2014
• Tom: Vol. 135, nr 4
• Strony: 483--501
• Opis fizyczny: Bibliogr. 17 poz., tab., wykr.

Twórcy

autor

Przymus P.

• Faculty of Mathematics and Computer Science, Nicolaus Copernicus University, Chopina 12/18, Torun, Poland

autor

Kaczmarski K.

• Faculty of Mathematics and Information Science, Warsaw University of Technology, Koszykowa 75, 00-662 Warszawa, Poland

autor

Stencel K.

• Institute of Informatics, Warsaw University, Banacha 2, 02-097 Warszawa, Poland

Bibliografia

• [1] W. Andrzejewski and R. Wrembel. Gpu-wah: applying gpus to compressing bitmap indexes with word aligned hybrid. In Database and Expert Systems Applications, pages 315–329. Springer, 2010.
• [2] J. Bentley. Programming pearls: algorithm design techniques. Commun. ACM, 27(9):865–873, Sept. 1984.
• [3] S. Breß, I. Geist, E. Schallehn, M. Mory, and G. Saake. A framework for cost based optimization of hybrid cpu/gpu query plans in database systems. Control and Cybernetics, pages 27–35, 2013.
• [4] S. Breß and G. Saake. Why it is time for a hype: a hybrid query processing engine for efficient gpu coprocessing in dbms. Proceedings of the VLDB Endowment, 6(12):1398–1403, 2013.
• [5] S. Breß, E. Schallehn, and I. Geist. Towards optimization of hybrid cpu/gpu query plans in database systems. In New Trends in Databases and Information Systems, pages 27–35. Springer, 2013.
• [6] R. Buyya, D. Abramson, J. Giddy, and H. Stockinger. Economic models for resource management and scheduling in grid computing. Concurrency and computation: practice and experience, 14(13-15):1507–1542, 2002.
• [7] W. Fang, B. He, and Q. Luo. Database compression on graphics processors. Proceedings of the VLDB Endowment, 3(1-2):670–680, 2010.
• [8] D. Florescu and D. Kossmann. Rethinking cost and performance of database systems. ACM Sigmod Record, 38(1):43–48, 2009.
• [9] R. T. Marler and J. S. Arora. Survey of multi-objective optimization methods for engineering. Structural and multidisciplinary optimization, 26(6):369–395, 2004.
• [10] K. Muller. Advanced systems simulation capabilities in simpy. Europython 2004, 2004.
• [11] C. H. Papadimitriou and M. Yannakakis. Multiobjective query optimization. In Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, pages 52–59. ACM, 2001.
• [12] P. Przymus and K. Kaczmarski. Improving efficiency of data intensive applications on gpu using lightweight compression. In On the Move to Meaningful Internet Systems: OTM 2012 Workshops - Lecture Notes in Computer Science, volume 7567, pages 3–12. Springer Berlin Heidelberg, 2012.
• [13] P. Przymus and K. Kaczmarski. Dynamic compression strategy for time series database using gpu. In New Trends in Databases and Information Systems. 17th East-European Conference on Advances in Databases and Information Systems September 1-4, 2013 - Genoa, Italy, 2013.
• [14] P. Przymus and K. Kaczmarski. Time series queries processing with gpu support. In New Trends in Databases and Information Systems. 17th East-European Conference on Advances in Databases and Information Systems September 1-4, 2013 - Genoa, Italy, 2013.
• [15] P. Przymus, K. Kaczmarski, and K. Stencel. A bi-objective optimization framework for heterogeneous cpu/gpu query plans. In CS&P 2013 Concurrency, Specification and Programming. Proceedings of the 22nd International Workshop on Concurrency, Specification and Programming, September 25-27, 2013 - Warsaw, Poland.
• [16] O. O. Sonmez and A. Gursoy. Comparison of pricing policies for a computational grid market. In Parallel Processing and Applied Mathematics, pages 766–773. Springer, 2006.
• [17] M. Stonebraker, P. M. Aoki, W. Litwin, A. Pfeffer, A. Sah, J. Sidell, C. Staelin, and A. Yu. Mariposa: a wide-area distributed database system. The VLDB Journal, 5(1):48–63, 1996.