Method and system for reconfigurable parallel lookups using multiple shared memories

Patent metadata

Field	Value
Publication number	US-11435925-B2
Application number	US-202016996749-A
Country	US
Kind code	B2
Filing date	Aug 18, 2020
Priority date	Dec 27, 2013
Publication date	Sep 6, 2022
Grant date	Sep 6, 2022

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 converting device configured to support N parallel key-to-lookup indexes conversions, comprising:
N keys received at the converter, wherein each of the N keys is associated with a group of tiles from T tiles, wherein each of the T tiles includes M memories;
N×M lookup indexes to return from the converter after parallel conversions of the N keys to the N×M lookup indexes; and
N×M converters, wherein each of the N×M converters is configured to convert a key from the N keys to a lookup index from the N×M lookup indexes, wherein N, T and M are positive integer values.

2. The converting device of claim 1 , wherein the N×M lookup indexes are forwarded to a central reconfiguration interconnection fabric, wherein the central reconfiguration interconnection fabric is configured to connect each of the N×M lookup indexes to one of T tiles for comparing the key with pre-programmed keys stored in that tile.

3. The converting device of claim 1 , wherein each of the N×M converters comprise a log 2 (T)+1 hash functions and log 2 (T)+1 non-hash functions.

4. The converting device of claim 3 , wherein outputs of the functions have bitwidths ranging from m bits to log 2 (T)+m bits, wherein m is a positive integer value.

5. The converting device of claim 4 , wherein each of the N×M converters comprise a first configurable register for selecting one of the functions.

6. The converting device of claim 5 , wherein each of the N×M converters comprise a second configurable register for selecting a tile offset such that the lookup index points to a correct tile from the group of tiles associated with the key.

7. The converting device of claim 6 , wherein each lookup path of N lookup paths is associated with M converters of the N×M converters.

8. The converting device of claim 7 , wherein converter i of the M converters of each lookup path of N lookup paths is used to access memory i in one of the T tiles allocated for that lookup path.

9. The converting device of claim 8 , wherein each of M index converters of each lookup path of the N lookup paths is configurable based on a number of tiles allocated for that lookup path of the N lookup paths.

10. The converting device of claim 9 , wherein each of the N×M converters comprise an output index having log 2 (T)+m bits.

11. The converting device of claim 10 , wherein the log 2 (T) most significant bits in the output index are used to point to one of the T tiles and the m last significant bits in the output index are used as a memory read address.

12. The converting device of claim 11 , wherein each of the N×M lookup indexes includes a Tile identifier (ID) of a particular tile of the T tiles that is to be accessed by a respective lookup path of the N lookup paths.

13. The converting device of claim 12 , wherein each of the N×M lookup indexes includes a memory address of a memory in the particular tile from which data is read.

14. A method of supporting N parallel key-to-lookup indexes conversions, the method comprising:
receiving N keys at a converter device, wherein each of the N keys is associated with a group of tiles from T tiles, wherein each of the T tiles includes M memories;
storing N×M lookup indexes with the converter device, the N×M lookup indexes to return from the converter after parallel conversions of the N keys to the N×M lookup indexes; and
converting a key from the N keys to a lookup index from the N×M lookup indexes with N×M converters of the converter device, wherein N, T and M are positive integer values.

15. The method of claim 14 , further comprising forwarding the N×M lookup indexes to a central reconfiguration interconnection fabric, wherein the central reconfiguration interconnection fabric is configured to connect each of the N×M lookup indexes to one of T tiles for comparing the key with pre-programmed keys stored in that tile.

16. The method of claim 15 , wherein each of the N×M converters comprise a log 2 (T)+1 hash functions and log 2 (T)+1 non-hash functions.

17. The method of claim 16 , wherein outputs of the functions have bitwidths ranging from m bits to log 2 (T)+m bits, wherein m is a positive integer value.

18. The method of claim 17 , wherein each of the N×M converters comprise a first configurable register for selecting one of the functions.

19. The method of claim 18 , wherein each of the N×M converters comprise a second configurable register for selecting a tile offset such that the lookup index points to a correct tile from the group of tiles associated with the key.

20. The method of claim 19 , wherein each lookup path of N lookup paths is associated with M converters of the N×M converters.

21. The method of claim 20 , wherein converter i of the M converters of each lookup path of N lookup paths is used to access memory i in one of the T tiles allocated for that lookup path.

22. The method of claim 21 , wherein each of M index converters of each lookup path of the N lookup paths is configurable based on a number of tiles allocated for that lookup path of the N lookup paths.

23. The method of claim 22 , wherein each of the N×M converters comprise an output index having log 2 (T)+m bits.

24. The method of claim 23 , wherein the log 2 (T) most significant bits in the output index are used to point to one of the T tiles and the m last significant bits in the output index are used as a memory read address.

25. The method of claim 24 , wherein each of the N×M lookup indexes includes a Tile identifier (ID) of a particular tile of the T tiles that is to be accessed by a respective lookup path of the N lookup paths.

26. The method of claim 25 , wherein each of the N×M lookup indexes includes a memory address of a memory in the particular tile from which data is read.

Assignees

• Marvell Asia Pte Ltd

Inventors

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

Classifications

• H04L45/745

  Address table lookup; Address filtering · CPC title

• G06F12/0864

  using pseudo-associative means, e.g. set-associative or hashing · CPC title

• G06F3/0683

  Plurality of storage devices · CPC title

• G11C15/04

  using semiconductor elements · CPC title

• H04L45/7453

  using hashing · CPC title