Re: [computer-go] Hardware-Instruction.

["chrilly" <chrilly@xxxxxxxx>]

>I don't think I would want to get into using CPU-specific instructions. But
>I must say I've sometimes thought about what could be useful to have in
>terms of Go-specific hardware. In Tsume-Goliath I think I found that the
>single most expensive function was getNlib(), which would retrieve the
>number of liberties of a chain at a certain coordinate and put the
>coordinates of those liberties in a little list, with a maximum of 'n'
>liberties. A very simple and basic function, used in a lot of different
>places. The total time spent in this one function was something like 20 or
>30%.
>
I think it is not easy to implement this function efficiently in hardware.
It is trivial if one accepts - as worst case - N cycles (where N is the
length of the chain). But if one wants something like log(N) or even 1 cycle
it gets difficult. In my paper designs I have not found a reasonable
implementation for log(N). The problem is that two stones of a chain can
share the same liberty. How does one avoid dubble-counting when summing up
the liberties in parallel? If one counts sequential like in software one can
mark the liberties. This is the N-cycles method. But that would be no big
improvement. If one makes a hardware Go-programm one has to solve this
problem. I think its solvable. One has just to have the right idea.
I know of some papers of finding connected components in picture-processing
in log(N) time. This is the same problem. But the algorithms are very
complicated. I can not imagine how to implement this directly in hardware.

Chrilly



_______________________________________________
computer-go mailing list
computer-go@xxxxxxxxxxxxxxxxx
http://www.computer-go.org/mailman/listinfo/computer-go/