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 data key.
  14         This module will search for the given data in all internal entries
  15         and output whether a  single or multiple match was found.
  16         If an single entry is found the address be returned and single_match
  17         is set HIGH. If multiple entries are found the lowest address is
  18         returned and multiple_match is set HIGH. If neither single_match or
  19         multiple_match are HIGH this implies no match was found. To write
  20         to the CAM set the address bus to the desired entry and set write_enable
  21         HIGH. Entry managment should be performed one level above this block
  22         as lookup is performed within.
  23
  24         Notes:
  25         The read and write operations take one clock cycle to complete.
  26     """
  27
  28     def __init__(self, data_size, cam_size):
  29         """ Arguments:
  30             * data_size: (bit count) The size of the data
  31             * cam_size: (entry count) The number of entries int he CAM
  32         """
  33
  34         # Internal
  35         self.cam_size = cam_size
  36         self.encoder = AddressEncoder(cam_size)
  37         self.decoder = Decoder(cam_size)
  38         self.entry_array = Array(CamEntry(data_size) \
  39                             for x in range(cam_size))
  40         self.vector_assembler = VectorAssembler(cam_size)
  41
  42         # Input
  43         self.enable = Signal(1)
  44         self.write_enable = Signal(1)
  45         self.data_in = Signal(data_size) # The data to be written
  46         self.data_mask = Signal(data_size) # mask for ternary writes
  47         self.address_in = Signal(max=cam_size) # address of CAM Entry to write
  48
  49         # Output
  50         self.read_warning = Signal(1) # High when a read interrupts a write
  51         self.single_match = Signal(1) # High when there is only one match
  52         self.multiple_match = Signal(1) # High when there at least two matches
  53         self.match_address = Signal(max=cam_size) # The lowest address matched
  54
  55     def elaborate(self, platform=None):
  56         m = Module()
  57         # Encoder checks for multiple matches
  58         m.submodules.AddressEncoder = self.encoder
  59         # Decoder is used to select which entry will be written to
  60         m.submodules.Decoder = self.decoder
  61         # Don't forget to add all entries to the submodule list
  62         entry_array = self.entry_array
  63         m.submodules += entry_array
  64         m.submodules.VectorAssembler = self.vector_assembler
  65
  66         # Decoder logic
  67         m.d.comb += [
  68             self.decoder.i.eq(self.address_in),
  69             self.decoder.n.eq(0)
  70         ]
  71
  72         with m.If(self.enable):
  73             # Set the key value for every CamEntry
  74             for index in range(self.cam_size):
  75
  76                 # Write Operation
  77                 with m.If(self.write_enable):
  78                     with m.If(self.decoder.o[index]):
  79                         m.d.comb += entry_array[index].command.eq(2)
  80                     with m.Else():
  81                         m.d.comb += entry_array[index].command.eq(0)
  82
  83                 # Read Operation
  84                 with m.Else():
  85                     m.d.comb += entry_array[index].command.eq(1)
  86
  87                 # Send data input to all entries
  88                 m.d.comb += entry_array[index].data_in.eq(self.data_in)
  89                 # Send all entry matches to encoder
  90                 ematch = entry_array[index].match
  91                 m.d.comb += self.vector_assembler.i[index].eq(ematch)
  92
  93             # Give input to and accept output from encoder module
  94             m.d.comb += [
  95                 self.encoder.i.eq(self.vector_assembler.o),
  96                 self.single_match.eq(self.encoder.single_match),
  97                 self.multiple_match.eq(self.encoder.multiple_match),
  98                 self.match_address.eq(self.encoder.o)
  99             ]
 100
 101         # If the CAM is not enabled set all outputs to 0
 102         with m.Else():
 103             m.d.comb += [
 104                     self.read_warning.eq(0),
 105                     self.single_match.eq(0),
 106                     self.multiple_match.eq(0),
 107                     self.match_address.eq(0)
 108             ]
 109
 110         return m
 111
 112 if __name__ == '__main__':
 113     cam = Cam(4, 4)
 114     main(cam, ports=[cam.enable, cam.write_enable,
 115                      cam.data_in, cam.data_mask,
 116                      cam.read_warning, cam.single_match,
 117                      cam.multiple_match, cam.match_address])
 118