? (0xe2.0x9a.0x9b@gmail.com) on 8/16/09 wrote:
---------------------------
>.....
>I do not think it is possible to artificially increase the theoretical maximum
>ILP the way you are suggesting. The theoretical limit does apply to all correct
>permutations of instructions in a program, so you cannot get above the limit just
>by changing the order of instructions, for example. So what do you exactly mean by "writing the programs differently"?

Sorry, to be more clear I mean that there are always many available alogrithms (at the high conceptual algorithm) to complete a job, and these can be suited to different systems - I am talking about using complete (and obviously very difficult..) rewrites of softrware here, not compiler tweaks.

A moderately good example is sorting - the optimal sorting algorithm for sequential execution is VERY different from the optimal with a large number of parallel resources (and is next to impossible to parallelise without base algorithmic changes due to high instruction dependency) - a compiler will never turn one algorithm into another at that level.
A FFT is another good example, there are a number of techniques to change its scheduling features - which use some very subtle tricks, and make it more/less parallel.
It is often also the case that an algorithm that exposes more parallelism is in total instructions executes somewhat less efficient, and only faster in walltime when a suitable number of execution resources are available.

>Perhaps you mean that, for example, a simpler O(N*N) algorithm would have higher
>theoretical ILP than a sophisticated O(N*logN) algorithm with the same semantics.

Thats a massive oversimplification, and an example of the 'bad' approach you were talking about - talking about orders is next to useless here - I am talking about complete changes in implementation/design.

>The problem here is the wall-clock time: the latter algorithm would always finish
>first, which kind of invalidates the simpler algorithm despite it having higher
>ILP.

A bit of an overgeneralisation of course, but you are talking about your initial case (silly ways to get ILP for its own sake) - I am talking about something very different.

>I mean, you were talking about "usefully consume more ILP" - but there is nothing
>useful about the slower algorithm, because it is slower. So what exactly do you
>mean by "usefully consume more ILP"? - Give me a concrete example please.

I never said it would be a stupidly designed slower alogrithm. many such algorithms can be 10-20% more instructions (or even no more..) but expose a lot more ILP, in which case it would be a win..


>
>>A good example is SSE code, which is written to take advantage directly of a (small
>>amount) of explicit ILP in effect - which should give a higher 'reading' than older
>>(and usually simpler) non SSE codes (I am talking about quite specific highly SSE
>>optimised code here, such as video codecs and audio processors, for example).
>
>You cannot somehow by magic surpass the theoretical limit (as you suggested) by
>substituting 4 FMUL instructions with one SSE vector instruction. Look:
>
>A (4 scalar instructions):
>a[0] := b[0]*c[0]
>a[1] := b[1]*c[1]
>a[2] := b[2]*c[2]
>a[3] := b[3]*c[3]
>
>B (1 vector instruction):
>a[0..3] := b[0..3]*c[0..3]
>
>Results:
>A: max 4 instructions per clock
>B: max 1 instruction per clock
>A: max 4 parallel multiplications
>B: max 4 parallel multiplications

Way to completely miss my point, now please read CAREFULLY.

What I am saying is that the advent of SSE (and other similar codes) made some people go and hunt for better algorithms that COULD execute across such vectors - and by definition if that same code is moved back to sequential, it has higher ILP than the original pre-SSE(or whatever) code.
There are many good examples of this - pre vector machines almost no one was looking for such algorithms - they simply looked for the most efficient sequential case - FFT is again a good example here and looking over how optimal implementations work could be educational.

>The max number of parallel multiplications is the *same* in both cases. (The only
>advantage of B over A could be a lower memory bandwidth due to a shorter instruction,
>though that depends on instruction encoding). And if you count the vector instruction
>B as just 1 instruction (instead of counting it as 4 multiplications), then an ILP
>counted in such a way is actually *lower* for the vectorized case B than for case A.
>
>So, in essence, I do not think you have the slightest idea what you are talking
>about. But if you think you do and I am in error, please provide some concrete examples.

Nope, that would be you because you are suck in strawman territory, if you actually try and comprehend my point you will see that you are miss-characterising it.

>
>>There is a strange new world out there in high-ILP codes, and we are only just
>>starting to dabble in it. Like explicit vectors is can work great for some applications, and not at all for others.