barrel shifter

[Hendrik Greving]

hi,

does anybody know where to obtain the algorithm of how to make a
synthesis of a constant barrel shifter, or knows a paper that deals with
this issue?

e.g. result = 00011101 << b

is optimized by combining the b input bits for the output "result"
instead of using multiplexers.

Regards,
Hendrik Greving

 

[Jason Zheng]

Hendrik Greving wrote:

hi,

does anybody know where to obtain the algorithm of how to make a
synthesis of a constant barrel shifter, or knows a paper that deals with
this issue?

e.g. result = 00011101 << b

is optimized by combining the b input bits for the output "result"
instead of using multiplexers.

Regards,
Hendrik Greving
perhaps a google search would've answered your question:

http://answers.google.com/answers/threadview?id=388350

 

[Hendrik Greving]

Jason Zheng wrote:

Hendrik Greving wrote:

hi,

does anybody know where to obtain the algorithm of how to make a
synthesis of a constant barrel shifter, or knows a paper that deals
with this issue?

e.g. result = 00011101 << b

is optimized by combining the b input bits for the output "result"
instead of using multiplexers.

Regards,
Hendrik Greving

perhaps a google search would've answered your question:


http://answers.google.com/answers/threadview?id=388350

Maybe it's not clear, my question aims at how to optimize or to find a
solution for a constant barrel shifter.

Regards,
Hendrik

 

[Jason Zheng]

Hendrik Greving wrote:

Jason Zheng wrote:

Hendrik Greving wrote:

hi,

does anybody know where to obtain the algorithm of how to make a
synthesis of a constant barrel shifter, or knows a paper that deals
with this issue?

e.g. result = 00011101 << b

is optimized by combining the b input bits for the output "result"
instead of using multiplexers.

Regards,
Hendrik Greving


perhaps a google search would've answered your question:


http://answers.google.com/answers/threadview?id=388350


Maybe it's not clear, my question aims at how to optimize or to find a
solution for a constant barrel shifter.

Regards,
Hendrik
I think a constant barrel shifter would probably resemble a priority

encoder. This is a special case:

result = 32'b1 << b;

Why bother getting the algorithm? I bet it's treated just like a
combinational encoder in most synthesis tools.

~jz

 

[Hendrik Greving]

Jason Zheng wrote:

Hendrik Greving wrote:

Jason Zheng wrote:

Hendrik Greving wrote:

hi,

does anybody know where to obtain the algorithm of how to make a
synthesis of a constant barrel shifter, or knows a paper that deals
with this issue?

e.g. result = 00011101 << b

is optimized by combining the b input bits for the output "result"
instead of using multiplexers.

Regards,
Hendrik Greving



perhaps a google search would've answered your question:


http://answers.google.com/answers/threadview?id=388350



Maybe it's not clear, my question aims at how to optimize or to find a
solution for a constant barrel shifter.

Regards,
Hendrik

I think a constant barrel shifter would probably resemble a priority
encoder. This is a special case:

result = 32'b1 << b;

Why bother getting the algorithm? I bet it's treated just like a
combinational encoder in most synthesis tools.

~jz
Hi,

I'm looking for a quick way for finding a complexity estimate. I found
that mostly it's a combination of the b-bits of example above. So you
think the optimization are drawn by the low level optimizations of the
synthesis tool and too hard to estimate in high level?

Regards,
Hendrik

 

[Jason Zheng]

Hendrik Greving wrote:

Jason Zheng wrote:

Hendrik Greving wrote:

Jason Zheng wrote:

Hendrik Greving wrote:

hi,

does anybody know where to obtain the algorithm of how to make a
synthesis of a constant barrel shifter, or knows a paper that deals
with this issue?

e.g. result = 00011101 << b

is optimized by combining the b input bits for the output "result"
instead of using multiplexers.

Regards,
Hendrik Greving




perhaps a google search would've answered your question:


http://answers.google.com/answers/threadview?id=388350




Maybe it's not clear, my question aims at how to optimize or to find
a solution for a constant barrel shifter.

Regards,
Hendrik


I think a constant barrel shifter would probably resemble a priority
encoder. This is a special case:

result = 32'b1 << b;

Why bother getting the algorithm? I bet it's treated just like a
combinational encoder in most synthesis tools.

~jz

Hi,

I'm looking for a quick way for finding a complexity estimate. I found
that mostly it's a combination of the b-bits of example above. So you
think the optimization are drawn by the low level optimizations of the
synthesis tool and too hard to estimate in high level?

Regards,
Hendrik
Yes, but I don't work on any synthesis tools; that's just my gut feeling.

good luck.

 

Assuming the result is 1 bit, your "barrel shifter" turns into a
multiplexer with b connected to the select lines and the constant
connected to the data inputs. Then it can be optimized by propagating
the constants and combining terms.

Another way of looking at it is that you are computing a particular
logic function of the bits of b. The constant value is the truth-table
of that logic function (with the rightmost bit being the first entry),
and the multiplexer uses the value of b to select the appropriate table
entry from the truth-table. As in a truth-table, wherever there is a 1
in the constant, the corresponding minterm gets included (in the
multiplexer version, the multiplexer provides all the minterms of b,
and a data bit value of 1 gates that minterm to be included in the
result). So the optimal logic is just the minimum logic to compute
that particular function of the bits of b. The amount of logic
required is going to depend on the constant value that you provided
(i.e. the complexity of the truth-table).

If the synthesis optimizer is doing a good job, it should end up with
the same result as if you had specified that logic operation in a more
conventional way. For example, if you have a 2-bit b, and specify

result = 4'b1110 << b;

it should get the same result as if you said

case (b)
2'b00: result = 0;
2'b01: result = 1;
2'b10: result = 1;
2'b11: result = 1;
endcase

which should reduce to a 2-input OR-gate, since that is the truth-table
of an OR-gate.