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 

Azu
But that is how I mean..


03 Sep 2009, 19:45 

Azu
In my example the parameter is how many additions you are doing..


03 Sep 2009, 19:48 

Borsuc
Then it is O(N)
O(1) means that it is O(1), no matter the parameter (number of additions in this case), which is false, because it isn't constant. Bubble Sort is O(N^2), guess why. _________________ Previously known as The_Grey_Beast 

03 Sep 2009, 19:49 

Azu
Because that algorithm must run N*N times!
If I have a SIMD instruction that can do up to 16 additions at once, then it is running 1 time, as long as 16 or less additions need done, where as nonSIMD way would need ran 16 times to do 16 additions, or 2 times to do 2 additions, or whatever..... 

03 Sep 2009, 19:51 

revolution
Azu wrote: In my example the parameter is how many additions you are doing.. 

03 Sep 2009, 19:52 

Borsuc
@Azu: More correct would be to say that, because as you increase N, the amount of "steps" (let's keep it at abstract mathematical level) required increases by N^2. Or in other words, doubling N will quadruple the number of steps required.
Azu, it is about the number of "steps" needed. Doing them in parallel doesn't change anything, there's still 2 steps whether you do both at the same time, or whether you do them twice as fast. _________________ Previously known as The_Grey_Beast 

03 Sep 2009, 19:52 

Azu
No no no
The SIMD instruction will do the same amount of work whether you utilize the max amount of inputs it can work on at once or just give it 1 It's just that the excess will be wasted If it can do up to 16 at once and you give it say 3, it will be the same as if you give it 16.. it will take same amount of time, use same amount of resources, same complexity and everything. Different input but the complexity is constant. 

03 Sep 2009, 19:56 

Borsuc
O(N) is theoretical mathematical representation  there is no such thing as "waste" in math!
But that's irrelevant anyway. O(N) is asymptotical analyzation. This means as N tends to infinity you take the limit (and derivative). It's the mathematical term for how it "tends". You know, with limits (lim x>oo, stuff like that), which is x^2 for N^2, and 1 for O(1), not even using x! (no parameter change after all) Asymptotes 

03 Sep 2009, 23:13 

Azu
What I mean is, SIMD instructions do the same amount of work whether you are making full use of how much they can do or not. It doesn't vary based on how much work you need done. It can either handle however many operations you need or not. Hence O(1) whenever one of them is enough.


03 Sep 2009, 23:17 

Borsuc
Yes you are correct, but that has nothing to do with BigO notation. See my post above why
_________________ Previously known as The_Grey_Beast 

04 Sep 2009, 01:17 

Azu
Okay.. so what notation should I use instead?
I just want to express how many times an algorithm needs ran based on how much stuff it works on. Like this; loopy: mov al,byte[edi] add al,byte[esi] sub ecx,1 mov byte[edi],al lea edi,[edi+1] lea esi,[esi+1] je loopy Needs ran ecx times where as this; movdqa xmm0,dqword[esi] movdqa xmm1,dqword[edi] paddb xmm0,xmm1 movdqa dqword[edi],xmm0 Needs ran 1 time.. What is the correct notation that I should use to compare these? 

04 Sep 2009, 01:21 

revolution
AFAIK there is no notation for such a thing. Mathematicians are generally not interested in linear speedups so I doubt they have developed any special notation for it (if someone knows otherwise I would be happy to learn). Only computer programmers seem interested in linear speedups, so perhaps the measure of runtime, or clock counts, or instruction count, or byte count, or something, is the best you can get.


04 Sep 2009, 05:04 

Azu
Linear speadups? I'm talking about how many times you have to run the algorithm when you increase the number of inputs to it. That has absolutely nothing to do with runtime, clock counts, or instruction count. Look at my last example (before you ask, it's in the post right above yours).


04 Sep 2009, 07:24 

revolution
Azu wrote: Linear speadups? I'm talking about how many times you have to run the algorithm when you increase the number of inputs to it. That has absolutely nothing to do with runtime, clock counts, or instruction count. Look at my last example (before you ask, it's in the post right above yours). 

04 Sep 2009, 07:33 

Azu
No.. the required operations is constant as long as less than 17 inputs. Actually, it won't even work for >16 inputs, since I didn't put in any logic to handle that... so it's going to be constant no matter how many, lol. Where as the number of times the nonSIMD one will run is exactly how many inputs.
What is the notation for this? I think that, like I said, it should be "O(n)" for the nonSIMD one, and O(1) for the SIMD one if less than 17 inputs. Or x=16;how many it can do at once O(ceil(n/x)) to handle cases all the way up to infinitely, like I said a few pages back. (okay actually I changed it a little just now to make it more compact, but same result) You all keep saying that I am using the wrong notation so please tell me what is the right one to use for this. 

04 Sep 2009, 07:36 

revolution
Okay, so you have 16 operations per loop. That means:
0=1 loops 116=1 loop 1732=2 loops 3348=3 loops etc. That is how linear works. 

04 Sep 2009, 07:46 

Azu
For 0 through 16 it is 1 "loop" (not really a loop when it is just ran once though), like I said. Hence the "when N<17" qualifier I added to all my posts.
Last edited by Azu on 04 Sep 2009, 07:48; edited 1 time in total 

04 Sep 2009, 07:47 

revolution
Azu wrote: You all keep saying that I am using the wrong notation so please tell me what is the right one to use for this. 

04 Sep 2009, 07:48 

Azu
revolution wrote:
Code: ;func 1 loopy: loop loopy ;func 2 loopy: sub ecx,1 je loopy 

04 Sep 2009, 07:49 

Goto page Previous 1, 2, 3, 4, 5, 6, 7 Next < Last Thread  Next Thread > 
Forum Rules:

Copyright © 19992020, Tomasz Grysztar. Also on GitHub, YouTube, Twitter.
Website powered by rwasa.