Do the following problems from the textbook: 9.1abc [15 pts.], 9.15 [10 pts.], 10.5a [10 pts.], 10.9 [20 pts.], 11.1a [5 pts.], 11.4d [20 pts], 12.8abd [20 pts.]

Homework 4: Data path and control (due F 3/3/2006, 10:00 AM)

Do the following problems from the textbook: 13.1a [15 pts.], 13.17 [20 pts.], 14.2c [15 pts.], 14.6 [15 pts.], 15.6a [20 pts.], 15.14a [15 pts.]

Homework 5: Memory system design (due F 3/10/2006, 10:00 AM)

Do the following problems from the textbook: 17.15 [10 pts.], 18.4bc [20 pts], 18.10 [20 pts.], 19.7b [10 pts.], 20.3 [20 pts.], 20.12b [20 pts.]

Midterm and Final Exam Preparation

The following includes topics that will be emphasized, as well as list of exclusions from the midterm exam (Chapters 1-12) and final exam (Chapters 1-24). All sections not specifically excluded are required, even if they were not covered in class.

Chapters 1-2 -- Logic design: no direct problem, but you need to know (and be able to define) concepts such as tristate buffers, multiplexers, register files, and so on, used to explain the topics that follow.

Chapter 3 -- No problem or question.

Chapter 4 -- Computer performance: problem likely on CPI calculation, performance enhancement (Amdahl's law), instruction mix, and/or benchmarks.

Chapters 5-8 -- Instruction-set architecture: You do not need to memorize instruction codes or formats. Any problem in this area will be accompanied by a reference table providing a list of codes and formats if required. Ignore Sections 7.5, 7.6, 8.4, and 8.6.

Chapters 9-12 -- Computer arithmetic: problem likely on 2's-complement numbers, shift/logical operations (including distinction between arithmetic and logical shifts), adders and ALUs, shift-add multiplication, shift-subtract division, floating-point numbers, and/or floating-point arithmetic. Ignore pp. 205-206 in Section 11.3, pp. 214-215 in Section 11.6, and pp. 235-236 in Section 12.6.

The following apply to the final exam, which will include material from the preceding chapters as well, but to a much lesser degree (new material will be heavily emphasized).

Chapters 13-14 -- Data path and control: problem very likely on control unit structure, control signal generation, multicycle instruction execution, and control state machine. Section 14.5 is excluded.

Chapter 15-16 -- Pipelining: problem very likely on pipeline bubbles (how to insert or avoid them), pipeline control, data hazards, data forwarding, control hazards, delayed branch, and/or branch prediction.

Chapters 17-20 -- Memory hierarchy: problem very likely on the need for memory hierarchy, cache memory concepts (levels 1 and 2), miss/hit rate, average memory access time, compulsory/capacity/conflict misses, mapping schemes, virtual memory, page table, and/or TLB. Sections 17.5, 19.5, 19.6, and 20.5 are excluded.

Chapters 21-24 -- Input/output and interfacing: problem possible on memory-mapped, polled, or interrupt-driven I/O, buses, and interrupts. Sections 21.5, 21.6, 22.6, 23.5, 23.6, 24.5, and 24.6 are excluded.

Chapters 25-28 -- Advanced architectures: no problem or question.  

Return to: Top of this page 

Summer session 2005 offering of ECE 154

This area is reserved for important course announcements:  2005/07/25: The instructor will have special office hours on the eve of the final exam for last-minute questions ( i.e., on Thursday, 7/28, 5:00-7:30 PM).

2005/07/18: Homework 5 has been posted below; its due date is extended to Tuesday 7/26. There is a change in the coverage of the final exam; specifically, microprogramming (Section 14.5) is now excluded.

2005/07/13: Midterm exam (min, avg, max) grades were ( 56, 71, 83). The corresponding stats for HW2 and HW3 were (0, 80, 100) and (0, 63, 98), respectively. The latter become (74, 89, 100) and (50, 79, 98) if grades of 0 for homework not  turned in are excluded.

2005/07/11: Homework 4 has been posted below. It will be due on Monday 7/18 during the discussion session. Note that during the rest of this week (including on Friday, 7/15), we will have lectures covering the important Chapters 13-16 of the text.

2005/7/3: Homework 3 has been posted below. It will be due on Friday 7/8; in preparation for the midterm exam on Monday, 7/11 (beginning at 7:45 AM), solutions will be distributed during the discussion session on the due date.

005/06/27: Homework 2 has been posted below. Please note critical and noncritical corrections listed for page 110 of the textbook on its Web page.

2005/06/23: Homework 1 has been withdrawn and will not be graded, because some students may have gained unauthorized access to the solutions sheet. Its weight will be redistributed among the remaining four homework assignments. You can use Homework 1 for practice, comparing your solutions against those to be handed out next Monday. Homework 2 will be posted next week and will be due on its regular due date. The previous form of Homework 2, along with its solutions, was compromised as well; so a new version of this homework is being designed.

Calendar:

Course lectures, homework assignments, and exams have been scheduled as follows. This schedule will be strictly observed. 

Homework 1: Logic design and computer performance (due Monday, June 27)

Do the following problems from the textbook: 1.9b [15 pts.], 1.16 [20 pts.], 2.5a [15 pts.], 3.15 [10 pts.], 4.2 [25 pts.], 4.15 [15 pts.]

Homework 2: Instructions and assembly language (due Tuesday, July 5)

Do the following problems from the textbook: 5.4 [15 pts.], 5.9bd [20 pts.], 6.9ab [20 pts.], 7.3def [15 pts.], 8.3 [15 pts.], 8.8 [15 pts.]

Homework 3: Computer arithmetic (due Friday, July 8)

Do the following problems from the textbook: 9.3 [20 pts.], 10.5bc [15 pts.], 10.11 [15 pts.], 11.4b [20 pts.], 11.12 [15 pts.], 12.5 [15 pts.]

Homework 4: Data path and control (originally due on Monday, July 18)

Do the following problems from the textbook: 13.6 [15 pts.], 14.2b [15 pts.], 14.7 [20 pts.], 15.8 [20 pts.], 16.3 [15 pts.], 16.10ab [15 pts.]

Homework 5: Memory system design (due Monday, July 25; extended to Tuesday, July 26)

Do the following problems from the textbook: 17.1ab [15 pts.], 18.3 [15 pts.], 18.8 [20 pts.], 19.1 [15 pts.], 20.7 [15 pts.], 20.12a [20 pts.]

Midterm and Final Exam Preparation

The following includes topics that will be emphasized, as well as list of exclusions from the midterm exam (Chapters 1-12) and final exam (Chapters 1-24). All sections not specifically excluded are required, even if they were not covered in class.

Chapters 1-2 -- Logic design: no direct problem, but you need to know (and be able to define) concepts such as tristate buffers, multiplexers, register files, and so on, used to explain the topics that follow.

Chapter 3 -- No problem or question.

Chapter 4 -- Computer performance: problem likely on CPI calculation, performance enhancement (Amdahl's law), instruction mix, and/or benchmarks.

Chapters 5-8 -- Instruction-set architecture: You do not need to memorize instruction codes or formats. Any problem in this area will be accompanied by a reference table providing a list of codes and formats if required. Ignore Sections 7.5, 7.6, 8.4, and 8.6.

Chapters 9-12 -- Computer arithmetic: problem likely on 2's-complement numbers, shift/logical operations (including distinction between arithmetic and logical shifts), adders and ALUs, shift-add multiplication, shift-subtract division, floating-point numbers, and/or floating-point arithmetic. Ignore pp. 205-206 in Section 11.3, pp. 214-215 in Section 11.6, and pp. 235-236 in Section 12.6.

The following apply to the final exam, which will include material from the preceding chapters as well, but to a much lesser degree (new material will be heavily emphasized).

Chapters 13-14 -- Data path and control: problem very likely on control unit structure, control signal generation, multicycle instruction execution, and control state machine. Section 14.5 is excluded.

Chapter 15-16 -- Pipelining: problem very likely on pipeline bubbles (how to insert or avoid them), pipeline control, data hazards, data forwarding, control hazards, delayed branch, and/or branch prediction.

Chapters 17-20 -- Memory hierarchy: problem very likely on the need for memory hierarchy, cache memory concepts (levels 1 and 2), miss/hit rate, average memory access time, compulsory/capacity/conflict misses, mapping schemes, virtual memory, page table, and/or TLB. Sections 17.5, 19.5, 19.6, and 20.5 are excluded.

Chapters 21-24 -- Input/output and interfacing: problem possible on memory-mapped, polled, or interrupt-driven I/O, buses, and interrupts. Sections 21.5, 21.6, 22.6, 23.5, 23.6, 24.5, and 24.6 are excluded.

Chapters 25-28 -- Advanced architectures: no problem or question.  

Return to: Top of this page 

Summer session 2004 offering of ECE 154

Calendar:

Course lectures, homework assignments, and exams have been scheduled as follows. This schedule will be strictly observed. 

Homework 1: Logic design and computer performance (due Monday, June 28)

Do the following problems from the textbook: 1.9 (parts a and c), 2.19, 3.14b, 4.1, 4.12

Homework 2: Instructions and assembly language (due Thursday, July 1)

Do the following problems from the textbook: 5.2 (parts c and d), 5.9 (parts a and c), 6.5 (parts c and d), 6.7, 7.4 (parts a and b)

Homework 3: Computer arithmetic (due Friday, July 9)

Do the following problems from the textbook: 9.5, 9.14, 10.6, 11.1 (part a), 11.2 (part b), 12.6 (parts d and e)

Homework 4: Data path and control (due Tuesday, July 20)

Do the following problems from the textbook: 13.8, 13.13, 14.9, 15.5, 15.10

Homework 5: Memory system design (due Wednesday, July 28)

Do the following problems from the textbook: 17.2, 18.2, 18.9, 19.5, 20.6 (part b), 20.8

Midterm and Final Exam Preparation

The following includes topics that will be emphasized, as well as list of exclusions from the midterm exam (Chapters 1-12) and final exam (Chapters 1-22). All sections not specifically excluded are required, even if they were not covered in class.

Chapters 1-2 -- Logic design: no direct problem, but you need to know (and be able to define) concepts such as tristate buffers, multiplexers, register files, and so on, used to explain the topics that follow.

Chapter 3 -- No problem or question.

Chapter 4 -- Computer performance: problem likely on CPI calculation, performance enhancement (Amdahl's law), instruction mix, and/or benchmarks.

Chapters 5-8 -- Instruction-set architecture: You do not need to memorize instruction codes or formats. Any problem in this area will be accompanied by a reference table providing a list of codes and formats if required. Ignore Sections 7.5, 7.6, 8.4, and 8.6.

Chapters 9-12 -- Computer arithmetic: problem likely on 2's-complement numbers, shift/logical operations (including distinction between arithmetic and logical shifts), adders and ALUs, shift-add multiplication, shift-subtract division, floating-point numbers, and/or floating-point arithmetic. Ignore pp. 264-265 in Section 11.3, pp. 274-275 in Section 11.6, and pp. 299-301 in Section 12.6.

The following apply to the final exam, which will include material from the preceding chapters as well, but to a much lesser degree (new material will be heavily emphasized).

Chapters 13-14 -- Data path and control: problem very likely on control unit structure, control signal generation, multicycle instruction execution, and control state machine;  microprogramming (Section 14.5) is excluded.

Chapter 15-16 -- Pipelining: problem very likely on pipeline bubbles (how to insert or avoid them), pipeline control, data hazards, data forwarding, control hazards, delayed branch, and/or branch prediction.

Chapters 17-20 -- Memory hierarchy: problem very likely on the need for memory hierarchy, cache memory concepts (levels 1 and 2), miss/hit rate, average memory access time, compulsory/capacity/conflict misses, mapping schemes, virtual memory, page table, and/or TLB. Sections 17.5, 19.5, 19.6, and 20.5 are excluded.

Chapters 21-24 -- Input/output devices and Programming: problem possible on memory-mapped, polled, or interrupt-driven I/O. Sections 21.5, 21.6 and 22.6 are excluded.

Chapters 23-24 -- Buses, interfacing, interrupts: no problem or question.

Chapters 25-28 -- Advanced architectures: no problem or question. 

Return to: Top of this page 

Summer session 2003 offering of ECE 154

Calendar:

Course lectures, homework assignments, and exams have been scheduled as follows. This schedule will be strictly observed. 

Homework 1: Logic design and computer performance (due Monday, June 30)

Do the following problems from the textbook: 1.3, 2.6, 3.14a, 4.4, 4.11

Clarification on Problem 4.11a: Instruction mix means the fraction of instructions that are of each type. In this problem, two types of instructions are involved, so the answer would be the fraction x of instructions that are floating-point. The fraction of floating-point instructions executed is not the same as the fraction of time spent on executing them (50% in this case). The point here is to make you realize that the instruction mix and running time fractions are not the same but that they are related.

Homework 2: Instructions and assembly language (due Monday, July 7)

Do the following problems from the textbook: 5.2ab, 5.10ab, 6.5ab, 6.6, 7.3abc

Homework 3: Computer arithmetic (due Monday, July 14)

Do the following problems from the textbook: 9.6, 9.10, 10.7, 11.2ac, 12.6abc

Homework 4: Data path and control (due Monday, July 21; extended to Wednesday, July 23)

Do the following problems from the textbook: 13.12, 14.2a, 15.2, 16.9

Homework 5: Memory system design (due Monday, July 28; extended to Tuesday, July 29)

Do the following problems from the textbook: 17.3, 18.4ad, 18.7, 19.2, 20.4

Midterm and Final Exam Preparation

The following includes topics that will be emphasized, as well as list of exclusions from the midterm exam (Chapters 1-12) and final exam (Chapters 1-20). All sections not specifically excluded are required, even if they were not covered in class.

Chapters 1-2 -- Logic design: no direct problem, but you need to know (and be able to define) concepts such as tristate buffers, multiplexers, register files, etc., used to explain the topics that follow.

Chapter 3 -- No problem or question.

Chapter 4 -- Computer performance: problem likely on CPI calculation, performance enhancement (Amdahl's law), instruction mix, and/or benchmarks.

Chapters 5-8 -- Instruction-set architecture: You do not need to memorize instruction codes or formats. Any problem in this area will be accompanied by a reference table providing a list of codes and formats if required. Ignore Sections 8.4 and 8.6.

Chapters 9-12 -- Computer arithmetic: problem likely on 2's-complement numbers, shift/logical operations (incl. distinction between arithmetic and logical shifts), adders and ALUs, shift-add multiplication, shift-subtract division, floating-point numbers, and/or floating-point arithmetic. Ignore pp. 261-262 in Section 11.3, Sections 11.5-11.6, pp. 297-298 in Section 12.6, and all but the first two paragraphs of p. 296.

Chapters 13-14 -- Data path and control: problem very likely on control unit structure, control signal generation, multicycle instruction execution, and control state machine;  microprogramming is excluded.

Chapter 15-16 -- Pipelining: problem very likely on pipeline bubbles (how to insert or avoid them), pipeline control, data hazards, data forwarding, control hazards, delayed branch, and/or branch prediction.

Chapters 17-20 -- Memory hierarchy: problem very likely on the need for memory hierarchy, cache memory concepts (levels 1 and 2), miss/hit rate, average memory access time, compulsory/capacity/conflict misses, mapping schemes, virtual memory, page table, and/or TLB.

Chapters 21-24 -- Input/output, buses, interfacing, interrupts: no problem or question.

Chapters 25-28 -- Advanced architectures: no problem or question.

Return to: Top of this page 

Summer session 2002 offering of ECE 154

Calendar:

Course lectures, homework assignments, and exams have been scheduled as follows. This schedule will be strictly observed. 

Homework 1: Logic design and computer performance (due Monday, 2002 July 1)

Problem 1.19     Arithmetic expressions for logic gates

The arithmetic expressions characterizing logic gates (Fig. 1.1 in the notes) can be extended to gates with more than two inputs. This is trivial for AND gates. Write the equivalent arithmetic expressions for 3- and 4-input OR gates. Generalize the expression to an h-input OR gate.

Problem 2.15     Building larger shift registers and counters

a.        Explain how you would build a 32-bit shift register, given two 16-bit shift registers.

b.       Repeat part a for a 32-bit up counter, given two 16-bit up counters.

Problem 3.15     Effects of yield on die cost

A wafer containing 100 copies of a complex processor die costs $900 to manufacture. The area occupied by each processor is 2 cm² and the defect density is 2 per cm². What is the manufacturing cost per die?

Problem 4.7     Instruction mix and performance

This problem is a continuation of Example 4.6. We can redesign the machine M₁ so that its clock rate is 1.4 times the current rate (say, 1.4 GHz instead of 1 GHz). Doing this will require other design changes that increase all the CPIs by 1. How does M₂ compare to the redesigned M₁ in terms of performance?

Problem 4.15     Amdahl's law

You live in an apartment from which you have a 7-minute drive for your twice-a-week shopping trips to a nearby supermarket and a 20-minute drive to a warehouse store where you shop once every four weeks. You are planning to move to a new apartment. Compare the following two candidate locations with respect to the speedup they offer for your driving time during shopping trips.

a.        An apartment that is 10 minutes away from both a supermarket and a warehouse store.

b.       An apartment that is 5 minutes away from a supermarket and 30 minutes from a warehouse store.

Homework 2: Instructions and assembly language (due Monday, 2002 July 8)

Problem 5.4     Multiplying by a small power of two

Write a sequence of MiniMIPS instructions (using only the instructions in Table 5.1) to multiply the integer x stored in register $s0 by 2ⁿ, where n is a small nonnegative integer stored in $s1. The result should be placed in $s2. Hint: Use repeated doubling.

Problem 6.3     Divisibility by powers of two

A binary integer that has h consecutive 0s at its right end is divisible by 2^h. Write a MiniMIPS procedure that accepts a single unsigned integer in register $a0 and returns the largest power of 2 by which it is divisible (an integer in [0, 32]) in register $v0.

Problem 7.3     Additional pseudoinstructions

The following are some additional pseudoinstructions that one could define for MiniMIPS. In each case, supply an equivalent MiniMIPS instruction or sequence of instructions with the desired effect.

   partc: bgtz    reg,L           # if (reg) > 0, goto L

   partg: triple  regd,regs       # regd = 3 ´ (regs)

   parth: mulacc  regd,reg1,reg2  # regd = (regd) + (reg1) ´ (reg2)

Problem 8.2     Instruction formats

Categorize each of the MiniMIPS instruction given in Table 6.2 according to the number of addresses in its format (0-, 1-, 2-, or 3-address instruction, as in Fig. 8.2).

Homework 3: Computer arithmetic (due Monday, 2002 July 15)

Problem 9.11     Number radix conversion

Convert each of the following numbers from its indicated radix to radix-2 and radix-16 representations.

a.       Radix-10 numbers: 12,   5 655,   76 545 336

b.       Radix-12 numbers: 9a5,   b0a,   baabaa

Problem 9.15     Floating-point numbers

Consider the entries supplied for min and max in Table 9.1. Show how these values are derived and explain why the max values in the two columns are specified as being approximately equal to a power of 2.

Problem 10.x     Brent-Kung carry network

Draw a diagram similar to Fig. 10.11 that corresponds to the carry network of a 16-digit adder. Hint: See Fig. 10.12.

Problem 11.1     Multiplication algorithm

a.       By redoing the multiplication steps in Fig. 11.2, verify that if the cumulative partial product is initialized to 1011 instead of 0000, a multiply-add operation is performed.

b.       Show that regardless of the radix r and the initial value of the k-digit z⁽⁰⁾, the multiply-add result with k-digit operands is always representable in 2k digits.

Problem 12.x     Floating-point arithmetic

Show the results of the following floating-point operations. Justify your answers.

a.       min +_fp max

b.       min ´_fp max

c.       min /_fp max

Homework 4: Data path and control (due Wednesday, 2002 July 24, one day later than originally announced, in order to allow time for covering the material in class)

Problem 13.x     Control signals in the single-cycle data path

Extend Table 13.3 with lines corresponding to the following new instructions that might be added to the single-cycle MicroMIPS implementation. Justify your answers.

a.       Shift left logical (sll)

b.       Shift right arithmetic variable (srav)

Problem 14.x     Extending the multicycle data path

Suggest some simple changes (the simpler, the better) in the multicycle data path of Fig. 14.3 so that the following instructions can be included in the machine's instruction set:

a.       Load byte (lb).

b.       Load byte unsigned (lbu).

c.       Store byte (sb).

Problem 15.x     Pipelined data path and control

The following sequence of instructions is to be executed on the pipelined MicroMIPS of Chapter 15; i.e., with no data forwarding or branch prediction logic. Determine how many bubbles must be inserted and where. Explain your reasoning in each step. Can you suggest any reordering of instructions that would reduce the number of bubbles?

      addi  $9,$zero,0

      addi  $12,$zero,5000

Loop: addi  $12,$12,4

      lw    $8,40($12)

      add   $9,$9,$8

      addi  $11,$11,-1

      bne   $11,$zero,Loop

Problem 16.x     Pipeline performance

A 10-stage instruction pipeline runs at a clock rate of 1 GHz. The data forwarding scheme and the instruction mix are such that for 15% of instructions one bubble, for 10% two bubbles, and for 5% four bubbles must be inserted in the pipeline. The equivalent single-cycle implementation would lead to a clock rate of 150 MHz.

a.       What is the reduction in pipeline throughput over the ideal pipeline as a result of bubbles?

b.       What is the speedup of the pipelined implementation over the single-cycle implementation? 

Homework 5: Memory system design (due Tuesday, 2002 July 30)

Problem 18.x     Cache memory design

A computer system has 4 GB of byte-addressable main memory and a 256-KB cache memory with 32-byte blocks.

a.      Draw a diagram showing each of the components of a main memory address (i.e., how many bits for tag, set index, and byte offset) for a 4-way set-associative cache.

b.      Draw a diagram showing the tag comparison circuits, generation of the cache miss signal, and the data output for the cache.

c.      The performance of the computer system with 4-way set-associative cache architecture proves unsatisfactory. Two redesign options are being considered, implying roughly the same additional design and production costs. Option A is to increase the size of the cache to 512 KB. Option B is to increase the associativity of the 256 KB cache to 16-way. In your judgment, which option is more likely to result in greater overall performance and why?

Problem 18.y     Cache memory performance

A computer system uses two levels of caches L1 and L2. L1 is accessed in one clock cycle and supplies the data in case of an L1 hit. For an L1 miss, occurring 3% of the time, L2 is consulted. An L2 hit incurs a penalty of 10 clock cycles while an L2 miss implies a 100-cycle penalty. 

a.       Assuming a pipelined implementation with a CPI of 1 when there are no cache misses whatsoever (i.e., ignoring data and control dependencies), calculate the effective CPI when L2's local miss rate is 25%.

b.       If we were to model the 2-level cache as a single cache, what miss rate and miss penalty should we use?

c.       Changing the mapping scheme of L2 from direct to 2-way set-associative can improve its local miss rate to 22% while increasing its hit penalty to 11 clock cycles due to the more complex access scheme. Ignoring cost issues, is this change a good idea?

Problem 19.x     Virtual memory performance

The following computation is to be performed on a table T having 17 rows and 1024 columns. Note that i is row index and j is column index.

          for j = [0 ... 1023] {

               temp = 0;

               for i = [0 ... 16]

                    temp = temp + T[i][j];

               print(temp/17.0); }

The preceding program fragment computes an average value for each table column and prints it to the screen. Assume that each table element is a 32-bit floating-point number and that the memory is word-addressable. The temporary variable temp is kept in a processor register, so access to temp does not involve a memory reference. The main memory is paged and holds 16 pages of size 1024 words. The page replacement policy is "least-recently-used."

a.      Assuming that T is stored on the disk in row-major format, how many page faults will be encountered and what is the main memory hit ratio?

b.      What fraction of the misses in part a are compulsory? Capacity? Conflict?

c.      Repeat part a, this time assuming that T is stored on the disk in column-major format.

d.      What fraction of the misses in part c are compulsory? Capacity? Conflict? 

Final Exam Preparation

Chapters 1-2 -- Logic design: no direct problem, but you need to know (and be able to define) concepts such as tristate buffers, multiplexers, register files, etc., used to explain the topics that follow.

Chapter 3 -- No problem or question.

Chapter 4 -- Computer performance: problem likely on CPI calculation, performance enhancement (Amdahl's law), instruction mix, and/or benchmarks.

Chapters 5-8 -- Instruction-set architecture: You do not need to memorize instruction codes or formats. Any problem in this area will be accompanied by a reference table providing a list of codes and formats if required. Ignore Section 8.6.

Chapters 9-12 -- Computer arithmetic: problem likely on 2's-complement numbers, shift/logical operations (incl. distinction between arithmetic and logical shifts), shift-add multiplication, shift-subtract division, floating-point numbers, and/or floating-point arithmetic. Ignore pp. 198-199 in Section 11.3, Sections 11.5-11.6, and pp. 226-228 in Section 12.6.

Chapters 13-14 -- Data path and control: problem very likely on control unit structure, control signal generation, multicycle instruction execution, and control state machine;  microprogramming is excluded.

Chapter 15-16 -- Pipelining: problem very likely on pipeline bubbles (how to insert or avoid them), pipeline control, data hazards, data forwarding, control hazards, delayed branch, and/or branch prediction.

Chapters 17-20 -- Memory hierarchy: problem very likely on the need for memory hierarchy, cache memory concepts (levels 1 and 2), miss/hit rate, average memory access time, compulsory/capacity/conflict misses, mapping schemes, virtual memory, page table, and/or TLB.

Chapters 21-22 -- Input/output: problem likely on I/O performance, polling vs. interrupts, and/or I/O addressing.

Chapters 23-24 -- Buses, interfacing, interrupts: no problem or question.

Chapters 25-28 -- Advanced architectures: no problem or question.  

Solutions for the practice final exam

1. Address translation: The process by which physical memory address is derived from a given virtual address (also known as address mapping).

Bus arbitration: The process used to decide which of several units that need to use the bus is allowed to use it next.

Conflict miss: A cache miss that occurs because restricted mapping in the cache (direct or set-associative) has caused the required data to be overwritten by other data; does not apply to a fully associative cache.

Delayed branch: A type of conditional branch in which the instruction (or several instructions) immediately following the branch are always executed, whether or not the branch is taken.

Interrupt-driven I/O: Input/output operations that are performed at the request of devices that have something to send to the CPU or need to receive data from the CPU (as opposed to polling-based I/O in which the CPU takes the initiative).

Pseudoinstruction: An assembly-language command that is used as if it were a machine  instruction but is replaced by one or more actual machine instructions during the assembly process.

Set-associative cache: A cache that allows an incoming cache line (block) to be mapped into any of a fixed number of locations (at least two).

TLB: (Translation lookaside buffer) A small cache that keeps the most recently used page table entries to avoid an extra memory access for translating a virtual address to a physical address.

2. (a) The largest k-bit unsigned integer is 2^k - 1 whose square is 2^(2k) - 2^(k+1) + 1. This is less than or equal to 2^(2k) - 1 for all k (so 2k bits are adequate) but it it greater than 2^(2k-1) - 1 for k > 1 (so 2k - 1 bits are inadequate, except in the uninteresting case of k = 1).

(b) The magnitude of k-bit 2's-complement numbers is at most 2^(k-1), so the magnitude of the product of two such numbers can be as large as 2^(2k-2). Therefore, the two MSBs of the 2k-bit product must be identical (00 for a positive product and 11 for a negative product). There is only one exception: The square of -2^(k-1), which is 2^(2k-2) begins with 01 at the most significant end.

3. (a) The ALU output is stored in rt for arithmetic and logic instructions with an immediate operand. Examples include addi, andi, xori.

(b) Data memory output is stored in a register only for lw instruction. In this case, the destination register is rt. So, data memory to rt is never used.

(c) Register $31 can be the destination of arithmetic/logic results when it is specified as rd or rt. The only instruction for which we choose register $31 implicitly is jal. In this case, the incremented PC value will be stored in $31. So, ALU to $31 is never used.

4. (a) It represents a multicycle implementation (due to the sequencing and branching logic shown). A single-cycle implementation is usually not microprogrammed; even if it were, the microprogram address logic would consist of a simple decoder that selects a single microinstruction to be executed for a given opcode.

(b) They allow the microprograms for several instructions to share a common segment and then branch out to do different things for different instructions (based on their opcodes).

(c) It is derived directly from a 2-bit field in the current microinstruction.

(d) Say, ALUSrc (which selects the lower input to the ALU) and RegWrite (which instructs the register file to perform a write operation). We can choose any two signals from the diagram of Problem 5.

5. (a) These are control signals that are carried along with the instruction until they are needed.

A represents control signals for the last pipeline stage (register writeback).

B represents control signals for the data cache access stage.

C represents control signals for the ALU operation stage.

(b) This mux allows the output of the ALU or the incremented PC value to be written in a register.

(c) This box extends a 16-bit immediate operand to 32 bits by replicating its sign bit (sign extension).

6. This problem was solved in Homework 5. It is included in this practice final as a representative example of problems on memory hierarchy.

7. (a) Rate of polling must be at least 600/min or 10/s to ensure that no data is lost. The time to execute 400 instructions is 400 / (20 000 000) s = 0.02 ms. Hence, polling time is 10 (rate/s) x 100 (terminals) x 0.02 = 20 ms in each second or 2%. This option is thus infeasible.

(b) Interrupt rate is at most 12 000 / min or 200/s. The time to execute 1000 instructions is 1000 / (20 000 000) s = 0.05 ms. Hence, interrupt servicing time is 200 (rate/s) x 0.05 = 10 ms in each second or 1%. This option is also infeasible.

Return to: Top of this page   

Summer session 2001offering of ECE 154

Calendar:

Course lectures, homework assignments, and exams have been scheduled as follows. This schedule will be strictly observed. It is a good idea to look over the specified course material before each lecture if possible. A six-week session is not long enough for covering the entire 900-page textbook. Students are encouraged to read other parts of the text, such as sections providing historical perspective, but the course exams are based only on the topics covered in class (including any handouts) and text pages listed in the “required” column below. Sections in the “recommended” column contain particularly useful background or supplementary material. 

Homework 1: Logic design and computer performance (due Monday, 2001 July 2)

All exercises in this homework are from the textbook.

A [15 points]: Do exercises 1-21 to 1-26.

B [15 points]: Do exercise B-13.

C [15 points]: Do exercise B-14.

D [10 points]: Do exercise 2.1.

E [10 points]: Do exercise 2.5.

F [20 points]: Do exercise 2.15.

G [15 points]: Do exercise 2.16.

Homework 2: Instructions and assembly programming (due Monday, 2001 July 9)

All exercises in this homework are from the textbook.

A [10 points]: Do exercise 3.1.

B [15 points]: Do exercise 3.6.

C [30 points]: Do exercise 3.11.

D [20 points]: Do exercise 3.17.

E [15 points]: Do exercise 3.18.

F [10 points]: Do exercise 3.20.

Homework 3: Computer arithmetic and ISA (due Monday, 2001 July 16)

All but one (item H) of the exercises in this homework are from the textbook.

A [10 points]: Do exercise 4.15.

B [15 points]: Do exercise 4.19.

C [10 points]: Do exercise 4.26.

D [15 points]: Do exercise 4.40.

E [10 points]: Do exercise 4.41.

F [10 points]: Do exercise 4.49.

G [10 points]: Do exercise 4.50.

H [10 points]: Modify the top diagram in Figure 4.56 so that E and F are added first, with their sum then added to the sum of A and B; in other words, A + B and E + F are formed in parallel before using the  5-bit adder in the bottom row of the diagram. Calculate the time for this new arrangement and compare the result to those obtained in Exercise 4.50.

I [10 points]: Do exercise 4.55.

Homework 4: Datapath and control (due Monday, 2001 July 23)

All exercises in this homework are from the textbook.

A [15 points]: Do exercise 5.3.

B [15 points]: Do exercise 5.7.

C [15 points]: Do exercise 5.9.

D [15 points]: Do exercise 5.10.

E [15 points]: Do exercise 5.16.

F [25 points]: Do exercise 5.23.

Homework 5: Pipelining and memory hierarchy (due Monday, 2001 July 30)

All exercises in this homework are from the textbook.

A [10 points]: Do exercise 6.4.

B [20 points]: Do exercise 6.9.

C [10 points]: Do exercise 6.15.

D [15 points]: Do exercise 6.21.

E [20 points]: Do exercise 6.31.

F [10 points]: Do exercise 7.7.

G [15 points]: Do exercise 7.13.

Final Exam Preparation

Appendix B -- Logic design: no direct problem, but you need to know concepts such as tristate buffers, multiplexers, register files, etc., used to explain the topics that follow.

Chapter 2 -- Computer performance: problem likely on CPI calculation, performance enhancement (Amdahl's law), instruction mix, and/or benchmarks.

Chapter 3 -- Instruction-set architecture: no direct problem, only conceptual questions (see problem 1 in the practice final). However, you do need to know various instructions and their execution steps to be able to explain control, pipelining, pipeline hazards, etc.

Chapter 4 -- Computer arithmetic: problem likely on 2's-complement numbers, shift/logical operations (incl. distinction between arithmetic and logical shifts), shift-add multiplication, shift-subtract division, floating-point numbers, and/or floating-point arithmetic (no need to know floating-point instructions in MIPS).

Chapter 5 -- Data path and control: problem very likely on single-cycle design, control signal generation, multicycle design, control state machine, and/or microprogramming.

Chapter 6 -- Pipelining: problem very likely on pipeline bubbles (how to insert or avoid them), pipeline control, data hazards, data forwarding, control hazards, delayed branch, and/or branch prediction.

Chapter 7 -- Memory hierarchy: problem very likely on the need for memory hierarchy, cache memory (levels 1 and 2), miss/hit rate, average memory access time, compulsory/capacity/conflict misses, mapping schemes, virtual memory, page table, and/or TLB.

Chapter 8 -- I/O and interfacing: problem likely on I/O performance, polling vs. interrupts, I/O addressing, buses, and/or bus arbitration.

Chapter 9 -- Parallel processing: no problem or question.

Return to: Top of this page 

Summer session 2000 offering of ECE 154

Calendar:

Course lectures, homework assignments, and exams have been scheduled as follows. This schedule will be strictly observed. It is a good idea to look over the specified course material before each lecture if possible. A six-week session is not long enough for covering the entire 900-page textbook. Students are encouraged to read other parts of the text, such as sections providing historical perspective, but the course exams are based only on the topics covered in class (including any handouts) and text pages listed in the “required” column below. Sections in the “recommended” column contain particularly useful background or supplementary material. 

* Videotape: On Tue. 6/27 and Wed. 6/28, the instructor will be away at a technical conference. The class will be held in the usual place and time with special videotaped lectures.

Return to: Top of this page  ||  Go up to: B. Parhami's course syllabi or his home page