flat assembler
Message board for the users of flat assembler.

Index > Windows > Disable SMT for my process?

Goto page Previous  1, 2, 3, 4, 5, 6, 7  Next
Author
Thread Post new topic Reply to topic
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 17467
Location: In your JS exploiting you and your system
revolution
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.
Post 03 Sep 2009, 17:40
View user's profile Send private message Visit poster's website Reply with quote
Azu



Joined: 16 Dec 2008
Posts: 1159
Azu
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 -.-
Post 03 Sep 2009, 17:45
View user's profile Send private message Send e-mail AIM Address Yahoo Messenger MSN Messenger ICQ Number Reply with quote
LocoDelAssembly
Your code has a bug


Joined: 06 May 2005
Posts: 4633
Location: Argentina
LocoDelAssembly
Post 03 Sep 2009, 17:54
View user's profile Send private message Reply with quote
Azu



Joined: 16 Dec 2008
Posts: 1159
Azu
Thanks for backing me up.
Post 03 Sep 2009, 17:59
View user's profile Send private message Send e-mail AIM Address Yahoo Messenger MSN Messenger ICQ Number Reply with quote
LocoDelAssembly
Your code has a bug


Joined: 06 May 2005
Posts: 4633
Location: Argentina
LocoDelAssembly
Backing you up? Ok...
Post 03 Sep 2009, 18:16
View user's profile Send private message Reply with quote
Borsuc



Joined: 29 Dec 2005
Posts: 2466
Location: Bucharest, Romania
Borsuc
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
Post 03 Sep 2009, 18:16
View user's profile Send private message Reply with quote
Azu



Joined: 16 Dec 2008
Posts: 1159
Azu
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
Post 03 Sep 2009, 18:28
View user's profile Send private message Send e-mail AIM Address Yahoo Messenger MSN Messenger ICQ Number Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 17467
Location: In your JS exploiting you and your system
revolution
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?
Post 03 Sep 2009, 18:36
View user's profile Send private message Visit poster's website Reply with quote
Azu



Joined: 16 Dec 2008
Posts: 1159
Azu
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.
Post 03 Sep 2009, 18:42
View user's profile Send private message Send e-mail AIM Address Yahoo Messenger MSN Messenger ICQ Number Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 17467
Location: In your JS exploiting you and your system
revolution
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.
Post 03 Sep 2009, 19:08
View user's profile Send private message Visit poster's website Reply with quote
Azu



Joined: 16 Dec 2008
Posts: 1159
Azu
If you don't know just say so.
Post 03 Sep 2009, 19:10
View user's profile Send private message Send e-mail AIM Address Yahoo Messenger MSN Messenger ICQ Number Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 17467
Location: In your JS exploiting you and your system
revolution
Azu wrote:
If you don't know just say so.
I have no idea what you are talking about.
Post 03 Sep 2009, 19:12
View user's profile Send private message Visit poster's website Reply with quote
Azu



Joined: 16 Dec 2008
Posts: 1159
Azu
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
Post 03 Sep 2009, 19:13
View user's profile Send private message Send e-mail AIM Address Yahoo Messenger MSN Messenger ICQ Number Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 17467
Location: In your JS exploiting you and your system
revolution
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.
Post 03 Sep 2009, 19:16
View user's profile Send private message Visit poster's website Reply with quote
Azu



Joined: 16 Dec 2008
Posts: 1159
Azu
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?
Post 03 Sep 2009, 19:19
View user's profile Send private message Send e-mail AIM Address Yahoo Messenger MSN Messenger ICQ Number Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 17467
Location: In your JS exploiting you and your system
revolution
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.
Post 03 Sep 2009, 19:30
View user's profile Send private message Visit poster's website Reply with quote
Azu



Joined: 16 Dec 2008
Posts: 1159
Azu
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.
Post 03 Sep 2009, 19:33
View user's profile Send private message Send e-mail AIM Address Yahoo Messenger MSN Messenger ICQ Number Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 17467
Location: In your JS exploiting you and your system
revolution
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.
Post 03 Sep 2009, 19:38
View user's profile Send private message Visit poster's website Reply with quote
Azu



Joined: 16 Dec 2008
Posts: 1159
Azu
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
Post 03 Sep 2009, 19:42
View user's profile Send private message Send e-mail AIM Address Yahoo Messenger MSN Messenger ICQ Number Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 17467
Location: In your JS exploiting you and your system
revolution
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.
Post 03 Sep 2009, 19:44
View user's profile Send private message Visit poster's website Reply with quote
Display posts from previous:
Post new topic Reply to topic

Jump to:  
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


Copyright © 1999-2020, Tomasz Grysztar. Also on YouTube, Twitter.

Website powered by rwasa.