Pipelining (Sections 6.1,6.2,6.8)
Memory Hierarchy (Sections 7.1-7.5)
| ||||||||||
Sample QuestionsIdentify the data hazard in the following code (assume the MIPS 5 stage pipeline):
add $t0,$t1,$t2
add $s3,$t0,$t0
For the above problem, if we use forwarding, what is the minimum number of stall cycles that cannot be avoided? Explain! Repeat the above question for this code:
lw $t0,16($sp)
add $s3,$t0,$t0
Given the following timings for various components in a MIPS datapath, compare the speed of a single-cycle implementation vs. a multi-cycle, pipelined implementation (assume 5-stage MIPS pipeline).
Answer: Single cycle would require a cycle time of 10+2+4+10+4 = 30 ns. 10 for Instruction Fetch (memory access)2 for Instruction Decode/Register Fetch (register read) 4 for ALU 10 for Memory Access 4 for Register Write Multicycle pipelined means all operations happen each cycle, so the slowest operation limits the clock speed. In this case the clock would be 10ns, and it takes 5 cycles (50 ns) for a single instruction to exectute. If we assume there are no stalls, this would result in one instruction completing every cycle, for a CPI of 10ns vs. a CPI of 30ns for the non-pipelined, single cycle implementation. Given a cache design and main memory size, be able to tell how many bits are used for each tag and index. For example: Memory adress size is 32 bits, cache is 16K bytes, block size is 4 words (16 bytes). How many tag bits (per cache slot) are needed for each set/slot if the cache is 1) direct mapped, 2) 2-way set associative, 3) 4-way set associative, or 4) fully associative? For the above caches, how many bits are needed for each index? For the above caches, how many total bits are needed to store all the tags (for the entire cache)?. Given a CPI assuming a perfect cache (hit rate 100%), what will the CPI be if the actual hit rate is 90%, the miss penalty is 20 cycles and 25% of the instructions access memory? Another twist on the same problem, compare the performance of two different cache designs given the miss rates of each (need to calculate speedup). Yet another twist: given a processor without a cache and a cache design, calculate the speedup with the cache. Why is minimization of the miss rate (minimizing page faults) so important when designing a virtual memory system? What is address translation and how is it done? What is a translation lookaside buffer? What is a page table? Where is a page table stored? Describe how virtual memory can be used to support multiple processes Describe a program that would benefit from a specific cache architecture (for example, a program that would do much better with a 4-way set associative cache than with a direct mapped cache). Below are some examples of what to expect for questions that cover all the material in the course. The general idea is that you need to draw from your knowledge of multiple topics to be able to answer the questions. The questions on the exam will not be limited to those described below - this is just to give you a general idea of what to expect. Given the description of a program (the instruction mix ratios), and of 2 processors that can run the same program (the clock rates, cache parameters, memory timings), compare the performance of the program on the two processors. Repeat the above calculations for 2 processors, one that uses a single-cycle implementation and the other uses a pipelined, multi-cycle implementation (obviously you will also need to be given information about the number of stalls, etc). Compare the performance of two (small) subroutines given the MIPS assembly language for each implementation of the subroutine. You should be able to do things like estimate the instruction count Given a description of a few instruction and the datapath that supports those instructions, design the logic for the control system (given opcodes, come up with equations and logic for each control line in the datapath). Describe 3 major differences between CISC and RISC instruction sets. Pick the topic you know the most about (from the course), and summarize the important issues. Justify why you think the issues you mention are the most important. Example topics: memory hierarchy, pipelining, datapath and control, instruction sets, etc. |