3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Well, I just realized that almost the same question was asked just 4h ago. However, the other asker focusses on memory access rather than on parallell computing, so I think my question has its own right to exist $\endgroup$ – Bananach Mar 27 '14 at 16:20
  • $\begingroup$ How do you define 'dependent step'? In matrix-vector products, the additions are part of a reduction to a single variable, which introduces data dependency. $\endgroup$ – Max Hutchinson Mar 27 '14 at 18:51
  • 3
    $\begingroup$ Welcome to SciComp! I suggest you rephrase your question to focus on the "dependent steps" idea and change your title accordingly. The concept you seem to be trying to express is that all of the steps of an algorithm should be laid out as a DAG, with an edge $(u,v)$ expressing that step $u$ depends on step $v$. Edges have weights corresponding the time it takes to compute from $u$ what is needed for $v$. Then the critical path (path with the shortest sum of weights) will be a limiting factor in parallelizing the algorithm. $\endgroup$ – Geoff Oxberry Mar 27 '14 at 20:25
  • $\begingroup$ Thanks for the suggestion! I read in the critical path method(en.wikipedia.org/wiki/Critical_path_method), and it pretty much covers what I envisioned $\endgroup$ – Bananach Mar 28 '14 at 13:51
  • 1
    $\begingroup$ "Dependent steps" is too simple. A+B+C has two dependent steps, but no dependencies across the vectors/matrices. $\endgroup$ – mabraham Apr 7 '14 at 21:44
7
$\begingroup$

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 equations
Gaussian 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.

$\endgroup$
4
$\begingroup$

First of all, a bit on the terminology. FLOPS are "floating point operations per second", and they are typically not used to measure the performance of algorithms, but of machines.

I assume that you mean that the complexity of algorithms is measured in the total number of floating point operations required to do the job (probably one could write that as FLOPs with lower case "s").

I think that even in times of parallel computing, this is a useful measure. FLOPs simply tell you how much work needs to be done. When I have a problem that requires more FLOPs than even my parallel machine can provide within reasonable time, I'm lost. Insofar, the FLOPs give you a lower limit of the time you will need.

However, I agree that with parallel machines, the measure has become far less useful, as almost no algorithm is actually able to use the full performance of the machine on a single problem. Therefore, your idea of an alternative measure seems reasonable to me. I am not aware of any alternative, but I have never looked for one. Maybe you want to elaborate on your idea?

Just as a side remark: the crazy thing is that supercomputing centers still mostly look at the number of FLOPS of their machines that can be used on a single problem, and that is what the TOP 500 benchmarks are all about. Therefore, they buy extremely expensive network interconnects to connect the whole machine. However, with the coming generation of exascale computers, there will be only a handful of algorithms that will be able to really use it. On the other hand, there are lots of problems that could profit from the computing power when splitting up the machine into smaller subsystems. That is what actually happens in supercomputing centers in more than 90% of the time anyway. Still, this kind of problems are shunned by the supercomputing community as being "trivially parallelizable", as they cannot be used to argue for the expensive interconnects.

$\endgroup$
  • 3
    $\begingroup$ "Embarrassingly parallel" is a more common expression than "trivially parallel". Also, embarrassingly parallel problems are not "shunned", they simply don't exist in the vast majority of applications. If you can find an embarrassingly parallel way to do nuclear reactor, astrophysics, or fluid dynamics simulations you'll be very, very famous. $\endgroup$ – Doug Lipinski Mar 29 '14 at 1:12
  • 1
    $\begingroup$ I disagree. Even though the application itself usually is not embarrassingly parallel, I think that only in rare cases, it is enough to run an application only once with one specific set of parameters. Typically, one has to run the application several times with different parameters sets - and that could easily be parallelized, and that would be embarrassingly parallel. $\endgroup$ – olenz Apr 3 '14 at 7:20
  • $\begingroup$ Also, you are of course right about the term "embarrassingly parallel", although I have heard it called "pleasantly parallel", as these problems are indeed much more pleasant to handle, than the hard parallel problems. $\endgroup$ – olenz Apr 3 '14 at 7:33
  • $\begingroup$ Oh, and yes, embarrassingly parallel problems are shunned. Just go to your local supercomputing center and tell them that you would like to run 1 million jobs that each require 1 core for a few hours. I don't think you would get the computing time. $\endgroup$ – olenz Apr 3 '14 at 7:36
  • 1
    $\begingroup$ Also, you don't ask to run 1 million jobs on 1 core, you ask to run 1 job on 1 million cores. And if your application is embarrassingly parallel then you don't need the supercomputer infrastructure anyway and will be turned down for that reason. $\endgroup$ – Doug Lipinski Apr 3 '14 at 15:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.