公开(公告)号：US20240104136A1

公开(公告)日：2024-03-28

申请号：US18520358

申请日：2023-11-27

Applicant: Altera Corporation

Inventor： Johan KARLSSON RÖNNBERG ,  Mikael SUNDSTRÖM

IPC: G06F16/901 ,  G06F16/22 ,  G06F16/2453 ,  G06F16/2455

CPC classification number: G06F16/9024 ,  G06F16/2246 ,  G06F16/24542 ,  G06F16/24554

Abstract: Methods, apparatus, and systems for efficient partitioning and construction of graphs for scalable high-performance search applications. A method for partitioning a set of ternary keys having one or more wildcards includes analyzing patterns of the set of ternary keys and storing ternary keys with the same pattern in the same subset. The patterns may include uncompressed patterns and compressed patterns. When there are more patterns than a target number of subgraphs, patterns are repeatedly merged until the number of merged patterns matches the target number of subgraphs. Table entries having ternary keys corresponding to the ternary keys in a final set of merged patterns of ternary keys are generated and partitioned into sub-tables, with each sub-table associated with a respective sub-graph. Tables with hundreds of thousands or millions of entries are supported.

公开(公告)号：US20240354305A1

公开(公告)日：2024-10-24

申请号：US18751034

申请日：2024-06-21

Applicant: Altera Corporation

Inventor： Mikael SUNDSTRÖM

IPC: G06F16/2455 ,  G06F16/22

CPC classification number: G06F16/24558 ,  G06F16/2228

Abstract: Methods, apparatus, and systems for efficient partitioning and construction of graphs for scalable high-performance search applications. In one aspect a graph-based method for performing a longest prefix match (LPM) is disclosed. A plurality of ternary keys and created or accessed, each representing an Internet Protocol (IP) mask and having a length w and a number of specific bits comprising a prefix length followed by one or more wildcards. The ternary keys are partitioned into subsets as a function of the prefix lengths of the ternary keys. For each subset, a graph is constructed, and the graph is stored in memory. The graphs are searched for a match for an IP address. A result associated with the graph associated with the subset of prefixed with the longest prefix length is returned. Associated apparatus and systems for implementing the methods are also disclosed. In some embodiments, a graph memory engine (GME) is used.