src/TLB/Cam.py

   1 from nmigen import Array, Cat, Module, Signal
   2 from nmigen.lib.coding import Decoder
   3 from nmigen.cli import main #, verilog
   4
   5 from CamEntry import CamEntry
   6 from AddressEncoder import AddressEncoder
   7
   8 class Cam():
   9     """ Content Addressable Memory (CAM)
  10
  11         The purpose of this module is to quickly look up whether an
  12         entry exists given a data key.
  13         This module will search for the given data in all internal entries
  14         and output whether a  single or multiple match was found.
  15         If an single entry is found the address be returned and single_match
  16         is set HIGH. If multiple entries are found the lowest address is
  17         returned and multiple_match is set HIGH. If neither single_match or
  18         multiple_match are HIGH this implies no match was found. To write
  19         to the CAM set the address bus to the desired entry and set write_enable
  20         HIGH. Entry managment should be performed one level above this block
  21         as lookup is performed within.
  22
  23         Notes:
  24         The read and write operations take one clock cycle to complete.
  25         Currently the read_warning line is present for interfacing but
  26         is not necessary for this design. This module is capable of writing
  27         in the first cycle, reading on the second, and output the correct
  28         address on the third.
  29     """
  30
  31     def __init__(self, data_size, cam_size):
  32         """ Arguments:
  33             * data_size: (bits) The bit size of the data
  34             * cam_size: (number) The number of entries in the CAM
  35         """
  36
  37         # Internal
  38         self.cam_size = cam_size
  39         self.encoder = AddressEncoder(cam_size)
  40         self.decoder = Decoder(cam_size)
  41         self.entry_array = Array(CamEntry(data_size) for x in range(cam_size))
  42
  43         # Input
  44         self.enable = Signal(1)
  45         self.write_enable = Signal(1)
  46         self.data_in = Signal(data_size) # The data to be written
  47         self.data_mask = Signal(data_size) # mask for ternary writes
  48         self.address_in = Signal(max=cam_size) # address of CAM Entry to write
  49
  50         # Output
  51         self.read_warning = Signal(1) # High when a read interrupts a write
  52         self.single_match = Signal(1) # High when there is only one match
  53         self.multiple_match = Signal(1) # High when there at least two matches
  54         self.match_address = Signal(max=cam_size) # The lowest address matched
  55
  56     def elaborate(self, platform=None):
  57         m = Module()
  58         # AddressEncoder for match types and output address
  59         m.submodules.AddressEncoder = self.encoder
  60         # Decoder is used to select which entry will be written to
  61         m.submodules.Decoder = self.decoder
  62         # CamEntry Array Submodules
  63         # Note these area added anonymously
  64         entry_array = self.entry_array
  65         m.submodules += entry_array
  66
  67         # Decoder logic
  68         m.d.comb += [
  69             self.decoder.i.eq(self.address_in),
  70             self.decoder.n.eq(0)
  71         ]
  72
  73         encoder_vector = []
  74         with m.If(self.enable):
  75             # Set the key value for every CamEntry
  76             for index in range(self.cam_size):
  77
  78                 # Write Operation
  79                 with m.If(self.write_enable):
  80                     with m.If(self.decoder.o[index]):
  81                         m.d.comb += entry_array[index].command.eq(2)
  82                     with m.Else():
  83                         m.d.comb += entry_array[index].command.eq(0)
  84
  85                 # Read Operation
  86                 with m.Else():
  87                     m.d.comb += entry_array[index].command.eq(1)
  88
  89                 # Send data input to all entries
  90                 m.d.comb += entry_array[index].data_in.eq(self.data_in)
  91                 # Send all entry matches to encoder
  92                 ematch = entry_array[index].match
  93                 encoder_vector.append(ematch)
  94
  95             # Give input to and accept output from encoder module
  96             m.d.comb += [
  97                 self.encoder.i.eq(Cat(*encoder_vector)),
  98                 self.single_match.eq(self.encoder.single_match),
  99                 self.multiple_match.eq(self.encoder.multiple_match),
 100                 self.match_address.eq(self.encoder.o)
 101             ]
 102
 103         # If the CAM is not enabled set all outputs to 0
 104         with m.Else():
 105             m.d.comb += [
 106                     self.read_warning.eq(0),
 107                     self.single_match.eq(0),
 108                     self.multiple_match.eq(0),
 109                     self.match_address.eq(0)
 110             ]
 111
 112         return m
 113
 114     def ports(self):
 115         return [self.enable, self.write_enable,
 116                      self.data_in, self.data_mask,
 117                      self.read_warning, self.single_match,
 118                      self.multiple_match, self.match_address]
 119
 120
 121 if __name__ == '__main__':
 122     cam = Cam(4, 4)
 123     main(cam, ports=cam.ports())
 124