Use the same reference string as in question (1). However, this time assume that

Question

Use the same reference string as in question (1). However, this time
assume that there are 4 sets and that C is 4-way set associative: there
are 4 sets, each with 4 blocks. A block still holds 1 word. The set address
is now the reference string number modulus 4. For instance, the first
number in the reference string is 1; hence, the word at address 1 goes into
set 1 % 4 == set 1. Here's a depiction of what a set looks like:

Si +----+----+----+----+
| | | | |
+----+----+----+----+
[0] [1] [2] [3]

Each set is like an array of four elements, with element one of the words.
Now suppose a set is full and that a new element needs to come into the set.
Which element should be overwritten? Here are the rules:

-- Fill the set in left-to-right order, that is, index 0, then 1, then 2, then 3.

-- Keep track of the last entry. Suppose, for instance, that the set has been
full for some time and that the last entry was into [2]. The next entry would
go into [3]. The next after that into [0]; and so on.

Write a program that simulates what happens to the cache with the reference string
from question (1). Here's a start (don't forget #include whatever libs you need):

#define Empty (-1)
#define SetCount (4)
#define WordCount (4)

int sets[SetCount][WordCount];
int main() {
int reference_string[ ] =
{ 1, 4, 8, 5, 20, 17, 19, 56, 9, 11, 4, 43, 5, 6, 9, 17, 9, 56, 9, Empty };
char* set_names[ ] = {"S0", "S1", "S2", "S3"};
...

You're free to work on the above code or create your own solution from scratch.

The program should output a running account of what happens for each address in the
reference string. For example, the output might begin as follows:

Miss for word 1 in Set 1
Word 1 inserted into Set 1 at position 0

Miss for word 4 in Set 0
Word 4 inserted into Set 0 at position 0

Explanation / Answer

#include<conio.h>
#define Empty -1
#define SetCount 4
#define WordCount 4

int sets[SetCount][WordCount];

void main()
{
int n,i;
int reference_string[]={1,4,8,5,20,17,19,56,9,11,4,43,5,6,9,17,9,56,9,Empty};
char *set_names[]={"s0","s1","s2","s3"};
clrscr();

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

  n=reference_string[i]%4;
  switch(n)
   {
   case 0:printf(" miss for word%d in set%c",n,*(set_names[n]));
    printf(" word %d inserted into set %d",reference_string[i],n);
    break;
   case 1:printf(" miss for word %d in set%c",n,*(set_names[n]));
    printf(" word %d inserted into set %d",reference_string[i],n);
    break;
   case 2:printf(" miss for word %d in set%c",n,*(set_names[n]));
    printf(" word %d inserted into set%d",reference_string[i],n);
    break;
   case 3:printf(" miss for word %d in set %c",n,*(set_names[n]));
    printf(" word %d inserted into set%d",reference_string[i],n);
    break;
   }
    }

    getch();

}

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

---

---

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