How to implenetment an efficient shifter

[Fano]

Hi.
I'm trying to implement a 32bits shifter (both shift left and
right).
with (synthesziable) VHDL. I've browsed a lot of examples but all are
shifting one bit data per clock period. I want my shifter shift
arbitrary bits (1~31 bits, decided by the input) in just one clock
period. How can I achieve that ?
Thanks in advance!

//BR
Fano

 

[fe]

Fano,
check for barrel shifter in google or this file for example.
http://www.csee.umbc.edu/help/VHDL/samples/bshift.vhdl

regards
fe

 

[ben cohen]

Hi.
I'm trying to implement a 32bits shifter (both shift left and
right).
with (synthesziable) VHDL. I've browsed a lot of examples but all are
shifting one bit data per clock period. I want my shifter shift
arbitrary bits (1~31 bits, decided by the input) in just one clock
period. How can I achieve that ?
Thanks in advance!

//BR
Fano

The shifter is called a "barrel shift".
Do a google group search on "barrel shift vhdl".
That was discussed extensively in the past, and several different
coding methods are discussed.
----------------------------------------------------------------------------
Ben Cohen Publisher, Trainer, Consultant (310) 721-4830
http://www.vhdlcohen.com/ (e-mail address removed)
Author of following textbooks:
* Using PSL/SUGAR with Verilog and VHDL
Guide to Property Specification Language for ABV, 2003 isbn
0-9705394-4-4
* Real Chip Design and Verification Using Verilog and VHDL, 2002 isbn
0-9705394-2-8
* Component Design by Example ", 2001 isbn 0-9705394-0-1
* VHDL Coding Styles and Methodologies, 2nd Edition, 1999 isbn
0-7923-8474-1
* VHDL Answers to Frequently Asked Questions, 2nd Edition, isbn
0-7923-8115
------------------------------------------------------------------------------

 

[Ulf Samuelsson]

Hi.
I'm trying to implement a 32bits shifter (both shift left and
right).
with (synthesziable) VHDL. I've browsed a lot of examples but all are
shifting one bit data per clock period. I want my shifter shift
arbitrary bits (1~31 bits, decided by the input) in just one clock
period. How can I achieve that ?
Thanks in advance!

//BR
Fano

The barrel shifter is basically 32 x 32 -> 1 mux,
You need probably 1024 logic elements just for the shifter,
and maybe more if there is routing congestion - very likely.
There are reasons why the FPGA designers avoid barrel shifter.
It is better to shift 0-3 times or 0..7 times before the full shift.

 

[Pieter Hulshoff]

The barrel shifter is basically 32 x 32 -> 1 mux,

You need probably 1024 logic elements just for the shifter,

Nah, assuming you have 4 input LUTs in your FPGA you'd get (per bit):
32 bits input + 5 bits selection = 37 bits =>
37/4 => 10 LUTs initial selection
10/4 => 3 LUTs second selection
3/4 => 1 LUT third selection
total = 14 LUTs, 3 level deep logic (sounds doable to me)
14*32 = 448 LUTs in total for the logic elements

In an ASIC you'd be using 4-1 muxes:
32/4 = 8 muxes initial selection
8/4 = 2 muxes second selection
2/4 = 1 mux (2 input would do) third selection
total = 11 muxes, 3 level deep logic
11*32 = 352 muxes in total, 32 of which can be 2-1 muxes

We've done 256 bits wide barrel shifters (input 512 bit, output 256 bit) at
155 MHz in ASICs without too many problems, so I don't see why this 32 bit
one should be a problem for an FPGA. Any idea on the clockspeed you need
this at?

Regards,

Pieter Hulshoff

 

[Pieter Hulshoff]

32 bits input + 5 bits selection = 37 bits =>

37/4 => 10 LUTs initial selection
10/4 => 3 LUTs second selection
3/4 => 1 LUT third selection
total = 14 LUTs, 3 level deep logic (sounds doable to me)
14*32 = 448 LUTs in total for the logic elements

I may have been a bit too optimistic here with regards to the flexibility of
the LUTs... Let's assume a worst case scenario where each LUT can only be
used as a 2-1 mux:
32/2 = 16 LUTs
16/2 = 8 LUTs
8/2 = 4 LUTs
4/2 = 2 LUTs
2/2 = 1 LUT
31*32 = 996 LUTs, 5 level deep logic
A good compiler will probably end up somewhere between 488 and 996 LUTs,
with 3 or 4 level deep logic. Unless this has to run at very high speeds, I
still don't see a problem in making this work.

Regards,

Pieter Hulshoff

 

[Ray Andraka]

That is the naive, hard, slow, and expensive way to do it. A 32 bit barrel
shift should be implemented as 5 layers of 32 2:1 muxes, for a total of
160 3 input logic elements. Each layer is selected by one bit of the
select code so that (for example) the first layer shifts by either 0 ro 16
bits, the next by 0 or 8 bits, the next by 0 or 4 bits, the next by 0 or 2
bits and the last by 0 or 1 bits. Each layer feeds the inputs of the next
layer. No reason to avoid it, this is not all that resource intensive
(more so than an adder, less so than a parallel multiply).

The barrel shifter is basically 32 x 32 -> 1 mux,
You need probably 1024 logic elements just for the shifter,
and maybe more if there is routing congestion - very likely.
There are reasons why the FPGA designers avoid barrel shifter.
It is better to shift 0-3 times or 0..7 times before the full shift.

--
Best Regards
Ulf at atmel dot com
These comments are intended to be my own opinion and they
may, or may not be shared by my employer, Atmel Sweden.

--
--Ray Andraka, P.E.
President, the Andraka Consulting Group, Inc.
401/884-7930 Fax 401/884-7950
email (e-mail address removed)
http://www.andraka.com

"They that give up essential liberty to obtain a little
temporary safety deserve neither liberty nor safety."
-Benjamin Franklin, 1759

 

[Ray Andraka]

Use the layered approach (it is an optimal merged tree). 2:1 muxes are most
efficient, even in an ASIC. With pipelining registers (ie a latency of 5
clocks), this structure can be run at pretty close to the max toggle frequency
of the FPGA. If this is a normalizing shift, then the shift decision at each
step is determined by the number of leading sign bits at that steps input.

Nah, assuming you have 4 input LUTs in your FPGA you'd get (per bit):
32 bits input + 5 bits selection = 37 bits =>
37/4 => 10 LUTs initial selection
10/4 => 3 LUTs second selection
3/4 => 1 LUT third selection
total = 14 LUTs, 3 level deep logic (sounds doable to me)
14*32 = 448 LUTs in total for the logic elements

In an ASIC you'd be using 4-1 muxes:
32/4 = 8 muxes initial selection
8/4 = 2 muxes second selection
2/4 = 1 mux (2 input would do) third selection
total = 11 muxes, 3 level deep logic
11*32 = 352 muxes in total, 32 of which can be 2-1 muxes

We've done 256 bits wide barrel shifters (input 512 bit, output 256 bit) at
155 MHz in ASICs without too many problems, so I don't see why this 32 bit
one should be a problem for an FPGA. Any idea on the clockspeed you need
this at?

Regards,

Pieter Hulshoff

--
--Ray Andraka, P.E.
President, the Andraka Consulting Group, Inc.
401/884-7930 Fax 401/884-7950
email (e-mail address removed)
http://www.andraka.com

"They that give up essential liberty to obtain a little
temporary safety deserve neither liberty nor safety."
-Benjamin Franklin, 1759

 

[fe]

Worst case for a simple left/right barrel shifter is : 5 level of 2-1 mux
per bit per direction + 1 level of 2-1 mux to select between direction (left
or right).
So for a 32 bit barrel shifter : 5x32=160 LUT for left shift + 5x32=160 for
right shift + 1x32=32 for direction --> 352 LUT total.
Synthesis tool will compact it (less than 352 lut).

regards
fe

 

[Ray Andraka]

Less than that. if it is a rotate, then left by N is the same as right bits-N.
If a shift so that 0's get shifted in lsb, or sign gets extended then you can
start with a shifter that is 3x the input width, with 0's in the bottom N bits
and extended sign in the top N bits. Note that the muxes for the extended sign
and the zeros will optimize out to reduce the size. This requires an additional
layer over what you had before, or roughly 6x32 = 192 luts, plus a few luts to
recode the select word if needed.

Worst case for a simple left/right barrel shifter is : 5 level of 2-1 mux
per bit per direction + 1 level of 2-1 mux to select between direction (left
or right).
So for a 32 bit barrel shifter : 5x32=160 LUT for left shift + 5x32=160 for
right shift + 1x32=32 for direction --> 352 LUT total.
Synthesis tool will compact it (less than 352 lut).

regards
fe

--
--Ray Andraka, P.E.
President, the Andraka Consulting Group, Inc.
401/884-7930 Fax 401/884-7950
email (e-mail address removed)
http://www.andraka.com

"They that give up essential liberty to obtain a little
temporary safety deserve neither liberty nor safety."
-Benjamin Franklin, 1759