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