Pipeline, Geometric Decomposition, Data Parallelism

Geometric Decomposition

This pattern is another use of divide and conquer, divide up the data structure and do computation at each unit. I did not find this pattern interesting. Although in the task schedule part, the author express a preference on static cyclic allocation, I think it is hard to keep the load balaced when the computation become sparse. And for the dynamic scheduling, overhead is a big problem. A combinition of the two might help, static first, then switch to dynamic when reaches some threshold.

I think the most challenging part of this pattern is the update operation, cautions and supervisions are necessary.

Data Parallelism

Alright, this is all? Shortest pattern that I've ever read. A pattern looks very likely to Geometric Decomposition, but view it in another dimension, which is keep the data chunk fixed and move the command sequence on them. I am not sure how to combine those data chunck during the processes though. I don't think it is anything like the MapReduce because I could not find in the description of how to combine those data sets. Maybe as it said "When the operations are for the most part uniformly applied to these elements, an effective solution is to treat the problem as a single stream of instructions applied to each element." it does not contain the combine part. Still, I could not see this pattern very in a useful way.

Pipeline

As its name tells us, this pattern is about dividing work into simple steps, set up multiple stations and each station works based on the production from previous one then send to the next. The biggest challenge is to divide the work in order to have a fairly similar runing time on each station to avoid bottleneck. I think the idea is much like the Data parallelism, but this pattern is described in a more understandable way and provides a lot more details. I actually read this pattern after the Data Parallelism and I think I'm wrong about no combination in Data Parallelism Pattern. The combination itself should be a station and the data to combine can be send as works or just messages.

Armstrong Chapter 5

This chapter describe a method in programming fault-tolerant system: the supervisor and hierachy of tasks. I think this kind of hierachy is very efficient in error handling in a way that the supervision processes are very important, especially in identify the errors.

Recently,we see a lot of this kind of "divide and conquer" ideas in patterns and parallel programming, I think the supervisor and the hierachical way of managing is a variant of this central idea.

Task Parallelism, Recursive Splitting and Discrete Event patterns

Task parallelism
I think this pattern is really straight forward by the name if you read the content first. This pattern should belongs to structural pattern because basically it describe a abstract structure. I think better run times can be get from software as well as from hardware. Sometimes a better implementation can save us some time. I believe this pattern is not platform relavant, but yes I think learn more about hardware platform can make a better implementation sometimes.

Recursive Splitting
I found this pattern somehow interesting, because there is nothing really new in this pattern, but it is described in a more computational way. And this pattern is able to add some other patterns to it.

Discrete Event Pattern
I like the message passing most, but under some circumstances, shared-memory can be easier to use, maybe abused a lot. I think the accurate deadlock detection can be hard but simply timeout can be misleading too. Sometimes we do want to know if it is the deadlock or other problems cause timeout.

Dense Linear Algebra,

I haven't use or heard those patterns.

I think the Dense Linear Algebra is easy to understand and the author try to make it easier to understand by using a lot of picture to illustrate.
For Graph Algorithm Pattern, I think I see enough definition in the paper that can help understanding the problem. Monte Carlo Pattern gives two examples which I found useful in understanding the pattern.

To me the computational pattern and the structual pattern are all aiming at efficiently solving certain problem. Structual patterns ease the design by building up relationships between entities in a simple way; Computational patterns find the best math model for the problem in the solution space. Hmmm, I will say the distinction is fuzzy.


Small problems that I have when reading through the patterns.

For Dense Linear Algebra, in performance analysis, isn't O(N^3) > O(N)? Why it seems like BLAS level 3 stand out?

Armstrong Thesis Ch 2.

I think the six descriptions are great guidelines of characterizing the software architecture.  If I try to describe a system, I might use the some of them, probably not all.  I don't see the necessity of the construction guidelines in majority of the system descriptions.



I don't have much experience in parallel programming, and I don't remember that I've ever worked with a system with inter-process communication solely via messages.  I'd like to hear some examples tonight.


I think the "fast-fail" idea is suitable with the requirement of the system, which has a lower tolerance of fault. I think in the Thesis, the author lists some properties that needs to be built in such as a failure status need to be recorded and the isolation of crashed processors.

I think it is a good decision to make for treating the messaging layer as unreliable in the telecom environment that is working.  The tradeoffs will be the additional confirmation in the system.

Event based implicit invocation & Map reduce

Event based implicit invocation

I think the difference between this event based pattern and observor pattern is the medium.  The similarity exists in that both of the patterns do some decoupling job to separate the publisher and subscriber to get better scalibility. And event based pattern uses medium as a hub to receive/dispatch the event whileas the observor is one to one.

Implicit invocation makes it ideal for broadcasting and requires less process for the medium.  I don't know about the security here to broadcasting. 

I think the "standard" messaging mechanism can only be achieved flexibly using a "middle man", since the one to one relationship is not good in adding new members.  An extra layer of abstraction is needed here.

I think that kind of structrue is widely used in distributed system.  The main error handling should reside in the "hub" so that error messages can be passed along or to be handled. But there should be some simpler error handlings in "node" too, in case the "hub" fails.


Map reduce

For some reason, when I saw this master-worker pattern, I immediately thought of the propagation of Storm, they share the same concepts of managers and workers. And because of this really efficient way of managing the robot machine, that spam spread very quickly around the world and I think parallel programming can be benefit from that too. 

Refactoring for Reentrancy

This is the third paper discussing about refactoring in paralellism.  This paper is dealing a more difficault problem, creating a program that can be run in parallel on multicores without additional control or separate VM for each program instance.  Like previous two papers, the refactoring of making program reentrant needs several steps that contains interactions with programmer.  Same as the tools that are described in previous two papers, the paper lists some statistics to show the efficiency and correctness of this tool.

The tool uses the concept of Lazy Initialization, but as mentioned in the paper that the initialization code the reentrant tool generates may alter program behavior, which will probably makes this tool unuable in complex code that will read mutable static field in other class. And that I think is pretty common in systems of a certain size.

Beautiful Architecture Ch 14.

I always find interesting topics in this book, and here comes what I am always waiting for: a chapter about a pure OO language, the Smalltalk! I found a lot of fun from Squeak in Smalltalk this Summer in another course taught by Professor Ralph Johnson. It's such a natual way in Smalltalk that objects interacting with each other through the messages. I think that gives this OO language a little bit favor of functional languages. The functions in Smalltalk are small yet powerful, the whole developing environment in Squeak is so convenient that I almost hate Visual Studio when I have to switch back to C# in my work.

One of the many interesting feature of Smalltalk is that it supporting "Duck typing", I recently found the support of this feature in C# too, the problem is C# is a strong typed language, and there is some debates in the internet about how to use the "Duck typing" in C#, or if it should be used.  Anyway, I appreciate the duck typing in Smalltalk that give me another option of polymorphism.

Since Smalltalk's open environment, it seems to me that Squeak is turning into a big lab, new concepts are implemented and tested there and later on adopted by other languages.  So even with so many cool concepts and architecture, it is not stable enough and not used much in industries.

I seem Smalltalk or Squeak as a system with beautiful architecture, I feel pitty that they are not known or used by many programmers. But I think that is one of the reason that they can always do something cool and never been done before.  I can't imagine any main stream architecture will have the opportunity of doing that.