cse240a: Assignments

Homework Policy

• Homeworks are due by 1:45pm 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.
• 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: 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 the "Assessments" in CSE240A WebCT. To access the WebCT, you need to login http://webctweb.ucsd.edu first. Then select "CSE 240A - 2010 Winter Swanson".

You do not need to submit summaries for papers that you present as part of assignment 2.

Due: First week of class

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: January 19

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

Due: January 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. Consider the matrix_add function shown below:

   	int matrix_add(int a[128][128], int b[128][128], int c[128][128])
   	{
   	  int i, j;
       	  for(i = 0; i < 128; i++)
                for(j = 0;j < 128; j++)
                 	c[i][j] = a[i][j] + b[i][j];
             return 0;
           }                
   	

   In each iteration, the compiled code will load a[i][j] first, and then load b[i][j]. After performing the addition of a[i][j] and b[i][j], the result will be stored to c[i][j]. The processor has a 64KB, 2-way, 64Byte-block L1 data cache, and the cache uses LRU policy once a set if full. The L1 data cache is write-back and write-allocate. If the addresses of array a, b, c are 0x10000, 0x20000, 0x30000 and the cache is currently empty, please answer the following questions:
   • What is the L1 D-cache miss rate of the matrix_add function? How many misses are contributed by compulsory miss? How many misses are conflict misses?
   • If the L1 hit time is 1 cycle, and the L1 miss penalty is 20 cycles. What is the average memory access time?
   • Continued from the previous problem. If we add a victim cache that can hold 8 entries into the L1 data cache, what is the average memory access time? Assume that it takes 2 cycles if the data is a hit in victim cache.
   • A cache may use a write buffer to reduce write latency. Would there be any advantage to combining write buffer and victim cache into a single piece of hardware? Would there be any disadvantages?
2. You are building a system around a single-issue in-order processor running at 1 GHz and has a CPI of 0.7 excluding memory accesses. The only instructions that read or write data from memory are loads (20% of all instructions) stores (5% of all instructions).
   The memory system for this computer is composed of a split L1 cache that imposes no penalty on hits. Both the I-cache and D-cache are direct mapped and hold 32KB each. The I-cache has 2% miss rate and 32-byte blocks, and the D-cache is write through with a 5% miss rate and 16-byte blocks. There is a write buffer on the D-cache that eliminates stalls for 95% of all writes. You may assume the caches use write-allocate.
   The 512KB write-back, unified L2 cache has 64-byte blocks and an access time of 10ns. It is connected to the L1 cache by a 128-bit data bus that runs at 200 MHz and can transfer one 128-bit word per bus cycle. Of all memory references sent to the L2 cache in this system, 80% are satisfied without going to main memory. Also 50% of all blocks replaced are dirty.
   The 128-bit-wide main memory has an access latency of 60ns, after which any number of bus words may be transferred at the rate of one per cycles on the 128-bit-wide 133 MHz main memory bus.
   • What is the overall CPI, including memory accesses?
   • You are considering replacing the 1 GHz CPU with one that runs at 2 GHz, but is otherwise identical. How much faster does the system run with a faster processor? Assume the L1 cache still has no hit penalty, and that the speed of the L2 cache, main memory, and buses remains the same in absolute terms (e.g. the L2 cache still has a 10 ns access time and a 200 MHz bus connecting it to the CPU and L1 cache).
3. Smith and Goodman found that for a given small size, a direct-mapped instruction cache consistently outperformed a fully associative instruction cache using LRU replacement.
   • Explain how this would be possible. (Hint: You can't explain this using the three C's (compulsory, capacity, conflict) model of cache misses because it "ignores" the cache policy.)
   • Explain where replacement policy fits into the three C's model, and explain why this means that misses caused by replacement policy are "ignored"--or, more precisely, cannot in general be definitively classified--by the three C's model.
   • Are there any replacement policies for the fully-associative cache that would outperform the direct-mapped cache? Ignore the policy of "do what a direct mapped cache would do."
4. Way prediction allows an associative cache to provide the hit time of a direct-mapped cache. The MIPS R10K processor uses way prediction to achieve a different goal: reduce the cost of a chip package.
   The R10K hardware includes an on-chip L1 cache, an on-chip L2 tag comparison circuitry, and an on-chip L2 way prediction table. L2 tag information is brought on chip to detect an L2 hit or miss. The way prediction tables contains 8K 1-bit entries, each corresponding to two L2 cache blocks. L2 cache storage is built externally to the processor package, must be two-way associative, and may have one of several block sizes.
   • How can way predictoin reduce the number of pins needed on the R10K package to read L2 tags and data, and what is the impact on performance compared to a package with a full complement of pins to interface to the L2 cache?
   • What is the performance drawback of just using the same smaller number of pins but not including way prediction?
   • If a 512 KB L2 cache has 64-byte blocks, how many way prediction entries are needed? How would the R10K support this need?
   • For a 4 MB L2 cache with 128-byte blocks, how is the usefulness of the R10K way prediction table analogous to that of a branch history table?
5. You are interested in calculating the access time of a 128KB, 4-way set associative write-back cache with 32 byte blocks. As you learned in class, there are various ways to index and tag your cache in relation to your virtual memory system. Consider that you have the following information about your system:
   • Accessing the TLB: 5ns
   • Indexing the cache to access its data portion: 10ns
   • Indexing the tag array of the data cache: 8ns
   • Tag comparisons: 4ns
   • Multiplexing the output data: 2ns

   Assume that all other parts are insignificant to the access time of the cache.

   For the following configurations, calculate the amount of time it takes to get data from the cache on a load hit. Assume that your page size is 4KB. Be sure to explain your answers; just writing down numbers won't get you credit even if they end up being correct.

   1. A physically-indexed, physically-tagged cache
   2. A virtually-indexed, virtually-tagged cache
   3. A virtually-indexed, physically-tagged cache
   
   

Changelog

Due: February 16

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. Use the following code fragment:

   Loop:	L.D.	F1,0(R3)
   	ADD.D	F2,F1,F4
   	MUL.D	F1,F2,F6
   	ADD.D	F1,F1,F5
   	ADD.D	F7,F7,F1
   	DADDI	R2,R2,-1
   	BNEZ	R2,Loop
   	DADDI	R6,R6,#4
   	L.D	F3,0(R6)

   The initial value of R2 is 2. Assume the branch instruction is in the BTB and the branch is always predicted taken.

   • Please list the instruction sequenece will executed. Please also list all true dependences (RAW), anti-dependences (WAR) and output dependences (WAW) in the instruction seqeuence.
   • Assuming that you are given a processor using Tomasulo algorithm for instruction scheduling. The execution time and reservation stations for each functional unit is listed as below:

     Functional Unit	Execution Time	Reservation Stations
     Int ALU	1 cycle	3
     FP Add	2 cycle	2
     FP Mult	3 cycle	2
     Memory Access	1 cycle	4 for Address Calculation, 3 for loads, 3 for stores
     Branch	1 cycle	1

     Please draw the pipeline diagram according to the Tomasulo handout for the given code.
   • Assuming that you are using an Alpha 21264-Like processor that is very similar to a real Alpha 21264 except the processor has the same function unit execution time and branch predictor as the previous problem. Please draw the pipeline diagram for the given code. (You may assume the processor has the same number of functional units as the previous problem. Ignore the functional unit cluster problem and assume there are bypass paths for memory and ALU operations)
   • Assuming R2 is very large, which of the above performs better and why?
2. You are asked to evaluate the performance of the following branch prediction schemes:
   • I: Static backward taken, forward not taken.
   • II: Local predictor with two-bit state machine (Saturating counter/Bimodal).
   • III: Global predictor based on 6-bit history and a 1-bit state machine associate with each entry. (6,1) correlating predictor.
   Now, you are given the following code segment. Assume each of the branch PC never cause conflicts/alias with other branches and the predictors are intialized as all zeros. Please evaluate the branch prediction accuracy for all the give prediction schemes.

   •                 int i, j;
                     for(i = 0; i < 100; i++) // only one branch at the end of the loop
                     {
                         for(j = 0;j < 5; j++) // only one branch at the end of the loop
                             c[i][j] = a[i][j] + b[i][j];             
                     }
                 

   •                 int i, j;
                     for(i = 0; i < 100; i++) // only one branch at the end of the loop
                     {
                         for(j = 0;j < 2; j++) // only one branch at the end of the loop
                         {
                             if(j%2) // j%2 == 0 means taken
                                 c[i][j] = a[i][j] + b[i][j];
                         }
                     }
                 

Changelog

Due: March 11

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. Consider the following three CPU organizations:
   I. CPU CMP: 2-core superscalar processor with out-of-order issue capabilities. Each core has two functional units. Only a single thread can run on each core at a time.
   II. CPU FMT: A fine-grained multithreaded processor that allows instructions from two threads to be run concurrently on the two functional units, though only instructions from a single thread can be issued to run on any cycle.
   III.CPU SMT: An SMT processor that allows instructions from two threads to be run concurrently on the two functional units, and instructions from either or both threads can be issued to run on any cycle.
   Assume we have two threads A and B to run on these CPUs that include the following operations:
   

   Thread A	Thread B
   A1- takes 2 cycle to execute A2- depends on the result of A1 A3- conflicts for a functional unit with A2 (They must use the same one) A4- depends on the result of A2	B1- no dependencies B2- conflicts for a functional unit with B1 (They must use the same one) B3- no dependencies B4- depends on the result of B2

   How many cycles will it take to execute these two threads on each of the above three processors? How many issue slots are wasted due to hazards? (You may assume these processors have ful capability of eliminating false dependencies and all the instructions are already in instruction queues. If not specified, the instruction will take one cycle to execute)
2. A simulation study shows that the average branch misprediction rate of selected SPEC92 benchmarks nearly doubles from 5% to 9.1% while going from 1 thread to 8 threads in an SMT processor. However, the wrong-path instructions fetched drops from 24% on a single-threaded processor to 7% on an 8-thread SMT processor.
   1. Please give the reason why the branch misprediction rate increases.
   2. Why is the number of fetched wrong-path instructions decreases? (Hint: This is related to the scheduling of instructions)
   3. Another simulation study for online transaction-processing workload, OLTP, shows a decrease in instruction cache miss rate from 14% to 9%. When is such a decrease, called constructive cache interference, likely to happen?
3. Assume that you are running the following code segment on a symmetric multicore processor, where the inital values of both x and y are 0.
   

   Core 1	Core 2
   x = 2; w= x+y+1;	y=2; z=x+y;

   1. Please list all the possible resulting values of w, x, y, z. For each possible outcome, explain how we might arrive at those values. You may need to examine all possible interleavings of instructions.(If you feel that there are too many possibilities, you may assume the cache is coherent.)
   2. If you wanted to make the system sequentially consistent, what are the key constrains you need to impose?
   3. Assume the processor supports "relaxed memory consistency" model, which requires synchronization to be explicitly identified. To achieve "relaxed memory consistency" model, the processor provides a "barrier" instruction, which ensures that all memory operation preceding the barrier instruction complete before any memory operations following the barrier are allowed to begin. Where would you include the barrier instructions in the above code segment to get the final result as x = 2, y = 2, w = 5, and z = 4?