Barrel shifter

Schematic of a 4-bit crossbar barrel shifter. x denotes input bits and y denotes output bits.

A barrel shifter is a digital circuit that can shift a data word by a specified number of bits in one clock cycle. It can be implemented as a sequence of multiplexers (mux.), and in such an implementation the output of one mux is connected to the input of the next mux in a way that depends on the shift distance.

For example, take a four-bit barrel shifter, with inputs A, B, C and D. The shifter can cycle the order of the bits ABCD as DABC, CDAB, or BCDA; in this case, no bits are lost. That is, it can shift all of the outputs up to three positions to the right (and thus make any cyclic combination of A, B, C and D). The barrel shifter has a variety of applications, including being a useful component in microprocessors (alongside the ALU).

Implementation

A barrel shifter is often implemented as a cascade of parallel 2×1 multiplexers. For a 8-bit barrel shifter, two intermediate signals are used which shifts by four and two bits, or passes the same data, based on the value of S[2] and S[1]. This signal is then shifted by another multiplexer, which is controlled by S[0]:

 int1  = IN       , if S[2] == 0
       = IN   << 4, if S[2] == 1
 int2  = int1     , if S[1] == 0
       = int1 << 2, if S[1] == 1
 OUT   = int2     , if S[0] == 0
       = int2 << 1, if S[0] == 1

Larger barrel shifters have additional stages.

Cost

The number of multiplexers required for an n-bit word is $\scriptstyle n\log_2n$ .^[1] Five common word sizes and the number of multiplexers needed are listed below:

128-bit — $\scriptstyle 128\times\log_2(128) = 128\times7 = 896$
64-bit — $\scriptstyle 64\times\log_2(64) = 64\times6 = 384$
32-bit — $\scriptstyle 32\times\log_2(32) = 32\times5 = 160$
16-bit — $\scriptstyle 16\times\log_2(16) = 16\times4 = 64$
8-bit — $\scriptstyle 8\times\log_2(8) = 8\times3 = 24$

Cost of critical path in FO4 (estimated, without wire delay):

32-bit: from 18 FO4 to 14 FO4^[2]

Uses

A common usage of a barrel shifter is in the hardware implementation of floating-point arithmetic. For a floating-point add or subtract operation, the significands of the two numbers must be aligned, which requires shifting the smaller number to the right, increasing its exponent, until it matches the exponent of the larger number. This is done by subtracting the exponents, and using the barrel shifter to shift the smaller number to the right by the difference, in one cycle. If a simple shifter were used, shifting by n bit positions would require n clock cycles.

References

↑ Kroening, D.; Strichman, Ofer (2008). Decision Procedures. Springer. p.159.
↑ http://www.realworldtech.com/page.cfm?ArticleID=RWT081502231107&p=4

External links

University of Hamburg for a useful Java Barrel shifter.
Xilinx Application Note Implementation of Barrel shifter using Xilinx FPGAs.

CPU technologies

Architecture	Von Neumann Harvard (Modified Harvard) Dataflow TTA

Instruction set	ASIP CISC RISC EDGE EPIC MISC OISC VLIW NISC ZISC TRIPS Comparison

Word size	1-bit 4-bit 8-bit 9-bit 10-bit 12-bit 15-bit 16-bit 18-bit 22-bit 24-bit 25-bit 26-bit 27-bit 31-bit 32-bit 33-bit 34-bit 36-bit 39-bit 40-bit 48-bit 50-bit 60-bit 64-bit 128-bit 256-bit 512-bit variable

Execution	Instruction pipelining Bubble Operand forwarding Out-of-order execution Register renaming Speculative execution Branch predictor Memory dependence prediction Hazards

Parallel level	Bit Bit-serial Word Instruction Scalar Superscalar Task Thread Process Data Vector Memory

Multithreading	Temporal Simultaneous Preemptive Cooperative

Flynn's taxonomy	SISD SIMD MISD MIMD SPMD Addressing mode

Types	Digital signal processor (DSP) GPGPU Microcontroller Physics processing unit System on a chip (SoC) Cellular

Components	Address generation unit (AGU) Arithmetic logic unit (ALU) Barrel shifter Floating-point unit (FPU) Back-side bus Multiplexer Demultiplexer Registers Memory management unit (MMU) Translation lookaside buffer (TLB) Cache Register file Microcode Control unit Clock rate

Power management	APM ACPI Dynamic frequency scaling Dynamic voltage scaling Clock gating

CPU hardware security	Non-executable memory (NX bit) Bounds checking (Intel MPX) Hardware restriction (firmware) Trusted Execution Technology Secure cryptoprocessor Hardware security module Hengzhi chip

This article is issued from Wikipedia - version of the Sunday, February 07, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.