In times of parallel computing, it seems to me that algorithms (also basic ones, like matrix-vector multiplication) should be measured by their dependent steps (that use results from steps before) rather than in total number of Floating Point Operations.For example, disregarding memory access, matrix-vector multiplication has $O(n^3)$ Floating Point Operations, but only 2 dependent steps (first do the multiplications, then the additions)Of course even with modern GPUs you cannot compute infinitely many steps in parallel, add up infinitely many numbers, or cache infintely many values, but to compensate for this you can multiply the 'dependent steps length' of your algorithm  by a factor (dependent on number of FPUs, cachesize etc. and the respecitve maximal needs of your algorithm) to obtain reasonable estimates. Thanks for your opinions/references/objections/caveats/pitfallsNote: I'm no computer specialist (especially not concerning hardware), just a mathematician working with MATLAB every now and then
Why is computational cost measured in Floating Pt. Ops. in times of parallel computing?
algorithms;parallel computing;performance;complexity
In fact, the precise total number of operations is very rarely used as a measure of computational cost. Instead, you will most often see the computational order (i.e. $\mathcal{O}(n^3)$). This big O notation roughly means that the number of operations is proportional to $n^3$ and tells you how the total number of operations scales as the number of unknowns is changed. This is an extremely useful measure of computational complexity because it gives you an estimate of the relative cost as you scale up the size of your problem.Consider a simple example: solving a linear system of equationsGaussian elimination is $\mathcal{O}(n^3)$ so if you double the number of unknowns it will take $2^3=8$ times as long. If you're performing a 3D computation and half your grid spacing you'll have $2^3=8$ times as many grid points (unknowns) and need to do $8^3=512$ times more work to solve your linear system.Algebraic multigrid (AMG) solves linear systems in $\mathcal{O}(n)$ time. Even though it may take significantly longer to solve a small system of equations using AMG, as you scale up your number of unknowns, the work scales much slower. In this case 8 times the unknowns means 8 times the work.The above discussion is entirely independent of parallel versus serial execution. In general, parallel performance is discussed in terms of parallel efficiency. Parallel efficiency generally depends both on problem size and number of processes and is defined as$$\textit{Efficiency(n,p)} = \dfrac{T_{1}(n)}{p\cdot T_{p}(n,p)}$$where $n$ is the number of unknowns, $p$ is the number of processes, and $T_p$ is the runtime using $p$ processes. For example, an algorithm with a 50% parallel efficiency will run 5x as fast on 10 cores compared to a single core (rather than 10x as fast on 10 cores).Note that the parallel efficiency does not affect the computational order or vice versa. The computational complexity reflects the number of floating point operations that must be performed which does not depend on the number of processes used. On the other hand, parallel efficiency is largely determined by the communication requirements of the algorithm as is closely tied to the communication bandwidth and latency. If every process must communicate with every other all the time you will have very poor parallel efficiency. On the other hand, algorithms that require no communication between processes are known as embarrassingly parallel and achieve nearly 100% parallel efficiency. This is typical of Monte Carlo algorithms.Although it is perhaps not as widely discussed outside of large computations, parallel efficiency is quickly becoming almost as important as the computational order due to the prevalence of many core computers.