ECE 645

Computer Arithmetic
Spring 2012


Time and location:   Monday, 7:20-10:00 PM, Innovation Hall, room 137

Instructor:                  Kris Gaj     
Email:                          kgaj (at) gmu.edu
Office hours:             Monday, 6:00-7:00 PM;  Tuesday, 7:30-8:30 PM; 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. Objectives, Scope, and Organization. 01/23/2012
  2. Basic Adders and Counters.  Implementation of Adders in FPGAs.   01/23/2012, 01/30/2012
  3. Carry-Lookahead and Carry-Select Adders. Hybrid Adders.   02/06/2012
  4. Conditional-Sum Adders and Parallel Prefix Network Adders.    02/13/2012
  5. Multioperand Addition. 02/20/2012, 02/27/2012
  6. Number Representation: Part 1    03/05/2012
  7. Number Representation: Part 2    03/19/2012
  8. Embedded Resources of FPGAs. 03/26/2012
  9. Midterm Exam    04/02/2012
  10. Tree and Array Multipliers. Multiplication in FPGAs.    04/09/2012
  11. Sequential Multipliers: Part 1   04/16/2012
  12. Sequential Multipliers: Part 2.  04/23/2012
  13. Dividers 04/30/2012


Lecture slides

Posted gradually before a given lecture.

Lecture 10: Dividers

Lecture 9: Sequential Multipliers

Lecture 8: Tree and Array Multipliers

Lecture 7: FPGA Embedded Resources

Lecture 6: Number Representation - Part 2

Lecture 5: Number Representation - Part 1

Lecture 4: Multioperand Addition.

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

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

Lecture 1: Basic Adders and Counters. Implementation of Adders in FPGAs.

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

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

 

Project

Proposed Project Topics:

1. GCM Mode of Operation of AES

Basic Reading:

Recommendation for Block Cipher Modes of Operation: Galois/Counter Mode (GCM) and GMAC, NIST Special Publication 800-38D, 2007.

GCM Test Vectors

2. Tree mode of operation of Skein

Basic Reading:

Skein Round 3 Submission Package available here.

Aric Schorr, Performance Analysis of a Scalable Hardware FPGA Skein Implementation, MS Thesis, RIT 2010.

David M. Webster, Versatile FPGA Architecture for Skein Hashing Algorithm, MS Thesis, RIT 2011.

3. Modular exponentiation unit based on McIvor et al. architecture

Basic Reading:

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.

4. Modular exponentiation unit based on Huang et al. architecture
  
Basic Reading:

M. Huang, K. Gaj, T. El-Ghazawi, "New Hardware Architectures for Montgomery Modular Multiplication Algorithm," IEEE Transactions on Computers, IEEE Transactions on Computers, vol. 60, no. 7, July 2011, pp. 923-936.

5. Modular exponentiation unit based on Suzuki et al. architecture

Basic Reading:

D. Suzuki and T. Matsumoto, "How to Maximize the Potential of FPGA-Based DSPs for Modular Exponentiation," IEICE Trans. Fundamentals, vol. E94-A, no. 1, Jan. 2011, pp. 211-222.

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.

6. Floating point unit for Decimal64 floating-point format
   supporting at least multiplication and addition
  
Basic reading:

Decimal64 floating-point format, Wikipedia.

IEEE 754-2008, Wikipedia.

General Decimal Arithmetic

Other Project Related Links:

ATHENa Website

FPGA Embedded Resources

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

 

Homework Assignments

Homework 3 - due date Monday, March 26, 7:20pm - please submit a printout in class, and an electronic version using Blackboard.

Homework 2 - due date Monday, March 5, 7:20pm - please submit a printout in class, and an electronic version using Blackboard.

Homework 1 - due date extended to Monday, February 13, 7:20pm - please submit a printout in class, and an electronic version using Blackboard.

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

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

 

Reference Materials

Tutorials

The Detailed Instructions on How to Configure your FPGA Tools at School, and Install and Configure your FPGA Tools at Home, last updated Jan. 24, 2012

Tutorial on Simulation with Aldec Active-HDL, ver 2.6, Jan. 24, 2012

Tutorial on Simulation with ModelSim, ver. 1.1, Feb. 1, 2012

Tutorial on Simulation with ISim, ver 1.0, Feb. 1, 2012

Simulators Reference Guide - covering Aldec Active-HDL, ModelSim, and ISim, ver 1.0, Feb. 1, 2012

Tutorial on FPGA Design Flow based on Aldec Active-HDL, ver. 1.6, Oct. 22, 2011

Tutorial on FPGA Design Flow based on Xilinx ISE/Webpack and ModelSim, ver. 1.7,  Oct. 22, 2011

Tutorial on Tutorial on Critical Path Analysis using Synplify Premier DP, ver. 1.0, Nov. 18, 2011

Introduction to Simulation with ModelSim-Altera and Altera Quartus II Setup, ver. 1.0, Oct. 22, 2011

Xfig - Installation and Start-up Guide, ver. 1.0, Sep. 25, 2010

Xfig - Export to PDF Format, ver. 1.0, Dec. 30, 2011


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 Tools

Aldec Active HDL

Xilinx ISE WebPACK - main page

 

Related course web pages

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

ECE 545: Fall 2011 (with Dr. Gaj), 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 2012 - solutions

Midterm Exam from Spring 2011

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 2011

Final Exam from Spring 2010 - Solutions: Problem 1, Problem 2, Problem 3, Problem 5

Final Exam from Spring 2009

Midterm Exam 2 from Spring 2007

Midterm Exam 2 from Spring 2006

Midterm Exam 2 from Spring 2005