TLB/src/Cam.py

   1 from nmigen import Array, Module, Signal
   2 from nmigen.lib.coding import Encoder, 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 = Encoder(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         # 000 => NA 001 => Read 010 => Write 011 => Search
  42         # 100 => Reset 101, 110, 111 => Reserved
  43         self.command = Signal(3)
  44         self.enable = Signal(1)
  45         self.data_in = Signal(data_size) # The data to be written
  46         self.data_mask = Signal(data_size) # mask for ternary writes
  47         self.write_enable = Signal(1) # write
  48         self.address = Signal(max=cam_size) # address of CAM Entry to write/read
  49
  50         # Output
  51         self.data_hit = Signal(1) # Denotes a key data pair was stored at key_in
  52         self.data_out = Signal(data_size) # The data mapped to by key_in
  53
  54     def elaborate(self, platform=None):
  55         m = Module()
  56         # Encoder is used to selecting what data is output when searching
  57         m.submodules += self.encoder
  58         # Decoder is used to select which entry will be written to
  59         m.submodules += self.decoder
  60         # Don't forget to add all entries to the submodule list
  61         entry_array = self.entry_array
  62         m.submodules += entry_array
  63
  64         # Decoder logic
  65         m.d.comb += [
  66             self.decoder.i.eq(self.address),
  67             self.decoder.n.eq(0)
  68         ]
  69
  70         # Set the key value for every CamEntry
  71         for index in range(self.cam_size):
  72             with m.Switch(self.command):
  73                 # Read from a single entry
  74                 with m.Case("0-1"):
  75                     m.d.comb += entry_array[index].command.eq(1)
  76                     # Only read if an encoder value is not ready
  77                     with m.If(self.decoder.o[index] & self.encoder.n):
  78                         m.d.comb += self.data_out.eq(entry_array[index].data)
  79                 # Write only to one entry
  80                 with m.Case("010"):
  81                     # Address is decoded and selects which
  82                     # entry will be written to
  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                 # Search all entries
  88                 with m.Case("011"):
  89                     m.d.comb += entry_array[index].command.eq(1)
  90                 # Reset
  91                 with m.Case("100"):
  92                     m.d.comb += entry_array[index].command.eq(3)
  93                 # NA / Reserved
  94                 with m.Case():
  95                     m.d.comb += entry_array[index].command.eq(0)
  96
  97             m.d.comb += [
  98                    entry_array[index].data_in.eq(self.data_in),
  99                    self.encoder.i[index].eq(entry_array[index].match)
 100             ]
 101
 102         # Process out data based on encoder address
 103         with m.If(self.encoder.n == 0):
 104             m.d.comb += [
 105                 self.data_hit.eq(1),
 106                 self.data_out.eq(entry_array[self.encoder.o].data)
 107             ]
 108         with m.Else():
 109             m.d.comb += self.data_hit.eq(0)
 110
 111         return m
 112
 113 if __name__ == '__main__':
 114     cam = Cam(4, 4)
 115     main(cam, ports=[cam.command, cam.address,
 116                      cam.data_in, cam.data_hit,
 117                      cam.data_out])
 118