TLB/src/Cam.py

   1 from nmigen import Array, 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 from VectorAssembler import VectorAssembler
   8
   9 class Cam():
  10     """ Content Addressable Memory (CAM)
  11
  12         The purpose of this module is to quickly look up whether an
  13         entry exists given a certain key and return the mapped data.
  14         This module when given a key will search for the given key
  15         in all internal entries and output whether a match was found or not.
  16         If an entry is found the data will be returned and data_hit is HIGH,
  17         if it is not LOW is asserted on data_hit. When given a write
  18         command it will write the given key and data into the given cam
  19         entry index.
  20         Entry managment should be performed one level above this block
  21         as lookup is performed within.
  22
  23         Notes:
  24         The search, write, and reset operations take one clock cycle
  25         to complete.  Performing a read immediately after a search will cause
  26         the read to be ignored.
  27     """
  28
  29     def __init__(self, data_size, cam_size):
  30         """ Arguments:
  31             * data_size: (bit count) The size of the data
  32             * cam_size: (entry count) The number of entries int he CAM
  33         """
  34
  35         # Internal
  36         self.cam_size = cam_size
  37         self.encoder = AddressEncoder(cam_size)
  38         self.decoder = Decoder(cam_size)
  39         self.entry_array = Array(CamEntry(data_size) \
  40                             for x in range(cam_size))
  41         self.vector_assembler = VectorAssembler(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         # Encoder checks for multiple matches
  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         # Don't forget to add all entries to the submodule list
  63         entry_array = self.entry_array
  64         m.submodules += entry_array
  65         m.submodules.VectorAssembler = self.vector_assembler
  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         with m.If(self.enable):
  74             # Set the key value for every CamEntry
  75             for index in range(self.cam_size):
  76
  77                 # Write Operation
  78                 with m.If(self.write_enable):
  79                     with m.If(self.decoder.o[index]):
  80                         m.d.comb += entry_array[index].command.eq(2)
  81                     with m.Else():
  82                         m.d.comb += entry_array[index].command.eq(0)
  83
  84                 # Read Operation
  85                 with m.Else():
  86                     m.d.comb += entry_array[index].command.eq(1)
  87
  88                 # Send data input to all entries
  89                 m.d.comb += entry_array[index].data_in.eq(self.data_in)
  90                 # Send all entry matches to encoder
  91                 ematch = entry_array[index].match
  92                 m.d.comb += self.vector_assembler.i[index].eq(ematch)
  93
  94             # Give input to and accept output from encoder module
  95             m.d.comb += [
  96                 self.encoder.i.eq(self.vector_assembler.o),
  97                 self.single_match.eq(self.encoder.single_match),
  98                 self.multiple_match.eq(self.encoder.multiple_match),
  99                 self.match_address.eq(self.encoder.o)
 100             ]
 101
 102         # If the CAM is not enabled set all outputs to 0
 103         with m.Else():
 104             m.d.comb += [
 105                     self.read_warning.eq(0),
 106                     self.single_match.eq(0),
 107                     self.multiple_match.eq(0),
 108                     self.match_address.eq(0)
 109             ]
 110
 111         return m
 112
 113 if __name__ == '__main__':
 114     cam = Cam(4, 4)
 115     main(cam, ports=[cam.enable, cam.write_enable,
 116                      cam.data_in, cam.data_mask,
 117                      cam.read_warning, cam.single_match,
 118                      cam.multiple_match, cam.match_address])
 119