ECE 645

Computer Arithmetic
Spring 2011

Time and location:   Monday, 4:30-7:10 PM, Nguyen Engineering Building, room 1109

Instructor:                  Kris Gaj     
Email:                          kgaj (at) gmu.edu
Office hours:             Monday, 7:30-8:30 PM;  Tuesday & Thursday 4:30-5:30 PM; and by appointment

 

Required Textbooks 

Behrooz Parhami, Computer Arithmetic: Algorithms and Hardware Design, 2nd Edition, Oxford University Press, New York, 2010, ISBN 978-0-19-532848-6.

Recommended Textbooks

Jean-Pierre Deschamps, Gery Jean Antoine Bioul, Gustavo D. Sutter,  Synthesis of Arithmetic Circuits: FPGA, ASIC and Embedded Systems,  Wiley-Interscience, 2006, ISBN 978-0-471-68783-2.

Milos D. Ercegovac and Tomas Lang, Digital Arithmetic, Morgan Kaufmann Publishers, 2004.

Isreal Koren, Computer Arithmetic Algorithms, 2nd edition, A. K. Peters, Natick, MA, 2002, ISBN 1-56881-160-8.

Sundar Rajan, Essential VHDL: RTL Synthesis Done Right, S & G Publishing, 1998.

Volnei A. Pedroni, Circuit Design with VHDL, The MIT Press, 2004, ISBN: 0-262-16224-5.

Other literature
 

Software Packages Used in This Class

Course Description

Course Outline (subject to possible modifications):

  1. Basic Adders.  01/24/2011
  2. Implementation of Adders in FPGAs. Counters.     01/31/2011
  3. Carry-Lookahead and Carry-Select Adders. Hybrid Adders.   02/07/2011
  4. Conditional-Sum Adders and Parallel Prefix Network Adders.    02/14/2011
  5. Number Representation: Part 1    02/21/2011
  6. Number Representation: Part 2    02/28/2011
  7. Multioperand Addition. 03/07/2011
  8. Montgomery Multipliers and Exponentiation Units 03/21/2011
  9. Midterm Exam    03/28/2010
  10. Tree and Array Multipliers. Multiplication in FPGAs.: Part 1    04/04/2011
  11. Tree and Array Multipliers. Multiplication in FPGAs.: Part 2    04/11/2011
  12. Sequential Multipliers: Part 1   04/18/2011
  13. Sequential Multipliers: Part 2. Serial Multipliers. Modular Multipliers.  04/25/2011
  14. Dividers    05/02/2011


Lecture slides

Lecture 10: Basic Dividers

Lecture 9: Sequential Multipliers

Lecture 8: Tree and Array Multipliers

Lecture 7: Montgomery Multipliers and Exponentiation Units

Lecture 6: Multioperand Addition

Lecture 5: Number Representation: Part 2. Little-Endian vs. Big-Endian Representations. Floating Point Representations.

Lecture 4: Number Representation: Part 1. Unsigned and Signed Fixed-Point Representations. 

Lecture 3: Conditional-Sum Adders and Parallel Prefix Network Adders

Lecture 2: Carry-Lookahead, Carry-Select, and Hybrid Adders

Lecture 1: Basic Adders

Lecture 0: Objectives, Scope, and Organization of the Course

Posted gradually before a given lecture.

See the course web page from Spring 2010 for slides from the previous year.

 

Project 

Reference Software Implementation of the Montgomery Multiplication:   source codes    readme.txt    test vectors

Literature for Project 2:

  1. C. McIvor, M. McLoone, J.V. McCanny, A. Daly, W. Marnane, "Fast Montgomery Modular Multiplication and RSA Cryptographic Processor Architectures", 37th Annual Asilomar Conference on Signals, Systems and Computers, Pacific Grove, CA, USA, November 2003, pp. 379 - 384.
  2. S.B. Ors, L. Batina, B. Preneel, J. Vandewalle, "Hardware Implementation of a Montgomery Modular Multiplier in a Systolic Array," International Parallel and Distributed Processing Symposium, IPDPS 2003, Nice, France.
  3. E. Öksüzoğlu, E. Savaş, "Parametric, Secure and Compact Implementation of RSA on FPGA," 2008 International Conference on Reconfigurable Computing and FPGAs, Reconfig 2008, Cancun, Mexico, Dec. 2008, pp. 391 - 396.
  4. A.F. Tenca and C.K. Koc, “A Scalable Architecture for Montgomery Multiplication,” Cryptographic Hardware and Embedded Systems workshop, CHES 1999, Worcester, MA, USA, LNCS, vol. 1717, pp. 94–108.
  5. A.F. Tenca, G. Todorov, and C.K. Koc, “High-Radix Design of a Scalable Modular Multiplier,” Cryptographic Hardware and Embedded Systems workshop, CHES 2001, Paris, France, LNCS, vol. 2162, pp. 185–201.
  6. M. Huang, K. Gaj, T. El-Ghazawi, "New Hardware Architectures for Montgomery Modular Multiplication Algorithm," IEEE Transactions on Computers (to appear in 2011).
  7. D. Harris, R. Krishnamurthy, M. Anders, S. Mathew, S. Hsu, "An Improved Unified Scalable Radix-2 Montgomery Multiplier," 17th IEEE Symposium on Computer Arithmetic, ARITH 2005, Cape Cod, MA, USA, pp.172-178.
  8. N. Pinckney and D.M. Harris, "Parallelized Radix-4 Scalable Montgomery Multipliers," Journal Integrated Circuits and Systems 2008; vol. 3,  no.1, pp. 39-45.
  9. D. Suzuki, "How to Maximize the Potential of FPGA Resources for Modular Exponentiation," Cryptographic Hardware and Embedded Systems workshop, CHES 2007, Vienna, Austria, LNCS, vol. 4727, pp. 272-288.

Specification of Project 1 - final submission deadline extended to Wednesday, March 23, 2011, 11:59pm.

Literature for Project 1:

ATHENa Website

Round 3 SHA-3 Candidates

Comparing Hardware Performance of Fourteen Round Two SHA-3 Candidates Using FPGAs,
by Ekawat Homsirikamol, Marcin Rogawski, and Kris Gaj, Cryptology ePrint Archive: Report 2010/445 - Revised December 21, 2010

SHA-3 Zoo - Hardware Implementations

FPGA Embedded Resources

Materials related to the course projects will be posted gradually over the duration of the course.

 

Homework Assignments

Homework 2 - due Friday,  March 11, 11:59pm

Homework 1 - due Monday, February 14, 4:30pm

Posted gradually about a week before a given assignment is due.

See the course web page from Spring 2010 for homework assignment from the previous year.

 

Reference Materials

Computer Arithmetic Algorithms Simulators

Simulator by Isreal Koren

 

VHDL

VHDL Instructions: Templates & Examples

OpenCores Coding Guidelines

The Low Carb VHDL Tutorial - by Bryan Mealy

VHDL Tips & Tricks - a very useful set of slides from the Integrated Systems Laboratory, ETH Zurich

 

FPGA Devices and Tools

Introduction to FPGA Devices and Tools

GMU FPGA CAD Tools at School and Home

Tutorial on Simulation using Aldec Active-HDL

Tutorial on FPGA Design Flow based on Aldec Active-HDL

Tutorial on FPGA Design Flow based on Xilinx ISE

Active HDL Student Edition

Xilinx ISE WebPACK - main page

Xilinx ISE WebPACK - FAQ

 

Related course web pages

ECE 645: Spring 2010 (with Dr. Gaj),  Spring 2009 (with Dr. Gaj),  Spring 2008 (with Dr. Hwang), 

ECE 545: Fall 2010 (with Dr. Gaj),  Fall 2009 (with Dr. Gaj), Fall 2008 (with Dr. Hwang)

ECE 448: Spring 2011 (with Dr. Gaj),  Spring 2010 (with Dr. Gaj), Spring 2009 (with Dr. Gaj)

 

Practice Exams

DISCLAIMER: The exams from previous years are not representative of the material covered in class this semester, and may include questions you are not required to know solutions to, and omit material covered in the class this year.

Practice Midterm Exam from Spring 2005

Practice Midterm Exam from Spring 2004

 

Midterm Exam from Spring 2010 - solutions

Midterm Exam from Spring 2009 - solutions

Midterm Exam 1 from Spring 2007 - solutions

Midterm Exam 1 from Spring 2005 - solutions

Midterm Exam 1 from Spring 2004 - solutions

Midterm Exam 1 from Spring 2002 - solutions

Midterm Exam 1 from Spring 2000

 

Final Exam from Spring 2010

Final Exam from Spring 2009

Midterm Exam 2 from Spring 2007

Midterm Exam 2 from Spring 2006

Midterm Exam 2 from Spring 2005