Planning for parallelism

Question

If you plan to write a very computationally intensive parallel application, what guidelines would you use to design your objects (whether classes or structs, or anything else) to maximize your potential of getting the most out of the parallelism.

I am thinking of an application that say interprets/compiles a tree-like graph of objects that require creating stuff, passing it to another object to be processed, and so on, with tree like structure.

What should one consider from the early design process?

Answer 1

If you can get away with using a lot of immutable data structures, that will save you a lot of time, typing, and headache.

Answer 2

If you're creating stuff and then passing it to be processed then almost surely you can design your application to make use of message passing and object isolation.

First step will be identify responsibilities, that is, identifying who is gonna handle what. Every who is rounded by a box.

Second step will be defining the information flow between your boxes, that is, if A produces X... who consumes it?

After that two steps you'll have a simple graph with leafs representing workers and arrows representing messages. Every arrow represents a dependency order (that is, if an arrow goes from A to B then A needs to be executed before B).

With this you'll be able to easily see what actions can be made parallel and what actions are indeed sequential in a graphical easy to see, easy to show way.

Then just implement a Pipe structure to let you pass messages between workers so that every worker has a pipeline of work.

On a final note: Once the original design is done, it's relatively easy to refactor it in order to improve. For example, nodes which make the same work can share work PIPES, so that 8 syntax analyzer consume from the "lexic token" pipe, or change it so that workers can "steal" work from other workers pipes, etc.

Answer 3

The pattern Jorge Córdoba describes above is just one approach. The following is definitely worth a read:

http://www.amazon.com/Patterns-Parallel-Programming-Software/dp/0321228111

It very much depends on the dependencies between your data as to the best way to decompose your problem. For example, patterns like Master-Worker and single program multiple data (SPMD) tend to be very simple approaches if your problem lends itself to sunch and approach.