Loop Parallelism, Task Queue, Graph Partitioning

Loop Parallelism
1. The author says the goal of incremental parallelization is to "evolve" a sequential program into a parallel program. If you have experience in refactoring code from sequential to parallel, how did your approach differ from the steps presented in the paper?

We currently have a project at work where we are transforming a sequential firmware to a parallel program. The approach we are taking is the same as described on this paper. We are incrementally applying transformations to selected area of the code to achieve parallelism. This is approach is the only option we have because people are not opened to a complete rewrite of the system. The advantage of incremental parallelization is that it is easy to debug and test the program because the code should still work correctly after each change. We are running our regular regression test after each refactoring and that give us confidence after each step.

2. Many of us have used Eclipse or another IDE, with their respective plugins, for execution profiling. What has been your experience with these tools? What is your preferred method of locating the code in question (automatic or manual)?

In this class we have read about many tools in eclipse that can be helpful because the work in automated. I prefer to use tested tools if they are available. Manual work is painful, but sometimes that is the only option available.

3. The author states, "The application of many transformations to many loops may be necessary before efficient performance is achieved." What is your opinion on this statement?

That is expected because of the Amdahl law as mentioned by the author. Enough code needs to be optimized to achieve the desired speedup. So it is good to target the areas with greater parallelization potential first.

Task Queue Implementation Pattern
1. How would you compare the Task Queue pattern to other similar distribution patterns like divide-and-conquer and fork/join pattern?

I think this pattern has the same idea as divide-and-conquer and fork/join pattern. They all involve dividing the work into independent subtasks and executing them in parallel. I think the task queue can be used to schedule the subtasks created by divide-and-conquer and fork/join.

2. It was nice to see a pattern with some actual code examples. How important were the examples in understanding the concepts presented in this paper?

The idea of the pattern is straightforward: First divide the work into independent units, then decide between eager and lazy scheduling, and finally decide on centralized or decentralize task queue. The author explains the tradeoffs between simplicity of implementation (centralized task queue) and scalability (decentralized task queue) the code examples presented were helpful as an illustration of the idea presented.

Graph Partitioning Implementation Strategy Pattern
1. This was probably one of the more math-oriented patterns I have seen and/or read. How often have you experienced a situation where the graph partition strategy would have been useful? If never, can you think of any future situations where this pattern might be come in handy and could be applied?

I thought I was reading a chapter of the “hard” algorithm's class I am taking this semester. I have a very good understanding of various problems in graph theory and I think this pattern did a great job at explaining the theory. I don’t have any experience with real world applications that uses the Graph partitioning strategy. More example of applications of this pattern would have been helpful.