49 The four questions require a program with Sets and LinesPerSet as different 5

Question

49   The four questions require a program with Sets and LinesPerSet as different
50   configuration parameters. (Written in C)
51  
52   ** Please submit four separate source files for the four questions:
53   q1.c, q2.c, q3.c, q4.c
54   **
55  
56  
57  
58  
59  
60  
61  
62   Recall that the sets are numbered 0 through N - 1. For example,
63   if N = 4, the sets are identified as Set0, Set1, Set2, and Set3. The same goes for
64   the lines. If there are 2 lines per set, then the lines are identified as Line0 and
65   Line1. For simplicity, hard-code the reference string, the number of sets, and the
66   number of lines per set into the program code. You then submit one version of the
67   program per question (q1.c, etc.). For example, here's a sample program for 4 sets,
68   1 line per set, and the reference string shown:
69  
70   #include <stdio.h>
71  
72   #define Sets (4) /* number of sets in the cache */
73   #define LinesPerSet (1) /* lines per set: each line with one word */
74   #define Empty (-1) /* marks end of reference string */
75  
76   void main() {
77   int reference_string[ ] = {1,2,3,4,1,2,3,4,5,6,7,8,1,Empty);
78   /* ... */
79   }
80  
81   For this example, the output should be equivalent to:
82  
83   Miss for word 1 in Set 1
84   Word at 1 inserted into Set 1 at line 0
85  
86   Miss for word 2 in Set 2
87   Word at 2 inserted into Set 2 at line 0
88  
89   Miss for word 3 in Set 3
90   Word at 3 inserted into Set 3 at line 0
91  
92   Miss for word 4 in Set 0
93   Word at 4 inserted into Set 0 at line 0
94  
95   Hit for word 1 in Set 1 in line 0
96  
97   Hit for word 2 in Set 2 in line 0
98  
99   Hit for word 3 in Set 3 in line 0
100  
101   Hit for word 4 in Set 0 in line 0
102  
103   Miss for word 5 in Set 1
104   Word at 5 inserted into Set 1 in line 0
105  
106   Miss for word 6 in Set 2
107   Word at 6 inserted into Set 2 in line 0
108  
109   Miss for word 7 in Set 3
110   Word at 7 inserted into Set 3 in line 0
111  
112   Miss for word 8 in Set 0
113   Word at 8 inserted into Set 0 in line 0
114  
115   Miss for word 1 in Set 1
116   Word at 1 inserted into Set 1 in line 0
117  
118   The output should begin with "Hit" or "Miss". If there's a Hit, indicate which set
119   and which line holds the desired word. If there's Miss, indicate the set that was
120   searched in vain for the word; indicate the line into which the word is inserted.
121  
122   For the first four questions, the reference string is the same:
123  
124   1,4,8,5,20,17,19,56,9,1,11,17,11,54,1,4,9,56,5,43,18,5,6,9,17,9,56,9
125  
126   A word's cache address is its memory address modulo the number of sets. For
127   example, if there are 16 sets, then
128  
129   1 % 16 = 1 ;; word at 1 goes into set 1
130   4 % 16 = 4 ;; word at 4 goes into set 4
131   ...
132   19 % 16 = 3 ;; word at 19 goes into set 3
133   ...
134  
135   The referenced word goes into the appropriate set, displacing a word already there
136   if necessary. By assumption, each line contains exactly one word. For each question,
137   assume that the cache is empty to begin.
138  
139   The questions specify the number of sets and lines per set.
140  

Question 1:
141 16 sets
142   1 line per set
143   (This cache is thus direct-mapped.)
144  

Question 2:
145 4 sets
146   4 lines per set
147   (This cache is thus 4-way set-associative.)
148  
149   Now suppose a set is full and that a new line needs to come into the set.
150   Which line already in the set should be overwritten? Here is the algorithm:
151  
152   -- Fill a set in line order 0, 1, 2, and 3: first line 0, then line 1,
153   then line 2, then line 3, then line 0 again, and so on.
154  
155   -- Keep track of the line least recently used: in these examples, "used"
156   means "brought into the set." Suppose, for instance, that four lines are
157   brought into an initially empty cache. The set is S. By assumption, the
158   lines come in as line 0, line 1, line 2, and line 3. At this point, line 0
159   in S is the "least recently used." If another line comes into set S, the new
160   line displaces (overwrites) line 0. The next new line in S would displace
161   line 1; and so on.
162  
163   This replacement algorithm is LRU.
164  

Question 3:
165 8 sets
166   2 lines per set
167   (This cache is thus 2-way set-associative.)
168  
169   Use LRU for replacement.
170  

Question 4:
171 4 sets
172   8 lines per set
173   (This cache is thus 8-way set-associative.)
174  
175   Use LRU for replacement.

Explanation / Answer

DO RATE if satisfied. all four queries can be implemented using this source itself. Just change the #defines according to sets and lines.

code with indentation : http://pastebin.com/q4ZmCigp

Comment if doubt.

#include <stdio.h>

//Just change the below for each query.
//This source works for all queries (any N set x M Line cache)

#define Sets (4) /* number of sets in the cache */
#define LinesPerSet (4) /* lines per set: each line with one word */
#define Empty (-1) /* marks end of reference string */

//Declare the Cache
int cache[Sets][LinesPerSet];
int LRU[Sets]; //LRU index storage

void initCache(){
    int i, j;
    for(i=0; i<Sets; i++){
        LRU[i] =0;
        for(j=0; j<LinesPerSet; j++)
            cache[i][j] = Empty;
    }
}
int queryCache(int address){
    int retValue = 0; //return 1 if hit, 0 for miss
    int i;
    int line;

    int wordCacheAddress = address % Sets;
    int pageNo = address / Sets;

    //Search each line in set
    for(i=0; i<LinesPerSet; i++)
        if( cache[wordCacheAddress][i] == pageNo ){
            printf(" Hit for word %d in Set %d in line %d ",
                    address, wordCacheAddress, i);
            return 1;
        }
    printf(" Miss for word %d in Set %d ", address, wordCacheAddress);
    line = LRU[wordCacheAddress]++;
    if( LRU[wordCacheAddress] == LinesPerSet )
        LRU[wordCacheAddress] = 0;
    cache[wordCacheAddress][line] = pageNo;

    printf("Word at %d inserted into Set %d at line %d ",
            address, wordCacheAddress, line);
    return retValue;
}

void main() {
    int reference_string[ ] = { 1,4,8,5,20,     17,19,56,9,1,
                               11,17,11,54,     1,4,9,56,5,43,
                               18,5,6,9,17,     9,56,9, Empty};

    int i=0;

    //Initialize Cache with empty
    initCache();
    while( reference_string[i] != Empty ){
        queryCache( reference_string[i] );
        i++;
    }
}

Related Questions

Navigate

• Browse (All)
• Browse 4
• Subjects

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