TLB/src/Cam.py

   1 from nmigen import Array, Module, Signal
   2 from nmigen.lib.coding import Encoder
   3 from nmigen.compat.fhdl.structure import ClockDomain
   4
   5 from CamEntry import CamEntry
   6
   7 # Content Addressable Memory (CAM)
   8 # The purpose of this module is to quickly look up whether an entry exists
   9 # given a certain key and return the mapped data.
  10 # This module when given a key will search for the given key
  11 # in all internal entries and output whether a match was found or not.
  12 # If an entry is found the data will be returned and data_hit is HIGH,
  13 # if it is not LOW is asserted on data_hit. When given a write
  14 # command it will write the given key and data into the given cam entry index.
  15 # Entry managment should be performed one level above this block as lookup is
  16 # performed within.
  17 class Cam():
  18
  19     # Arguments:
  20     #  key_size: (bit count) The size of the key
  21     #  data_size: (bit count) The size of the data
  22     #  cam_size: (entry count) The number of entries int he CAM
  23     def __init__(self, key_size, data_size, cam_size):
  24         # Internal
  25         self.clk = ClockDomain(reset_less=True)
  26         self.key_size = key_size
  27         self.data_size = data_size
  28         self.cam_size = cam_size
  29         self.entry_array = Array(CamEntry(key_size, data_size) \
  30                             for x in range(cam_size))
  31         self.encoder_input = Signal(cam_size)
  32
  33         # Input
  34         self.command = Signal(2) # 00 => NA 01 => Read 10 => Write 11 => Search
  35         self.address = Signal(max=cam_size) # address of CAM Entry to write/read
  36         self.key_in = Signal(key_size) # The key to search for or to be written
  37         self.data_in = Signal(key_size) # The data to be written
  38
  39         # Output
  40         self.data_hit = Signal(1) # Denotes a key data pair was stored at key_in
  41         self.data_out = Signal(data_size) # The data mapped to by key_in
  42
  43     def elaborate(self, platform=None):
  44         m = Module()
  45
  46         m.submodules.encoder = encoder = Encoder(self.cam_size)
  47         m.submodules += self.entry_array
  48
  49         # Set the key value for every CamEntry
  50         for index in range(self.cam_size):
  51             with m.Switch(self.command):
  52                 # Read and Search both read from the CamEntry
  53                 with m.Case("-1"):
  54                     m.d.comb += self.entry_array[index].command.eq(1)
  55                 # Write only to one entry
  56                 with m.Case("10"):
  57                     with m.If(self.address == index):
  58                         m.d.comb += self.entry_array[index].command.eq(2)
  59                     with m.Else():
  60                         m.d.comb += self.entry_array[index].command.eq(0)
  61                 # NA
  62                 with m.Case():
  63                     m.d.comb += self.entry_array[index].command.eq(0)
  64
  65             m.d.comb += [
  66                    self.entry_array[index].key_in.eq(self.key_in),
  67                    self.entry_array[index].data_in.eq(self.data_in),
  68                    self.encoder_input[index].eq(self.entry_array[index].match)
  69             ]
  70
  71         with m.Switch(self.command):
  72             # Read
  73             with m.Case("01"):
  74                 m.d.comb += [
  75                     self.data_hit.eq(0),
  76                     self.data_out.eq(self.entry_array[self.address].data)
  77                 ]
  78             # Write
  79             with m.Case("10"):
  80                 m.d.comb += [
  81                     self.data_hit.eq(0),
  82                     self.entry_array[self.address].key_in.eq(self.key_in),
  83                     self.entry_array[self.address].data_in.eq(self.data_in)
  84                 ]
  85             # Search
  86             with m.Case("11"):
  87                 m.d.comb += encoder.i.eq(self.encoder_input)
  88                 with m.If(encoder.n == 0):
  89                     m.d.comb += [
  90                         self.data_hit.eq(0),
  91                         self.data_out.eq(self.entry_array[encoder.o].data)
  92                     ]
  93                 with m.Else():
  94                     m.d.comb += self.data_hit.eq(1)
  95             # NA
  96             with m.Case():
  97                 m.d.comb += self.data_hit.eq(0)
  98
  99         return m