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         # CamEntry Array Submodules
  65         # Note these area added anonymously
  66         entry_array = self.entry_array
  67         m.submodules += entry_array
  68         # VectorAssembler Submodule
  69         m.submodules.VectorAssembler = self.vector_assembler
  70
  71         # Decoder logic
  72         m.d.comb += [
  73             self.decoder.i.eq(self.address_in),
  74             self.decoder.n.eq(0)
  75         ]
  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                 # Write Operation
  82                 with m.If(self.write_enable):
  83                     with m.If(self.decoder.o[index]):
  84                         m.d.comb += entry_array[index].command.eq(2)
  85                     with m.Else():
  86                         m.d.comb += entry_array[index].command.eq(0)
  87
  88                 # Read Operation
  89                 with m.Else():
  90                     m.d.comb += entry_array[index].command.eq(1)
  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