[quote name='stu2000' timestamp='1298056459' post='4776034']
I read somewhere that cuda works well because it hides memory access latencies by running other threads during this time so even though memmory is slow, this is 'hidden' though this is probably referring to accessing the gpu local/texture memory rather than the global memory, I don't know.
Unless the card on which it's running contains a flux capacitor or graviton generator, then the laws of physics still hold. Even on GPU, memory access patterns are crucial. Morton order, Sloan or Cuthill-McKee ordering, tricks like that all matter.
[/quote]
I wasnt referring to anything amazing in the field of physics, just referring to this section that I had read:
One key difference is in how the two architectures address the issue of accessing off-chip
memory, a very expensive operation with hundreds clock cycles of latency. CPUs devote a
lot of transitors to on-chip caches in order to reduce as much as possible the overall latency
caused by off-chip memory accesses. For applications with no or very little parallelism, this
latency reduction is the best strategy. For applications with a high number of parallel
computations, another strategy is to ensure that the processor is always busy with some
computations while other computations are waiting on memory accesses or at
synchronization points. In other words, latency is “hidden” rather than reduced. This latency NVIDIA OpenCL Programming for the CUDA Architecture 3
hiding strategy adopted by GPUs is schematized in Figure 1. Latency hiding requires the
ability to quickly switch from one computation to another. A GPU multiprocessor (i.e. a
compute unit in OpenCL terminology) is therefore designed to support hundreds of active
threads at once and unlike CPUs, the cost of switching from one thread to another is
insignificant
src:
http://www.nvidia.co...ingOverview.pdf
GPUs are great for things which have very small and fully independent state. For example, updating 20 million particles. But as soon as you start dealing with any kind of global or shared state, things get complicated.
For most problems, algorithmic improvements matter most, and those rely on branching to cull away unfeasible paths. And that is something that general purpose CPUs shine at with branch prediction, pipelines, large caches, ... For most realistic computational problems, CPUs and GPUs perform about the same if comparing equivalent implementations.
Yes I had been building upon this point ( that gpu's work best in an independent state) for this algorithm, stating that I had wanted to create permutations from a continually increasing index. This way each thread is given its own integer index and creates its own permutation from which to calculate the route length (TSP) This will be many more than one instruction. However, it seems that it is very much more calculation intensive to create a permutation from an index, rather than carry on in a recursive method from the previous permutation and thats where this whole thing about shared communication/memory seems to have popped out from.
I would still like to see if running lots of threads on a GPU, completely independent, but more calculation intensive (generate permutations from index) as a whole is faster or slower than running a single thread recursive algorithm on a CPU.
Stu
