Email this article 
Open Access
Subscription or Fee Access
Development of Floating Point Multiplier used in LU-Factorization Hardware Interpreter
Abstract
Given a system of linear equations, a complete reduction of the coefficient matrix to Reduced Row Echelon (RRE) form is far from the most efficient algorithm if one is onlyinterested in finding a solution to the system. However, the Elementary Row Operations (EROs) that constitute such a reduction are themselves at the heart of many frequently used numerical (i.e., computercalculated) applications of Linear Algebra [1]. EROs can be used to produce a so-called LU- factorization of a matrix into a product of two significantly simpler matrices. Unlike dagonalization and the polar decomposition for matrices these LU Decompositions can be computed reasonably quickly for many matrices [1]. LUfactorizations are also an important tool for solving linear systems of equations. It should be noted that the factorization ofcomplicated objects into simpler components is an extremely common problem solving technique in mathematics. The LU factorization algorithm is as such a very complex and time consuming task. The only way to reduce the time would be to use a hardware interpreter for executing the linear code [2]. The interpreter which takes in a stream of variable length instructions representing the symbolic unrolled instructions in the LU factorization algorithm [2]. The output of the interpreter is the sparse L and U factors where the matrix values are in IEEE-754 double precision format [2],[3]. In this paper, multiplication algorithms are analyzed, cores have been developed in Verilog HDL and its pipelined versions are tested using Field Programmable Gate Arrays (FPGAs).
Keywords
References
Heshan A1-Twaijry and Michael J. Flynn. Performance/area tradeoffs in booth multipliers Technical report, Stanford University, November 1995.
Peter J. Ashen den. The Designer’s guide to VHDL. Morgan Kauffman Publishers, 1995
Prithviraj Banarjee. Parallel Algorithms for VLSI-Computer Aided Design. Prentice Hall, New Jersey, 1994.
P.L.Brown, W.S. Richman. The choice of base. Communications of the ACM, Vol 12, No. 10, 1969.
Xilinx Datasheet. VIRTEX 2.5v field programmable gate arrays. Technical report, Xilinx Inc., April 2001.
Stuart F. Oberman David L. Harris and Mark A. Horowitz. Srt division architectures and implementations. In Proceeding of the 13th IEEE Symposium on Computer Arithmetic. Stanford University, July 1997.
Stuart F.Oberman and Michael J.Flynn. Division algorithms and implementations. IEEE Transactions on Computers, VOL 4, No. 8, August 1997.
John L Hennessey and David A Patterson. Computer Organization and Design-The Hardware/Software Interface. Margin Kauffman Publishers, 1994.
John L Hennessey and David A Patterson. Computer Architecture-A Quantitative Approach. Morgan Kauffmann, 2000.
Chen-Ying Hsu. Variable precision arithmetic processor in FPGAs. Master’s thesis. University of Toronto, 1998.
Kai Hwang. Computer Arithmetic-Principles, Architecture, and Design. John Wiley and Sons, 1979.
J.A.Hidalgo, V.Moreno-Vergara, O.Oballe, A, Daza, M.J.Martin- Vazuez, and A.Gago. A radix-8 multiplier unit design for specific purpose. In XIII Conference of Design of Circuits and Integrated Systems (DCIS’98) Madrid. Dept. de Electronic, E.T.S.I. Industrials,1998.
J.Kahan, W.Palmer. On a proposed floating-point standard. Technical report. SIGNUM Newsletter, Special Issue, October 1979.
K.C.Chang. Digital Design and Modeling with VHDL Syntheses. IEEE Computer society Press, 1997.
Israel Korea. Computer Arithmetic Algorithms. Prentice Hall, New Jersey, 1993.
Weng Fook Lee. VHDL-Coding and Logic Synthesis with SYNOPSYS. Academic Press, 2000.
Allison L. Walters. A scaleable fir filter implementation using 32-bit floating point complex arithmetic on a FPGA based custom computing platform. Master’s thesis, Virginia Polytechnic Institute and StateUniversity, 1998.
AI Walters Nabeel Shirazes and Peter Athena’s. Quantitative analysis of floating point arithmetic on FPGA based custom computing machines. In presented at the 5th International Workshop on Field Programmable Logic and Applications. Virginia Polytechnic Institute and State University, April 1995.
New York, NY: Institute of Electrical and Electronics Engineers. IEEE Standard for Binary Floating-Pont Arithmetic, ansi/ieee STD 754-1985.Edition, 1985.
Stuart F. Oberman and Michael J.Flynn. Implementing division and other floating-point operations A system perspective. In proceedings of SCAN-95, International Symposium on Scientific Computing, Computer Arithmetic, and Validated Numeric, September 1995.
Stuart F. Oberman and Michael J.Flynn. Design issues in division and other flatting-point operations. IEEE Transactions on Computers, 1997.
Stuart Franklin Oberman. Design Issues in High Performance Floating Point Arithmetic Units. PhD thesis, Stanford University, November 1996.
Jan Ogrodzki. Circuit Simulation Methods and Algorithms. CRC Press, 1994.
Amos R. Omondi. Computer Arithmetic Systems-Algorithms, Architectures and Implementations. Prentice Hall Internationsl, 1994.
Akber Syed. A hardware interpreter for sparse matrix Lu factorization. Master’s thesis, University of Cincinnati, 2002.
Sanjeev Thiyagarajan. Reducing memory space for completely unrolled Lu factorization of sparse matrices. Master’s thesis, university of Cincinnati, May 2001.
Gary W.Bewick. Fast Multiplication algorithms and implementation PhD thesis, Stanford University, February 1994.
Hong Zhang. An evolution of complete loop unrolling technique for solving sparse linear system of equations using direct methods Master’s thesis, University of Cincinnati, 1998.
Refbacks
- There are currently no refbacks.