
ECE 154: Information on Previous Offerings
Behrooz Parhami: 2007/06/19  Email: 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 uptodate version of this page, visit it at the new address: http://www.ece.ucsb.edu/~parhami/ece_154_old.htm Link to the most recent offering of ECE 154: Intro. to Computer ArchitecturePrevious offerings of ECE 154
Return to:
Top of this page Winter quarter 2006 offering of ECE 154This area is reserved for important course announcements: 2006/3/14: During the finals weeks (3/2024), the following extended office hours will apply  M 11:0012:30 (BP), T 1:002:30 (BP), W 12:302:00 (BB), R 9:0010:30 (BP) and 2:304:00 (HF), F 9:0010:30 (BP). In addition, a review session will be held by B. Benson on M 3/20, 9:0011:00 AM in Phelps 3523. 2006/3/3: New versions of the presentations for Parts I to IV of the textbook have been posted to the book's Web page. 2006/2/28: Homework 5 has been posted below. It will be due by 10:00 AM on Friday 3/10. 2006/2/22: Homework 4 has been posted below. It will be due by 10:00 AM on Friday 3/3. 2006/2/9: Information about exclusions from the midterm exam has been updated. 2006/1/31: Homework 3 has been posted below. It will be due by 10:00 AM on Friday 2/10. Also some new corrections, including several for pages 151153, have been posted to the textbook's Web page. 2006/1/17: Homework 2 has been posted below. It will be due by 10:00 AM on Friday 1/27. 2006/1/10: Homework 1 has been posted below. It has two parts that must be submitted separately. Both parts will be due by 10:00 AM on Friday 1/20 in the ECE 154 homework box located on the fifth floor of Engineering I.
Calendar: Course
lectures, homework assignments, and exams have been scheduled as follows. This
schedule will be strictly observed.
Homework: General Requirements Deposit solutions in ECE 154 homework box (5th floor of Engr I) before 10 AM on due date. 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. Homework 1: Logic design and computer performance (due F 1/20/2006, 10:00 AM) Please staple and submit your solutions for the two parts separately. Part A  Do the following problems from the textbook: 1.1ab [10 pts.], 1.11 [15 pts.], 2.5b [20 pts.], 2.9 [15 pts.] Part B 
Homework 2: Instructions and assembly language (due F 1/27/2006, 10:00 AM) Do the following problems from the textbook: 5.11 [15 pts.], 5.16a [15 pts.], 6.4 [20 pts.], 7.2fghi [20 pts.], 7.3h [10 pts.], 8.13 [20 pts] Homework 3: Computer arithmetic (due F 2/10/2006, 10:00 AM) 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 112) and final exam (Chapters 124). All sections not specifically excluded are required, even if they were not covered in class. Chapters 12  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 58  Instructionset 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 912  Computer arithmetic: problem likely on 2'scomplement numbers, shift/logical operations (including distinction between arithmetic and logical shifts), adders and ALUs, shiftadd multiplication, shiftsubtract division, floatingpoint numbers, and/or floatingpoint arithmetic. Ignore pp. 205206 in Section 11.3, pp. 214215 in Section 11.6, and pp. 235236 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 1314  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 1516  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 1720  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 2124  Input/output and interfacing: problem possible on memorymapped, polled, or interruptdriven I/O, buses, and interrupts. Sections 21.5, 21.6, 22.6, 23.5, 23.6, 24.5, and 24.6 are excluded. Chapters 2528  Advanced architectures: no problem or question.
Return to:
Top of this page Summer session 2005 offering of ECE 154This 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 lastminute questions ( i.e., on Thursday, 7/28, 5:007: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 1316 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 112) and final exam (Chapters 124). All sections not specifically excluded are required, even if they were not covered in class. Chapters 12  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 58  Instructionset 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 912  Computer arithmetic: problem likely on 2'scomplement numbers, shift/logical operations (including distinction between arithmetic and logical shifts), adders and ALUs, shiftadd multiplication, shiftsubtract division, floatingpoint numbers, and/or floatingpoint arithmetic. Ignore pp. 205206 in Section 11.3, pp. 214215 in Section 11.6, and pp. 235236 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 1314  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 1516  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 1720  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 2124  Input/output and interfacing: problem possible on memorymapped, polled, or interruptdriven I/O, buses, and interrupts. Sections 21.5, 21.6, 22.6, 23.5, 23.6, 24.5, and 24.6 are excluded. Chapters 2528  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 112) and final exam (Chapters 122). All sections not specifically excluded are required, even if they were not covered in class. Chapters 12  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 58  Instructionset 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 912  Computer arithmetic: problem likely on 2'scomplement numbers, shift/logical operations (including distinction between arithmetic and logical shifts), adders and ALUs, shiftadd multiplication, shiftsubtract division, floatingpoint numbers, and/or floatingpoint arithmetic. Ignore pp. 264265 in Section 11.3, pp. 274275 in Section 11.6, and pp. 299301 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 1314  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 1516  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 1720  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 2124  Input/output devices and Programming: problem possible on memorymapped, polled, or interruptdriven I/O. Sections 21.5, 21.6 and 22.6 are excluded. Chapters 2324  Buses, interfacing, interrupts: no problem or question. Chapters 2528  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 floatingpoint. The fraction of floatingpoint 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 112) and final exam (Chapters 120). All sections not specifically excluded are required, even if they were not covered in class. Chapters 12  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 58  Instructionset 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 912  Computer arithmetic: problem likely on 2'scomplement numbers, shift/logical operations (incl. distinction between arithmetic and logical shifts), adders and ALUs, shiftadd multiplication, shiftsubtract division, floatingpoint numbers, and/or floatingpoint arithmetic. Ignore pp. 261262 in Section 11.3, Sections 11.511.6, pp. 297298 in Section 12.6, and all but the first two paragraphs of p. 296. Chapters 1314  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 1516  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 1720  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 2124  Input/output, buses, interfacing, interrupts: no problem or question. Chapters 2528  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 4input OR gates. Generalize the expression to an hinput OR gate. Problem 2.15 Building larger shift registers and counters a. Explain how you would build a 32bit shift register, given two 16bit shift registers. b. Repeat part a for a 32bit up counter, given two 16bit 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^{2} and the defect density is 2 per cm^{2}. 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_{1} 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_{2} compare to the redesigned M_{1} in terms of performance? Problem 4.15 Amdahl's law You live in an apartment from which you have a 7minute drive for your twiceaweek shopping trips to a nearby supermarket and a 20minute 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^{n}, 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 3address 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 radix2 and radix16 representations. a. Radix10 numbers: 12, 5 655, 76 545 336 b. Radix12 numbers: 9a5, b0a, baabaa Problem 9.15 Floatingpoint 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 BrentKung carry network Draw a diagram similar to Fig. 10.11 that corresponds to the carry network of a 16digit 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 multiplyadd operation is performed. b. Show that regardless of the radix r and the initial value of the kdigit z^{(0)}, the multiplyadd result with kdigit operands is always representable in 2k digits. Problem 12.x Floatingpoint arithmetic Show the results of the following floatingpoint 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 singlecycle data path Extend Table 13.3 with lines corresponding to the following new instructions that might be added to the singlecycle 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 10stage 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 singlecycle 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 singlecycle implementation? Homework 5: Memory system design (due Tuesday, 2002 July 30) Problem 18.x Cache memory design A computer system has 4 GB of byteaddressable main memory and a 256KB cache memory with 32byte 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 4way setassociative 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 4way setassociative 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 16way. 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 100cycle 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 2level cache as a single cache, what miss rate and miss penalty should we use? c. Changing the mapping scheme of L2 from direct to 2way setassociative 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 32bit floatingpoint number and that the memory is wordaddressable. 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 "leastrecentlyused." a. Assuming that T is stored on the disk in rowmajor 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 columnmajor format. d. What fraction of the misses in part c are compulsory? Capacity? Conflict?
Final Exam Preparation Chapters 12  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 58  Instructionset 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 912  Computer arithmetic: problem likely on 2'scomplement numbers, shift/logical operations (incl. distinction between arithmetic and logical shifts), shiftadd multiplication, shiftsubtract division, floatingpoint numbers, and/or floatingpoint arithmetic. Ignore pp. 198199 in Section 11.3, Sections 11.511.6, and pp. 226228 in Section 12.6. Chapters 1314  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 1516  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 1720  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 2122  Input/output: problem likely on I/O performance, polling vs. interrupts, and/or I/O addressing. Chapters 2324  Buses, interfacing, interrupts: no problem or question. Chapters 2528  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 setassociative) 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. Interruptdriven 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 pollingbased I/O in which the CPU takes the initiative). Pseudoinstruction: An assemblylanguage 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. Setassociative 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 kbit 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^(2k1)  1 for k > 1 (so 2k  1 bits are inadequate, except in the uninteresting case of k = 1). (b) The magnitude of kbit 2'scomplement numbers is at most 2^(k1), so the magnitude of the product of two such numbers can be as large as 2^(2k2). Therefore, the two MSBs of the 2kbit product must be identical (00 for a positive product and 11 for a negative product). There is only one exception: The square of 2^(k1), which is 2^(2k2) 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 singlecycle 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 2bit 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 16bit 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 sixweek session is not long
enough for covering the entire 900page 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 121 to 126. B [15 points]: Do exercise B13. C [15 points]: Do exercise B14. 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 5bit 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  Instructionset 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'scomplement numbers, shift/logical operations (incl. distinction between arithmetic and logical shifts), shiftadd multiplication, shiftsubtract division, floatingpoint numbers, and/or floatingpoint arithmetic (no need to know floatingpoint instructions in MIPS). Chapter 5  Data path and control: problem very likely on singlecycle 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 sixweek session is not long
enough for covering the entire 900page 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

