TLB/src/SetAssociativeCache.py

   1 import sys
   2 sys.path.append("../src/ariane")
   3
   4 from nmigen import Array, Cat, 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
  11 # TODO: use a LFSR that advances continuously and picking the bottom
  12 # few bits from it to select which cache line to replace, instead of PLRU
  13 # http://bugs.libre-riscv.org/show_bug.cgi?id=71
  14 from plru import PLRU
  15
  16 SA_NA = "00" # no action (none)
  17 SA_RD = "01" # read
  18 SA_WR = "10" # write
  19
  20 class MemorySet:
  21     def __init__(self, memory_width, set_count, active,
  22                        tag_start, tag_end, tag_size):
  23         #self.memory_width = memory_width
  24         #self.set_count = set_count
  25         self.tag_start = tag_start
  26         self.tag_end = tag_end
  27         self.active = active
  28         self.mem = Memory(memory_width, set_count)
  29         self.r = self.mem.read_port()
  30         self.w = self.mem.write_port()
  31
  32         # inputs (address)
  33         self.cset = Signal(max=set_count)          # The set to be checked
  34         self.tag = Signal(tag_size)                # The tag to find
  35
  36         # outputs
  37         self.active_bit = Signal()
  38         self.tag_valid = Signal()
  39         self.valid = Signal()
  40
  41     def elaborate(self, platform):
  42         m = Module()
  43         m.submodules.mem = self.mem
  44         m.submodules.r = self.r
  45         m.submodules.w = self.w
  46
  47         read_port = self.r
  48         m.d.comb += read_port.addr.eq(self.cset)
  49         # Pull out active bit from data
  50         data = read_port.data
  51         m.d.comb += self.active_bit.eq(data[self.active])
  52         # Validate given tag vs stored tag
  53         tag = data[self.tag_start:self.tag_end]
  54         m.d.comb += self.tag_valid.eq(self.tag == tag)
  55         # An entry is only valid if the tags match AND
  56         # is marked as a valid entry
  57         m.d.comb += self.valid.eq(self.tag_valid & self.active_bit)
  58
  59         return m
  60
  61
  62 class SetAssociativeCache():
  63     """ Set Associative Cache Memory
  64
  65         The purpose of this module is to generate a memory cache given the
  66         constraints passed in. This will create a n-way set associative cache.
  67         It is expected for the SV TLB that the VMA will provide the set number
  68         while the ASID provides the tag (still to be decided).
  69
  70     """
  71     def __init__(self, tag_size, data_size, set_count, way_count):
  72         """ Arguments
  73             * tag_size (bits): The bit count of the tag
  74             * data_size (bits): The bit count of the data to be stored
  75             * set_count (number): The number of sets/entries in the cache
  76             * way_count (number): The number of slots a data can be stored
  77                                   in one set
  78         """
  79         # Internals
  80         active = 0
  81         self.data_start = active + 1
  82         self.data_end = self.data_start + data_size
  83         self.tag_start = self.data_end
  84         self.tag_end = self.tag_start + tag_size
  85         input_size = tag_size + data_size # Size of the input data
  86         memory_width = input_size + 1 # The width of the cache memory
  87         self.mem_array = Array() # memory array
  88
  89         for i in range(way_count):
  90             ms = MemorySet(memory_width, set_count, active,
  91                            tag_size, self.tag_start, self.tag_end)
  92             self.mem_array.append(ms)
  93
  94         self.way_count = way_count  # The number of slots in one set
  95         self.tag_size = tag_size    # The bit count of the tag
  96         self.data_size = data_size  # The bit count of the data to be stored
  97
  98         # Finds valid entries
  99         self.encoder = AddressEncoder(way_count)
 100
 101         self.plru = PLRU(way_count) # Single block to handle plru calculations
 102         self.plru_array = Array() # PLRU data on each set
 103         for i in range(set_count):
 104             self.plru_array.append(Signal(self.plru.TLBSZ, name="plru%d" % i))
 105
 106         # Input
 107         self.enable = Signal(1)   # Whether the cache is enabled
 108         self.command = Signal(2)  # 00=None, 01=Read, 10=Write (see SA_XX)
 109         self.cset = Signal(max=set_count)          # The set to be checked
 110         self.tag = Signal(tag_size)                # The tag to find
 111         self.data_i = Signal(data_size) # The input data
 112
 113         # Output
 114         self.ready = Signal(1) # 0 => Processing 1 => Ready for commands
 115         self.hit = Signal(1)            # Tag matched one way in the given set
 116         self.multiple_hit = Signal(1)   # Tag matched many ways in the given set
 117         self.data_o = Signal(data_size) # The data linked to the matched tag
 118
 119     def check_tags(self, m):
 120         """ Validate the tags in the selected set. If one and only one
 121             tag matches set its state to zero and increment all others
 122             by one. We only advance to next state if a single hit is found.
 123         """
 124         # Vector to store way valid results
 125         # A zero denotes a way is invalid
 126         valid_vector = []
 127         # Loop through memory to prep read/write ports and set valid_vector
 128         # value
 129         for i in range(self.way_count):
 130             valid_vector.append(self.mem_array[i].valid)
 131
 132         # Pass encoder the valid vector
 133         m.d.comb += self.encoder.i.eq(Cat(*valid_vector))
 134         # Only one entry should be marked
 135         # This is due to already verifying the tags
 136         # matched and the valid bit is high
 137         with m.If(self.hit):
 138             m.next = "FINISHED_READ"
 139             # Pull out data from the read port
 140             read_port = self.mem_array[self.encoder.o].r
 141             data = read_port.data[self.data_start:self.data_end]
 142             m.d.comb += [
 143                 self.data_o.eq(data)
 144             ]
 145             self.access_plru(m)
 146         # Oh no! Seal the gates! Multiple tags matched?!? kasd;ljkafdsj;k
 147         with m.Elif(self.multiple_hit):
 148             # XXX TODO, m.next = "FINISHED_READ" ? otherwise stuck
 149             m.d.comb += [
 150                 self.data_o.eq(0)
 151             ]
 152         # No tag matches means no data
 153         with m.Else():
 154             # XXX TODO, m.next = "FINISHED_READ" ? otherwise stuck
 155             m.d.comb += [
 156                 self.data_o.eq(0)
 157             ]
 158
 159     def access_plru(self, m):
 160         """ An entry was accessed and the plru tree must now be updated
 161         """
 162         # Pull out the set's entry being edited
 163         plru_entry = self.plru_array[self.cset]
 164         m.d.comb += [
 165             # Set the plru data to the current state
 166             self.plru.plru_tree.eq(plru_entry),
 167             # Set what entry was just hit
 168             self.plru.lu_hit.eq(self.encoder.o),
 169             # Set that the cache was accessed
 170             self.plru.lu_access_i.eq(1)
 171         ]
 172
 173     def read(self, m):
 174         """ Go through the read process of the cache.
 175             This takes two cycles to complete. First it checks for a valid tag
 176             and secondly it updates the LRU values.
 177         """
 178         with m.FSM() as fsm_read:
 179             with m.State("READY"):
 180                 m.d.comb += self.ready.eq(0)
 181                 # check_tags will set the state if the conditions are met
 182                 self.check_tags(m)
 183             with m.State("FINISHED_READ"):
 184                 m.next = "READY"
 185                 m.d.comb += self.ready.eq(1)
 186                 m.d.sync += self.plru_array[self.cset].eq(self.plru.plru_tree_o)
 187
 188     def write_entry(self, m):
 189         lru_entry = self.plru.replace_en_o
 190         plru_entry = self.plru_array[self.cset]
 191         m.d.comb += [
 192             self.plru.plru_tree.eq(plru_entry),
 193             self.encoder.i.eq(lru_entry)
 194         ]
 195
 196         with m.If(self.encoder.single_match):
 197             write_port = self.mem_array[self.encoder.o].w
 198             m.d.comb += [
 199                 write_port.en.eq(1),
 200                 write_port.addr.eq(self.cset),
 201                 write_port.data.eq(Cat(1, self.data_i, self.tag))
 202             ]
 203
 204     def write(self, m):
 205         with m.FSM() as fsm_write:
 206             with m.State("READY"):
 207                 m.d.comb += self.ready.eq(0)
 208                 self.write_entry(m)
 209                 m.next ="FINISHED_WRITE"
 210             with m.State("FINISHED_WRITE"):
 211                 m.d.comb += self.ready.eq(1)
 212                 plru_entry = self.plru_array[self.cset]
 213                 m.d.sync += plru_entry.eq(self.plru.plru_tree_o)
 214                 m.next = "READY"
 215
 216
 217     def elaborate(self, platform=None):
 218         m = Module()
 219
 220         m.submodules.PLRU = self.plru
 221         m.submodules.AddressEncoder = self.encoder
 222         for i, mem in enumerate(self.mem_array):
 223             setattr(m.submodules, "mem%d" % i, mem)
 224
 225         # do these all the time?
 226         m.d.comb += [
 227             self.hit.eq(self.encoder.single_match),
 228             self.multiple_hit.eq(self.encoder.multiple_match),
 229         ]
 230
 231         for mem in self.mem_array:
 232             m.d.comb += mem.cset.eq(self.cset)
 233             m.d.comb += mem.tag.eq(self.tag)
 234
 235         with m.If(self.enable):
 236             with m.Switch(self.command):
 237                 # Search all sets at a particular tag
 238                 with m.Case(SA_RD):
 239                     self.read(m)
 240                 with m.Case(SA_WR):
 241                     self.write(m)
 242                     # Maybe catch multiple tags write here?
 243                     # TODO
 244         return m
 245
 246     def ports():
 247         return [self.enable, self.command, self.cset, self.tag, self.data_i,
 248                 self.ready, self.hit, self.multiple_hit, self.data_o]
 249
 250 if __name__ == '__main__':
 251     sac = SetAssociativeCache(4, 4, 4, 4)
 252     vl = rtlil.convert(sac)
 253     with open("SetAssociativeCache.il", "w") as f:
 254         f.write(vl)