Method and system for reconfigurable parallel lookups using multiple shared memories
View Patent ↗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 programmed based on how the tiles are allocated for each lookup.
1. A method of performing N parallel lookups using a pool of shared memories:
partitioning T tiles to N groups, wherein each of the T tiles includes M memories, and wherein each of N lookup paths is associated with an input port and an output port, and wherein each of N lookup paths is assigned to one of the N groups, wherein N, T and M are positive integer values; and
executing the N parallel lookups, comprising:
for each of N input keys:
converting the input key into a plurality of lookup indexes, wherein each of the plurality of lookup indexes includes a Tile identifier (ID) of a particular tile in one of the N groups that is to be accessed by a respective lookup path and also includes a memory address of a memory in the particular tile from which data is read;
determining by using a collection of match information from the particular tile which hit information to return; and
determining by using a collection of hit information from those tiles indicated by the plurality of lookup indexes which final lookup result to return for a lookup path associated with the input key.
2. The method of claim 1 , wherein in the determination of which hit information to return from the particular tile, a highest priority is given to a memory in that particular tile having a lowest Mem identifier (ID) among all memories in that particular tile.
3. The method of claim 2 , wherein the hit information includes hit data and location of the hit data corresponding to a matched key, wherein the location of the hit data includes of a Mem identifier (ID), an address of a memory associated with the Mem ID, and location of the hit data in the memory.
4. The method of claim 1 , wherein in the determination of which final lookup result to return for a lookup path, a highest priority is given to a tile having a lowest Tile identifier (ID) among all tiles allocated for the lookup path.
5. The method of claim 4 , wherein the final lookup result includes hit data, a Tile identifier (ID) of a tile containing the hit data, memory identifier (ID) and memory address where the hit data is read.
6. The method of claim 1 , further comprising, prior to executing the N parallel lookups:
computing hash size for each lookup path;
generating configuration bits for hash selection and tile offset for each lookup path;
configuring networks connecting lookup paths and the tiles; and
programming the memories for each lookup path.
7. The method of claim 6 , wherein a technique for programming the memories for each lookup path is based on a D-LEFT lookup technique with M ways and P buckets.
8. A method of performing N parallel lookups using a pool of T×M shared memories:
partitioning T tiles to N groups, wherein each of the T tiles includes M memories, and wherein each of N lookup paths is associated with an input port and an output port, and wherein each of N lookup paths is assigned to one of the N groups, wherein N, T and M are positive integer values; and
executing the N parallel lookups, comprising:
for each of N input keys:
converting the input key into a plurality of lookup indexes, wherein each of the plurality of lookup indexes includes a Tile identifier (ID) of a particular tile in one of the N groups that is to be accessed by a respective lookup path and also includes a memory address of a memory in the particular tile from which data is read.
9. The method of claim 8 , further comprising determining by using a collection of match information from the particular tile which hit information to return.
10. The method of claim 9 , wherein in the determination of which hit information to return from the particular tile, a highest priority is given to a memory in that particular tile having a lowest Mem identifier (ID) among all memories in that particular tile.
11. The method of claim 10 , wherein the hit information includes hit data and location of the hit data corresponding to a matched key, wherein the location of the hit data includes of a Mem identifier (ID), an address of a memory associated with the Mem ID, and location of the hit data in the memory.
12. The method of claim 8 , further comprising determining by using a collection of hit information from those tiles indicated by the plurality of lookup indexes which final lookup result to return for a lookup path associated with the input key.
13. The method of claim 12 , wherein in the determination of which final lookup result to return for a lookup path, a highest priority is given to a tile having a lowest Tile identifier (ID) among all tiles allocated for the lookup path.
14. The method of claim 13 , wherein the final lookup result includes hit data, a Tile identifier (ID) of a tile containing the hit data, memory identifier (ID) and memory address where the hit data is read.
15. The method of claim 8 , further comprising, prior to
executing the N parallel lookups:
computing hash size for each lookup path;
generating configuration bits for hash selection and tile offset for each lookup path;
configuring networks connecting lookup paths and the tiles; and
programming the memories for each lookup path.
16. The method of claim 15 , wherein a technique for programming the memories for each lookup path is based on a D-LEFT lookup technique with M ways and P buckets.
17. A method of performing N parallel lookups using a pool of shared memories:
partitioning T tiles to N groups, wherein each of the T tiles includes M memories, and wherein each of N lookup paths is associated with an input port and an output port, and wherein each of N lookup paths is assigned to one of the N groups, wherein N, T and M are positive integer values;
computing hash size for each lookup path;
generating configuration bits for hash selection and tile offset for each lookup path;
configuring networks connecting lookup paths and the tiles;
programming the memories for each lookup path; and
executing the N parallel lookups, comprising:
for each of N input keys:
converting the input key into a plurality of lookup indexes, wherein each of the plurality of lookup indexes includes a Tile identifier (ID) of a particular tile in one of the N groups that is to be accessed by a respective lookup path and also includes a memory address of a memory in the particular tile from which data is read;
determining by using a collection of match information from the particular tile which hit information to return; and
determining by using a collection of hit information from those tiles indicated by the plurality of lookup indexes which final lookup result to return for a lookup path associated with the input key.
18. The method of claim 17 , wherein in the determination of which hit information to return from the particular tile, a highest priority is given to a memory in that particular tile having a lowest Mem identifier (ID) among all memories in that particular tile.
19. The method of claim 18 , wherein the hit information includes hit data and location of the hit data corresponding to a matched key, wherein the location of the hit data includes of a Mem identifier (ID), an address of a memory associated with the Mem ID, and location of the hit data in the memory.
20. The method of claim 17 , wherein in the determination of which final lookup result to return for a lookup path, a highest priority is given to a tile having a lowest Tile identifier (ID) among all tiles allocated for the lookup path.
21. The method of claim 20 , wherein the final lookup result includes hit data, a Tile identifier (ID) of a tile containing the hit data, memory identifier (ID) and memory address where the hit data is read.
22. The method of claim 17 , wherein a technique for programming the memories for each lookup path is based on a D-LEFT lookup technique with M ways and P buckets.