|
ECE
252B: Computer Arithmetic
Behrooz
Parhami: 2008/06/03
|| E-mail: parhami at ece.ucsb.edu || Other
contact info at: Bottom
of this page
Go up to: B.
Parhami's course syllabi or his
home page
ECE 252B: Spring Quarter 2008 offering
This area is reserved for important course
announcements: 2008/05/30: Presentations for Parts V and
VI have now been updated for spring 2008 in the textbook's website. Except for
grade stats for HW4 and the final exam, to be posted as they become available,
all information on this page is now final and will not be further updated.
2008/05/25: HW4 (last one for
the course) has been posted below. Please also see the posted notes on homework
solutions.
2008/05/19: Updated presentations for part
IV of the text have been posted.
2008/05/11: HW3 has been
posted below. The midterm exam grades have a mean of 62 and a median of 65. The
grade list is as follows -- 39 42 45 47 48 57 58 62 62 67 68 69 70 73 74 76 81
86
2008/04/22: HW2 has been
posted below. Updated presentation for part III of the textbook will be posted
by April 30.
0008/04/07: HW1 and a
preliminary list of research topics have been posted below. Updated presentation
for part I of the textbook is now available on the book's website.
2008/03/20: Welcome to the ECE
252B website for spring 2008. During the quarter, you will need to consult two
websites associated with the course. This website is the "course website." There
is also a website for our textbook, where downloadable presentations and
information on discovered errors can be found. You can reach the latter website
by clicking on the textbook link under "References" below.
|
Course: |
ECE 252B – Computer Arithmetic, University of California, Santa Barbara,
Spring 2007, Enrollment Code 10736 |
|
Catalog
entry: |
252B.
Computer Arithmetic. (4)
PARHAMI. Prerequisites:
ECE 152A-B. Lecture, 4 hours. Standard and unconventional number
representations. Design of fast two-operand and multioperand adders.
High-speed multiplication and division algorithms. Floating-point numbers,
algorithms, and errors. Hardware algorithms for function evaluation.
Pipelined, digit-serial and fault-tolerant arithmetic processors. |
|
Instructor: |
Behrooz
Parhami, Room 5155 HFH (Engineering I), Phone
805-893-3211, parhami at ece.ucsb.edu |
|
Meetings: |
TR
12:00-1:30, Room 1431 Phelps Hall |
|
Consultation: |
Open
office hours, held in Room 5155 HFH (Engineering I) – T 9:00-10:30, R 10:00-11:30 |
|
Motivation: |
Computer
arithmetic is a subfield of digital computer organization. It deals with
the hardware realization of arithmetic functions to support various
computer architectures as well as with arithmetic algorithms for
firmware/software implementation. A major thrust of digital computer
arithmetic is the design of hardware algorithms and circuits to enhance
the speed of various numeric operations. Thus much of what is presented in
this course complements the architectural
and algorithmic speedup techniques covered as part of the advanced
computer architecture (ECE 254A/B/C) sequence.
|
|
Prerequisites: |
Familiarity
with logic design and switching theory as well as fundamentals of digital
system design (ECE 152A and ECE 152B or equivalents).
|
|
References: |
Required
textbook
(expected at the UCSB bookstore in late March 2008)
Parhami,
B., Computer Arithmetic: Algorithms
and Hardware Designs, Oxford, 2000 (click on the title of the
textbook to access its website). The Bookstore has been
instructed to order the 4th or a later printing of the book which has all known typos
and other errors corrected and contains some additional material. If you
buy a used copy of the third or earlier printing, please make sure you
correct the errors using the errata provided in the book's website
(accessible via the link above). The price at the Bookstore is $125.00 for
new books and $93.75 for used copies.
Other
useful
books,
not required
Deschamps/Bioul/Sutter, Synthesis of Arithmetic
Circuits: . . . , 2006 (TK7895.A65D47).
Ercegovac/Lang,
Digital Arithmetic, Morgan Kaufmann, 2004.
Swartzlander,
Computer Arithmetic, vols. 1-2,
IEEE Computer Soc. Press (QA76.6.C633).
Koren, Computer Arithmetic
Algorithms,
2nd ed., A K Peters,
2002.
Omondi,
Computer Arithmetic Systems: . . . ,
Prentice-Hall, 1994 (QA76.9.C62O46).
Ercegovac/Lang,
Division and Square Root: . . . , Kluwer, 1994 (QA76.9.C62E73).
Oklobdzija,
High-Performance System Design, IEEE Press, 1999
(TK7871.99.M44037).
Waser/Flynn,
Intro. to Arithmetic for Digital
Systems Designers
(TK7895.A65W37.1982).
Knuth,
The Art
of Computer Programming: Seminumerical
Algorithms (QA76.6.K64 vol 2).
Hwang,
Computer Arithmetic: Principles, Architecture, and Design
(TK7888.3.H9).
Kulisch/Miranker,
Computer Arithmetic in Theory and
Practice (QA162.K84).
Research
Sources
Proc.
Symp. Computer Arithmetic (1969, 72, 75 78, and odd years
since 1981).
IEEE Trans. Computers, particularly special issues on computer
arithmetic (8/70, 6/73, 7/77, 4/83, 8/90, 8/92, 8/94, 7/98, 7/00, 3/05,
8/08?).
Electronic Resources at UCSB
http://www.library.ucsb.edu/eresources/databases/
(electronic journals, collections, etc.)
http://www.library.ucsb.edu/subjects/engineering/ece.html (research
guide in ECE) |
|
Evaluation: |
Students
will be evaluated based on the following three components with the given
weights:
|
|
|
20%
-- Homework (see the course calendar for general requirements and
schedule). |
|
|
30%
-- Closed-book midterm exam (see the course calendar for date and
coverage). |
|
|
50%
-- Open-book final exam (see the course calendar for date, time,
and coverage)
|
| Research: |
An
optional
research
paper
may
be
substituted
for
the
final exam.
A
student
interested in this option,
will review a subfield of computer arithmetic or do original research on a
selected topic. A list of research topics is provided below; however, please feel free to propose your
own topic for approval. A publishable report earns an “A” for the course,
regardless of homework and midterm grades. See the “deadlines” column
in course calendar for schedule and due dates. |
Calendar:
Course
lectures, homework assignments, and exams have been scheduled as follows. This
schedule will be strictly observed. Textbook chapters are specified for lectures
and exams. It is a good idea to look over the specified material
before
each lecture if possible.
|
Day
& Date |
Chap |
Lecture
Topic |
Deadlines
and Notes |
|
Tues.
4/1 |
1-2 |
Numbers
and signed values |
This is a
serious lecture -- Really! |
|
Thur.
4/3 |
3-4 |
Redundant and residue
representations |
|
|
Tues.
4/8 |
5 |
Basic addition and counting |
HW#1
posted (chapters 1-7) |
|
Thur.
4/10 |
6 |
Carry-lookahead adders |
Research
topic defined |
|
Tues.
4/15 |
7 |
Variations in fast adders |
|
|
Thur.
4/17 |
8 |
Multioperand
addition |
HW#1 due |
|
Tues.
4/22 |
9 |
Basic
multiplication schemes |
HW#2 posted (chapters
8-11) |
|
Thur.
4/24 |
10 |
High-radix multipliers |
|
|
Tues.
4/29 |
11 |
Tree and array multipliers |
Preliminary references due |
|
Thur.
5/1 |
12 |
Variations in multipliers |
HW#2 due |
|
Tues.
5/6 |
1-11 |
Midterm
exam: closed book (12-2 PM) |
Held in class; note
extended time |
|
Thur.
5/8 |
13 |
Basic
division schemes |
|
|
Tues.
5/13 |
14 |
High-radix
division |
HW#3 posted (chapters
12-16) |
|
Thur.
5/15 |
15 |
Variations in dividers |
Paper title and references due |
|
Tues.
5/20 |
16 |
Division by convergence |
|
|
Thur.
5/22 |
17-18 |
Floating-point
numbers and operations |
HW#3 due |
|
Tues.
5/27 |
19-20 |
Errors, precision, and certifiability |
HW#4 posted
(chapters 17-22) |
|
Thur.
5/29 |
21 |
Square-rooting
methods |
Paper abstract and outline due |
|
Tues.
6/3 |
22 |
CORDIC algorithms |
|
|
Thur. 6/5 |
23-24 |
Other
topics in function evaluation |
HW#4 due |
|
Mon. 6/9 |
1-24
|
Final
exam: open book (12-3 PM) |
Held in class, Complete
paper due |
Homework:
General Requirements
Solutions should be brought to class on the due date
and handed in before the lecture begins.
Late
homework will not be accepted, so plan to start work on your assignments early.
Use
a cover page that includes your name, course and assignment number for your
solutions.
Staple
the sheets and write your name on top of every sheet in case sheets are
separated.
Although
some cooperation is permitted, direct copying will have severe consequences.
ECE 252B s2008, Homework #1: Number Systems and Addition (chaps. 1-7, due Thur.
April 17)
Do the following problem from the textbook or listed below: 1.I
[20 pts.], 3.9a [15 pts.], 5.3 [10 pts.], 5.8 [15 pts.], 6.3 [15 pts.], 7.7 [25
pts]
Problem 1.I (Fixed-radix positional number systems) Let
Nk,r be an integer whose representation in
radix r consists of k digits of 1, that is, Nk,r
= (1 1 . . . 1)r, where the number of 1 digits is k.
(a) Show the 2k-bit radix-2 representation of the square of Nk,2.
(b) Prove that except for N1,10, no Ni,10
is a perfect square. (c)
Show that Ni,10 divides Nj,10
iff i divides j.
ECE
252B s2008, Homework #2: Multioperand Addition and Multiplication (chaps. 8-11, due Thur. May
1)
Do the following problem from the textbook: 8.7
[15 pts.], 8.12 [20 pts.], 9.9a [10 pts.], 9.12 [20 pts.], 10.1 [15 pts.], 11.10 [20
pts]
ECE
252B s2008, Homework #3: Multiplication and Division (chaps. 12-16, due Thur.
May 22)
Do the following problem from the textbook: 12.13
[15 pts.], 12.15 [15 pts.], 13.5a [10 pts.], 13.12a [15 pts.], 14.8 [20 pts.], 15.5 [10
pts], 16.12 [15 pts.]
ECE
252B s2008, Homework #4: Floating-Point and Function Evaluation (chaps. 17-22, due Thur. June
5)
Do the following problem from the textbook: 17.7 [15 pts.],
18.6bc [15 pts.], 19.7 [20 pts.], 20.2 [10 pts.], 21.2b [20 pts.], 22.2c [20
pts.]
ECE 252B s2008, Notes
on homework solutions and other topics
For HW2, Problem 12.13c, the suggested substitutions (essentially
the same as for the Baugh-Wooley method) applied to the simplified bit-matrix of
part b yields the following in columns 4-6 (column 7 is ignored because the
square is always positive, and columns 0-3 do not change). Column 4: x3, x2x1',
x3x0'. Column 5: x2x1, x3x1'. Column 6: x3, x3x2'. The required circuit consists
of a 3-bit CSA and a 4-bit adder (or, equivalently, a 4-bit CSA and a 3-bit
adder). Ignore the last sentence in the solution handout, as it is incorrect.
For HW2, Problem 13.12, the term 1 + 2^(-36) and the associated
shift-add step are not needed, given 32 bits of precision.
ECE 252B s2008, Possible Research Topics
1. Mod-(2a + 1) Number Representations and
Arithmetic
2. A Survey of Hardware Multipliers in Microprocessors
3. Radix-16 SRT Division in Intel's New Penryn Processors
4. Augmenting FPGAs for Faster Arithmetic Operations
5. Cube Roots: Hardware Algorithms and Applications
6. Accurate Summation of Sets of Floating-Point Numbers
7. Function Evaluation by Piecewise Linear Approximation
8. Smaller Lookup Tables via Nonuniform Segmentation
9. Arithmetic in the European
Logarithmic Microprocessor
10. Arithmetic in IBM's Blue Gene/L Parallel Supercomputer
ECE 252B s2008, Midterm
Exam Preparation
Textbook
sections
that are not required for the closed-book midterm exam: 3.5, 3.4, 3.6,
4.4, 4.5, 4.6, 6.3, 7.2, 10.5 (some of these may be included in the final exam, which
will be open-book)
ECE 252B s2008,
Final Exam Preparation
The
final exam will include Chapters 1-24, emphasizing the topics covered
after the midterm. The following sections are excluded: 3.5
(pp.
45-48), 3.6, 4.4, 4.5, 4.6, 7.2, 10.5, 15.4, 15.6, 19.4,
19.5, 19.6, 20.2, 21.4, 21.6, 22.6, 23.4, 24.4-24.6. All other sections are included, even if they were not discussed in class.
Return to:
Top of this page || Go up to: B.
Parhami's course syllabi or his
home page
|
