Disable SMT for my process?

Index > Windows > Disable SMT for my process?

Goto page Previous 1, 2, 3, 4, 5, 6, 7 Next

Author

Thread

revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 20454
Location: In your JS exploiting you and your system

revolution 03 Sep 2009, 17:40

Azu wrote:

It can if N is small enough.

Here's an example;

Let's say you have a non-SIMD algorithm that takes 1 clock cycle per addition, and then you have a SIMD algorithm that does 16 additions in 2 clock cycles.

The non-SIMD one is O(N), but if N<17 then the SIMD one is O(1).

It is clear you do not understand the big-O notation. Your example is wrong. Big-O is not a measure of clock cycles used in a CPU.

03 Sep 2009, 17:40

Azu

Joined: 16 Dec 2008
Posts: 1159

Azu 03 Sep 2009, 17:45

revolution wrote:

Azu wrote:
It can if N is small enough.

Here's an example;

Let's say you have a non-SIMD algorithm that takes 1 clock cycle per addition, and then you have a SIMD algorithm that does 16 additions in 2 clock cycles.

The non-SIMD one is O(N), but if N<17 then the SIMD one is O(1).
It is clear you do not understand the big-O notation. Your example is wrong. Big-O is not a measure of clock cycles used in a CPU.

If I didn't know that I would have said O(N*1) and O(2), respectively -.-

03 Sep 2009, 17:45

LocoDelAssembly
Your code has a bug

Joined: 06 May 2005
Posts: 4624
Location: Argentina

LocoDelAssembly 03 Sep 2009, 17:54

http://www.soe.ucsc.edu/classes/cmps102/Spring04/TantaloAsymp.pdf

03 Sep 2009, 17:54

Azu

Joined: 16 Dec 2008
Posts: 1159

Azu 03 Sep 2009, 17:59

Thanks for backing me up.

03 Sep 2009, 17:59

LocoDelAssembly
Your code has a bug

Joined: 06 May 2005
Posts: 4624
Location: Argentina

LocoDelAssembly 03 Sep 2009, 18:16

Backing you up? Ok...

03 Sep 2009, 18:16

Borsuc

Joined: 29 Dec 2005
Posts: 2465
Location: Bucharest, Romania

Borsuc 03 Sep 2009, 18:16

Quote:

As we’ll see, the asymptotic run time of an algorithm gives a simple, and machine independent, characterization of it’s complexity.

_________________
Previously known as The_Grey_Beast

03 Sep 2009, 18:16

Azu

Joined: 16 Dec 2008
Posts: 1159

Azu 03 Sep 2009, 18:28

When an algorithm needs ran n times (where n is how many elements you feed to it) to get the result, it is O(N) complexity. If it only needs ran once for however many elements it processes, it is O(1).

Loops, for example, are O(N), where as jump tables are O(1).

I'm really not sure what the ambiguity is. Confused

03 Sep 2009, 18:28

revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 20454
Location: In your JS exploiting you and your system

revolution 03 Sep 2009, 18:36

Azu wrote:

When an algorithm needs ran n times (where n is how many elements you feed to it) to get the result, it is O(N) complexity. If it only needs ran once for however many elements it processes, it is O(1).

Did you understand the document that LocoDelAssembly linked?

03 Sep 2009, 18:36

Azu

Joined: 16 Dec 2008
Posts: 1159

Azu 03 Sep 2009, 18:42

revolution wrote:

Azu wrote:
When an algorithm needs ran n times (where n is how many elements you feed to it) to get the result, it is O(N) complexity. If it only needs ran once for however many elements it processes, it is O(1).
Did you understand the document that LocoDelAssembly linked?

I read part of it, and stopped when I saw sines, since trigonometry has nothing to do with what we're talking about.

If big-O notation isn't right for what I described then please just tell me what is, because that's always how I've seen it used.

03 Sep 2009, 18:42

revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 20454
Location: In your JS exploiting you and your system

revolution 03 Sep 2009, 19:08

Alexander Pope (1688 - 1744) wrote:

A little learning is a dangerous thing; drink deep, or taste not the Pierian spring: there shallow draughts intoxicate the brain, and drinking largely sobers us again.

03 Sep 2009, 19:08

Azu

Joined: 16 Dec 2008
Posts: 1159

Azu 03 Sep 2009, 19:10

If you don't know just say so.

03 Sep 2009, 19:10

revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 20454
Location: In your JS exploiting you and your system

revolution 03 Sep 2009, 19:12

Azu wrote:

If you don't know just say so.

I have no idea what you are talking about.

03 Sep 2009, 19:12

Azu

Joined: 16 Dec 2008
Posts: 1159

Azu 03 Sep 2009, 19:13

About what you replied to..

Azu wrote:

If big-O notation isn't right for what I described then please just tell me what is

03 Sep 2009, 19:13

revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 20454
Location: In your JS exploiting you and your system

revolution 03 Sep 2009, 19:16

SIMD gives linear speed up, like I mentioned earlier. If that is not what you are asking then please explain more what you want to know and I will answer if I can.

03 Sep 2009, 19:16

Azu

Joined: 16 Dec 2008
Posts: 1159

Azu 03 Sep 2009, 19:19

These

Azu wrote:

Here's an example;

Let's say you have a non-SIMD algorithm that takes 1 clock cycle per addition, and then you have a SIMD algorithm that does 16 additions at once in 2 clock cycles.

The non-SIMD one is O(N), but if N<17 then the SIMD one is O(1).

Azu wrote:

When an algorithm needs ran n times (where n is how many elements you feed to it) to get the result, it is O(N) complexity. If it only needs ran once for however many elements it processes, it is O(1).

Loops, for example, are O(N), where as jump tables are O(1).

You said big-O notation is not like that, so I am asking; what is the right notation to use for it?

03 Sep 2009, 19:19

revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 20454
Location: In your JS exploiting you and your system

revolution 03 Sep 2009, 19:30

You need to understand that big-O has a hidden factor 'c' that is not stated in any mathematical document. This factor 'c' is the linear factor and is not important to arithmetic complexity measurements hence it is ignored. This factor 'c' is where the CPU clocks rates and SIMD will have an effect.

So you would kind of get c×O(something) - although you will never see that in any literature. The part in the brackets cannot ever be changed just by using wider instructions or different instructions or faster clock rates any any other linear speed up.

03 Sep 2009, 19:30

Azu

Joined: 16 Dec 2008
Posts: 1159

Azu 03 Sep 2009, 19:33

The hidden "c" is how long the algo takes to run and n is how many times it needs ran.. so didn't I use big-O correctly then?

If you can do between 1 and 16 of something at once via SIMD, then isn't it O(1) as long as there is under 17? Where as with normal instructions that work on 1 byte at a time it would be O(n).. what is wrong with this? I don't understand how I am misusing it.

03 Sep 2009, 19:33

revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 20454
Location: In your JS exploiting you and your system

revolution 03 Sep 2009, 19:38

Azu wrote:

The hidden "c" is how long the algo takes to run and n is how many times it needs ran.. so didn't I use big-O correctly then?

If you can do between 1 and 16 of something at once via SIMD, then isn't it O(1) as long as there is under 17? Where as with normal instructions that work on 1 byte at a time it would be O(n).. what is wrong with this? I don't understand how I am misusing it.

The algorithmic complexity doesn't change because of SIMD. Without SIMD you do, say, 4 'add's in four cycles to get some results. With SIMD you still do 4 'add's (i.e. the complexity is still the same, you still had to do 4 'add's) in one clock cycle. So the complexity never changed, only the runtime timing changed.

03 Sep 2009, 19:38

Azu

Joined: 16 Dec 2008
Posts: 1159

Azu 03 Sep 2009, 19:42

If you can do up to 4 at once.. then wouldn't it be O(1) as long as you are doing less than 5 adds? Where as if you did them one at a time using non-SIMD then it should be O(N)..

Here's a way to put it without needing the "as long as you are doing less than X";

n=How many
x=How many of them you can do at once

O(1+floor(n/x))

Shouldn't this be correct always?

Last edited by Azu on 03 Sep 2009, 19:45; edited 2 times in total

03 Sep 2009, 19:42

revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 20454
Location: In your JS exploiting you and your system

revolution 03 Sep 2009, 19:44

Your understanding of N is not correct. N is a measure of the input size, not a loop count or any other CPU specific thing.

03 Sep 2009, 19:44

Goto page Previous 1, 2, 3, 4, 5, 6, 7 Next

< Last Thread | Next Thread >

Forum Rules:

You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You can download files in this forum