A fast parallel reed-solomon decoder on a reconfigurable architecture

ABSTRACT

This paper presents a software implementation of a very fast parallel Reed-Solomon decoder on the second generation of MorphoSys reconfigurable computation platform, which is targeting on streamed applications such as multimedia and DSP. Numerous modifications of the first-generation of the architecture have made a scalable computation and communication intensive architecture capable of extracting parallelisms of fine grain in instruction level. Many algorithms and the whole Digital Video Broadcasting base-band receiver as well, have been mapped onto the second architecture with impressing performance. The mapping of a Reed-Solomon decoder proposed in this paper highly parallelizes all of its sub-algorithms, including Syndrome Computation, Berlekamp Algorithm, Chein Search, and Error Value Computation, in a SIMD fashion. The mapping is tested on a cycle-accurate simulator, "Mulate", and the performance is encouragingly better than other architectures. The decoding speed of the RS (255,239,16) decoder using two different methods of GF multiplication can be 1.319Gbps and 2.534Gbps, respectively. Furthermore, since there is no functionality specifically tailored to Reed-Solomon decoder, the result has demonstrated the capability of MorphoSys architecture to extracting Instruction Level Parallelism from streamed applications.

REFERENCES

• 1: Hartej Singh , Ming-Hau Lee , Guangming Lu , Nader Bagherzadeh , Fadi J. Kurdahi , Eliseu M. Chaves Filho, MorphoSys: An Integrated Reconfigurable System for Data-Parallel and Computation-Intensive Applications, IEEE Transactions on Computers, v.49 n.5, p.465-481, May 2000 [doi>10.1109/12.859540]
• 2: Ming-Hau Lee , Hartej Singh , Guangming Lu , Nader Bagherzadeh , Fadi J. Kurdahi , Eliseu M. C. Filho , Vladimir Castro Alves, Design and Implementation of the MorphoSys Reconfigurable ComputingProcessor, Journal of VLSI Signal Processing Systems, v.24 n.2-3, p.147-164, Mar. 2000 [doi>10.1023/A:1008189221436]
• 3: Chengzhi Pan , Nader Bagherzadeh , Amir Hosein Kamalizad , Arezou Koohi, Design and Analysis of a Programmable Single-Chip Architecture for DVB-T Base-Band Receiver, Proceedings of the conference on Design, Automation and Test in Europe, p.10468, March 03-07, 2003
• 4: Vikas Agarwal , M. S. Hrishikesh , Stephen W. Keckler , Doug Burger, Clock rate versus IPC: the end of the road for conventional microarchitectures, Proceedings of the 27th annual international symposium on Computer architecture, p.248-259, June 2000, Vancouver, British Columbia, Canada
• 5: Michael S. Schlansker , B. Ramakrishna Rau, EPIC: Explicitly Parallel Instruction Computing, Computer, v.33 n.2, p.37-45, February 2000 [doi>10.1109/2.820037]
• 6: Michael Bedford Taylor , Jason Kim , Jason Miller , David Wentzlaff , Fae Ghodrat , Ben Greenwald , Henry Hoffman , Paul Johnson , Jae-Wook Lee , Walter Lee , Albert Ma , Arvind Saraf , Mark Seneski , Nathan Shnidman , Volker Strumpen , Matt Frank , Saman Amarasinghe , Anant Agarwal, The Raw Microprocessor: A Computational Fabric for Software Circuits and General-Purpose Programs, IEEE Micro, v.22 n.2, p.25-35, March 2002 [doi>10.1109/MM.2002.997877]
• 7: Scott Rixner , William J. Dally , Ujval J. Kapasi , Brucek Khailany , Abelardo López-Lagunas , Peter R. Mattson , John D. Owens, A bandwidth-efficient architecture for media processing, Proceedings of the 31st annual ACM/IEEE international symposium on Microarchitecture, p.3-13, November 1998, Dallas, Texas, United States
• 8: Christoforos Kozyrakis , David Patterson, Vector vs. superscalar and VLIW architectures for embedded multimedia benchmarks, Proceedings of the 35th annual ACM/IEEE international symposium on Microarchitecture, November 18-22, 2002, Istanbul, Turkey
• 9: Michael Bedford Taylor , Walter Lee , Saman Amarasinghe , Anant Agarwal, Scalar Operand Networks: On-Chip Interconnect for ILP in Partitioned Architectures, Proceedings of the 9th International Symposium on High-Performance Computer Architecture, p.341, February 08-12, 2003
• 10: Girish Venkataramani , Walid Najjar , Fadi Kurdahi , Nader Bagherzadeh , Wim Bohm, A compiler framework for mapping applications to a coarse-grained reconfigurable computer architecture, Proceedings of the 2001 international conference on Compilers, architecture, and synthesis for embedded systems, November 16-17, 2001, Atlanta, Georgia, USA [doi>10.1145/502217.502235]
• 11: R. Maestre , F. J. Kurdahi , N. Bagherzadeh , H. Singh , R. Hermida , M. Fernandez, Kernel scheduling in reconfigurable computing, Proceedings of the conference on Design, automation and test in Europe, p.21-es, January 1999, Munich, Germany [doi>10.1145/307418.307460]
• 12: Implementation of high speed Reed-Solomon decoder. {Conference Paper} 42nd Midwest Symposium on Circuits and Systems (Cat. No.99CH36356). IEEE. Part vol. 2, 2000, pp.808-12 vol. 2. Piscataway, NJ, USA.
• 13: Martina M, Masera G, Piccinini G, Vacca F, Zamboni M. VLSI Reed Solomon decoder architecture for networked multimedia applications. {Conference Paper} Proceedings 14th Annual IEEE International ASIC/SOC Conference (IEEE Cat. No.01TH8558). IEEE. 2001, pp.347--51. Piscataway, NJ,USASystems II-Analog & Digital Signal Processing, vol.47, no.11, Nov. 2000, pp.1254--70. Publisher: IEEE, USA.
• 14: Wen C. Lin, Microprocessors: Fundamentals and Applications, John Wiley & Sons, Inc., New York, NY, 1977
• 15: www.amphion.com <http://www.amphion.com>
• 16: www.ti.com <http://www.ti.com>
• 17: www.xilinx.com <http://www.xilinx.com>

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Single-instruction-stream, multiple-data-stream processors (SIMD)

General Terms:
Algorithms, Design, Experimentation, Performance

Keywords:
Berlekamp algorithm, Chein search, Reed-Solomon codes, SIMD processor, reconfigurable architecture