6 ms·

What are some of these complex tasks you had in mind? I think that almost any computation-bound task, however complex, could benefit from GPU acceleration. But

by miloshh 18y ago

What are some of these complex tasks you had in mind? I think that almost any computation-bound task, however complex, could benefit from GPU acceleration. But I would like to hear about exceptions.

DarkShikari 18y ago
A motion search, for video compression, is what I was trying. It has some huge disadvantages: 1. The threading model is completely unsuited to a search that takes a different number of iterations per block (since it wants all the threads doing the same thing). 2. CPUs already have the PSADBW instruction, which allows an absurd effective throughput: its literally an instruction dedicated to this kind of task. Its also a purely 8-bit integer problem, so it doesn't benefit from the high-performance floating point units on the GPU. Due to 1), you're pretty much restricted to either crippling your performance, using a very simplified search, or using an exhaustive search. And if you're using an exhaustive search, it turns out that there's a mathematically equivalent and vastly faster way to do it called "sequential elimination"... which is completely impractical to implement on a GPU as well due to its linear nature, and which allows a Core 2 to vastly outperform a GPU and possibly even be competitive with a dedicated FPGA doing a normal exhaustive search.
- miloshh 18y ago
  Hmmm.. OK. You mind posting a link to the pseudo-code of the algorithm? The problem of different number of iterations per thread is quite common, but can often be fixed. If all threads in a block have the same number if iterations, you're fine; different blocks can take different number of iterations. As long as the number of blocks is much higher than the number of SMs, the machine will dynamically schedule the blocks to available SMs. If each thread takes a different number of iterations, it's more difficult, but you can still do dynamic allocation yourself, by running as many blocks as you have SMs, and having each thread pick up work as it needs. You can also randomize the assignment of work to threads, so the expected amount of work is roughly the same. This all depends on the particular problem and data, though... As for the 8-bit nature of the problem - this is true, you're not utilizing the floating point units that are the biggest advantage of the GPU. How large are the vectors you need to do PSADBW over?
  - wmf 18y ago
    If all threads in a block have the same number if iterations, you're fine; different blocks can take different number of iterations. As long as the number of blocks is much higher than the number of SMs, the machine will dynamically schedule the blocks to available SMs. At this point the programmer's head has already exploded. MIMD systems (like OpenMP on Larrabee) don't have any of this BS.
    - miloshh 18y ago
      No, Larrabee will have exactly the same issues. Except threads will be called fibers, and blocks will be called threads. Read the Larrabee paper from Siggraph 08. The way to get maximum performance out of a given chip area is to use SIMD, and that's here to stay, with all the associated issues.
      - wmf 18y ago
        Except threads will be called fibers, and blocks will be called threads. That's how their rasterizer works, but I'm talking about using it as a regular x86. The way to get maximum performance out of a given chip area is to use SIMD, and that's here to stay There's a big difference between MIMD+narrow SIMD and super wide SIMD.
        miloshh 18y ago
        The Larrabee SIMD width will be 16 and NVIDIA's is currently 32, so that's almost the same. Not just the rasterizer, but any application that wants to take full advantage of Larabee will have to use the SIMD vector units to the max. Larrabee might turn out to have great performance (which I hope), but if it does, the reason will not be black magic or breaking laws of physics. The reason will be SIMD.
        wmf 18y ago
        For some reason it's easier for me to wrap my head around one thread driving a 16-wide SIMD unit than 32 threads that execute in lockstep. I know it ends up being equivalent but it feels different. Also, on Larrabee you can execute a different kernel on each core, while on GPUs you can't.

by miloshh 18y ago

What are some of these complex tasks you had in mind? I think that almost any computation-bound task, however complex, could benefit from GPU acceleration. But I would like to hear about exceptions.

DarkShikari 18y ago

A motion search, for video compression, is what I was trying. It has some huge disadvantages: 1. The threading model is completely unsuited to a search that takes a different number of iterations per block (since it wants all the threads doing the same thing). 2. CPUs already have the PSADBW instruction, which allows an absurd effective throughput: its literally an instruction dedicated to this kind of task. Its also a purely 8-bit integer problem, so it doesn't benefit from the high-performance floating point units on the GPU. Due to 1), you're pretty much restricted to either crippling your performance, using a very simplified search, or using an exhaustive search. And if you're using an exhaustive search, it turns out that there's a mathematically equivalent and vastly faster way to do it called "sequential elimination"... which is completely impractical to implement on a GPU as well due to its linear nature, and which allows a Core 2 to vastly outperform a GPU and possibly even be competitive with a dedicated FPGA doing a normal exhaustive search.

miloshh 18y ago
Hmmm.. OK. You mind posting a link to the pseudo-code of the algorithm? The problem of different number of iterations per thread is quite common, but can often be fixed. If all threads in a block have the same number if iterations, you're fine; different blocks can take different number of iterations. As long as the number of blocks is much higher than the number of SMs, the machine will dynamically schedule the blocks to available SMs. If each thread takes a different number of iterations, it's more difficult, but you can still do dynamic allocation yourself, by running as many blocks as you have SMs, and having each thread pick up work as it needs. You can also randomize the assignment of work to threads, so the expected amount of work is roughly the same. This all depends on the particular problem and data, though... As for the 8-bit nature of the problem - this is true, you're not utilizing the floating point units that are the biggest advantage of the GPU. How large are the vectors you need to do PSADBW over?
- wmf 18y ago
  If all threads in a block have the same number if iterations, you're fine; different blocks can take different number of iterations. As long as the number of blocks is much higher than the number of SMs, the machine will dynamically schedule the blocks to available SMs. At this point the programmer's head has already exploded. MIMD systems (like OpenMP on Larrabee) don't have any of this BS.
  - miloshh 18y ago
    No, Larrabee will have exactly the same issues. Except threads will be called fibers, and blocks will be called threads. Read the Larrabee paper from Siggraph 08. The way to get maximum performance out of a given chip area is to use SIMD, and that's here to stay, with all the associated issues.
    - wmf 18y ago
      Except threads will be called fibers, and blocks will be called threads. That's how their rasterizer works, but I'm talking about using it as a regular x86. The way to get maximum performance out of a given chip area is to use SIMD, and that's here to stay There's a big difference between MIMD+narrow SIMD and super wide SIMD.
      - miloshh 18y ago
        The Larrabee SIMD width will be 16 and NVIDIA's is currently 32, so that's almost the same. Not just the rasterizer, but any application that wants to take full advantage of Larabee will have to use the SIMD vector units to the max. Larrabee might turn out to have great performance (which I hope), but if it does, the reason will not be black magic or breaking laws of physics. The reason will be SIMD.
        wmf 18y ago
        For some reason it's easier for me to wrap my head around one thread driving a 16-wide SIMD unit than 32 threads that execute in lockstep. I know it ends up being equivalent but it feels different. Also, on Larrabee you can execute a different kernel on each core, while on GPUs you can't.