Hacker News Reader

Comment by sillysaurus | Hacker News Reader

Can you give an example of an algorithm that you feel is difficult to port to a GPU in a way that takes advantage of its capabilities? I'd like to try my hand at porting one. It's a lot of fun and hasn't been difficult so far. I'm genuinely curious whether it's odd that "taking advantage of the characteristics of different kinds of memory" is quite natural to me, or if I have a distorted view of my own capabilities. Either way I'll learn something, though, which is the fun part.

(Obviously something like scrypt would be difficult to port to a GPU since by definition it's un-parallelizable, but other algorithms should be doable.)

View on HN

Dijkstra's shortest path. (IE: Pointer chasing). Goertzel's algorithm

If you have a simple, straight through algorithm running on a few million datapoints. GPU's are great. If it deviates even a little from there, gpu's start to fumble. Writing those two algorithms is an afternoons exercise in Mathematica or matlab, but several weeks adventure on a GPU.

And remember computers are cheaper than humans (Currently, $0.12/hr at amazon and $10/hr minimum wage).

Try any P-complete problem or arbitrary integer multiplication.

Have you started benchmarking, yet? Just see if you a) can do way better than the CPU, and b) are competitive with other people porting to the GPU. Of course, you'll have to choose an algorithm that's already ported for the second comparison.

Regarding the second comparison, it's easy to do trivially better than someone else's work if you use their work as a starting point. But that type of optimization doesn't really matter as much as the first one you mentioned: the ability to "take that which would have run on a CPU, and parallelize it to run on a GPU.". It has always felt quite natural for me to do that, so it was strange to hear that it's so hard for others. Why is it difficult for them, but easy for me?

The easiest way for me to solve this mystery is to try to port an example someone considers difficult. Do you know of any?

try matrix multplication. I mean a real matrices, say 10000x10000. And once you're there, try a LU decomposition of matrix, with proper numerical erro handling. You'll soon get to the point where you fell it's harder than you tought. And BTW, matrix multiplication or LU decomposition are super fundamental stuff when solving equations (which in turn is super fundamental when you want to compute bridges, constructions, aerodynamics, etc...)

Sparse or dense matrices?

I don't know very much about this, but do you think that part of your success has just been the benefit you get from going from dynamic ram to static ram? Seems that alone would give you a baseline performance improvement?

GPUs use dynamic RAM too (though discrete cards usually have GDDR rather than DDR, which gives higher bandwidth). The most fundamental difference between a CPU and GPU isn't the memory hierarchy (modern GPUs are growing cache hierarchies as well) but the core architecture (vector/highly threaded "small cores", vs. out-of-order/superscalar "big cores").

Reply on news.ycombinator.com