src/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 import sys
  10 sys.path.append("ariane/src/")
  11
  12 from nmigen import Array, Cat, Memory, Module, Signal, Mux, Elaboratable
  13 from nmigen.compat.genlib import fsm
  14 from nmigen.cli import main
  15 from nmigen.cli import verilog, rtlil
  16
  17 from AddressEncoder import AddressEncoder
  18 from MemorySet import MemorySet
  19
  20 # TODO: use a LFSR that advances continuously and picking the bottom
  21 # few bits from it to select which cache line to replace, instead of PLRU
  22 # http://bugs.libre-riscv.org/show_bug.cgi?id=71
  23 from plru import PLRU
  24 from LFSR import LFSR, LFSR_POLY_24
  25
  26 SA_NA = "00" # no action (none)
  27 SA_RD = "01" # read
  28 SA_WR = "10" # write
  29
  30
  31 class SetAssociativeCache(Elaboratable):
  32     """ Set Associative Cache Memory
  33
  34         The purpose of this module is to generate a memory cache given the
  35         constraints passed in. This will create a n-way set associative cache.
  36         It is expected for the SV TLB that the VMA will provide the set number
  37         while the ASID provides the tag (still to be decided).
  38
  39     """
  40     def __init__(self, tag_size, data_size, set_count, way_count, lfsr=False):
  41         """ Arguments
  42             * tag_size (bits): The bit count of the tag
  43             * data_size (bits): The bit count of the data to be stored
  44             * set_count (number): The number of sets/entries in the cache
  45             * way_count (number): The number of slots a data can be stored
  46                                   in one set
  47             * lfsr: if set, use an LFSR for (pseudo-randomly) selecting
  48                     set/entry to write to.  otherwise, use a PLRU
  49         """
  50         # Internals
  51         self.lfsr_mode = lfsr
  52         self.way_count = way_count  # The number of slots in one set
  53         self.tag_size = tag_size    # The bit count of the tag
  54         self.data_size = data_size  # The bit count of the data to be stored
  55
  56         # set up Memory array
  57         self.mem_array = Array() # memory array
  58         for i in range(way_count):
  59             ms = MemorySet(data_size, tag_size, set_count, active=0)
  60             self.mem_array.append(ms)
  61
  62         # Finds valid entries
  63         self.encoder = AddressEncoder(way_count)
  64
  65         # setup PLRU or LFSR
  66         if lfsr:
  67             # LFSR mode
  68             self.lfsr = LFSR(LFSR_POLY_24)
  69         else:
  70             # PLRU mode
  71             self.plru = PLRU(way_count) # One block to handle plru calculations
  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(max=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         self.multiple_hit = Signal(1)   # Tag matched many ways in the given set
  88         self.data_o = Signal(data_size) # The data linked to the matched tag
  89
  90     def check_tags(self, m):
  91         """ Validate the tags in the selected set. If one and only one
  92             tag matches set its state to zero and increment all others
  93             by one. We only advance to next state if a single hit is found.
  94         """
  95         # Vector to store way valid results
  96         # A zero denotes a way is invalid
  97         valid_vector = []
  98         # Loop through memory to prep read/write ports and set valid_vector
  99         for i in range(self.way_count):
 100             valid_vector.append(self.mem_array[i].valid)
 101
 102         # Pass encoder the valid vector
 103         m.d.comb += self.encoder.i.eq(Cat(*valid_vector))
 104
 105         # Only one entry should be marked
 106         # This is due to already verifying the tags
 107         # matched and the valid bit is high
 108         with m.If(self.hit):
 109             m.next = "FINISHED_READ"
 110             # Pull out data from the read port
 111             data = self.mem_array[self.encoder.o].data_o
 112             m.d.comb += self.data_o.eq(data)
 113             if not self.lfsr_mode:
 114                 self.access_plru(m)
 115
 116         # Oh no! Seal the gates! Multiple tags matched?!? kasd;ljkafdsj;k
 117         with m.Elif(self.multiple_hit):
 118             # XXX TODO, m.next = "FINISHED_READ" ? otherwise stuck
 119             m.d.comb += self.data_o.eq(0)
 120
 121         # No tag matches means no data
 122         with m.Else():
 123             # XXX TODO, m.next = "FINISHED_READ" ? otherwise stuck
 124             m.d.comb += self.data_o.eq(0)
 125
 126     def access_plru(self, m):
 127         """ An entry was accessed and the plru tree must now be updated
 128         """
 129         # Pull out the set's entry being edited
 130         plru_entry = self.plru_array[self.cset]
 131         m.d.comb += [
 132             # Set the plru data to the current state
 133             self.plru.plru_tree.eq(plru_entry),
 134             # Set that the cache was accessed
 135             self.plru.lu_access_i.eq(1)
 136         ]
 137
 138     def read(self, m):
 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("READY"):
 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_READ"):
 149                 m.next = "READY"
 150                 m.d.comb += self.ready.eq(1)
 151                 if not self.lfsr_mode:
 152                     plru_tree_o = self.plru.plru_tree_o
 153                     m.d.sync += self.plru_array[self.cset].eq(plru_tree_o)
 154
 155     def write_entry(self, m):
 156         if not self.lfsr_mode:
 157             m.d.comb += [# set cset (mem address) into PLRU
 158                          self.plru.plru_tree.eq(self.plru_array[self.cset]),
 159                          # and connect plru to encoder for write
 160                          self.encoder.i.eq(self.plru.replace_en_o)
 161                         ]
 162             write_port = self.mem_array[self.encoder.o].w
 163         else:
 164             # use the LFSR to generate a random(ish) one of the mem array
 165             lfsr_output = Signal(max=self.way_count)
 166             lfsr_random = Signal(max=self.way_count)
 167             m.d.comb += lfsr_output.eq(self.lfsr.state) # lose some bits
 168             # address too big, limit to range of array
 169             m.d.comb += lfsr_random.eq(Mux(lfsr_output > self.way_count,
 170                                            lfsr_output - self.way_count,
 171                                            lfsr_output))
 172             write_port = self.mem_array[lfsr_random].w
 173
 174         # then if there is a match from the encoder, enable the selected write
 175         with m.If(self.encoder.single_match):
 176             m.d.comb += write_port.en.eq(1)
 177
 178     def write(self, m):
 179         """ Go through the write process of the cache.
 180             This takes two cycles to complete. First it writes the entry,
 181             and secondly it updates the PLRU (in plru mode)
 182         """
 183         with m.FSM() as fsm_write:
 184             with m.State("READY"):
 185                 m.d.comb += self.ready.eq(0)
 186                 self.write_entry(m)
 187                 m.next ="FINISHED_WRITE"
 188             with m.State("FINISHED_WRITE"):
 189                 m.d.comb += self.ready.eq(1)
 190                 if not self.lfsr_mode:
 191                     plru_entry = self.plru_array[self.cset]
 192                     m.d.sync += plru_entry.eq(self.plru.plru_tree_o)
 193                 m.next = "READY"
 194
 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)