US 6,272,614 B1 · Processing method and apparatus involving a processor instruction using hashing

Abstract

A program-controlling processing unit executes instructions stored in memory. A special instruction type is provided for selectively retrieving an element from memory in dependence on the value of input data subject of the instruction. Each instruction of this type has a header identifying the instruction type, and a body in the form of a hash table having at least one entry with both (i) a check value corresponding to a value of interest of the input data subject of the instruction, and (ii) an element to be used when the input data has said value of interest. Upon execution of such an instruction, the related input data is hashed to produce an offset value that is used to access in memory, relative to the position in memory of the current instruction, a corresponding entry in the hash table of the instruction. If a “hit” results (that is, the check value of the accessed entry matches the input data value), the entry element is operatively output. Such a compact, relocatable, instruction is of particular use in processing units for controlling packet switches where the packet destination address is used to determine routing.

Claims20

Dependent claims

A processing method in which program-controlled processing means, in the course of executing an instruction of a given type stored in memory, is caused to selectively retrieve an element from memory in dependence on the value of input data subject of the instruction;

said instruction having a header identifying the instruction as of said given type, and a body in the form of a hash table having at least one entry with both (i) a check value corresponding to a value of interest of said input data subject of the instruction, and (ii) an element to be used when said input data has said value of interest;
said method involving the steps:
(a) determining whether a current instruction to be executed by the processing means is of said given type;
(b) where step (a) determines that the instruction is of said given type, hashing the said input data subject of the instruction to produce an offset value;
(c) using the offset value produced in step (b) to access in memory, relative to the position in memory of the current instruction, a corresponding entry in the hash table of the current instruction;
(d) comparing the value of the input data with the check value held in the entry accessed in step (c), and making available the associated entry element for operative use only when the compared values match.

3 more elements

Apparatus provided with comprising processing means for executing a program that includes an instruction having a header and a body, the header identifying it as of a given type, and the body being in the form of a hash table having at least one entry with both a check value and an output element;

the processing means having for processing an instruction of said given type:
hashing means for hashing an input data value to produce an offset value;
offset-access means for using said offset value to access an entry of the instruction's hash table at an offset relative to the instruction header;
and comparator means for outputting the element of the accessed hashtable entry when the letter's check value matches the input data value.

1 more element

Apparatus comprising a processor for executing a program that includes an instruction having a header and a body, the header identifying it as of a given type, and the body being in the form of a hash table having at least one entry with both a check value and an output element;

the processor having, for processing an instruction of said given type:
hashing apparatus for hashing an input data value to produce an offset value;
offset-access apparatus for using said offset value to access an entry of the instruction's hash table at an offset relative to the instruction header;
and
a comparator for outputting the element of the accessed hash-table entry when the latter's check value matches the input data value.

2 more elements

Dependencies are inferred from the claim text.

Processing method and apparatus involving a processor instruction using hashing

Life of this patent

Processing method and apparatus involving a processor instruction using hashing

Life of this patent

Abstract

Claims20