cse141: Assignments

Homework Policy

• Homeworks are due by 3:30pm on the due date unless otherwise noted.
• Turn in your printed solutions to Hung-Wei's mailbox in the CSE grad student mailroom, unless otherwise noted.
• Late assignments will not be accepted.
• There is no regrading of written homeworks, except for addition errors. No single problem will have a significant impact on your grade.
• Homework must be completed individually.
• Studying in groups is definitely encouraged.
• Typically, homework assignments may be graded based on a statistical subset of the problems in each assignment.
• Homeworks must be typed or clearly handwritten. Illegible/unreadable answers will receive no credit.

Integrity Policy

• Cheating WILL be taken seriously. Doing otherwise is not fair to honest students. It is also not fair to allow the cheater to thing that it is a reasonable alternative in life.
• Please review the UCSD student handbook for more details on Academic Integrity.
• Anyone copying information or having information copied during a test will receive an F for the class and will not be allowed to drop. They will be reported to their college dean. If you can prove non-cooperative copying took place, your grade may be restored, but you must prove it to the dean--I don't want to be involved. Anyone caught cheating or falsely representing the work of others on the homework will not be allowed to turn in further homework. Your grade will be based exclusively on the tests with a penalty of 25% OR GREATER applied.
• We photocopy a random sampling of the exams in order to ensure that students do not modify their tests after they have been returned.
• Online solutions, etc.: A solutions manual exists for this text. Using it, or any solutions you may find on the internet elsewhere IS CHEATING and will be dealt with accordingly. We know what the solution manual solutions look like. Homework is a small fraction of your grade.

Assignments

Due: October 1

Please login into the WebCT blackboard learning system. Your login name is your official UCSD user name (i.e., your @ucsd.edu email address without the "@ucsd.edu" part). Password is your campus wide password.

Select the "CSE 141 - 2009 Fall Swanson" within your course list and then click on the "Discussions" in your course tools. Take some time to explore the discussion board features.

Reading the WebCT discussion board is mandatory. It is the only place that all announcement related to class will be posted.

Due: October 1

Please send TA a code name for the grade sheet (appearing in the grade sheet instead of your real name).

Changelog

Due: October 8

Unless otherwise noted, the following problems are from the Patterson & Hennessy textbook.

• Chapter 2: 2.6(part b only) and 2.18(part b only)
• Solution

Changelog

Due: October 15

Unless otherwise noted, the following problems are from the 4th edition of the Patterson & Hennessy textbook.

• Chapter 1: 1.3.5, 1.4.4 - 1.4.6, , 1.12.5(b), 1.14.4-1.14.6
Solution.

Due: October 15

In this assignment, you may need gcc and gdb. If you are not familiar with these tools, here is a short tutorial about the basic use of them. Now, consider the C code.

1. Please use gcc to generate the assembly for these two functions without optimization (-O0).
   1. Identify each function in the output file, and then create an annotated version of the assembly that includes a brief description of what each instruction is doing (referencing statements in the source code where appropriate), and a count of the arithmetic operations and memory accesses required by each instruction (check the slides from Thursday for an example).
      To figure out what the assembly code does, use the four documents listed below. The first one should have most of what you need and includes common addressing modes as well, so start there. However, depending on which version of gcc your machine has installed and which particular processor you are running, you may encounter additional instructions. The other documents will be helpful in this case. Unfortunately, we have not found a good, concise listing of x86 instructions.
   2. How many arithmetic operations and memory accesses will sum(a, 10) require (assuming 'a' is an array of 10 integers)?
   3. How about max(4, 1)?
2. Repeat the previous problem, but compile the program with optimization level 1 (-O1).
3. Assuming arithmetic operations and memory accesses take the same amount of time, what is the speedup of the optimized version relative to the unoptimized version?

References

• Table of instructions you are likely to encounter in this class (this will be updated throughout the course).
• A good reference for 32bit x86 instructions.
• A very compact summary of x86 instructions.
• A longer document about 64-bit x86..

Changelog

Due: October 22

Unless otherwise noted, the following problems are from the 4th edition of the Patterson & Hennessy textbook.

• Chapter 1: 1.10.4(a)-1.10.6(a), 1.15.5(a)-1.15.6(a) (Please try to apply Amdahl's Law on 1.15.5(a)-1.15.6(a))
• Chapter 4: 4.7.1(b)-4.7.3(b), 4.10.4(b)
Solution

Changelog

Due: October 29

Unless otherwise noted, the following problems are from the 4th edition of the Patterson & Hennessy textbook.

• Chapter 4: 4.15.1-4.15.3, 4.17.4-4.17.6, 4.20.1-4.20.3, 4.22.1 (Do only part b. for all above problems)
Solution

Changelog

Due: November 3

• Chapter 4: 4.22.2-4.22.6(b)
Solution

Changelog

Due: November 12

Unless otherwise noted, the following problems are from the 4th edition of the Patterson & Hennessy textbook.

• Chapter 4: 4.23.3(b), 4.24.1(b)-4.24.3(b)
Solution

Due: November 12

Repeat problem 4.24.2-4.24.3(b), but assume that we are using a 5-bit global history branch predictor. Also assume that the prediction of each global history is based on 1-bit predictor.

Changelog

Due: November 19

Unless otherwise noted, the following problems are from the 4th edition of the Patterson & Hennessy textbook.

• Chapter 5: 5.4.1-5.4.2, 5.4.4-5.4.6, 5.7.1-5.7.6, 5.8.4-5.8.5 (Do only part b. of all above problems). The index field in 5.4 should be 11-5. The local miss rate of DM L2 in 5.8 should be 100%, and the local miss rate of 8-way L2 is 40%.
Solution

Changelog

Due: December 3

Unless otherwise noted, the following problems are from the 4th edition of the Patterson & Hennessy textbook.

• Chapter 5: 5.5.2, 5.10.1, 5.11.1, 5.11.2, 5.17.1, (Do only part b. of all above problems)
• Chapter 6: 6.3.1, 6.3.3
(Do only part b. of all above problems) Solution

Changelog

Due: December 7

Unless otherwise noted, the following problems are from the 4th edition of the Patterson & Hennessy textbook.

• Chapter 7: 7.7, 7.12.1, 7.12.3 (Do only part a. of all above problems)
• Chapter 4: 4.28.2, 4.28.5. 4.32.5(Do part a. of the two problems) Using the following MIPS code:

  			add $1,$0,$0
  			Again: beq $1,$2,End
  			add $6,$3,$1
  			add $8,$4,$1
  			lw $7,0($6)
  			addi $1,$1,1
  			sw $7,0($8)
  			beq $0,$0,Again
  			End:
  			

Solution