Method and system for an algorithm and circuit for a high performance exact match lookup function
US9047329B1 · kind B1 · utility
Assignee
Inventor
Key dates
| Filing date | Apr 27, 2012 |
| Grant date | Jun 2, 2015 |
| Priority date | — |
| Expiry date | Oct 24, 2032 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F16/9017
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
In one aspect, a device is configured to provide a lookup operation for looking up a data value stored in a result table. The device includes several data tables for storing keys, or compressed representations of keys, associated with data values stored in the result table. During an example lookup operation, storage locations included within the data tables are searched for a particular key, or compressed representations of the key. If the key is found, the storage location is used to identify a memory address associated with the result table. In some implementations, the data tables are accessed in parallel to provide a lookup operation having a fixed latency. Storage locations within the data tables also are arranged to reduce the amount of memory used to implement each data table. In some implementations, the data tables are configured to use no more than one result table access per lookup operation.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.