基於RTL與OpenCL在FPGA上實現Reed-Solomon編碼加速器之效能與效率比較

簡易檢索 / 詳目顯示

回結果列表

研究生：	藍莉婷 Li-Ting Lan
論文名稱：	基於RTL與OpenCL在FPGA上實現Reed-Solomon編碼加速器之效能與效率比較 Implementation and Comparisons of Performance and Efficiency of RTL-based versus OpenCL-based FPGA Reed-Solomon Encoder Accelerator
指導教授：	林昌鴻 Chang-Hong Lin
口試委員:	林銘波 Ming-Bo Lin 沈中安 Chung-An Shen 洪崇凱 Chong-Kai Hong
學位類別：	碩士 Master
系所名稱：	電資學院 - 電子工程系 Department of Electronic and Computer Engineering
論文出版年：	2019
畢業學年度：	107
語文別：	英文
論文頁數：	58
中文關鍵詞：	Hadoop分散式文件系统、Reed-Solomon碼、現場可程式化邏輯閘陣列
外文關鍵詞：	HDFS, Open Computing Language (OpenCL)
相關次數：	點閱：311 下載：0
分享至:	分享至facebook 分享至twitter

查詢本校圖書館目錄查詢臺灣博碩士論文知識加值系統勘誤回報

上一筆

在Hadoop分散式文件系统(Hadoop Distributed File System, HDFS) [1]中使用Erasure Coding [3]可以提高儲存效率，同時保持傳統HDFS基於複製機制[2]之數據持久性。眾所周知，Reed-Solomon (RS)碼[4]是一種以特定大小的資料區塊為編碼單位的Erasure Code，主要用於同時修復數個錯誤，在數位通訊和儲存系統中具有廣泛的應用。然而，RS碼在解碼運算具高複雜度並且耗費大量運算資源。過去已經有一些研究提出，在現場可程式化邏輯閘陣列(FPGA)上實現RS碼來加速並提高其處理的吞吐量。在本論文中，我們基於RTL和OpenCL，在FPGA上實現並加速RS編碼器的演算法，並比較其效能和效率的差別。基於使用Intel® ISA-L [10]實現的Erasure Code，我們選擇實現RS(10,4)編碼器以獲得更高的吞吐量。我們詳細解釋了使用FPGA來實現基於RTL和OpenCL的開發過程和設計流程。而為了提高性能，我們將演算法分為多個步驟，並以多核心或多引擎實現並行化數據處理。我們的設計採用Intel® Arria® 10GX FPGA來實現。在實驗結果中，基於RTL的RTL-16C和RTL-32C兩種設計，其吞吐量達到6.24 GB/s和6.69 GB/s，而基於OpenCL的OpenCL-2E和OpenCL-4E兩種設計，其吞吐量達到3.39 GB/s和6.38 GB/s。使用基於Intel® ISA-L實現的RS碼，以單執行緒在Intel® Core i5-7400 CPU上運行的吞吐量僅為0.03 GB/s。結果表明，我們實現的吞吐量優於之前基於Intel® ISA-L實現的吞吐量約209倍。

Using Erasure Coding [3] in Hadoop Distributed File System (HDFS) [1] can improve storage efficiency while still provides data persistence similar to traditional replication-based [2] HDFS. Reed-Solomon (RS) code [4] is a well-known erasure code, which is a family of block-based error correcting codes with a wide range of applications in digital communications and storage, designed to correct multiple errors. However, the RS code is considered to be computationally expensive. Some previous works implemented the algorithm on Field Programmable Gate Arrays (FPGAs), in order to accelerate the RS encoding and increase processing throughput. In this thesis, we implement and accelerate the RS encoder algorithm by using RTL-based and OpenCL-based FPGAs and compare the performance and efficiency. Based on the Intel® ISA-L [10] implementation of erasure coding, we chose to implement the RS(10,4) encoder for higher throughput. We explain in detail the development process and design flow for RTL-based and OpenCL-based FPGA implementations. To improve performance, we divide the algorithm into multiple steps and implement multi-core or multi-engine to parallelize the data processing. Our designs are implemented on Intel® Arria® 10GX FPGAs. In the experimental results, our RTL-based RTL-16C and RTL-32C throughputs reached 6.24 GB/s and 6.69 GB/s, while OpenCL-based OpenCL-2E and OpenCL-4E throughputs reached 3.39 GB/s and 6.38 GB/s. The throughput of the single-threaded code based on Intel® ISA-L erasure code running on the Intel® Core i5-7400 CPU is only 0.03 GB/s. The results show that we achieve a throughput that is 209x better than the previous Intel® ISA-L based throughput.

摘要 I
ABSTRACT II
致謝 III
LIST OF CONTENTS IV
LIST OF FIGURES VI
LIST OF TABLES VII
CHAPTER 1    INTRODUCTION 1
1.1    Motivations 1
1.2    Contributions 3
1.3    Thesis Organizations 4
CHAPTER 2    RELATED WORKS 5
2.1    HDFS Erasure Coding 5
2.2    RS Encoder Algorithm 7
2.3    Previous Works Implemented RS 10
CHAPTER 3    HARDWARE IMPLEMENTATION 12
3.1    RTL Implementation 12
3.1.1   Design Flow 12
3.1.2   Architecture 13
3.1.3   DDR RW Controller Module 15
3.1.4   Register Controller Module 17
3.1.5   Data Mux In Module 18
3.1.6   Encoder Module 19
3.1.7   Data Mux Out Module 22
3.2    OpenCL Implementation 23
3.2.1   Design Flow 23
3.2.2   Architecture 25
3.2.3   Data Dispatcher Kernel 26
3.2.4   Encoder Kernel 28
3.2.5   Optimization of OpenCL Kernel 29
CHAPTER 4    EXPERIMENTAL RESULTS 32
4.1    Resource Utilization 33
4.2    Execution Time and Throughput 34
4.2.1   RTL Designs 34
4.2.2   OpenCL Designs 38
4.3    Comparing with Previous Works 40
CHAPTER 5    CONCLUSIONS 43
REFERENCES 45
                                

[1] K. Shvachko, H. Kuang, S. Radia and R. Chansler, “The Hadoop Distributed File System,” 2010 IEEE 26th Symposium on Mass Storage Systems and Technologies (MSST), Incline Village, NV, 2010, pp. 1-10.
[2] H. Weatherspoon, J. D. Kubiatowicz, “Erasure coding vs. replication: A quantitiative comparison,” Revised Papers from the First International Workshop on Peer-to-Peer Systems (IPTPS ’01), p.328-338, March 07-08, 2002.
[3] J. S. Plank, “Erasure codes for storage systems: A brief primer,” Login: The USENIX Magazine, vol. 38, no. 6, pp. 44-50, December 2013.
[4] I.S. Reed and G. Solomon, “Polynomial Codes over Certain Finite Fields,” Journal of the Society for Industrial and Applied Mathematics, Vol. 8, pp. 300-304, 1960.
[5] J. S. Plank, K. M. Greenan, E. L. Miller, “Screaming Fast Galois Field Arithmetic Using Intel SIMD Instructions,” 11th USENIX Conference on File and Storage Technologies (FAST ’13), 2013.
[6] M. L. Curry, A. Skjellum, H. L. Ward, R. Brightwell, “Gibraltar: A Reed-Solomon coding library for storage applications on programmable graphics processors,” Concurrency and Computation: Practice and Experience, vol. 23, no. 18, pp. 2477-2495, 2011.
[7] X. Chu, C. Liu, K. Ouyang, L. S. Yung, H. Liu and Y. Leung, “PErasure: A parallel Cauchy Reed-Solomon coding library for GPUs,” 2015 IEEE International Conference on Communications (ICC), London, 2015, pp. 436-441.
[8] A. Azad and M. Shahed, “A Compact and Fast FPGA based Implementation of Encoding and Decoding Algorithm Using Reed Solomon Codes,” International Journal of Future Computer and Communication, Vol. 3, No. 1, February 2014.
[9] G. Chen, H. Zhou, X. Shen, J. Gahm, N. Venkat, S. Booth and J. Marshall, “OpenCL-Based Erasure Coding on Heterogeneous Architectures,” 2016 IEEE 27th International Conference on Application-specific Systems, Architectures and Processors (ASAP), London, 2016, pp. 33-40.
[10] “Intel® Intelligent Storage Acceleration Library (Open Source): https://01.org/zh/intel%C2%AE-storage-acceleration-library-open-source-version?langredirect=1,” [Online].
[11] “The Apache Software Foundation: HDFS Erasure Coding: https://hadoop.apache.org/docs/r3.1.2/hadoop-project-dist/hadoop-hdfs/HDFSErasureCoding.html,” [Online].
[12] “The Apache Software Foundation: Apache Hadoop: https://hadoop.apache.org/,” [Online].
[13] P. Corbett, B. English, A. Goel, T. Grcanac, S. Kleiman, J. Leong, S. Sankar, “Row-diagonal parity for double disk failure correction,” 3rd USENIX Conference on File and Storage Technologies (FAST ’04), 2004.
[14] L. Xu and J. Bruck, “X-code: MDS array codes with optimal encoding,” IEEE Transactions on Information Theory, vol. 45, no. 1, pp. 272-276, Jan. 1999.
[15] C. Huang and L. Xu, “STAR : An Efficient Coding Scheme for Correcting Triple Storage Node Failures,” IEEE Transactions on Computers, vol. 57, no. 7, pp. 889-901, July 2008.
[16] C. Wu, X. He, G. Wu, S. Wan, X. Liu, Q. Cao, C. Xie, “HDP code: A Horizontal-Diagonal Parity Code to Optimize I/O load balancing in RAID-6,” 2011 IEEE/IFIP 41st International Conference on Dependable Systems & Networks (DSN), Hong Kong, 2011, pp. 209-220.
[17] C. Wu, S. Wan, X. He, Q. Cao and C. Xie, “H-Code: A Hybrid MDS Array Code to Optimize Partial Stripe Writes in RAID-6,” 2011 IEEE International Parallel & Distributed Processing Symposium, Anchorage, AK, 2011, pp. 782-793.
[18] Z. Shen and J. Shu, “HV Code: An All-Around MDS Code to Improve Efficiency and Reliability of RAID-6 Systems,” 2014 44th Annual IEEE/IFIP International Conference on Dependable Systems and Networks, Atlanta, GA, 2014, pp. 550-561.
[19] D. Ford, F. Labelle, F. I. Popovici, M. Stokely, V.-A. T. L. Barroso, C. Grimes, and S. Quinlan, “Availability in globally distributed storage systems,” 9th USENIX Symposium on Operating Systems Design and Implementation (OSDI '10), 2010.
[20] M. Sathiamoorthy, M. Asteris, D. Papailiopoulos, A. G. Dimakis, R. Vadali, S. Chen, and D. Borthakur, “XORing Elephants: Novel Erasure Codes for Big Data,” 39th International Conference on Very Large Data Bases (VLDB), vol. 6, no. 5, pp. 325-336, Mar. 2013.
[21] J. K. Omura, J. L. Massey, “Computational method and apparatus for finite field arithmetic,” US Patent Number 4,587,627, May 1986.
[22] J. Lacan and J. Fimes, “Systematic MDS erasure codes based on Vandermonde matrices,” IEEE Communications Letters, vol. 8, no. 9, pp. 570-572, Sept. 2004.
[23] J. Blomer, M. Kalfane, M. Karpinski, R. Karp, M. Luby, and D. Zuckerman, “An XOR-based erasure-resilient coding scheme,” Tech. Rep. TR-95-048, The International Computer Science Institute, Berkeley, CA, August 1995.
[24] Z. Zhang, A. Wang, K. Zheng, Uma Maheswara G., and Vinayakumar B, “Introduction to HDFS Erasure Coding in Apache Hadoop: https://blog.cloudera.com/blog/2015/09/introduction-to-hdfs-erasure-coding-in-apache-hadoop/,” September 23, 2015, [Online].
[25] “IEEE Standard for System Verilog--Unified Hardware Design, Specification, and Verification Language: https://standards.ieee.org/standard/1800-2017.html,” 1800-2017, [Online].
[26] Khronos® OpenCL Working Group, “The OpenCL Specification: https://www.khronos.org/registry/OpenCL/specs/2.2/html/OpenCL_API.html,” May 12, 2018, [Online].
[27] “ModelSim*-Intel® FPGA Edition Software: https://www.intel.com/content/www/us/en/software/programmable/quartus-prime/model-sim.html,” [Online].
[28] “Intel® Quartus® Prime Pro Edition Software: https://www.intel.com.tw/content/www/tw/zh/software/programmable/quartus-prime/download.html,” [Online].
[29] “Timing Analyzer Quick Start Tutorial: https://www.intel.com/content/dam/www/programmable/us/en/pdfs/literature/hb/qts/ug_tq_tutorial.pdf,” [Online].
[30] “Intel® Intelligent Storage Acceleration Library (ISA-L) Source: https://github.com/intel/isa-l,” [Online].
[31] “Intel® FPGA SDK for OpenCL Software Technology: https://www.intel.com.tw/content/www/tw/zh/software/programmable/sdk-for-opencl/overview.html,” [Online].
[32] “Intel® FPGA SDK for OpenCL Pro Edition: Programming Guide: https://www.intel.com/content/www/us/en/programmable/documentation/mwh1391807965224.html,” [Online].
[33] “Intel® FPGA SDK for OpenCL Pro Edition: Best Practices Guide: https://www.intel.com/content/www/us/en/programmable/documentation/mwh1391807516407.html,” [Online].

全文公開日期 2024/07/24 (校內網路)
全文公開日期本全文未授權公開 (校外網路)
全文公開日期本全文未授權公開 (國家圖書館：臺灣博碩士論文系統)

簡易檢索 / 詳目顯示

相關論文