Electrical computers and digital data processing systems: input/ – Intrasystem connection – Bus access regulation
Reexamination Certificate
1999-01-14
2001-05-15
Thai, Xuan M. (Department: 2781)
Electrical computers and digital data processing systems: input/
Intrasystem connection
Bus access regulation
C710S065000, C712S204000
Reexamination Certificate
active
06233642
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Technical Field
The present invention relates in general to rotator circuits in processors and in particular to wiring rotator circuits within a processor. Still more particularly, the present invention relates to minimizing the input routing required in wiring a 64-bit rotator circuit.
2. Description of the Related Art
Rotate operations are special cases of shift operations in which “end-around,” the process of copying bits shifted off one end of an operand into the other end, is employed. A simple example of rotating a 64-bit operand is shown in the two lines below, with the operand given in the first line and the result given in the second:
01000011 00011111 01010011 00001110 10110111 01010101 01111101 01001011
01100011 11101010 01100001 11010110 11101010 10101111 10101001 01101000
The 64-bit operand in the first line has been rotated 5 positions to the left in the second line. Alternate bytes of the “before” operand have been italicized in both lines for emphasis.
In a 64-bit architecture, it is necessary to perform rotate operations which are from 0 to 63 bits in offset. Rotate operations are commonly performed by an array
502
of multiplexer circuits
504
as shown in FIG.
5
. Each multiplexer
504
provides the shifting for a single bit position of the output, which requires that the full set of 64 input signals be routed to each multiplexer
504
in array
502
to accomplish a rotate of 0-63 positions. This large number of inputs presents significant wiring challenges in addition to obstacles to efficient use of circuit area.
The most straightforward method for wiring a 64-bit rotator is to route all 64 input to each simple multiplexer structure as shown in FIG.
5
. The downside of this approach is that the entire rotator structure would be very short in the vertical dimension and very long in the horizontal dimension—an extremely poor aspect ratio—as a result of forming 64 side-by-side 64-input multiplexers. Additionally, it is impractical to build a circuit primitive providing the functionality of a 64-bit multiplexer utilizing only a single stage of circuitry.
It would be desirable, therefore, to provide a solution to the poor aspect ratio which a 64-bit rotator circuit would naturally tend to assume. It would further be advantageous for the solution to be consistent with use of multiple stage of circuitry for the functionality of a 64-input multiplexer.
SUMMARY OF THE INVENTION
It is therefore one object of the present invention to provide an improved rotator circuit for processors.
It is another object of the present invention to provide an improved method and system for wiring rotator circuits within a processor.
It is yet another object of the present invention to provide a method and system for minimizing the input routing required in wiring a 64-bit rotator circuit.
The foregoing objects are achieved as is now described. Each bitslice multiplexing structure of a rotator circuit is configured as a plurality of first stage 8:1 multiplexers each receiving eight of the rotator circuits as inputs and one second stage 8:1 multiplexer receiving the outputs of the first-stage multiplexers are inputs. To achieve the desired functionality with a single set of shift input signals, the rotator inputs to the first-stage multiplexers are changed for different bitslice multiplexing structures within the rotator, and the connection of the first-stage multiplexer outputs to the second-stage multiplexer inputs are changed for different groups of bitslice multiplexing structures. The first-stage multiplexers are positioned between two input buses running across the entire width of the rotator circuit. Any input of the first-stage multiplexer may be connected to an input signal conductor within the input buses above or below the first-stage multiplexer, and the input buses and the first-stage multiplexers are distributed on opposite sides of the second-stage multiplexer. This limits the number of wires required in one metallization level for the vertical direction to twelve at any horizontal cross-section of the bitslice multiplexing structure. The resulting rotator circuit has an improved aspect ratio, more efficient circuit area usage, and better overall circuit performance for performing rotate operations from 0 to 63 bits on 64-bit operands.
The above as well as additional objects, features, and advantages of the present invention will become apparent in the following detailed written description.
REFERENCES:
patent: 4937775 (1990-06-01), Engeler et al.
patent: 5410677 (1995-04-01), Roskowski et al.
patent: 5581718 (1996-12-01), Grochowski
patent: 5604498 (1997-02-01), Park
patent: 5764165 (1998-06-01), Buch
patent: 5845100 (1998-12-01), Gupta et al.
patent: 6112018 (2000-08-01), Tran et al.
“Method forlmplementing a Customized DCVS Circuit Design for an N-Bit Rotator”; IBM Technical Disclosure Bulletin, Jun. 1, 1988; US; vol. 31, No. 1; pp. 303-307, Jun. 1988.
Martens David James
Yaniv Elan Tsvi
England Anthony V. S.
Felsman Bradley Vaden Gunter & Dillon, LLP
International Business Machines - Corporation
Thai Xuan M.
LandOfFree
Method of wiring a 64-bit rotator to minimize area and... 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 of wiring a 64-bit rotator to minimize area and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of wiring a 64-bit rotator to minimize area and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2531112