Say if I wanted to parallelise an algorithm. Only certain parts of this algorithm can be parallelised. The other parts are trivial and not worth distributing. Do I do all of these trivial calculations on my master node and then broadcast the data to all remaining nodes OR do I conduct these calculations on ALL processors?
3 Answers
$\begingroup$
$\endgroup$
2
If the operation is as trivial as you say, and each node has all the information necessary to carry out the operation, then the communication will be substantially more expensive than recomputing locally on each node. That said, it's a good exercise to write both implementations and compare; experiment is better than the advice of strangers on the internet.
The break-even point when a task becomes non-trivial will depend on how the problem has been parallelized. It's much lower for shared-memory parallelism on the same machine than it is for distributed-memory parallelism across a cluster. For that matter, it probably depends on whether your cluster is using ethernet or infiniband. A handy reference that I often come back to is Latency Numbers Every Programmer Should Know. It's 6 years old at this point but the same principle still applies.
answered Jul 20, 2018 at 19:31
-
$\begingroup$ Your answer would be reasonable for shared memory. This question is tagged "MPI". $\endgroup$ Jul 21, 2018 at 14:50
-
$\begingroup$ I think this answer is actually very reasonable for an MPI, OpenMP and hybrid context... $\endgroup$– BlaBAug 6, 2018 at 19:29
$\begingroup$
$\endgroup$
An addition to @Daniel Shapero's answer.
It might also be important to know if there are computations that can lead to different results depending on which machine they are launched (or just vary from launch to launch) – and how sensitive is your code to those fluctuations.
These will be even more pronounced if the cluster you are working on is inhomogeneous (nodes can be different).
Possible examples:
- Computations that depend on random number generator (with non-fixed seed)
- Floating-point calculations. Which might slightly differ from machine-to-machine (if the architecture/OS is different) or even on the same machine (say, OpenMP reduction has been performed).
Now, if this is the case and your future calculation are really sensitive to that, you might consider broadcasting instead of everybody calculating this step individually.
Again, the benchmarking will give you the ultimate answer.
answered Jul 20, 2018 at 20:12
$\begingroup$
$\endgroup$
1
Since you tagged this with "MPI": there is no master node. The stuff that is too trivial should be done redundantly on every process.
Bear in mind that even sending a single byte through an MPI message is the equivalent of (tens of) thousands of operations.
-
$\begingroup$ Of course, that scaling depends on the system infrastructure. If the problem is small enough to be running on a single machine, then it will be a lot closer to a shared memory paradigm, and possibly using shared memory as a method of exchange under the hood. $\endgroup$– origimboJul 21, 2018 at 21:42
id=0as a master one. And say, write tostdoutonly from it, or time things only on it. $\endgroup$