Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
2000-06-02
2003-11-25
Ngo, Chuong Dinh (Department: 2124)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
Reexamination Certificate
active
06654776
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention pertains generally to microcomputer instruction sets. More particularly, the invention is a method and apparatus for computing leading zero count with offset using a parallel nibble calculation scheme.
2. The Prior Art
In certain microcomputer instruction sets such as the MAJC (Micro Architecture for Java Computing) architecture by Sun Microsystems®, a leading zero count with offset instruction is carried out. For example, when evaluation of the saturation of a fixed-length word is desired, the leading zero count with offset instruction provides the number of significant bits, allowing for an offset.
Leading zero count with offset (LZCO) instruction comprises counting the number of leading zeros in a first number and subtracting a second “offset” number from this count value.
FIG. 1
shows a LZCO instruction implementation
1
according to the prior art.
As noted above, in LZCO instruction, two input operands, identified as RS
1
(designated
2
) and RS
2
(designated as
3
), are provided. By way of example, RS
1
is depicted as a 32-bit number and RS
2
is depicted as a 5-bit number. The count of leading zeros in RS
1
must be determined. RS
2
provides the “offset” value with is subtracted from the count of leading zeros (determined from RS
1
).
The count of leading zeroes in RS
1
is determined by a conventional leading zero detector (LZD)
4
. The LZD
4
comprises software and/or circuitry to evaluate RS
1
and determine the count of leading zeros in RS
1
(designated as
5
). This count
5
is provided as an output from LZD
4
and in provided as a first input for the subtrator unit
6
.
The subtractor unit
6
has as its second input the RS
2
offset
3
. The subtractor unit
6
subtracts the RS
2
value
3
from the count of leading zeros (5) to generate a 6-bit number result (7).
It is desirable to provide an implementation which carries out this LZCO operation in a fast manner. The prior art algorithm, while providing the correct result (7), is carried out in a relatively slow manner because the LZD must complete its function before the subtraction can begin. These operations are carried out serially, maximizing the delay for the result.
Accordingly, there is a need for a method and apparatus which provides for faster calculation of leading zero count with offset instruction. The present invention satisfies these needs, as well as others, via a parallel nibble calculation scheme and generally overcomes the deficiencies found in the background art.
BRIEF DESCRIPTION OF THE INVENTION
The present invention is a method and apparatus for calculating leading zero count with offset (LZCO) instructions using a parallel nibble calculation scheme. The invention further relates to machine readable media on which are stored embodiments of the present invention. It is contemplated that any media suitable for retrieving instructions is within the scope of the present invention. By way of example, such media may take the form of magnetic, optical, or semiconductor media. The invention also relates to data structures that contain embodiments of the present invention, and to the transmission of data structures containing embodiments of the present invention.
The invention operates upon two input operands, identified as RS
1
and RS
2
. RS
1
is represented by a plurality of nibbles, each nibble comprising four bits. For example, if RS
1
comprises a thirty-two (32) bit number, RS
1
is represented by eight (8) nibbles. Each nibble has a corresponding nibble placement within RS
1
corresponding to a relative nibble order of significance. For example, in the 32-bit RS
1
example, Nibble
7
corresponds to bits
31
,
30
,
29
, and
28
of RS
1
, Nibble
6
corresponds to bits
27
,
26
,
25
, and
24
, Nibble
5
corresponds to bits
23
,
22
,
21
and
20
, and Nibble
0
corresponds to bits
3
,
2
,
1
and
0
. As will be readily apparent to those skilled in the art, each of the other nibbles
1
,
2
,
3
, and
4
corresponds to bits associated with the nibble's placement within RS
1
.
Each nibble has a corresponding relative nibble order of significance, such that nibbles having higher bits will have a higher order of significance than nibbles having lower bits. For example, Nibble
7
comprising bits
31
,
30
,
29
, and
28
will have a higher order of significance than Nibble
6
corresponding to bits
27
,
26
,
25
and
24
since bits
31
,
30
,
29
, and
28
have a higher order of significance than bits
27
,
26
,
25
and
24
. Accordingly, Nibble n will have a higher order of significance than Nibble (n−1).
The RS
2
operand is provided as an “offset” value. As noted above, the desired result of the LZCO operation produces is a value of RS
2
subtracted from the count of leading zeros in RS
1
. The present invention provides a parallel nibble calculation scheme to generate this result, as described herein.
According to a first embodiment of the invention, the method comprises calculating 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, and selecting 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.
According to a second embodiment of the invention, the apparatus comprises a select circuit which receives as its input RS
1
and produces an output; a lower two bits result calculator, having as its input RS
1
, RS
2
and the select circuit output, the lower two bits result calculator providing an output; and an upper bit result calculator, having as its input RS
2
, the select circuit output, and the lower two bits result calculator output.
The output of the lower two bits result calculator provides the lower two bits of the desired LZCO operation result and a carryout value. The output of the upper bit result calculator provides the upper remaining bits of the desired LZCO operation result.
It will be apparent to those skilled in the art having the benefit of this disclosure that the invention is also suitable for calculating a leading ones count with offset using the parallel nibble calculation scheme of the present invention. Additionally, the invention is also suitable for calculation of leading zero/one count with an add offset, rather than a subtract offset with trivial modification to the embodiments as described herein as would be apparent to those skilled in the art. It is further noted that the present invention further provides a leading zero/one detector where the offset operand (RS
2
) is zero (0).
An object of the invention is to provide a method and apparatus for carrying out LZCO instruction which overcomes the deficiencies in the prior art.
Another object of the invention is to provide a method and apparatus for carrying out LZCO instruction which uses a parallel nibble calculation scheme.
Further objects and advantages of the invention will be brought out in the following portions of the specification, wherein the detailed description is for the purpose of fully disclosing the preferred embodiment of the invention without placing limitations thereon.
REFERENCES:
patent: 4586154 (1986-04-01), Berry
patent: 4631696 (1986-12-01), Sakamoto
patent: 5568410 (1996-10-01), Bechade
patent: 5798952 (1998-08-01), Miller et al.
patent: 5798953 (1998-08-01), Lozano
patent: 5805486 (1998-09-01), Sharangpani
patent: 5894427 (1999-04-01), Chung
patent: 5940625 (1999-08-01), Smith
patent: 6195673 (2001-02-01), Park
patent: 6477552 (2002-11-01), Ott
Hu Ruey-Hsien
Ott Michael L.
Do Chat C.
Martine & Penilla LLP
Ngo Chuong Dinh
Sun Microsystems Inc.
LandOfFree
Method and apparatus for computing parallel leading zero... 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 computing parallel leading zero..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for computing parallel leading zero... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3136197