Branch-and-Bound, Graphical Models, Structured Grids

Branch-and-Bound Pattern

The pattern has 4 basic operations branching, evaluation, bounding, and pruning operations. The problem is split into sub problems like branches and this decomposition can be done using some other patterns like geometric decomposition pattern or so, and then these pieces can be parallelized and run on multiple cores. Each sub problem get evaluated and if it has a feasible solution then proceed it for the bounding and then to prune so that we will have optimal solution.

I like the flowchart and it’s very nicely described. I like the algorithmic style of presenting the paper as it is appropriate for this one.

Graphical Models Pattern

Looks like this pattern is still in process and didn’t give me a feel for it be a parallel pattern. It only mentioned how transformations and searching of trees can be parallelized. I am not sure if I understand the whole problem that author is trying to solve. Looking forward for class and then reread it again…

Structured Grids Pattern

This pattern explains how to parallelize operations on a large grid or array. The pattern uses geometric decomposition to decompose the problem into smaller arrays and then operations are performed in parallel in each array. Ghost nodes are used to figure out any dependencies of neighboring nodes.

I like the double buffering and adaptive mesh refinement idea s to refine the rendering. I have read some adaptive mesh refinements before in gaming to reduce the number of vertices and edges in a 3D model. Usually this is performed during game development and cached somewhere. Overall I like this paper batter than others I have read for this week’s class.