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