## File: cachesimulator.py ## Author(s): Peter Castelein, Tristan Koster ## Date: 12/08/2021 ## E-mail(s): petercastelein@tamu.edu, tkoster123@tamu.edu ## Description: ## Our cache simlulator which mirrors the functionallity of the online 351 simulator import sys import math from random import randrange from collections import deque class CacheLine: ''' Class to represent a line inside a cache block Attributes: freq: frequency policy counter valid: valid bit dirty: dirty bit tag: tag bits data: dictionary representing the data bits in the line ''' def __init__(self): ## frequency policy counter self.freq = 0 ## valid bit self.valid = 0 ## dirty bit self.dirty = 0 ##tag address as string self.tag = "" ##Data as a dictionary self.data = {} def __str__(self): ##toString method to easily print a cacheline object """ toString method to display a line as: valid dirty tag data """ final = (f"{self.valid} {self.dirty} {self.tag}") for key,value in self.data.items(): final += " " + value return final class Cache: ''' Class to represent the entire cache based on user inputs Attributes: size: total cache size block_size: size of each block e_val: associativity setting set_size: size of each set tag_l: length of set address bit s_l: length of set address bits b_l: length of data block address bits pol: replacement policy hit: hit policy miss: miss policy num_hits: total number of hits num_misses: total number of misses sets: list of sets (sets are represented as lists) lines_qs: list of queues of line indexes for replacement policy ''' def __init__(self): ##total cache size self.size = 0 ##size of each block self.block_size = 0 ##associativity self.e_val = 0 ##size of each set self.set_size = 0 ##length of tag address bit self.tag_l = 0 ##length of set address bits self.s_l = 0 ##length of data block address bits self.b_l = 0 ##replacement policy self.pol = 0 ##hit policy self.hit = 0 ##miss policy self.miss = 0 ##total number of hits self.num_hits = 0 ##total number of misses self.num_misses = 0 ##list of sets self.sets = [] ##queue of lines self.line_qs = [] ## Global variables c = Cache() ## Our cache, the data struct RAM = ["00"] * 256 ## Creates list of zero'd bytes of length 256 def main(): ''' Main function that runs the whole program ''' inputFile = sys.argv[1] #Get input file command line argument print("*** Welcome to the cache simulator ***") print("initialize the RAM:") #iniit-ram is typed by user ramRange = input().split(" ") # ramRange = ["init-ram", "0x00", "0xFF"] upper = hex2Decimal(ramRange[2]) with open(inputFile) as f: for i,line in enumerate(f): #i being the index counter if i > upper: break RAM[i]=(line.rstrip('\n')) print("RAM successfully initialized!") cacheSize = int(input("cache size: ")) while cacheSize < 8 or cacheSize > 256: cacheSize = int(input("cache size: ")) blockSize = int(input("data block size: ")) while blockSize < 1 or blockSize > 8: blockSize = int(input("data block size: ")) associativity = int(input("associativity: ")) while associativity != 1 and associativity !=2 and associativity !=4: associativity = int(input("associativity: ")) replacementPolicy = int(input("replacement policy: ")) while replacementPolicy < 1 or replacementPolicy > 3: replacementPolicy = int(input("replacement policy: ")) writeHit = int(input("write hit policy: ")) while writeHit != 1 and writeHit != 2: writeHit = int(input("write hit policy: ")) writeMiss = int(input("write miss policy: ")) while writeMiss != 1 and writeMiss != 2: writeMiss = int(input("write miss policy: ")) #Calculations below are equivalent to important sizing calcs in textbook/slides c.size = cacheSize c.block_size = blockSize c.e_val = associativity c.set_size = int(math.ceil(cacheSize/(blockSize * associativity))) c.s_l = int(math.ceil(math.log(c.set_size, 2))) c.b_l = int(math.ceil(math.log(blockSize, 2))) c.tag_l = int(math.ceil(math.log(len(RAM), 2) - (c.s_l + c.b_l))) c.pol = replacementPolicy c.hit = writeHit c.miss = writeMiss for i in range(c.set_size): c.sets.append([]) # each individual set in the cache sets is a list c.line_qs.append(deque()) for j in range(c.e_val): c.sets[i].append(CacheLine()) # will access lines as 2d lists - i is set selection, j is line selction c.sets[i][j].tag = "00" # Tag is initialized to 0 and is always represented by a byte c.line_qs[i].append(j) for k in range(c.block_size): c.sets[i][j].data[k] = "00" # Data blocks initialized to all 00's print("cache successfully configured!") running = True while running: #Run until quit print("*** Cache simulator menu ***") # command now splitting on blank for Read/Write parameters command = input("type one command:\n1. cache-read\n2. cache-write\n3. cache-flush\n4. cache-view\n5. memory-view\n6. cache-dump\n7. memory-dump\n8. quit\n****************************\n").split(" ") if command[0] == 'quit': #Leave loop now if quit break address = "" if len(command) < 2 else command[1] val = "" if len(command) < 3 else command[2] # Switch on imput command to appropriate function, neccesitates giving all functions same parameters # address and val used in cacheWrite # addresss used in cacheRead, val not used # addresss and val are ignored for all other commands switch(command[0], address, val) print("Exiting Simulator...") def cacheRead(address, val): ''' Attempts to read a value at input address. If it is a hit, the value is returned, a hit is counted and the metrics for replacement are updated. If it is a miss, a line to be evicted is selected by policy and he line is writen back to memory if the dirty bit is set. The evicted line is then filled with the corresponding values from memory and the line is set to clean and valid. address: The Address that we are attempting to read a value from val: Not Used output: set: The set index tag: The tag value hit: yes/no for read hit eviction_line: The evicted line's index ram_address: The ram address data: The data read (either from cache or memeory) return: None ''' # convert address to a binary string add_i = hex2Decimal(address) add_b = '{0:08b}'.format(add_i) # break it into accessor information # generate tag address value as 1 byte hex string if (c.tag_l): #2X specifies hex string, the int function converts the bit string slice to int tag = '{0:02X}'.format(int(add_b[0:c.tag_l],2)) else: tag = "00" # generate set index as bit string and int if (c.s_l): set_index_s = add_b[c.tag_l:c.tag_l + c.s_l] set_index = int(set_index_s, 2) else: set_index_s = "" set_index = 0 # generate block offset as bit string and int if (c.b_l): block_offset_s = add_b[c.tag_l + c.s_l:] block_offset = int(block_offset_s, 2) else: block_offset = 0 is_hit = False for j in range(c.e_val): if c.sets[set_index][j].valid == 1: if c.sets[set_index][j].tag == tag: # read data on hit data = c.sets[set_index][j].data[block_offset] is_hit = True ev_line = -1 ram_ad = -1 c.num_hits += 1 # eviction policy tracking update if c.pol == 2: # least recently used logic c.line_qs[set_index].remove(j) c.line_qs[set_index].append(j) if c.pol == 3: # least freq used logic c.sets[set_index][j].freq += 1 break if(is_hit): is_hit = "yes" else: is_hit = "no" if c.pol == 1: if (len(c.line_qs[set_index])): # pick smallest line number to evict ev_line = c.line_qs[set_index].popleft() else: # All lines full, randomly evicting a line ev_line = randrange(c.e_val) elif c.pol == 2: # least recently used logic ev_line = c.line_qs[set_index].popleft() c.line_qs[set_index].append(ev_line) else: # least freq used logic ev_line = 0 for j in range(1, c.e_val): if c.sets[set_index][j].freq < c.sets[set_index][ev_line].freq: ev_line = j c.sets[set_index][ev_line].freq +=1 # If we are evicting a line with a dirty bit, we need to write that cache line back to memory if c.sets[set_index][ev_line].dirty: write_back_add_b = c.sets[set_index][ev_line].tag + set_index_s + ("0" * c.b_l) write_back_add_i = int(write_back_add_b, 2) for k in range(c.block_size): RAM[write_back_add_i+k] = c.sets[set_index][ev_line].data[k] ram_ad = address data = RAM[add_i] # setup add_i to be pre offset for full line load add_i = add_i - block_offset c.sets[set_index][ev_line].tag = tag c.sets[set_index][ev_line].dirty = 0 c.sets[set_index][ev_line].valid = 1 for k in range(c.block_size): c.sets[set_index][ev_line].data[k] = RAM[add_i+k] c.num_misses += 1 print(f"set:{set_index}\ntag:{tag}\nhit:{is_hit}\neviction_line:{ev_line}\nram_address:{ram_ad}\ndata:0x{data}") def cacheWrite(address, val): ''' Attempts to write a value at input address. If it is a hit, the value is writen according to write hit policy, a hit is counted and the metrics for replacement are updated. If it is a miss, If we are not write allocating, then the memory is written. It we are write allocating, then the line to be evicted is selected by policy and the line is writen back to memory if the dirty bit is set. The evicted line is then filled with the corresponding values from memory and updated with the val we wanted to write. Finally, if write through is enabled, the value is also written to memory and the line is set clean and valid, otherwise the line is set valid and dirty. address: The Address that we are attempting to write a value to val: The value being written output: set: The set index tag: The tag value write_hit: yes/no for write hit eviction_line: The evicted line's index ram_address: The ram address data: The data writen (either to cache or memeory or both) dirty_bit: The status of hypothetical writen line's dirty bit return: None ''' val = val[2:] # convert address to a binary string add_i = hex2Decimal(address) add_b = '{0:08b}'.format(add_i) # break it into accessor information # generate tag address value as 1 byte hex string if (c.tag_l): #2X specifies hex string, the int function converts the bit string slice to int tag = '{0:02X}'.format(int(add_b[0:c.tag_l],2)) else: tag = "00" # generate set index as bit string and int if (c.s_l): set_index_s = add_b[c.tag_l:c.tag_l + c.s_l] set_index = int(set_index_s, 2) else: set_index_s = "" set_index = 0 # generate block offset as bit string and int if (c.b_l): block_offset_s = add_b[c.tag_l + c.s_l:] block_offset = int(block_offset_s, 2) else: block_offset = 0 is_hit = False for j in range(c.e_val): if c.sets[set_index][j].valid == 1: if c.sets[set_index][j].tag == tag: # write data on hit c.sets[set_index][j].data[block_offset] = val if (c.hit == 1): RAM[add_i] = val # write through dirty_b = 0 # write through else: # write back c.sets[set_index][j].dirty = 1 dirty_b = 1 # write back is_hit = True ev_line = -1 ram_ad = -1 c.num_hits += 1 # eviction policy tracking update if c.pol == 2: # least recently used logic c.line_qs[set_index].remove(j) c.line_qs[set_index].append(j) if c.pol == 3: # least freq used logic c.sets[set_index][j].freq += 1 break if(is_hit): is_hit = "yes" else: is_hit = "no" if (c.miss == 2): ev_line = -1 # no write-allocate RAM[add_i] = val # no write-allocate dirty_b = 0 # no write-allocate else: # write-allocate # find line to evict if c.pol == 1: if (len(c.line_qs[set_index])): # pick smallest line number to evict ev_line = c.line_qs[set_index].popleft() else: # All lines full, randomly evicting a line ev_line = randrange(c.e_val) elif c.pol == 2: # least recently used logic ev_line = c.line_qs[set_index].popleft() c.line_qs[set_index].append(ev_line) else: # least freq used logic ev_line = 0 for j in range(1, c.e_val): if c.sets[set_index][j].freq < c.sets[set_index][ev_line].freq: ev_line = j c.sets[set_index][ev_line].freq +=1 # If we are evicting a line with a dirty bit, we need to write that cache line back to memory if c.sets[set_index][ev_line].dirty: write_back_add_b = c.sets[set_index][ev_line].tag + set_index_s + ("0" * c.b_l) write_back_add_i = int(write_back_add_b, 2) for k in range(c.block_size): RAM[write_back_add_i+k] = c.sets[set_index][ev_line].data[k] # setup add_i_no_off to be pre offset for full line load add_i_no_off = add_i - block_offset c.sets[set_index][ev_line].tag = tag c.sets[set_index][ev_line].valid = 1 c.sets[set_index][ev_line].dirty = 1 dirty_b = 1 for k in range(c.block_size): c.sets[set_index][ev_line].data[k] = RAM[add_i_no_off+k] # write-allocate c.sets[set_index][ev_line].data[block_offset] = val # Write through hit policy demands that the RAM is kept up to date with cache. if (c.hit == 1): RAM[add_i] = val c.sets[set_index][ev_line].dirty = 0 dirty_b = 0 ram_ad = address c.num_misses += 1 print(f"set:{set_index}\ntag:{tag}\nwrite_hit:{is_hit}\neviction_line:{ev_line}\nram_address:{ram_ad}\ndata:0x{val}\ndirty_bit:{dirty_b}") def cacheFlush(address, val): #Set everything to zero ''' Clears out the entire cache and resets everything to 0 addresss: Not Used val: Not Used return: None ''' for i in range(c.set_size): c.line_qs[i].clear() for j in range(c.e_val): c.line_qs[i].append(j) c.sets[i][j].dirty = 0 c.sets[i][j].valid = 0 c.sets[i][j].tag = '00' for key,value in c.sets[i][j].data.items(): c.sets[i][j].data[key] = '00' print("cache_cleared") def cacheView(address, val): ''' Displays the entire queue for the user to see while also displaying policies address: Not Used val: Not Used return: None ''' replacement = "random_replacement" if c.pol == 1 else "least_recently_used" hit = "write-through" if c.hit == 1 else "write-back" miss = "write-allocate" if c.miss == 1 else "no_write-allocate" print(f"cache_size:{c.size}\ndata_block_size:{c.block_size}\nassociativity:{c.e_val}\nreplacement_policy:{replacement}\nwrite_hit_policy:{hit}\nwrite_miss_policy:{miss}\nnumber_of_cache_hits:{c.num_hits}\nnumber_of_cache_misses:{c.num_misses}\ncache_content:") for i in range(c.set_size): for j in range(c.e_val): print(c.sets[i][j]) #j represents a cache line object index def hexBuilder(lineAddress): #Converts decimal to hexadecimal ''' Converts an address from decimal to hexadecimal lineAddress: Address is decimal form return: Hexadecimal as a string ''' digits = "0123456789ABCDEF" x = (lineAddress % 16) rest = lineAddress // 16 if (rest == 0): return digits[x] # recursively builds the string return hexBuilder(rest) + digits[x] def hex2Decimal(hex): #Convert from hexadecimal to decimal ''' Converts a hexadecimal number into decimal hex: hexadecimal number as a string return: decimal number as an int ''' hex = hex[2::] dec = int(hex,16) return dec def memoryView(address, val): ''' Displays the current RAM for user address: Not Used val: Not Used return: None ''' lineAddress = 0 memorySize = 256 #Hardcoded for now print(f"memory_size: {memorySize}\nmemory_content: \naddress:data") lineHex = hexBuilder(lineAddress) if len(lineHex) == 1: lineHex = "0"+ lineHex #In case hexadecimal contains only one digit lineHex = "0x"+lineHex counter = 0 for key in RAM: print(f"{lineHex} {key}" ,end=" ") if counter == 0 else print(key, end = " ") counter +=1 if counter == 8: #Print 8 per line lineAddress+=8 lineHex = hexBuilder(lineAddress) #Grab new hexadecimal number if len(lineHex) == 1: lineHex = "0"+ lineHex lineHex = "0x"+lineHex print() counter = 0 def cacheDump(address, val): ''' Copies data of the cache into a text file address: Not Used val: Not Used return: None ''' textfile = open("cache.txt","w") for i in range(c.set_size): for j in range(c.e_val): for key,value in c.sets[i][j].data.items(): #Put cache values in file textfile.write(value + ' ') textfile.write("\n") def memoryDump(address, val): #Copies everything currently in RAM into a text file ''' Copies data of the RAM into a text file address: Not Used val: Not Used return: None ''' textfile = open("ram.txt", "w") for element in RAM: textfile.write(element + "\n") textfile.close() def default(address, val): ''' Runs if switch statement recieves invalid input address: Not Used val: Not Used return: None ''' print("Invalid input") def switch(command, address, val): ''' Switch statement equivalent for python 3 command: user input of which command to run address: address value for cache-read/write val: value for cache write return: user inputted function call ''' switcher = { 'cache-read':cacheRead, 'cache-write':cacheWrite, 'cache-flush':cacheFlush, 'cache-view':cacheView, 'memory-view':memoryView, 'cache-dump':cacheDump, 'memory-dump':memoryDump } return switcher.get(command,default)(address, val) if __name__ == "__main__": main()