equivalent number of instruction

Question

I've a question (just like me)...

but...if I've a choosen algorithm written in C or C++ or whatever code you want...fixed a compiler I can determine the number of instructions but these intructions are different each other: x ADD, y MUL, z MOV, f FADD, t FMUL (F stands for FLOATING)...Is there a methodology or equation or something else that permits to write the number of instructions in number of "Equivalent instruction" to compare different algorith? Is there somebody of you that use this type of metric? is it a rubbish?

Thanks

Marco

Part2: I Know that it dipends on uP and architecture in general. My problem is: To determine a execution time of different algorithms implemented on different architectures of soft core. On y-axis I must write time, on x-axis the number of instruction and the point of the graph are parametrized by the type of architecture (excuse me for my english). But on x-axix I think it's better to use something like number of "equivalent instruction"...

Is it a rubbish idea?

Velvety

Answer 1

You don't quite understand the problem. Execution speed depends not only on instructions but on inter-instruction dependencies also. Microprocessors can execute several instructions at the same time given this instructions don't depend on each other. The ability to execute several instructions at a time differs from one processor family to another. That's why this task is really hardware-specific, it can't be solved once and for all.

All you can do is graph an execution timeline of instructions and processor cycles. Processor cycles could be y-axis, instructions could be x-axis. You'll have problems predicting cache hits and misses and execution time of many instructions will vary greatly depending on cache hits/misses. Be ready to spend a lot of time with processors manuals.

Queer

Thanks But I can't use processor cycle 'cause i could use also a pure FPGA architecture, not uP based...so processor cycle become a nonsense in this situation... – Velvety

You have to consider the pipelining and execution units of the processor, that's essential for precise execution time prediction. This implies that you know what each execution unit is doing on each processor cycle. – Queer

Answer 2

It would have to take into account pipelining and all kinds of other intricacies, many of which will vary by processor. In other words, I can't see it being particularly useful even if it's feasible.

There are also things which the algorithm wouldn't be able to tell you, like how many cache misses there'll be etc - these could be much more important than the raw instruction count.

Southwestward

Thanks Jon, is there a way to determine a measure of effort of fixed algorithm? But no something like O(nlog(n))...that is accademic...Thanks – Velvety

Not that I'm aware of. I usually find that "run it and time it" is the simplest approach, and works pretty well. – Southwestward

Jon, sometimes cache misses can be predicted. For example, if you multiply two large matrices, you know for sure that retrieving each column of the second matrix will lead to a lot of cache misses and can even evaluate the cost of this. – Queer

@sharptooth: Surely that will depend on the size of the cache, how much is fetched at a time etc. My point is it's a pretty intricate calculation :) – Southwestward

@Jon: Yeap, it's real hardcore. No doubt in that. – Queer

Answer 3

It's not rubbish, it's just vague. To go from Algorithm to SOurce code to Object COde to core... so many details to nail down, each of which can have significant performance implications.

Have a look at Hennessey & Patterson's "Computer Architecture, A Quantitative Approach"

Gatha

That's not vague, that's ultra hardcore. It can be quite effective if done after careful high-level optimization. – Queer