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/pitfalls
Note: I'm no computer specialist (especially not concerning hardware), just a mathematician working with MATLAB every now and then