ECE
645
Computer Arithmetic
Spring 2011
Time and location: Monday,
4:307:10 PM, Nguyen Engineering Building, room 1109
Instructor: Kris
Gaj
Email:
kgaj
(at) gmu.edu
Office
hours: Monday,
7:308:30 PM; Tuesday &
Thursday 4:305:30 PM; and by appointment
Required
Textbooks
Behrooz
Parhami,
Computer
Arithmetic: Algorithms and Hardware Design,
2^{nd}
Edition, Oxford University
Press, New York, 2010, ISBN 9780195328486.
Recommended
Textbooks
JeanPierre
Deschamps, Gery Jean Antoine Bioul, Gustavo D. Sutter,
Synthesis
of Arithmetic Circuits: FPGA, ASIC and Embedded Systems,
WileyInterscience, 2006, ISBN 9780471687832.
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 1568811608.
Sundar Rajan,
Essential
VHDL: RTL Synthesis Done Right,
S & G Publishing, 1998.
Volnei A. Pedroni,
Circuit Design
with VHDL,
The
MIT Press, 2004, ISBN:
0262162245.
Other
literature
Software Packages Used
in This Class
 Aldec Active HDL
 Synopsys Synplify Pro
 Xilinx ISE or Xilinx WebPACK
 ModelSim SE or ModelSim PE Student
Edition
Course
Description
Course Outline (subject to possible
modifications):
 Basic Adders. 01/24/2011
 Implementation of Adders in FPGAs.
Counters. 01/31/2011
 CarryLookahead and CarrySelect
Adders. Hybrid Adders.
02/07/2011
 ConditionalSum Adders and Parallel Prefix Network Adders. 02/14/2011
 Number Representation: Part
1 02/21/2011
 Number Representation: Part
2 02/28/2011
 Multioperand
Addition. 03/07/2011
 Montgomery Multipliers and
Exponentiation
Units 03/21/2011
 Midterm
Exam
03/28/2010
 Tree and Array
Multipliers. Multiplication in FPGAs.: Part
1
04/04/2011
 Tree and Array
Multipliers. Multiplication in FPGAs.: Part 2
04/11/2011
 Sequential Multipliers: Part 1
04/18/2011
 Sequential Multipliers: Part 2. Serial Multipliers. Modular Multipliers. 04/25/2011
 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. LittleEndian vs. BigEndian
Representations. Floating Point Representations.
Lecture 4: Number Representation: Part
1. Unsigned and
Signed FixedPoint Representations.
Lecture 3: ConditionalSum
Adders and Parallel Prefix Network Adders
Lecture 2: CarryLookahead,
CarrySelect, 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:
 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.
 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.
 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.
 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.
 A.F. Tenca, G.
Todorov, and C.K. Koc, “HighRadix
Design of a Scalable Modular Multiplier,” Cryptographic
Hardware and Embedded Systems workshop, CHES 2001, Paris, France, LNCS,
vol. 2162, pp. 185–201.
 M. Huang, K. Gaj,
T. ElGhazawi, "New Hardware
Architectures for Montgomery Modular Multiplication Algorithm,"
IEEE Transactions on Computers (to appear in 2011).
 D. Harris, R.
Krishnamurthy, M. Anders, S. Mathew, S. Hsu, "An Improved
Unified Scalable Radix2 Montgomery Multiplier," 17th IEEE Symposium on Computer Arithmetic, ARITH 2005, Cape Cod, MA, USA, pp.172178.
 N. Pinckney and
D.M. Harris, "Parallelized
Radix4 Scalable Montgomery Multipliers," Journal Integrated
Circuits and Systems 2008; vol. 3, no.1, pp. 3945.
 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.
272288.
Specification of
Project 1  final submission
deadline extended to
Wednesday, March 23,
2011, 11:59pm.
Literature
for Project
1:
 P.
Zicari and S.
Perri, “A
Fast
Carry Chain Adder for Virtex5 FPGAs,”
15th IEEE
Mediterranean Electrotechnical Conference, MELECON 2010, Valletta,
Malta, 2628 April 2010, pp. 304 – 308.
 S.
Xing, W.W.H. Yu,
"FPGA
Adders: Performance Evaluation and Optimal Design,"
IEEE Design
& Test of Computers, vol. 15, no. 1, pp. 2429, Jan.Mar. 1998.
 F.
Dinechin, H.D.
Nguyen, B. Pasca, “Pipelined FPGA Adders,” 20th
International Conference on Field Programmable Logic and Applications,
Milano, Italy, Aug. 31st  Sep. 2nd, 2010 (paper
+ slides).
 F.
Dinechin, H.D.
Nguyen, B. Pasca, “Pipelined
FPGA Adders,” ENSL
Report no. 201016, April 2010.
 FloPoCo
project
web site
ATHENa
Website
Round 3 SHA3 Candidates
Comparing
Hardware Performance of Fourteen Round Two SHA3 Candidates Using FPGAs,
by Ekawat Homsirikamol, Marcin Rogawski, and Kris Gaj, Cryptology
ePrint Archive: Report 2010/445  Revised
December 21, 2010
SHA3 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
VHDL
OpenCores
Coding
Guidelines
VHDL
Tips & Tricks  a very
useful set of slides from the Integrated
Systems Laboratory, ETH Zurich
FPGA Devices and Tools
Tutorial on Simulation using Aldec
ActiveHDL
Tutorial on FPGA Design Flow based on
Aldec
ActiveHDL
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