Native Lookup Instruction for File-Access Processor Searching a Three-Level Lookup Cache for Variable-Length Keys
First Claim
1. A micro-processor comprising:
- an instruction decoder for decoding instructions in a program being executed by the processor, the instructions including a lookup instruction;
a register file containing registers that store operands operated upon by the instructions, the registers being identified by operand fields in the instructions decoded by the instruction decoder;
a memory-access unit for accessing entries of a lookup cache;
an address generator for generating an address to the memory-access unit;
a comparator for comparing stored keys read from the entries to an input key;
wherein the input key is a variable-length operand;
a lookup unit, activated by the instruction decoder when the lookup instruction is decoded, for performing a lookup operation indicated by the lookup instruction, the lookup operation searching the lookup cache for a matching entry that has a stored key that matches the input key, whereby the lookup instruction is decoded and executed by the processor.
9 Assignments
0 Petitions
Accused Products
Abstract
A processor natively executes lookup instructions. The lookup instruction is decoded to determine which general-purpose register (GPR) contains a pointer to a lookup key in a buffer. A variable-length key is read from the buffer and hashed to generate an index into a first-level cache and a hashed tag. An address of a bucket of entries for the index is generated and tags from these entries are read and compared to the hashed tag. When an entry matches the hashed tag, a second-level entry is read. A stored key from the second-level entry is compared to the input key to determine a match. The addresses of the matching second-level and first-level entries are written to GPR'"'"'s specified by operands decoded from the lookup instruction. When the key or entry data is long, the second-level entry also contains a pointer to a key extension or data extension in a third-level cache.
-
Citations
23 Claims
-
1. A micro-processor comprising:
-
an instruction decoder for decoding instructions in a program being executed by the processor, the instructions including a lookup instruction;
a register file containing registers that store operands operated upon by the instructions, the registers being identified by operand fields in the instructions decoded by the instruction decoder;
a memory-access unit for accessing entries of a lookup cache;
an address generator for generating an address to the memory-access unit;
a comparator for comparing stored keys read from the entries to an input key;
wherein the input key is a variable-length operand;
a lookup unit, activated by the instruction decoder when the lookup instruction is decoded, for performing a lookup operation indicated by the lookup instruction, the lookup operation searching the lookup cache for a matching entry that has a stored key that matches the input key, whereby the lookup instruction is decoded and executed by the processor.
-
-
2. A processor comprising:
-
an instruction decoder for decoding instructions in a program being executed by the processor, the instructions including a lookup instruction;
a register file containing registers that store operands operated upon by the instructions, the registers being identified by operand fields in the instructions decoded by the instruction decoder;
a memory-access unit for accessing first-level entries and second-level entries of a lookup cache;
an address generator for generating a first-level address and a second-level address to the memory-access unit;
a comparator for comparing tags read from the first-level entries to a key derivative and for comparing stored keys read from the second-level entries to an input key;
wherein the input key is a variable-length operand while the key derivative is generated from the input key;
a lookup unit, activated by the instruction decoder when the lookup instruction is decoded, for performing a lookup operation indicated by the lookup instruction, the lookup operation searching the lookup cache for a matching second-level entry that has a stored key that matches the input key, whereby the lookup instruction is decoded and executed by the processor. - View Dependent Claims (3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17)
-
-
18. A computerized method for executing a lookup instruction comprising:
-
decoding instructions for execution by a processor including decoding the lookup instruction that contains an opcode that specifies a lookup operation on a lookup cache;
decoding a first operand field in the lookup instruction and a result field in the lookup instruction, the first operand field specifying a first register that contains a key pointer to an input key in a buffer while the result field specifies a result register that a result of the lookup operation is to be written to;
reading an input key from a buffer at a location indicated by the key pointer;
hashing the input key to generate a hashed key;
generating an index from a first portion the hashed key and a hashed tag from a second portion of the hashed key;
generating a bucket address of a bucket of first-level entries in a first-level cache of the lookup cache;
reading a plurality of stored tags from first-level entries in the bucket addressed by the bucket address;
comparing the plurality of stored tags from the bucket to the hashed key to find a matching first-level entry in the bucket that has a stored tag that matches the hashed key;
generating a second-level address for a corresponding second-level entry that corresponds to the matching first-level entry;
reading a stored key from the corresponding second-level entry using the second-level address to locate the corresponding second-level entry;
comparing the stored key read from the corresponding second-level entry to the input key to determine a key match; and
when the key match is found, writing the second-level address to the result register or to a second result register predetermined by the result field in the lookup instruction;
whereby the lookup instruction is decoded and executed to find the second-level address for a key match. - View Dependent Claims (19, 20, 21)
-
-
22. A specialized processor comprising:
-
decode means for decoding instructions including decoding a lookup instruction that contains an opcode that specifies a lookup operation on a lookup table;
a register file containing registers accessible by execution of instructions decoded by the decode means;
operand decode means for decoding a first operand field in the lookup instruction and a result field in the lookup instruction, the first operand field specifying a first register in the register file that contains a key pointer to an input key in a buffer and the result field specifying a result register in the register file that a result of the lookup operation is to be written to;
buffer means for storing variable-length operands including an input key that is read from the buffer means at a location indicated by the key pointer;
hash means for hashing the input key to generate a hashed key, the hashed key having an index and a hashed tag;
first address means, receiving the index, for generating a bucket address of a bucket of first-level entries in a first-level cache of the lookup table;
first match means for reading a plurality of stored tags from first-level entries in the bucket addressed by the bucket address and for comparing the plurality of stored tags from the bucket to the hashed key to find a matching first-level entry in the bucket that has a stored tag that matches the hashed key;
second address means for generating a second-level address for a corresponding second-level entry that corresponds to the matching first-level entry;
second match means for reading a stored key from the corresponding second-level entry using the second-level address to locate the corresponding second-level entry, and for comparing the stored key read from the corresponding second-level entry to the input key to determine a key match; and
result means, responsive to the key match, for writing the bucket address to the result register and for writing the second-level address to a register that follows the result register;
whereby the lookup instruction is decoded and executed to find the key match. - View Dependent Claims (23)
-
Specification