Mechanisms ECE 3035
Popular in Course
Popular in ELECTRICAL AND COMPUTER ENGINEERING
This 0 page Study Guide was uploaded by Cassidy Effertz on Monday November 2, 2015. The Study Guide belongs to ECE 3035 at Georgia Institute of Technology - Main Campus taught by Staff in Fall. Since its upload, it has received 73 views. For similar materials see /class/233924/ece-3035-georgia-institute-of-technology-main-campus in ELECTRICAL AND COMPUTER ENGINEERING at Georgia Institute of Technology - Main Campus.
Reviews for Mechanisms
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 11/02/15
ECE 3035 Computing Mechanisms Study Guide Solutions Version 10 10 Solutions Problem IN1 3 ports MIPS Assembly Language addi addi addi 1 1 4 bne 1 Part A What are the value of 1 at the following times in the execution of the loop above Assume Array begins at 6000 and Bright begins at 7024 1 when Ic is first executed 6000 1 when Ic is last executed 7020 1 when IE is last executed 7024 Part B Write a code fragment that packs four unsigned eight bit values A B C and D stored in 1 2 3 and 4 in order into a single 32 bit word stored in 1 When complete value A should be stored in the least signi cant byte while value D is stored in the most signi cant byte Use only 1 2 3 4 all of which can be modi ed label instruction comment sll 2 2 8 move B 8 bits left or 112 packBA sll 3316 move C 8 bits left or 113 packCBA s 4 4 24 move D 8 bits left or 114 pockDCBA Part C In a recursive subroutine two registers 1 and 2 and the unmoved return address of the subroutine39s caller must be preserved on the stack prior to the recursive call Write a MIPS code fragment that preserves these three words on the stack addi 12 ad SP sw RA sw 1 1 sw ECE 3035 Compu ring Mechanisms S rudy Guide Solu rions Version 10 Problem INZ 5 par rs MIPS Assembly Language Part A Write a MIPS program fragment that computes 17 B C and puts the result in register 6 Assume B and C are in registers 1 and 2 respectively Use a minimum number of instructions and registers You may reuse registers 1 and 2 sub 112 BzBC addi 6 0 17 6 17 mul r 16 Lo17BC mflo 6 6 resul r Part B Suppose A is stored in memory location 1020 and B is stored in memory location 1024 Write a MIPS program fragment that computes 256 A B 16 and stores the result at memory location 1028 Use a minimum number of instructions and registers lw 110200 1 mem1020 lw 2 10240 2 mem1024 sra 224 2216 add 221 2 AB16 sll 2 2 8 2 256AB16 sw 21028O mem2028 2 Part C Write a MIPS program fragment to jump to address 0xABCD1234 lui 1 OXABCD load upper word ori 1 1 Ox1234 combine wi rh lower word Jr 1 Jump To OXABCD1234 no re since MISASIM does no r suppor r hexadecimal value specifica rion a decimal equivalen r would have To be specified Par l D Suppose an image processing system stores a 512x256 pixel image in memory Each pixel is represented by 8 bits and they are store contiguously in memory How much memory in kilobytes does this require How many bits are needed to address 1 pixel 512 x 256 pixels x1by repixel 29 x 28 217 128 Kby res To address 128 Kby res an address would require a r leas r 17 bi rs Par l E Write a MIPS fragment that exchanges two registers 1 and 2 without using any other registers or memory hint think xor xor 112 11 xor 2 xor 212 21xor 2 xor 21 xor 112 11 xor 2 xor 12 ECE 3035 Computing Mechanisms Study Guide Solutions Version 10 Problem IN3 1 part MIPS and C Part A Consider the following MIPS code which is the packeddataasm example from the rst module httpwww ece ontech J J 39 lm 39 Wcked dataasm Write a C program corresponding to this MIPS code by lling in body of the C program fragment provided below Assume that the registers 2 3 and 6 hold variables Pixels P and Result respectively Computes the OR of four 8 bit pixels packed in a 32 bit data word 2 Pixels packed data word 3 P a single pixel 6 Result bit wise OR of all pixels data Pixels word l286936l decimal equivalent of OxFF3BAlOF text Dilate lw 2 Pixels0 andi 6 55 mask extract PO OxFF logical shift right by 8 bits mask extract Pl shift off Pl 6 P1 or PO mask extract P2 shift off P2 2 is right with just P3 6 P2 or P1 or PO 6 P3 or P2 or P1 or PO srl 2 2 8 andi 3 2 255 srl 2 2 8 or 6 3 6 andi 3 2 255 srl 2 2 8 or 6 3 6 or 6 2 6 333333333 0 int Pixels 42869361 int main int P int Result Pixels amp 255 Pixels Pixels gtgt 8 P Pixels amp 255 Result P I Result Pixels Pixels gtgt 8 P Pixels amp 255 Result P I Result Pixels Pixels gtgt 8 Result Pixels I Result return Result ECE 3035 Computing Mechanisms S rudy Guide Solutions Version 10 Problem IN4 2 parts MIPS Assembly Language Part A Create an assembly language implementation of dot product on two 10 element integer arrays Here the values are placed in an array in static memory using the Word assembler directive When your program completes the result should be returned in register 3 This program computes the dot product of two ten element integer arrays data word 243 459 896 535 264 698 268 281 921 886 B word 864 215 781 151 435 128 276 336 790 825 text 1N4A addi 1 0 A set memory base of array A addi 2 0 B set memory base of array B addi 3 0 0 initialize running sum Loop lw 4 01 load current element of A lw 5 401 load current element of B mult 4 5 multiply corresponding elts mflo of A and B add 3 3 4 add product to running sum addi 1 1 4 update array address bne 1 2 Loop exit when array address B jr 31 return to operating system Part B Create an assembly language function that computes the averages of even and odd numbers in a variable sized array Here the values are placed in an array in static memory using the Word assembler directive The number of values is implied by the address of the next value in static memory at label Next Assume at least one even and one odd value occurs in the list When your program completes the average of all even numbers is returned in 4 and the average of all odd numbers is returned in 5 This program finds the largest smallest and average values for an integer array data Arrayword 243 459 896 535 264 698 268 281 921 886 word 864 215 781 151 435 128 276 336 790 825 word 501 725 835 160 300 095 481 282 515 282 word 662 770 776 998 758 447 758 272 015 398 word 042 645 565 265 105 778 739 148 309 960 word 903 067 469 126 673 864 658 333 170 987 word 565 228 235 477 568 254 628 421 788 012 word 246 170 746 892 586 875 055 850 885 828 word 717 797 971 862 269 082 824 728 650 470 word 740 522 232 648 323 Next word 00 1 array pointer 2 array size 3 input 4 min 44 5 max 6 avg 7 pred ECE 3035 text IN4B Loop Skipl Skip2 mflo jr Compu ring Mechanisms S rudy Guide Solu rions 0 Array 0 Next 2 1 0 0 ArrayO ArrayO Version 10 set memory base load end condition compute size in bytes clear average initialize min initialize max first element offset load next value add to running sum compare input to min skip is gt otherwise update min compare max to input skip if gt otherwise update max adjust array pointer loop until end is reached compute size in words compute average move result return to operating system ECE 3035 Computing Mechanisms Study Guide Solutions Version 10 Problem FCl 2 parts Flow Control Part A Draw the control ow graph corresponding to the following C code fragment Be sure to draw the control ow determined by the compound predicate and the break do C getcFP D fooC if C l 0 ampamp DC lt 100 D C else if C gt 105 D 0 break else D while C l EOF Printistats D DC lt 100 T F PrintStatsD Part B Write a single C statement that corresponds to the following MIPS code Assume 1 holds A 2 holds B 3 holds C and 4 holds D Do not use an z39f then else bne 3 0 Set bne 1 0 Reset beq 2 0 Reset Set addi 4 0 1 j Continue Reset addi 4 0 0 Continue DCIIAampampB ECE 3035 Computing Mechanisms Study Guide Solutions Version 10 Problem FCZ 2 parts Flow Control Part A Draw the control ow graph corresponding to the following C fragment including the ow within the compound predicate for I 100 I gt O I if XI lt NumX ampamp YI lt NumY ll ZI l O ZI 51 else YI 31 X lt NumX F Y lt NumY T F T F Z 5 I X0 Y0 Part B Express the switch statement below as a at compound predicate if thenelse statement that uses only logical Operators 2 l l l Do not use logical AND amp amp switch N case 0 x x y break if N 0 N z 20 case 10 yx y xxl break 39 y case 20 x x y else break y X y default y x y l ECE 3035 Computing Mechanisms Study Guide Solutions Version 10 Problem FC3 3 parts Flow Control Part A Write the C code fragment that corresponds to this control ow graph Use the appropriate looping construct Where possible compress nested ifthenelse constructs into a at if thenelse using compound logical predicates W for J100 J gt 0 J 2 if VJ gt Min ampamp VJ lt Max Flag OK YJ J 10 else XJ 10 J J X0 Y0 Part B Write a single C statement that corresponds to the following MIPS code Assume 1 holds A 2 holds B 3 holds C and 4 holds D Do not use an z39f then else addi 4 0 0 bne 3 0 Set beq 1 0 Continue beq 2 0 Continue Set addi 4 0 1 Continue m DCAampampB Part C 2 Turn this nested ifthenelse statement into a at compound predicate ifthenelse statement which uses only basic operators such as and l and logical amp amp and H operators if P if Q A else if R if S A else B else B else B if P ampamp Q R ampamp S A else B ECE 3035 Computing Mechanisms S rudy Guide Solutions Version 10 Problem FC4 3 parts Flow Control Part A Turn this doubly nested if statement into a single ifthenelse statement using a compound predicate notxlt3 if ylOO Z 50 else Z 20 else Z 20 if xlt3 y100 z 20 else 2 50 Part B Write a single C statement that corresponds to the following MIPS code Assume 1 holds A 2 holds B and 3 holds C Do not use an ifthenelse beq 1 0 False beq 2 0 False addi 3 0 1 False addi 3 0 0 Continue m C A ampamp B Part C Draw a control ow graph for the following C fragment Assume blocks A B C and D contain several C statements Use proper control flow graph notation if x Y block A if N M if J K ECE 3035 Computing Mechanisms S rudy Guide Solutions Version 10 Problem STl 3 parts Pointers and Arrays The following static variables are allocated in memory beginning at address 5000 int AU 7 5 9 97 1 int C25D17PA double H 314 double J ampH int K int 9 ampAll Part A Determine the numerical values for the following expressions A5 25 P1 98 Q1 97 A3 36 J 5032 ampK 5044 Part B Can the following statement be implemented given the declaration of A above Explain why or why not A A 1 No because A is a constant base address Part C 2 Write the MIPS code implementation of the dynamically allocated array access below in the smallest number of instructions A pointer to the array declared below is stored in 3 Variables A B and C reside in 4 5 and 6 respectively Modify only 1 and 2 and the indexed memory location int Array8632 array declaration ArrayABC 81 implement this label instruction comment addi 1 0 192 LxLy mult 4 1 ALxLy mflo 1 sll 2 5 5 BLx add 2 2 1 ALxLy BLx add 2 2 6 ALxLy BLx C sll 2 2 2 byte offset add 2 2 3 base of array addi 1 0 81 value to store sw 1 02 store 81 at ArrayABC ECE 3035 Computing Mechanisms Study Guide Solutions Version 10 Problem STZ 3 parts Pointers and Structures Part A The following variables are allocated in memory beginning at address 5000 Complete the memory map below with the variable names at each word or byte in memory Do not include the variable s value 5000 A gt gt gt 5004 B0 gt gt gt int A int Bu 1 2 5008 3m gt gt gt char C 2 char DH Hello 5012 C Dlol D1 Dlzl M E 5016 DB D4 D5 slack char F 5020 E gt gt gt 5024 F gt gt gt Part B Suppose the following code follows the definitions in Part A List the values of the listed variables following execution of this code EB A E Ell F ampDll CF A 3 C 39e39 D 5013 E 5004 F 5014 Part C Consider the following structure declaration struct State int Num char Name NAMELENGTH int YearPop NUMYEARS float Growth l Suppose S is a pointer to a previously allocated and initialized State object Write proper C statements to perform the following structure accesses Store initial year population in integer P P 5gtYearPop0 Store first character of Name in character C C 5gtName0 Set Growth to percentage 5 gtGrowfh 1000 5 gtYearPop1 5 gtYearPop0 growth between years 0 and l 5 gtYearPop0 ECE 3035 Computing Mechanisms Study Guide Solutions Version 10 Problem FP1 6 parts Edge Detection Functions Suppose 3 contains the base address of a 32x32 pixel subarray within an image Each pixel is a packed RGB value contained in the lower 24 bits of a 32bit word Suppose 1 contains the address ofa pixel in the 32x32 subarray Part A Write a MIPS code fragment that tests whether the pixel is on the top edge of the subarray and if so branches to the label Target label instruction comment sub 2 1 3 subtract array base slti 2 2 128 is pixel in first row bne 2 0 Target then skip to target Part B Write code that test whether the pixel is on the right boundary of the suba1ray and if so branches to the label Target label instruction comment sub 2 1 3 subtract array base addi 2 2 4 compute next pixel position andi 2 2 127 is next pixel on left edge beq 2 2 Target then skip to target Part C Write a MIPS code fragment that tests whether the pixel is on the bottom edge of the subarray and if so branches to the label Target Label Instruction Comment sub 2 1 3 subtract array base slti 2 2 3968 is pixel in last row 4096128 beq 2 0 Target then skip to target Part D Write code that test whether the pixel is on the left boundary of the subarray and if so branches to the label Target Label Instruction Comment sub 2 1 3 subtract array base andi 22127 is pixel on left edge beq 2 0 Target then skip to target ECE 3035 Compu ring Mechanisms S rudy Guide Solu rions Version 10 Part E Suppose 8 holds variable x and 11 holds variable y What is the mathematical expression computed by the following code fragment eg y 2 y slt 5 8 11 beq 5 0 Next add 8 11 0 Next Answer y minx y Par r F Registers 13 14 and 15 each contain a color pixel value R G B respectively in their lowest 8 bits with 0 s in their upper 24 bits Write code to pack them into an RGB color pixel representation in the lower 24 bits of a word and store it in an output image array whose base address is labeled Edges at the pixel offset stored in 2 Modify only 2 13 14 15 label instruction comment sll 13 13 8 shif r red lef r one by re ori 13 13 14 combine red and green sll 13 13 8 shif r red ampgreen lef r one byfe ori 13 13 15 add blue To red amp green sw 13 Edges2 sfore packed word in To memory ECE 3035 Computing Mechanisms Study Guide Solutions Version 10 Problem FP2 1 part Parameter Passing amp Activation Frames Part A The following C function includes a call by value parameter and two call by reference parameters Implement both the caller and called function in MIPS assembly Use proper procedure linkage conventions This program tests different parameter passing conventions include ltstdiohgt X Bi int Y 55 int Z 44 int P int ConditionaliEXchangeunt int int P O ConditionaliExchangewx ampY P P r39 ConditionaliExchangewY ampZ P printfquotX d Y d Z dnquot X Y Z int ConditionaliEXchangeunt A int B int C i T l This program tests different parameter passing conventions text FP2 add 30 29 00 set caller39s FP addi 29 29 16 create storage for locals X Y Z P addi 01 00 33 load value 33 sw 01 430 initialize x 33 addi 01 00 55 load value 55 sw 01 830 initialize Y 55 addi 01 00 44 load value 44 sw 01 1230 initialize Z 55 set P 0 and prepare to call CXchange here w s 00 1630 P 0 addi 29 29 24 allocate beginning of CXchange39s frame sw 31 2029 push return address sw 30 1629 push current FP main39s FP addi 01 30 4 form ampX sw 01 1229 push input ampX addi 1 30 8 form ampY sw 01 829 push input ampY lw 01 1630 get P sw 01 429 push input P note space for uninit39d return val is at 029 jal CXchange call CXchangeampX ampY P lw 30 1629 restore main39s FP lw 31 2029 restore main39s return addr 14 ECE 3035 add se add sw add jr CXchange add lw beg Compu ring Mechanisms S rudy Guide Solu rions 1 29 29 24 t P 1 01 01 1 29 31 30 1 01 01 1 01 01 01 01 00 1 l630 29 24 2029 l629 30 8 1229 30 12 829 l630 429 CXchange 30 31 29 31 l629 2029 30 00 add 30 29 0 1 29 29 4 01 01 01 02 02 03 02 01 02 01 03 01 430 00 End 1230 OOl 4 30 830 003 1230 OOl 4 30 830 003 01 01 29 31 430 030 30 0 1 and prepare Version 10 adjust stack pointer to call CXchange again ititititititit 1343 itititl i 1343 itititl i allocate beginning of CXchange39s frame push return address push current FP main39s FP form ampY push input ampY form ampZ get P push input P call CXchangeampY ampZ P restore main39s FP restore main39s return addr pop locals from stack return to operating system set base of frame pointer create storage for local Temp load input C if not C branch to End look up address passed as dereference A Temp A look up address passed as dereference B look up address passed as A load local Temp look up address passed as B Temp first input second input lst input 2nd input load input C write the return value C pop CXchange39s activation frame return to caller ECE 3035 Computing Mechanisms S rudy Guide Solutions Problem PCl 1 par r Part A The function Bar below left calls function Foo after completing code block 1 Write MIPS assembly code that properly calls Foo Include all instructions between code block 1 and code block 2 Symbolically label all required stack entries and give their values if they Version 10 Activation Frames are known below right Bar s Fl 9900 XXX XXX 9896 W2 1 t B U 9892 Vl 4 m M 9888 VO 9 int V 9 4 1 SP 9884 R 1 int R V2 9880 RA NA code block 1 9876 EB 9900 9872 R 1 R FOOR ampR V 9868 ampR 9884 code block 2 9864 V 9888 9860 RV NA 9856 label instruction comment addi 29 29 24 allocate activation frame sw 31 2029 preserve RA sw 30 1629 preserve FP lw 1 1630 copy R s value sw 1 1229 store in activation frame addi 1 30 16 compute R s effective address sw 1 829 store in activation frame addi 1 30 12 computer V s base address sw 1 429 store in activation frame jal Foo call Foo lw 31 2029 restore RA lw 30 1629 restore FP lw 1 029 load return value sw 1 1630 store in R addi 29 29 24 deallocate activation frame ECE 3035 Part B Assume the code above calls a function int Foo int A properly completes and references its activation frame Write short code fragments for Foo that perform the access of the specified function parameters below Assume Foo s frame pointer is Computing Mechanisms Study Guide Solutions B C that properly set and no parameters are present in registers ie access all parameters from Foo s activation frame 5 B dereference B and store the value in 5 I 1w 5 830 l get pointer B 1w 5 0 5 I dereference B C 2 6 stores the contents of register 6 into C2 l 1w 1 430 l load base of array C I I sw 6 81 I store 6 at C2 A decrements A 1w 1 1230 load A addi 1 1 1 decrement A sw 1 1230 store A return A returns A as the return value 1w 1 1230 load A sw 1 030 store in RV slot add 29 30 0 deallocate activation frame jr 31 return to caller Version 10 ECE 3035 Problem PCZ 2 parts int Bar int A 21 B 33 char C Hil int Fooint char code block 1 B FooampA C code block 2 Computing Mechanisms Study Guide Solutions Version 10 Activation Frames Part A The function Bar below left calls function Foo after completing code block 1 Write MIPS assembly code that properly calls Foo You should include all instructions between code block 1 and code block 2 List the symbolic names and values for each stack entry below right Bar is called by a j a1 instruction at address 2000 Foo returns 55 Bar s PP 9900 Bar s RV 9896 A 21 9892 B 33 9888 C Hil 98 8 4 Bar39s RA 2004 9880 Bars FP99OO 9876 ampA9896 9872 C 9888 SP Foo39s FPgt 9868 Foo39s RV 55 label instruction comment addi 29 29 20 allocate stack space for Foo call sw 311629 preserve Bar39s return address sw 301229 preserve Bar39s frame pointer addi 2 30 4 compute address of A jal Foo sw 2 829 store ampA addi 2 30 12 compute address of C sw 2 429 store C call Foo w 311629 restore Bar39s return address w 301229 restore Bar39s frame pointer w 2 029 load Foo39s return value sw 2 s30 store in B addi292920 deallocate stack space for Foo call Part B Explain why an activation frame cannot be fully allocated by a called function An activation frame must be partially created by the caller so it can initialize input parameters to the called function and access the returned value ECE 3035 Computing Mechanisms S rudy Guide Solutions Version Problem 551 2 par rs C Programming and Make fi Part A The C program below should count the frequency of letters in a text le and print a letter usage histogram Fill in the body of the dowhile loop to complete the program Keep track of the number of letters encountered in NumLetters and keep a frequency count of each the 26 letters in the LetterCount array Only count characters that are one of the 26 letters in either lowercase or uppercase of the alphabet void LetterHistogramFILE FP int Char I NumLetters 0 int LetterCount 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 OI OI OI 0 int getcFILE do Char getcFP NumLetters 1 if Char gt a ampamp Char lt 2 LetterCountChar a 1 else if Char gt A ampamp Char lt Z LetterCountChar A J 1 else NumLetters 1 While Char EOF printfquotLetter Occurrence Histogramnquot for I 0 I lt 26 I printfquotc 5d 4lfnquot I 39A39 LetterCountI 1000 LetterCountI NumLetters Part B Answer the following questions about the makeflle fragments above What is the name of the linker used in this makeflle gcc 10 les of What type off11es are produced by the line that begins c o object files What does bright depend on P1 4ojpegdecoderojpegencodeno What does refer to in the line that links the program bright ECE 3035 Computing Mechanisms Study Guide Solutions Version 10 Problem DT1 3 parts Dynamic Typing and Interpretation Part A Consider the following program fragment Line number Instruction 10 int x 11 float y 314 12 x 5 13zyyx 14 x abc 15 x xy If the programming language is statically typed such as C at which line of code would a type error first occur Assume the language has Clike coercion rules Line number If the programming language is dynamically typed at which line of code would a type error first occur Assume the language has Clike coercion rules Line number 15 Part B Compare static versus dynamic typing in terms of l runtime performance static typing is faster at runtime less runtime overhead 2 compilation time dynamic typing has shorter compile time no type checking Part C Suppose the following object is allocated on the heap using mal loc Assume the heap pointer is 5000 and there is no free list Show where A B C and D are placed in memory Record the object size ie write the actual size value where it belongs and show the heap pointer following the allocation struct Thing int AZl char B7 char C double D l 419 5000 size size size size 28 5004 A0 A0 A0 A0 5008 A1 A1 A1 A1 5012 B0 B1 B2 B3 5016 B4 B5 B6 slack 5020 C C C C 5024 D D D D 5028 D D D D HP 5032 ECE 3035 Computing Mechanisms Study Guide Solutions Version 10 Problem DTZ 3 parts Dynamic Typing and Interpretation Part A Name two extra tasks required to support the call of a function pointer that are not part a normal function call implemented using the j a1 instruction 1 The return address must be computed and saved 2 The Jump target must be loaded into a register Part B List two bene ts of dynamic weak typing 1 Dynamic typing does not require type declarations in source code 2 Dynamic typing support automatic garbage collection Part C Suppose the following object is allocated on the heap using mal loc Assume the heap pointer is 5000 and there is no free list Show where A B C and D are placed in memory Record the object size ie write the actual size value where it belongs and show the heap pointer following the allocation struct Thing int A int 3 char CllOl double D 419 5000 size size size size 28 5004 A A A A 5008 B B B B 5012 CO C1 CZ C3 5016 C4 C5 C6 cm 5020 Cs C9 slack slack 5024 D D D D 5028 D D D D HP 5032 ECE 3035 Compu ring Mechanisms S rudy Guide Solu rions Version 10 Problem HM1 2 par rs Hash Tables Part A Heap Pointer 5016 5028 5040 5052 5066 Free List 0000 5028 5052 5028 Buckets 5000 5028 5040 5004 5008 5016 5012 5052 5036 5062 5086 5110 Part B lHeap Pointer 50165028504050525066 Free List 0000501650525016 Buckets 5000 5004 50165028 5008 5052 5012 5040 222 5056 444 666 5082 ECE 3035 Computing Mechanisms Study Guide Solutions Ver swn 10 Problem HMZ 2 parts Hash Table Implementation Void InsertHashTable HT int Key int Value define INITN UMBUCKETS 5 Link FoundLink define LINKBLOCKSIZE 16 define RESIZERATIO l FoundLink FindiKeyHT Key define NOMATCH 1 if FoundLink 1 NULL define DEBUG O FoundLinkegtValue Value else typedef Struct Link lf HTgtFreeLinkS NULL Key HTegtFreeLinkS MakeiNewiLinksL int Value FoundLink HTegtFreeLinkS struct Link Next HTegtFreeLinks HTegtFreeLinksegtNextF Link FoundLinkegtKey Key FoundLinkegtValue Value typedef Struct FoundLinkegtNext HTegtBucketsHashHT KeyL Buckets HTegtBucketsHashHT Keyl FOundLink int NumBuckets HTegtSize 1 Link FreeLinks if HTgtSize gt HTegtNumBuckets RESIZERATIO Size int HashTable ResizeiHashiTable HT l l Part A Complete the C function FindiKey that searches the hash table for an entry corresponding to a specified key It should return a pointer to the matching Link entry if the key is found or return NULL if the key is not found in the hash table Link FindiKeyHashTable HT int Key Link ThisLink int Index int HashHashTable HT int Key Index HashHT Key ThisLink HT gtBucketsIndex while ThisLink NULL ampamp ThisLink gtKey Key ThisLink ThisLink gtNext return ThisLink Part B The following questions are related to the hash table implementation listed above When Ins ert is called more than once with the same key what occurs Where is a new entry link placed on the bucket list What is the range of possible values for average bucket list length Describe the type of Bucket s in HashTabl e in 10 words or less What is the size in bytes of HashTable What is the size in bytes of the initial Buckets array value replacement If is pushed on ro The front of The list 0 1 an array of pointers To link structures 4 x 4 16 bytes 5x4 20 bytes ECE 3035 CompuTing Mechanisms STudy Guide SoluTions Version 10 Problem HM3 4 parTs Heap Manager Implementation Consider the following fragment from a HeapManager implementation Note that 2 is the freed object pointer and 3 is the free list beq 3 0 Labell 101 add 6 3 0 102 1w 4 42 103 1w 5 43 104 slt 5 5 4 105 bne 5 0 Labe13 106 Labell sw 3 02 107 ParT A Using abstract terms de ne what is being compared in 105s1t Don39t simply transliterate the MIPS instructions e g don t say reg 2 is added to reg 3 The size of The objecT being freed is compared To The size of The firsT objecT on The free isT ParT B Describe the two cases where 107 sw is executed in terms de ned in the project speci cation Be speci c 1 If The objecT being freed is less Than or equal To The firsT free isT objecT 2 If The free isT in empTy ParT C 2 Consider the three pointers below Assume their initialized value is the address of an appropriate address in memory For each statement below list the resultant value If the value is undecidable list error char Heap 5000 mem5000 5500 void Object 6000 mem6000 6500 void Free 7000 mem7000 7500 Heap 1 l Object 1 l Free 1 l int Free 1 l l 5001 l error i 7004 l 7504 l ParT D Concisely de ne the following terms void pointer A poinTer To an objecT of unknown Type null pointer A poinTer conTaining The quotempTyquot value nu O ECE 3035 Computing Mechanisms Study Guide Solutions Version 10 Problem HM4 3 parts Heap Management Below is a snapshot of heap storage The heap has been allocated contiguously beginning at address 6000 with no gaps between objects using a heap manager implemented in C Below is a portion of the heap manager Char HEAPSIZE char V0 d FreePtr V0 d Free Ob Ob LastPtr 7 ampFreePtr 1 tOb l NULL ampamp e LastPtr V0 d Ob ectPtr LastPtr ectPtr Assume Heathr 6168 and FreePtr 6092 and FreePtr is locatedataddress 5064 Par l39 A Circle all object size words in the snapshot above Par l39 B List the base addresses of the heap objects that are on the free list in the order 6092 6024 6120 6100 they appear on the free list Par l C Suppose the following function call is made Free p where p61 32 Given the snapshot of heap above what is the value of the following at each of the indicated locations in the code ThisPtr LastPtr ObjectPtr at L9 6092 5064 6036 at L47 6100 6120 6100 ECE 3035 Computing Mechanisms Study Guide Solutions Version 10 Problem HM5 5 ports Garbage Collection Below is a snapshot of heap storage Values that are pointers are denoted with a The heap pointer is 6168 The heap has been allocated contiguously beginning at 6000 with no gaps Part A Suppose the stack holds a local variable whose value is the memory address 6052 and register 3 holds the address 6148 No other registers or static variables currently hold heap memory addresses List the addresses of all objects in the heap that are not garbage Addresses of Non Garbage Objects 6052 6100 6148 6036 6004 6072 6080 Part B Create a free list by scanning the memory for garbage starting at address 6000 and pushing each reclaimed object on the front of the free list List the addresses of the objects in order on the free list at the end of the scan Free List 6132 6120 6092 6024 Part C Based on the free list created in part B if an object of size 13 bytes is allocated what address will be returned using a best t allocation strategy Address 6172 Part D Based on the free list created in part B if an object of size 9 bytes is allocated what address will be returned using a best t allocation strategy Address 6132 Part E If the local variable whose value is the address 6052 is popped from the stack which addresses will be reclaimed by each of the following strategies If none write none You do not have to list addresses already on the free list from part B Reference Counting 6052 Mark and Sweep 6052 6100 6004 6072 6080 Old New Space copying 6052 6100 6004 6072 6080 ECE 3035 Computing Mechanisms Study Guide Solutions Version 10 Problem PM1 5 parts Multitasking Part A Explain the difference between nonpreemptive and preemptive multitasking In nonpreemptive multitasking tasks give up control voluntarily when it ends is stalled or reaches a predefined suspend In preemptive multitasking a task is interrupted asynchronously by a hardware timer when an OSdefined execution period has expired Part B Explain the most common method to implement task priorities in a preemptive multitasking environment For example suppose Task A has twice the priority of Task B Using a fixed length time slot increasing priority equates to assigning a larger number of slots Low priority tasks receive few slots This allows all tasks to regularly execute but still implements a priority scheme Part C Explain three differences between the implementation of interrupt handling and multitasking 1 interrupt handlers use memory stack from current task 2 multitasking employs a clock to divide processor time 3 multitasking swaps task39s IP register file VM xlate table Part D List three bene ts of virtual memory in a preemptive multitasking operating system like Unix 1 pages in physical memory do not have to be moved during task swap 2 tasks all see large uniform memory space 3 only translation table is stored in task object along with IP and reg file Part E Consider a multitasking system with four tasks TA TB Tc and TD TA and TB execute at equal priority Tc gets twice as much processor time as TA while TD gets a third of the processor time of TA What percentage of the processor time does TD receive Ignore external factors page faults interrupts waits for IO etc Show work TATBX Tc2X TDX3 X3 X X 2X X3 113 77 ECE 3035 Computing Mechanisms Study Guide Solutions Version 10 Problem PMZ 4 parts Multitasking Part A 2 List three things that must be maintained in a task object for a multitask OS 1 IP of next instruction to be executed when task is resumed 2 The values of all registers in the register file 3 translation table for virtual address space but not the pages Part B Why can t we implement a timeslicing preemptive multitasking OS without hardware support Explain Time slicing requires the executed task to be interrupted when its allocated time is exhausted An external timer lock is required to interrupt the task Part C Explain what happens in a multitasking operating system when too little physical memory is available Why is performance affected so signi cantly Be speci c When physical memory devoted to frames is inadequate each task begins pushing other tasks39 pages out of physical memory As tasks are scheduled in the core they request missing pages and suspend Lengthy disk access latencies mean little useful work is accomplished on any task This phenomenon is called thrashby Part D Suppose three tasks executing in a preemptive multitasking operating system have the following priorities on a scale of 1 lowest 7 4 highest Task A 2 Task B 4 Task C 1 Show an appropriate execution schedule by shading the boxes when each task is executing in the map below Draw at least two cycles of your schedule Task C l l l I l Task B I a l 9l10l11121314l15l161718 Task A I Problem PM3 2 parts Multicore Part A What is the anticipated speedup of a typical application running on a dual core processor versus an otherwise identical single core processor Explain Unless the processor is heavily loaded with multiple applications the expected speedup on a dual core processor is negligible Only explicitly multithreaded applications will realize an improvement in execution time on an otherwise lightly loaded multicore processor
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'