Parallelism in D?

[Jason House]

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.


> 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.

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.

> 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.

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