Electrical computers and digital processing systems: memory – Address formation – Hashing
Reexamination Certificate
1999-04-30
2001-08-07
Yoo, Do Hyun (Department: 2187)
Electrical computers and digital processing systems: memory
Address formation
Hashing
C712S220000
Reexamination Certificate
active
06272614
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to a processing method and apparatus involving a processor instruction employing hashing.
BACKGROUND OF THE INVENTION
Processor instructions are known that provide for branching in dependence on the value of some parameter stored at a particular location (often in the accumulator of the processor ALU). Processor instructions are also known that provide for a degree of indirection in accessing an element to be handled by the instruction; by this is meant that the location of the target element is not directly specified in the instruction, but instead the instruction specifies a location that holds the address of the location storing the target element. More sophisticated indirection involves pre or post indexing based on a value held in a specific processor register (pre-indexing involves modifying the address specified in the instruction whereas post-indexing involves modifying the address stored in the location specified in the instruction).
In apparatus such as a packet switch, a controlling processor will generally be required to carry out some action based on the value of an input quantity such as a packet destination address. This desired capability can be viewed as a branching operation in which the processor must branch to a required action dependent on the value of the input quantity. Alternatively the desired capability can be likened to an operation involving indirection post-indexed by the value of the input quantity. However, in applications such as controlling a packet switch, the range of possible values of the input quantity may be very large even though only a very limited subset of these values may be of interest. The standard branch instructions or instructions involving indirection cannot cope with this requirement in a compact and simple manner and will generally use a number of memory locations corresponding to the number of possible values of the input quantity.
It is an object of the present invention to provide a compact and flexible way of controlling a processor to selectively access elements in dependence on the value of an input quantity.
As will become apparent below, the present invention achieves this object by employing hashing. Hashing is itself a well known technique by which a relatively long input is transformed into a shorter output. Hashing is used for many different purposes including memory look-up and for forming message authentication codes. A large number of different hashing functions are known.
In order to facilitate an understanding of the present invention, a brief description of hashing as applied to memory look-up will now be given with reference to
FIG. 1
of the accompanying drawings. More particularly, in the
FIG. 1
arrangement, an input
10
(for example, a 48-bit input) is to be used to retrieve data held in memory
11
. In the current example, only a relatively small number of the possible values of the input
10
are of interest (for example, seven values). The memory is provided with a number of locations
12
equal, to or greater than, the number of input values of interest (but less than all possible input values), and the input
10
is applied to a hashing function
13
that transforms the input
10
into a shorter length index
14
matched to the size of the memory (in the current example, this might be a 3-bit index). The hashing function
14
is chosen such that every input value of interest produces a unique value of the index
14
and this latter value is then used to access a corresponding location of the memory
11
—this location being that used to store the data that it is desired to associate with the input value concerned.
Of course, many values of the input
10
will give rise to the same index value but it is only desired to register a “hit” (a valid output of data from the memory
11
) for the input value of interest that hashes to that index value. Accordingly, along with the data to be output, each memory location stores a check value corresponding to the input value for which that data is valid. When a memory location
12
is accessed, the check value is compared in comparator
15
with the current value of the input
10
and a data valid output
16
is only produced if there is a match. If the check value and input value do not match, a “miss” occurs. In so-called “perfect” hashing where every input value of interest is mapped by the hashing function
13
into its own unique value of index, this is the end of the process; however, it is often more efficient to practice “non-perfect” hashing in which there are some clashes between values of interest. In such cases, various strategies have been devised; for example, the indexed location may give access to a linked list of values of interest associated with that location. Another strategy is to effect “re-hashing” (that is, carrying out a hash retry) generally using a different hash function from that originally employed. Re-hashing strategies may extend to multiple re-hashing attempts each with a different predetermined hash function.
SUMMARY OF THE INVENTION
According to the present invention, there is provided 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; the 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 the input data subject of the instruction, and (ii) an element to be used when the input data has said value of interest; the 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 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.
In this manner, a compact instruction, relocatable in memory, is provided which is effective to produce different outcomes depending on the value of the input data subject of the instruction.
The element accessed in step (d) may be used by the processing means in several different ways. Thus, the element may be output as a control value and used, for example, for controlling packet routing in a packet switch. Alternatively, the accessed element may be used as an indicator of the location of a next instruction to be executed by the processing means. A further use of the accessed element is as a return value that is returned to a prior instruction responsible for calling the instruction of said given type, the returned value being used, for example, as an index into a table associated with the prior instruction.
The source of the input data subject of the instruction may be implicit (for example, all such data may be provided at the same source as will generally be the case if the instruction is called by another instruction and the input data is passed as a calling parameter). Alternatively, the instruction header may include an input-selection parameter providing a source indicator for the input data (
10
). This source indicator may specify a memory/register location holding the input data and/or specific bits of interest of a wider input.
The header of the instruction may include a size parameter indicative of the size of the hash table contained in the body of the instruction, this size parameter being used to limit the size, and thus the value range, of the offset value produced in step (b) in order to ma
Calamvokis Costas
Edwards Aled Justin
Hewlett--Packard Company
Portka Gary J.
Yoo Do Hyun
LandOfFree
Processing method and apparatus involving a processor... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Processing method and apparatus involving a processor..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Processing method and apparatus involving a processor... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2528483