Credits: 3-0-0-0 (9)
Prerequisites: CS220 or EE370
Who can take the course: PhD, Masters, 3rd and 4th year UG Students
Departments that may be interested: CSE, EE, DIS
Computer arithmetic in the last two decades has gone through exponential growth due to innovation in the domain of computer architectures and development of efficient algorithms for computing arithmetic routines. The recent advances in computationally intensive fields like machine learning and cryptography require fast arithmetic computation and, hence, the study of computer arithmetic. In this course, our objective is to learn advanced concepts of computer arithmetic and implement these algorithms on Field-Programmable Gate Arrays (FPGAs). The course will cover topics like redundant number system, residue number system, advanced representation of floating numbers, advanced addition, multiplication, and division algorithms, implementation of square-root, CORDIC, and fast Fourier transform (FFT), etc. After completing this course, students will not only be knowledgeable about these algorithms but also know how to efficiently implement them on hardware.
| Broad Topic | Key Areas | No. of Lectures |
|---|---|---|
| Number System | Refresher on 1’s and 2’s complement system, Redundant number system, Digit Sets, Generalized Sign-Digit systems, Binary Sign-Digit (BSD) System | 4 |
| Integer Arithmetic | High Speed Addition, Parallel prefix adder, High speed multiplication, Karatsuba algorithm, Matrix multiplication | 4 |
| FPGA implementation of Integer Arithmetic | LUT and Carry chain based adder, DSP based multiplication, Implementing Karatsuba multiplication | 4 |
| Modular Arithmetic | Linear congruence, GCD and LCM computation, Field addition, Field multiplication, field inversion, Chinese Remainder Theorem, Residue Number System, Number Theoretic Transformation | 6 |
| FPGA implementation of Modular Arithmetic | Implementing Field addition, Montgomery multiplication, Fermat’s theorem for inversion, Euclidean inversion algorithm | 4 |
| Floating point arithmetic | IEEE 754 floating point, Guard and sticky bits, POSIT system | 6 |
| FPGA implementation of Floating point arithmetic | Implementing Posit and IEEE-754 | 4 |
| Function Evaluation | Square-root, CORDIC, FFT, Approximate computing | 8 |
1.B. Parhami, Computer Arithmetic and Hardware Design, 2nd ed. New York, NY, USA: Oxford University Press, 2010.
2. I. Koren, Computer Arithmetic Algorithms, 2nd ed. Natick, MA, USA: A K Peters, 2001.
1. M. J. Flynn and S. F. Oberman, Advanced Computer Arithmetic Design. New York, NY, USA: John Wiley & Sons, 2001.
2. U. W. Kulisch, Advanced Arithmetic for the Digital Computer. Vienna, Austria: Springer, 2002.