TLB/src/SetAssociativeCache.py

   1 from nmigen import Array, Memory, Module, Signal
   2 from nmigen.compat.genlib import fsm
   3 from nmigen.cli import main
   4
   5 from AddressEncoder import AddressEncoder
   6
   7 SA_NA = "00" # no action (none)
   8 SA_RD = "01" # read
   9 SA_WR = "10" # write
  10
  11
  12 class SetAssociativeCache():
  13     """ Set Associative Cache Memory
  14
  15         The purpose of this module is to generate a memory cache given the
  16         constraints passed in. This will create a n-way set associative cache.
  17         It is expected for the SV TLB that the VMA will provide the set number
  18         while the ASID provides the tag (still to be decided).
  19
  20     """
  21     def __init__(self, tag_size, data_size, set_count, way_count):
  22         """ Arguments
  23             * tag_size (bits): The bit count of the tag
  24             * data_size (bits): The bit count of the data to be stored
  25             * set_count (number): The number of sets/entries in the cache
  26             * way_count (number): The number of slots a data can be stored
  27                                   in one set
  28         """
  29         # Internals
  30         self.active = 0
  31         self.lru_start = self.active + 1
  32         self.lru_end = self.lru_start + way_count.bit_length()
  33         self.data_start = self.lru_end
  34         self.data_end = self.data_start + data_size
  35         self.tag_start = self.data_end
  36         self.tag_end = self.tag_start + tag_size
  37         cache_data = way_count + 1 # Bits required to represent LRU and active
  38         input_size = tag_size + data_size # Size of the input data
  39         memory_width = input_size + cache_data # The width of the cache memory
  40         memory_array = Array(Memory(memory_width, entry_count)) # Memory Array
  41         self.read_port_array = Array()  # Read port array from Memory Array
  42         self.write_port_array = Array() # Write port array from Memory Array
  43         # Populate read/write port arrays
  44         for i in range(way_count):
  45             mem = memory_array[i] # Memory being parsed
  46             self.read_port_array.append(mem.read_port()) # Store read port
  47             self.write_port_array.append(mem.write_port()) # Store write port
  48
  49         self.way_count = way_count # The number of slots in one set
  50         self.tag_size = tag_size  # The bit count of the tag
  51         self.data_size = data_size  # The bit count of the data to be stored
  52
  53         self.encoder = AddressEncoder(max=way_count) # Finds valid entries
  54
  55         # Input
  56         self.enable = Signal(1) # Whether the cache is enabled
  57         self.command = Signal(2)  # 00=None, 01=Read, 10=Write (see SA_XX)
  58         self.cset = Signal(max=set_count) # The set to be checked
  59         self.tag = Signal(tag_size) # The tag to find
  60         self.data_i = Signal(data_size + tag_size) # The input data
  61
  62         # Output
  63         self.ready = Signal(1) # 0 => Processing 1 => Ready for commands
  64         self.hit = Signal(1) # Tag matched one way in the given set
  65         self.multiple_hit = Signal(1) # Tag matched many ways in the given set
  66         self.data_o = Signal(data_size) # The data linked to the matched tag
  67
  68     def check_tags(self, m):
  69         """
  70         Validate the tags in the selected set. If one and only one tag matches
  71         set its state to zero and increment all others by one. We only advance
  72         to the next state if a single hit is found.
  73         """
  74         # Vector to store way valid results
  75         # A zero denotes a way is invalid
  76         valid_vector = []
  77         # Loop through memory to prep read/write ports and set valid_vector
  78         # value
  79         for i in range(self.way_count):
  80             m.d.comb += [
  81                 self.write_port_array[i].addr.eq(self.cset),
  82                 self.read_port_array[i].addr.eq(self.cset)
  83             ]
  84             # Pull out active bit from data
  85             data = self.read_port_array[i].data;
  86             active_bit = data[self.active];
  87             # Validate given tag vs stored tag
  88             tag = data[self.tag_start:self.tag_end]
  89             tag_valid = self.tag == tag
  90             # An entry is only valid if the tags match AND
  91             # is marked as a valid entry
  92             valid_vector.append(tag_valid & valid_bit)
  93
  94         # Pass encoder the valid vector
  95         self.encoder.i.eq(Cat(*valid_vector))
  96         # Only one entry should be marked
  97         # This is due to already verifying the tags
  98         # matched and the valid bit is high
  99         with m.If(self.encoder.single_match):
 100             m.next = "FINISHED"
 101             # Pull out data from the read port
 102             read_port = self.read_port_array[self.encoder.o]
 103             data = read_port.data[self.data_start:self.data_end]
 104             m.d.comb += [
 105                 self.hit.eq(1),
 106                 self.multiple_hit.eq(0),
 107                 self.data_o.eq(data)
 108             ]
 109             self.update_set(m)
 110         # Oh no! Seal the gates! Multiple tags matched?!? kasd;ljkafdsj;k
 111         with m.Elif(self.encoder.multiple_match):
 112             m.d.comb += [
 113                 self.hit.eq(0),
 114                 self.multiple_hit.eq(1),
 115                 self.data_o.eq(0)
 116             ]
 117         # No tag matches means no data
 118         with m.Else():
 119             m.d.comb += [
 120                 self.hit.eq(0),
 121                 self.multiple_hit.eq(0),
 122                 self.data_o.eq(0)
 123             ]
 124
 125     def update_set(self, m):
 126         """
 127         Update the LRU values for each way in the given set if the entry is
 128         active.
 129         """
 130         # Go through all ways in the set
 131         for i in range(self.way_count):
 132             # Pull out read port for readability
 133             read_port = self.read_port_array[i]
 134             with m.If(read_port.data[0]):
 135                 # Pull out lru state for readability
 136                 lru_state = read_port.data[self.data_start:self.data_end]
 137                 # Pull out write port for readability
 138                 write_port = self.write_port_array[i]
 139                 # Enable write for the memory block
 140                 m.d.comb += write_port.en.eq(1)
 141                 with m.If(i == self.encoder.o):
 142                     m.d.comb += write_port.data.eq(0)
 143                 with m.Elif(state < self.way_count):
 144                     m.d.comb += write_port.data.eq(state + 1)
 145                 with m.Else():
 146                     m.d.comb += write_port.data.eq(state)
 147
 148     def read(self, m):
 149         """
 150         Go through the read process of the cache.
 151         This takes two cycles to complete. First it checks for a valid tag
 152         and secondly it updates the LRU values.
 153         """
 154         with m.FSM() as fsm:
 155             with m.State("SEARCH"):
 156                 m.d.comb += self.ready.eq(0)
 157                 # check_tags will set the state if the conditions are met
 158                 self.check_tags(m)
 159             with m.State("FINISHED"):
 160                 m.next = "SEARCH"
 161                 m.d.comb += self.ready.eq(1)
 162
 163     def elaborate(self, platform=None):
 164         m = Module()
 165         m.submodules += self.read_port_array
 166         m.submodules += self.write_port_array
 167
 168         with m.If(self.enable):
 169             with m.Switch(self.command):
 170                 # Search all sets at a particular tag
 171                 with m.Case(SA_RD):
 172                     self.read(m)
 173                 # TODO
 174                 # Write to a given tag
 175                 # with m.Case(SA_WR):
 176                     # Search for available space
 177                     # What to do when there is no space
 178                     # Maybe catch multiple tags write here?
 179                     # TODO
 180         return m