src/TLB/Cam.py

   1 from nmigen import Array, Cat, Module, Signal, Elaboratable
   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
   8
   9 class Cam(Elaboratable):
  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: (bits) The bit size of the data
  35             * cam_size: (number) 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
  44         # Input
  45         self.enable = Signal(1)
  46         self.write_enable = Signal(1)
  47         self.data_in = Signal(data_size) # The data to be written
  48         self.data_mask = Signal(data_size) # mask for ternary writes
  49         self.address_in = Signal(max=cam_size) # address of CAM Entry to write
  50
  51         # Output
  52         self.read_warning = Signal(1) # High when a read interrupts a write
  53         self.single_match = Signal(1) # High when there is only one match
  54         self.multiple_match = Signal(1) # High when there at least two matches
  55         self.match_address = Signal(max=cam_size) # The lowest address matched
  56
  57     def elaborate(self, platform=None):
  58         m = Module()
  59         # AddressEncoder for match types and output address
  60         m.submodules.AddressEncoder = self.encoder
  61         # Decoder is used to select which entry will be written to
  62         m.submodules.Decoder = self.decoder
  63         # CamEntry Array Submodules
  64         # Note these area added anonymously
  65         entry_array = self.entry_array
  66         m.submodules += entry_array
  67
  68         # Decoder logic
  69         m.d.comb += [
  70             self.decoder.i.eq(self.address_in),
  71             self.decoder.n.eq(0)
  72         ]
  73
  74         encoder_vector = []
  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                 encoder_vector.append(ematch)
  95
  96             # Give input to and accept output from encoder module
  97             m.d.comb += [
  98                 self.encoder.i.eq(Cat(*encoder_vector)),
  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     def ports(self):
 116         return [self.enable, self.write_enable,
 117                      self.data_in, self.data_mask,
 118                      self.read_warning, self.single_match,
 119                      self.multiple_match, self.match_address]
 120
 121
 122 if __name__ == '__main__':
 123     cam = Cam(4, 4)
 124     main(cam, ports=cam.ports())
 125