I worry that this problem statement could almost work just as well for the “graphical algorithms’ pattern. It needs to be more narrowly focused. How about:

• For a problem represented in terms of a graph, how do we decompose this graph into sub-graphs so we can efficiently exploit the concurrency in the problem?

Notes from the class workshop 4/8

What should the graph be representing?

There are two categories of graph representations:

1. problem representation (data structure)
2. algorithm execution (task)

Your context section assumes the reader already knows about parallel graph algorithms and graph partitioning. Remember, the goal is to setup the context of the problem such that it leads you into graph partitioning as a solution.

I’d reorganize your content to stress the following progression:

• Many important problems are based on computing over graphs. Present your existing content about PDE solvers and solutions to the sparse linear algebra problem.

• To exploit concurrency, you need to decompose the graph problem into smaller sub problems. In other words, the reason to break up the graph is to expose concurrency.

• To create an efficient parallel program, the compute time required from each processing element must be roughly the same … i.e. the work required for each sub problem must be evenly divided among the compute elements.

• Dependencies between nodes mapped onto a communication network define the communication overhead associated with the problem. This needs to be minimized.

Then define the graph partitioning problem as a technique to effectively address all three of these points. In other words, don’t assume the reader knows all about graph partitioning. Lead them to this problem.

Notes from class workshop 4/8

(note: task vs data representation in the graph is mixed here, comments address both cases)

• Second sentence - talking about task graph. Need to add a sentence about graphs representing data. Edges may also have computation associated with them (speech).

• Second to last sentence in the first paragraph - main focus of the pattern (as the Implementation level pattern) - load balancing, minimizing communication/locality. This needs to be the focus of the discussion.

• Graph Partitioning is used when:

1. we have a starting problem represented as a graph, with more tasks that than processors - scheduling is the concern here
2. we need to create concurrent tasks in a problem, we use graph partitioning to accomplish this

• when parallelizing a problem that can be represented as a graph, one needs to take the data structure into account to efficiently exploit concurrency

The forces were fine.

The solution was good. I thought it was a useful summary of the key approaches used. I liked the use of clear pedagogical examples.

Notes from class workshop 4/8

Forces = Universal forces

• Accuracy vs Load balancing - accurate partitioining is good, but sometimes less accurate, over-segmented partitioning yields better LB opportunities

• Static vs dynamic partitioning

• Time to partition vs gain from partitioning & parallelism

Last sentence in the second force - unclear

Solution

Make sure to address the Forces, highlight important trade-offs.

Add mapping & locality discussion (implementation layer).

1. Find representation model - add data structure as something that can be represented as a graph.

Add examples to the graph structure descriptions.

If this is an implementation strategy pattern - move the partitioning algorithm description to an appendix and focus on the implementation considerations such as load-balancing and locality

Invariant

Tasks don't need data outside of their partition during computation

Sum of tasks in the partitions = total set of tasks

Add 3. what do you do after you decompose, how does it help parallelism (implementation layer)

This pattern appears at a low level in the pattern language where we should be guiding the user to solutions expressed as actual source code. Hence, I’d carry your example through to show pseudo code or better yet and actual working program using your API of choice.

Sparse matrix-vector multiplication is OK, but I’d prefer a more complex example … maybe a PDE solver.

You forgot the “known uses” and an “Other Patterns” sections.