Method and system for reconfigurable parallel lookups using multiple shared memories

Patent metadata

Field	Value
Publication number	US-12323145-B2
Application number	US-202217874544-A
Country	US
Kind code	B2
Filing date	Jul 27, 2022
Priority date	Dec 27, 2013
Publication date	Jun 3, 2025
Grant date	Jun 3, 2025

Abstract

Embodiments of the present invention relate to multiple parallel lookups using a pool of shared memories by proper configuration of interconnection networks. The number of shared memories reserved for each lookup is reconfigurable based on the memory capacity needed by that lookup. The shared memories are grouped into homogeneous tiles. Each lookup is allocated a set of tiles based on the memory capacity needed by that lookup. The tiles allocated for each lookup do not overlap with other lookups such that all lookups can be performed in parallel without collision. Each lookup is reconfigurable to be either hash-based or direct-access. The interconnection networks are programed based on how the tiles are allocated for each lookup.

First claim

We claim:

1. A tile device comprising:
M memories that each have a unique memory identifier (Mem ID), wherein each of the M memories include 2 m entries, wherein each of the entries contains P pairs, each of the P pairs comprising a pre-programmed key and pre-programmed data; and
a matching and selection logic configured to receive an input key and output a lookup result, where M is a positive integer value greater than 1, and m and P are positive integer values.

2. The tile device of claim 1 , wherein a lookup result includes a lowest Mem ID and memory address where the pre-programmed data is stored.

3. The tile device of claim 1 , wherein a lookup result is forwarded to an output reconfiguration interconnection fabric, wherein the output reconfiguration interconnection fabric is configured to connect each of T tiles to one of N final output selection devices for N lookup paths, where T and N are positive integer values.

4. A tile device comprising:
M memories that each have a memory identifier (Mem ID), wherein each of the M memories include 2 m entries, wherein each of the entries contains P pairs, each of the P pairs comprising a pre-programmed key and pre-programmed data; and
a matching and selection logic configured to receive an input key and output a lookup result, where M is a positive integer value greater than 1, and m and P are positive integer values, wherein each of the N final output selection devices comprise:
a collecting block configured to receive lookup results from all of the tiles that reserved a respective lookup path; and
a selection block configured to select one final lookup result from all of the lookup results collected by the collecting block, wherein the selected final lookup result is from a hit tile having a lowest tile identifier (Tile ID).

5. The tile device of claim 4 , wherein the selected final lookup result includes hit data, a tile identifier (Tile ID), one of the Mem IDs and a memory address where the hit data is stored.

6. The tile device of claim 4 , wherein the selected final lookup result is based on key matching results between pre-programmed keys in the memories and the input key.

7. A tile device comprising:
a matching and selection logic configured to receive an input key and output a lookup result, wherein the matching and selection logic includes:
a matching block configured to determine whether the input key matches any of one or more programmable keys in M memories, the M memories each having a memory identifier (Mem ID); and
a selection block configured to select a memory from those memories of the M memories that contain programmable keys matching the input key, wherein the selection block selects the memory based on the Mem IDs of those memories of the M memories that contain programmable keys matching the input key, where M is a positive integer value greater than 1.

8. The tile device of claim 7 , wherein the lookup result comprises pre-programmed data, the Mem ID of the selected memory and memory address where the pre-programmed data is stored.

9. The tile device of claim 7 , wherein the lookup result is forwarded to an output reconfiguration interconnection fabric, wherein the output reconfiguration interconnection fabric is configured to connect a tile device to one of N final output selection devices for N lookup paths, where N is a positive integer value.

10. The tile device of claim 9 , wherein each of the N final output selection devices comprises:
a collecting block configured to receive lookup results from all tiles that reserved that a respective lookup path; and
a selection block configured to select one final lookup result from all of the lookup results collected by the collecting block, wherein the selected final lookup result is from a tile of the tiles having a lowest tile identifier (Tile ID).

11. The tile device of claim 10 , wherein the selected final lookup result includes hit data, a tile identifier (Tile ID), one of the Mem IDs and a memory address where the hit data is stored.

12. The tile device of claim 10 , wherein the selected final lookup result is based on key matching results between programmable keys in the memories and the input key.

13. The tile device of claim 7 , wherein each of the M memories include a plurality of entries.

14. The tile device of claim 7 , wherein each of the entries comprise programmable data.

15. A tile device comprising:
M memories that each have a plurality of entries, wherein each of the entries has a pre-programmed key; and
a matching and selection logic configured to receive an input key and output a lookup result, wherein the lookup result is forwarded to an output reconfiguration interconnection fabric that is configured to connect a tile device to one of N final output selection devices for N lookup paths, wherein each of the N final output selection devices comprises:
a collecting block configured to receive lookup results from all tiles that reserved a respective lookup path; and
a selection block configured to select one final lookup result from all of the lookup results collected by the collecting block, wherein the selected final lookup result is from a tile of the tiles having a lowest tile identifier (Tile ID), where Nis a positive integer value.

16. The tile device of claim 15 , wherein the lookup result further comprises a lowest Mem ID and memory address where pre-programmed data of the plurality of entries is stored.

17. The tile device of claim 15 , wherein the selected final lookup result includes hit data, a Tile ID and a memory address where the hit data is stored.

18. The tile device of claim 15 , wherein the selected final lookup result is based on key matching results between the pre-programmed keys in the memories and the input key.

Assignees

• Marvell Asia Pte Ltd

Inventors

• Tran Anh T
• Schmidt Gerald
• Daniel Tsahi
• Shrivastava Saurabh

Classifications

• G06F3/0683

  Plurality of storage devices · CPC title

• G06F3/0644

  Management of space entities, e.g. partitions, extents, pools · CPC title

• G06F3/061

  Improving I/O performance · CPC title

• H04L45/745

  Address table lookup; Address filtering · CPC title

• H04L45/7452

  Multiple parallel or consecutive lookup operations (lookup operation involving Bloom filters H04L45/7459) · CPC title