Sun Microsystems, Inc.

Silicon Access Networks, Inc.

Altera Corporation

Michael L Ott

Choon Ping Chng

Tzungren A Tzeng

Ruey-Hsien Hu

The present invention provides a method and system to select a valid entry in a deterministic pseudo-random approach. The method may randomly select one of numerous valid entries in order to ensure that no specific entry or set of entries is consistently ignored. Moreover, the method may be deterministic in order that the selection technique could be precisely controlled for purposes such as testing and predetermined selection. The method of the present invention may be carried out in five parts: first, the total range of entries is divided into regions, each of which is further divided into one or more sub-regions; pre-determined or constantly-changing weighting is assigned to each region in the second step; an OR operation is then performed on the entries of each sub-region to determine which of the sub-regions, if any, contains no valid entries and thus may be disregarded in the final step; the weightings assigned in step two are examined in order to select a sub-region from a region where more than one sub-region contains valid entries. Furthermore, the final step combines the original entry's signal with the appropriate collection of ignore signals, and effectively selects one entry as the final output.

Method and system for deterministic pseudo-random valid entry resolution

Disclosed herein is an apparatus and method for determining if a first number is greater than or equal to a second number. By analyzing nibbles of a multi-bit number in parallel to determine for each nibble if the nibbles are unequal and if a first nibble is greater than a second nibble and thereafter logically determining which of the highest order nibbles, if any, are unequal to discover whether the first number is greater than the second number, or determining that all nibble pairs are equal and thus concluding that both numbers are equal. A digital logic circuit is preferably employed for such analysis.

Parallel greater than analysis method and apparatus

A method and apparatus for resolving priority among a plurality of data values. The priority resolution method of the invention analyzes the data values one bit at a time, starting from the most significant bit. In one embodiment, at an initial analysis step, the method determines whether the most significant bits of the data values are asserted. If at least one of the most significant bits is asserted, the data values that have unasserted most significant bits are eliminated from consideration. If none of the most significant bits is asserted, none of the data values will be eliminated at the initial step. The same analysis steps are repeated for each successive bit until only the largest data values remain. The priority resolution method of the present invention may be used to determine the smallest data value. In that embodiment, the data values are first bit-wise inverted.

Method and apparatus for priority resolution

A range match circuit is disclosed for fast compare of an incoming address by partitioning the incoming address into fields. In one embodiment, a 16-bit incoming address is divided into quarterly fields, or four segments of 4-bit addresses, for comparison with a 16-bit top end boundary that has been divided into quarterly fields and a 16-bit bottom end boundary that has been divided into quarterly fields. Consequently, the range match circuit is able to analyze the entire 16-bit address field in parallel and perform simple combinational logic to determine if the incoming address is within the boundaries described by the top edge and bottom edge of the range.

Method and system for range matching

Disclosed herein is a apparatus and method for packing a 16-bit number into an 8-bit result byte. The method and apparatus utilize a parallel processing right shift circuit and a filter to obtain desired results. The parallel processes are comprised of a plurality of multiplexers capable of discretely analyzing smaller groups of bits. In this manner, higher throughput may be obtained than previously known.

Parallel pack instruction method and apparatus

A method and apparatus for detecting leading zeros in a number represented by a plurality of four-bit nibbles, each nibble having an associated order of significance, said method comprising is disclosed. The leading zero detector calculates a leading zero count for each nibble in parallel, associates with each nibble count calculation a bit value inversely corresponding to the nibble's order of significance, and selects the nibble count calculation which corresponds to the highest order nibble without all zero values.

Optimized method and apparatus for parallel leading zero/one detection

A method and apparatus for computing leading zero count with offset (LZCO) using a parallel nibble calculation scheme. The invention receives as its input a first operand and a second &ldquo;offset&rdquo; operand. The first operand is identified by a plurality of nibbles, each comprising four bits. The LZCO calculator calculates the lower two bits of the result for each nibble while simultaneously (or in parallel) calculating the upper remaining bits of the result for each nibble. The LZCO also selects the resulting nibble calculation for the lower two bits and the upper bits according to the nibble that corresponds to the highest order nibble without all zero values.

Method and apparatus for computing parallel leading zero count with offset

An optimized system and method for a parallel leading zero anticipation which ascertains &ldquo;end of run&rdquo; patterns in parallel. A string representing the operands of the floating-point addition is divided into nibbles of predetermined bit length (normally 4 bits). Each nibble is analyzed for the end of run patterns and the results from this analysis determine whether a run of leading zero's or one's has ended within the nibble, and if there has been an end of run, the location (bit) of the end of run. The highest order nibble that has an end of run provides the higher order bits in the LZA (leading zero anticipator output) value, while the lower two bits of the LZA value are correlated from the location end of run within the nibble, as previously determined.

Optimized system and method for parallel leading one/zero anticipation

A carry-out bit generator determines if a bit pattern from two positive numbers matches one of the patterns for which a carry-out bit would be generated in addition. These patterns include a T G pattern and a T pattern (with a carry-in). Superscript n represents a number between zero and m&minus;1, superscript m represents the number of registers, T represents a 0/1 or 1/0 pair and G represents a 1/1 pair.

Fast carry-out generation

A device for performing a consecutive clear bits count on an operand with an offset includes a plurality of logic circuits, each associated with a prioritized portion of the operand. Each logic circuit activates an all-zero signal when its respective portion of the operand consists of all zeros, performs a leading zero count on its respective portion of the operand, and generates a leading zero signal by offsetting its leading zero count with a first portion of the offset. Also, a priority encoder generates a signal encoding the priority of the highest priority inactive all-zero signal, and muxes select first and second portions of the leading zero signal associated with the highest priority inactive all-zero signal as a first portion of the consecutive clear bits count and a carryout selector signal, respectively, in accordance with the priority encoded signal. Further, adders generate a no-carryout signal by offsetting the priority encoded signal with a second portion of the offset, and generate a carryout signal by offsetting the priority encoded signal with the second portion of the offset and adding one. A mux then selects one of the no-carryout and carryout signals as a second portion of the consecutive clear bits count in accordance with the carryout selector signal.

Growing community of inventors

Pleasanton, CA, United States of America

Michael L Ott