4 ms·
> even the most parallel programs tend to have bottlenecks There's a big class of "embarrassingly parallel" tasks, which usually are only limited by how quickl
by rm999 14y ago
> even the most parallel programs tend to have bottlenecks
There's a big class of "embarrassingly parallel" tasks, which usually are only limited by how quickly you can move your data to where it needs to be.
- marshray 14y agoWhat makes something EP is that there is very little data (relative to the CPU time) that needs to be moved. For example, to compute a nice image of points near the Mandelbrot set, you only need to move the requested parameters (4 floats) to the CPU, let it churn for a long time, and retrieve the resulting pixels (3 bytes each).
- rm999 14y agoI think EP describes a problem, whereas how much data you have to move around is dependent on your implementation. For example, SETI@home is an EP problem that could be run on a multicore machine completely in parallel without moving data. The fact that it is run on many computers over the internet doesn't change that it's EP. In fact, it is exactly because it is EP that it can be run @home.
- marshray 14y agoI agree SETI@Home is very EP. What did I say to suggest it was not?
- rm999 14y agoI'm not arguing that it's EP, I'm using it as an counterexample to your point. You can solve SETI by moving data around or without moving data around, but that doesn't change the inherent fact that it is a EP algorithm.
- marshray 14y agoBut do we agree that if SETI required moving so much data around that it was clearly difficult to keep the CPUs fully utilized then it would not be an EP problem?
- dkersten 14y agoTo me, something is EP if it has no or few dependencies between data, regardless of how much the data does or doesn't need to be moved around.
- marshray 14y agoYeah, that's probably more important. But they're related and the amount of data is not completely irrelevant. Say instead of the Mandelbrot set we're talking about generating large vectors of random numbers. This task should obviously have no data dependencies and there are algorithms that can generate random numbers much faster than an external CPU bus can transfer them to memory. If raw bandwidth limitations mean that our CPUs see only 10% utilization is this still a "fully EP" problem? Because it should easily achieve full CPU utilization on most any machine, couldn't we say that Mandlebrot is more EP than the RNG problem?
- dkersten 14y agoI would say that the RNG problem is EP in that each data item can be processed completely in parallel with the others. The fact that there is a memory bottleneck doesn't really say anything about the nature of the problem but rather the hardware its running on.
- marshray 14y agoBTW, thanks for the really interesting discussion!