DOC PREVIEW
U of I CS 232 - Midterm Exam - CS 232

This preview shows page 1-2 out of 7 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 7 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 7 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 7 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

1CS232 Midterm Exam 3December 1, 2004100Total403402201Your ScoreMaximumQuestionName:Section: This exam has 7 pages including the pipelined datapath diagram on the lastpage, which you are free to tear off. You have 50 minutes, so budget your time carefully! No written references or calculators are allowed. To make sure you receive credit, please write clearly and show your work. We will not answer questions regarding course material.2Question 1: Conceptual Questions (20 points).Part (a)An ideal pipelined machine has a sustained CPI of 1. List causes (discussed in class) for a pipelined machine having a CPI above 1. We’re looking for 3 distinct causes, but you may write up to 5 answers. (10 points)1.2.3.4.5.Part (b) What does LRU stand for? What is it? What property of programs does it exploit? Be specific, but limit your answers to three sentences. (10 points)3Question 2: Cache Organization and Performance (40 points)Part (a) Compute how many bits of storage are required to implement the following cache for a machine with 32-bit addresses (include all data, tag, and control state): a write-back, write-no-allocate, 4-way set associative cache with 1024 32-byte blocks. Five bits are required for each set to store full LRU (4! = 4x3x2x1 = 24 < 25). You can leave your answer as an expression. Show work for partial credit. (10 points)Part (b)Given a direct-mapped cache with 4 blocks of 4 bytes, which of the following byte accesses hit? (10 points)110101100001001110100101110010010001001100001111100111Miss110001Hit/MissAddress (binary)  4Question 2, continuedPart (c) Compute the average memory access time for a 4-way set-associative, unified L2 cache with 64B blocks and a 95% hit rate. The access time for this 1MB cache is 8 cycles, and it take 80 cycles to move a 64B block from memory to the cache. You can leave your answer as an expression. (10 points)Part (d)Consider a cache that holds two blocks of 1-byte each. Write 2 sequences of accesses using the following notation: A1, A2, A3, etc. are distinct addresses that map to the first block, and B1, B2, B3, etc. are distinct addresses that map to the second block of a direct mapped cache. For example: A2, B1, B1, A9, B7, A6. Sequence 1: Write a sequence of at most 5 accesses that has a better hit rate on a direct mapped cache than on a fully-associative cache (using LRU). (5 points)Sequence 2: Write a sequence of at most 5 accesses that has a better hit rate on a fully-associative cache (using LRU) than on a direct mapped cache. (5 points)5Question 3: Pipelining (40 points)The inner loop for the C code shown can be written as:loop: sub $t3, $t3, 1add $t0, $t0, 4add $t1, $a0, $t0lw $t2, 0($t1)add $t2, $t2, 1sw $t2, 0($t1)bgt $t3, $zero, loopPart (a)Label all dependences within one iteration of this code (not just the ones that will require forwarding). One iteration is defined as the instructions between the sub and bgt,inclusive. (5 points)Part (b)If the loop executes many times, we are mostly concerned with the performance of the “steady state” execution where the branch is taken (i.e., make the common case fast). Assume the pipeline with forwarding (you can assume that a register can be read in the same cycle it is written) but without branch prediction shown on the last page. Using the grids below, indicate the pipeline stage each instruction is in for each cycle (stalls can be marked with an S or --). (15 points)for (int i = 0 ; i < max ; ++ i) {++ A[i];}N+1sub21098NbgtNswNaddNlwNaddFNaddWMEDFNsub76543210987654321iterInst6Question 3, continuedPart (c)Label each instruction with the forwarding paths it requires (1, 2, 3, 4: as labeled on the final page of this exam)? (5 points)loop: sub $t3, $t3, 1 _________add $t0, $t0, 4 _________add $t1, $a0, $t0 _________lw $t2, 0($t1) _________add $t2, $t2, 1 _________sw $t2, 0($t1) _________bgt $t3, $zero, loop _________Part (d)Re-write the code on the previous page (same as the code above) for optimal performance (10 points). In addition, try to minimize the number of required forwarding paths and explain which forwarding paths are still required. (5 points)Extra Credit:Explain (in words) how the code could be re-written so that it executes without stalls or unnecessary instructions on hardware with no bypassing. (+5 points)7Pipelined DatapathHere is the final datapath that we discussed in class.• Forwarding is performed from the EX/MEM and MEM/WB latches to the ALU inputs. The control equation for the Rs register input to the ALU is shown at the bottom of the page. The Rt input is similar.• Branch resolution takes place in the Decode stage.• A hazard unit inserts stalls for lw instructionsZeroResult010101012010120140AdrsData RAMDataForwardControlHazard++PCAdrsInstr.RAMR1R2WrData12Registers=ID/EX.RegisterRtID/EX.MemReadRtRsPC WriteIF/ID.Write××××4ExtIF.FlushRtRdRsIF/IDID/EXEX/MEMMEM/WBEX/Mem.RegRdMEM/WB.RegisterRdMEM/WB.RegWriteEX/Mem.RegWriteif ((EX/MEM.RegWrite == 1) and (EX/MEM.RegisterRd == ID/EX.RegisterRs)) then ForwardA = 1else if ((MEM/WB.RegWrite == 1) and(MEM/WB.RegisterRd == ID/EX.RegisterRs))then ForwardA = 2ControlMuxCPI = Cycles Per InstructionAMAT = hit_time + (miss_rate * miss_penalty)Memory Stall Cycles = # loads * miss_rate *


U of I CS 232 - Midterm Exam - CS 232

Download Midterm Exam - CS 232
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Midterm Exam - CS 232 and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Midterm Exam - CS 232 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?