Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
2001-02-13
2004-07-27
Mai, Tan V. (Department: 2121)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
Reexamination Certificate
active
06769005
ABSTRACT:
FIELD OF THE INVENTION
The present invention pertains generally to the field of computer hardware. More specifically, the present invention pertains to a method and apparatus for resolving priorities among a number of data values.
BACKGROUND OF THE INVENTION
In a computer network, data are typically transferred in data structures referred to as “packets.” A packet can travel through network according to information included within the packet header. Network routers and switches can receive packets, and process the packet according to the header information. Typical routers and switches carry out the packet routing and switching functions by a matching the header (or portions of the header) to a number of entries. If the header matches an entry, an indication (e.g., a MATCH signal) will be generated. The match indication can be used by the routers and switches to determine the packet's destination and the manner to which the packet should be processed.
One type of device that is particularly useful for performing the “matching” function is the content addressable memory (CAM). The main advantage of a CAM device is that the entire CAM can be searched in a single clock cycle. The input signal to the CAM would be a bit string representation of the data being searched for in the CAM. The outputs would be a MATCH signal indicating whether the data are found, and the address of the CAM where the matching data is located. If matching data is found in multiple addresses the CAM may also generate priority data indicative of the relative importance and priority of the addresses.
Given a large number of addresses, each having an assigned priority, the determination of which of those addresses has the highest priority is difficult.
According to one embodiment, the larger the data value, the higher the priority. Thus, the largest data value corresponds to the highest priority value.
The brute force approach is to compare address priorities two at a time. For a thousand possible priority values, the first step would require five hundred comparators. The lower priority value of each pair would be tossed aside, and the higher priority value would be passed on to the next step. This shrinking cone of comparators would continue until the highest priority address is left. This method, while straightforward, requires an increasingly large number of comparators as the number of address priorities to be compared increases.
SUMMARY OF THE DISCLOSURE
In summary, a method and apparatus for resolving priority among a plurality of data values is disclosed. The priority resolution method of the present invention does not compare the data values two at a time. Furthermore, the priority resolution method of the present invention does not require an increasingly large number of comparators as the number of data values to be compared increases.
The priority resolution method of the invention analyzes the data values one bit-position at a time, starting from the most significant bit. For each bit-position, the method determines whether any one of the bits at the current bit-position is asserted (e.g., the bit has a value of “1”). If at least one of the is asserted, the data values associated with the unasserted bits (e.g., bits having values of “0”) are eliminated from consideration as the highest priority data value in the subsequent steps. If none of the bits at the current bit-position is asserted, none of the data values will be eliminated from consideration as the highest priority data value. The same steps are repeated for each successive bit until only the largest data value remains.
An embodiment of the present priority resolution method may be used to determine the smallest value among a plurality of data values. In that embodiment, the data values are first bit-wise inverted. The bit-wise inverted data values are then analyzed, one bit at a time, starting from the most significant bit, until only the largest inverted data value remains. The smallest data value is then obtained by inverting the largest inverted data value.
An apparatus in accordance with the present invention includes a circuit for resolving priorities among a plurality of data values. The circuit of the present embodiment includes a plurality of successive stages, each of which is configured for analyzing one bit-position of the data values. Each stage includes a circuit for receiving “still valid” bits from a previous stage, a circuit for determining whether the data bits at the bit-position are asserted, and a circuit for generating “still valid” bits for the next stage. In the present embodiment, the “still valid” bits indicate that the associated data values are still valid. That is, if a data value's “still valid” bit is asserted, then it can be determined that the data value has not been eliminated for consideration as the highest priority data value by a previous stage. Data values are eliminated from consideration one stage at a time until the largest data value is left.
Embodiments of the present invention include the above and further include a circuit for resolving highest priority amongst a plurality of data values. The circuit includes: a first stage for receiving the first highest priority bits of the data values, and a second stage for receiving the second-from-highest priority bits. Particularly, the first stage includes circuitry for determining whether the first highest priority bits of the data values are asserted, and circuitry for generating “still valid” signals associated with the data values having asserted highest priority bits. The second stage receives the “still valid” bits generated by the first stage, and includes circuitry for determining whether the second-from-highest priority bits of the data values associated with the “still valid” signals are asserted. The second stage also has circuitry for generating “still valid” signals associated with the data values not eliminated by the first stage and having asserted second-from-highest priority bits. The “still valid” signals are then used by a subsequent stage to further eliminate data values from consideration.
REFERENCES:
patent: 4446452 (1984-05-01), Munter
patent: 4539549 (1985-09-01), Hong et al.
patent: 4998219 (1991-03-01), Frauenglass
patent: 5122979 (1992-06-01), Culverhouse
patent: 5262969 (1993-11-01), Ishihara
patent: 5721809 (1998-02-01), Park
patent: 5726923 (1998-03-01), Okumura et al.
patent: 6446101 (2002-09-01), Braun
Fernandez Dennis S.
Fernandez & Associates LLP
Mai Tan V.
Silicon Access Networks
LandOfFree
Method and apparatus for priority resolution does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for priority resolution, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for priority resolution will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3189614