computer of 32 bits with a data cache memory of 32 KB has lines of 64 bytes. The

Question

computer of 32 bits with a data cache memory of 32 KB has lines of 64 bytes. The cache is 2-way associative. Consider the following code fragment: int m[512][512]; sum = 0; for (i = 0; i < 512; i ++) for (j = 0; j < 512; j++) sum = sum + m[i][j]; int m[512][512]; sum = 0; for (i = 0; i < 512; i ++) for (j = 0; j < 512; j++) sum = sum + m[j][i]; Assuming that the sum variable is stored in a register, calculate the hit ratio that produce this code fragment. (the matrix is stored by rows). computer of 32 bits with a data cache memory of 32 KB has lines of 64 bytes. The cache is 2-way associative. Consider the following code fragment: int m[512][512]; sum = 0; for (i = 0; i < 512; i ++) for (j = 0; j < 512; j++) sum = sum + m[i][j]; int m[512][512]; sum = 0; for (i = 0; i < 512; i ++) for (j = 0; j < 512; j++) sum = sum + m[j][i]; Assuming that the sum variable is stored in a register, calculate the hit ratio that produce this code fragment. (the matrix is stored by rows). computer of 32 bits with a data cache memory of 32 KB has lines of 64 bytes. The cache is 2-way associative. Consider the following code fragment: int m[512][512]; sum = 0; for (i = 0; i < 512; i ++) for (j = 0; j < 512; j++) sum = sum + m[i][j]; int m[512][512]; sum = 0; for (i = 0; i < 512; i ++) for (j = 0; j < 512; j++) sum = sum + m[j][i]; Assuming that the sum variable is stored in a register, calculate the hit ratio that produce this code fragment. (the matrix is stored by rows).

Explanation / Answer

Cache size=32 KB

Block size=64B.

Number of blocks in cache=32KB/64B=32*210/64=29=512 blocks

Assume int size is 4B, so array m[512][512] size=29*29*4=220 B i.e. 220/64=214 blocks

one block contains 64B/4B=16 elements

Now Consider the code segment:

int m[512][512];

sum = 0;

for (i = 0; i < 512; i ++)

for (j = 0; j < 512; j++) sum = sum + m[i][j];

Here our matrix m is row major(stored by rows) and we read those row by row,

So for one element we read a block(16 elements) i.e. for 1 Miss next 15 elements are Hit.

Thus Hit ratio= (220-214)/218=0.93

Now consider the code segment:

int m[512][512];

sum = 0;

for (i = 0; i < 512; i ++)

for (j = 0; j < 512; j++)

sum = sum + m[j][i];

Here our matrix is row major and we are reading column wise,

As our cache is 2 way set associatative and it has 512 blocks, so there are 512/2=256 sets

0,256,512 blocks are mapped to set 0, 1,257,513 are mapped to set 1.

Here each row has 512 elements i.e. 512/4=128 blocks.

As we read column wise we read in following order, 0,128,256,512, ...

So, we read m[0][0] and load block 0 to set 0, then m[1][0] and load block 128 to set 1,

then m[2][0] to set 0. Now set 0 is full, then we read m[2][0] and load block 384 to set 1,

Now set 1 is full, then read m[3][0] and load block 512 to set 0 and replace block 0 from cache.

So, as block 0 is replaced to read other elements in block 0 we have to bring block 0

again to cache, Thus for each element we have one block read.

So, Hit ratio=0

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.