A framework for cost based optimization of hybrid CPU/GPU query plans in database systems

• Autorzy: Bress S. , Geist I. , Schallehn E. , Mory M. , Saake G.
• Języki publikacji: EN

Abstrakty

EN

Current database research identified the use of computational power of GPUs as a way to increase the performance of database systems. As GPU algorithms are not necessarily faster than their CPU counterparts, it is important to use the GPU only if it is beneficial for query processing. In a general database context, only few research projects address hybrid query processing, i.e., using a mix of CPU- and GPU-based processing to achieve optimal performance. In this paper, we extend our CPU/GPU scheduling framework to support hybrid query processing in database systems. We point out fundamental problems and propose an algorithm to create a hybrid query plan for a query using our scheduling framework. Additionally, we provide cost metrics, accounting for the possible overlapping of data transfers and computation on the GPU. Furthermore, we present algorithms to create hybrid query plans for query sequences and query trees.

• Wydawca: Systems Research Institute, Polish Academy of Sciences
• Czasopismo: Control and Cybernetics
• Rocznik: 2012
• Tom: Vol. 41, no. 4
• Strony: 715--742
• Opis fizyczny: Bibliogr. 46 poz., il.

Twórcy

autor

Bress S.

• Otto-von-Guericke University Magdeburg, Universitätsplatz 2, D-39106 Magdeburg

autor

Geist I.

• Otto-von-Guericke University Magdeburg, Universitätsplatz 2, D-39106 Magdeburg

autor

Schallehn E.

• Otto-von-Guericke University Magdeburg, Universitätsplatz 2, D-39106 Magdeburg

autor

Mory M.

• Otto-von-Guericke University Magdeburg, Universitätsplatz 2, D-39106 Magdeburg

autor

Saake G.

• Otto-von-Guericke University Magdeburg, Universitätsplatz 2, D-39106 Magdeburg

Bibliografia

• 1. AKDERE, M. and CETINTEMEL, U. (2012) Learning-basedQuery PerformanceModeling and Prediction. International Conference on Data Engineering (ICDE). IEEE, 390–401.
• 2. AMD CORPORATION (2011) AMD Accelerated Parallel Processing OpenCL Programming Guide, rev1.3f edition, Dec 2011.
• 3. ANDRZEJEWSKI, W. and WREMBEL, R. (2010) GPU-WAH: ApplyingGPUs to Compressing Bitmap Indexes with Word Aligned Hybrid. In International Conferences on Database and Expert Systems Applications: Part II (DEXA (2)). Springer, 315–329.
• 4. AUGONNET, C., THIBAULT, S., NAMYST, R. and WACRENIER, P.A. (2011) StarPU: a unified platform for task scheduling on heterogeneous multicore architectures. Concurrency and Computation: Practice & Experience, 23(2), 187–198.
• 5. AUGUSTYN, D.R. and ZEDEROWSKI, S. (2012) ApplyingCUDA Technology in DCTBased Method of Query Selectivity Estimation. In: Second ADBIS workshop on GPUs In Databases (GID), Springer, 3–12.
• 6. BAGHSORKHI, S.S., DELAHAYE, M., PATEL, S.J., GROPP, W.D. and HWU, W.M.W. (2010) An Adaptive Performance Modeling Tool for GPU Architectures. SIGPLAN Not.,, 45, 105–114.
• 7. BAKKUM, P. and SKADRON, K. (2010) Accelerating SQL database operations on a GPU with CUDA. In: 3rdWorkshop on General-PurposeComputation onGraphics Processing Units, GPGPU ’10, ACM, 94–103.
• 8. BEIER, F., KILIAS, T. and SATTLER, K.U. (2012) GiST Scan Acceleration using Coprocessors. In: Eighth Internationl Workshop on Data Management on New Hardware, DaMoN’12, ACM, 63–69.
• 9. BREß, S., BEIER, F., RAUHE, H., SCHALLEHN, E., SATTLER, K.U. and SAAKE, G. (2012) Automatic Selection of Processing Units for Coprocessing in Databases. In: 16th East-European Conference on Advances in Databases and Information Systems (ADBIS), Springer, 57–70.
• 10. BREß, S., MOHAMMAD, S. and SCHALLEHN, E. (2012) Self-TuningDistribution of DB-Operations on Hybrid CPU/GPU Platforms. In: Grundlagen von Datenbanken (GvD), CEUR-WS, 89–94.
• 11. BREß, S., SCHALLEHN, E. and GEIST, I. (2012) Towards Optimization of Hybrid CPU/GPU query Plans in Database Systems. In: Second ADBIS workshop on GPUs In Databases (GID), Springer, 27–35.
• 12. CHAUDHURI, S. (1998) An Overview of Query Optimization in Relational Systems. In: Symposium on Principles of Database Systems (PODS), ACM, 34–43.
• 13. DIAMOS, G., WU, H., LELE, A., WANG, J. and YALAMANCHILI, S. (2012) Efficient Relational Algera Algorithms and Data Structures for GPU. Technical report, Center for Experimental Research in Computer Systems (CERS).
• 14. FANG, W., HE, B. and LUO., Q. (2010) Database Compression on Graphics Processors. Proceedings of the VLDB Endowment (PVLDB), 3, 670–680.
• 15. GAROFALAKIS, M.N. and IOANNIDIS, Y. (1997) ParallelQuery Scheduling andOptimization with Time- and Space-Shared Resources. In: 3rd International Conference on Very Large Data Bases, VLDB’97. Morgan Kaufmann Publishers Inc., 296–305.
• 16. GETOOR, L., TASKAR, B. and KOLLER, D. (2001) Selectivity estimation using probabilistic models. In: International Conference on Management of Data, SIGMOD’ 06, ACM, 325–336.
• 17. GOVINDARAJU, N., GRAY, J., KUMAR, R. and MANOCH, D. (2006) GPUTeraSort: High Performance Graphics Coprocessor Sorting for Large Database Management. In: SIGMOD International Conference on Management of Data, SIGMOD’ 06, ACM, 325–336.
• 18. GOVINDARAJU, N.K., LLOYD, B., WANG, W., LIN, M. and MANOCHA, D. (2004) Fast Computation of Database Operations using Graphics processors. SIGMOD International Conference on Management of Data, SIGMOD ’04, pages 215–226. ACM.
• 19. GREGG, C. and HAZELWOOD, K. (2010) Where is the data? Why You Cannot Debate CPU vs. GPU Performance without the Answer. In: Proceedings of the IEEE International Symposium on Performance Analysis of Systems and Software, ISPASS’11, IEEEE, 134–144.
• 20. HASAN, W., FLORESCU, D. and VALDURIEZ, P. (1996) Open Issues in ParallelQuery Optimization. SIGMOD Record, 25(3), 28–33.
• 21. HE, B., LU, M., YANG, K., FANG, K., GOVINDARAJU, N.K., Luo, Q. and SANDER, P.V. (2009) RelationalQuery Coprocessing on Graphics Processors. ACMTrans. Database Syst., 34(21),1–21(39).
• 22. HE, B., YANG, K., FANG, R., LU, M., GOVINDARAJU, N., Luo, Q. and SANDER, P. (2008) Relational Joins on Graphics Processors. In SIGMOD International Conference on Management of Data, SIGMOD ’08, ACM, 511–524.
• 23. HE, B., and YU, J.X (2011) High-ThrouhputTransaction Executions on Graphics Processors. Proceedings of the VLDB Endowment (PVLDB), 4(5), 314–325.
• 24. HEIMEL, M. and MARKL, V. (2012) A First Step Towars GPU-assisted Query Optimization. In: Third International Workshop on Accelerating Data Management Systems Using Modern Processor and Storage Architectures (ADMS’12). www.adams-conf.org/heimel_adms12.pgf.
• 25. HEIMEL, M. (2011) Investigating Query Optimization for a GPU-accelerated Database. Master’s thesis, Technische Universität Berlin, Electrical Engineering and Computer Science, Department of Software Engineering and Theoretical Computer Science.
• 26. HONG, S. and KIM, H. (2009) An Analytical Model for a GPU Architecutre with Memory-level and Thread-level Parallelism Awarness. SIGARCH Comput. Archit. News,, 37152–163.
• 27. HONG, W. and STONEBRAKER, M. (1993) Optimization of Parallel Query Execution Plans in XPRS. Distributed and Parallel Databases, 1(1), 9–32.
• 28. ILI´C, A., PRATAS, F., TRANCOSO, P. and SOUSA, L. (2011) High Performance Scientific Computing with Special Emphasis on Current Capabilities and Future Perspectives. In: High-Performance Computing on Heterogeneous Systems: Database Queries on CPU and GPU, IOS Press, 202-222.
• 29. ILI´C, A. and SOUSA, L. (2011) CHPS: An Environment for Collaborative Execution on Heterogeneous Desktop Systems. International Journal of Networking and Computing (IJNC), 1(1).
• 30. KALDEWEY, T., LOHMAN, G., MUELLER, R. and VOLK, P. (2012) GPU Join Processing Revisited. In: Eighth International Workshop on data Management on New Hardware, DaMoN’12, ACM, 55–62.
• 31. KERR, A., DIAMOS, G. and YALAMANCHILI, S. (2010) ModelingGPU-CPUWorkloads and Systems. In: 3rd Workshop on General-Purpose Computation on Graphics Processing Units, GPGPU ’10, ACM, 31–42.
• 32. KOTHAPALLI, K., MUKHERJEE, R., REHMAN, M.S., PATIDAR, S., Narayanan, P.J. and SRINATHAN, K. (2009) A Perfromance Prediction Model for the CUDA GPGPU Platform. In: International Conference on High Performance Computing (HiPC), IEEE, 463–472.
• 33. KIRKELLAS, M., CINTRA, M. and VIGLAS, S. (2010) Scheduling threads for ibntraquery parallelism on multicore processors. Technical Report EDI-INFR-RR-1345, University oof Edinburgh, School of informatics, http://www.inf.ed.ac.uk/ publications/report/1345.html.
• 34. LANZELOTTE, R.S.G., VALDURIEZ, P., ZAÏT and ZIANE, M. (1994) Invited Project review: Industrial-strength parallel query optimization: issues and lessons. Inf. Syst., 19(4), 311–330.
• 35. LAUER, T., DATTA, A., KHADIKOV, Z. and ANSELM, C. (2010) ExploringGraphics Processing Units as Parallel Coprocessors for Online Aggregation. In: International Workshop on Data warehousing and OLAP, DOLAP’10, ACM, 77–84.
• 36. MATSUNAGA, A. and FORTES, J.A.B. (2010) . On the Use of Machine Learning to Predict the Time and Resources Consumed by Applications. In: International Conference on Cluster Cloud and Grid Computing, 495–504. IEEE.
• 37. MOUSSALI, R., HALSTEAD, R., SAOOLUM, M., NAJJAR, W. and TSOTRAS, V.J. (2011) Efficient XML Path Filtering Using GPUs. In: VLDB-Workshop on Acelerating Data Management Systems Using Modern Processor and Storage Architecutres (ADMS). www.adams-conf.org/p9-MOUSSALLI.pdf.
• 38. NIVIDIA (2012) NVIDIA CUDA C ProgrammingGuide. http://developer.download. nvidia.com/compute/DevZone/docs/html/C/doc/CUDA_C_Programming_ Guide.pdf, 30–34, Version 4.0, [Online; accessed 1-May-2012].
• 39. PIRK, H. (2012) Efficient Cross-Device Query Processing. Proceedings of the VLDB Endowment.
• 40. PIRK, H., MANEGOLD, S. and KERSTEN, M. (2011) Accelerating Foreign-Key Joins using Asymmetric Memory Channels. In: VLDB - Workshop on Accelerating Data Management Systems Using Modern Processor and Storage Architectures (ADMS). VLDB Endowment, 585–597.
• 41. PIRK, H., SELLAM, T., MANEGOLD, S. and KERSTEN, M. (2012) X-Device Query Processing by Bitwise Distribution. In: Proceedings of the Eighth International Workshop on Data Management on New Hardware, DaMoN ’12, 48–54. ACM.
• 42. SANDERS, J. and KANDROT, E. (2010) CUDA by Example: An Introduction to General-Purpose GPU Programming. Addison-Wesley Professional, 1st edition.
• 43. SCHAA, D. and KAELI, D. (2009) Exploring the Multiple-GPU Desing Space. In: International Symposiumon Parallel& Distributed Processing, IPDPS’09. IEEE, 1–12.
• 44. WALKOWIAK, S., WAWRUCH, K., NOWOTKA, M., LIGOWSKI, L. and RUDNICKI, W. (2010) Exploring Utilisation of GPU for Database Applications. Procedia Computer Science, 1(1), 505–513.
• 45. ZHANG, N., HAAS, P.J., JOSIFOVSKI, V., LOHMAN, G.M. and ZHANG, C. (2005) Statistical Learning Techniques for Costing XML Queries. In: International Conference on Very Large Data Bases, VLDB ’05, VLDB Endowment, 289–300.
• 46. ZHANG, Y. and OWENS, J.D. (2011) A Quantitative PerformanceAnalysisModel for GPU Architectures. Computer Engineering, 382–393.