code for adaptive weight ranking policy for improving cache performance.here is
ID: 3759973 • Letter: C
Question
code for adaptive weight ranking policy for improving cache performance.here is the algorithm
3 WEIGHT RANKING ALGORITHM In this section we will use the standard replacement policy terminologies. We assume that the size of the blocks is equal and the replacement algorithm is used to manage a memory that holds a finite number of these blocks. A hit will occur when there is a reference to a block in the buffer. When we have a reference to a block not in the buffer, a miss will occur and referenced block must be added to buffer. When buffer is full and a miss occurs, an existing block must be replaced to make room for a new one. For ranking of the referenced blocks, we consider three factors. Let Fi be the frequency index which holds the frequency of each block i in the buffer and Ri be the recency index which shows the clock of last access when buffer has been referenced and N is the total number of access to be made. Then the weighting value of block i can be computed as: Initially all the indices of Ri , Fi ,Wi are set to 0.
1) Whenever a page frame k is referenced, the hardware increments corresponding Fi by 1.When a hit occurs the respective Ri counter will hold the corresponding clock access value. At any instant, the block whose weight index is lowest is the least recently used block, the block with next higher weight index is the next least recently used, and so forth.
2) When a miss occurs i.e. a new object k is placed in the i block then Fi and Ri for the new block will be updated .Because, it means that object k has been placed and once referenced.
In every access to buffer, if referenced block i is in the buffer then a hit is occurred and our policy will work in this way:
1) Fi will be changed to Fi + 1 for every i and Ri will hold the corresponding clock access value.
But if referenced block i is not in the buffer then a miss occurs and our policy will choose the block in buffer, by calculating the weight function i.e. searching for object with smallest weighting value. It will be evaluated as follows:
1) The Wi value has to be evaluated for each block i, for every N Ri.
2) Now the page i with lowest weight index Wi will be replaced with k. Then the corresponding Rk will be the clock value, Fk =1 and Wk will be set to 0.
Explanation / Answer
Pseudo Code of Adaptive weight ranking policy for improving Cache Performance:
1: Upon a Request of Block with an address:Addx
2: Set_id = Findset (Addx){//find out the set of the block}
3: for i ¼ 1 ! Associtivity do
4: if Set_id[i]==Addx then
5: R[Setid][i]+=1{//Increment Rcounter of Block i of
Set_id}
6: E[Setid][i]=0 {//Reset Ecounter to 0 because of reuse}
7: return Hit
8: end if
9: end for
10: //If can not find Addx in Setid, means a miss
11: if CounterMiss[Setid]==4 then
12: //it has been 4 misses since last Ecounter increment
13: for i ¼ 1 ! Associativity do
14: E[Setid][i]+=1{//Increment E-counter of every block in
Setid by 1}
15: end for
16: else
17: CounterMiss[Setid]+=1
18: end if
19: Smallest_Rank = Search (Setid){//Search smallest Rank in Setid}
20: Victim = Random (Smallest_Rank){//Randomly Chose
Victim From all Smallest_Rank}
21: R[Setid][Victim]=0
22: E[Setid][Victim]=0
23: return Victim
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.