TLB/src/Cam.py

   1 from nmigen import Array, Module, Signal
   2 from nmigen.lib.coding import Decoder, Encoder, PriorityEncoder
   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         # TODO create a module that merges the priority encoder and
  36         # encoder into one?
  37         self.encoder = Encoder(cam_size)
  38         self.p_encoder = PriorityEncoder(cam_size)
  39         self.decoder = Decoder(cam_size)
  40         self.entry_array = Array(CamEntry(data_size) \
  41                             for x in range(cam_size))
  42
  43         # Input
  44         self.enable = Signal(1)
  45         self.write_enable = Signal(1)
  46         self.data_in = Signal(data_size) # The data to be written
  47         self.data_mask = Signal(data_size) # mask for ternary writes
  48         self.address_in = Signal(max=cam_size) # address of CAM Entry to write
  49
  50         # Output
  51         self.read_warning = Signal(1) # High when a read interrupts a write
  52         self.single_match = Signal(1) # High when there is only one match
  53         self.multiple_match = Signal(1) # High when there at least two matches
  54         self.match_address = Signal(max=cam_size) # The lowest address matched
  55
  56     def elaborate(self, platform=None):
  57         m = Module()
  58         # Encoder checks for multiple matches
  59         m.submodules.encoder = self.encoder
  60         # Priority Encoder is used to select output address
  61         m.submodules.p_encoder = self.p_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
  68         # Decoder logic
  69         m.d.comb += [
  70             self.decoder.i.eq(self.address_in),
  71             self.decoder.n.eq(0)
  72         ]
  73
  74         with m.If(self.enable):
  75             # Set the key value for every CamEntry
  76             for index in range(self.cam_size):
  77
  78                 # Read Operation
  79                 with m.If(~self.write_enable):
  80                     m.d.comb += entry_array[index].command.eq(1)
  81
  82                 # Write Operation
  83                 with m.Else():
  84                     with m.If(self.decoder.o[index]):
  85                         m.d.comb += entry_array[index].command.eq(2)
  86                     with m.Else():
  87                         m.d.comb += entry_array[index].command.eq(0)
  88
  89                 # Send data input to all entries
  90                 m.d.comb += entry_array[index].data_in.eq(self.data_in)
  91                 #Send all entry matches to encoder
  92                 m.d.comb += self.encoder.i[index].eq(entry_array[index].match)
  93                 # Send all entry matches to the priority encoder
  94                 m.d.comb += self.p_encoder.i[index].eq(entry_array[index].match)
  95
  96             # If the priority encoder recieves an input of 0
  97             # If n is 1 then the output is not valid
  98             with m.If(self.p_encoder.n):
  99                 m.d.comb += [
 100                     self.read_warning.eq(0),
 101                     self.single_match.eq(0),
 102                     self.multiple_match.eq(0),
 103                     self.match_address.eq(0)
 104                 ]
 105             # If the priority encoder recieves an input > 0
 106             with m.Else():
 107                 # Multiple Match if encoder n is invalid
 108                 with m.If(self.encoder.n):
 109                     m.d.comb += [
 110                         self.single_match.eq(0),
 111                         self.multiple_match.eq(1)
 112                     ]
 113                 # Single Match if encoder n is valid
 114                 with m.Else():
 115                     m.d.comb += [
 116                         self.single_match.eq(1),
 117                         self.multiple_match.eq(0)
 118                     ]
 119                 # Always set output based on priority encoder output
 120                 m.d.comb += self.match_address.eq(self.p_encoder.o)
 121
 122         # If the CAM is not enabled set all outputs to 0
 123         with m.Else():
 124             m.d.comb += [
 125                     self.read_warning.eq(0),
 126                     self.single_match.eq(0),
 127                     self.multiple_match.eq(0),
 128                     self.match_address.eq(0)
 129             ]
 130
 131         return m
 132
 133 if __name__ == '__main__':
 134     cam = Cam(4, 4)
 135     main(cam, ports=[cam.enable, cam.write_enable,
 136                      cam.data_in, cam.data_mask,
 137                      cam.read_warning, cam.single_match,
 138                      cam.multiple_match, cam.match_address])
 139