DOC PREVIEW
U of I CS 232 - Final Exam

This preview shows page 1-2-3-4-5 out of 15 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 15 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 15 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 15 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 15 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 15 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

CS232 Final ExamMay 10, 2002Question 1: MIPS programmingQuestion 1 continuedQuestion 2: ForwardingQuestion 2 continuedQuestion 3: Pipelining performanceQuestion 3 continuedQuestion 4: Cache performanceQuestion 4 continuedQuestion 5: Cache computationsQuestion 5 continuedQuestion 6: Input/OutputQuestion 6 continuedMIPS InstructionsPipelined Datapath1CS232 Final ExamMay 10, 2002Name:• This exam has 15 action-filled pages, including this cover.• There are six questions, worth a total of 150 points.• Pages 14-15 contain a summary of the MIPS instruction set and a diagramof a pipelined datapath. You may tear these sheets out.• No other written references or calculators are allowed.• Write clearly and show your work. State any assumptions you make.• You have 3 hours. Budget your time!Question Maximum Your Score125225325425525625Total 1502Question 1: MIPS programmingWe’ll start off by writing some MIPS functions to solve a common technical interview question: how can you reverse the order of the words in a string? For example, reversing the words in the string I Love Lucywould result in Lucy Love I.A string is just an array of bytes, with each byte representing one character. The last byte of the array is always 0, to indicate the end of the string. Also, a space is represented by the value 32. For instance, the string above might be stored in memory from addresses 500–511 as follows.Part (a)First write a function rev, which simply reverses bytes in an array. The arguments passed in $a0 and $a1 are the starting address and the number of bytes to reverse. For example, invoking rev for the string above with $a0 and $a1 set to 502 and 4 should change the string to I evoL Lucy. There is no return value. Make sure to follow all MIPS calling and register save conventions. (10 points)\0ycuLevoLICharacter0121991177632101118111763273Byte511510509508507506505504503502501500Address3Question 1 continuedPart (b)Using the rev function, you should now be able to write revwords to reverse the order of the words within a string. The only argument is the starting address of the string, passed in $a0. Again, there is no return value. You may write additional “helper” functions if you like, but be sure you follow all MIPS calling and register save conventions. (15 points)You can implement revwords according to the following basic algorithm.1. Call rev to completely reverse the original string. For example, I Love Lucy becomes ycuL evoL I. Remember that strings are terminated by a 0 byte.2. Then use rev to reverse each word in the new string—ycuL evoL I becomes Lucy Love I. You canassume that “words” are separated by a space character, with the byte value 32.4Question 2: ForwardingConsider the pipelined datapath shown on page 15. Part (a)Describe the difficulty in executing the following instructions in this datapath. How many stall cycles must be inserted to correctly execute this code? (5 points)sub $a3, $a3, $a1beq $a3, $0, SomewhereOverTheRainbowPart (b)Explain how the number of stalls could be minimized with forwarding. Show how muxes might be added to the pipelined datapath on the next page, and discuss how they can be controlled by a forwarding unit. Giving equations is the most concise approach, but in any case make sure your description is clear and precise.You can assume the register file and ALU have the same latency, while muxes have negligible delays. You only need to consider dependencies between branches and R-type arithmetic instructions with the format shown below—you don’t have to worry about loads or other I-type instructions. (20 points)5-010-615-1120-1625-2131-26BitsfuncshamtrdrtrsopFields5Question 2 continuedZeroResult010101012010120140AdrsData RAMDataForwardControlHazard++PCAdrsInstr.RAMR1R2WrData12Registers=ID/EX.RegisterRtID/EX.MemReadRtRsPC WriteIF/ID.Write× 4ExtIF.FlushRtRdRsIF/IDID/EXEX/MEMMEM/WBEX/Mem.RegRdMEM/WB.RegisterRdMEM/WB.RegWriteEX/Mem.RegWrite6Question 3: Pipelining performanceHere is a short MIPS assembly language loop. (This is a simpler version of a very common operation in scientific applications.) Assume that we run this code on the pipelined datapath shown on page 15.Part (a)Find the number of clock cycles needed to execute this code, accounting for all possible stalls and flushes. Assume that $a3 is initially set to 100. (5 points)Frodo:lw $t0, 0($a1)mul $t1, $t0, $a2lw $t0, 0($a0)add $t0, $t0, $t1sw $t0, 0($a0)sub $a3, $a3, 1addi $a0, $a0, 4addi $a1, $a1, 4bne $a3, $0, FrodoPart (b)Rewrite the code to eliminate as many stalls as possible. Show your modified assembly language program below. (10 points)7Question 3 continuedPart (c)What is the performance improvement of your new function as compared to the original one? Again, assume that $a3 is initially set to 100. (5 points)Part (d)Suggest a way to rewrite this code to reduce the number of cycles lost to flushes. You do not have to show any actual code. (5 points)8Question 4: Cache performanceAMAT = Hit time + (Miss rate × Miss penalty)Memory stall cycles = Memory accesses × miss rate × miss penaltyThe Corleone 2000 processor has two levels of data caches, with the characteristics shown below. You can also assume that it takes 50 clock cycles to request and complete a 32-byte transfer between main memory and the L2 cache.Part (a)How many bits of a 32-bit main memory address would be used as the tag, index and block offset fields, for each of the two caches above? Assume that 1 KB = 210bytes. Also, 32 = 25and 256 = 28. (5 points)2%5%Miss rate19 cycles1 cycleHit time4-wayDirect-mappedAssociativity32 bytes8 bytesBlock size256 KB32 KBData sizeL2L1Block offsetIndex sizeTag sizeL2L1Part (b)Find the average memory access time for both the L2 and L1 caches. (5 points)9Question 4 continuedPart (c)While you’re still in the mood, let’s look at the Frodo code again. Assume that $a0 and $a1 are initially 3000 and 4000, and the loop iterates 100 times. Both level 1 and level 2 data caches are empty at first. How many memory stall cycles would be required for theexecution of this code, according to the formula and table givenon the previous page? (5 points)Frodo:lw $t0, 0($a1)mul $t1, $t0, $a2lw $t0, 0($a0)add $t0, $t0, $t1sw $t0, 0($a0)sub $a3, $a3, 1addi $a0, $a0, 4addi $a1, $a1, 4bne $a3, $0, FrodoPart (d)Briefly discuss how each of the different write policies (write-back or write-through for hits, and allocate-on-write or write-around for misses) might affect the performance of


View Full Document

U of I CS 232 - Final Exam

Documents in this Course
Goal

Goal

2 pages

Exam 1

Exam 1

5 pages

Exam 1

Exam 1

6 pages

Exam 2

Exam 2

6 pages

Exam 1

Exam 1

5 pages

Load more
Download Final Exam
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 Final Exam 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 Final Exam 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?