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.

Dense Linear Algebra, Graph Algorithms, and Monte Carlo

I have never used any of these patterns. I also never heard of them specificity, but I knew of the ideas behind the first two patterns. The Linear Algebra pattern allows for the efficient calculation of matrix multiplication. It does this by using outer products and improves on spacial locality by splitting up the matrices into blocks. Which lends to the caveat of this pattern. In order to use it, the programmer needs to be able to control how the matrices are laid out in memory.

I am currently in the Algorithm course here and I have seen that lots of problems can be easily solved, as well as visualized, with the help of graphs. There are many ways in order to store graphs in memory depending on the type of graph and this paper does a pretty good job at explaining it.

The monte carol pattern is the one I never heard of before and its design is an interesting one, if not simplistic. How it works is that is runs many different independent experiments in parallel, then it computes the summary of all the results.

Armstrong Chapter 2

This chapter focus on fault tolerant systems with an emphasis on switching equipment. The paper says in order to be fault-tolerant, the systems needs to be fault-isolated, which means a failure in one part of the system will not effect the whole system. This is achieved in the paper by running each modules in separate processes and the communication between these processes is read-only. This way an error in one process will not infect another. There is a lot of overhead when this is done with OS processes.

I am reminded of the other paper in the book about fault-tolerant operating systems, Guardian. Guardian's system was about redundancy. It had duplicated hardware as well as software processes. This is more of trying to isolate systems as to not interfere with one another.