Parallelism in D?

[Jason House]

Craig Black wrote:

> 
> "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?

Go and chess are both complex games, but computers perform far worse at go. 
In fact, I play go better than the best computer did when I entered the
field.  They beat me now, but are still quite far from professional
players.



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

I had to invent my 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?

Unfortunately, I would expect it to get worse :(



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

I meant a post on the computer go newsgroup.  I couldn't find the post when
I wrote my reply to you :(  It was written in some other language (C++?)
and is not open source.  When I get the time I'll likely try my hand at
doing that too.


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

Thanks.