Data search method and apparatus, and integrated circuit

Patent metadata

Field	Value
Publication number	US-12332805-B2
Application number	US-202318357506-A
Country	US
Kind code	B2
Filing date	Jul 24, 2023
Priority date	Feb 7, 2021
Publication date	Jun 17, 2025
Grant date	Jun 17, 2025

Abstract

A data search apparatus includes a logical search circuit and a memory, and the logical search circuit is connected to the memory through a databus. The databus can access all memory resources, and each part of databus resource can access all the memory resources. A logical search resource provided by the logical search circuit can be divided into a plurality of parts as required, and each part of logical resource can access node data in the memory through the bus resource.

First claim

What is claimed is:

1. An apparatus, comprising:
a logical search circuit comprising a first node logic;
a memory connected to the logical search circuit through a databus;
a parsing circuit;
a decision circuit; and
a first comparison circuit group comprising a first plurality of comparison circuits,
wherein the memory comprises a first memory block and a second memory block,
wherein the first node logic is configured to:
when receiving a first table lookup request, read, from a first data table stored in the first memory block through the databus, first node data to be queried based on the first table lookup request; and
when receiving a second table lookup request, read, from a second data table stored in the second memory block through the databus, second node data to be queried based on the second table lookup request,
wherein the parsing circuit is configured to: parse the first table lookup request to obtain a first key, send the first key to the first plurality of comparison circuits, and distribute the first node data to the first plurality of comparison circuits, wherein the first node data comprises a plurality of first data parts, and the plurality of first data parts are in a one-to-one correspondence with the first plurality of comparison circuits;
any comparison circuit in the first comparison circuit group is configured to: match the first key sent by the parsing circuit against a distributed data part to obtain a first matching result, and send the first matching result to the decision circuit; and

the decision circuit is configured to summarize first matching results separately sent by the first plurality of comparison circuits to obtain a query result corresponding to the first table lookup request.

2. The apparatus according to claim 1 , wherein the parsing circuit is further configured to:
determine that the first table lookup request comes from a first search interface, and distribute, to the first comparison circuit group based on a mapping relationship between the first search interface and the first comparison circuit group, the first key obtained by parsing the first table lookup request and the first node data to be queried based on the first table lookup request.

3. The apparatus according to claim 1 , wherein the first node data occupies a first bus resource of the databus; and
the parsing circuit is specifically configured to distribute, to the first comparison circuit group based on a mapping relationship between the first bus resource and the first comparison circuit group, the first node data received from the first bus resource and the first key obtained by parsing the first table lookup request.

4. The apparatus according to claim 1 , wherein the logical search circuit further comprises a second comparison circuit group, and the second comparison circuit group comprises a second plurality of comparison circuits, wherein:
the parsing circuit is further configured to: receive a third table lookup request, parse the third table lookup request to obtain a second key, and send the second key to the second plurality of comparison circuit;
the parsing circuit is further configured to distribute, to the second plurality of comparison circuits, read third node data to be queried based on the third table lookup request, wherein the third node data comprises a plurality of second data parts, and the plurality of second data parts are in a one-to-one correspondence with the second plurality of comparison circuits;
any comparison circuit in the second comparison circuit group is configured to: match the second key sent by the parsing circuit against a distributed data part to obtain a second matching result, and send the second matching result to the decision circuit; and
the decision circuit is further configured to summarize second matching results separately sent by the plurality of second comparison circuits to obtain a query result corresponding to the third table lookup request.

5. The apparatus according to claim 4 , wherein the parsing circuit is specifically configured to:
when receiving the first table lookup request, select an idle first comparison circuit group from the first comparison circuit group and the second comparison circuit group, and distribute, to the first comparison circuit group, the first node data and the first key obtained by parsing the first table lookup request.

6. The apparatus according to claim 4 , wherein a mode currently used by the apparatus is a first search mode, and in the first search mode, the apparatus supports parallel processing on at least two table lookup requests; and
the apparatus further supports a second search mode, and in the second search mode, the apparatus supports parallel processing on one table lookup request.

7. The apparatus according to claim 6 , wherein the first node logic is further configured to:
receive a fourth table lookup request in the second search mode; and
read, from the first memory block through the databus, a first part of data comprised in fourth node data to be queried based on the fourth table lookup request, and read, from the second memory block, a second part of data comprised in the fourth node data to be queried based on the fourth table lookup request.

8. The apparatus according to claim 7 , wherein:
the apparatus is configured to use a longest prefix match (LPM) manner;
the decision circuit comprises a first comparator, a second comparator, a result selector, and a data selector;
the first comparator is configured to: obtain the first matching results of the first comparison circuit group and the second matching results of the second comparison circuit group, separately output a first summary result to the second comparator and the data selector, and separately output a second summary result to the second comparator and the result selector;
the first summary result is a result obtained by summarizing the first matching results;
the second summary result is a result obtained by summarizing the second matching results;
the second comparator is configured to: summarize the first summary result and the second summary result to obtain a third summary result, and output the third summary result to the result selector;
the result selector is configured to: output the second summary result to the data selector in the first search mode, and output the third summary result to the data selector in the second search mode; and
the data selector is configured to: output, in the first search mode based on the second summary result and the first summary result, search results separately corresponding to a first search request and a third search request; and output, in the second search mode based on the third summary result, a query result corresponding to a fourth search request.

9. A method, performed by a logical search circuit, wherein the logical search circuit comprises a first node logic connected to a memory through a databus, a parsing circuit, a decision circuit, and a first comparison circuit group, the first comparison circuit group comprises a first plurality of comparison circuits, and the memory comprises a first memory block and a second memory block, wherein the method comprises:
when receiving a first table lookup request, reading, by the first node logic from a data table stored in the first memory block through the databus, first node data to be queried based on the first table lookup request;
when receiving a second table lookup request, reading, by the first node logic from a data table stored in the second memory block through the databus, second node data to be queried based on the second table lookup request
parsing, by the parsing circuit, the first table lookup request to obtain

Assignees

• Huawei Tech Co Ltd

Inventors

• Liu Yang
• Yu Jingzhou
• Liu Cong
• Guo Lingbo
• Xing Yusheng
• Zhou Liwei

Classifications

• G06F16/9038

  Presentation of query results · CPC title

• G06F13/378 Primary

  using a parallel poll method · CPC title

• G06F13/374

  using a self-select method with individual priority code comparator · CPC title

• G06F12/1009 Primary

  using page tables, e.g. page table structures · CPC title

• H04L45/74 Primary

  Address processing for routing · CPC title