Method and apparatus for efficient selection of a boundary...

Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed

Reexamination Certificate

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

C708S671000, C340S146200

Reexamination Certificate

active

06341296

ABSTRACT:

BACKGROUND OF THE INVENTION
The present invention relates generally to digital logic. More particularly, the invention relates to a method and apparatus for quickly identifying a lowest or highest boundary value from among a number of values. The invention has particular applications in the field of high-performance digital communications and has other applications.
In a number of digital logic applications, it is necessary to determine the highest value or lowest value number of a group of digitally-encoded numbers. In this application boundary value will be used to indicate either a highest or lowest value. One such application is determining cell or packet scheduling in a digital communications device. In such a device, cells, packets, buffers, or other entities, may each be assigned a number indicating their priority. A scheduling routing selects a cell, packet, buffer or other entity based on its priority value as compared with the priority values of other entities seeking service. In some applications, the priority values associated with a cell, packet, buffer, or other entity are referred to as tags.
Typically, this selection is accomplished using a tree of comparators.
FIG. 1
illustrates a prior art method for determining a boundary value out of 16 numbers using four stages of comparators. In the first stage, numbers are paired (in many applications in a fixed order or essentially at random) and input into comparators
10
. The boundary higher or lower value of each pair is passed to the next stage and the other value is discarded. For 16 tags, this process is repeated three more times, until one boundary value emerges.
This prior art device has a number of disadvantages. The first is that in a hardware implementation, each comparator is generally comprised of a large number of gates (usually XOR gates) and this consumes a large chip area. As is known in the art, the total chip area needed for a hardware implementation can be reduced by reusing compare elements for different stages, but doing so adds to the complexity of the circuit and increases processing time.
Two other related disadvantages are that it is difficult to determine if more than one of the initial tags is equal to the boundary value and it is difficult to signal to the initial tags or values which of them was selected as the boundary value. This is because the output of the final comparator
10
a
is simple an N bit number representing the boundary detected. While both of these difficulties can be address in a circuit such as
FIG. 1
, doing so requires additional feedback circuitry and can also require additional time for processing.
What is needed is a method and apparatus that can select one or more boundary values from a number of input values without the disadvantageous and limitations of prior art methods.
SUMMARY OF THE INVENTION
The present invention is a method and apparatus for quickly the maximum or minimum boundary value from a group of values that quickly indicates the output boundary value and indicates each input value that matched that boundary value.
In one embodiment, the invention is constructed of slice logic blocks, each block processing one of the input values to determine if it is a maximum value. A result block, shared by all the logic blocks, produces the boundary value.
The invention also comprises a method for selecting a boundary value by comparing all the bits in one input value to input bits and conditioned bits from other input values.
In a communications device, such as an ATM switch or routing table or other devices, the input values (in this embodiment referred to as tags) may represent a priority level and the device and method of the invention can be used to very quickly determine tags indicating the highest or lowest priority buffers or cells awaiting service.
The invention will be explained with respect to specific embodiments, but will be clear to those of skill in the art that the invention may be deployed in many alternative logic applications. The invention may also be deployed as described below for operation of a wide variety of communications devices. For the sake of clarity, the invention will be described in terms of specific examples. It is inherent in the art that logic devices and processes and communications devices can be highly variable in the arrangement and configuration of different components. These examples should therefore been taken as illustrations and not seen as limiting the invention and the invention should not be limited except as provided by the attached claims and allowable equivalents.


REFERENCES:
patent: 4539549 (1985-09-01), Hong et al.
patent: 4757464 (1988-07-01), Zimmermann et al.
patent: 4760374 (1988-07-01), Moller
patent: 4774688 (1988-09-01), Kobayashi et al.
patent: 4799152 (1989-01-01), Chuang et al.
patent: 4967349 (1990-10-01), Kodama et al.
patent: 5262969 (1993-11-01), Ishihara
patent: 5721809 (1998-02-01), Park
patent: 6115725 (2000-09-01), Shibata et al.

LandOfFree

Say what you really think

Search LandOfFree.com for the USA inventors and patents. Rate them and share your experience with other people.

Rating

Method and apparatus for efficient selection of a boundary... 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 efficient selection of a boundary..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for efficient selection of a boundary... will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFUS-PAI-O-2851484

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.