TLB/src/Cam.py

   1 from nmigen import Array, Module, Signal
   2 from nmigen.lib.coding import PriorityEncoder, Decoder
   3 from nmigen.cli import main #, verilog
   4
   5 from CamEntry import CamEntry
   6
   7 class Cam():
   8     """ Content Addressable Memory (CAM)
   9
  10         The purpose of this module is to quickly look up whether an
  11         entry exists given a certain key and return the mapped data.
  12         This module when given a key will search for the given key
  13         in all internal entries and output whether a match was found or not.
  14         If an entry is found the data will be returned and data_hit is HIGH,
  15         if it is not LOW is asserted on data_hit. When given a write
  16         command it will write the given key and data into the given cam
  17         entry index.
  18         Entry managment should be performed one level above this block
  19         as lookup is performed within.
  20
  21         Notes:
  22         The search, write, and reset operations take one clock cycle
  23         to complete.  Performing a read immediately after a search will cause
  24         the read to be ignored.
  25     """
  26
  27     def __init__(self, data_size, cam_size):
  28         """ Arguments:
  29             * data_size: (bit count) The size of the data
  30             * cam_size: (entry count) The number of entries int he CAM
  31         """
  32
  33         # Internal
  34         self.cam_size = cam_size
  35         self.encoder = PriorityEncoder(cam_size)
  36         self.decoder = Decoder(cam_size)
  37         self.entry_array = Array(CamEntry(data_size) \
  38                             for x in range(cam_size))
  39
  40         # Input
  41         self.enable = Signal(1)
  42         self.write_enable = Signal(1)
  43         self.data_in = Signal(data_size) # The data to be written
  44         self.data_mask = Signal(data_size) # mask for ternary writes
  45         self.address_in = Signal(max=cam_size) # address of CAM Entry to write
  46
  47         # Output
  48         self.read_warning = Signal(1) # High when a read interrupts a write
  49         self.single_match = Signal(1) # High when there is only one match
  50         self.multiple_match = Signal(1) # High when there at least two matches
  51         self.match_address = Signal(max=cam_size) # The lowest address matched
  52
  53     def elaborate(self, platform=None):
  54         m = Module()
  55         # Encoder is used to selecting what data is output when searching
  56         m.submodules += self.encoder
  57         # Decoder is used to select which entry will be written to
  58         m.submodules += self.decoder
  59         # Don't forget to add all entries to the submodule list
  60         entry_array = self.entry_array
  61         m.submodules += entry_array
  62
  63         # Decoder logic
  64         m.d.comb += [
  65             self.decoder.i.eq(self.address_in),
  66             self.decoder.n.eq(0)
  67         ]
  68
  69         # Set the key value for every CamEntry
  70         for index in range(self.cam_size):
  71             with m.If(self.enable):
  72
  73                 # Read Operation
  74                 with m.If(~self.write_enable):
  75                     m.d.comb += entry_array[index].command.eq(1)
  76
  77                 # Write Operation
  78                 with m.Else():
  79                     with m.If(self.decoder.o[index]):
  80                         m.d.comb += entry_array[index].command.eq(2)
  81                     with m.Else():
  82                         m.d.comb += entry_array[index].command.eq(0)
  83
  84                 # Send data input to all entries
  85                 m.d.comb += entry_array[index].data_in.eq(self.data_in)
  86                 # Send all entry matches to the priority encoder
  87                 m.d.comb += self.encoder.i[index].eq(entry_array[index].match)
  88
  89                 # Process out data based on encoder address
  90                 with m.If(self.encoder.n):
  91                     m.d.comb += [
  92                         self.read_warning.eq(0),
  93                         self.single_match.eq(0),
  94                         self.multiple_match.eq(0),
  95                         self.match_address.eq(0)
  96                     ]
  97                 with m.Else():
  98                     m.d.comb += [
  99                         self.single_match.eq(1),
 100                         self.match_address.eq(self.encoder.o)
 101                     ]
 102
 103             with m.Else():
 104                 m.d.comb += [
 105                         self.read_warning.eq(0),
 106                         self.single_match.eq(0),
 107                         self.multiple_match.eq(0),
 108                         self.match_address.eq(0)
 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