Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Parallel algorithms in chess programming

Author: Vincent Diepeveen

Date: 11:05:26 04/17/01

Go up one level in this thread


On April 17, 2001 at 13:32:12, Robert Hyatt wrote:

>On April 17, 2001 at 11:56:02, Vincent Diepeveen wrote:
>
>>On April 17, 2001 at 09:44:18, Robert Hyatt wrote:
>>
>>>On April 17, 2001 at 08:00:27, Vincent Diepeveen wrote:
>>>
>>>>On April 16, 2001 at 22:07:10, Robert Hyatt wrote:
>>>>
>>>>>On April 16, 2001 at 18:15:52, Dieter Buerssner wrote:
>>>>>
>>>>>>In a different discussion, Vincent wrote the following:
>>>>>>
>>>>>>>It is not difficult to implement the form of parallellism as used by
>>>>>>>Rudolf. Invented by a frenchman who couldn't spell a word english and
>>>>>>>who wrote an impossible article for JICCA (did anyone proofread it at
>>>>>>>the time as i'm pretty sure they didn't get his parallel idea?).
>>>>>>>
>>>>>>>At the time when i read the article i was pathetically laughing about it
>>>>>>>actually as i also didn't get the idea of the frenchman. But it appears
>>>>>>>everyone who can make a chessprogram work under win2000 can also get
>>>>>>>within an afternoon his program parallel to work. Then some debugging
>>>>>>>and a day later it works cool.
>>>>>>
>>>>>>I'd be very interested in this algorithm, that can be implemented at an
>>>>>>afternoon :-)
>>>>>>
>>>>>>Could you point elaborate on this.
>>>>>>
>>>>>>BTW. In Paderborn, Roland Pfister also told me, that he knows this from Rudolf
>>>>>>Huber, and he even started to explain it to me. Somhow, we (or me) got
>>>>>>distracted, and I cannot remember the essential things.
>>>>>>
>>>>>>What I remember is, that the time consuming work, of making your
>>>>>>search/evaluation routines free from all those global variables is not needed.
>>>>>>
>>>>>>Regards,
>>>>>>Dieter
>>>>>
>>>>>
>>>>>Global variables will _always_ be a problem.  Unless you avoid threads
>>>>>altogether and use separate processes.  But then you incur other penalties
>>>>>you have to solve...
>>>>
>>>>Multiprocessing is faster anyway of course as multithreading as i
>>>>do not need to read a stupid pointer.
>>>>
>>>>Arrays which are only read and not modified one can put in shared memory
>>>>and read from there without penalties.
>>>>
>>>>The penalty for multithreading is, when using ansi-c conventions,
>>>>way bigger as for multiprocessing.
>>>>
>>>>Multiprocessing is more than ok.
>>>>
>>>>Obviously it's not always so easy to get it to work, because of
>>>>different causes
>>>>  - allocating shared memory in linux isn't simple
>>>>  - windows NT server/tuple server versions have the bad habit
>>>>    to always swap away shared memory to the cache when the allocated
>>>>    memory size is huge.
>>>>  - to share memory in NT in such a way that programs have the same
>>>>    virtual adress space is not evident, as there are 2 functions which
>>>>    one can use and one of them is not going to work for you. Don't need
>>>>    to mention that by accident i picked the wrong function initially :)
>>>>
>>>>Of course all the above problems are solvable
>>>
>>>
>>>Just use your approach to search trees with 2 nodes.  Then tell me how efficient
>>>it is to use messages and pipes to get the other processes busy on such small
>>>trees, compared to threads which have zero overhead...  :)
>>
>>Sorry i'm missing the problem. I'm using shared memory for the
>>parallellism within 1 node to get them
>>so all i need to do is:
>>
>>  g->gosearch = true;
>
>That is sort of what I do.  With a pointer.  :)  Just like you.  :)
>
>
>
>>
>>Then all processes start searching.
>>
>>Starting threads is more expensive!
>
>
>no it isn't.. because I start the threads _one_ time.  In linux, threads are
>far faster to start than real heavyweight processes since the virtual memory
>has to be allocated, stuff read from disk, etc.  But this doesn't matter since
>we both start the processes _one_ time and keep them around for the entire
>game.  That is therefore a non-issue.
>
>
>
>>
>>Obviously using more nodes to search at is more difficult but
>>i have no idea how to start a thread over the network on a diff
>>machine :)
>
>try "pvm_spawn()"  :)
>
>
>
>
>>
>>>The pointer issue is _not_ a big one.  At most it costs a couple of percent
>>
>>For me it would be around 10% but go on.
>
>Not really.  How do you get to the shared hash table?  Magic or a pointer?
>If you want to pass a thread something to search, how do you do it?  Via a
>message (which is horribly slow) or thru shared memory using a pointer.  I
>do the latter.  When you want to tell a thread to stop searching because
>another thread found a beta cutoff in this position, how do you do this?
>Via a message?  Or via a shared memory flag?  I use the latter.
>
>Ditto for updating search bounds, etc...

Even if i walk around the church to update search, that's all not
interesting.

My evaluation is the slowest part. It is eating *all* system time
except around 10%.

in evaluation i reference a lot of the times for example:

   board[sq_e2]

If i change all those arrays to

  threadglobalpointer->snelbord[sq_d3] == wbishop
  && tgp->snelbord[sq_d2] == wpawn

then my prog gets directly 10% slower as in the
majority of my logics i have to add a pointer.

Get the problem?

there where you have a pointer for search i also have one,
there where you have a pointer for evaluation for every
array i do NOT have a pointer.

So also my makemove is hell faster because of this,
my generation is hell faster
my attacktables are hell faster
all extension functions are faster
and especially expensive logics in the evaluation is faster,

checking whether my king is incheck is not even relevant here
as i don't do that as i already know whether it is attacked from
attacktables.

Most savings for this pointer are in expensive mobility loops and in
attacktables which also eat a few % of system time.

If i count that all then 10% is a very small estimated slowdown.
Most likely it'll be more like 20%, especially with GCC which has
probs with efficient register usage!

>
>
>
>>
>>>in speed, but it also gives back a lot since threads can
>>>look at other thread's
>>>local memory if they know what they are doing...
>>
>>My entire search is in shared memory, i wouldn't know the difference
>>between that memory and memory your thread look in.
>
>Right.  And in your shared memory you _must_ use a pointer also.  :)
>Since there is no other way to access it.

Exactly, but search eats no system time in diep!







This page took 0 seconds to execute

Last modified: Thu, 15 Apr 21 08:11:13 -0700

Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.