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         Currently the read_warning line is present for interfacing but
  27         is not necessary for this design. This module is capable of writing
  28         in the first cycle, reading on the second, and output the correct
  29         address on the third.
  30     """
  31
  32     def __init__(self, data_size, cam_size):
  33         """ Arguments:
  34             * data_size: (bit count) The size of the data
  35             * cam_size: (entry count) The number of entries in the CAM
  36         """
  37
  38         # Internal
  39         self.cam_size = cam_size
  40         self.encoder = AddressEncoder(cam_size)
  41         self.decoder = Decoder(cam_size)
  42         self.entry_array = Array(CamEntry(data_size) for x in range(cam_size))
  43         self.vector_assembler = VectorAssembler(cam_size)
  44
  45         # Input
  46         self.enable = Signal(1)
  47         self.write_enable = Signal(1)
  48         self.data_in = Signal(data_size) # The data to be written
  49         self.data_mask = Signal(data_size) # mask for ternary writes
  50         self.address_in = Signal(max=cam_size) # address of CAM Entry to write
  51
  52         # Output
  53         self.read_warning = Signal(1) # High when a read interrupts a write
  54         self.single_match = Signal(1) # High when there is only one match
  55         self.multiple_match = Signal(1) # High when there at least two matches
  56         self.match_address = Signal(max=cam_size) # The lowest address matched
  57
  58     def elaborate(self, platform=None):
  59         m = Module()
  60         # AddressEncoder for match types and output address
  61         m.submodules.AddressEncoder = self.encoder
  62         # Decoder is used to select which entry will be written to
  63         m.submodules.Decoder = self.decoder
  64         # Don't forget to add all entries to the submodule list
  65         entry_array = self.entry_array
  66         m.submodules += entry_array
  67         m.submodules.VectorAssembler = self.vector_assembler
  68
  69         # Decoder logic
  70         m.d.comb += [
  71             self.decoder.i.eq(self.address_in),
  72             self.decoder.n.eq(0)
  73         ]
  74
  75         with m.If(self.enable):
  76             # Set the key value for every CamEntry
  77             for index in range(self.cam_size):
  78
  79                 # Write Operation
  80                 with m.If(self.write_enable):
  81                     with m.If(self.decoder.o[index]):
  82                         m.d.comb += entry_array[index].command.eq(2)
  83                     with m.Else():
  84                         m.d.comb += entry_array[index].command.eq(0)
  85
  86                 # Read Operation
  87                 with m.Else():
  88                     m.d.comb += entry_array[index].command.eq(1)
  89
  90                 # Send data input to all entries
  91                 m.d.comb += entry_array[index].data_in.eq(self.data_in)
  92                 # Send all entry matches to encoder
  93                 ematch = entry_array[index].match
  94                 m.d.comb += self.vector_assembler.i[index].eq(ematch)
  95
  96             # Give input to and accept output from encoder module
  97             m.d.comb += [
  98                 self.encoder.i.eq(self.vector_assembler.o),
  99                 self.single_match.eq(self.encoder.single_match),
 100                 self.multiple_match.eq(self.encoder.multiple_match),
 101                 self.match_address.eq(self.encoder.o)
 102             ]
 103
 104         # If the CAM is not enabled set all outputs to 0
 105         with m.Else():
 106             m.d.comb += [
 107                     self.read_warning.eq(0),
 108                     self.single_match.eq(0),
 109                     self.multiple_match.eq(0),
 110                     self.match_address.eq(0)
 111             ]
 112
 113         return m
 114
 115 if __name__ == '__main__':
 116     cam = Cam(4, 4)
 117     main(cam, ports=[cam.enable, cam.write_enable,
 118                      cam.data_in, cam.data_mask,
 119                      cam.read_warning, cam.single_match,
 120                      cam.multiple_match, cam.match_address])
 121