CSCI 2122 - Systems Programming - A5

• 作业标题：CSCI 2122 - Systems Programming - A5
• 课程名称：Dalhouse University CSCI 2122 Systems Programming
• 完成周期：3天

1. Description

(1) [4+2 +4+2+2] You are given the following code to analyze:

1. int x[2][128];
2. int i, sum = 0;
3. for (i = 0; i < 128; i++)
4. sum += x[0][i] * x[1][i];

Assume the code is executed under the following conditions:

• sizeof(int) = 4
• Array x begins at mem. addr. 0x0 and is stored in row-major order.
• Cache initially empty
• Only mem. accesses are to elements of x. Rest of the variables are in registers.

(a) Case 1: Assume cache is 512 bytes, direct-mapped, with 16 byte blocks. What
is the miss rate? Explain.

(b) Case 2: What is the miss rate if the cache size is doubled (becomes 1024 bytes).
Explain.

(c) Case 3: If the cache were to be a 512 byte, two-way set-associative cache using
an LRU replacement policy, with 16 byte cache blocks. What is the cache miss
rate? Explain.

(d) For case 3, will a larger cache size help reduce the miss rate? Why or why
not?

(e) For case 3, will a larger block size help reduce the miss rate? Why or why
not?

(2) 3M decides to make Post-its by printing yellow squares on white pieces of paper. As
part of the printing process, they need to set the CMYK (cyan, magenta, yellow,
black) value for every point in the square. 3M hires you to determine the efficiency of
the following algorithms on a machine with a 2,048-byte direct-mapped data cache
with 32-byte blocks. You are given the following definitions:

1 struct point color f
2 int c;
3 int m;
4 int y;
5 int k;
6 g;
7
8 struct point color square[16][16];
9 int i, j;

Assume the three functions are executed under the following conditions:
• sizeof(int) = 4
• square begins at memory address 0.
• The cache is initially empty.
• The only memory accesses are to the entries of the array square. Variables i
and j are stored in registers.
A. [ 1 + 4 + 1]

1 for (i = 0; i < 16; i++) {
2     for (j = 0; j < 16; j++) {
3         square[i][j].c = 0;
4         square[i][j].m = 0;
5         square[i][j].y = 1;
6         square[i][j].k = 0;
7     }
8 }

(a) What is the total number of writes? Explain.

(b) What is the total number of writes that miss in the cache? Explain.

(c) What is the miss rate? Explain.

。。。