臺灣博碩士論文加值系統

近年來在電子商務和網路多媒體的蓬勃發展之下，RAID的高頻寬和高可靠度逐漸受到重視，而且VLSI的製程技術精進，使硬碟在可靠度上的需求大幅提昇。
在RAID相關研究之20年歷史，大多仍直接採用同位元檢查(Parity checking)的技術來進行一個已知錯(Erasure)或一顆硬碟失效除錯，若欲將抗錯能力提昇到二顆硬碟，以EVENODD碼為最佳的選擇[5][6]，但需要大量的Cache記憶體，而且複雜的解錯模式並不適合VLSI的實現。本論文提出以RS碼為理論基礎的解碼器供參考。
Reed-Solomon (RS)碼[12][13]有著優異的除錯能力，且不需大量的記憶體，但長期以來許多RAID抗錯的相關研究上，認為RS碼在解碼及編碼上是非常複雜[8]，本論文所提出的方法，在架構上簡化複雜的RS碼解碼過程[11]，解決小額存取(Small write)的問題[15]，並且進一步有效的VLSI化。同時，本論文研究的重點為採用Embedded System完成測試平台，並提供一個完整的高階網路多媒體檔案伺服器SoC的解決方案。

The RAID, with high throughput and reliability, is drawing more and more attention in the multimedia and network applications. With modem VLSI manufacture process and new HDD technology, the requirement of disk reliability is growing up.
In the passed 20 years, most error-free technique in RAID used parity check. This technique can solve one erasure or one disk failure problem. The ENENODD[5][6] is the first method to solve two-disks failure, but the recover mode is too complex to implement in VLSI. In addition, huge cache memory is required.
Reed-Solomon (RS) Codes[12][13] have the outstanding ability of error correction with little memory required. Many papers about error free of RAID tell us that the RS codes are very complex in coding and decoding[8]. In this thesis, we simplify the RS codes decoder[11] and solve the small write problem[15]. Those IPs provide transparent and real-time operation in system design. It’s more efficient to implement in VLSI and may support the SoC total solution in high-level internet-multimedia file server in the future.

ACKNOWLEDGEMENTS I
摘要 II
ABSTRACT III
LIST OF CONTENTS VI
LIST OF FIGURES VIII
LIST OF TABLES IX
CHAPTER 1 INTRODUCTION 1
1.1 Objectives 1
1.2 The Motivation 2
1.3 The Proposed Methods and Contributions 3
1.4 The Organization of Thesis 4
CHAPTER 2 THE BACKGROUND AND PAPER SURVEY 5
2.1 Background and History 5
2.2 The Definitions 6
2.3 The Parity Check 7
2.4 The Introduction of RAID0, 1, 10 and RAID5 9
2.4.1 The RAID0 9
2.4.2 The RAID1 10
2.4.3 The RAID10 11
2.4.4 The RAID5 11
2.5 The Recent Development of Advanced System 14
2.6 The Small Write Problem 14
CHAPTER 3 THE STUDY OF EVENODD CODE 16
3.1 Encoding 16
3.2 Decoding 19
3.2.1 One Erasure 19
3.2.2 Two Erasures 20
3.2.3 One Random Error 24
3.3 Summary 26
CHAPTER 4 THE DESIGN OF RS-CODES FOR ERROR AND ERASURE CORRECTION 28
4.1 Galois Filed 28
4.2 The RS Codes Encoder 31
4.3 The RS Codes Decoder 32
4.3.1 The Syndrome Evaluation Algorithm 33
4.3.2 Peterson-Gorenstein-Zierler Algorithm 34
4.4 The Design of Fast Error and Erasure Correction Algorithm 36
4.4.1 The Design of Single Random Error Correction 36
4.4.2 The Design of Single or Double Erasure Correction 39
4.5 The Problem in RS Codes Encoder 41
CHAPTER 5 THE DESIGN OF RS CODES FOR SMALL WRITE MODULE 43
5.1 Introduction 43
5.2 The Proposed Algorithm of Small Write Encoder 44
5.3 Summary 47
CHAPTER 6 THE PROPOSED RS-RAID SYSTEM 48
6.1 Introduction 48
6.2 System Design 48
6.3 System Operation 51
6.3.1 The System Level 51
6.3.2 The Disk Level 53
CHAPTER 7 THE SYSTEM IMPLEMENTATION 55
7.1 The Error/Erasure Module 55
7.2 The Small Write Module 58
CHAPTER 8 SYSTEM PERFORMANCE AND ANALYSIS 61
8.1 Memory Access 61
8.1.1 EVENODD Code 62
8.1.2 RS codes 66
8.1.3 Summary 66
8.2 Small Write 70
8.2.1 EVENODD 71
8.2.2 Improved EVENODD 72
8.2.3 RS codes 73
8.2.4 Summary 73
CHAPTER 9 THE CONCLUSIONS AND FUTURE WORK 74
9.1 Conclusions 74
9.2 Future Work 75
REFERENCE 77
PUBLICATION LIST 79
APPENDIX 80
I. Test Bed Specification 80
Architecture 80
Data Flow Diagram 81
Codec Specification 81
SRAM Allocation 81
System Commands 82
Disk Commands 82
II. RS-RAID System Circuits Diagram 83
III. System-Level Circuits Diagram 84
IV. Disk-Level Circuits Diagram 85

[1] Patterson D.A., Chen P., Gibson G. and Katz R.H.: “Introduction to redundant arrays of inexpensive disks (RAID)”, COMPCON Spring '89. Thirty-Fourth IEEE Computer Society International Conference: Intellectual Leverage, Digest of Papers, 1989, Page(s): 112-117.
[2] Hua K.A., Khanh Vu and Ta-Hsiung Hu: “Improving RAID performance using a multibuffer technique”, Data Engineering, 1999. Proceedings, 15th International Conference on, 23-26 March 1999, Page(s): 79-86.
[3] Yokota H. and Goto M.: “FBD: a fault-tolerant buffering disk system for improving write performance of RAID5 systems”, Dependable Computing, 1999. Proceedings. 1999 Pacific Rim International Symposium on, 16-17 December. 1999, Page(s): 95-102.
[4] Peng Cheng, Hai Jin, Xinrong Zhou, Qiong Chen and Jiangling Zhang: ”HUST RAID: high performance RAID in real-time system”, Communications, Computers and Signal Processing, 1999 IEEE Pacific Rim Conference on, 22-24 August 1999, Page(s): 59-62.
[5] Blaum, M. Brady, J. Bruck, and J. Menon J: “EVENODD: an optimal scheme for tolerating double disk failures in RAID architectures”, Proceedings the 21st Annual International Symposium on Computer Architecture, 18-21 April 1994, Page(s): 245-254.
[6] Blaum, M. Brady, J. Bruck and J. Jai Menon: “EVENODD: an efficient scheme for tolerating double disk failures in RAID architectures”, IEEE Transactions on Computers, February 1995, Page(s): 192-202.
[7] Dan Feng, Hai Jin and Jiangling Zhang; ”Improved EVENODD code”, ISIT, IEEE International Symposium on Information Theory, 1997, Page: 261.
[8] James S. Plank: “A Tutorial on Reed-Solomon Coding for Fault-Tolerance in RAID-like Systems'', Software -- Practice & Experience, 27(9), September 1997, Page(s): 995-1012.
[9] M.H. Jing, Y.H. Chen, Y.T Chang and T.K. Truong, Fellow, IEEE: “A New VLSI for Implementing the Multiplication and Inverse in the RS-Code”, 4th Multimedia Tech. And Appl. Symp. Taiwan, April 16 1999, Page(s): 304-311.
[10] M.H. Jing, Y.H. Chen and K.Y. Yuan: “The Comparison of EVENODD Code and RS Code for RAID Applications” APCMTA’2000, Asia Pacific Conference on Multimedia Technology and Applications. Kaohsiung Taiwan, December 2000, Page(s): 261-267.
[11] M.H. Jing, Y.H. Chen and J.E. Liao: “A Fast Error and Erasure Correction Algorithm for a Simple RS-RAID”, Int. Conf. On Info-tech and Info-net, Beijing, October. 29, 2001, Page(s): 333-338
[12] Stephen B. Wicker: “Error control systems for digital communication and storage”, Prentice-Hall international, Inc. 1995.
[13] Irving S. Reed and Xuemin Chen: “Error-Control Coding For Data Networks”, Kluwer Academic Publishers. 1999.
[14] M. Morris Mano: “Computer system architecture, 3rd edition”, Prentice-Hall international, Inc. 1993.
[15] M.H. Jing, T.K. Truong, Fellow, IEEE, Y.H. Chen, J.E. Liao and C.H. Chien: “A New Method to scope with Small Write problem In RAID”, The 2002 International Conference on Information and Knowledge Engineering, Las Vegas, USA, June 24-27, 2002, Page(s). 564-569.
[16] “Intel integrated RAID Controller GSU31 user’s manual rev1.0”, Intel Corporation, 2000
[17] K.Y. Yuan: “A Research on Implementing RAID Controller Using RS-Code Technique”, department of information engineering, I-Shou University, Kaohsiung, Taiwan, June 2000.
[18] Y.H. Chen: “The Implementation of Reed-Solomon Code Using Inversionless Berlekamp Massey Algorithm”, department of information engineering, I-Shou University, Kaohsiung, Taiwan, June 1999.