Andrew login ID:Full Name:CS 15-213, Spring 2004Exam 2April 8, 2004Instructions:• Make sure that your exam is not missing any sheets, then write your full name and Andrew login IDon the front.• Write your answers in the space provided below the problem. If you make a mess, clearly indicateyour final answer.• The exam has a maximum score of 79 points and a total of 17 pages.• The problems are of varying difficulty. The point value of each problem is indicated. Pile up the easypoints 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 not use a calculator,laptop or other wireless device. Good luck!1 (16):2 (10):3 (8):4 (12):5 (9):6 (10):7 (14):TOTAL (79):Page 1 of 17Problem 1. (16 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 13 bits wide.• The cache is 4-way set associative, with a 4-byte block size and 32 total lines.In the following tables, all numbers are given in hexadecimal. The Index column contains the set indexfor each set of 4 lines. The Tag columns contain the tag value for each line. The V column contains thevalid bit for each line. The Bytes 0–3 columns contain the data for each line, numbered left-to-right startingwith byte 0 on the left.The contents of the cache are as follows:4-way Set Associative CacheIndex Tag V Bytes 0–3 Tag V Bytes 0–3 Tag V Bytes 0–3 Tag V Bytes 0–30 84 1 ED 32 0A A2 9E 0 BF 80 1D FC 10 0 EF 09 86 2A E8 0 25 44 6F 1A1 18 1 03 3E CD 38 E4 0 16 7B ED 5A 02 0 8E 4C DF 18 E4 1 FB B7 12 022 84 0 54 9E 1E FA 84 1 DC 81 B2 14 48 0 B6 1F 7B 44 89 1 10 F5 B8 2E3 92 0 2F 7E 3D A8 9F 0 27 95 A4 74 57 1 07 11 FF D8 93 1 C7 B7 AF C24 84 1 32 21 1C 2C FA 1 22 C2 DC 34 73 0 BA DD 37 D8 28 1 E7 A2 39 BA5 A7 1 A9 76 2B EE 73 0 BC 91 D5 92 28 1 80 BA 9B F6 6B 0 48 16 81 0A6 8B 1 5D 4D F7 DA 29 1 69 C2 8C 74 B5 1 A8 CE 7F DA BF 0 FA 93 EB 487 84 1 04 2A 32 6A 96 0 B1 86 56 0E CC 0 96 30 47 F2 91 1 F8 1D 42 30Part 1The box below shows the format of a physical address. Indicate (by labeling the diagram) the fields thatwould be used to determine the following:O The block offset within the cache lineI The cache indexT The cache tag12 11 10 9 8 7 6 5 4 3 2 1 0Page 2 of 17Part 2For 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: 0x0D74Physical address format (one bit per box)12 11 10 9 8 7 6 5 4 3 2 1 0Physical memory referenceParameter ValueCache Offset (CO) 0xCache Index (CI) 0xCache Tag (CT) 0xCache Hit? (Y/N)Cache Byte returned 0xPhysical address: 0x0AEEPhysical address format (one bit per box)12 11 10 9 8 7 6 5 4 3 2 1 0Physical memory referenceParameter ValueCache Offset (CO) 0xCache Index (CI) 0xCache Tag (CT) 0xCache Hit? (Y/N)Cache Byte returned 0xPage 3 of 17Part 3For the given contents of the cache, list all of the hex physical memory addresses that will hit in Set 7. Tosave space, you should express contiguous addresses as a range. For example, you would write the fouraddresses 0x1314, 0x1315, 0x1316, 0x1317 as 0x1314--0x1317.Answer:The following templates are provided as scratch space:12 11 10 9 8 7 6 5 4 3 2 1 012 11 10 9 8 7 6 5 4 3 2 1 012 11 10 9 8 7 6 5 4 3 2 1 0Part 4For the given contents of the cache, what is the probability (expressed as a percentage) of a cache hit whenthe physical memory address ranges between 0x1080 - 0x109F. Assume that all addresses are equallylikely to be referenced.Probability = %The following templates are provided as scratch space:12 11 10 9 8 7 6 5 4 3 2 1 012 11 10 9 8 7 6 5 4 3 2 1 0Page 4 of 17Problem 2. (10 points):This problem requires you to analyze the behavior of the program below which transposes the N × N int-matrix A.Forthis problem, N = 4. For this problem, you should assume that the loop variables x and y are kept in registers and donot cause memory accesses. Likewise, the temporary variable t which is used to exchange two array elements is alsostored in a register and does not cause any load/store from/to the memory system or the caches.1 #define N 4 /* Array size */2 ...3 int A[N][N] = {0};4 ...5 { int x, y;6 ...7 for (y = 0; y < N; y++) {8 for (x = y + 1; x < N; x++) {9 int t;10 t = A[y][x];11 A[y][x] = A[x][y];12 A[x][y] = t;13 }14 }15 ...16 }You are supposed to analyze how this program will interact with a simple cache. The cache line size is 2*sizeof(int).The cache is cold when the program starts. Further more, the array A is aligned so that the first two elements are storedin the same cache line.You are supposed to fill out the tables below. For each load (ld) and store (st) operation to an element of the array A,you should indicate if this operation misses (M) or hits (H) in the cache. Note that this program does not touch thediagonal array elements.1. The cache is direct mapped and has two (2) lines:ld= st= ld= st= ld= st=ld= st= ld= st= ld= st=ld= st= ld= st= ld= st=ld= st= ld= st= ld= st=2. The cache is 2-way set-associative and has one set. It uses the least recently used (LRU) replacement policy:ld= st= ld= st= ld= st=ld= st= ld= st= ld= st=ld= st= ld= st= ld= st=ld= st= ld= st= ld= st=Page 5 of 17Problem 3. (8 points):Consider the following C programs. (For space reasons, we are not checking error return codes, so assumethat all functions return normally.) Assume that printf is unbuffered and that each call to printfexecutes atomically./* ecf.c */#include <stdio.h>#include <sys/types.h>#include <sys/wait.h>#define MAXLEN 32int main(int argc, char *argv[]){int i, status, limit;char num[MAXLEN+1];pid_t pid;limit = atoi(argv[1]);for(i = 0; i < limit; i++) {if((pid = fork()) == 0) {snprintf(num, MAXLEN, "%d", i+10);execl("./kid", "./kid", num, NULL);}if(i == (limit - 2)) {waitpid(pid, &status, 0);printf("%d\n", status);}}return 0;}-------------------------------------------/* kid.c */#include <stdio.h>int main(int argc, char *argv[]){printf("%d\n", atoi(argv[1]));return 0;}Page 6 of 17Assume that ecf.c is compiled into ecf and kid.c is compiled into kid in the same directory. List all possibleoutputs (note the newlines) of the following command:[user@host directory]$ ./ecf 3Page 7 of 17Problem 4. (12 points):This problem concerns the way virtual addresses …
View Full Document
Unlocking...