Hi xavier687-ga,
Data shifting is a required element of many key computer operations,
from address generation to arithmetic functions. Shifting a single
data bit one field at a time can be a slow process, however. This is
where a barrel shifter comes in.
A barrel shifter is a combinational logic device/circuit that can
"shift or rotate a data word by any number of bits in a single
operation."
http://computing-dictionary.thefreedictionary.com/barrel%20shifter
Basically, a barrel shifter works to shift data by incremental stages
which avoids extra clocks to the register and reduces the time spent
shifting or rotating data (the specified number of bits are
moved/shifted/rotated the desired number of bit positions in a single
clock cycle). A barrel shifter is commonly used in computer-intensive
applications, such as Digital Signal Processing (DSP), and is useful
for most applications that shift data left or right - a normal style
for C programming code.
Yes, a barrel shifter can be used to rotate data. Rotation (right) is
similar to shifting in that it moves bits to the left. With rotation,
however, bits which "fall off" the left side get tacked back on the
right side as lower order bits, while in shifting the empty space in
the lower order bits after shifting is filled with zeros.
http://shay.ecn.purdue.edu/~ee495al/Labs/Lab2/prelab/x58.html
"A barrel shifter is a combinational logic circuit with n data inputs,
n data outputs, and a set of control inputs that specify how to shift
the data between input and output. A barrel shifter that is part of a
microprocessor CPU can typically specify the direction of shift (left
or right), the type of shift (circular, arithmetic, or logical), and
the amount of shift (typically 1 to n-1 bits, but sometimes 1 to n
bits)."
http://www.ddpp.com/DDPP3_mkt/c06samp1.pdf (good graphs and examples
of a 16-bit barrel shifter)
"A four -input barrel shifter has four data inputs, four data outputs
and two control inputs that specify rotation by 0, 1, 2 or 3
positions. A simple approach would use four 4-input multiplexers,
since each output can receive data from any input. This approach
yields the best solution only if the select lines can be pipelined,
and the 4-input multiplexer design described above is used. The
combination barrel shifter can be implemented in one level of four
CLBs...."
http://direct.xilinx.com/bvdocs/appnotes/xapp026.pdf
"The action of a barrel shifter can be emulated in software, but this
takes valuable time probably not available in real-time video or audio
applications. The hardware barrel shifter is becoming a popular
feature on the latest MCUs [microcontrollers]."
http://www.electronicproducts.com/ShowPage.asp?SECTION=3700&PRIMID=&FileName=sepmot1.sep2001
Here is an example of a 32-bit cascadable barrel shifter "designed for
use in floating-point normalization, word pack/unpack, field
extraction and similar applications":
http://www.logicdevices.com/ps/obsolete/pdf/lsh32.pdf
I hope this has satisfactorily answered your question. If you need
something explained further, please let me know by posting a request
for clarification.
Regards,
--inquisitivega |
Clarification of Answer by
inquisitive-ga
on
16 Aug 2004 06:22 PDT
Hi xavier897-ga,
Just wanted to add some further information on the use and history of
the barrel shift algorithm and barrel shifter hardware:
Introduction of the Barrel Shifter in the Pentium 386
"The world of home computers didn't really become interesting until
late 1986 when Intel released its 3rd generation chip - the 80386, or
simply the 386....Both chips [Motorola countered the Intel 386 with
its 68030 chip] also introduced something known as a barrel shifter, a
circuit in the chip which can shift or rotate any 32-bit number in one
clock cycle. Something used often by many different machine language
instructions."
http://www.emulators.com/docs/pentium_1.htm
Lack of Barrel Shifter in the Pentium 4
The removal of the barrel shifter from Intel's P4 design (the barrel
shift algorithm is implemented in the code instead of in the
hardware)is blamed by most for its slowness.
"It so happens that these bit rotates are at the heart of the RC5
algorithm [a fast block cipher used in key expansion, encryption, and
decryption], being executed hundreds of times for each key checked,
and the poor cycle count for this instruction on the P4 renders it so
slow at this algorithm."
http://lists.distributed.net/pipermail/rc5/2003-September/040144.html
"Again, as an example, the Athlon and K5 and Pentium-III benefit in
RC5 work because they implimented a "barrel shifter" in hardware - RC5
relies a LOT on one particular instruction that uses that barrel
shifter. The P4 suffers a LOT from having it's barrel shifter
implimented in microcode, which makes that particular instruction a
LOT slower."
http://www.mersenneforum.org/archive/index.php/t-1317.html
Barrel Shifter Patents
Numeric Data Processor - U.S. Patent 4,338,675, Palmer, et al. (Intel
Corporation) July 6, 1982 "The numeric processor also includes a
programmable shifter capable of arbitrary numbers of bit and byte
shifts in a single clock cycle."
http://patft.uspto.gov/netacgi/nph-Parser?Sect2=PTO1&Sect2=HITOFF&p=1&u=%2Fnetahtml%2Fsearch-bool.html&r=1&f=G&l=50&d=PALL&RefSrch=yes&Query=PN%2F4338675
Patent for a Barrel shifter circuit having rotation function - U.S.
Patent 5,155,698, Niimi, October 13, 1992
http://patft.uspto.gov/netacgi/nph-Parser?Sect2=PTO1&Sect2=HITOFF&p=1&u=%2Fnetahtml%2Fsearch-bool.html&r=1&f=G&l=50&d=PALL&RefSrch=yes&Query=PN%2F5155698
Patent for a Bi-Directional Barrel Shifter - U.S. Patent 5,465,223,
Nishimura (inventor), November 7, 1995
http://patents.nimblewisdom.com/patent/5465223-Barrel-shifter
Regards,
--inquisitivega
|
Clarification of Answer by
inquisitive-ga
on
16 Aug 2004 18:38 PDT
Hi xavier687-ga,
First of all, thank you so much for the wonderful feedback and the
additional tip. That made my day!
As for your question on the patent application, I can't promise to
know the answer without seeing the question, but I promise to do my
absolute best to see that I provide the answer you require. If, for
some reason, I can't answer it properly, I will honestly tell you that
as well.
Yes, I will be available on 8/17 and will look for your question. You
can post the question to my attention if you would like - just put
"For inquisitive-ga" in the subject line and the other Google Answers
researchers will leave the question for me to answer.
Thanks again!
--inquisitivega
|
