Structured Grids, Branch and Bound and Graphical Models

Structured Grid Computational Pattern
This is a very common pattern that is very easy to get a mental image of. Structured grids model spaces in N dimensions as discrete points that interact. Their interaction can be regular or irregular (this pattern only talk about regular interactions) and in the regular case they are usually characterized by a fixed-size stencil.

We discussed it in class today and the biggest problem with this pattern is that it overlaps heavily with geometric decomposition. Indeed it actually describes geometric decomposition as the essence of the task manager described in this pattern's solution. First, geometric decomposition is about decomposing and solving geometric problems in parallel with the issues that bring and is not just a task manager. Second, if geometric decomposition was the essence of a subset of this solution then why would one have that pattern at all. A much more sensible strategy is for this pattern to discuss the problem/solution of performing structured grid computations, discuss stencils and then provide pointers to patterns that can be used to parallelize it. This could of course be geometric decomposition, but also master worker, etc. In particular this means that border exchanges belongs in geometric decomposition (which only mention them for about one paragraph. Indeed, as a part of cs527 I have actually written an entire pattern about just border exchanges. The current draft, with all its flaws, can be found here: URL.

Also, border exchanges as described in this pattern are insufficient to implement their first example. Even if the ghost nodes extend three rows/colums out from their chunks as they mention they still have to deal with the (literal) corner cases as their stencils will need cells from diagonal chunks. To see how this is usually handled refer to the border exchange pattern above.

Actually, todays discussion made the tight relationship between geometric decomposition and border exchanges clearer to me and I am wondering whether it would make sense to attempt to extend my border exchange pattern to be a geometric decomposition pattern or perhaps to try to merge them. It would give geometric decomposition a very specific meaning, more so perhaps than the OPL authors intended. It would essentially cover data-parallel, iterative refinement algorithms with border exchanges, but for me that is what geometric decomposition is. In patterns I value preciseness more than completeness. The original design patterns had this property. They did not give a complete design framework that is sufficiently vague to be complete like many textbooks attempt. Instead they gave crisp, specific and often non-intuiative solutions to concrete problems and for me it was this that gave them their greatest value. Besides I suspect other data-parallel algorithms with other types of communication, like the tiled N-Body example given in yesterdays OPL session, are covered by the Data Parallel pattern.


Branch & Bound Pattern
This pattern was pretty good. It started out with a decent example in the SAT decision problem and gave a good explanation of issues with branch and bound by authors who seemed to know what they were talking about very well. One area of potential improvement would be to add a code example. The paper also seems to implicitly conclude that structure-based parallelization is the one that makes sense, but if that is the case then why talk about the other two. Potentially the construction-based parallelization can give less synchronization overhead at the cost of more work, but I can't see a case where I would want operation-based parallelization. If there are such cases then the pattern should address those.

Another possible improvement that was suggested in class would be to start off with a chess or checkers example. The examples that are there are good, but I suspect many more developers will have some mental image of how a computer chess player searches for moves. It would at least be a more colorful and graphical example as the first example.


Graphical Models
When first reading the title of this pattern I must admit I was thinking of 3D meshes. We discussed it in class and other seemed to have other first-impression, but none seemed to match what it actually is about. Professor Johnson suggested that maybe it should be called s Probabilistic Methods or Stochastic Methods, both of which would have been preferable.

Even after reading the pattern I have no idea about how where it would apply or how I would start applying it. It lacks an example and I happen not to know the Junction Tree Algorithm. An example would have gone a long way, but even the pattern lacked pointers on how to go about parallelizing it. Other computation patterns has a parallel issues section and some, like circuits, are sprinkled with pointers to other patterns. This one had one line that said that "This search can be rather trivially parallelized" related to trying out randomized factorizations, which leads me to suspect that other parts of the patter can be parallelized. If not then wouldn't this just be a subset of branch and bound or perhaps something simpler?