TLB/src/SetAssociativeCache.py

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