Parallelism in D?

[Craig Black]

"Jason House" <jason.james.house at gmail.com> wrote in message 
news:fslscj$e60$1 at digitalmars.com...
> Craig Black wrote:
>
>> "Jason House" <jason.james.house at gmail.com> wrote in message
>> news:fsk0h4$2bl8$1 at digitalmars.com...
>>> Ansible wrote:
>>>
>>>> Parallel programming being the Next Big Thing these days, I'm wondering
>>>> what is out there as far as parallel programming
>>>> libraries/utilities/whatever for D?
>>>>
>>>> Has anyone created a D layer for MPI, for instance?  What about
>>>> transactional memory?
>>>>
>>>> I have a game engine that I wrote in C++ and I'm thinking about porting
>>>> to D one of these days.  Making use of those extra cores is high on the
>>>> priority list for me in the future.
>>>
>>> I'm writing a multi-threaded game engine in D.  I'm always looking for
>>> more
>>> developers ;)
>>
>> How far have you got?
>
> I started about a year ago, and have a functional game-playing engine for
> playing go.  It uses monte carlo techniques, including UCT [1] and RAVE
> [2].  I'm half-done implementing a bradley-terry model for move ordering
> [3].  Combining all 3 of those is nearly state of the art in the field of
> computer go.
>
> The framework will support other games, and other search algorithms.  I 
> have
> not implemented other games but have implemented other search algorithms.

Intersesting.  I'm not that familiar with computer go.  (I just looked it up 
on Wikipedia.)  What turned you on to computer go?  What search algorithms 
have you explored and what are the possible applications?

>
>> I'm curious as to your experience with multi-threading in D.
>
> I have 4 types of threads/processes:
> 1. Communication (via GTP [4]) to a GUI or online server
> 2. Information gathering and time management
> 3. Managing a single search (ie. UCT RAVE)
> 4. Performing a part of a search
>
> I designed it to use message queues.  Each thread has a queue for incoming
> command delegates.  Each thread is responsible for processing commands out
> of the queue when it reaches a stable state (for search threads, that's
> about once every milisecond).  The design helps me keep multi-threading
> issues in check and has so far been successful.

Does Phobos, Tango, or another D library provide facilities for message 
queues or did you have to invent your own?

>
> This was my first multi-threaded design in any language.
>
>
>> How much are you relying on GC or custom memory
>> management?
>
> I use all automatic memory management.
>
>> How much does the GC hinder parallelism?
>
> Profiling indicates about 25% of my time is spent with memory related
> activities.

That's not bad.  Do you think this would become a problem as the number of 
processors increase?

>> How do you
>> partition the workload and how scalable is your approach?
>
> Work partitioning is partially discussed above.  I've done experimented 
> with
> multiple worker threads for pure monte carlo searches, but have not yet
> invested effort in doing that for UCT or alpha beta.  A recent post (using
> a non-locking hash table) showed about about 11x speed up with 16
> processors.

Very impressive.  This is a hash table written in D?  Did you write this 
code?  Any chance I could use it?

> My latest focuses have been:
> * Using weak pointers in a transposition table
> * Unit testing search algorithms and setting up cruise control
> * Adding machine-learing based move ordering (on hold for above two)
>
> I'm ashamed to say, but I actually put the move ordering stuff on hold 
> when
> I noticed my engine was weaker than it should be.  Either my addition of
> transposition tables broke the automatic memory management or I added a
> search bug somewhere.  I've been investigating those two options.
>
> Adding search algorithm unit tests is something I've been meaning to do.
> Regardless of if it's the fastest way to fix my problem, it offers a good
> learning experience to gain practice with algorithm unit testing and 
> cruise
> control.  The engine has more or less remained under active development 
> for
> several years.  About a year ago, I switched designs and programming
> languages (C++ to D).  I'm more interested in learning D and robust code
> design than I am with being the top in the computer go field (although 
> it'd
> be a nice perk!)
>
> [1] http://senseis.xmp.net/?UCT
> [2] http://www.machinelearning.org/proceedings/icml2007/papers/387.pdf
> [2] http://remi.coulom.free.fr/Amsterdam2007/MMGoPatterns.pdf
> [4] http://www.lysator.liu.se/~gunnar/gtp/gtp2-spec-draft2/gtp2-spec.html

Sounds like a fun project.  Good luck!

-Craig