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