Computer Arithmetic - Fall 2001

Dr. Guy Even

The Computer Arithmetic course is about how to design an Arithmetic Logic Unit (ALU) and a Floating Point Unit. The course deals with the mathematical foundation as well as the hardware implementation.

place & time

Thursdays, 16-18, Room 207, Kitot Building.

Projects

Time to start thinking about projects. About 5 pairs of students may do a project instead of the final exam. Students interested in doing a project will have to be already halfway in completing the project by the end of the semester. So it is about time to consider working on it. I am open to suggestions, but am also providing a ``list'' of project ``directions''.

1. Timing analysis of the Seidel-Even FP-ADD algorithm. This project requires access to a simulation tool with timing analysis. One can also download some free simulators. Timing analysis requires gate level description and should take into account not only gate delays but also loads and fanouts. Wire delays are harder to account for, unfortunately...
2. Error analysis of iterative division algorithms. This topic requires using using some multi-precision software such as Mathematica, Maple, or simple bc. The goal is to design a software tool that will analyze the precision of a (floating point) divider (i.e. is the initial approximation good enough? are intermediate multiplications precise enough? etc.).
3. Hardware and software projects related to arithmetic applications on smart cards. Topics can be related to implementing cryptographic applications, arithmetic co-processors, etc.

homework

• Course Requirements.
• Assignment #1 - Recoding and parallel addition.
• Assignment #2 - Two's complement and normaliztion shift.
• Assignment #3 - Take home exam.

course material

1. Recodings. There are three references for this topic. See also references mentioned within these papers.
   1. Partial Compression and Recoding by Daumas, Even, and Matula.
   2. Further reducing the redundancy of a notation over a minimally redundant digit set, by Daumas and Matula.
   3. An IEEE compliant floating-point adder that conforms with the pipelined packet-forwarding paradigm by Nielsen, Matula, Lyu, and Even, in IEEE Transactions on Computers, Vol. 49, No. 1, pp. 33-47, January 2000.
2. IEEE standard on floating point arithmetic.
   1. On the design of IEEE compliant floating point units by Even and Paul, IEEE Transactions on Computers Volume: 49 Issue: 5 , May 2000.
   2. Arnon Warshavsky's IEEE floating point demo. I needed to install some DLL files from here.

   3. The Decomposition Theorem for IEEE Floating Point Rounding. By S. M. Müller and W.J. Paul.
3. IEEE rounding (injection based rounding)
   1. Guy Even, Silvia M. Müller, and Peter-Michael Seidel, A Dual Precision IEEE Floating-Point Multiplier, Integration, The VLSI Journal, Volume 29, Issue 2, pp. 167-180, September 2000.
4. Floating Point Multiplication. A comparison of three rounding algorithms for IEEE floating-point multiplication by Even and Seidel, Page(s): 638 -650, IEEE Transactions on Computers, Volume: 49 Issue: 7 , July 2000.
5. Floating-Point Addition.
   1. On the Design of Fast IEEE Floating-Point Adders by Peter Seidel and Guy Even.
6. Floating Point Division
   1. Floating Point Division and Square Root Algorithms and Implementation in the AMDK7 Microprocessor, S. Oberman - Advanced Micro Devices. Paper from 14th IEEE Symposium on Computer Arithmetic Adelaide, Australia April 14 - 16, 1999. (click on the posrtscript version)
   2. A draft of a paper on an error analysis of Goldschmidt's division algorithm by Even, Seidel, and Feguson.

references

• List of references.
• Class Notes written in the past two years by students taking the course. Some of these class notes are pretty good - however, read with a (big) grain of salt.
  • Spring 98
  • Spring 99

About this document ...