Microprocessor Design/Shift and Rotate Blocks

Shift and Rotate

edit

Shift and rotate blocks are essential elements in most processors. They are useful on their own, but they also are used in multiplication and division modules. In a binary computer, a left shift has the same effect as a multiplication by 2, and a right shift has the same effect as a division by 2. Since shift and rotate operations perform much more quickly than multiplication and division, they are useful as a tool in program optimization.

Logical Shift

edit
   
A left logical shift A right logical shift

In a logical shift, the data is shifted in the appropriate direction, and a zero is shifted into the new location.

Arithmetic shift

edit
 
A right arithmetic shift

In an arithmetic shift, the data is shifted right so that the sign of the data item is preserved. This means that the MSB is the value that is shifted into the new position. An arithmetic left shift is the same as a logical left shift, and is therefore not shown here.

Rotations

edit
   
A left rotation A right rotation

A rotation is like a shift, except the bit shifted off the end of the register is then shifted into the new spot.

Fast Shift Implementations

edit

The above images in each section help to indicate a method to shift a register more quickly, at the expense of requiring additional hardware. Instead of having one register that attempts to shift in place, we have two registers in parallel, with wires connecting the various blocks together. When a shift is indicated, gates open that allow the data to pass from one register to the next, the proper number of spaces forward or backward.

In practice, fast shift blocks are implemented as a "barrel shifter". The barrel shifter includes several "levels" of multiplexers, each connected to the previous one by straight wires (wires that transfer the data without a shift), and wires that cause a shift by successive powers of two. For instance, the first level of shift would be 4 spaces, the next level would be 2 spaces, and the last level would be 1 space. In this way, the value of each shift level corresponds to the binary representation of the number of spaces to shift. This implementation makes for very fast shifters that can shift an arbitrary number of spaces in a single clock cycle.

Further reading

edit

32-Bit Barrel Shifter Implementation Using 74-Series Integrated Circuits