Thanks for sharing this Christian,
in my lines comments.
On Sep 9, 2009, at 5:54 PM, Christian Nentwich wrote:
I did quite a bit of testing earlier this year on running playout
algorithms on GPUs. Unfortunately, I am too busy to write up a tech
report on it, but I finally brought myself to take the time to
write this e-mail at least. See bottom for conclusions.
For performance testing, I used my CPU board representation, and a
CUDA port of the same (with adjustments), to test the following
algorithm:
- Clear the board
- Fill the board according to a uniform random policy
- Avoid filling eyes, according to simple neighbour check
- Avoid simple ko
- Count the score and determine the winner
In other words: no tree search is involved, and this is the
lightest possible playout. The raw numbers are as follows:
- CPU Search: 47,000 playouts per CPU core per second, on an Intel
6600 Core-2 Duo
- GPU Search: 170,000 playouts per second, on an NVidia Geforce
285 card
Interesting to know is how many nodes per second this is that hammers
to the local shared memory
and which IPC you overall had. This 9% might not be very accurate
read further for that.
nvidia is of course the weakest of all GPU manufacturers currently if
you run on the gpu's rather than the tesla.
Nvidia is of course most famous as they were the first with gpgpu for
the big masses and promoting this.
Note in 90s i already stumbled upon implementations of chessprograms
at graphics cards by hardware designers who did do this as a hobby,
at the time they were higher clocked than cpu's in many occasions.
Nvidia is not really revealing what instructions the gpu's have, so
this is a major bottleneck in your software program probably.
To start with it is quite possible that entire 'gflops' calculation
of nvidia is totally based upon combined instructions,
such as multiplyadd.
So streamcore in principe can do at maximum 1 instruction a cycle,
yet the numbers Nvidia slams around with are based upon
things that are counted as 2 instructions (so 8 flops) whereas in
reality it is 1 instruction at the gpu.
If you're not using this in the program then that already hammers
down theoretical gains one can theoretical achieve at nvidia.
Other manufacturers seem more open here.
Note that privately approaching Nvidia also didn't help. It was for
some potential pilot project a while ago for simulation software
(simulation of whatever
generics up to fighter jet software). Obviously a pilot is a pilot
project and not some massive deal. Nvidia indicated only wanting to
reveal *perhaps* something
in case of a paper deal of really a lot of 'tesla' cards.
As we know those are a bit pricey (not for the simulator clients), so
a deal of hundreds or thousands of pre-ordered cards, that would not
work out of course.
A pilot project is there to convince something is possible.
We know that the bandwidth from the gpu's for gpgpu work is a lot
worse than from the tesla versions of nvidia,
which is throughout your story the problem. However i see solutions
there.
Also your result is not so bad. Most likely you wrote quite efficient
software in CUDA.
So basically what so to speak limited your nps is the fact that your
software program probably is doing very little work a node.
When using more knowledge, it is quite possible that you hardly
slowdown, as latency to the memory is simply what you keep hitting.
So maybe you can make the program lossless more knowledgeable.
Also what i am missing fro myour side is some technical data with
respect to how many bytes you lookup in shared RAM for each
streamcore at each node.
For example, i might be confusing device RAM here, i thought
cacheline size is 256 bytes per read to each core.
So if you use considerable less than that, it's seriously slower of
course.
The algorithm running on the GPU is a straight port, with several
optimisations then made to severely restrict memory access. This
means the algorithm is a "naive" sort of parallel algorithm,
parallel on a per-board level like the CPU implementation, rather
than per-intersection or some other sort of highly parallel algorithm.
Memory access other than shared processor memory carries a severe
penalty on the GPU. Instead, all threads running on the GPU at any
one time have to make do with a fast shared memory of 16834 bytes. So:
- The board was compressed into a bit board, using 2*21 unsigned
ints per thread
2 * 21 * 32 = 1344 bits
Maybe it is the case the gpu is very ugly slow in bit manipulations,
these things have not been designed to do some sort of squared
cryptography.
- The count of empty, white and black intersections and the ko
position was also in shared memory per thread
it doesn't speed up near the edges to do things dirty cheap and illegal
and just gamble that illegal results don't backtrack to root ?
(this as their playstrength is real weak yet)
- String/group/block type information was in global memory, as
there was no way to store it in 16384 bytes
Maybe this gave also a severe penalty, in a few days time i'll bug
some guys from RAM companies on this subject.
Optimal speed was at 80 threads per block, with 256 blocks. The
card had only 9% processor occupancy, due to the shared memory
being almost exhausted. However, branch divergence was at only 2%,
which is not bad at all - suggesting that the form of parallelism
may not be a block. This may be because the "usual" case of a point
either being illegal to play, or a simple play without a need to
merge or remove strings is by far the most common case.
Conclusions:
I see these results as broadly negative with the current generation
of technology. Per-board parallelism on a GPU is not worth it
compared to the CPU speed and the severe drawbacks of working on a
GPU (testing is hard, unfamiliar environment for most programmers,
lots of time to spend on optimisation, etc).
I see your result very positive, but indeed as you say a big problem,
which also in my calculations was there of 2 years ago,
is that the cache size per core is a problem.
Did you consider AMD 770 card?
It has 4x more cache per core and each core consists out of 5
execution units.
The problems would be severely compounded by trying to integrate
any tree search, or heavy playouts. Trees are almost impossible to
construct on a GPU because pointers cannot be transferred from the
host to the GPU. They could still be represented using arrays, but
the random nature of tree access would cause huge penalties as it
would prevent coalesced memory access.
GPU requires total different approach. The big advantage you have on
the thing is you can put through huge amoutns of instructions.
The real problem is that it is so fast that when you access the
device RAM that you run into serious trouble.
If some dozens of streamcores read from the same RAM that's a big
problem.
Highly parallel algorithms (e.g. one thread per intersection) can
still be investigated, but my (unproven!) intuition is that it is
not worth it, as most intersections will be idle on any given move,
wasting processor occupancy time.
nah i find the result very encouraging in fact, as you started with
shitzero information on how to avoid the RAM and have no clue about
which instructions the gpu actually
implements.
the trick is more to focus upon *where is the gpu good at* i feel.
You've tried a cpu approach here and are faster than a dual core and
a lot.
That's much better than others who tried.
It needs a step by step improvement and more thorough understanding
of how the hardware works and its capabilities,
to know where to improve.
For example with cpu's we know that the L1 cache has a throughput of
1 (intel) or 2 (amd) a cycle, and a latency that's quite bad.
We can easily measure to be within L1 or how much we are outside, yet
just a few do it.
If you would post on this list: "how many L1i and L1d misses do you
have?" i bet nearly no one can answer it.
In case of my chessproggie it's 1.34% misses in L1i (core2) and 0.6%
to L1d (just 0.1% gets found in L2 the rest is hashtables to RAM).
From the people who know such technical details, you would need
someone who is clever enough to find a plan and a use for what the
gpu's CAN deliver,
namely more instructions a cycle, than quadcores can.
So all kind of things that work rather branchless get very cheap.
For example software with big evaluation functions (or knowledge to
select moves) will be able to improve quality of the program
meanwhile get nearly the same nps like you got,
and at quadcores they would slowdown a lot.
My feeling is that GPUs may have some potential in this area, but
possibly in a supplementary role such as running additional pattern
matching in the background, or driving machine learning components.
Some chinese researchers reported already a while ago they achieved
at 8800 based gpu's an efficiency of 20-25% of nvidia and 40%-50% at
ATI/AMD cards for their
embarrassingly parallel software. It was not 100% clear what type of
software though as they might not be happy to reveal exactly what and
how.
Now with an attempt here that's totally hammering onto the latency of
the caches and RAM, you already get 9% at a first attempt, that's
very freakin good.
Vincent
This e-mail is a bit hurried, so.. questions are welcome!!
Christian
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
