Homework #4: Introduction to Computer Systems - 18x13: Summer 2024

Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

Homework #4: Introduction to Computer Systems - 18x13: Summer 2024

Question 1                          1 / 1 pts

Given the following pseudocode (assume that all memory accesses are valid)

int N = 20

for(int j = 0; j < N; j ++){

      for(int i = 0; i < N; i ++){

             A[i ] += B[j ]

       }

}

Considering only the inner loop, which variables exemplify the principle of temporal locality?

Question 2                     14 / 14 pts

This problem requires you to analyze the cache behavior of a function that sums the elements of an

array A:

int A[2 ][4 ];

int sum() {

int i, j, sum=0;

for (j=0; j<4; j++) {

  for (i=0; i<2; i++) {

    sum += A[i ][j ];

  }

}

return sum;

}

Assume the following:

• The memory system consists of registers, a single L1 cache, and main memory.

• The cache is cold when the function is called and the array has been initialized elsewhere.

• Variables i, j, and sum are all stored in registers.

• The array A is aligned in memory such that the first two array elements map to the same cache block.

• sizeof(int) == 4.

• The cache is direct mapped, with a block size of 8 bytes.

A. Suppose that the cache consists of 2 sets. Fill out the table to indicate if the corresponding memory access in A will be a hit (h) or a miss (m):

A                       Col 0                   Col 1                 Col 2                 Col 3

Row 0                  m                       m                       m                     m

Row 1                  m                       m                       m                     m

B. What is the pattern of hits and misses if the cache consists of 4 sets instead of 2 sets?

A                      Col 0                     Col 1                 Col 2                Col 3

Row 0                 m                          h                      m                     h

Row 1                 m                          h                      m                     h

Question 3                 10 / 10 pts

This problem tests your understanding of the the cache organization and performance. Assume the following:

sizeof(int) = 4

Array x begins at memory address 0.

The cache is initially empty.

The only memory accesses are to the entries of the array x. All variables are stored in registers.

Consider the following C code:

int x[128 ];

int i, j;

int sum = 0;

for (i = 0; i < 64; i ++){

  j = i + 64;

  sum += x[i ] * x[j ];

}

Case 1

1. Assume your cache is a 256-byte direct-mapped data cache with 8-byte cache blocks. What is the cache

miss rate? (2 pts)

miss rate = [ Select ] %

2. If the cache were twice as big, which of the following is closest to the miss rate?

miss rate = 50 %

Case 2

1. Assume your cache is 256-byte 2-way set associative using an LRU replacement policy with 8-byte cache

blocks. Which of the following is closest to the miss rate? (1 pts)

miss rate = [ Select ] %

2. Will larger cache size help to reduce the miss rate? (Yes / No) [ Select ]

3. Will larger cache block help to reduce the miss rate? [ Select ]