Branch-and-Bound, Graphical Models, Structured Grids

Branch and bound pattern involves dividing the problem into smaller sub-problems, using the problem's definition to set constraints that must be met by sub-problems and eliminating the sub problems that do not satisfy the constraints. This is all done with the four steps: branching, evaluation, bounding and pruning. The theoretical aspects of the pattern are very well explained, but more code examples would have been helpful for understanding.

I did not understand exactly how the Graphical Models pattern solves the problem statement. In many problems we use measurements that can be performed to infer things and make conclusions. This is usually done with some kind of probability distribution as used in this pattern. But the solution is not clear to me. It is unfortunate that they did not include any examples to illustrate the solution.

I think the Structural Grids pattern is basically about using geometric decomposition to decompose the problem into smaller chunks and have processing elements operate on separate chunks in parallel. It looks like this is applicable to image processing, but I did not fully understand the example presented.

Shared Queue, Speculation, Digital Circuits

Shared Queue:

What experience have you had with shared queues, and what factors did you use to decide whether to use single vs. multiple queues?
Shared queues are widely used in the system I develop at work. One of the share queues is an “I/O completion status queue” shared by multiple processors that process completed I/O operation. We use a single queue, because back in the days there were only 2 processors. Now with the increase number of processors sharing the queue we are getting scalability issues because of excess contention.

An enqueue or dequeue seems like a very small operation. Why is there so much concern over contention to the queue? What factors cause this?
They are basic operations on a sequential program, when the queue is accessed concurrently appropriate synchronization must be implemented

Seeing as how the authors lay out quite a bit of code to support the variations of these patterns, they seem to mitigate their own concern as to the value of "simple protocols". Why would someone opt for the less efficient implementation, given that the concerns are already outlined, and sample code available?
It depends on the requirements of the application. If performance is not a major concern, I would go with a simple implementation even if the more efficient, but complicated code already exists. In my work environment we have performance numbers that we need to meet and we have to meet them even if it means writing an ugly code as long as it performs good.


Speculation:

Speculation seems like a pretty straightforward pattern, though potentially a quite powerful one. What factors would you consider to decide if speculation is an appropriate/beneficial pattern to apply?
I agree this seems like a very powerful pattern. It uses the idea of hardware speculation implemented in almost all modern processors. The factor to consider here is the cost of wrong speculations and the probability of making such wrong speculations. If the cost of wrong speculation is minimal compared to the gain of good speculation, then this pattern can produce great results.

Seeing as how you may not have data about the statistical distribution of inputs to expect before you build the program, and therefore perhaps not know the average cost of rollback, etc., is it prudent to implement the speculation pattern at the outset, or wait to evolve the application to include speculative optimizations down the road? What if the performance increase that speculation has the potential to generate is necessary to meet the minimum requirements of the specification? Is speculation still a viable pattern to apply, or would effort be better spent on other parallel optimizations with more certain outcome?
Speculation is a very powerful technique and I think that, for applications with predictable inputs, it is worth investigating if speculation can help meet the requirements.

Circuits:

Was this pattern what you expected from the name?

No, but after realizing that it was about bitwise operations, the name make more sense because digital circuits deal with bitwise operations.
I am a low level firmware programmer and I deal with bits operations on a regular basis. The concepts explained in the patterns are widely used by low level programmers: Large inputs are divided into smaller blocks and the bitwise operations are applied to the blocks independently to perform the calculation.

PRES: Probabilistic Replay with Execution Sketching on Multiprocessors

This is one of the most interesting papers I have read so far in this class. The problem of reproducing bugs is one that I face on a regular basis at work. The code that I write runs on a card (“small computer”) embedded in a big server and is responsible for driving I/O operations between the server and storage over a fiber channel network. We drive on average 100.000 I/O operations per second. Concurrency and timings bugs are common and reproducing them is painful and not always possible. We have been working for years to improve our ability to reproduce problems, but externals timings condition (On the server, network and storage) makes it even more challenging. The system that we currently have mainly consists of logging huge amount of data so that the error can reproduce. However, this represents a significant overhead and is only used under development and test. It is impossible to add so many traces in production code because customers cannot tolerate the performance impact.

The paper presents the idea of recording only partial information (sketches) during production and using an intelligent replayer during debugging. The sketches are used as a guideline to the replayer to reproduce the bug. The tool uses a different idea than most of the bug reproduction tools. The main goal here is to reproduce the bug by finding a combination that leads to the bug and not to reproduce the exact execution path and states that led to the bug. This is a great approach because different executions path and states can lead to the same bugs and this approach increases the changes of reproducing the bug with fewer replays.

Many reproductions are usually necessary for the programmer to find the root cause of complex bugs. So, one of the major advantages of this tool is that it guaranties reliably reproduction of the bug after the first successful reproduction.

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.

Pipeline, Geometric Decomposition, Data Parallelism

The three patterns describe how to achieve parallelism by dividing the data or dividing the operations that are performed on the data. I think all parallel patterns can be classified into the two categories: data parallel patterns and task parallel patterns.

The pipeline pattern is probably one of the most used patterns. Pipeline can be used in any system where a sequence of identical operations is processed in stages. I have used this pattern in a network adapter’s code to significantly reduce latency and increase throughput of sending and receiving packet over a fiber channel network.

The geometric decomposition pattern involves decomposing the data structure into chunks and decomposing the update operations on the data into tasks with each task managing a set of chunks. The biggest challenge in this pattern is to ensure that non local data required to perform an update operation is available before the update operation. So data exchange mechanism is critical for this pattern as it affects the potential parallelism.

The Data parallelism pattern advocates treating the problem as a single stream of operations applied to each element of a data structure. This is a similar idea as in the geometric decomposition, but here there are no details about the implementation of the pattern. I am not sure if the solution can be useful without a combine stage. The idea of applying instructions to each element of the data structure is good, but the results need to be combined to produce the final result.

Armstrong thesis chapter 5

The concept that I like the most in this chapter is the notion of having supervision hierarchies. The tree representation is a great way of distributing error recovery responsibilities to nodes, so that each node can monitor the errors in its child nodes. The error recovery mechanism described in this chapter is very robust and I think this approach will allow building very robust software systems. The difficulty that I see in real world application is that it is not always clear to the developers what an error is. The error recovery mechanism here requires the programmers to know exactly what an error is so that an error recovery procedure is initiated whenever that error occurs. This is not an easy task because most of time it only after a crash that the programmer becomes aware of some type of errors.

The author gives the notion of well-behaved functions(WBF) as a way of determining what an error is. WBF are functions that should not generate an exception unless an error is encountered. So this allows the programmer to interpret any exception generated by a WBF as an error. Amount the rules to follow when writing WBF, I found rule 2 interesting. The author advocates raising an exception when the specification is not clear about what to do. I think this is a better approach to determine and address specification errors instead of the programmer making assumptions about the design.

Task Parallelism, Recursive Splitting, Discrete Event

Task Parallelism

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?

The title gives a pretty good idea on what to expect. I knew the pattern will describe a solution that consists of dividing a problem into a series of task and solving then concurrently. I did not directly think about defining tasks with data distribution as a primary concern.

2.- In what category falls this pattern?

I am not sure how to classify this pattern. In order to produce the tasks, this pattern can use both the structural pattern and/or computational patterns that describe the problem.

3.- What platform do you have more experience programming parallel applications on? And what Task Management Mechanism? (Jobs over Networks, OS Processes, SW Task Queue, HW Task Queue)

I am working on a prototype to convert a sequential I/O firmware to a parallel application on an embedded I/O adapter consisting of 2 powerPC cores. I have not done much yet that I can share. I am still in the process of getting embedded Linux to boot on the platform before I start to change the current application.

5.- Do you think that this patterns requires you to learn more about hardware platforms in order to make a correct implementation?

The pattern requires the user to have an understanding of both the application’s concurrency characteristics and the hardware platform characteristics in order to arrive at the solution. I think this is good idea because many systems do not perform at their full potential because the programmers only focus on understanding one side. I worked in a system where knowing the cache replacement algorithm of the CPU allowed us to make changes in the application that led to a urge performance improvement. In parallel programming I believe that a good solution is not possible without a good understanding the parallel hardware characteristics.

Recursive Splitting

This pattern describes a solution to problems that can be recursively decomposed in a series of independent tasks. The recursive splitting problems can be solved in parallel hardware by having nodes work concurrently on different recursively generated task. The major issue to be addressed while applying this pattern is to come up with a choice of splitting that make efficient use of the hardware resources to produce the solution. The author mentions the tradeoff between getting greater efficiency by selecting larger base cases, versus getting greater opportunity for concurrency by selecting small base cases. The author provides good explanations on how to implement the solution and states the cases where the solution is not applicable. The premise for the pattern to work is to recursively generate more than one task per tasks. So problem like selection sort where only one task is recursively generated are not applicable.

Discrete Event:

This pattern is similar to the Event-based except that here, more consideration is given to ordering constraint and a solution is given that provides a simple way of dealing with the constraints. I agree with the author that often the best approach to deal with deadlocks is to use timeouts. I work on a real time system where we use timeouts to make the system predictable. It is easier to implement and works very good in our environment.

Armstrong thesis chapter 4

How did Erlang's view of the world help with implementing an HTTP server?

In Erlang everything is a process and processes can only interact by exchanging messages. So to implement a HTTP server, the main loop of the server code create a new process for each connection, then listen for client’s requests and respond.

The author describes an interesting concept of handling errors, which is based on the hardware duplication approach of handling failures. In order to provide high reliability, many systems have redundant hardware so that if one fails the other can recover it and keep the system running. This idea is used and implemented in Erlang. The processes are linked in the event that one fails the other is notified of the failure with an explanation so that appropriate actions can be taken. The failing process sends a message to the other process before it terminate. If there is a hardware failure on the machine on which one process runs, the hardware failure is converted to look like a software failure. This allows a uniform error recovery mechanism to be used for both hardware and software failures.

Another interesting concept is the notion of completely separate error-handling code from the code solving the problem and have them run in different threads of executions. The main advantage on this approach is that the code can be developed in a single node system and ported to a distributed environment with only minor code changes.

How important is it to use intentional programming when it comes to maintenance? (The author gave the example of history of theDictionary API)

I think this is the central idea behind writing code that is easy to maintain. The function’s name and variable should be meaningful, descriptive and clearly express the function’s purpose.

Dense Linear Algebra, Graph Algorithms, Monte Carlo

Do you know these patterns, or are they new to you? If they are new,could you understand them? What questions did you have? What couldthe authors have done (more pictures, more examples, more definitions)to help you get it?

I know and have used most of the ideas presented, but I did not know them as patterns. Considering linear algebra, graph algorithm and Monte Carlo methosd as patterns seem strange to me. These are three huge areas of studies and there are generally complete course (e.g. graph theory) to study these problems. There are many different graph algorithms and the type of problems that can be modeled to them is huge. Maybe a pattern language for graph algorithm is more appropriate.

I have taken classes in linear algebra and algorithm where we discussed graph algorithms and Monte Carlos methods. So it was straightforward read for me. Overall I think they did a great job in describing the patterns. For the linear algebra pattern, the figures to illustrate the matrix multiplication and memory hierarchy are helpful in understanding various approaches when starting from scratch. Graph algorithm and Monte Carlo methods include enough details to understand.

How are computational patterns different from structural patterns? Is there a clear distinction, or a fuzzy one?

The only thing that I can see is that structural patterns define the structure(the steps) to use to solve a problem (e.g. a software design problem) and computational patterns actually solve the computational problems.

Armstrong thesis chapter 2

This chapter makes some simple and very intuitive points in defining architecture. An architecture is basically composed on 4 parts: A problem domain which state the problem that the architecture is designed to solve, a philosophy which is the ideas behind the architecture being developed, a set of construction guidelines and predefined components that can be use to avoid designing from scratch
The author uses these 4 steps in developing architecture for fault tolerant systems. Fault tolerant systems as defined in the thesis are software systems that behave reasonably in case of errors. They have a hierarchical structure consisting of multiple levels. The complexity of tasks performed at each level increases with the levels. So the top level performs the most complex task. To achieve fault tolerance the author emphasizes strong encapsulation to prevent errors in one part of the system from affecting other parts. Error isolation is the key here and is the main characteristics of COPL . The processes running on the machine must be isolated so that an error in one process does not affect another process.
Another point That I found interesting is the notion of “fast fail” where a process stops in case of an error. The idea is that the process should either work properly or should signal the failure and stop. I think this is a good idea and can be implemented for some systems. However it is kind of counterintuitive to the notion of fault tolerance. It seems more logical that such systems should try to recover from failure especially given the fact that failures are part of most software systems.

Event based / Map reduce

Map reduce

Map reduce is a pattern based on the map and reduce functions usually found in functional languages. The idea is very simple. The map function is applied in parallel to each object in a set, then the results are collected and combined by the reduce function to get the output. This pattern is great for applicable problems and another advantage come from the fact that when incorporated into a framework, the programmer only need to provide the map and reduce functions. One of the aspects of this pattern that we are currently looking at in one of our cloud computing project is to incorporate a reschedule function. Basically when the operations are been carried out independently on different servers, if a map or a reduce fails we want to reschedule the failed operation without having to reschedule all the other tasks.

Event based

This pattern is similar to the observer pattern. The system is composed of components that can post events (announcers) or listen to events (listeners) and a medium which is the central piece of the solution acting as the liaison between the listeners and announcers. The medium dispatches the received events to affected listeners and allows listener to register and listen to events of their choice. I think the main difference with the observer pattern is the presence of the medium. In the observer pattern the subject maintains a list of its observers and directly notifies them of state changes without passing through an intermediate medium.

Pipes & Filters,Layered systems, iterative refinement

How do the two repeats differ from the first versions that you read?
I think the difference is that they are presented here to show how to exploit task parallelism.

Did they miss anything?
I am not sure if there is a reason why they did not include any picture to illustrate the concepts. It makes things simpler to follow.

Did they include something that the first versions didn't?
Pictures would have made their points easy to follow, but they did do a good job at describing the patterns in steps. The analogy
with the task graph for pipes and filters was very good.

Did you learn anything from them?
I did not learn anything new from the first 2 patterns as I already knew them. The third pattern was confusing to me.

Doyou have any advice to the authors of these patterns?
They should includes some pictures and/or graphs to facilitate learning

For the new pattern, have you seen programs that used it? If so, doyou have a good story to tell about it? What was hardest tounderstand about this pattern?
I probably used the idea behind this pattern, but the description is not very clear to me . It is like some kind of loop unrolling where each iteration
is considered independently.

Rereading the classics: BA ch 14

This chapter is more like a summary of the beautiful architecture book. It has been an enjoyable and rewarding experience reading this book. I have learned so much from some of the greatest architectures and thought a great deal about the architectures that were not so great. One the lesson that I learned is that there is no such thing as the perfect architecture for a system. It is important to look at what exist and how people have solved similar problems before embarking on a design. Patterns are great and should be applied where applicable. This book emphasizes the importance of good architecture and as software builders we need to know that a good design is vital to the success of the product at all stages (development and support)

This chapter talks about Smalltalk, which is an interesting programming language. I did not learn much new thing in this chapter because I used Smalltalk on CS598. An interesting aspect of Smalltalk is that it is a pure object oriented language, where everything is an object and objects interact with each other only through messages. Another aspect is that the programmer must work in the smalltalk environment with the set of class libraries provided. This makes smalltalk less flexible and it is one of the reasons why it did not become very popular even if many of the concepts of smalltalk were adopted by other languages.
The conclusion of this chapter, which also like a conclusion to the book remind us again of our task as programmers. Just as programming, architecture is a matter of practice. We need to build systems that are not only beautiful, but that work. The very last sentence of the book states that very clearly: “Architecture is a chaotic adventure because beautiful architecture alone is not enough; not only beauty, but also usefulness, is the law for architecture and programming alike”

Refactoring for Reentrancy

This paper describes a concept that I have been hearing a lot lately at work as we are thinking about porting a sequential firmware we have to a new multicore platform that is been developed by our hardware group. A program is reentrant if distinct executions of the program on distinct inputs cannot affect each other,whether run sequentially or concurrently. This has the great advantage that reentrant programs can be ported to multicore machine without the need of concurrency control or the need of running each program instance on a separate virtual machine.
The authors argue that manually converting legacy single threaded programs to reentrant programs is a perilous and labor-intensive task because these programs use global states in a non reentrant way. So to help the programmer transform the code to a reentrant program, the authors proposed and developped a java automated refactoring tool that replaces global mutable state with thread-local state. This allows the execution thread to get a separate copy of each global variable. When the tool introduces the thread-local state, the programmer only needs to manually modify the code to use a new thread for each execution instance of the program to make the program reentrant.

Clearly this is a great tool for java and for those who use eclipse, but I think a generic tool performing this task will be great. We do not use java and eclipse for our firmware development, but I can see how helpful it will be to have such a tool.

Software architecture: OO versus functional BA ch 13

In this chapter, the author compares the functional programming style with the object oriented style. It is probably not a surprise to any one that he comes to the conclusion that OO style is the better approach because it provides higher level abstraction and more extensible and reusable.
OO style is the most widely used programming model. Thinking in terms of objects allows for greater abstraction in the design and OO techniques like inheritance and polymorphism are powerful for creating extensible and reusable code. This makes object-Oriented environment more manageable especially as the system grows towards the enterprise level.

Functional model is good when the program does not need to remember the states and when only the final result matters. It is great for mathematics as the program can be written almost exactly as the mathematic expression. I used ML in a compiler class and it was quite impressive to see how one line of ML program can compute very complex matrix operations. The corresponding function to achieve the same task in a language like java would take many lines of code.

I think functional languages are very hard to learn for people who started with object oriented programming style. OO style is very similar to the way people think and it is very intuitive compared to the functional style.

ReLooper: Refactoring for Loop Parallelism

As the previous paper on Concurrencer, this paper describes a refactoring technique aimed at converting sequential code to parallel programs. The target for Relooper is transforming an array to a ParallelArray. A ParallelArray is a special array in java that supports parallel operations. The authors make the point that many programmers prefer to use refactoring to incrementally covert their code from sequential to parallel programs. Compared to a complete re-designed for parallelism, the refactoring approach is considered safer and allow to maintain a working version of the code while the refactorings are being performed.

ReLooper efficiently analyses whether the loops can be parallelized and replace them with equivalent parallel operations. I think the tool is helpful, but it will be good to see how all these tools designed to help programmers parallelize their programs work together. It seems like there are many tools out there each targeting a particular type of refactoring for parallelism. I am not sure if enough tests have been done to proof the correctness of these tools. I do like the fact that ReLooper does a static analysis on the code before it performs the transformations and warn the user about conflicting memory accesses and I/O operations.

When the bazaar sets out to build cathedrals BA ch 12

Author mentioned some key technical decisions like dropping the idea if it doesn’t work in reasonable time frame; maintain the core functionality working all the time while the changes have been made to the project, etc… What are some other ideas that you get in mind while you are reading these technical decisions or some other ideas that we may have seen in cathedral type project building (in our work places)?

In software development there are always difficult decisions that have to be made with various consequences. As described in this chapter larger scale software projects are not only technically challenging, but also involve other issues. Open sources project need to overcome technical, social and structural issues, while commercial software development teams usually need to deal with aggressive schedules, reduced costs.
The decision of completely redesign KDE from KDE3 to KDE4 was a courageous and risky decision. I believe such a decision was only possible because of the open source status the project. Given the large number of contributors they were able to maintain KDE3 and quickly redesign the system. The decision was needed to make KDE platform independent and ended up being a successful decision as it made the platform more stable and brought more users.
From my experience it is not easy to take a redesign decision in commercial environment. I have worked on couple of project that clearly needed a complete re-design. In one case, the system was very messy and very hard to maintain. Many developers argued to the management that a redesign was necessary and will pay off in the long run, but senior management completely opposed the idea because it was critical to bring new functionality to the market and the redesign was just too much of a risk to take. After reading the Evolution of Akonadi, KDEPIM community depended on architecture meetings / conference secessions to discuss the key architecture items and author mentioned about most of the high level / key items are agreed but implementation of individual items still faced some heated discussions. Have you had any similar experience where you agreed to key concept but varied how it needs to be implemented either in bazaar / cathedral model implementation of the project?

This happened on almost all the projects I have worked on in my current position. We develop firmware for a system where reliability and performance are critical. We regularly have heated discussions in low level designs and code reviews about implementations and code efficiency. Currently we are developing code of conducts and code guidelines so that we can refer to them for conflict resolution in the future. I like the section where the authors talks about how some of decisions are made in KDE. They talked about: “those who do the work decide”. I argue that some of us working in commercial companies can only dream of such an environment. As people who do the work we are usually not even in the room when decisions are made. Senior executives make the decisions usually based on market conditions, set the date the product needs to be ready and push the decision down to development teams for implementation.

Refactoring sequential Java code for concurrency via concurrent libraries

I truly enjoyed reading this paper because it is simple, well organized and easy to follow. The authors describe a rafactoring tool that enables developers to convert sequential java code to parallel code using the java.util.concurrent(j.u.c) package. The j.u.c package provides utility classes for concurrent programming. To use the tool, the programmer selects the target piece of code, and applies the appropriate refactoring. This allows the program to be incrementally transformed to a parallel program using a series of refactorings under the control of the programmer. While not perfect yet, I think this tool has a great advantage over manual refactoring. The paper presents pretty convincing details how the tool achieved better results compared to manual refactorings done on the same projects.
The tool is not completely automated as the programmer needs to select a piece of code and target it with the rafactorings. This still leave room for omission. A fully automated tool will probably find more areas suited for parallelism than a programmer. So, logical extensions opportunities for the Concurrencer include fully automation and the support for additional refactorings.

Parallel refactoring tools are great, but for some cases, it is probably more difficult to retrofit concurrency into a sequential program than to re-design for parallelism. If a team has the time and the resources I believe they should redesign. It will be easier and more parallelism will be achieved that way instead of being constrained by a sequential design that was done without taking into account parallelism.

A Java Fork/Join Framework

This paper describes the design and implementation of Fork/join framework that support a parallel solution to the classical divide and conquer style problems. Those problems can be divided into subtasks that are solved in parallel and the subtask's results combined at the end to produce the final result. I believe this is the most basic and intuitive type of parallel programming. The authors claim that the framework is efficient, support scalable parallel processing and provide a simple API to the programmer. However I think that little details on the performance analysis and scalability test was done only on a single JVM. So It is hard to tell how well this system really perform and how scalable it is. I think this is a weakness for this paper because such a work should have focused on showing how this framework handles more efficiently Fork/join applications compared to traditional thread frameworks who have more overhead than required by Fork/join.

GNU/EMACS: Creeping featurism is a strength BA ch 11

I am a fan of Emacs and I have been using it for years, so a lot of the features described in this chapter were not a surprise to me. Emacs is very powerful. In my team we always juke around: Old folks saying “you kids with Emacs” while the younger team members say “you old folks with VI”. I am not sure if other people have seen the same trend.

I will comment on the questions:

* Is it possible for a system like Emacs to be created in a non-open source way?
I think that everything is possible if the money is invested, but it will probably take a huge investment to do it. Emacs has benefited a lot from the contribution of the community. Developing such an extensible and customizable editor is not an easy task * What are some of the disadvantages of a system like Emacs? I don’t see any for people who take the time to learn and discover the features. It can take a while to assimilate all the important features. Like any free software, there is always the risk of not having support.

* What architecture decisions have allowed Emacs to grow like it has?
The decision of making it highly extensible and customizable.

* When is avoiding complexity a good/bad argument for implementation? It is good to avoid complexity if the added complexity does not add any value necessary for the project. For example if performance is critical to a project, then there will be some complexity added to get the performance out of the system.

* Do you think Firefox will replace Emacs?
I do not see how that is possible. They are 2 different things

Our Pattern Language

This paper describes a pattern language for parallel programming. The authors first make the point that the software industry must change from a sequential to a parallel approach in order to accommodate the increasing shift to parallel processors. This change does not affect all the programmers equally. Low level programmers, who works at the hardware- software interface needs to master parallel programming, while application programmers only need to be weakly aware of it. I found surprising that they mentioned that application programmers may have little background in computer science, specially knowing that a vast majority of computer science graduate work as application programmer.

The benefits of grouping the patterns into a language is that it gives parallel software architects a conceptual framework that help them organize their understanding of the problem and guide them from the beginning of a design to its realization on a real hardware.
As mentioned in the paper I think some of the computational patterns may even be whole pattern languages of their own. I take the example of Graph algorithms. Graph theory is a large area of computer science and there are many different problems that can be solved using some class of graph algorithms. I do not think that they can all be described in one pattern. There need to be pattern for each of the known graph problem, for which there is a solution that expert takes for granted.

I will really be interested in the Data Locality pattern. I took a class in computer architecture and realized our difficult it is to design cache coherence protocol in multicore systems. I think this is one of the major tasks that low level software for multi-processor platforms must handle. Depending on the underlying cache coherence protocol, the low level software must be implemented appropriately to avoid trashing the caches. In single processor systems, it is very easy to figure out where a line of memory is. It is either in memory, in L1 or L2 cache for systems with 2 levels of caches. I a system with multiple processors, the line can be in any processor's L1/L2 cache or in memory.

Metacircular virtual machines: Jikes BA ch 10

This paper presents another example of a system that emphasizes the advantages of using a single language for runtime and implementation of the system. Jikes is a VM developed completely in java to run java applications. The author describes the component of the system after first presenting the concept of self-hosting, which is writing a programming language in its own language.

The author argues that using java to write the components had many advantages. I completely agree that using Java’s collection simplifies the development by allowing the components to focus on their roles. It is a great advantage of Java compared to languages likes C where the programmer needs to take care of managing the underlying data structure and memory.

Jikes has its own threading model because there was a lack of threading support in operating system when it was developed. To the question of knowing if it was a good choice? I think they did not have any choice. There was no support for threading so they had to develop one. This has advantage because it allowed them to adapt the threading model to the need of the system allowing them to run many threads. The only downside as mentioned in the chapter is that it can have some undesirable performance problems because the OS does not know about the JVM managing threads.

The Adaptive Object Model Architectural Style

This Paper presents Adaptive Object-model (AOM), which are considered as a more flexible alternative to the conventional object-oriented design (OOD). Some nice examples along with advantages and disadvantages of AOM are presented. In AOM system, the object model is stored in a database and the system interprets it. AOM systems do not model the system based on the classes and their attributes and methods, but represent them as metadata, which are interpreted and translated to dictate the system’s behavior. So changing the application does not require changing the code, but the metadata. I think this is a very good feature compared to OOD systems where changing an application require changing the code and releasing a new version of the application.

The system is adaptable to changes, because any changes in the metadata are immediately interpreted and reflected in the running application.
This architectural style is very interesting and great for system where flexibility and dynamic runtime configuration are important. I never work on a large scale system requiring these characteristics, but I did a class project a couple of years ago, where a GUI was developed to read, interpret and display the products and the prices stored in a database. I am not sure if that was an AOM system, but it was very cool to see the system automatically changed whenever there was a change in the database.

I understand that Architects of AOM are very proud of their system. Who will not be proud to architect a system that adapt to modifications without requiring code changes? I think the AOM architectural style has a very interesting concept and provide a great solution. The author mentions that developers who have to use and maintain these systems usually find them hard to understand and do not think they are that great. Maybe this is an example where the architectural concept is great, but the implementation is not as great. I don’t have experience with these systems and I do not understand why this is the case. Maybe some folks with experience using AOM system can tell us why they are hard to maintain.

Among the examples provided, I especially like the User-Defined Product framework (UDP). It shows how an AOM architectural style can be used to allow users to construct new kind of components or various complex business objects from existing components without any code change.

JPC: an x86 PC emulator in pure Java BA ch 9

This chapter describes the architecture of an x86 pc emulator written in Java. The authors first give the motivation of developing the emulator despite the existence of emulators like QEMU and Bochs. They argued that those emulators have some security holes and need to be recompiled in order to run on a new host system. They also described why they choose an emulator instead of a VM. VMs need some degree of hardware support while Emulators are written completely in software and do not need any specific support from the underlying hardware. The emulator runs just like a normal application running on the computer and is therefore the most stable and secure way of creating virtual machines. Given these facts the authors decided to build as emulator in the JVM, which provides guaranteed security and performs good enough to stay practical.

After making the case for developing the JPC the authors focused on the most challenging aspect of emulation, which is dealing with performance. Applications running on the emulated machine incur significant software emulation overhead at runtime. So it was critical for JPC to deal and reduce the overhead of emulation. The authors took a very discipline approach and considered a series of performance tips in their architecture. I believe their approach to incorporating optimizations wherever it had a positive impact was very successful and is the right approach. Being able to boot a virtual DOS and run games within a secure JVM running on any machine is quite impressive.

I like the steps that the followed and presented at the end of the chapter as being the steps to a beautiful architecture. They focused on limited end-to-end prototyping of the complete system rather than prototyping components of the final product. This had the advantage that it allowed more flexibility and allowed to prove the concept before engaging in large scale work. This approach is unfortunately not always possible in commercial settings, where people do not have the luxury of getting paid for writing throwaway code. For an academic setting or for research teams at companies this is definitely a great recipe for creating beautiful architectures.

Guardian: a fault-tolerant operating system BA ch 8

Guardian is an operating system that was designed to work with the hardware to provide fault tolerance with minimum overhead. The author first describes the main idea behind building fault tolerant systems. The design was centered on the idea of avoiding a single point of failure. Failures should be contained and not cause the entire system to fail. This was achieved by using redundant components to provide continuous operation in case of a component failure. The system has at least 2 CPUs, 2 busses, as well as duplicated I/O and storage components. The downside of this approach as acknowledged by the author is the cost. Duplicating hardware components will almost double the cost of the system.

The operating system was designed to work with the duplicated hardware components. The OS manages the system and transfers the load if it detects a component’s failure. For example if a CPU fails, it is stopped and the load is transferred to the other CPU without system downtime. Depending on the type of failure, the OS either recover from it or the failing component is replaced. The system offered some cool features like the “nonstop” function, which is the ability to remove and replace components without turning off the system. This is very desirable and important feature especially in server environments, where reliability and availability are critical. So, the Tandem platform offered similar features as some of the most powerful and expensive servers in the world like IBM mainframes. If we take that into account, we can say that the high cost of the Tandem system shouldn’t have been a major issue if it offered features that conventional systems could not.
One aspect of their solution that I don’t like is check-pointing. It uses CPU cycles and the author mentioned that it is left to the programmer to decide when and how much data to checkpoint. I am not sure if that is easily feasible. It requires the programmer to have an in-depth knowledge of the system in order to take appropriate checkpoints.

BIG BALL OF MUD

This paper is definitely the most interesting of the papers I have read so far in this class. All the points made in the paper are very applicable to many of the projects I worked on. big ball of mud systems are unstructured, with no clear defined architecture style. It typically has many code smells like, duplicated code, spaghetti code. These systems evolve over time with no formal architecture, with various people working on it and making fixes just to keep the system running. From my experience there many reasons that impact the quality of the software: Ever changing requirements, cost and aggressive schedules are usual characteristics of many software projects. People do not have the time and the money to invest on good architectures and therefore big ball of mud are created. It is very interesting that the authors document this kind of systems. They explain why this kind of architecture is so popular. Among the forces behind theses systems are the cost of architecture and the skills of programmers. The authors explain in the patterns how the programmer maintaining the messy code should learn to understand how it evolved, what it does, and how to improve it.
I like this quote:
“Overgrown, tangled, haphazard spaghetti code is hard to comprehend, repair, or extend, and tends to grow even worse if it is not somehow brought under control”
This is such an important statement. If it is hard to understand, restructure and make changes to a system, it is important to stop the system from getting even worse. This should be done by correctly planning and structuring any new addition to the system so that the mess can be restricted to a fixed area

I have worked on a legacy system that was first developed about 30 years ago. Most of the senior members on the project started with horizontal microcode, then change the project over the years to use C and C++. The code is messy because of the thousands of patches and new functionalities that have been added over the years to keep the system running and provide new value to customers. Working in that environment I realize how many factors influence the quality of a system and how important it is to try to understand theses system as described in this paper.

Xen and the beauty of virtualization BA ch 7

This chapter presents one of the hottest topics in information technology. Virtualization is increasingly becoming critical in today’s infrastructure because of its economic benefits and the features like isolation and security. Xen is an open source virtual machine monitor that allows multiples guess operating system to concurrently run on the same computer hardware under the supervision of the hypervisor.
One of the major challenge in architecting virtual machine monitors is to figure out how to executive privileged instructions in guess Operating system. This is because the hypervisor runs in the most privileged mode and the guess Os in lower privileged levels. In some systems, executing an instruction at an inappropriate privileged level causes an exception that the hypervisor can trap. However, this is not always possible because some system do not generate the exception.
Before Xen this issue was addressed by rewriting the OS code at runtime and replacing privileged instructions by direct calls to the hypervisor. The advantage of that approach is that The guess OS can run unmodified because emulation makes the virtual machine looks exactly the same as the physical hardware.
Xen introduced a new idea called paravirtualization, which presents an interface to the virtual machine that is not identical to the physical machine. The features of a machine that are hard to virtualize are replaced with hooks that allow the guess and the Host OS to communicate in executing the instruction. Paravirtualization remove the overhead of runtime code rewriting and emulation and can also allow some instruction to be executed directly by the guess OS. The only problem is that Guess OS need to be modified to support the paravirtualized architecture.

Xen’s architects designed the hypervisor to be a simple small layer between the hardware and the guess Operating systems, responsible for managing the hardware and scheduling Guess’s tasks and ensuring that each guess get a fair share of the hardware time. So to reduce complexity and the risk of damaging the whole system, most of the management functions are not done in the hypervisor, but at domain 0.

With the increasing use and importance of virtualization, most processor manufacturers are now providing virtualization support in their platform to allow unmodified guess operating systems to run on the hypervisor. The hardware is changed to notify the hypervisor each time a privileged instruction is executed. Latest version of Xen added support for these hardware virtual machines. The author makes the point that Xen was able to quickly provide this support because of its open source status. Developers from Intel and AMD helped write the low level code needed to supports the new CPU and Xen also used other open source projects like QEMU for device emulation. This is an example of some of the advantages of open source.

Layered Architectures

The Layered architectural pattern describes the widely used principle of decomposing a complex task into a number of subtasks. Almost any development team and organization where I have worked claimed to use this principle in their developments. Most classes or books on software engineering emphasize the notion of decomposing systems into layers and defining interfaces between them. So, when I saw the name “layered architecture” my first impression was that it is a basic and fundamental concept. When I started reading the pattern I found very interesting that the authors mentioned at the beginning that most systems that people claim to use layered architectures are either a collection of multiples architectural styles or just some collection of cooperating components without clear boundaries. In this pattern the author attempts to give a more rigorous definition and properties of corrects layered architectures.

Some of the important ideas to keep in mind when designing a layered architecture includes: localizing changes to one part of the system, cohesion within components and loose coupling between unrelated components, avoid crossing too many components, reusable parts and parts that can be exchanged by different implementations without affecting other layers. The multiple obvious advantages of this approach are presented by the authors. I liked that they also gave some disadvantage of the solution. I believe layered architectures are great to tackle complexity in large complex system, but they add unnecessary complexity to simple systems. For example there is a lot of overhead if the lower layers need to perform expensive tasks not needed by the upper layers. Even though this is considered good software engineering practices, it should be determined just as with any other pattern if layered architecture is a good solution for the problem before using it.

Data Grows Up (Facebook) BA ch 6

This chapter has a significant number of details about the Facebook system. It is more like a low level design to me. I got lost many times trying to understand all the details. The author explains the design decisions made and the rational behind them. Facebook was initially conceived as a social website where a user request causes data to be fetched, transformed and displayed. The platform was then extended to include other web services, a query language and a data-driven markup language (FBML) that allows outside applications to incorporate facebook’s data into their system. This feature is very helpful to other applications because it allows them to use valuable information already on facebook.
To guarantee user’s privacy, not all data are available through the data services. External applications do not have access to some data that facebook make available to the user.
I found very interesting the way the data-driven markup language is interpreted by facebook. Basically the external applications are some sort of data services providing the content to be displayed. Facebook interprets the FBML and displays the content provided by the application without violating the privacy of the user.

This chapter illustrates how an architecture can evolve from a simple social web page to a powerful platform with various other features. Each new change caused architects to change the system using even more powerful design decisions to add the features while keeping the fundamental requirements of data privacy and site experience integrity. So scalability is very critical to this architecture. Given the large number of people using facebook today, I am pretty sure that changes are ongoing and will continue on this architecture to provides new features

Pipes and Filters

The Pipes and filters pattern is very popular and widely used. It is almost a common sense idea to divide a large processing task into small sequences of independent steps and have some kind of connection between them. This is exactly what this pattern does: the processing steps are encapsulated into filters components and they are connected by pipes.
I have used this architectural pattern in an I/O project at work. The work involved moving data from a server’s memory to storage devices on a fiber channel network under the control of an adapter firmware. The task consisted of fetching the I/O request from the server’s memory, interpreting the request, fetching the data, computing and verifying a checksum on the data, then setting up DMA engines to send the data over the fibre channel network. We used the pattern to divide the task into several sequential processing steps. The work of each filter was isolated from the other components and this was a major advantage this year when we decided to use multiple threads on the system.

Resource-oriented architectures: BA ch 5

The chapter begins with an embarrassing fact that many organizations face today. It is very common for employees and internal users to search for their own information using the web even when there are internal search engines. Maybe it is just because we are so dependent on web that we are very quick on turning to it when we are looking for information. The sad true is that, most of the times this is not because of the Google’s dependency, but it just because it is easier to find information on the web than it is to find information internally. This is primarily because organizations focus more on the software and services and underemphasize the data. So the author makes the point that organization should focus more on finding ways to manage and reuse their data.

The paper defines resource-oriented architecture and all its advantages. ROA use logical names for named resources. This approach does not leak implementation details and provide a clear separation of the resources from the URL. The logical request is sent to a resource-oriented engine, which interprets it and turned it into a physical representation of the resource. That way, resources can be migrated and backend implementation changed without affecting the clients. Among other important properties of the ROA design choice are scalability, caching, and a focus on information.

I think there is a big advantage in putting data at the forefront. Making data available and easily accessible allows the backend system to cache results and make changes without affecting the clients. However, I am not sure how practical this can be in the real world. Many systems are based on the technologies described in this chapter as conventional web services or software centric architectures. It is will take a significant effort and will be very disruptive to change existing designs to ROA. Maybe ROA can be attractive for large organizations with massive amount of data that should be organized and decouple from clients to make them easily manageable and accessible internally.

Excerpts from Christopher Alexander One Two Three

The author starts in chapter one by making many analogies to explain that complex things in the world do not just happen. In other words, we cannot suddenly give birth to something gigantic without explanations. Those things can only be generated by a process. After that, the authors talks about buildings and the process of their construction.
He describes in a very interesting and simple way how the process of building is just a collection of patterns that give builders the ability to combine them to create an infinite variety of buildings.

We can clearly see how this applies to software architecture. In architecting a system, the architect uses patterns, which are things that repeat. That is he does not invent or suddenly give birth to the architecture of the system, but uses known best practices and solutions to similar problems as references while building the new architecture. Those known best practices and solutions can be combined and arranged into different ways to form various new architectures. So the architect makes the appropriate use of the patterns to produce the new architecture.

The notion of having a pattern language is also very interesting because we can think of the collection of patterns as a set of words in a language. To support that the author makes the analogy that ordinary languages give us the power to create an infinite variety of sentences. So if we think in theme of software architecture we can say that the pattern language gives architects the power to create a variety of architectures.

ArchJava

This paper attempts to solve a very relevant and important problem. It is critical to correctly architect a system, but even more critical to implement a system that complies with its architecture. What is the point of making a great architecture if the implementation does not follow it? I cannot count how many times I discussed with my colleagues about violations of architecture that are a direct consequence of the separation of the architecture from the implementation. Even when inconsistencies are found between the implementation and the architecture, both are updated separately leaving room for inconsistencies. ArchJava presents a very interesting idea that unifies implementation and the architecture to ensure that the implementation conforms to the architecture.

I really like the section about ensuring communication integrity among the components. I think that is one of the most common violation. It is very easy to add calls to methods from different components without making sure it is allowed by the architecture. It is a great feature to be able to detect any such communication integrity violation and decide if the architecture should be updated or the dependency removed. The author pointed out the limitation in detecting the communication violation because they considered only methods calls. I believe it is not a big deal for many java applications because method calls are the most common inter-components communication mechanisms.

Beautiful Architecture Ch 4: Making Memories

This chapter describes the architecture of a photo processing workflow system. The typical scenario of a customer's order is as followed: The photographer takes pictures using a camera, loads them to a studio workstation, selects the good ones and enhanced them. After the enhancements the order is burned into a DVD, which is sent to the printing facility for further processing and printing. The printed pictures are sent back to the studio for customer pickup.

During the architecture they considered many aspects that I can now considered common sense after reading a few chapters in this book. For example, they divided the system into components and defined clear interfaces between them, kept module dependencies minimal, and built a very scalable and flexible system.

I specially liked the UI model separation from the domain model. Typically when the IU is closely tight to the domain model, it is difficult to change the domain and do unit testing. The author addressed this problem by separating both models using the facade design patterns to simplify their communication. The façade defined a higher level interface that made the domain model easier to use by the IU model. The IU only needs to ask the façade for service that it would otherwise need to traverse the graph of domain objects to figure out. This was a great use of a design pattern.

Beautiful Architecture Chapter 3: Architecting for Scale

We are in an era of computing where optimization to increase performance on a single processor his slowly hitting the wall. We started to see new processing platforms with many processor cores tightly integrated for parallel processing. The problem is that very few programmers know how to program these multicore systems. people are predicting that parallel programming skills are very important and will increasingly become important and valuable. My company started investing in equipping programmers with the right tools and concepts of parallel programming.
Is everybody wrong? is there a way of hiding concurrency from the programmer? At least that is the first impression that I got from reading the paper. Their goal was to hide the complexity of programming multiple threads and cores from the game developers, allowing them to see the system as a single threaded machine. This made me very excited about the paper until I read the section about performance and latency.
For their approach of hiding concurrency from the developer to work, they do not keep significant data in main memory. One of the major design decision here is to store the data persistently. This is will have a major impact on the response time and performance of the system.
So I see a couple of contradictions in the paper and I am not sure if I will classify it as a "beautiful architecture"
If latency is of big concern for games as mentioned in the paper, why will the author architect a system knowing that it will suffers from latency problems?
Parallelism should be a way of improving performance. If the goal is to make it simple for the developer, we should have significant performance benchmarks to make sure the solution does not take away the advantage of parallelism.

4 + 1 Views

I found this paper very interesting and simple to read and follow. The author presents a simple, but powerful way of dealing with complexity when architecting large systems. The main goal of many architectures is to use a single architectural style to provide a single view of the system. We all know how challenging and confusing it can be to look at a convoluted diagram. The author proposes to separate the architecture of the system into four essential views: logical, process, development, and physical. The four views work together and their collaboration is illustrated by the use of important scenarios.

I believe that “4+1” is a beautiful architecture for software architectures. What I mean is that it is a simple method to build and document powerful systems from an architectural perspective. It is very flexible and can be adapted to almost any project. The various views assure that all aspects of the system are taken into consideration and documented. This is usually difficult to achieve in single view architecture.

I am not very sure about the relation between the logical and the development views. The author says that they are very close, but address different concerns. I am thinking that the logical view described here is only important from the end-user perspective to see that the behavioral requirements are met. From a developer perspective, I think the development view deals with dividing the system in major subsystem, with each subsystem having a logical view (subsystem’s cohesion) and an interface for external subsystems (coupling)

A Tale of Two Systems - BA Chapter 2

This paper describes the environment where many new recruits work in when they join a new organization. For the folks still fulltime students, unless you are very lucky, you must be prepared to deal with a messy metropolis once you start your career. Most of the jobs out there today are to replace baby boomers that are retiring, and work on legacy systems that are usually messy metropolis. So refactoring and reverse engineering skills are very critical and hot in the market place.

Many legacy systems started as a small project, but have grown over the years into messy systems because of the constant need of delivery new functionalities under aggressive schedule. I agree with the author that it was very brave for the organization to take the step of rewriting the application. For some critical systems a very thorough analysis is needed to asset the risk and the cost of rewriting the system. From my experience rewriting messy systems has never worked because they are deployed on thousand of machines around the world and the ability to understand and refactor it is the only option.

The author mentioned some great factor to consider in order to make a good architecture. This is very important and useful when building a new system. Unfortunately most professionals do not get the chance to build new systems. They work with existing systems and spend their time either fixing bugs or testing code written by others. So, the ability to figure out the design from the messy code is even more valuable.

software-architecture-in-practice-chapter-4

What is considered quality software? Many people have a set quality attributes that systems must exhibit such as efficiency, reliability, security, maintainability, adaptability, sustainability, modularity, portability. In complex system it is nearly impossible to achieve quality attribute in isolation because meeting one attribute might have negative impact on the others. The importance of each quality attribute depends on the system and the author emphasizes the need of considering quality attributes at the architecture level and throughout the design, development and deployment of the system.
The must important attributes are usability, Modifiability and performance.
Usability refers to the user friendliness of the system. What does user friendly mean? Different users have different taste and different levels of computer and learning skills. So it is difficult to understand usability. We can try to understand how usability is defined for the product and the people who will use it. But there will always be unsatisfied users.
The rest of the qualities in the book are described in details with various scenarios that ease understanding.

From my own practical experience, business qualities are increasingly becoming important. Cost and schedule are the driving forces of many architecture decisions. Companies keep trying to build better products with less cost and aggressive schedule. So Attributes like “time to market” and “cost and benefit” presented as generalities in the book are actually very important attributes in many organizations.

What is Architecture?

A good architecture is more than just a high level design of a system. It is one that facilitates the job of the low level designers and the developers by providing a set of design rules that aids reduce complexity and guides the development and verification of the system. However, traditional architectures are different from software architecture. The author makes the point that contemporary architects may have a set of characteristics that a system must satisfy, while it is nearly impossible to guaranty all these rules in complex software systems because improving one aspect might impact the other. Software architects constantly play with trade-offs and the characteristics that are important depend on the system that is being built.

Architecture is commonly considered as the structure of a system. The author supports that idea and presents the advantage of looking at a system as a set of interacting components. This approach is intended to deal with the complexity of systems because it allows the architect to understand and satisfy a particular concern before moving to the next one. The author presents beautiful architectures as the ones with well defined use structures to enable iterative and incremental construction, well-defined testable modules and interfaces between them. I found it interesting because iterative and incremental development is an essential part of the agile software development process. Does this imply that beautiful architectures are the ones that facilitate the use of an agile development process?

PatG Blog for CS527 at UIUC

This blog has been created as a part of Cs527 (Advanced Topics in Software Engineering), at UIUC.