Re:Multi-core and multi-threading performance
by dkersten on Thursday October 11, 2012 @12:24PM
(#4641504)
To 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.
Re:Multi-core and multi-threading performance
by marshray on Thursday October 11, 2012 @12:41PM
(#4641589)
Yeah, 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?
Re:Multi-core and multi-threading performance
by dkersten on Friday October 12, 2012 @06:45AM
(#4644477)
I 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.
Re:Multi-core and multi-threading performance
by marshray on Friday October 12, 2012 @08:36AM
(#4644727)
BTW, thanks for the really interesting discussion!
Re:Multi-core and multi-threading performance
by rm999 on Thursday October 11, 2012 @11:46AM
(#4641293)
I 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.
Re:Multi-core and multi-threading performance
by marshray on Thursday October 11, 2012 @01:42PM
(#4641848)
I agree SETI@Home is very EP. What did I say to suggest it was not?
Re:Multi-core and multi-threading performance
by rm999 on Thursday October 11, 2012 @03:01PM
(#4642202)
I'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.
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).