Parallel efficiency

Question

I would like to calculate efficiency of parallel alghoritm, using the number of computations instead of time computations.

In materials from my studies I have a formula like below: $$ \eta(n,p) = \frac{\omega(n)}{\omega(n)+h(n,p)} = \frac{1}{1+h(n,p)/\omega(n)}, $$ where

• $\eta(n, p)$ - efficiency of parallel program which realized n-sized task on machine with p-number of CPUs
• $\omega(n)$ - number of computations for a n-sized task
• $h(n,p)$ - number of I/O operations for a n-sized parallel task

I have an application in two modes which realized 2mln of the same operations on:

• 4 threads with 4 CPUs. (with division of operations between all threads)
• serial computations with 4 CPUs.

The formula looks simple but I don't know how to apply it. I would like to ask about an explanation of mentioned formula in a real world example.

Answer 1

This formula seems to assume that one operation counted by $\omega(n)$ takes as long as one I/O operation counted by $h(n,p)$. So to apply it, you have to be able to count operations in your code and scale them to the same time scale. The further elaboration dividing the numerator and denominator by $\omega$ probably scales this out effectively, but you still have to be able to count operations. Depending on your CPU/co-processor, counting operations can be easier or harder.

You also need to be able to define for yourself what kind of operations are meant by I/O operations. I.e., does this mean writing to disk or does it include operations to RAM, the network, etc. I presume this formula was derived by substituting $t(n,p) = t_{\rm compute}(n,p) + t_{\rm I/O}(n,p) + \ldots$ into Amdahl's law and turning the crank with $t_{\rm compute}(n,p)=\omega(n,p)/\dot{\omega}(n,p) + \ldots$, etc. I presume also that this was part of an explanation that tries to explain where parts of the times that appear in Amdahl's Law can come from. In order to employ such a formula, you've got to know a lot about your computer and your code. You have to be able to count lots of different types of operations within your code, and you have to know the rate that your computer managed to actually do them at.

I think this is much harder than just measuring execution time at each $n$ and $p$ and is not worth approaching.