This time I read three of the computational patterns from OPL: Dense Linear Algebra, Graph Algorithms, and Monte Carlo. These are mainly suited for data-centric applications, in particular computing-intensive ones that need a lot of computations and thus the need to go parallel. Calling these systematic methods for computing and for aggregating results as patterns is new to me, in the past I am more familiar with structural/ architectural patterns or design patterns. With applications that are computing-intensive, during the high-level design stage the implementers would need to go back and forth between the structural patterns and the computational patterns to use for the overall architecture, since in this scenario optimizing the computation time is the key.
All three of the patterns are math-centric. The first two the name should be self-explanatory; for Monte Carlo it involves solving a problem by statistically sample its solution space under different parameter settings to derive a good estimation/ approximation. In one sense they are new to me since I have never done programming using those patterns, but at the same time they are familiar as I have done such exercises in my Math and Algorithms classes. For the types of the problems that we need to leverage these computational patterns, correctly formatting the problem to a linear algebra formula or a graph representation is more than half of the battle. In fact most of the time I spent in my Algorithm class was to try to reduce problems to a graph so I could then use well-known graph algorithms to solve them. (Incidentally, the solution section of the Graph Algorithms pattern makes a good final review sheet for CS473). So I definitely see benefits if there are also followup lower-level patterns that show how to convert some recurring types of problems to some mathematical representations.
Wednesday, October 21, 2009
Tuesday, October 20, 2009
Thoughts on Armstrong thesis ch. 2 - The Architectural Model
This is my first blog on the thesis written by Joe Armstrong titled "Making reliable
distributed systems in the presence of software errors" and it focuses on chapter 2. Chapter 1 of the thesis goes through some history of his projects and provides a breakdown of the rest of the thesis, thus chapter is actually the first chapter that touches the core of the thesis.
Joe Armstrong starts by defining his proposed architecture for building a fault-tolerant Telecom system. He does this by giving a set of descriptions to characterize his architecture. Out of the six descriptions that he provides, the fifth one, a way of describing things, seems to be a prelude to the actual description of an architecture. The first two, a problem domain and a philosophy, to me are the core to understand any architecture and thus I would place them above the rest. As for what else can be added to characterize an architecture better, these descriptions do not directly describe the interface between the modules but in this case it is probably OK since we are clear that all the communication is through message passing. Another description that I would expect from architecture dealing with data flows is a description of how an unit of data flows through the system, sometimes it is called "a day of life of a data packet" or something similar, which gives a lot of insight of a system.
The author then drills down to the various descriptions of the architecture. As for the problem domain, he makes it clearly that reliability and concurrency are critical. The system requirements also include the ability to support soft real-time and to be distributed. One of his way to achieve high reliability is to locally isolates faults. To be able to do this, he argues that there should not be data sharing between processes. Instead, all communication is through messages. Such discipline also prevent any of hidden dependencies between processes, many are unaware by the software maintainers. I also work on a system that use message passing as the primary mean of inter-process communication. Not only does it facilitate high reliability, it also makes in-state software upgrade easy. Very often when upgrading from one version of software to another its data structure also change; thus one can see if the structures are shared between processes, then it makes hard for an individual process to upgrade. In contrast, with message passing it is easy for a new version of software to add translation in its send or receive routines to deal with different version of the messages. Since each process knows which message versions that it supports, it also makes it possible to have a sanity checking to ensure two processes can communicate (share some common versions of a message).
The author then introduces the concept of concurrency oriented programming. He also creates Erlang, a Concurrency Oriented Language (COPL). He believes that programming in such language makes modeling the real world, which is concurrent, easy. Erlang handles process and concurrency management in the language. This is new to me as I am used to letting the OS to handle them. As for anything that is OS-agnostic, it makes an application written in Erlang more portable and to have a more consistent behavior across different OS. However, on the flop side this also means that the language and its libraries need to provide more support.
distributed systems in the presence of software errors" and it focuses on chapter 2. Chapter 1 of the thesis goes through some history of his projects and provides a breakdown of the rest of the thesis, thus chapter is actually the first chapter that touches the core of the thesis.
Joe Armstrong starts by defining his proposed architecture for building a fault-tolerant Telecom system. He does this by giving a set of descriptions to characterize his architecture. Out of the six descriptions that he provides, the fifth one, a way of describing things, seems to be a prelude to the actual description of an architecture. The first two, a problem domain and a philosophy, to me are the core to understand any architecture and thus I would place them above the rest. As for what else can be added to characterize an architecture better, these descriptions do not directly describe the interface between the modules but in this case it is probably OK since we are clear that all the communication is through message passing. Another description that I would expect from architecture dealing with data flows is a description of how an unit of data flows through the system, sometimes it is called "a day of life of a data packet" or something similar, which gives a lot of insight of a system.
The author then drills down to the various descriptions of the architecture. As for the problem domain, he makes it clearly that reliability and concurrency are critical. The system requirements also include the ability to support soft real-time and to be distributed. One of his way to achieve high reliability is to locally isolates faults. To be able to do this, he argues that there should not be data sharing between processes. Instead, all communication is through messages. Such discipline also prevent any of hidden dependencies between processes, many are unaware by the software maintainers. I also work on a system that use message passing as the primary mean of inter-process communication. Not only does it facilitate high reliability, it also makes in-state software upgrade easy. Very often when upgrading from one version of software to another its data structure also change; thus one can see if the structures are shared between processes, then it makes hard for an individual process to upgrade. In contrast, with message passing it is easy for a new version of software to add translation in its send or receive routines to deal with different version of the messages. Since each process knows which message versions that it supports, it also makes it possible to have a sanity checking to ensure two processes can communicate (share some common versions of a message).
The author then introduces the concept of concurrency oriented programming. He also creates Erlang, a Concurrency Oriented Language (COPL). He believes that programming in such language makes modeling the real world, which is concurrent, easy. Erlang handles process and concurrency management in the language. This is new to me as I am used to letting the OS to handle them. As for anything that is OS-agnostic, it makes an application written in Erlang more portable and to have a more consistent behavior across different OS. However, on the flop side this also means that the language and its libraries need to provide more support.
Sunday, October 18, 2009
Thoughts on OPL patterns: Event Based and Map Reduce
As a continuation of reading through patterns documented by OPL, this blog is on the Event Based pattern and the Map Reduce pattern.
For the Event Based pattern, the Yury Markovsky, Dai Bui, Hugo Andrade, and Jimmy Su frame it as a separation of intent to take a certain action from the actual implementation of the action; which I think it is both an interesting take and a concise way to describe the pattern. This pattern also makes the implementation of inter-module communication easy for the individual module implementers. They can just focus on implementing the event handlers.
As an invariant of this pattern, the author states that announcers of events do not know which listeners will be affected by those events. I think this invariant is too rigid. What about a system that the interested parties directly register to the announcer? I would think even this type of systems still qualify for Event Based pattern.
As for the Map Reduce pattern, it is used when a problem can be clearly separated into two stages: one stage for computation on subsets of its data, and the second stage to aggregate the result. As Tim Mattson points out, problems using this pattern has distinct two stages and thus one can provide a map-reduce framework shared by different applications; the domain expert for an application only needs to provide a map and a reduce function. This fits into an overall theme that we have encounters in various readings which is the separation of concerns between the concurrency experts and the application domain experts.
For the Event Based pattern, the Yury Markovsky, Dai Bui, Hugo Andrade, and Jimmy Su frame it as a separation of intent to take a certain action from the actual implementation of the action; which I think it is both an interesting take and a concise way to describe the pattern. This pattern also makes the implementation of inter-module communication easy for the individual module implementers. They can just focus on implementing the event handlers.
As an invariant of this pattern, the author states that announcers of events do not know which listeners will be affected by those events. I think this invariant is too rigid. What about a system that the interested parties directly register to the announcer? I would think even this type of systems still qualify for Event Based pattern.
As for the Map Reduce pattern, it is used when a problem can be clearly separated into two stages: one stage for computation on subsets of its data, and the second stage to aggregate the result. As Tim Mattson points out, problems using this pattern has distinct two stages and thus one can provide a map-reduce framework shared by different applications; the domain expert for an application only needs to provide a map and a reduce function. This fits into an overall theme that we have encounters in various readings which is the separation of concerns between the concurrency experts and the application domain experts.
Thursday, October 15, 2009
Thoughts on OPL patterns: Pipes & Filters, Layered Systems, and Iterative Refinement
The reading for the first part of the next class consists of three patterns from Out Pattern Language (OPL). The first two, Pipes & Filters and Layered Systems are familiar to us as we have read about them from another source. The third pattern, Iterative Refinement, is new.
The one on the Layered system seems very clear to me. It also helps greatly that I am already familiar with the pattern. I do feel that the authors put a lot of stress on portability. I guess this must be one of the main reason that people choose to use this pattern.
As for the third pattern, I find it hard to follow. I have seen some examples that avoids the dependencies between tasks to promote parallel execution; then addressing the dependencies at the end when merging the results. Since the invariants of this pattern are very general, I am not sure whether they actually fit into this pattern. Perhaps some pictures or a more concrete example can help to clarify.
Tuesday, October 13, 2009
Thoughts on Refactoring for Reentrancy
This paper is the third paper we read in CS527 regarding refactoring an aspect of Java program to enable it to run concurrently. This time it is to about making a Java program reentrant. As the other two papers, Jan Wloka, Manu Sridharan, and Frank Tip first characterize and analyze non-reentrant Java programs and propose steps to refactor them. After, they provide a semi-automatic Eclipse refactoring plugin and evaluate the tool to be both useful and efficient.
One major factor that makes a Java program non-reentrant is having global state. Thus, the refactoring involves replacing it and its static initialization with thread-local state and explicit lazy-initialization. Although doing so will affect the timing of the initialization but it is the authors' experience that such change often does not affect outcome.
While reading through it, I have a lingering doubt that such refactoring only work with the type of global state that does not correlate to the number of times the program is executed. For example, if there is a global state, counter, that tracks the number of times a program is called to perform a certain action, then this refactoring would not work as it does not increment a single copy of the counter. In this case, one will need to rely on other technique such as marking the global state synchronized. Granted that I don't use Java in my daily work but I think there are many cases with the global states that fall under this category. Since the authors do not explicitly call this out, I am still not sure.
One major factor that makes a Java program non-reentrant is having global state. Thus, the refactoring involves replacing it and its static initialization with thread-local state and explicit lazy-initialization. Although doing so will affect the timing of the initialization but it is the authors' experience that such change often does not affect outcome.
While reading through it, I have a lingering doubt that such refactoring only work with the type of global state that does not correlate to the number of times the program is executed. For example, if there is a global state, counter, that tracks the number of times a program is called to perform a certain action, then this refactoring would not work as it does not increment a single copy of the counter. In this case, one will need to rely on other technique such as marking the global state synchronized. Granted that I don't use Java in my daily work but I think there are many cases with the global states that fall under this category. Since the authors do not explicitly call this out, I am still not sure.
Sunday, October 11, 2009
Thoughts on Beautiful Architecture ch. 14 - Reading the Classics
This chapter is roughly divided into three sections. First, Panagiotis Louridas generally describes the software classics and just as the literary classics they have heavy influences on the later works. The author also proposes that programming languages can also be considered as classics as they also have major influences on the later languages and the software architecture that build on top of them. The author uses the Design Patterns and the Smalltalk language to make his point. One thing about thinking in patterns that the author has pointed out is that it inspires design reusability. These days, many of us already think software as consisted of modules with clear APIs that are reusable and easily swappable.
The author then dives into an introduction of the Smalltalk language and at the same time describes typical Object-Oriented language features in general. Compare to many other OO languages, Smalltalk is the purist that everything in it is an object. Unlike the strongly-typed language, its users do not explicitly declare type information. Instead, types are defined implicitly by what they do and their interfaces thus the type-checking is done at runtime when a selector (message) is passed to an object. There, an unexpected receiver may not handle such message and thus an error is notified.
At the end, the author turns the focus to brick and mortar architecture and in an attempt to also explain Smalltalk's lack of popularity. It is a rather interesting read as the author illustartes that some of the most influential architectures are actually hardly usable. As the author quotes Louis Sullivan, "form ever follows function". While we set to in search of beautiful architecture, we should not sacrifice the function. This being at the end of the last chapter of the book serves as an awakening advice to its readers.
The author then dives into an introduction of the Smalltalk language and at the same time describes typical Object-Oriented language features in general. Compare to many other OO languages, Smalltalk is the purist that everything in it is an object. Unlike the strongly-typed language, its users do not explicitly declare type information. Instead, types are defined implicitly by what they do and their interfaces thus the type-checking is done at runtime when a selector (message) is passed to an object. There, an unexpected receiver may not handle such message and thus an error is notified.
At the end, the author turns the focus to brick and mortar architecture and in an attempt to also explain Smalltalk's lack of popularity. It is a rather interesting read as the author illustartes that some of the most influential architectures are actually hardly usable. As the author quotes Louis Sullivan, "form ever follows function". While we set to in search of beautiful architecture, we should not sacrifice the function. This being at the end of the last chapter of the book serves as an awakening advice to its readers.
Friday, October 9, 2009
Thoughts on ReLooper: Refactoring for Loop Parallelism
Like the Concurrencer paper that I've posted a review on this week, this paper also presents a semi-automatic tool in Eclipse for refactoring Java program. It has a similar approach and philosophy as the Concurrencer paper. Just like the previous paper, it thinks the programmer knows that best and should make the ultimate call. It also has the same flow as the last paper which provides analysis on the underlying refactoring, presents a tool to retrofit parallelism into sequential Java programs semi-automatically, and gives empirical data to prove its accuracy and usefulness. In this paper it takes advantage of Java's ParalleArray framework and provides a tool, Relooper, that refactors loops on arrays and vectors acting on each element per iteration into parallel loops.
The tool should be a nice addition to the Eclipse refactoring toolkit. Looking at the results, it provides relatively few false positives except in one case. The authors have manually verified that there are no false negatives. Having no false negatives should be one of the most important characteristic this tool out to have to be really useful. Unfortunately it seems there is not a good way to test this thoroughly except by manual verification of the results after running Relooper on test programs.
The paper also outlines the characteristics of a loop that can be made parallel. It is a good idea to note down these so we can make sure our future programs can easily be parallel. What I gathered from this paper is that a loop should have these three characteristics:
1. A loop traverses all elements of an array.
2. No loop-carried dependencies.
3. Memory update in loop iterations are not conflicting.
The tool should be a nice addition to the Eclipse refactoring toolkit. Looking at the results, it provides relatively few false positives except in one case. The authors have manually verified that there are no false negatives. Having no false negatives should be one of the most important characteristic this tool out to have to be really useful. Unfortunately it seems there is not a good way to test this thoroughly except by manual verification of the results after running Relooper on test programs.
The paper also outlines the characteristics of a loop that can be made parallel. It is a good idea to note down these so we can make sure our future programs can easily be parallel. What I gathered from this paper is that a loop should have these three characteristics:
1. A loop traverses all elements of an array.
2. No loop-carried dependencies.
3. Memory update in loop iterations are not conflicting.
Thursday, October 8, 2009
Thoughts on Beautiful Architecture ch. 13 - Software Architecture: Object-Oriented versus Functional
In this chapter, Bertrand Meyer attempts to solidify the sense of "beauty" in beautiful architectures with certain criteria. The author focuses on three qualities: reliability, extendability, and reusability. He then argues that the object-oriented programming style achieves higher marks in all the criteria. In this day of age, when the OO style is much more prevalent than functional programming, I suspect that he is mostly preaching to the choir.
One of the main advantage of functional programming is the avoidance of program state. As the author has successfully argued, having states is useful and sometimes almost necessary and thus even the modern functional languages provide some mechanism for states. On the flip side, the OO style can lessen the complexity that come with having states with programming styles such as the separation of commands and queries, which I believe is a beneficial and common style today.
A couple of major advantages I believe regarding OO programming that the authors have also mentioned are first, by thinking in terms of object, it brings a programmer's mind set to a higher abstraction level and that usually helps when designing the overall architecture. It becomes even more necessary as programs grow in complexity; second, class inheritance greatly improves code reuse. With inheritance one inherits the default behavior from its parent(s) for free. This automatically promotes code reuse. The code reduction is felt even greater with multi-layer inheritance.
One of the main advantage of functional programming is the avoidance of program state. As the author has successfully argued, having states is useful and sometimes almost necessary and thus even the modern functional languages provide some mechanism for states. On the flip side, the OO style can lessen the complexity that come with having states with programming styles such as the separation of commands and queries, which I believe is a beneficial and common style today.
A couple of major advantages I believe regarding OO programming that the authors have also mentioned are first, by thinking in terms of object, it brings a programmer's mind set to a higher abstraction level and that usually helps when designing the overall architecture. It becomes even more necessary as programs grow in complexity; second, class inheritance greatly improves code reuse. With inheritance one inherits the default behavior from its parent(s) for free. This automatically promotes code reuse. The code reduction is felt even greater with multi-layer inheritance.
Tuesday, October 6, 2009
Thoughts on Refactoring Sequential Java Code for Concurrency via Concurrent Libraries
This paper is regarding semi-automatic refactoring support for Java programs. It takes advantage of the java.util.concurrent package available in Java 5 and the FrontJoinTask framework in Java 7. The authors present a tool, Concurrencer that enables users to transform a sequential program to parallel via converting int to AtomicInteger, HashMap to ConcurrentHashMap, and Recursion to ForkJoinTask.
In the paper, one major sell point for this tool is that it does not need user annotation. However, this tool being semi-automatic means that it still requires manual inspection to identify the places in the code for transformation. Nevertheless, it is useful. As the authors have pointed out, manual refactoring is error-prone; having a tool to do the busy work should be a lot safer provided that it does the work correctly.
One factor that influences whether a programmer chooses to use a refactoring tool is trust. When a programmer uses a tool, he or she loses control. Thus, it is very important that he can comprehend the automatic refactoring being done. Out of the three types of refactoring Concurrencer provides, the first two a programmer should have no problems understand but the last one may not be obvious. It is very likely that a programmer needs to go through the changed code in detail just to make sure it is correct. Thus, although the authors advertises the LOC that the tool saves the programmer from typing, in reality it may not save time. Saying that, it does help if complete automatic unit tests are available to verify or if the programmer reads this paper beforehand to understand the ForkJoin conversion. The trust level will build up gradually over time.
In the paper, one major sell point for this tool is that it does not need user annotation. However, this tool being semi-automatic means that it still requires manual inspection to identify the places in the code for transformation. Nevertheless, it is useful. As the authors have pointed out, manual refactoring is error-prone; having a tool to do the busy work should be a lot safer provided that it does the work correctly.
One factor that influences whether a programmer chooses to use a refactoring tool is trust. When a programmer uses a tool, he or she loses control. Thus, it is very important that he can comprehend the automatic refactoring being done. Out of the three types of refactoring Concurrencer provides, the first two a programmer should have no problems understand but the last one may not be obvious. It is very likely that a programmer needs to go through the changed code in detail just to make sure it is correct. Thus, although the authors advertises the LOC that the tool saves the programmer from typing, in reality it may not save time. Saying that, it does help if complete automatic unit tests are available to verify or if the programmer reads this paper beforehand to understand the ForkJoin conversion. The trust level will build up gradually over time.
Monday, October 5, 2009
Thoughts on Beautiful Architecture ch. 12 - When the Bazaar Sets Out to Build Cathedrals
In this chpater Till Adam and Mirko Boehm set out to describe the KDE project, focusing on Akonadi and ThreadWeaver. Along the way, they gave out insights on large-scale open source projects as a whole.
The authors made some keen statements on the strengths of open source projects. The mantra of "those who do the work decide" not only empowers the foot soldiers also install a sense of ownership and responsibilities in them. The ideas that people are the most scarce and valuable resource and the only criteria to include code in the software is its quality and if it is being maintained install honor in the authors. These are the same ideas being kicked around in for-profit software companies but are never fully practiced due to various non-technical reasons such as time to market, inter-team politics, leaders's desire to strongarm an decision, etc. Sometimes it is rather surprising what the scope and the quality an open source project can achieve when motivation by money and fame has failed.
Back to KDE and Akonadi in specific, it is driven by needs of the masses. It is the more Bazaar-style project of the two the authors talk about. Its background provides a good example about how an architecture based on some underlying assumptions deteriorated over time due to requirements changes. Since changes do not come instantly but rather gradually, there is always a constant struggle to either retrofit or rebuild. In the space of Akondi framework which deals with personal information management, there has been huge changes in its scope and scale as more applications converge to share and access personal data (a recurring theme in this class - data is king), the community finally come to a consensus to rebuild. To tackle this complex problem, the Layer architecture pattern is used to separate the concerns. Adding a platform API layer between applications and the storage access infrastructure so the applications using the Genome API and those using the KDE API can both share the infrastructure makes it development-platform-independent which greatly increases its usability.
In contrast, the ThreadWeaver project follows a more Cathedral-style path: it stemmed from an individual's vision. The individual has a vision to provide a conveniently available job scheduler for concurrency to make concurrent programming easy (another recurring theme - concurrent framework to shield the burden of concurrency from applications). The ThreadWeaver scheduler takes care of job scheduling and dependency enforcement at the same time allows its user enough control by specifying job dependency, priority, and queue policy. The specific example on the use of inverse ordering and priority to gives more weights on data that is already partially processed over the new data which prevents all data being processed at locked steps is a nice pattern that can be used by most of the Pipeline architecture that needs the similar behavior.
The authors made another key statement at the end: to take advantage of concurrency, it is not enough to provide a tool to move stuff to threads, the difference is scheduling. This is especially true if the move to concurrency is to achieve better performance.
The authors made some keen statements on the strengths of open source projects. The mantra of "those who do the work decide" not only empowers the foot soldiers also install a sense of ownership and responsibilities in them. The ideas that people are the most scarce and valuable resource and the only criteria to include code in the software is its quality and if it is being maintained install honor in the authors. These are the same ideas being kicked around in for-profit software companies but are never fully practiced due to various non-technical reasons such as time to market, inter-team politics, leaders's desire to strongarm an decision, etc. Sometimes it is rather surprising what the scope and the quality an open source project can achieve when motivation by money and fame has failed.
Back to KDE and Akonadi in specific, it is driven by needs of the masses. It is the more Bazaar-style project of the two the authors talk about. Its background provides a good example about how an architecture based on some underlying assumptions deteriorated over time due to requirements changes. Since changes do not come instantly but rather gradually, there is always a constant struggle to either retrofit or rebuild. In the space of Akondi framework which deals with personal information management, there has been huge changes in its scope and scale as more applications converge to share and access personal data (a recurring theme in this class - data is king), the community finally come to a consensus to rebuild. To tackle this complex problem, the Layer architecture pattern is used to separate the concerns. Adding a platform API layer between applications and the storage access infrastructure so the applications using the Genome API and those using the KDE API can both share the infrastructure makes it development-platform-independent which greatly increases its usability.
In contrast, the ThreadWeaver project follows a more Cathedral-style path: it stemmed from an individual's vision. The individual has a vision to provide a conveniently available job scheduler for concurrency to make concurrent programming easy (another recurring theme - concurrent framework to shield the burden of concurrency from applications). The ThreadWeaver scheduler takes care of job scheduling and dependency enforcement at the same time allows its user enough control by specifying job dependency, priority, and queue policy. The specific example on the use of inverse ordering and priority to gives more weights on data that is already partially processed over the new data which prevents all data being processed at locked steps is a nice pattern that can be used by most of the Pipeline architecture that needs the similar behavior.
The authors made another key statement at the end: to take advantage of concurrency, it is not enough to provide a tool to move stuff to threads, the difference is scheduling. This is especially true if the move to concurrency is to achieve better performance.
Subscribe to:
Comments (Atom)