Basic GRASP policy implementation built on top of LRU

grasp_lru.py

import numpy as np


cache_size=0
cache_empty=True

def refer(addr,hint,dq,dictionary):

    print('Want to access addr: ',addr,' with hint: ',hint)

    

    if(addr==-1):
      print("Invalid access")
      return

    pos=0
    found=False

    if not(addr in dictionary): #Block is not present in the cache
        if(dq.size==cache_size):
            #Eviction
            last=dq[dq.size-1]
            dq=dq[:-1]
            del dictionary[last]

    else:
        # block is present in cache
        found=True
        pos=dictionary[addr]
        dq=np.delete(dq,pos)
        print('pos: ',pos)
        
        del dictionary[addr]

        for key in dictionary:
            if dictionary[key]>pos:
                dictionary[key]=dictionary[key]-1

        print("If block is found")

        print("dq: ",dq)
        print("dict: ",dictionary)
    
    # insertion

    if(hint==0):    #High re-use insertion and hit-promotion
        dq=np.insert(dq,0,addr)
        for key in dictionary:
            dictionary[key]=dictionary[key]+1
        
        if not(addr in dictionary):
            dictionary[addr]=0

    elif (hint==1):
        if not(found): # Medium re-use insertion 
            prev_key=dq[dq.size-1]
            dq=np.insert(dq,dq.size-1,addr)
            dictionary[addr]=dq.size-2
            dictionary[prev_key]=dq.size-1
        else:   # Medium re-use hit promotion
            prev_key=dq[pos-1]
            dq=np.insert(dq,pos-1,addr)
            dictionary[addr]=pos-1
            dictionary[prev_key]=pos

            for key in dictionary:
                if (key!= prev_key and dictionary[key]>=pos):
                    dictionary[key]=dictionary[key]+1
        
    else:
        if not(found):# Low re-use insertion 
            dq=np.append(dq,addr)
            dictionary[addr]=dq.size-1
        else:   # Low re-use hit promotion
            prev_key=dq[pos-1]
            dq=np.insert(dq,pos-1,addr)
            dictionary[addr]=pos-1
            dictionary[prev_key]=pos

            for key in dictionary:
                if (key!= prev_key and dictionary[key]>=pos):
                    dictionary[key]=dictionary[key]+1

    print("dq: ",dq)
    print("dict: ",dictionary)

    return dq, dictionary



if __name__ == "__main__":

    cache_size=4        # no of entries in a cache
  

    addr_hint_list=[[1,0], [2,0], [3,2], [1,0], [4,0], [5,2], [6,1], [6,1], [6,1], [3,2], [3,2],[5,2],[3,2]] #2d-list with 0th element=address and 1st element=hint

    # hinaddr_hint_listts[i][1]=0: High reuse region
    #addr_hint_list[i][1]=1: Medium reuse region
    #addr_hint_list[i][1]=2: Low reuse region

    num_accesses=len(addr_hint_list)

    dq=np.array([])     #LRU circular queue
    dictionary={}       #helps in iteration of LRU

    for i in range(len(addr_hint_list)):
        dq, dictionary=refer(addr_hint_list[i][0], addr_hint_list[i][1], dq, dictionary)