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         # XXX change name of write_enable interface to write_enable_n ?
  74         wen = Signal(reset_less=True)
  75         m.d.comb += wen.eq(~self.write_enable)
  76
  77         with m.If(self.enable):
  78             # Set the key value for every CamEntry
  79             for index in range(self.cam_size):
  80
  81                 # Read Operation
  82                 with m.If(wen):
  83                     m.d.comb += entry_array[index].command.eq(1)
  84
  85                 # Write Operation
  86                 with m.Else():
  87                     with m.If(self.decoder.o[index]):
  88                         m.d.comb += entry_array[index].command.eq(2)
  89                     with m.Else():
  90                         m.d.comb += entry_array[index].command.eq(0)
  91
  92                 # Send data input to all entries
  93                 m.d.comb += entry_array[index].data_in.eq(self.data_in)
  94                 # Send all entry matches to encoder
  95                 ematch = entry_array[index].match
  96                 m.d.comb += self.vector_assembler.i[index].eq(ematch)
  97
  98             # Give input to and accept output from encoder module
  99             m.d.comb += [
 100                 self.encoder.i.eq(self.vector_assembler.o),
 101                 self.single_match.eq(self.encoder.single_match),
 102                 self.multiple_match.eq(self.encoder.multiple_match),
 103                 self.match_address.eq(self.encoder.o)
 104             ]
 105
 106         # If the CAM is not enabled set all outputs to 0
 107         with m.Else():
 108             m.d.comb += [
 109                     self.read_warning.eq(0),
 110                     self.single_match.eq(0),
 111                     self.multiple_match.eq(0),
 112                     self.match_address.eq(0)
 113             ]
 114
 115         return m
 116
 117 if __name__ == '__main__':
 118     cam = Cam(4, 4)
 119     main(cam, ports=[cam.enable, cam.write_enable,
 120                      cam.data_in, cam.data_mask,
 121                      cam.read_warning, cam.single_match,
 122                      cam.multiple_match, cam.match_address])
 123