PRES

The first thing I thought when I read that this was going to talk about to recreate bugs in a multi-threaded system was the previous paper CHESS. In CHESS, the system was basically trying all possible thread interleavings (being smart about it of course) in order to replicate the dreaded “Heisenbug”. PRES on the other hand has an slightly different approach. Instead of trying to achieve all possible thread interleavings, PRES trys to use previously known interleavings or execution sketches as guidelines and feedback from failed replays to get closer to reproducing a target concurrency bug.

Armstrong Chapter 6

We have finally come to the end of the Armstrong thesis. I thought this chapter did a very good job explaining how everything we have read up till now connects so well together. I liked how the supervisor structure that was talked about in the previous chapter was used to add a hierarchy to a parallel structure to protect it from faults.

Overall I really enjoyed reading the thesis as a whole, even though some of the code examples required me to stare at it for quite sometime in order to really know what was happening.

Loop Parallelism, Task Queue, Graph Implementation Strategy and Pipeline, Geometric Decomposition and Data Parallelism

This is one of the most practical patterns I have read about parallelizing code. Its premise is so simple. It starts out by identifying key loops within a program. Then you analyze how that loop handles data and its dependencies. The next step is the heart of the pattern and the most work, in my opinion, to identify key loop transforms. The author provides a list of common transforms that can be used on most occasion. The programmer will then keep applying these transforms, ensuring that serial equivalence at each step.

The Task Queue pattern can be defined as a “mechanism to synchronously distribute a sequence of tasks among parallel threads of execution”. The idea is that problem is broken down into smaller “tasks” which are then placed in a queue. Parallel threads will then take tasks off the queue and perform computations on them.

The graph implementation strategy paper seemed to talk more about how to partition the graph than how to incorporate parallelism by exploiting the concurrency in those graphs.

Pipeline is a very simple pattern that achieves parallelism by dividing the operations or the data into stages that can be acted on in parallel. It seems very familiar to the pipes and filters pattern. I have not personally used this pattern, but I understand why this pattern is widely used.


I don't think there is much to say about the Data Parallelism pattern. I just thought it was weird that it was only 3 sentences long.

Armstrong Chapter 5

Let's face it. No one can write perfect code. The best we can hope for is to write fault tolerant code and even that is difficult. One of the first things that needs to be understood by the programmer is what exactly is an error. There are also different levels of severity for errors. Some errors can be handled by the function that caused the error, while others may need to know more information in order to fix the problem. In these cases the programmer will just throw an exception and let the supervision trees handle where to take the problem next. Supervision trees are hierarchies of processes where the parent has an OR/AND relationship with its children. If a parent receives an exception from one of its children, depending on its relationship, it may restart one or all of its children processes.

Task Parallelism, Discrete Events and Recursive Splitting

Well this no better way to start off this blog than to answer the first question.

1)When you first saw this pattern title, did you feel like you knew the subject beforehand? After reading the pattern, did you confirm your impression or did it surprise you? How?

I have to be honest I did think that I knew what the subject was and I was surprised. I thought that is was a simple pattern of trying to add parallelism to sets of independent data. It was very interesting to see how this sort of pattern can be used to solve a wide range of problems. It would have been nice for me if they gave a simple code example to flush out the pattern a little better.

Recursive splitting was a very well written straight forward pattern. The examples they gave also helped clear up any confusion on what the pattern was actually doing.