Andrew login ID Full Name CS 15 213 Fall 2002 Exam 2 November 12 2002 Instructions Make sure that your exam is not missing any sheets then write your full name and Andrew login ID on the front Write your answers in the space provided below the problem If you make a mess clearly indicate your final answer The exam has a maximum score of 66 points The problems are of varying difficulty The point value of each problem is indicated Pile up the easy points quickly and then come back to the harder problems This exam is OPEN BOOK You may use any books or notes you like You may use a calculator but no laptops or other wireless devices Good luck 1 09 2 08 3 08 4 12 5 10 6 10 7 09 TOTAL 66 Page 1 of 12 Problem 1 9 points This problem tests your understanding of code optimization Consider the following function for computing the product of an array of integers We have unrolled the loop by a factor of 4 int aprod int a int n int i w x y z r 1 for i 0 i n 3 i 4 w a i x a i 1 y a i 2 z a i 3 r r w x y z Product computation for i n i r a i return r For the line labeled Product computation we can use parentheses to create 3 different associations of the computation as follows r r w x y z r r w x y z r r w x y z A1 A2 A3 Complete the following table with the theoretical CPE cycles per element of each of these associations Assume that this machine has an infinite number of integer multipliers all capable of operating in parallel with each other Also assume that integer multiplication on this machine has a latency of 4 cycles and an issue time of 1 cycle Version Theoretical CPE A1 A2 A3 Here are some hints Recall that the CPE measure assumes that the run time measured in clock cycles for an array of length is a function of the form where is the CPE Theoretical CPE means the performance that would be achieved if the only limiting factors were the data dependences of computation and the latency and issue time of the integer multiplier Page 2 of 12 Problem 2 8 points The following problem concerns basic cache lookups The memory is byte addressable Memory accesses are to 1 byte words not 4 byte words Physical addresses are 14 bits wide The cache is 4 way set associative with a 4 byte block size and 64 total lines In the following tables all numbers are given in hexadecimal The Index column contains the set index for each set of 4 lines The Tag columns contain the tag value for each line The V column contains the valid bit for each line The Bytes 0 3 columns contain the data for each line numbered left to right starting with byte 0 on the left The contents of the cache are as follows Index 0 1 2 3 4 5 6 7 8 9 A B C D E F Tag 0C 3A 26 B8 54 F6 BE A0 F0 30 38 3A D4 DC D6 7E V 0 1 0 1 1 0 0 0 1 1 1 1 0 1 0 1 Bytes 0 3 03 3E CD 38 A9 76 2B EE 75 F7 3F C6 E0 22 19 3A 86 B8 F0 C6 04 2A 32 6A 2F 7E 3D A8 D6 A4 89 92 ED 32 0A A2 1E C2 AE 60 5D 4D F7 DA 61 C6 5E 74 17 52 75 2C 54 9E 1E FA 14 9A 0D 4A 32 21 1C 2C Tag A0 54 78 D2 4C 9E C0 10 E4 08 82 64 AE B6 EA FA V 0 0 1 0 1 0 0 0 1 0 1 0 0 1 1 1 4 way Set Associative Cache Bytes 0 3 Tag V 16 7B ED 5A 40 0 BC 91 D5 92 98 1 9E 3A 0F DA 26 1 02 B3 8F B6 D4 1 AA 29 AE 16 56 1 B1 86 56 0E CC 0 27 95 A4 74 C4 1 FD FE D6 DA 76 0 BF 80 1D FC 14 1 5C 3E DF F2 CA 0 69 C2 8C 74 9C 1 03 97 BA 62 80 1 62 89 EF 18 8E 0 DC 81 B2 14 00 0 C8 1D E6 6E 38 1 22 C2 DC 34 BE 1 8E 80 00 25 76 96 07 DE EF 25 A8 F8 BB B6 F3 BA Bytes 0 3 4C DF 18 BA 9B F6 4C B6 A8 31 E1 02 46 80 6E 30 47 F2 11 6B D8 D5 CD 4A 09 86 2A CF 84 DA CE 7F DA 11 72 12 7D 8C 7C 1F 7B 44 38 F3 5C DD 37 D8 Tag 58 84 5E C2 1C 06 8A E2 BC 5C 3E E0 68 74 64 B8 V 0 1 1 0 1 1 1 0 1 1 1 1 0 0 0 0 FB 48 92 18 13 F8 C7 7C 25 F1 FA C5 26 10 6C E7 Bytes 0 3 B7 12 02 16 81 0A 04 E5 2E 09 73 02 EA A8 66 1D 42 30 B7 AF C2 68 3A 1A 44 6F 1A 6B DC DE 93 EB 48 EC 76 4E 57 7F C2 F5 B8 2E 8F BD A8 A2 39 BA Part 1 The box below shows the format of a physical address Indicate by labeling the diagram the fields that would be used to determine the following CO CI CT 13 The block offset within the cache line The cache index The cache tag 12 11 10 9 8 7 6 5 4 3 2 Page 3 of 12 1 0 Part 2 For the given physical address indicate the cache entry accessed and the cache byte value returned in hex Indicate whether a cache miss occurs If there is a cache miss enter for Cache Byte returned Physical address 2BB2 A Physical address format one bit per box 13 12 11 10 9 8 7 6 5 4 3 2 1 0 5 4 3 2 1 0 B Physical memory reference Parameter Cache Offset CO Cache Index CI Cache Tag CT Cache Hit Y N Cache Byte returned Value 0x 0x 0x 0x Physical address 098B A Physical address format one bit per box 13 12 11 10 9 8 7 6 B Physical memory reference Parameter Cache Offset CO Cache Index CI Cache Tag CT Cache Hit Y N Cache Byte returned Value 0x 0x 0x 0x Page 4 of 12 Problem 3 8 points This problem tests your understanding of cache conflict misses Consider the following matrix transpose routine typedef int array 2 2 void transpose array dst array src int i j for j 0 j 2 j for i 0 i 2 …
View Full Document
Unlocking...