臺灣博碩士論文加值系統

感測技術和網路的進步使得產生大數據成為可能，資料庫成為了支援搜尋和分析資料重要的儲存空間。隨著感測技術和網路的進步，大量的資料在資料庫中被產生和收集。急劇增加的資料量使得及時回應查詢要求成為一個巨大的挑戰。為了支援現今資料庫所需的高運算吞吐量，FPGA(場域可程式化邏輯閘陣列)被用來作為實現高吞吐量的資料庫查詢功能的高效加速平台。然而，和其他的可程式化處理器相比，FPGA繁瑣且耗時的設計流程是一個沉重的設計考量。以往FPGA上的加速器選擇資料庫一系列查詢操作中單一的運算(例如排序)來做加速。而寫死固定的硬體設計也使得FPGA對於支援不同查詢和操作上較沒有彈性。本篇論文提出一個可重新配置的加速器架構來支援端對端的查詢加速。我們提出針對不同資料處理操作的模組化的引擎，這個引擎可以針對不同的設計參數重新配置。資料處理模組按照不同運算階段分配，並且針對查詢要求組成並產生加速器架構。透過我們的系統化解決方案，FPGA上的加速器可以適應不同的查詢要求。透過TPC-DS的實驗，我們提出的架構比傳統的CPU解決方案快56.5%。和前人的FPGA設計相比，提出的加速器在總體性能上快23.8%，節省50.09% FPGA的資源使用。我們的實驗也顯示和固定設計相比，可重新配置的設計可以更有效率的適應不同查詢特徵並獲得30.1%的性能提升

Database has become an important repository to support search and analysis of a dataset. With the advances of sensing and networking technology, vast amount of data is being generated and collected in databases. The drastically growing volume of database has made the in-time query response a great challenge. To support the excessive processing throughput required by the modern big database, FPGA (Field Programmable Gate Array) has been adopted as an efficient acceleration platform to attain high throughput database queries. However, when compared with programmable processors, the cumbersome and time-consuming design process of FPGA becomes a serious design concern. Previous accelerators on FPGA chose to support only the single operator, such as sorting, along the series of operations in a database query. The hard-coded hardware design also makes FPGA inflexible to support different queries and operations. This thesis proposes a Reconfigurable Database Processor (RDP) to support end-to-end query acceleration. We introduce the modular engines for different data processing operations in queries. The engines can be reconfigured to support different design parameters. The data processing modules are allocated into stages, and composed to generated the accelerator structure for queries. RDP can be adapted to the requirements of different queries by applying our systematic solution. The experiments on the queries of TPC-DS, the proposed RDP has attained 56.5% over the conventional solution on CPU. When compared with the previous FPGA designs, RDP shows 23.8% advantage on the overall performance while saving 50.09% FPGA resources. We have also shown that the reconfigurable designs can more effectively adapt to the query characteristics and attain up to 30.1% performance gain when compared with a fixed design.

摘要 I
ABSTRACT II
誌謝 IV
Contents V
List of Figures VII
List of Tables VII
Chapter 1 Introduction 1
Chapter 2 Background and Related Works 6
2.1 Overview of query processing 6
2.2 Selection Stage 9
2.3 Join Stage 10
2.4 Aggregation Stage 12
2.5 Sorting Stage 13
2.6 Summary of Different Stages 14
Chapter 3 System architecture of Query Accelerator 15
3.1 Data Flow in TPC-DS Query 15
3.2 Overall Architecture 16
3.3 Controller 18
3.4 Comparator 19
3.5 Sorter 19
3.6 Selection Engine 21
3.7 Join Engine 23
3.8 Reconfigurable with Different Types of Queries 25
Chapter 4 Experimental Results 28
4.1 Simulation Model 28
4.2 SystemC Model 28
4.3 TPC-DS benchmark 29
4.4 Performance Comparison Between Different Accelerator 29
4.5 Resource Comparison Between Different Accelerator 32
4.6 Performance Comparison Between Different Queries 33
4.7 Support Reconfigurable Architecture 34
Chapter 5 Conclusions 36
References 37

[1] CJ Date, “An introduction to database systems”, Pearson Education, India ,1981
[2] Li Da Xu, Lian Duan, “Big data for cyber physical systems in industry 4.0: a survey”, Enterprise Information Systems, Volume 13, pp. 148-169, Mar 2018
[3] L. Zhang et al., "Visual analytics for the big data era — A comparative review of state-of-the-art commercial systems," 2012 IEEE Conference on Visual Analytics Science and Technology (VAST), Seattle, WA, 2012, pp. 173-182.
[4] Andrew McAfee and Erik Brynjolfsson, “Big data: the management revolution, Harvard Business review,” Harvard Business Review, R1210C, pp. 1-9, October 2012
[5] B. Sukhwani et al., "Database analytics acceleration using FPGAs," 2012 21st International Conference on Parallel Architectures and Compilation Techniques (PACT), Minneapolis, MN, 2012, pp. 411-420.
[6] Ran Rui et al., “Fast Equi-Join Algorithms on GPUs: Design and Implementation”, SSDBM '17: Proceedings of the 29th International Conference on Scientific and Statistical Database ManagementJune 2017, Article No.: 17, pp. 1–12
[7] M. Roozmeh and L. Lavagno, "Implementation of a performance optimized database join operation on FPGA-GPU platforms using OpenCL," 2017 IEEE Nordic Circuits and Systems Conference (NORCAS): NORCHIP and International Symposium of System-on-Chip (SoC), Linkoping, 2017, pp. 1-6.
[8] Jens Teubner and Louis Woods, Data processing on FPGAs, Morgans & Claypool publishers, 2013
[9] P. Papaphilippou and W. Luk, "Accelerating Database Systems Using FPGAs: A Survey," 2018 28th International Conference on Field Programmable Logic and Applications (FPL), Dublin, 2018, pp. 125-1255.
[10] Jian Fang et al., “In-memory database acceleration on FPGAs: a survey”, The VLDB Journal, 29, pp. 33–59, October 2019
[11] S. Jun, S. Xu and Arvind, "Terabyte Sort on FPGA-Accelerated Flash Storage," 2017 IEEE 25th Annual International Symposium on Field-Programmable Custom Computing Machines (FCCM), Napa, CA, 2017, pp. 17-24.
[12] S. Haas et al., "A database accelerator for energy-efficient query processing and optimization," 2016 IEEE Nordic Circuits and Systems Conference (NORCAS), Copenhagen, 2016, pp. 1-5.
[13] C. Dennl, D. Ziener and J. Teich, "On-the-fly Composition of FPGA-Based SQL Query Accelerators Using a Partially Reconfigurable Module Library," 2012 IEEE 20th International Symposium on Field-Programmable Custom Computing Machines, Toronto, ON, 2012, pp. 45-52.
[14] Z. Zhou, C. Yu, S. Nutanong, Y. Cui, C. Fu and C. J. Xue, "A Hardware-Accelerated Solution for Hierarchical Index-Based Merge-Join," in IEEE Transactions on Knowledge and Data Engineering, vol. 31, no. 1, pp. 91-104, 1 Jan. 2019.
[15] C. Dennl, D. Ziener and J. Teich, "Acceleration of SQL Restrictions and Aggregations through FPGA-Based Dynamic Partial Reconfiguration," 2013 IEEE 21st Annual International Symposium on Field-Programmable Custom Computing Machines, Seattle, WA, 2013, pp. 25-28.
[16] Jian Ouyang, Wei Qi, Yong Wang, YichenTu, Jing Wang and Bowen Jia, "SDA: Software-Defined Accelerator for general-purpose big data analysis system," 2016 IEEE Hot Chips 28 Symposium (HCS), Cupertino, CA, 2016, pp. 1-23.
[17] M. Owaida, D. Sidler, K. Kara and G. Alonso, "Centaur: A Framework for Hybrid CPU-FPGA Databases," 2017 IEEE 25th Annual International Symposium on Field-Programmable Custom Computing Machines (FCCM), Napa, CA, 2017, pp. 211-218.
[18] Changkyu Kim et al., “Sort vs. Hash Revisited: Fast Join Implementation on Modern Multi-Core CPUs”, Proceedings of the VLDB Endowment, Volume 2, Issue 2, August 2009
[19] N. Faujdar and S. P. Ghrera, "A practical approach of GPU bubble sort with CUDA hardware," 2017 7th International Conference on Cloud Computing, Data Science & Engineering - Confluence, Noida, 2017, pp. 7-12.
[20] Woźniak M., et al., “Preprocessing Large Data Sets by the Use of Quick Sort Algorithm”, In: Skulimowski A., Kacprzyk J. (eds) Knowledge, Information and Creativity Support Systems: Recent Trends, Advances and Solutions. Advances in Intelligent Systems and Computing, vol 364. Springer, Cham
[21] Wojciech M Zabołotny "Dual port memory based Heapsort implementation for FPGA", Proc. SPIE 8008, Photonics Applications in Astronomy, Communications, Industry, and High-Energy Physics Experiments 2011, 80080E (6 October 2011)
[22] W. Song, D. Koch, M. Luján and J. Garside, "Parallel Hardware Merge Sorter," 2016 IEEE 24th Annual International Symposium on Field-Programmable Custom Computing Machines (FCCM), Washington, DC, 2016, pp. 95-102.
[23] X. Liu and Y. Deng, "Fast Radix: A Scalable Hardware Accelerator for Parallel Radix Sort," 2014 12th International Conference on Frontiers of Information Technology, Islamabad, 2014, pp. 214-219.
[24] K. E. Batcher, “Sorting networks and their applications”, AFIPS '68 (Spring): Proceedings of the April 30--May 2, 1968, spring joint computer conference, pp. 307–314
[25] Raghunath Othayoth Nambiar et al., “The making of TPC-DS”, VLDB '06: Proceedings of the 32nd international conference on Very large data bases, September 2006, pp. 1049–1058
[26] Fei-Fei Li. (2020, February 18). Next Generation Enterprise Cloud Native Distributed Database Systems
[Online]. Available: https://developer.aliyun.com/article/746466
[27] Philip Russom, “Big data analytics”, TDWI best practices report, fourth quarter, 2011
[28] AbdulsalamYassine et. al, “IoT big data analytics for smart homes with fog and cloud computing”, Future Generation Computer Systems, Volume 91, February 2019, pp. 563-573
[29] E. Monmasson and M. N. Cirstea, "FPGA Design Methodology for Industrial Control Systems—A Review," in IEEE Transactions on Industrial Electronics, vol. 54, no. 4, pp. 1824-1842, Aug. 2007
[30] W. Altoyan and J. J. Alonso, "Investigating Performance Losses in High-Level Synthesis for Stencil Computations," 2020 IEEE 28th Annual International Symposium on Field-Programmable Custom Computing Machines (FCCM), Fayetteville, AR, USA, 2020, pp. 195-203
[31] J. Lachmair, T. Mieth, R. Griessl, J. Hagemeyer and M. Porrmann, "From CPU to FPGA — Acceleration of self-organizing maps for data mining," 2017 International Joint Conference on Neural Networks (IJCNN), Anchorage, AK, 2017, pp. 4299-4308
[32] Singh, D., Reddy, C.K., “A survey on platforms for big data analytics.”, Journal of Big Data 2, 8 (2015).
[33] X. Chen and X. Lin, "Big Data Deep Learning: Challenges and Perspectives," in IEEE Access, vol. 2, pp. 514-525, 2014
[34] Haifeng Wang, “Duer: Intelligent Personal Assistant”, CIKM '16: Proceedings of the 25th ACM International on Conference on Information and Knowledge Management, October 2016, pp. 427
[35] J. Andreu-Perez, C. C. Y. Poon, R. D. Merrifield, S. T. C. Wong and G. Yang, "Big Data for Health," in IEEE Journal of Biomedical and Health Informatics, vol. 19, no. 4, pp. 1193-1208, July 2015
[36] Bates, D. W., Saria, S., Ohno-Machado, L., Shah, A. & Escobar, G. Big data in health care: using analytics to identify and manage high-risk and high-cost patients. Health Aff. 33, 1123–1131 (2014).
[37] Nguyen, H. (2008) GPU Gems 3. Addison-Wesley, Boston.
[38] Napoli, C., Pappalardo, G. and Tramontana, E. (2013) Using Modularity Metrics to Assist Move Method Refactoring of Large Systems. Proc. Int. Conf. Complex, Intelligent, and Software Intensive Systems (CISIS), Taichung, Taiwan, July 3–5, pp. 529–534. IEEE, Los Alamos.
[39] N. Devarajan, S. Navneeth and S. Mohanavalli, "GPU accelerated relational hash join operation," 2013 International Conference on Advances in Computing, Communications and Informatics (ICACCI), Mysore, 2013, pp. 891-896
[40] Oded Green, et. al, “GPU merge path: a GPU merging algorithm”, ICS '12: Proceedings of the 26th ACM international conference on Supercomputing, June 2012, pp. 331–340
[41] Jianting Zhang, et. al, “High-performance online spatial and temporal aggregations on multi-core CPUs and many-core GPUs”, DOLAP '12: Proceedings of the fifteenth international workshop on Data warehousing and OLAP, November 2012, pp. 89–96
[42] B. Romanous et al., "High-Performance Parallel Radix Sort on FPGA," 2020 IEEE 28th Annual International Symposium on Field-Programmable Custom Computing Machines (FCCM), Fayetteville, AR, USA, 2020, pp. 224-224, doi: 10.1109/FCCM48280.2020.00055.
[43] Nikola Samardzic, et. al, “Bonsai: High-Performance Adaptive Merge Tree Sorting”, ACM/IEEE International Symposium on Computer Architecture (ISCA), 2020
[44] Gorker Alp Malazgirt, et. al, “Accelerating Complete Decision Support Queries Through High-Level Synthesis Technology”, FPGA '15: Proceedings of the 2015 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays, February 2015, pp. 277
[45] TPC-DS [Online] http://www.tpc.org/tpcds/
[46] Information Technology - Database Language SQL, CMU
[47] Hongbo Zou, et. al, “FlexAnalytics: A Flexible Data Analytics Framework for Big Data Applications with I/O Performance Improvement”, Big Data Research, Volume 1, August 2014, pp. 4-13