# why shift is slower than integer multiply shift ,integer multiply

**URL:** <https://forums.developer.nvidia.com/t/why-shift-is-slower-than-integer-multiply-shift-integer-multiply/17395>\
**Category:** CUDA Programming and Performance\
**Created:** [June 29, 2010, 6:06am UTC](https://forums.developer.nvidia.com/t/why-shift-is-slower-than-integer-multiply-shift-integer-multiply/17395 "2010-06-29T06:06:42Z")\
**Posts on this page:** 20\
**Page:** 1

<div class="post-metadata">

**Author:** ![azaonline](https://developer.download.nvidia.com/images/forums/profile-default-devtalk-84.png) [@azaonline](https://forums.developer.nvidia.com/u/azaonline)\
**Post date:** [June 29, 2010, 6:06am UTC](https://forums.developer.nvidia.com/t/why-shift-is-slower-than-integer-multiply-shift-integer-multiply/17395/1 "2010-06-29T06:06:42Z")

</div>

we know integer multiply by 2^n can be replaced by shift operation, which is faster.

As version 1 & 2 shown, I replace tid\*4 by tid\<\<2(I think it can speedup). But the actual result shows version 1 is faster than version 2. I have tested many times.

I was confused.

why shift is slower than integer multiply? my GPU is G260

**uint tid**

**version 1**

des[tid \* 4 + 0] = …;

des[tid \* 4 + 1] = …;

des[tid \* 4 + 2] = …;

des[tid \* 4 + 3] = …;

\_\_syncthreads();

…

\_\_syncthreads();

float4 d;

d.x = \_\_fdividef(des[tid \* 4 + 0], len[0]);

d.y = \_\_fdividef(des[tid \* 4 + 1], len[0]);

d.z = \_\_fdividef(des[tid \* 4 + 2], len[0]);

d.w= \_\_fdividef(des[tid \* 4 + 3], len[0]);

d\_des[idx \* 16 + tid] = d;

**version 2**

des[(tid\<\<2)] = …;

des[(tid\<\<2) + 1] = …;

des[(tid\<\<2) + 2] = …;

des[(tid\<\<2) + 3] = …;

\_\_syncthreads();

…

\_\_syncthreads();

float4 d;

d.x = \_\_fdividef(des[(tid\<\<2)], len[0]);

d.y = \_\_fdividef(des[(tid\<\<2) + 1], len[0]);

d.z = \_\_fdividef(des[(tid\<\<2) + 2], len[0]);

d.w = \_\_fdividef(des[(tid\<\<2) + 3], len[0]);

d\_des[(idx\<\<4) + tid] = d;

---

<div class="post-metadata">

**Author:** ![tera](https://developer.download.nvidia.com/images/forums/profile-default-devtalk-84.png) [@tera](https://forums.developer.nvidia.com/u/tera)\
**Post date:** [June 29, 2010, 7:03am UTC](https://forums.developer.nvidia.com/t/why-shift-is-slower-than-integer-multiply-shift-integer-multiply/17395/2 "2010-06-29T07:03:37Z")

</div>

There should be no difference at all as the compiler does this substitution for you anyway. How are you timing your code?

---

<div class="post-metadata">

**Author:** ![tera](https://developer.download.nvidia.com/images/forums/profile-default-devtalk-84.png) [@tera](https://forums.developer.nvidia.com/u/tera)\
**Post date:** [June 29, 2010, 7:03am UTC](https://forums.developer.nvidia.com/t/why-shift-is-slower-than-integer-multiply-shift-integer-multiply/17395/3 "2010-06-29T07:03:37Z")

</div>

There should be no difference at all as the compiler does this substitution for you anyway. How are you timing your code?

---

<div class="post-metadata">

**Author:** ![azaonline](https://developer.download.nvidia.com/images/forums/profile-default-devtalk-84.png) [@azaonline](https://forums.developer.nvidia.com/u/azaonline)\
**Post date:** [June 29, 2010, 7:14am UTC](https://forums.developer.nvidia.com/t/why-shift-is-slower-than-integer-multiply-shift-integer-multiply/17395/4 "2010-06-29T07:14:43Z")

</div>

I use “cudaEvent\_t start, stop” for timing as followed

cudaEventRecord(start, 0);

…

cudaEventRecord(stop, 0);

cudaEventSynchronize(stop);

cudaEventElapsedTime(&time, start, stop);

and If i use \_\_mul24(tid,4) instead of tid \* 4, whether thay are also no difference?

> [@](#):
>
> There should be no difference at all as the compiler does this substitution for you anyway. How are you timing your code?

---

<div class="post-metadata">

**Author:** ![azaonline](https://developer.download.nvidia.com/images/forums/profile-default-devtalk-84.png) [@azaonline](https://forums.developer.nvidia.com/u/azaonline)\
**Post date:** [June 29, 2010, 7:14am UTC](https://forums.developer.nvidia.com/t/why-shift-is-slower-than-integer-multiply-shift-integer-multiply/17395/5 "2010-06-29T07:14:43Z")

</div>

I use “cudaEvent\_t start, stop” for timing as followed

cudaEventRecord(start, 0);

…

cudaEventRecord(stop, 0);

cudaEventSynchronize(stop);

cudaEventElapsedTime(&time, start, stop);

and If i use \_\_mul24(tid,4) instead of tid \* 4, whether thay are also no difference?

> [@](#):
>
> There should be no difference at all as the compiler does this substitution for you anyway. How are you timing your code?

---

<div class="post-metadata">

**Author:** ![Sylvain\_Collange](https://developer.download.nvidia.com/images/forums/profile-default-devtalk-84.png) [@Sylvain\_Collange](https://forums.developer.nvidia.com/u/Sylvain_Collange)\
**Post date:** [June 29, 2010, 8:54am UTC](https://forums.developer.nvidia.com/t/why-shift-is-slower-than-integer-multiply-shift-integer-multiply/17395/6 "2010-06-29T08:54:18Z")

</div>

You might want to look at the assembly generated with decuda.

Three things to consider:

- There is a MAD instruction which can compute a \* b + c (multiply is 24x24-bit only on SM 1.x devices), but the instruction doing a \>\> b + c only exists on SM 2.0 devices (Fermi).
- SM 1.x devices have special registers and instructions to deal with addresses.
- At the hardware level, addresses are in bytes.

So the compiler has to multiply your addresses by 4 (or shift by 2) anyways.  
It is likely that in the first case,  
des[tid \* 4 + 3] = …;  
is first turned into a store at byte [des + (tid \* 4 + 3) \* 4],  
then optimized as [des + tid \* 16 + 12],  
then finally as [des + tid \<\< 4 + 12].

I suspect what happens is: by using an unusual idiom, you prevent the compiler from inferring what you mean, and applying distributivity to fuse both mulitplications/shifts together.  
So just stick with multiplication…  
Be sure that if a simple and widely-known optimization can be applied safely and has a benefit in every case, then the compiler will use it…

---

<div class="post-metadata">

**Author:** ![Sylvain\_Collange](https://developer.download.nvidia.com/images/forums/profile-default-devtalk-84.png) [@Sylvain\_Collange](https://forums.developer.nvidia.com/u/Sylvain_Collange)\
**Post date:** [June 29, 2010, 8:54am UTC](https://forums.developer.nvidia.com/t/why-shift-is-slower-than-integer-multiply-shift-integer-multiply/17395/7 "2010-06-29T08:54:18Z")

</div>

You might want to look at the assembly generated with decuda.

Three things to consider:

- There is a MAD instruction which can compute a \* b + c (multiply is 24x24-bit only on SM 1.x devices), but the instruction doing a \>\> b + c only exists on SM 2.0 devices (Fermi).
- SM 1.x devices have special registers and instructions to deal with addresses.
- At the hardware level, addresses are in bytes.

So the compiler has to multiply your addresses by 4 (or shift by 2) anyways.  
It is likely that in the first case,  
des[tid \* 4 + 3] = …;  
is first turned into a store at byte [des + (tid \* 4 + 3) \* 4],  
then optimized as [des + tid \* 16 + 12],  
then finally as [des + tid \<\< 4 + 12].

I suspect what happens is: by using an unusual idiom, you prevent the compiler from inferring what you mean, and applying distributivity to fuse both mulitplications/shifts together.  
So just stick with multiplication…  
Be sure that if a simple and widely-known optimization can be applied safely and has a benefit in every case, then the compiler will use it…

---

<div class="post-metadata">

**Author:** ![wwa](https://developer.download.nvidia.com/images/forums/profile-default-devtalk-84.png) [@wwa](https://forums.developer.nvidia.com/u/wwa)\
**Post date:** [June 29, 2010, 11:04am UTC](https://forums.developer.nvidia.com/t/why-shift-is-slower-than-integer-multiply-shift-integer-multiply/17395/8 "2010-06-29T11:04:44Z")

</div>

See TABLE III of [Demystifying GPU Microarchitecture through Microbenchmarking](http://www.eecg.toronto.edu/~myrto/gpuarch-ispass2010.pdf)  
The throughput of shl/shr is 7.9 with 24 cycles of latency while integer mul’s is 1.7 and 96 cycles latency - there’s no way a mul is faster. It had to be optimized by compiler anyway as Sylvain said.  
(Also note the paradox: floating point mul’s throughput is 11.2 so float mul IS kind of faster than bitwise functions)

---

<div class="post-metadata">

**Author:** ![wwa](https://developer.download.nvidia.com/images/forums/profile-default-devtalk-84.png) [@wwa](https://forums.developer.nvidia.com/u/wwa)\
**Post date:** [June 29, 2010, 11:04am UTC](https://forums.developer.nvidia.com/t/why-shift-is-slower-than-integer-multiply-shift-integer-multiply/17395/9 "2010-06-29T11:04:44Z")

</div>

See TABLE III of [Demystifying GPU Microarchitecture through Microbenchmarking](http://www.eecg.toronto.edu/~myrto/gpuarch-ispass2010.pdf)  
The throughput of shl/shr is 7.9 with 24 cycles of latency while integer mul’s is 1.7 and 96 cycles latency - there’s no way a mul is faster. It had to be optimized by compiler anyway as Sylvain said.  
(Also note the paradox: floating point mul’s throughput is 11.2 so float mul IS kind of faster than bitwise functions)

---

<div class="post-metadata">

**Author:** ![Sylvain\_Collange](https://developer.download.nvidia.com/images/forums/profile-default-devtalk-84.png) [@Sylvain\_Collange](https://forums.developer.nvidia.com/u/Sylvain_Collange)\
**Post date:** [June 29, 2010, 11:53am UTC](https://forums.developer.nvidia.com/t/why-shift-is-slower-than-integer-multiply-shift-integer-multiply/17395/10 "2010-06-29T11:53:46Z")

</div>

> [@](#):
>
> The throughput of shl/shr is 7.9 with 24 cycles of latency while integer mul’s is 1.7 and 96 cycles latency - there’s no way a mul is faster.

It can be faster, but only under the following conditions:

- The compiler can ensure that both operands fit into 24 bits.

- The mul is followed by an add.

- We’re running on a SM 1.x device.

Strangely enough, they all seem to apply in the OP case.

Float mul being faster than 32-bit int mul (on SM 1.x) makes sense: a float multiplication only requires a 24x24-bit multiplier, which is roughly twice as small as a 32x32-bit multiplier…

---

<div class="post-metadata">

**Author:** ![Sylvain\_Collange](https://developer.download.nvidia.com/images/forums/profile-default-devtalk-84.png) [@Sylvain\_Collange](https://forums.developer.nvidia.com/u/Sylvain_Collange)\
**Post date:** [June 29, 2010, 11:53am UTC](https://forums.developer.nvidia.com/t/why-shift-is-slower-than-integer-multiply-shift-integer-multiply/17395/11 "2010-06-29T11:53:46Z")

</div>

> [@](#):
>
> The throughput of shl/shr is 7.9 with 24 cycles of latency while integer mul’s is 1.7 and 96 cycles latency - there’s no way a mul is faster.

It can be faster, but only under the following conditions:

- The compiler can ensure that both operands fit into 24 bits.

- The mul is followed by an add.

- We’re running on a SM 1.x device.

Strangely enough, they all seem to apply in the OP case.

Float mul being faster than 32-bit int mul (on SM 1.x) makes sense: a float multiplication only requires a 24x24-bit multiplier, which is roughly twice as small as a 32x32-bit multiplier…

---

<div class="post-metadata">

**Author:** ![wwa](https://developer.download.nvidia.com/images/forums/profile-default-devtalk-84.png) [@wwa](https://forums.developer.nvidia.com/u/wwa)\
**Post date:** [June 29, 2010, 1:24pm UTC](https://forums.developer.nvidia.com/t/why-shift-is-slower-than-integer-multiply-shift-integer-multiply/17395/12 "2010-06-29T13:24:32Z")

</div>

> [@](#):
>
> It can be faster, but only under the following conditions:
> 
> - The compiler can ensure that both operands fit into 24 bits.
> 
> - The mul is followed by an add.
> 
> - We’re running on a SM 1.x device.
> 
> Strangely enough, they all seem to apply in the OP case.
> 
> Float mul being faster than 32-bit int mul (on SM 1.x) makes sense: a float multiplication only requires a 24x24-bit multiplier, which is roughly twice as small as a 32x32-bit multiplier…

You’re right, I totally forgot about mad24.

here’s the benchmark:

[codebox]mov.b32 $r62, %clock

mad24.lo.u32.u16.u16.u32 $r1, $r0.hi, $r0.lo, $r0

add.b32 $r3,$r0,$r0 //kill forwarding

add.b32 $r2,$r1,$1 //cause RAW stall

mov.b32 $r63, %clock[/codebox]

It executes 40 cycles, which reveals true mad24 latency of 40-8-8=24 cycles, believe it or not.

Also true with floating mul.

---

<div class="post-metadata">

**Author:** ![wwa](https://developer.download.nvidia.com/images/forums/profile-default-devtalk-84.png) [@wwa](https://forums.developer.nvidia.com/u/wwa)\
**Post date:** [June 29, 2010, 1:24pm UTC](https://forums.developer.nvidia.com/t/why-shift-is-slower-than-integer-multiply-shift-integer-multiply/17395/13 "2010-06-29T13:24:32Z")

</div>

> [@](#):
>
> It can be faster, but only under the following conditions:
> 
> - The compiler can ensure that both operands fit into 24 bits.
> 
> - The mul is followed by an add.
> 
> - We’re running on a SM 1.x device.
> 
> Strangely enough, they all seem to apply in the OP case.
> 
> Float mul being faster than 32-bit int mul (on SM 1.x) makes sense: a float multiplication only requires a 24x24-bit multiplier, which is roughly twice as small as a 32x32-bit multiplier…

You’re right, I totally forgot about mad24.

here’s the benchmark:

[codebox]mov.b32 $r62, %clock

mad24.lo.u32.u16.u16.u32 $r1, $r0.hi, $r0.lo, $r0

add.b32 $r3,$r0,$r0 //kill forwarding

add.b32 $r2,$r1,$1 //cause RAW stall

mov.b32 $r63, %clock[/codebox]

It executes 40 cycles, which reveals true mad24 latency of 40-8-8=24 cycles, believe it or not.

Also true with floating mul.

---

<div class="post-metadata">

**Author:** ![azaonline](https://developer.download.nvidia.com/images/forums/profile-default-devtalk-84.png) [@azaonline](https://forums.developer.nvidia.com/u/azaonline)\
**Post date:** [June 29, 2010, 3:33pm UTC](https://forums.developer.nvidia.com/t/why-shift-is-slower-than-integer-multiply-shift-integer-multiply/17395/14 "2010-06-29T15:33:00Z")

</div>

If I use “\_\_mul24( a, b ) - c”, whether it also can be optimized by compiler? int a,b,c  
whether the speed of \_\_mul24( a, b ) +c and a\*b+c are equal, as compiler optimize? int a,b,c

---

<div class="post-metadata">

**Author:** ![azaonline](https://developer.download.nvidia.com/images/forums/profile-default-devtalk-84.png) [@azaonline](https://forums.developer.nvidia.com/u/azaonline)\
**Post date:** [June 29, 2010, 3:33pm UTC](https://forums.developer.nvidia.com/t/why-shift-is-slower-than-integer-multiply-shift-integer-multiply/17395/15 "2010-06-29T15:33:00Z")

</div>

If I use “\_\_mul24( a, b ) - c”, whether it also can be optimized by compiler? int a,b,c  
whether the speed of \_\_mul24( a, b ) +c and a\*b+c are equal, as compiler optimize? int a,b,c

---

<div class="post-metadata">

**Author:** ![wwa](https://developer.download.nvidia.com/images/forums/profile-default-devtalk-84.png) [@wwa](https://forums.developer.nvidia.com/u/wwa)\
**Post date:** [June 29, 2010, 5:31pm UTC](https://forums.developer.nvidia.com/t/why-shift-is-slower-than-integer-multiply-shift-integer-multiply/17395/16 "2010-06-29T17:31:35Z")

</div>

> [@](#):
>
> If I use “\_\_mul24( a, b ) - c”, whether it also can be optimized by compiler? int a,b,c
> 
> whether the speed of \_\_mul24( a, b ) +c and a\*b+c are equal, as compiler optimize? int a,b,c

I don’t think there’s a good answer to that. The part of the compiler which does that is proprietary and nobody outside NVIDIA knows how it exactly works. I could make a dummy kernel with that single operation and see if it optimizes, but that’s hardly a clue - compiler may decide otherwise in other cases.

---

<div class="post-metadata">

**Author:** ![wwa](https://developer.download.nvidia.com/images/forums/profile-default-devtalk-84.png) [@wwa](https://forums.developer.nvidia.com/u/wwa)\
**Post date:** [June 29, 2010, 5:31pm UTC](https://forums.developer.nvidia.com/t/why-shift-is-slower-than-integer-multiply-shift-integer-multiply/17395/17 "2010-06-29T17:31:35Z")

</div>

> [@](#):
>
> If I use “\_\_mul24( a, b ) - c”, whether it also can be optimized by compiler? int a,b,c
> 
> whether the speed of \_\_mul24( a, b ) +c and a\*b+c are equal, as compiler optimize? int a,b,c

I don’t think there’s a good answer to that. The part of the compiler which does that is proprietary and nobody outside NVIDIA knows how it exactly works. I could make a dummy kernel with that single operation and see if it optimizes, but that’s hardly a clue - compiler may decide otherwise in other cases.

---

<div class="post-metadata">

**Author:** ![azaonline](https://developer.download.nvidia.com/images/forums/profile-default-devtalk-84.png) [@azaonline](https://forums.developer.nvidia.com/u/azaonline)\
**Post date:** [June 30, 2010, 2:38am UTC](https://forums.developer.nvidia.com/t/why-shift-is-slower-than-integer-multiply-shift-integer-multiply/17395/18 "2010-06-30T02:38:10Z")

</div>

Thx

---

<div class="post-metadata">

**Author:** ![azaonline](https://developer.download.nvidia.com/images/forums/profile-default-devtalk-84.png) [@azaonline](https://forums.developer.nvidia.com/u/azaonline)\
**Post date:** [June 30, 2010, 2:38am UTC](https://forums.developer.nvidia.com/t/why-shift-is-slower-than-integer-multiply-shift-integer-multiply/17395/19 "2010-06-30T02:38:10Z")

</div>

Thx

---

<div class="post-metadata">

**Author:** ![azaonline](https://developer.download.nvidia.com/images/forums/profile-default-devtalk-84.png) [@azaonline](https://forums.developer.nvidia.com/u/azaonline)\
**Post date:** [July 1, 2010, 11:00am UTC](https://forums.developer.nvidia.com/t/why-shift-is-slower-than-integer-multiply-shift-integer-multiply/17395/20 "2010-07-01T11:00:48Z")

</div>

> [@](#):
>
> You’re right, I totally forgot about mad24.
> 
> here’s the benchmark:
> 
> [codebox]mov.b32 $r62, %clock
> 
> mad24.lo.u32.u16.u16.u32 $r1, $r0.hi, $r0.lo, $r0
> 
> add.b32 $r3,$r0,$r0 //kill forwarding
> 
> add.b32 $r2,$r1,$1 //cause RAW stall
> 
> mov.b32 $r63, %clock[/codebox]
> 
> It executes 40 cycles, which reveals true mad24 latency of 40-8-8=24 cycles, believe it or not.
> 
> Also true with floating mul.

“mad24” is multiply-add instruction for integer on CUDA?

there are lots of “a\*b+c”(int a,b,c) in my code. but why I can’t find “mad24” on its ptx?

my Gpu is G260.

How can I employ multiply-add operation of integer on CUDA to speedup my app?

[Next page](https://forums.developer.nvidia.com/t/why-shift-is-slower-than-integer-multiply-shift-integer-multiply/17395.md?page=2)