from nmigen import Array, Module, Signal
-from nmigen.lib.coding import Encoder
-from nmigen.compat.fhdl.structure import ClockDomain
+from nmigen.lib.coding import Decoder
+from nmigen.cli import main #, verilog
from CamEntry import CamEntry
+from AddressEncoder import AddressEncoder
+from VectorAssembler import VectorAssembler
-# Content Addressable Memory (CAM)
-# The purpose of this module is to quickly look up whether an entry exists
-# given a certain key and return the mapped data.
-# This module when given a key will search for the given key
-# in all internal entries and output whether a match was found or not.
-# If an entry is found the data will be returned and data_hit is HIGH,
-# if it is not LOW is asserted on data_hit. When given a write
-# command it will write the given key and data into the given cam entry index.
-# Entry managment should be performed one level above this block as lookup is
-# performed within.
class Cam():
-
- # Arguments:
- # key_size: (bit count) The size of the key
- # data_size: (bit count) The size of the data
- # cam_size: (entry count) The number of entries int he CAM
- def __init__(self, key_size, data_size, cam_size):
+ """ Content Addressable Memory (CAM)
+
+ The purpose of this module is to quickly look up whether an
+ entry exists given a certain key and return the mapped data.
+ This module when given a key will search for the given key
+ in all internal entries and output whether a match was found or not.
+ If an entry is found the data will be returned and data_hit is HIGH,
+ if it is not LOW is asserted on data_hit. When given a write
+ command it will write the given key and data into the given cam
+ entry index.
+ Entry managment should be performed one level above this block
+ as lookup is performed within.
+
+ Notes:
+ The search, write, and reset operations take one clock cycle
+ to complete. Performing a read immediately after a search will cause
+ the read to be ignored.
+ """
+
+ def __init__(self, data_size, cam_size):
+ """ Arguments:
+ * data_size: (bit count) The size of the data
+ * cam_size: (entry count) The number of entries int he CAM
+ """
+
# Internal
- self.clk = ClockDomain(reset_less=True)
- self.key_size = key_size
- self.data_size = data_size
self.cam_size = cam_size
- self.entry_array = Array(CamEntry(key_size, data_size) \
+ self.encoder = AddressEncoder(cam_size)
+ self.decoder = Decoder(cam_size)
+ self.entry_array = Array(CamEntry(data_size) \
for x in range(cam_size))
- self.encoder_input = Signal(cam_size)
+ self.vector_assembler = VectorAssembler(cam_size)
# Input
- self.command = Signal(2) # 00 => NA 01 => Read 10 => Write 11 => Search
- self.address = Signal(max=cam_size) # address of CAM Entry to write/read
- self.key_in = Signal(key_size) # The key to search for or to be written
- self.data_in = Signal(key_size) # The data to be written
+ self.enable = Signal(1)
+ self.write_enable = Signal(1)
+ self.data_in = Signal(data_size) # The data to be written
+ self.data_mask = Signal(data_size) # mask for ternary writes
+ self.address_in = Signal(max=cam_size) # address of CAM Entry to write
# Output
- self.data_hit = Signal(1) # Denotes a key data pair was stored at key_in
- self.data_out = Signal(data_size) # The data mapped to by key_in
+ self.read_warning = Signal(1) # High when a read interrupts a write
+ self.single_match = Signal(1) # High when there is only one match
+ self.multiple_match = Signal(1) # High when there at least two matches
+ self.match_address = Signal(max=cam_size) # The lowest address matched
def elaborate(self, platform=None):
m = Module()
-
- m.submodules.encoder = encoder = Encoder(self.cam_size)
- m.submodules += self.entry_array
-
- # Set the key value for every CamEntry
- for index in range(self.cam_size):
- with m.Switch(self.command):
- # Read and Search both read from the CamEntry
- with m.Case("-1"):
- m.d.comb += self.entry_array[index].command.eq(1)
- # Write only to one entry
- with m.Case("10"):
- with m.If(self.address == index):
- m.d.comb += self.entry_array[index].command.eq(2)
+ # Encoder checks for multiple matches
+ m.submodules.AddressEncoder = self.encoder
+ # Decoder is used to select which entry will be written to
+ m.submodules.Decoder = self.decoder
+ # Don't forget to add all entries to the submodule list
+ entry_array = self.entry_array
+ m.submodules += entry_array
+ m.submodules.VectorAssembler = self.vector_assembler
+
+ # Decoder logic
+ m.d.comb += [
+ self.decoder.i.eq(self.address_in),
+ self.decoder.n.eq(0)
+ ]
+
+ with m.If(self.enable):
+ # Set the key value for every CamEntry
+ for index in range(self.cam_size):
+
+ # Read Operation
+ with m.If(~self.write_enable):
+ m.d.comb += entry_array[index].command.eq(1)
+
+ # Write Operation
+ with m.Else():
+ with m.If(self.decoder.o[index]):
+ m.d.comb += entry_array[index].command.eq(2)
with m.Else():
- m.d.comb += self.entry_array[index].command.eq(0)
- # NA
- with m.Case():
- m.d.comb += self.entry_array[index].command.eq(0)
-
+ m.d.comb += entry_array[index].command.eq(0)
+
+ # Send data input to all entries
+ m.d.comb += entry_array[index].data_in.eq(self.data_in)
+ #Send all entry matches to encoder
+ m.d.comb += self.vector_assembler.input[index].eq(entry_array[index].match)
+
+ # Give input to and accept output from encoder module
m.d.comb += [
- self.entry_array[index].key_in.eq(self.key_in),
- self.entry_array[index].data_in.eq(self.data_in),
- self.encoder_input[index].eq(self.entry_array[index].match)
+ self.encoder.i.eq(self.vector_assembler.o),
+ self.single_match.eq(self.encoder.single_match),
+ self.multiple_match.eq(self.encoder.multiple_match),
+ self.match_address.eq(self.encoder.o)
]
-
- with m.Switch(self.command):
- # Read
- with m.Case("01"):
- m.d.comb += [
- self.data_hit.eq(0),
- self.data_out.eq(self.entry_array[self.address].data)
- ]
- # Write
- with m.Case("10"):
- m.d.comb += [
- self.data_hit.eq(0),
- self.entry_array[self.address].key_in.eq(self.key_in),
- self.entry_array[self.address].data_in.eq(self.data_in)
- ]
- # Search
- with m.Case("11"):
- m.d.comb += encoder.i.eq(self.encoder_input)
- with m.If(encoder.n == 0):
- m.d.comb += [
- self.data_hit.eq(0),
- self.data_out.eq(self.entry_array[encoder.o].data)
- ]
- with m.Else():
- m.d.comb += self.data_hit.eq(1)
- # NA
- with m.Case():
- m.d.comb += self.data_hit.eq(0)
-
+
+ # If the CAM is not enabled set all outputs to 0
+ with m.Else():
+ m.d.comb += [
+ self.read_warning.eq(0),
+ self.single_match.eq(0),
+ self.multiple_match.eq(0),
+ self.match_address.eq(0)
+ ]
+
return m
+
+if __name__ == '__main__':
+ cam = Cam(4, 4)
+ main(cam, ports=[cam.enable, cam.write_enable,
+ cam.data_in, cam.data_mask,
+ cam.read_warning, cam.single_match,
+ cam.multiple_match, cam.match_address])
+