It seems that with the increasing power of GPUs on consumer graphics cards, more and more people are trying to figure out what to do with GPUs other than graphics. The scientific computing society has been extremely interested in its uses and have found that GPUs can do sort of large number of elements up to 50 times faster than a CPU can due to the built in parallelism. More on General Purpose Computation on GPU can be found here: http://www.gpgpu.org/ So, my question and idea is whether we can offload AI load from CPUs onto GPUs as well. Of course, to a certain extent it may not be practical, but it would just be one of those cool things that you can say, "hey look, my graphics card can do this too." type of deal. So, for AI in games, I guess the first question people will ask is, "Can we get a GPU to do the A* algorithm for us?" If we can, then that may be fairly interesting application wise too. I know they have pure GPU oriented particle system engines, so why not GPU based game AI engines? Steal a few cycles from the graphics and use it for better AI. So, what do people think?

The problem is that its expensive to get data off the graphics card, no matter how easy it is to put it on the card or do the operations. I don't think it will be practical, but I have no facts to back this statement up.

Your primary problem will by the types of operations the GPU can do. If you are really interested in pursuing this, I would suggest working out the simplest algorithm you can, and heading over to the graphics groups and see if anyone has any ideas.

Off hand, my guess is that your first difficulty would be handling random access needed when exploring neighbors in a search algorithm. Graphics cards are more designed for algorithms which take small, predetermined data sets and work in parallel.

I'd be pretty impressed if you could get a full A* algorithm working on the graphics card, but considering a real implementation should be able to handle an arbitrary graph (and not just a square grid), I don't imagine it'd run much faster.

Quote:

Original post by Foxostro The problem is that its expensive to get data off the graphics card, no matter how easy it is to put it on the card or do the operations. I don't think it will be practical, but I have no facts to back this statement up.

I don't know if that will be a huge problem. An A* algorithm only needs to return the completed path to be useful, and you can probably store the path in something like 500 bytes. An enormously complicated neural network only needs to return the values of the final layer. In general, the data that represents "what action should the AI take" is going to be pretty small. So as long as it's cheap for the GPU to send us back 1k or so of data, we'll be alright.

Quote:

Original post by pinacolada Quote: Original post by Foxostro The problem is that its expensive to get data off the graphics card, no matter how easy it is to put it on the card or do the operations. I don't think it will be practical, but I have no facts to back this statement up. I don't know if that will be a huge problem. An A* algorithm only needs to return the completed path to be useful, and you can probably store the path in something like 500 bytes. An enormously complicated neural network only needs to return the values of the final layer. In general, the data that represents "what action should the AI take" is going to be pretty small. So as long as it's cheap for the GPU to send us back 1k or so of data, we'll be alright.

Alright, nevermind then. I hope this idea pans out! :)

A* is not an algorithm that lends itself to parallelization, so it's unlikely that a GPU-based solution would be at all performant.

IMHO, the "Stupid GPU Tricks" fad is one that is fading, fast. The bottom line is that a graphics card is designed for graphics. It's more programmable than it used to be, but the transistor layout is still one that's optimized for the rasterization pipeline and not for other things. The need for generalized parallel processing hardware on consumer-level computers is clear, but the GPU is not the chip that will fill this niche. Time spent on bludgeoning a GPU into executing algorithm XYZ is time wasted.

Well, in many aspects, if memory doesn't fail me, some modern GPUs have higher transitor counts than many CPUs currently on the market, but I guess the main issue in trying to "bludgeon" a GPU into doing what you want has to do with the fact that you need to first "bludgeon" programmers into thinking in a different way.

Architecturally, a GPU operates on the opposite extreme of most general purpose CPU, that is if memory surves me correctly. Where standard CPUs are constantly swapping operators, the GPU is constantly swapping data (streaming). So, programming for the two require the programmers to think differently.

Currently, it seems that mainly algorithms that can be massively parallelized will get benefits of GPU speed up, since your data is actually loaded in the form of a texture and them modified by a fragment program, which runs parallel for all pixels in the texture. So, I guess A* may not be the best candidate out there, but who knows, with some twisting of things, someone might be able to think differently and solve it in some strange convoluted way.

I guess the main reason I started this thread was to see how people thought about the possibility, whether its there or not, and just gauge reaction. As for anything concrete, I really don't have anything solid myself, which is something I'll probably work on in the future.

Quote:

Original post by WeirdoFu Well, in many aspects, if memory doesn't fail me, some modern GPUs have higher transitor counts than many CPUs currently on the market, but I guess the main issue in trying to "bludgeon" a GPU into doing what you want has to do with the fact that you need to first "bludgeon" programmers into thinking in a different way.

Not really. Perhaps game programmers, or PC application developers in general, but they're hardly the totality of computer science. People have been making algorithms specifically for SIMD architectures for decades. Simply parallelizing an algorithm, however, is not the end of the battle. You still need to deal with the fact that the GPU expects to work on 4-element floating point vectors; that it wants to perform triangle rasterization; that it expects to only perform random access in the form of "textures"; that it's unable to perform any cross-core communication. None of these limitations are inherent to SIMD architectures, and none of them needs to be present in a consumer-level SIMD chip.

If you're interested in path planning on parallel architectures in general, I think that's a very noble goal. A quick Google Scholar search turns up a few links; it seems that most researchers have approached the problem using the potential field approach, which intuitively is more parallelizable than A*.

Quote:

I guess the main reason I started this thread was to see how people thought about the possibility, whether its there or not, and just gauge reaction. As for anything concrete, I really don't have anything solid myself, which is something I'll probably work on in the future.

My reaction: I just got back from the SIGGRAPH conference. The last couple of years, there was an imperial buttload of papers and sketches and posters and courses on GPGPU. This year, there were noticeably fewer. Personally, I think researchers are thinking about the cell processor, and about how much they hate having to think about pixel shaders in order to write database software. Mark my words: within five years, we'll see multi-core processing on Intel and AMD processors. Get ready for that.

idea patent pending :D