src/unused/TLB/SetAssociativeCache.py

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