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

Link to the most recent offering of ECE 252B: Computer Arithmetic
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:   

TextParhami, 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

      


Dr. Behrooz Parhami, Professor

                     Office phone: +1 805 893 3211
E-mail: parhami@ece.ucsb.edu                 Messages: +1 805 893 3716
Dept. Electrical & Computer Eng.                  Dept. fax: +1 805 893 3262
Univ. of California, Santa Barbara                Office: Room 5155 Eng. I
Santa Barbara, CA 93106-9560 USA                      Deliveries: Room 4155 Eng. I