ECE
252B: Information on Previous Offerings
Behrooz
Parhami: 2007/06/19
|| E-mail: parhami@ece.ucsb.edu ||
Problems:
webadmin@ece.ucsb.edu
Other
contact info at: Bottom
of this page || Go up to: B.
Parhami's course syllabi or his
home page
On
June 19, 2007, Professor Parhami's UCSB ECE website moved to a new location. For
an up-to-date version of this page, visit it at the new address:
http://www.ece.ucsb.edu/~parhami/ece_252b_old.htm
Previous offerings of ECE 252B
Return to:
Top of this page
ECE 252B: Fall Quarter 2005 offering
This area is reserved for important course
announcements: The course was cancelled for the fall 2005 quarter; its next offering will be in
Spring 2007.
Return to:
Top of this page
ECE 252B: Winter Quarter 2005 offering
This area is reserved for important course
announcements: A new special issue of IEEE Trans. Computers
has just appeared (March 2005), leading to an update in the References section.
Some electronic resources have also been added to the References section.
Course grades were assigned and reported on 2005/03/15.
Course: |
ECE
252B – Computer Arithmetic, University of California, Santa Barbara,
Winter 2005, Enrollment Code 54320. This has been a fall-quarter course in
the past few years and may revert to that schedule next year. |
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. (F)
|
Instructor: |
Behrooz
Parhami, Room 5155 Engineering I, Phone
805-893-3211, parhami@ece.ucsb.edu
|
Meetings: |
MW
10:00-11:30, Room 3519 Phelps Hall |
Consultation: |
Open
office hours, held in Room 5155 Engineering I – M 11:40-1:00, W
12:30-2:00 |
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
(available at the bookstore in December 2004)
Parhami,
B., Computer Arithmetic: Algorithms
and Hardware Designs, Oxford, 2000. The Bookstore has been
instructed to order the 4th 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 Web page
(accessible via the link above).
Other
useful
books,
not required
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).
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 |
Mon.
1/3 |
1-2 |
Numbers
and signed values |
|
Wed. 1/5 |
3-4 |
Redundant
and residue systems |
|
Mon. 1/10 |
5-6 |
Basic and carry-lookahead addition |
HW#1
posted (chapters 1-7) |
Wed. 1/12 |
6-7 |
Other topics in fast addition |
Research
topic defined |
Mon. 1/17 |
|
Dr. King's birthday
-- no lecture |
|
Wed. 1/19 |
8 |
Multioperand
addition |
HW#1 due |
Mon. 1/24 |
9 |
Basic
multiplication schemes |
HW#2 posted (chapters
8-12) |
Wed. 1/26 |
10-11 |
High-radix and tree multipliers |
|
Mon.
1/31 |
11-12 |
Other topics in multiplication |
Preliminary references due |
Wed. 2/2 |
|
Review and make-up |
HW#2 due |
Mon. 2/7 |
1-12 |
Midterm
exam: closed book (10-12 AM) |
Held in class; note
extended time |
Wed.
2/9 |
13 |
Basic
division schemes |
HW#3 posted (chapters
13-16) |
Mon. 2/14 |
14-15 |
High-radix
division |
|
Wed. 2/16 |
15-16 |
Other topics in division |
Paper title and references due |
Mon. 2/21 |
|
President's day
holiday -- no lecture |
|
Wed. 2/23 |
17-18 |
Floating-point
numbers and operations |
HW#3 due |
Mon.
2/28 |
19-20 |
Errors, precision, and certifiability |
HW#4 posted
(chapters 17-22) |
Wed. 3/2 |
21 |
Square-rooting
methods |
Paper abstract and outline due |
Mon. 3/7 |
22 |
CORDIC algorithms |
|
Wed. 3/9 |
23-24 |
Other
topics in function evaluation |
HW#4 due |
Mon. 3/14 |
1-24
|
Final
exam: open book (8:30-11 AM) |
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 w2005, Course
Grade Stats
Item |
Out of |
Max |
Mean |
Median |
Min |
SD |
HW #1 |
100 |
80 |
62 |
61 |
47 |
n/a |
HW #2 |
100 |
82 |
67 |
74 |
37 |
n/a |
HW #3 |
100 |
96 |
82 |
76 |
74 |
n/a |
HW #4 |
100 |
86 |
79 |
82 |
66 |
n/a |
Midterm |
100 |
82 |
57 |
55 |
36 |
n/a |
Final/Paper |
100 |
83 |
70 |
69 |
59 |
n/a |
Course* |
100 |
83 |
65 |
60 |
58 |
n/a |
Course |
A (4.0) |
A+ |
3.3 |
3.0 |
B |
n/a |
*
Course = 20%(HW total / 4) + 30%(Midterm) + 50%(Final or Paper)
ECE 252B w2005, Homework #1: Number Systems and Addition (chap. 1-7, due Wed.
Jan. 19)
Do the following problems from the textbook or defined below: 2.1
[20 pts.], 3.11 [15 pts.], 5.A [15 pts.], 6.F [10 pts], 7.13
[20 pts.], 7.15 [20 pts.]
Problem 5.A Binary adders as versatile building
blocks -- Show how to use a 4-bit binary adder as: (a) A multiply-by-3 circuit
for a 4-bit unsigned number. (b)
Two independent 3-input majority circuits implementing 2-out-of-3 voting.
Problem 6.F Implementing the carry operator --
Show that the carry operator of
Fig. 6.6 can be implemented by using g = (g˘
Ú
g˛)(p˛
Ú
g˛),
thereby making all signals for p and g go through two levels of
logic using a NOT-NOR or NOR-NOR implementation.
ECE
252B w2005, Homework #2: Multioperand Addition and Multiplication (chap. 8-12, due
Wed. Feb. 2)
Do the following
problems from the textbook or defined below: 8.15 [25 pts.], 9.4c [20 pts],
9.15 [15 pts.], 10.5 [10 pts.], 11.E [15 pts.], 12.16 [15 pts.]
Problem 11.E
Unsigned/2’s-complement tree multiplier – Most processors allow both unsigned
and signed numbers as operands in their integer arithmetic units. Discuss the
design of a k
´
k tree multiplier that can act as an unsigned multiplier (for t =
0) or 2’s-complement multiplier (for t = 1), where t is a control
signal.
ECE
252B w2005, Homework #3: Division (chap. 13-16, due Wed. Feb. 23)
Do the following
problems from the textbook or defined below: 13.7b [20 pts.], 13.D [20 pts.],
14.2d [20 pts], 15.13abc [20 pts.], 16.A [20 pts.]
Problem 13.D Sequential division –
Perform the unsigned binary
division .
1100 1100
1100 / .
1001 11 by means
of the restoring algorithm. Hint: Watch for overflow.
Problem 16.A Sequential vs convergence
division – Suppose multiplication and addition take 5 and 1 time units,
respectively, and that all support and control functions (counting,
conditionals, register transfers, etc.) take negligible time due to overlapped
processing. Be brief and state all your assumptions clearly. (a) Express the
time needed for simple binary restoring division as a function of the word width
k. (b) Express the time needed for division by repeated multiplications
(without an initial table lookup or other speedup methods) as a function of k.
(c) Compare the results of parts a and b. Comment on the speed/cost tradeoffs
for different word widths.
ECE
252B w2005, Homework #4: Floating-Point and Function Evaluation (chap. 17-22, due
Wed. Mar. 9)
Do the
following problems from the textbook or defined below: 17.11 [20 pts.], 18.F
[20 pts.], 20.3 [20 pts.], 21.2a [20 pts.], 22.2ab [20 pts.]
Problem 18.F Monotonicity in floating-point
arithmetic – This problem is attributed to W. Kahan. Consider a computer that
performs floating-point multiplication by truncating (rather than rounding) the
exact 2p-digit product of p-digit normalized fractional
significands to p digits; that is, it either does not develop the lower p
digits of the exact product, or simply drops them. (a) Show that, for a radix
r greater than 2, this causes the monotonicity of multiplication to be
violated (i.e., there exist positive floating-point numbers a, b,
and c such that a < b but a
´fp
c > b
´fp c).
Hint: when x
´fp
y < 1/r, postnormalization
causes the least significant digit of the final product to be 0. (b) Show that
multiplication remains monotonic in radix 2 (i.e., a
Ł
b implies a
´fp
c Ł
b ´fp
c).
ECE 252B w2005, Notes
on homework solutions and other topics
None.
ECE
252B w2005, Possible
Research Topics
Given that no student has chosen the research path in lieu of the
final exam, this section will not be updated for the current quarter.
ECE 252B w2005, Midterm
Exam Preparation
Textbook
sections
that are not required for the closed-book midterm exam: 3.5, 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 w2005, 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, 24.6. All other sections are included, even if they were not discussed in class.
Return to:
Top of this page
ECE 252B: Fall Quarter 2003 offering
Course: |
ECE
252B – Computer Arithmetic, University of California, Santa Barbara,
Fall 2003, Enrollment Code 11106 |
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. (F)
|
Instructor: |
Behrooz
Parhami, Room 5155 Engineering I, Phone
805-893-3211, parhami@ece.ucsb.edu
|
Meetings: |
MW
4:00-5:30 PM, Room 1425 Phelps Hall |
Consultation: |
Open
office hours, held in Room 5155 Engineering I – M 11:00-12:30, W
12:30-2:00 |
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
(available at the bookstore in September)
Parhami,
B., Computer Arithmetic: Algorithms
and Hardware Designs, Oxford, 2000. The Bookstore has been
instructed to order the 4th 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 Web page
(accessible via the link above).
Other
useful
books,
not required
Swartzlander,
Computer Arithmetic, vols. 1-2,
IEEE Computer Soc. Press (QA76.6.C633).
Koren, Computer Arithmetic
Algorithms, Prentice-Hall,
1993 (QA76.9.C62K67).
Omondi,
Computer Arithmetic Systems: . . . ,
Prentice-Hall, 1994 (QA76.9.C62O46).
Ercegovac/Lang,
Digital Arithmetic, Morgan Kaufmann, 2004
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). |
Evaluation: |
Students
will be evaluated based on the following three components with the given
weights:
|
|
25%
-- Homework (see the course calendar for general requirements and
schedule). |
|
25%
-- 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 |
Mon.
9/22 |
1-2 |
Numbers
and signed values |
|
Wed.
9/24 |
3 |
Redundant
number representations |
HW#1
posted (chapters 1-4) |
Mon.
9/29 |
4 |
Residue
number systems |
|
Wed.
10/1 |
5 |
Basic addition and
counting |
HW#2 posted (5-6), HW#1 due |
Mon.
10/6 |
6 |
Carry-lookahead adders |
Research
topic defined |
Wed.
10/8 |
7 |
Variations
in fast adders |
HW#3 posted (7-8), HW#2 due |
Mon.
10/13 |
8 |
Multioperand
addition |
|
Wed.
10/15 |
9 |
Basic
multiplication schemes |
HW#4 posted
(9-10) |
Mon.
10/20 |
10 |
High-radix multiplication |
HW#3 due,
Preliminary ref's due |
Wed.
10/22 |
11 |
Tree
and array multipliers |
|
Mon.
10/27 |
12 |
Variations
in multipliers |
HW#5 posted (11-12),
HW#4 due |
Wed.
10/29 |
1-10 |
Midterm
exam: closed book (4-6 PM) |
Note
the extended time |
Mon.
11/3 |
13 |
Basic
division schemes |
|
Wed.
11/5 |
14
|
High-radix
division |
HW#6 posted
(13-14) |
Mon.
11/10 |
15 |
Variations
in dividers |
HW#5 due,
Paper
title & ref's due |
Wed.
11/12 |
16 |
Convergence
division |
HW#7 posted (15-16) |
Mon.
11/17 |
17-18 |
Floating-point
numbers & operations |
HW#6 due,
Prelim. abstract due |
Wed.
11/19 |
19-20 |
Errors,
precision, & certifiability |
HW#8 posted
(17-20) |
Mon.
11/24 |
21 |
Square-rooting
methods |
HW#7 due |
Wed.
11/26 |
|
No lecture due to Thanksgiving |
|
Mon.
12/1 |
22 |
The
CORDIC algorithms |
HW#8 due
|
Wed.
12/3 |
23-24 |
Other
topics in function evaluation |
Complete
paper due
|
Thur.
12/11 |
1-24
|
Final
exam: open book (4:00-7:00 PM) |
Place:
our regular classroom |
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.
Course
Grade Stats
Item |
Out of |
Max |
Mean |
Median |
Min |
SD |
HW #1 |
100 |
86 |
56 |
56 |
37 |
17 |
HW #2 |
100 |
78 |
63 |
60 |
48 |
10 |
HW #3 |
100 |
92 |
78 |
82 |
58 |
12 |
HW #4 |
100 |
98 |
79 |
74 |
67 |
11 |
HW #5 |
100 |
83 |
61 |
61 |
46 |
13 |
HW #6 |
100 |
98 |
88 |
90 |
76 |
9 |
HW #7 |
100 |
82 |
57 |
60 |
23 |
24 |
HW #8 |
100 |
73 |
56 |
53 |
40 |
12 |
Midterm |
100 |
80 |
71 |
70 |
62 |
7 |
Final/Paper |
100 |
77 |
65 |
60 |
57 |
9 |
Course* |
100 |
75 |
67 |
67 |
62 |
5 |
Course |
A (4.0) |
A |
3.3 |
B+ |
B |
0.41 |
*
Course = 25%(HW total / 8) + 25%(Midterm) + 50%(Final or Paper)
ECE
252B f2003, Homework #1: Number Representation (chapters 1-4, due Wed. Oct. 1)
Do
the following problems from the textbook: 1.3, 1.11, 2.13, 3.4a (part a only),
4.2
ECE
252B f2003, Homework #2: Basic & Carry-Lookahead Addition (chapters 5-6, due
Wed. Oct. 8)
Do
the following problems from the textbook: 5.6def, 5.10, 6.5, 6.12, 6.16
ECE
252B f2003, Homework #3: Other Addition Topics (chapters 7-8, due Mon. Oct. 20)
Do
the following problems from the textbook or defined below: 7.6, 7.8, 7.C, 8.11,
8.B
Problem
7.C (Carry-skip versus carry-select adders): Compare the costs and delays of
16-bit single-level carry-skip and carry-select adders, each constructed from
4-bit adder blocks and additional logic as needed. Which design would you
consider more cost-effective and why? State all your assumptions clearly.
Problem
8.B (carry-save adder trees): a. Show the widths of the four CSAs
required to reduce six 32-bit unsigned binary numbers to two. b.
Repeat part a, but assume that the six 32-bit unsigned numbers are the partial
products of a 32-by-6 multiplication (i.e., they are not aligned at the LSBs but
shifted to the left by 0, 1, 2, 3, 4, and 5 bits).
ECE
252B f2003, Homework #4: Basic & High-Radix Multiplication (chapters 9-10, due
Mon. Oct. 27)
Do
the following problems from the textbook: 9.3, 9.9b, 9.16, 10.8a, 10.9
ECE
252B f2003, Homework #5: Other Multiplication Topics (chapters 11-12, due Mon.
Nov. 10)
Do the following problems from the textbook: 11.10, 11.12, 12.1, 12.9*
* Correction to Problem 12.9: Change 2k
- 2j + 1 to 2k
- 2j
- 1
ECE
252B f2003, Homework #6: Basic & High-Radix Division (chapters 13-14, due
Mon. Nov. 17)
Do the following problems from the textbook or defined below:
13.14, 13.A,
14.1cd, 14.5
Problem 13.A
(sequential division):
Perform the unsigned fractional binary division .0110 1101 / .1011 using the
restoring and nonrestoring methods
ECE
252B f2003, Homework #7: Other Division Topics (chapters 15-16, due Mon. Nov.
24)
Do the following problems from the textbook or defined below:
15.2, 15.B, 16.7, 16.13
Problem 15.B
(radix-8 division):
Argue that the use of the quotient digit set
[–6, 6] is preferable to the minimal digit set [–4, 4] in a radix-8 divider that
forms the multiple 3d by inputting the two values 2d and d
into a four-input carry-save adder tree that also receives the carry-save
partial remainder as inputs.
ECE
252B f2003, Homework #8: Floating-Point Arithmetic (chapters 17-20, due Mon.
Dec. 1)
Do the following problems from the textbook or defined below:
17.12, 17.C, 18.3, 19.15, 20.2
Problem 17.C
(Logarithmic number systems):
Consider an 8-bit unsigned number system in which the base-2 logarithm is
represented with k = 3 whole and l = 5 fractional bits. a.
What is the range of this number system? b. What is the maximum
relative representation error for numbers within the above range? c.
Represent the numbers x = 7 and y = 11 as accurately as possible
in this number system.
Additional Practice Problems (chapters 21-24)
Because we have not done any homework on Chapters 21-24 of the
textbook, the following problems are recommended for practice: 21.9a, 21.15,
22.5, 23.4, 24.5
Notes
on homework solutions and other topics
A
better solution to Problem 6.12 is based on the delay and cost recurrences D(k)
= D(floor(k/2)) + 2 and C(k) = C(floor(k/2))
+ k - 1 for a Brent-Kung network of general
width k (not necessarily a power of 2).
In the solution handed out for Problem 11.12, the following
corrections are needed for parts b and c. A couple of these are due to simple
miscounting; one is due to the fact that in Wallace trees, HAs should not be
used unless not doing so would increase the latency (number of levels).
Part b, line 5 -- 3 HAs; line 6 -- . . . 1 3 1
1 1 9-bit adder; line 7 -- 7 HAs + 9-bit adder
Part c, line 5 -- 4 FAs + 3 HAs; line 7 -- 21 FAs + 7 HAs
ECE
252B f2003, Possible
Research Topics
In
the following, IEEETC-7/2000 refers to the latest computer arithmetic special
issue of IEEE Trans. Computers published in July 2000 and
ARITH-2001 (2003) stands for the Proc. 15th (16th) IEEE Symp. Computer Arithmetic held
in June 2001 (June 2003).
1.
Design of parallel-prefix adders, IEEETC-7/2000 pp. 659-680, ARITH-2001 pp.
218-225 + 277-284.
2.
Fast multiplication and powering, IEEETC-7/2000 pp. 681-701, ARITH-2001 pp.
23-39 + 73-79, ARITH-2003 pp. 204-211.
3.
Floating-point normalization and rounding, IEEETC-7/2000 pp. 638-658, ARITH-2001
pp. 7-12 + 173-194, ARITH-2003 pp. 95-103.
4.
Logarithmic arithmetic units, IEEETC-7/2000 pp. 702-726, ARITH-2001 pp. 229-245,
ARITH-2003 pp. 253-261; Also [Cole00].
5.
Function evaluation by table lookup, ARITH-2001 pp. 101-108 + 128-135,
ARITH-2003 pp. 114-121
6.
Arithmetic for cryptography, IEEETC-7/2000 pp. 740-758, ARITH-2001 pp. 59-65,
ARITH-2003 pp. 174-202.
Midterm
Exam Preparation
Textbook
sections
that are not required for the closed-book midterm exam: 3.5, 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)
Final
Exam Preparation
The
final exam will include Chapters 1-19 and 21-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,
21.4, 21.6, 22.6. All other sections are included, even if they were not discussed in class.
Return to:
Top of this page
ECE 252B: Fall Quarter 2002 offering
Course: |
ECE
252B – Computer Arithmetic, University of California, Santa Barbara,
Fall 2002, Enrollment Code 11700 |
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. (F)
|
Instructor: |
Behrooz
Parhami, Room 5155 Engineering I, Phone
805-893-3211, parhami@ece.ucsb.edu
|
Meetings: |
MW
4:00-5:30 PM, Room 1425 Phelps Hall |
Consultation: |
Open
office hours, held in Room 5155 Engineering I – M 11:00-12:30, W
12:30-2:00 |
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
(available at the bookstore)
Parhami,
B., Computer Arithmetic: Algorithms
and Hardware Designs, Oxford, 2000 (use the link to get
information on the textbook and its errata).
Other
books,
not required
Swartzlander,
Computer Arithmetic, vols. 1-2,
IEEE Computer Soc. Press (QA76.6.C633).
Koren, Computer Arithmetic Algorithms, Prentice-Hall,
1993 (QA76.9.C62K67).
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
Algor's (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). |
Evaluation: |
Students
will be evaluated based on the following three components with the given
weights:
|
|
25%
-- Homework (see the course calendar for general requirements and
schedule). |
|
25%
-- 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 |
Mon.
9/30/02 |
1-2 |
Numbers
and signed values |
|
Wed.
10/2/02 |
3-4 |
Redundant
and RNS representations |
HW#1
posted (chapters 1-4) |
Mon.
10/7/02 |
5 |
Basic addition and
counting |
|
Wed.
10/9/02 |
6 |
Carry-lookahead adders |
HW#2
posted (5-6), HW #1 due |
Mon.
10/14/02 |
7 |
Variations
in fast adders |
Research
topic defined |
Wed.
10/16/02 |
8 |
Multioperand
addition |
HW#3
posted (7-8), HW #2 due |
Mon.
10/21/02 |
9 |
Basic
multiplication schemes |
|
Wed.
10/23/02 |
10 |
High-radix multiplication |
HW#4
posted (9-10), HW #3 due |
Mon.
10/28/02 |
11 |
Tree
and array multipliers |
Preliminary
references due |
Wed.
10/30/02 |
12 |
Variations
in multipliers (begins by 4:15) |
HW
#4 due |
Mon.
11/4/02 |
1-10 |
Midterm
exam: closed book (4-6 PM) |
Note
the extended time |
Wed.
11/6/02 |
|
Instructor
at conference:
No lecture |
HW#5
posted (11-12) |
Mon.
11/11//02 |
|
Veterans'
Day Holiday:
No lecture |
|
Wed.
11/13/02 |
13 |
Basic
division schemes |
HW#6
posted (13-14), HW #5 due |
Mon.
11/18/02 |
14
|
High-radix
division |
Paper
title and references due |
Wed.
11/20/02 |
15-16 |
Other
division topics |
HW#7
posted (15-16), HW
#6 due |
Mon.
11/25/02 |
17-18 |
Floating-point
numbers & operations |
Preliminary
paper abstract due |
Wed.
11/27/02 |
19-20 |
Errors,
precision, & certifiability |
HW#8
posted (17-20), HW
#7 due |
Mon.
12/2/02 |
21 |
Square-rooting
methods |
|
Wed.
12/4/02 |
22 |
The
CORDIC algorithms |
HW
#8 due
|
Mon.
12/9/02 |
23-24 |
Other
topics in function evaluation |
Complete
paper due
|
Wed.
12/11/02 |
1-22
|
Final
exam: open book (4-7 PM) |
Phelps
1425 (our regular classroom) |
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.
Course
Grade Stats
Item |
Out of |
Max |
Mean |
Median |
Min |
SD |
HW #1 |
100 |
94 |
74 |
81 |
32 |
18 |
HW #2 |
100 |
98 |
75 |
84 |
30 |
26 |
HW #3 |
100 |
95 |
70 |
70 |
50 |
14 |
HW #4 |
100 |
96 |
83 |
86 |
42 |
17 |
HW #5 |
100 |
100 |
79 |
78 |
63 |
11 |
HW #6 |
100 |
100 |
87 |
87 |
72 |
8 |
HW #7 |
100 |
90 |
69 |
70 |
46 |
14 |
HW #8 |
100 |
90 |
77 |
80 |
51 |
13 |
Midterm |
100 |
83 |
73 |
74 |
63 |
7 |
Final/Paper |
100 |
90 |
72 |
69 |
57 |
13 |
Course* |
100 |
87 |
75 |
73 |
61 |
10 |
Course |
A (4.0) |
A+ |
3.3 |
B |
C+ |
0.66 |
*
Course = 25%(HW total / 8) + 25%(Midterm) + 50%(Final or Paper)
ECE
252B f2002, Homework #1: Number Representation (chapters 1-4, due Wed. Oct. 9)
Do
the following problems from the textbook: 1.4, 2.5, 2.7, 3.2, 4.3
ECE
252B f2002, Homework #2: Basic & Carry-Lookahead Addition (chapters 5-6, due
Wed. Oct. 16)
Do
the following problems from the textbook or defined below: 5.5e-h,
5.D, 6.3, 6.15, 6.H
Problem
5.D
Full adder hardware realization
Realize
a full adder by means of a minimum number of 2-to-1 multiplexers and no other
logic component (not even inverters).
Problem
6.H
Designing fast comparators
Given
a fast carry network of any design, show how it can be used to build a fast
comparator to determine if x > y, where x and y
are unsigned binary integers.
ECE
252B f2002, Homework #3: Other Addition Topics (chapters 7-8, due Wed. Oct. 23)
Do
the following problems from the textbook or defined below: 7.7, 7.18, 8.9, 8.14,
8.A
Problem
7.18
Correction In
part c, fractional precision modes are 4 ´
(8-bit) or 2 ´
(16-bit).
Problem
8.A
Generalized parallel counters
(a)
Show an implementation of a (5, 5; 4)-counter using (3;
2)-counters. (b) One level of (5, 5; 4)-counters can be used
to reduce five operands to two. What is the maximum number of operands that can
be reduced to two when two levels of (5, 5; 4)-counters are used? (c)
Generalize the result of part b to a counter that reduces x columns
of n dots to a 2x-bit result.
ECE
252B f2002, Homework #4: Basic & High-Radix Multiplication (chapters 9-10, due
Wed. Oct. 30)
Do
the following problems from the textbook or defined below: 9.11,
9.14e-g,
9.D,
10.3,
10.A
Problem
9.14
Correction The
last three parts should be labeled e, f, and g.
Problem
9.D
Sequential
2’s-complement multiplication
(a)
Represent x = 3, y = –3, and z = 5 as 4-bit,
2’s-complement numbers. (b) Compute x ´
z to get the 8-bit product, using the sequential algorithm with right
shifts. (c)
Compute y ´
z to get the 8-bit product, using the sequential algorithm with left
shifts.
Problem
10.A
Radix-4
Booth’s recoding Show
that radix-4 Booth’s recoding is equivalent to the following scheme:
(1)
Begin with a radix-4 operand employing the standard digit set [0, 3].
(2) Rewrite each 2 (3) digit as –2 (–1), with a radix-4 transfer of 1
to the next higher position. This results in an interim digit set [–2, 1].
(3)
Add the transfers to the interim digits to obtain the recoded number with
the digit set [–2, 2]. At the most significant end, ignore the outgoing
transfer for a 2’s-complement operand.
ECE
252B f2002, Homework #5: Other Multiplication Topics (chapters 11-12, due Wed.
Nov. 13)
Do
the following problems from the textbook or defined below: 11.1,
11.11a, 12.2, 12.12, 12.F
Problem
12.F
Building larger AMMs
A
6 ´
2 AMM computes an 8-bit value p = a ´
x + b
+ y, where a
and b (x and y)
are 6-bit (2-bit) unsigned numbers. Using dot notation, show how three such AMMs
can be used to build a 6 ´
6 AMM having two 6-bit multiplicative and two 6-bit additive inputs and
producing a 12-bit result.
ECE
252B f2002, Homework #6: Basic & High-Radix Division (chapters 13-14, due
Wed. Nov. 20)
Do
the following problems from the textbook or defined below: 13.5bc,
13.12bc, 13.C, 14.1ab, 14.10ab
Problem
13.C
Sequential nonrestoring division
Apply
the following modified form of nonrestoring division to the unsigned division
.101/.110. In each iteration, the shifted partial remainder is compared to ±d;
if it is ł
d (< –d),
qi
= 1 (-1)
is chosen; otherwise, qi
is set to 0. What do you think of this algorithm?
ECE
252B f2002, Homework #7: Other Division Topics (chapters 15-16, due Mon. Nov.
27)
Do
the following problems from the textbook or defined below: 15.6,
15.11, 15.12, 16.3, 16.A
Problem
16.A
Sequential
versus
convergence division
Suppose
multiplication and addition take 5 and 1 time units, respectively, while all
support and control functions (counting, conditionals, register transfers, etc.)
take negligible time due to overlapped processing. Be brief and state all your
assumptions clearly.
(a)
Express
the time needed for simple binary restoring division as a function of the word
width k. (b) Express
the time needed for division by repeated multiplications (without an initial
table lookup or other speedup methods) as a function of k. (c)
Compare the results of parts a and b. Comment on the speed/cost tradeoffs
for different word widths.
ECE
252B f2002, Homework #8: Floating-Point Arithmetic (chapters 17-20, due Mon.
Dec. 4)
Do
the following problems from the textbook or defined below: 17.10,
17.15, 18.6bc, 19.C, 20.2
Problem
19.C
Backward
error analysis
Suppose
we compute x4
by squaring x and again squaring the
result. Each squaring operation is done via a floating-point multiplication.
Show that the computed result is z =
[(1 + r)x]4
and establish a bound on the magnitude of r.
Notes
on homework solutions and other topics
Practice
problems from Chapters 21-22 (solutions will be handed out by 2002/12/9): 21.9a, 21.11, 22.1,
22.12
ECE
252B f2002, Possible
Research Topics
The
following is from the previous offering of the course in fall 2001. It will be
updated early in the fall quarter to reflect new topics and references.
In
the
following, IEEETC-7/2000 refers to the latest computer arithmetic
special issue of IEEE Trans. Computers published in July 2000 and
ARITH-2001 stands for the Proc. 15th IEEE Symp. Computer Arithmetic held
in June 2001.
1.
Design of parallel-prefix adders, IEEETC-7/2000 pp. 659-680, ARITH-2001 pp.
218-225 + 277-284.
2.
Fast multiplication and squaring, IEEETC-7/2000 pp. 681-701, ARITH-2001 pp.
23-39 + 73-79.
3.
Floating-point normalization and rounding, IEEETC-7/2000 pp. 638-658, ARITH-2001
pp. 7-12 + 173-194.
4.
Logarithmic arithmetic units, IEEETC-7/2000 pp. 702-726, ARITH-2001 pp. 229-245.
Also [Cole00].
5.
Function evaluation by table lookup, ARITH-2001 pp. 101-108 + 128-135
6.
Arithmetic for cryptography, IEEETC-7/2000 pp. 740-758, ARITH-2001 pp. 59-65.
Midterm
Exam Preparation
Textbook
sections
that are not required for the closed-book midterm exam: 3.5 (pp. 45-48), 3.6,
4.4, 4.5, 4.6, 6.3, 7.2 (some of these may be included in the final exam, which
will be open-book)
Final
Exam Preparation
The
final exam will include Chapters 1-19 and 21-22, 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, 15.4, 15.6, 19.4,
21.4, 21.6, 22.6. All other sections are included, even if they were not discussed in class.
Return to:
Top of this page
ECE 252B: Fall Quarter 2001 offering
Course: |
ECE
252B – Computer Arithmetic, University of California, Santa Barbara,
Fall 2001, Enrollment Code 58859 |
Instructor: |
Behrooz
Parhami, Room 5155 Engineering I, Phone
805-893-3211, parhami@ece.ucsb.edu
|
Meetings: |
MW
4:00-5:30 PM, Room 1174 HSSB |
Consultation: |
Open
office hours, held in Room 5155 Engineering I – M 9-10, W 1-2, R 3-4 |
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
(available at the bookstore)
Parhami,
B., Computer Arithmetic: Algorithms
and Hardware Designs, Oxford, 2000 (use the link to get
information on the textbook and its errata).
Recommended
book
(available at the bookstore, also to be put on 2-hour reserve)
Flynn/Oberman,
Advanced Computer Arithmetic Design, Wiley, 2001 (TK7895.A65F59).
Other
books,
not required
(* indicates that the book is to be put on 2-hour reserve)
*von
zur Gathen/Gerhard, Modern Computer Algebra, Cambridge, 1999.
*Swartzlander,
Computer Arithmetic, vols. 1-2,
IEEE Computer Soc. Press (QA76.6.C633).
*Koren, Computer Arithmetic Algorithms, Prentice-Hall,
1993 (QA76.9.C62K67).
*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
Algor's (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). |
Evaluation: |
Students
will be evaluated based on the following three components with the given
weights:
|
|
25%
-- Homework (see the course calendar for general requirements and
schedule). |
|
25%
-- 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 |
Mon.
9/24/01 |
1-2 |
Numbers
and signed values |
|
Wed.
9/26/01 |
3-4 |
Redundant
and RNS representations |
HW
#1
posted (chapters 1-4) |
Mon.
10/1/01 |
5 |
Basic addition and
counting |
|
Wed.
10/3/01 |
6 |
Carry-lookahead adders |
HW
#2
posted (5-6), HW #1 due |
Mon.
10/8/01 |
7 |
Variations
in fast adders |
Research
topic defined |
Wed.
10/10/01 |
8 |
Multioperand
addition |
HW
#3
posted (7-8), HW #2 due |
Mon.
10/15/01 |
9 |
Basic
multiplication schemes |
|
Wed.
10/17/01 |
10 |
High-radix multiplication |
HW#4
posted (9-10), HW #3 due |
Mon.
10/22/01 |
11 |
Tree
and array multipliers |
Preliminary
references due |
Wed.
10/24/01 |
12 |
Variations
in multipliers |
HW
#4 due |
Mon.
10/29/01 |
1-10 |
Midterm
exam: closed book (4-6 PM) |
HW
#5
posted (11-12) |
Wed.
10/31/01 |
13 |
Basic
division schemes |
|
Mon.
11/5//01 |
14
|
High-radix
division |
HW
#6
posted (13-14), HW #5 due |
Wed.
11/7/01 |
|
Instructor
at conference:
No lecture |
|
Mon.
11/12/01 |
|
Veterans'
Day Holiday:
No lecture |
Paper
title and references due |
Wed.
11/14/01 |
15 |
Variations
in dividers |
HW
#6 due |
Mon.
11/19/01 |
16 |
Division
by convergence |
HW
#7
posted (15-16) |
Wed.
11/21/01 |
17-18 |
Floating-point
numbers & operations |
Preliminary
paper abstract due |
Mon.
11/26/01 |
19-20 |
Errors,
precision, & certifiability |
HW
#8
posted (17-20), HW
#7 due |
Wed.
11/28/01 |
21 |
Square-rooting
methods |
|
Mon.
12/3/01 |
22 |
The
CORDIC algorithms |
HW
#8 due |
Wed.
12/5/01 |
23-24
|
Other
topics in function evaluation |
|
Fri. 12/7/01
|
1-22
|
Final
exam: open book (9AM-12PM) |
Complete
paper due
|
|
|
Final
to be held in Girvetz 1106 |
|
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 w2001, Homework #1: Number Representation (chapters 1-4, due Wed. Oct. 3)
Do
the following problems from the textbook: 1.1, 1.6, 2.3, 2.9, 3.7, 4.11
ECE
252B w2001, Homework #2: Basic & Carry-Lookahead Addition (chapters 5-6, due
Wed. Oct. 10)
Do
the following problems from the textbook: 5.3, 5.6abc, 5.7, 6.13
Additional
problem 6.C
Consider
a 16-bit carry-lookahead adder with 4-bit blocks. Assume that block p
and g signals are produced after 3
gate delays and that each block uses ripple-carry internally. The design uses a
lookahead carry generator with 2 gate delays. Carry ripples through each stage
in 2 gate delays and sum bits are computed in two gate delays once all the
internal carries are known. State your assumptions whenever the information
provided is not sufficient to answer the question.
a.
Compute
the total addition time, in terms of gate delays, for this 16-bit adder.
b.
We
gradually increase the adder width to 17, 18, 19, . . . bits using 4
ripple-carry groups of equal or approximately equal widths, while keeping the
block p and g
delay constant. At what word width k
would it be possible to increase the adder speed by using an additional level of
lookahead?
Bonus
(optional) problem for extra credit:
Problem 6.4 in the textbook.
ECE
252B w2001, Homework #3: Other Addition Topics (chapters 7-8, due Wed. Oct. 17)
Do
the following problems from the textbook: 7.13, 7.18, 8.12, 8.13
Additional
background and correction for Problem 7.18: Fractional precision is the opposite
of multiple precision. It is used when several low-precision numbers (such as
those found in multimedia data) are packed into a single word and processed in
parallel. Adding two such words, for example, has the effect of several
independent shorter additions. For this reason, the term "subword
parallelism" has also been used to describe this approach. Subword
arithmetic is often performed with saturation (see Problem 7.F below). In part c
of the problem, "(4 x 8)-bit or (2 x 16)-bit" should be "4 x
(8-bit) or 2 x (16-bit)".
Additional
Problem 7.F
In
certain applications, when the result of an arithmetic operation exceeds the
maximum allowed value, it would be inappropriate to generate the result modulo a
power of 2. For example, in media processing, we do not want addition of 1 to a
black pixel coded as FF in hexadecimal to turn it into a white pixel 00. Discuss
how two-operand addition can be performed with saturation so that whenever the
result exceeds 2^k – 1, the maximum value 2^k – 1 is produced
at output.
ECE
252B w2001, Homework #4: Basic & High-Radix Multiplication (chapters 9-10, due
Wed. Oct. 24)
Do
the following problems from the textbook: 9.4d, 9.10, 9.14abc, 10.1, 10.15
ECE
252B w2001, Homework #5: Other Multiplication Topics (chapters 11-12, due Wed.
Nov. 5)
Do
the following problems from the textbook: 11.3, 11.9, 11.17, 12.5a, 12.18
ECE
252B w2001, Homework #6: Basic & High-Radix Division (chapters 13-14, due
Wed. Nov. 14)
Do
the following problems from the textbook: 13.2, 13.9, 13.12d, 14.4cd (see below
), 14.14
Correction
to Problem 14.4: In all four parts, change the magnitude of the divisor d to
.1010
ECE
252B w2001, Homework #7: Other Division Topics (chapters 15-16, due Mon. Nov.
26)
Do
the following problems from the textbook: 15.3, 15.5, 16.6, 16.12
Additional Problem 15.B
Argue that the use of the quotient digit set [–6, 6] is preferable to the
minimal digit set [–4, 4] in a radix-8 divider that forms the multiple 3d
by inputting the two values 2d and d into a four-input carry-save
adder tree that also receives the carry-save partial remainder as inputs.
ECE
252B w2001, Homework #8: Floating-Point Arithmetic (chapters 17-20, due Mon.
Dec. 3)
Do
the following problems from the textbook: 17.4, 17.8, 18.5, 18.18, 19.5
Bonus
problem for extra credit: 20.4
ECE
252B f2001, Possible
Research Topics
In
the
following, IEEETC-7/2000 refers to the latest computer arithmetic
special issue of IEEE Trans. Computers published in July 2000 and
ARITH-2001 stands for the Proc. 15th IEEE Symp. Computer Arithmetic held
in June 2001.
1.
Design of parallel-prefix adders, IEEETC-7/2000 pp. 659-680, ARITH-2001 pp.
218-225 + 277-284.
2.
Fast multiplication and squaring, IEEETC-7/2000 pp. 681-701, ARITH-2001 pp.
23-39 + 73-79.
3.
Floating-point normalization and rounding, IEEETC-7/2000 pp. 638-658, ARITH-2001
pp. 7-12 + 173-194.
4.
Logarithmic arithmetic units, IEEETC-7/2000 pp. 702-726, ARITH-2001 pp. 229-245.
Also [Cole00].
5.
Function evaluation by table lookup, ARITH-2001 pp. 101-108 + 128-135
6.
Arithmetic for cryptography, IEEETC-7/2000 pp. 740-758, ARITH-2001 pp. 59-65.
Final
Exam Preparation
The
final exam will include Chapters 1-19 and 21-22, emphasizing the topics covered
after the midterm. The following sections are excluded: 4.4, 4.5, 4.6, 19.4,
22.6. All other sections are included, even if they were not discussed in class.
Return to:
Top of this page
ECE 252B: Winter Quarter 2001 offering
Course: |
ECE
252B – Computer Arithmetic, University of California, Santa Barbara,
Winter 2001, Enrollment Code 11270 |
Instructor: |
Behrooz
Parhami, Room 5155 Engineering I, Phone
805-893-3211, parhami@ece.ucsb.edu
|
Meetings: |
MW
(plus review sessions on F 2/9 and
3/16) 8:30-9:50 AM, Room 1160 Phelps Hall |
Consultation: |
Open
office hours, held in Room 5155 Engineering I – M 11-12, W 1-2, R 3-4 |
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
Parhami,
B., Computer Arithmetic: Algorithms
and Hardware Designs, Oxford, 2000 (use the link to get
information on the textbook and its errata).
Other
books
(not required)
Koren, Computer Arithmetic Algorithms, Prentice-Hall,
1993 (QA76.9.C62K67).
Omondi,
Computer Arithmetic Systems: . . . ,
Prentice-Hall, 1994 (QA76.9.C62O46).
Waser/Flynn,
Intro. to Arithmetic for Digital
Systems Designers (TK7895.A65W37.1982).
Knuth,
The Art
of Computer Programming: Seminumerical
Algor's (QA76.6.K64 vol 2).
Hwang,
Computer Arithmetic: Principles, Architecture, and Design
(TK7888.3.H9).
Swartzlander,
Computer Arithmetic, vols. 1-2,
IEEE Computer Soc. Press (QA76.6.C633).
Kulisch/Miranker,
Computer Arithmetic in Theory and
Practice (QA162.K84).
Ercegovac/Lang,
Division and Square Root: . . . , Kluwer, 1994 (QA76.9.C62E73).
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). |
Evaluation: |
Students
will be evaluated based on the following three components with the given
weights:
|
|
25%
-- Homework (see the course calendar for general requirements and
schedule). |
|
25%
-- 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 for
winter 2001 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 covered chapter(s) before
each lecture if possible.
Day
& Date |
Chap |
Lecture
Topic |
Deadlines
and Notes |
Mon.
1/8/01 |
1-2 |
Numbers
and signed values |
|
Wed.
1/10/01 |
3-4 |
Redundant
and RNS representations |
|
Mon.
1/15/01 |
|
Dr.
King's Birthday:
No lecture |
HW#1
posted (chapters 1-4) |
Wed.
1/17/01 |
5 |
Basic addition and
counting |
|
Mon.
1/22/01 |
6 |
Carry-lookahead adders |
HW#2
posted (5-6), HW #1 due |
Wed.
1/24/01 |
7 |
Variations
in fast adders |
Research
topic defined |
Mon.
1/29/01 |
8 |
Multioperand
addition |
HW#3
posted (7-8), HW #2 due |
Wed.
1/31/01 |
9 |
Basic
multiplication schemes |
|
Mon.
2/5/01 |
10 |
High-radix multiplication |
HW#4
posted (9-11), HW #3 due |
Wed.
2/7/01 |
11 |
Tree
and array multipliers |
Preliminary
references due |
Fri.
2/9/01 |
|
Review
(8:30-9:50 AM, 1160 Phelps) |
|
Mon.
2/12/01 |
12 |
Variations
in multipliers |
HW
#4 due |
Wed.
2/14/01 |
1-12 |
Midterm
exam: closed book (8-10 AM) |
|
Mon.
2/19/01 |
|
President's
Day:
No lecture |
HW#5
posted (12-13) |
Wed.
2/21/01 |
13 |
Basic
division schemes |
|
Mon.
2/26/01 |
14 |
High-radix
division |
HW#6
posted (14-16), HW #5 due |
Wed.
2/28/01 |
15-16 |
Other
division topics |
Paper
title and references due |
Mon.
3/5/01 |
17 |
Floating-point
numbers |
HW#7
posted (17-19), HW #6 due |
Wed.
3/7/01 |
18-19 |
Floating-point
operations and errors |
Preliminary
paper abstract due |
Mon.
3/12/01 |
21 |
Square-rooting
methods |
HW
#7 due |
Wed.
3/14/01 |
22 |
The
CORDIC algorithms |
|
Fri.
3/16/01 |
|
Review
(8:30-9:50 AM, 1160 Phelps) |
|
Mon.
3/19/01 |
1-22 |
Final
exam*: open book (8:30-11 AM) |
Complete
paper due by 12:00 noon |
|
|
*In
2162 Engr I, not our regular classroom |
|
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 w2001, Homework #1: Number Representation (chapters 1-4, due Mon. Jan. 22)
Do
the following five problems from the textbook:
1.2
(p. 15), 1.9 (p. 16), 2.10 (p. 32), 3.6 (p. 51), 4.5 (p. 70)
Hint
for Problem 1.9: Compute the weights associated with the first 16 positions of a
number.
Bonus
problem 1.D on number representation (for extra credit): We
want to build an abacus for use with the Roman numerals system. There are to be
seven positions labeled, from left to right, M, D, C, L, X, V, and I. Each
position is to have positive (black) and negative (red) beads to allow
representations such as MCDXXIV. What are the minimum required numbers of the
two types of beads in each position, given that all unsigned integers up to 1500
are to be representable?
ECE
252B w2001, Homework #2: Basic & Carry-Lookahead Addition (chapters 5-6, due
Mon. Jan. 29)
Do
the following five problems from the textbook:
5.5
parts j, l, m only (p. 88), 5.8 (p. 88), 5.9 (89), 6.1 (p. 104), 6.14 (p. 106)
ECE
252B w2001, Homework #3: Other Addition Topics (chapters 7-8, due Mon. Feb. 5)
Do
the following four problems from the textbook and part a of problem 7.E given
below:
7.4
(p. 121), 7.16 (p. 123), 8.6 (p. 138), 8.10 (p. 139)
Problem
7.E on self-timed carry-skip addition: (a) Apply the carry-skip idea to the
self-timed adder of Fig. 5.9, illustrating the result by drawing a block diagram
similar to that in Fig. 7.1 for a 16-bit carry-completion adder made of four
4-bit skip blocks. (b) [optional bonus part, for extra credit] Analyze the
expected carry completion time in the adder of part a, when blocks of fixed
width b are used to build a k-bit self-timed adder, and discuss
the practicality of this idea.
Note
(correction to the solution to Problem 3.6, part c): It was brought to my
attention that the proposed solution does not work when the number has leading
0s. In this case, the leftmost borrow of 1 will not be absorbed, leaving a
number with an invalid digit -1. There seems to be no way around this problem. A
-1 digit must create a borrow which must be propagated over a sequence of 0
digits. If 0s are not transformed to positive values, the borrow cannot be
absorbed. Because the length of the sequence of 0 digits is unbounded, no local
transformation (carry-free process) can decide if the 0s are part of a sequence
of leading 0s. If you feel that you made this point but did not receive proper
credit, please see me.
Note
(correction to the solution of Problem 6.1): Besides the misspelled
"performing" in part a, the term "pi_i" (or b_i) in the
expression for d_i in part b should be complemented.
ECE
252B w2001, Homework #4: Multiplication (chapters 9-11, due Mon. Feb. 12)
Do
the following six problems from the textbook:
9.1
(p. 153), 9.4b (p. 154), 9.14a (p. 155), 10.1 (p. 169), 10.3 (p. 169), 10.15 (p.
171)
ECE
252B w2001, Homework #5: Multiplication & Division (chapters 12-13, due Mon.
Feb. 26)
Do
the following three problems from the textbook, plus Problem 12.A given below:
12.4
(p. 205), 13.10 (p. 225), 13.13 (p. 226)
Problem
12.A on synthesis of multipliers:
a.
We want to synthesize a 12-by-4 parallel multiplier using single-bit and 4-bit
binary adders as the only building blocks. Using dot notation, specify an
efficient design that minimizes the cost, assuming unit cost for 1-bit adders
and 6 units for 4-bit adders.
b.
Repeat part a, this time using only (4, 4; 4)-counters and 4-bit adders.
c.
Repeat part a, this time using 4-by-4 multipliers and 4-bit adders as the only
building blocks.
ECE
252B w2001, Homework #6: Other Division Topics (chapters 14-16, due Mon. Mar. 5)
Do
the following three problems from the textbook, plus Problem 16.B given below:
14.4a,b
(p. 242), 14.8 (p. 243), 15.4 (p. 257)
Optional
problem (for extra credit): 16.10 (p. 274)
Problem
16.B on iterative reciprocation:
a.
Compute the reciprocal of d = (.1100 0000)_two using x^(i+1) = x^(i) (2 - x^(i)
d) and arithmetic with 12 bits after the radix point throughout.
b.
Repeat part a, using the expansion 1/d = 1/(1 - y) = (1 + y)(1 + y^2)(1 +
y^4)..., where y = 1 - d, instead of the Newton-Raphson iteration. Each term 1 +
y^(2^(i+1)) is computed by squaring y^(2^i) and adding 1.
c.
Compare the results of parts a and b and discuss.
ECE
252B w2001, Homework #7: Floating-Point Arithmetic (chapters 17-19, due Mon.
Mar. 12)
[Note
on HW#6: The statement of Problem 16.10 seems to be in error and I have been
unable to ascertain what the correct version is. If you are able to find the
correct version of the suggested convergence formula, then do the problem.
Otherwise, you can do Problem 16.11 instead, which is quite similar and serves
the same purpose as the one originally assigned.]
Do
the following four problems from the textbook:
17.7
(p. 294), 17.14 (p. 295), 18.9 (p. 309), 19.9 (p. 325)
Optional
problem (for extra credit): 19.10 (p. 326)
Notes
on MRRE for logarithmic representation
Consider
two consecutive logarithms L and L + ulp and a number x that falls between 2^L
and 2^(L + ulp).
Relative
error for rounding down = (x - 2^L)/x
Relative
error for rounding up = (2^(L + ulp) - x)/x
The
worst-case occurs when the relative error is the same for rounding down or
up. Thus, the worst-case x satisfies:
(x
- 2^L)/x = (2^(L + ulp) - x)/x
From
the above, we get x = (2^(L + ulp) + 2^L)/2. Plug this into either
relative error equation to get:
MRRE
= (2^ulp - 1)/(2^ulp + 1)
Because
2^ulp is very close to 1, MRRE is approximately (2^ulp - 1)/2
ECE
252B w2001, Possible
Research Topics
The
ECE 252B research topics for winter 2001 are based on the latest computer arithmetic
special issue of IEEE Trans. Computers published in July 2000. The special issue contains six
pairs of papers in the following areas. Each pair can be chosen as a research
subject area. The research report will be based on a detailed study of the chosen pair
of papers, plus additional references that the student will identify in order to
prepare a complete and informative paper. The six subject areas are:
1.
Function evaluation = reciprocation & square-rooting, pp. 628-637 + CORDIC, pp.
727-739.
2.
Rounding, pp. 638-658.
3.
Addition, pp. 659-680.
4.
Multiplication, pp. 681-701.
5.
Logarithmic processors, pp. 702-726.
6.
Cryptography, pp. 740-758.
Return to:
Top of this page
ECE 252B: Winter Quarter 2000 offering
Course: |
ECE
252B – Computer Arithmetic, University of California, Santa Barbara,
Winter 2000, Enrollment Code 10686 |
Instructor: |
Behrooz
Parhami, Room 5155 Engineering I, Phone
805-893-3211, parhami@ece.ucsb.edu
|
Meetings: |
MW
8:30-10:00 AM, Room 1437 Phelps Hall |
Consultation: |
Open
office hours (held in Room 5155 Engineering I) – M 10:00-11:00, T
11:30-12:30, W 1:00-2:00 |
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: |
Text–Parhami,
B., Computer Arithmetic: Algorithms
and Hardware Designs, Oxford, 2000.
Other
books –
Koren, Computer Arithmetic
Algorithms, Prentice-Hall, 1993.
Omondi,
Computer Arithmetic Systems: . . . ,
Prentice-Hall, 1994 (QA76.9.C62O46).
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).
Swartzlander,
Computer Arithmetic, vols. 1-2,
IEEE Computer Soc. Press (QA76.6.C633).
Kulisch/Miranker,
Computer Arithmetic in Theory and
Practice (QA162.K84).
Ercegovac/Lang,
Division and Square Root:
Digit-Recurrence . . . , Kluwer, 1994.
Other
Sources – Proc.
Int’l Symp. on Computer Arithmetic (1969, 72, 75 78, and odd years
since 1981) and 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) |
Evaluation: |
Students
will be evaluated based on the following three components with the given
weights:
|
|
25%
-- Homework (see the “deadlines” column in course calendar for
schedule). |
|
25%
-- 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.
A
student
interested in this option,
will review a subfield of computer arithmetic or do original research on a
selected topic. 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 covered chapter(s) before
each lecture if possible.
Day
and Date |
Chap |
Lecture
Topic |
Deadlines |
Mon.
1/10/00 |
1-2 |
Numbers
and signed values |
|
Wed.
1/12/00 |
3-4 |
Redundant
and RNS representations |
HW#1
given (1-4) |
Mon.
1/17/00 |
|
HOLIDAY:
No lecture |
|
Wed.
1/19/00 |
5-6 |
Basic
and carry-lookahead addition |
HW
#2 given (5-6), #1 due |
Mon.
1/24/00 |
7 |
Variations
in fast adders |
Research
topics defined |
Wed.
1/26/00 |
8 |
Multioperand
addition |
HW
#3 given (7-8), #2 due |
Mon.
1/31/00 |
9-10 |
Basic
and high-radix multiplication |
|
Wed.
2/2/00 |
11 |
Tree
and array multipliers |
HW
#4 given (9-12), #3 due |
Mon.
2/7/00 |
12 |
Variations
in multipliers |
Preliminary
references due |
Wed.
2/9/00 |
13 |
Basic
division schemes |
HW
#4 due |
Mon.
2/14/00 |
1-12 |
MIDTERM
EXAM: closed book |
|
Wed.
2/16/00 |
14 |
High-radix
division |
HW
#5 given (13-14) |
Mon.
2/21/00 |
|
HOLIDAY:
No lecture |
|
Wed.
2/23/00 |
15-16 |
Other
division topics |
HW
#6 given (15-16), #5 due |
Mon.
2/28/00 |
17-18 |
Floating-point
arithmetic |
Paper
title and references due |
Wed.
3/1/00 |
19-20 |
Computation
errors and precision |
HW
#7 given (17-20), #6 due |
Mon.
3/6/00 |
21 |
Square-rooting
methods |
Preliminary
paper abstract due |
Wed.
3/8/00 |
22 |
The
CORDIC algorithms |
HW
#8 given (21-24), #7 due |
Mon.
3/13/00 |
23-24 |
Function
evaluation |
|
Wed.
3/15/00 |
25-28 |
Implementation
topics |
HW
#8 due |
Fri.
3/24/00 |
1-24 |
FINAL
EXAM: open book |
Complete
paper due |
Return to:
Top of this page || Go up to: B.
Parhami's course syllabi or his
home page
|