www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Parallelism in D?

reply Ansible <notmyemailaddress nospam.com> writes:
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.
Mar 28 2008
next sibling parent Tim Burrell <tim timburrell.net> writes:
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 with you.  OpenMP support (or something similar) would really be 
ideal.  I think if D wants to continue to sway developers from other 
system languages parallel support is a must have.  Maybe gdc could be a 
reasonable path to OpenMP as it already has support for C and C++ (and I 
think Obj-C too).

Honestly even MPI isn't really sufficient these days.  MPI is [sort-of] 
great for doing clustered / distributed stuff, but no where near where 
we need to be for SMP / shared memory parallelism.

Pretty much every C++ compiler has OpenMP support these days, so it's a 
bit sad to see D lagging in this respect.  OpenMP is by no means the 
be-all / end-all of parallelism, but it's a lot better than nothing.

I get why it's a non-trivial thing for D -- first of all the use of mark 
/ sweep style GC means parallelism is more difficult.  Obviously you 
can't have a parallel system where every thread is halted whenever a 
sweep occurs, so I suspect some fairly major redesign would have to 
occur?  I'm open to being wrong about this though...

Personally I think a more advanced memory management scheme would be a 
good thing anyway, but perhaps that's just me :).
Mar 28 2008
prev sibling next sibling parent reply Jason House <jason.james.house gmail.com> writes:
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 ;)
Mar 28 2008
parent reply "Craig Black" <craigblack2 cox.net> writes:
"Jason House" <jason.james.house gmail.com> wrote in message 
news:fsk0h4$2bl8$1 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'm curious as to your experience with 
multi-threading in D.  How much are you relying on GC or custom memory 
management?  How much does the GC hinder parallelism?  How do you partition 
the workload and how scalable is your approach?

-Craig
Mar 28 2008
parent reply Jason House <jason.james.house gmail.com> writes:
Craig Black wrote:


 "Jason House" <jason.james.house gmail.com> wrote in message
 news:fsk0h4$2bl8$1 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
Mar 29 2008
parent reply "Craig Black" <craigblack2 cox.net> writes:
"Jason House" <jason.james.house gmail.com> wrote in message 
news:fslscj$e60$1 digitalmars.com...

 Craig Black wrote:


 "Jason House" <jason.james.house gmail.com> wrote in message
 news:fsk0h4$2bl8$1 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
Mar 29 2008
parent Jason House <jason.james.house gmail.com> writes:
Craig Black wrote:


 
 "Jason House" <jason.james.house gmail.com> wrote in message
 news:fslscj$e60$1 digitalmars.com...

 Craig Black wrote:


 "Jason House" <jason.james.house gmail.com> wrote in message
 news:fsk0h4$2bl8$1 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.
Mar 29 2008
prev sibling parent Jason House <jason.james.house gmail.com> writes:
You sent me a private e-mail with a fake return e-mail address...
The best option I can think of is to respond publicly here.

Ansible wrote:

 Hi Jason;
 
 'Ansible' here - I'm interested in the game engine project - don't know 
 if we'll have the same goals or not, but I'd like to know more... is 
 this an open source project?  Got links?


I don't rule the project with an iron fist, so there should be room for your
individualized development goals.  The only real requirement I have is that
the project is fully functional approximately once a month.

The project is open source, and available under GPLv3.  The best starting
place to learn more is http://housebot.sourceforge.net

You'll notice a few high level pages along with pages that show the
historical evolution of the project (starting about a year ago).  You'll
find other popular open source stuff such as a bug database and a mailing
list.  Please let me know if there's any missing/unclear documentation that
you need for evaluating the project.  I'll do my best to update them.

I can also be reached throughinstant messengers, but I prefer to give that
kind of info off-list.
Mar 30 2008