cse240a: Assignments

Homework Policy

• Homeworks are due by 4:00pm on the due date unless otherwise noted.
• Turn in your printed solutions to Bryan'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.
• Studying in groups is definitely encouraged.
• Typically, homework assignments may be graded based on a statistical subset of the problems in each assignment.
• Homework 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 think 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: by September 30, 2011

We would like to make all grading transparent and available as soon as possible. Because of this, we are requesting students to choose a secret username which will appear in grade sheets.

You will submit your secret username via forms of Google documents. Form can be found here Please do not make it obvious to identify you. In rare case of name conflicts, you will be notified to resubmit.

Due: 1 hour before every class meeting

This course is discussion-based, so it is essential that you read the papers and come to class prepared to discuss. The purpose of these summaries to ensure that you do so and provide some structure to how your approach the papers.

Reading research papers critically is an essential skill that you need to develop in graduate school. It will serve you will regardless of what kind of job you end up with. There have been several articles written about how to about this. As your first excercise (in this course, anyway) in reading and synthesizing several articles on a subject, take a look at these three: one, two, three.

You will submit your paper reviews via forms of Google documents. Form can be found here Please answer all questions thoroughly and thoughtfully.

You do not need to submit summaries for papers that you present as part of your presentation. This is the case even if you are presenting with a partner.

Due: First week of class

Look at the course schedule and select a day/topic you would like to present. Assignments are first-come, first serve.

During class, I will let you know when you can send email (to the instructor and the TA) requesting a particular paper. Emails received before this time will not be accepted.

Due: Two weeks prior to your presentation

Make an appointment with me no more less than two weeks before your presenation day to discuss the topic. I will point you in the direction of extra readings, etc. that you should look at.

To ensure that we meet early enough, you should drop me a line about the meeting at least several days in advance.

Due: One week before your presentation

To prepare your slides, you should become an expert on the subject you are presenting. This means you should read papers in addition to the ones listed on the course web site and in addition to the ones I give to you during our meeting.

A goal to strive for is to be able to answer any question that someone might ask after reading the assigned papers. At the very least, this means you should have tried to find answers to all the questions that arose in your mind while reading those papers. You should also have good answers to most of the questions suggested in the guides to reading papers that you read at the beginning of the quarter.

Once you have become an expert on the subject, you need to condense all the information about the papers into about 45 minutes worth of slides. Typically, slides take about 1-2 minutes each. Use that value as a guide, but also practice presenting the slides to see if that guideline holds for you.

Spend time thinking about the slides and pay attention to the following issues:

• Do they tell a story? You should takes us on a little journey from motivation, to approach, to data, to conculsions, to your critiques of the paper overall.
• Are they well-organized? If I fell asleep for 2 minutes how long would it take for me to figure out what is going on after I woke back up? "Roadmap" slides can be useful for this.
• Are you getting lost in the details? What are the most important things to know about this paper? How does it relate to the other papers we have read? What is the most exciting thing about it?
• Don't spend too much time bashing the paper. All papers have problems, but they often also contain a kernel of an interesting idea. Understanding that that kernel is more important than dwelling on the paper's flaws.

Due: The day of your presentation

You will present your presentation during the second half of class. As usual, we will collect a set of questions about the material that you will look into and present answers to during the next class meeting.

Due: The class period following your presentation

Find answers to as many of the questions we raise in class as possible. This may mean reading some extra papers.

Changelog

Due: October 26

You are strongly encouraged to work on this assignment in groups of two. If you do work in a group of 2, submit only 1 report (but make sure both names are on it). While you may have your partner do all the work, this will only hurt you when the midterm and final come around so don't do it.

1. Anish, a graduate student, is designing a computer system that is going to process a set of 1000 30GB data sets from a near real-time climate simulation project that runs each day at the San Diego Supercomputing Center (SDSC). The job will start at 10pm and it must finish by 8am. Anish has two advisors who co-advise him: Helena and Rajesh. Helena explains that in designing the system to perform this computation, latency is critical. Rajesh, in a separate meeting, explains that Anish will need to pay close attention to system bandwidth. Explain why Helena and Roger are both right.
2. For the following code, would a stream buffer or a victim buffer be more effective? Why?

   		      void foo(List *head) {
   		         List * cur = head;
   		         while(cur->next) {
   		            cur = cur->next;
   		         }
   		      }
   		      

3. Assume my cache has 16 byte lines, 1024 lines, and is 2-way set associative. Integers are 4 bytes. Give the C code for a loop that has a very poor hit rate in this cache but whose hit rate raises to almost 100% if you double the number of lines to 2048.
4. Consider the following code. Integers and pointers are both 4 bytes.

   		      struct List {
   		         List * next;
   		         int data;
   		      }
   
   		      void foo(List *head) {
   		         List * cur = head;
   		         while(cur->next) {
   		            cur = cur->next;
   		         }
   		      }
   		      

   For a given total cache size, what cache line size will provide the best performance for this code? (hint: Your answer should not depend on the number of lines or the associativity of the cache.)
5. I like to evaluate computers using the following metric:
   ======= Awesomensess = (MB * CPUs * (MB/s of memory bandwidth)²)/(Watts * Dollars^0.5)
   What aspects of a computer system do I value most highly? Which do I dislike the most?
   If system A costs twice as much as system B, how much additional memory bandwidth does A need to provide in order for A and B to be equally awesome?

6. One goal of a single-address space operating system (SAOS) is to reduce the cost of sharing large in-memory objects between processes. In a conventional, multi-address space system sharing requires a copy from one address space to another. In a SAOS, no copy is required, but the system will need to do additional work to manage protection domains.

   If my application spends 45% of its time copying data to support sharing, what's the maximum possible speedup that the SAOS can provide for my application? and why?

7. In the text book you read about the benefits of a virtually indexed, physically tagged cache. The SAOS papers adds a PLB to the system as well.

   In order to minimize the cost of PLB misses, you would like to have a very, very large PLB. The access to such a PLB will be slower than the L1 access time. How can you add this large PLB to the system without impacting L1 access time while still ensuring that the currently running process cannot access any data it does not have permissions for?

   Draw a block diagram including the processor, the TLB, the PLB, and the L1 cache to illustrate your solution. Including any other changes required to the system to make it work.

8. Why is branch prediction accuracy so much more important in deeply pipelined processors?
9. The processor design that you are working on currently has 97% instruction cache hit ratio, 90% data cache hit ratio, and 80% branch prediction accuracy. Given a workload of 1 branch in every 5 instruction and 1 memory access in every 3 instructions, which portion of the hardware should you focus to improve: instruction cache's hit ratio, data cache's hit ratio, or branch predictor's accuracy? Say that the penalty for L1 cache misses and branch mispredictions are both 5 cycles.
10. J. E. Smith's study on branch prediction introduces saturating counter based branch prediction. Experimental results show that 2-bit counters outperform 3-bit counters due to program inertia. Provide a code sample for which a 3-bit counter performs better and another for which a 2-bit counter is better.
11. For each labeled branch in the code below (except the backward branch on the outer loop) which of the following branch predictors will perform best.
    • Local history (3 bits) to select a 2-bit predictor
    • Global history (3 bits) to select a 2-bit predictor
    • PC to select a 2-bit predictor
    • static (you can choose the direction)

    		for (j = 0; j < 100; j++) {
    			for (i = 0; i < 100;i++) {
    
    		                // rand3() returns 1,2, or 3 with equal probabilty
    				if(rand3() <= 1) { // A
    				}
    
    				if(i % 3 == 0) {// B
    				}
    
    				if (i % 2 == 0) {// C
    				}
    
    				if(i % 6 ==0) {// D
    				}
    
    				if (i < 4) { // E
    				}
    
    			}  // F
    		}
    			

Due: December 2

You are strongly encouraged to work on this assignment in groups of two. If you do work in a group of 2, submit only 1 report (but make sure both names are on it). While you may have your partner do all the work, this will only hurt you when the midterm and final come around so don't do it.

1. All the threads in an SMT processor share a single L1 data cache and a single L1 instruction cache. How could this potential hurt performance of the threads running on the processor? How could it help? Suggest a way that the architecture could limit the damage and maximize the gain. Would you expect the benefits to larger or smaller for the instruction cache or the data cache? Why?
2. Consider the following code, and assume that integers are 8 bytes and that ThreadA() and ThreadB() are run on different processors. You notice that when ThreadA() runs alone, it can update A 1billion times per second. When ThreadB() runs alone, it increments B 1Billion times per second. However, when they simultaneously on different processors, they each only manage to increment their variable 100 million times per second. Why? How would you fix it?

   	int A;
   	int B;
   	
   	void ThreadA() {while (1) {A++;}}
   	void ThreadB() {while (1) {B++;}}
   	

3. Imagine a web serving data center that serves billions of web requests per day. What kind of processor architecture would be the best fit for such an application? why? (This question is intentionally opened ended. State your assumptions and your reasoning.)
4. Both TXflash and FlashStore provide hardware support for particular applications, much as cryptomaniac and c-cores do. How is the motivation for TXFlash and FlashStore different than the motivation for those other projects? How is it the same? Do you think that TXFlash or FlashStore has a better or worse chance of being widely adopted than c-cores? Why?
5. The single-ISA heterogeneous multiprocessor paper and the conservation cores paper take very different approaches to specialization. Give 3 advantages of each relative to the other.