cse141: Assignments

Homework Policy

• Homeworks are due at 11am on the due date unless otherwise noted.
• Turn in your printed solutions to Sat'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

Changelog

Due: January 15

There is a link to the coures discussion board on the course homepage. Your login is your official UCSD user name (i.e., your @ucsd.edu email address without the "@ucsd.edu" part). Password is your PID.

Take some time to explore the discussion boards features. If you like, you can configure it to send everything to you by email, so you don't have to visit the website regularly.

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

Need an account? If you are enrolled through concurrent enrollment or, for some other reason do not have an account, email Sat with your prefered username and he will create an account for you.

Due: January 15

Email Sat your grading code name. It should be one word and less that 10 characters.

Due: Throughout the quarter

Participation in the discussion board is mandatory. It forms a significant fraction of your class participation grade.

If you have questions about the material in the class, post them to the general discussion forum. Sat and I will hold off on answering the questions for a while to give other student an opportunity to reply.

Posting Guidelines

• Be nice!!! There are no dumb questions, but there are plenty rude, disrepectful, and unconstructive answers. They will not be tolerated.
• Use desciptive subject lines so everyone can tell what your message is about.
• Anything related to computer system design is fair game in the discussion forum, even if we have not discussed it in class.
• Direct discussion of homeworks is not allowed! Obviously, you may have questions related to topics covered in the homework. You can ask these questions, but pose them more generally. Likewise, do not post partial or full solutions to homework problems.
• Questions and clarifications about the homework problems should go to the Admin forum. Sat and I will answer these questions post-haste.

Changelog

Due: January 22

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

• Chapter 2: 2.29
• Chapter 4: 4.1, 4.7a, 4.10
• Extra Problem 1:
  Decode the following MIPS instructions into assembly language instructions: Hint: Use the MIPS Data Reference Sheet (green).

  The break down into groups of 4 is just for readability.

  a) 0000 0000 1110 1000 1001 1000 0010 0000

  b) 0010 0001 0000 1001 0000 0000 1111 1111

  c) 0000 1000 0000 1100 0000 0000 0000 0001

Due: January 22

• Chapter 2: 2.6, 2.30, 2.32, 2.37
• Chapter 4: 4.8, 4.9, 4.11, 4.12, 4.17, 4.18

Changelog

Due: January 29

Unless otherwise noted, the following problems are from the 3rd edition of the Patterson & Hennessy textbook. You should also note that the problems from chapter 4 are on the book's companion CD.

• Chapter 4: 4.22
• Chapter 5 (revised printing): 5.2, 5.11, 5.28, 5.32
• Chapter 5 (original printing, see note above): 5.2, 5.11, 5.30, 5.34

Due: January 29

• Chapter 4: 4.19, 4.20
• Chapter 5 (revised printing): 5.3, 5.8-5.10, 5.12, 5.13, 5.27, 5.30, 5.31, 5.36
• Chapter 5 (original printing): 5.3, 5.8-5.10, 5.12, 5.13, 5.29, 5.32, 5.33, 5.38

Changelog

Due: February 7

Because you did not cover the multicycle CPU before last HW, this assignment will again have questions on this topic. There is no given list of "recommended" problems for this assignment. Instead, you should go through the recommended problems from the last assignment (specifically those on multicycle design).

• Problem 1: This problem is similar to problem 5.30 (or 5.32 in the original printing). However, here you must implement a new instruction called clear memory range (cmr). cmr takes a beginning memory address (in base+offset format) and register that specifies how many consecutive memory locations must be cleared. It then stores a "0" value in all memory locations starting at that beginning memory location and ending at that location plus the number given by the register. In RTL, the instruction performs the following work: Mem[R[rs]+imm, ..., R[rs]+imm+R[rt]] = 0. You may add some hardware to the datapath but you may not modify the memory. Show the changes to the datapath (available here), if any, and update the multicycle finite-state machine (available here) to include the cmr instruction.
• Problem 2: Your employer, SatTech, has decided to change their flagship product, the X2000 CPU, from a single cycle to a multicycle design. The X2000 has the same exact datapath as the single cycle CPU explored in your textbook. Assume the following times to use specific parts of the datapath:
  • Memory: 2.5ns
  • Register File: 1ns
  • ALU: 1.5ns
  Part a: Assuming that all other times are negligible (e.g. MUXes), what is the cycle time for the single cycle version of the X2000?
  
  Part b: A colleague of yours who is also working on the conversion to multicycle suggests the following cycle breakdown (using the same datapath as the multicycle CPU in the book):
  • Cycle 1: Instruction Fetch
  • Cycle 2: Decode (i.e. register access)
  • Cycle 3: Execute
  • Cycle 4: Memory Access
  • Cycle 5: Register Writeback
  With this setup, what is the cycle time for your colleague's version of the multicycle CPU? If 50% of instructions are ALU-type instructions (e.g. add, sub, etc), 20% are loads, 10% are stores, and 20% are branches, what is the CPI for this multicycle CPU? Is this multicycle CPU faster or slower than the single cycle X2000 and by how much?
  
  Part c: An old friend of yours from SwanSoft says that engineers with her company have managed to use the same multicycle datapath but have gotten better performance than your colleague's multicycle implementation. Of course, due to an NDA, she cannot tell you how. Is her claim possible? If so, show how and give the speedup compared to your colleague's version. If not, explain why not.

Due: February 12

This homework assignment is meant to be practice for pipelining before the midterm on Tuesday, February 12. Since we will not have a chance to grade and return this homework before the midterm, we will be providing solutions to the exam several days before the midterm. As such, you will not be required to turn anything in for this assignment. Please attempt to work on the problems before looking at the solutions as this is always the best way to learn the material.
As always, the following problems are from the revised printing of the 3rd edition of the Patterson & Hennessy textbook unless otherwise specified.

• Chapter 6: 6.2-6.4, 6.17, 6.21
• Additional Problem: You are given a diagram of a pipelined processor here. However, as you will notice, only some of the control signals are given. Based on the given information, list which instructions are in each stage of the pipeline (IF, ID, EX, MEM, and WB). If you cannot specify the exact instruction, list which instructions could be in that stage and what additional information (i.e. control signals) you would need to determine exactly which of these instructions was there.

Due: February 26

Unless otherwise noted, the following problems are from the 3rd edition "revised printing" of the Patterson & Hennessy textbook.

• Chapter 6: 6.34, 6.35, 6.36
• Note: For problem 6.34 assume that the processor has the following stages: IF1, IF2, ID, EX, MEM1, MEM2, WB.

Due: February 26

• Chapter 6: 6.33, 6.37, 6.38, 6.40

Due: March 6

Unless otherwise noted, the following problems are from the 3rd edition "revised printing" of the Patterson & Hennessy textbook.

• Chapter 7: 7.10, 7.29, 7.32
• Problem 7.17: The following problem is labeled as problem 7.17 in your book. It is part of the CD but has been copied here for those who lack the CD:
  Find the AMAT for a processor with a 2 ns clock, a miss penalty of 20 clock cycles, a miss rate of 0.05 misses per instruction, and a cache access time (including hit detection) of 1 clock cycle. Assume that the read and write miss penalties are the same and ignore other write stalls.

Due: March 6

• Chapter 7: 7.9, 7.18, 7.19, 7.25-7.27, 7.33, 7.34

Due: March 20

This homework assignment is meant to be practice for virtual memory before the midterm on Thursday, March 20. Since we will not have a chance to grade and return this homework before the midterm, we will be providing solutions to the assignment several days before the midterm. As such, you will not be required to turn anything in for this assignment. Please attempt to work on the problems before looking at the solutions as this is always the best way to learn the material.
As always, the following problems are from the revised printing of the 3rd edition of the Patterson & Hennessy textbook unless otherwise specified.

• Chapter 7: 7.39 - 7.41, 7.43 - 7.45
• Additional Problems: You should also do the recommended problems from assignment 7. I will be posting solutions to those also.