This chapter in the thesis on Erlang dealt with programming techniques. The two big topics covered were fault tolerance and abstracting out concurrency.
The author pointed out that concurrent programs are harder to write, so making a module that takes care of all the concurrent part separate can be a big gain for maintainability and reliability. Because Erlang only supports one way of communicating between processes (message passing), the language can be fairly simple to use when performing this task.
The fault tolerance discussion was quite interesting. The author listed several practices that help, including letting other processes handle the failure, crashing on an error and intentional programming. As part of intentional programming, Armstrong recommends NOT programming defensively, something sometimes taught religiously on the security side. However, the author is not saying to NOT check arguments, but that Erlang automatically treats unrecognized input as an error anyway. Having this feature built in to the programming language eliminates potentially confusing code meant to capture error cases.
Wednesday, October 21, 2009
Some Computational Patterns
In this post we'll look at three computational algorithms: Dense linear algebra, graph algorithms and monte carlo.
The Dense Linear algebra pattern was new to me. I have (unfortunately) not had the opportunity to take linear algebra, but I could still understand the pattern and see when you would need it. I thought the write up for this pattern did the best job of illustrating points with pictures than the others that have been looked at.
The Graph Algorithms pattern I thought tried to do too much. I have fairly good background in graph theory and algorithms, so none of the algorithms were new to me. The authors did do a good job of pointing out the parallel opportunities available in each algorithm, but didn't include this on all of them. There are so many graph based algorithms that only some of them could be highlighted, meaning the treatment of each one was rather short. More detail would be useful in several cases.
The Monte Carlo pattern is a statistical pattern that I have seen described once before. The writeup made sense and I could understand it.
The Dense Linear algebra pattern was new to me. I have (unfortunately) not had the opportunity to take linear algebra, but I could still understand the pattern and see when you would need it. I thought the write up for this pattern did the best job of illustrating points with pictures than the others that have been looked at.
The Graph Algorithms pattern I thought tried to do too much. I have fairly good background in graph theory and algorithms, so none of the algorithms were new to me. The authors did do a good job of pointing out the parallel opportunities available in each algorithm, but didn't include this on all of them. There are so many graph based algorithms that only some of them could be highlighted, meaning the treatment of each one was rather short. More detail would be useful in several cases.
The Monte Carlo pattern is a statistical pattern that I have seen described once before. The writeup made sense and I could understand it.
Monday, October 19, 2009
Event Based and Map Reduce Patterns
Map-Reduce and Event Based patterns can be common when creating parallel programs.
Event based architectures typically subscribe for notifications with some server, which then sends the notifications when a signal occurs. This is common in GUIs; for example, registering for when a window size changes and then performing action in a callback when it does. One thing I thought was missing from this pattern was the context passed with the event. Some events may require data, others may only want to know the event occurred. At any rate, how this context is handled by the component sending the events deserves some treatment.
Another thing to consider in this pattern is error handling. This can take many forms - errors when registering, dispatching or the processing the callback. It depends on this situation if it is useful or not. For example, a GUI program sending a callback about a new mouse location probably doesn't care what happens in routines receiving this event. On the other hand, someone waiting on an object to perform an action probably wants to know if the object is unexpectedly deleted or crashes. Otherwise, resources may be tied up indefinitely.
Map-Reduce is the pattern of performing some computation on a bunch of object in parallel (mapping), then gathering the results (Reduce). I do not have much experience with this pattern, but it does have some great applications. The most famous one is probably Google's paper on the pattern extending it to run on a cluster. Anytime some action that is side-effect free needs to be applied to every item, this pattern is a candidate for implementation.
Event based architectures typically subscribe for notifications with some server, which then sends the notifications when a signal occurs. This is common in GUIs; for example, registering for when a window size changes and then performing action in a callback when it does. One thing I thought was missing from this pattern was the context passed with the event. Some events may require data, others may only want to know the event occurred. At any rate, how this context is handled by the component sending the events deserves some treatment.
Another thing to consider in this pattern is error handling. This can take many forms - errors when registering, dispatching or the processing the callback. It depends on this situation if it is useful or not. For example, a GUI program sending a callback about a new mouse location probably doesn't care what happens in routines receiving this event. On the other hand, someone waiting on an object to perform an action probably wants to know if the object is unexpectedly deleted or crashes. Otherwise, resources may be tied up indefinitely.
Map-Reduce is the pattern of performing some computation on a bunch of object in parallel (mapping), then gathering the results (Reduce). I do not have much experience with this pattern, but it does have some great applications. The most famous one is probably Google's paper on the pattern extending it to run on a cluster. Anytime some action that is side-effect free needs to be applied to every item, this pattern is a candidate for implementation.
Armstrong Chapter 2
The Armstrong thesis paper details using the language Erlang when developing a concurrent application. It is notable for its use in switching equipment.
On of the key features in Erlang is its fault tolerance. This is achieved partially by running modules in separate software processes and then only communicating with read only messages. By not sharing data, a crash in one process cannot affect others. This approach would also work with OS processes, although the overhead can be high. Given the right requirements, it may be necessary. While threads are faster, they can typically access all other data in the same process and corrupt it.
Another big theme is building concurrency into the language primitives. While this does ease some of the development, I think a lot of its benefits can be gained through libraries that abstract out the same parts. Putting it in the language itself makes development easier, but possibly at the cost of flexibility. In this case, it is acceptable as the message passing and communication are only allowed in one form.
On of the key features in Erlang is its fault tolerance. This is achieved partially by running modules in separate software processes and then only communicating with read only messages. By not sharing data, a crash in one process cannot affect others. This approach would also work with OS processes, although the overhead can be high. Given the right requirements, it may be necessary. While threads are faster, they can typically access all other data in the same process and corrupt it.
Another big theme is building concurrency into the language primitives. While this does ease some of the development, I think a lot of its benefits can be gained through libraries that abstract out the same parts. Putting it in the language itself makes development easier, but possibly at the cost of flexibility. In this case, it is acceptable as the message passing and communication are only allowed in one form.
Wednesday, October 14, 2009
Patterns
I finished reading three different architectural patterns - pipe and filters, layered systems and iterative refinement algorithms. It was good to read the short definitions of the problems and see how to write a pattern.
The pipes and filters and layered systems pattern we have discussed before. When put into this format, the main thing added over the previous papers was a Forces section and a more concise solution section. This allows an architect to gain a quick idea of how the pattern can be applied to a problem. The previous papers contained a lot more implementation details, showing the typical problems you might face and how to overcome them, and lessons learned from existing implementations. While needed when actually doing the implementing, the architect may not need it up front.
The iterative refinement algorithm was a new topic defining a pattern in algorithms where some steps are repeated until a good enough solution is produced. Having taken algorithms and data mining, I can see when this pattern could be useful, but I have not run across it on my job.
The pipes and filters and layered systems pattern we have discussed before. When put into this format, the main thing added over the previous papers was a Forces section and a more concise solution section. This allows an architect to gain a quick idea of how the pattern can be applied to a problem. The previous papers contained a lot more implementation details, showing the typical problems you might face and how to overcome them, and lessons learned from existing implementations. While needed when actually doing the implementing, the architect may not need it up front.
The iterative refinement algorithm was a new topic defining a pattern in algorithms where some steps are repeated until a good enough solution is produced. Having taken algorithms and data mining, I can see when this pattern could be useful, but I have not run across it on my job.
CHESS
CHESS is a tool developed by Microsoft Research in order to discover automatically find bugs in highly concurrent systems. These "Heisenbugs" can otherwise be quite difficult to reproduce due to only occurring when a specific interleaving of threads happens.
To solve the problem, CHESS captures non-deterministic inputs, focusing especially on synchronization APIs that can cause different threads to run. By taking control of this and then allowing CHESS to deterministically decide which path to take, bugs can be found and reproduced. Each run through CHESS takes a different path.
As a Windows developer (including quite a bit of kernel mode), I was impressed with the work done in this paper. They wisely chose to intercept data at a layer higher than the kernel, where they would otherwise lose some of the context needed. I have spent days tracking down concurrency problems, and this tool would make it easier.
I also was intrigued by the search algorithm for determining which state to check next. Because any thread can be pre-empted, I knew when I started the paper that the potential different thread interleavings are practically infinite. They showed that most bugs could be reproduced with only a few threads since all options are searched, and that pre-empting is usually not too interesting. Keeping it too a minimum and only using fair schedules makes the search space manageable.
To solve the problem, CHESS captures non-deterministic inputs, focusing especially on synchronization APIs that can cause different threads to run. By taking control of this and then allowing CHESS to deterministically decide which path to take, bugs can be found and reproduced. Each run through CHESS takes a different path.
As a Windows developer (including quite a bit of kernel mode), I was impressed with the work done in this paper. They wisely chose to intercept data at a layer higher than the kernel, where they would otherwise lose some of the context needed. I have spent days tracking down concurrency problems, and this tool would make it easier.
I also was intrigued by the search algorithm for determining which state to check next. Because any thread can be pre-empted, I knew when I started the paper that the potential different thread interleavings are practically infinite. They showed that most bugs could be reproduced with only a few threads since all options are searched, and that pre-empting is usually not too interesting. Keeping it too a minimum and only using fair schedules makes the search space manageable.
Monday, October 12, 2009
Refactoring for Reentrancy
This paper was the third one on automatically refactoring programs for parallelism. In this case, the tool enabled programmers to change programs to make them reentrant, by removing global references, using lazy initializers and warning about unsafe API calls.
The approach taken by the authors requires that the developer make some changes to optimize the program when finished. The given benchmarks for analyzing the results were far from impressive - some programs ran even slower despite using multiple threads due to the overhead created by the getters and setters. The program could also take substantial time to run.
I think the tool could still be useful in some situations where a program is being refactored with the goal of running several copies simultaneously. I would also have liked more reasoning on why some methods were rejected at the beginning of the paper, such as making an environment block. It requires a lot of code change, but this approach did to, it would be interesting to see them contrasted.
The approach taken by the authors requires that the developer make some changes to optimize the program when finished. The given benchmarks for analyzing the results were far from impressive - some programs ran even slower despite using multiple threads due to the overhead created by the getters and setters. The program could also take substantial time to run.
I think the tool could still be useful in some situations where a program is being refactored with the goal of running several copies simultaneously. I would also have liked more reasoning on why some methods were rejected at the beginning of the paper, such as making an environment block. It requires a lot of code change, but this approach did to, it would be interesting to see them contrasted.
Rereading the Classics
This chapter dealt with the design of object oriented design by reviewing Smalltalk. This language truly treated everything as an object, although it did not become popular.
I found this chapter interesting in that it showed the strengths of the language, but then also compared it to physical architecture. Fallingwater and the Villa Savoye were used as parallelisms for Smalltalk, where something has a beautiful architecture, but is not practical for everyday use. The two aforementioned architectural building have been used as examples for new architects, but neither of them were suitable to live it, due to a leaking roof or other problem.
Likewise Smalltalk's features have found their way into more recent programming languages as the features were beautiful. But in this case, being beautiful is not enough. As the book ends, it correctly concludes that usefulness is of equal value in architecture.
I found this chapter interesting in that it showed the strengths of the language, but then also compared it to physical architecture. Fallingwater and the Villa Savoye were used as parallelisms for Smalltalk, where something has a beautiful architecture, but is not practical for everyday use. The two aforementioned architectural building have been used as examples for new architects, but neither of them were suitable to live it, due to a leaking roof or other problem.
Likewise Smalltalk's features have found their way into more recent programming languages as the features were beautiful. But in this case, being beautiful is not enough. As the book ends, it correctly concludes that usefulness is of equal value in architecture.
Wednesday, October 7, 2009
Relooper
Relooper is another automated tool for helping programmers parallelize programs during refactoring. It helps turn Arrays into ParallelArrays and automatically finds when loops can be transformed using the new API, presenting all the changes to the developer.
The new APIs being given are quite useful to programmers. I think it helps reduce errors that may otherwise occur when performing parallel computations. In this case, when performing some operation on all items in an array, it can easily be incorrectly implemented leading to off by one errors. Plus, how the array is accessed may be done in a way that is NOT safe in a parallel setting and managing the resources of the threads doing the computation is more overhead for a programmer. The API hides this and lets the developer focus on the task at hand - creating efficient code.
The paper presented several areas for quantifying the usefulness of Relooper - correctness, speed, number of changes, and gained speedup. While these are helpful, it would also be nice to see the usability, based on feedback from others. This can be hard to obtain due to needing others to actually use the tool and provide feedback, but can be beneficial in deciding if a tool is truly useful. Can others use it too, or not?
The new APIs being given are quite useful to programmers. I think it helps reduce errors that may otherwise occur when performing parallel computations. In this case, when performing some operation on all items in an array, it can easily be incorrectly implemented leading to off by one errors. Plus, how the array is accessed may be done in a way that is NOT safe in a parallel setting and managing the resources of the threads doing the computation is more overhead for a programmer. The API hides this and lets the developer focus on the task at hand - creating efficient code.
The paper presented several areas for quantifying the usefulness of Relooper - correctness, speed, number of changes, and gained speedup. While these are helpful, it would also be nice to see the usability, based on feedback from others. This can be hard to obtain due to needing others to actually use the tool and provide feedback, but can be beneficial in deciding if a tool is truly useful. Can others use it too, or not?
Functional vs. OO Design
This chapter compared the modularity and flexibility of functional programming languages vs. object oriented programming languages. The author admitted up front that his knowledge of functional programming was limited compared to his knowledge of object oriented, and I think that showed in the comparisons. I think his treatment was fair on the areas he covered, but a functional expert may have thrown in some more areas for comparison. He did a great job of showing how object oriented design can cleanly address some issues found in functional programming and perform on par with the functional strengths.
Functional programming can be quite flexible in that operators and parameters are treated in the same manner, making it easy to extend. However, object oriented does a better job of modeling problems, and reduces the amount of programming through inheritance, something not available in functional programming.
Of course, I have much more experience as well with object oriented program languages then functional, which is limited to some Lisp. I think it is most useful for when formal verification or other analysis is need on the code, as it provides a clean way to automate the process due to disallowing side effects.
I had not played before with Agents in object oriented design, and found the solution fairly elegant as well.
Functional programming can be quite flexible in that operators and parameters are treated in the same manner, making it easy to extend. However, object oriented does a better job of modeling problems, and reduces the amount of programming through inheritance, something not available in functional programming.
Of course, I have much more experience as well with object oriented program languages then functional, which is limited to some Lisp. I think it is most useful for when formal verification or other analysis is need on the code, as it provides a clean way to automate the process due to disallowing side effects.
I had not played before with Agents in object oriented design, and found the solution fairly elegant as well.
Monday, October 5, 2009
Concurrencer
Concurrencer is tool to automatically refactor Java code, enabling it to take advantage of new concurrent APIs. Atomic integer operations, concurrent hash map, and a fork/join thread pattern are all supported by the tool.
This approach is useful if the code is already "close" to being parallel friendly. For example, it detects locking when accessing variables and uses the information to decide whether or not a transformation can be applied. If the locking is absent when needed, the program is going to need to be either fixed or redesigned before being able to take advantage of the new APIs.
The semi-automated approach was also useful, as the tool was by the author's admission neither completely correct or complete. Blindly applying changes could cause errors in programs. By allowing the programmer to be involved, tools like this can let the programmer indicate his intent, rather than automatically making changes based on actual implementation.
This approach is useful if the code is already "close" to being parallel friendly. For example, it detects locking when accessing variables and uses the information to decide whether or not a transformation can be applied. If the locking is absent when needed, the program is going to need to be either fixed or redesigned before being able to take advantage of the new APIs.
The semi-automated approach was also useful, as the tool was by the author's admission neither completely correct or complete. Blindly applying changes could cause errors in programs. By allowing the programmer to be involved, tools like this can let the programmer indicate his intent, rather than automatically making changes based on actual implementation.
KDE Development
This chapter in Beautiful Architecture dealt with the structure of the KDE project with two case studies. Akonadi is the backbone of personal information management(PIM), used by email and similar applications. Threadweaver is the library used for highly concurrent operations.
Overall, I found the presentation quite biased toward open source development. Granted, this was trying to show the advantages of their architecture, and especially team development, but using straw man logical fallacies is not the way to do it.
Putting that aside, it was interesting to see the thought process used in arriving at decisions. It was hard for the team to arrive at a decision, because a consensus had to be arrived at when deciding how to implement the KDE PIM project. In a more formal team structure, a leader would make the decision and the team would have to live with the choice. In the KDE environment, greater buy-in is generated by having a consensus before beginning development, but at the expense of time in convincing others. Perhaps it would have been worthwhile to prototype different solutions and then obtain concrete metrics for going forward. On my last product we had a couple of options for ways to implement a design, so we prototyped the solutions to evaluate what would work best. Any thoughts?
Overall, I found the presentation quite biased toward open source development. Granted, this was trying to show the advantages of their architecture, and especially team development, but using straw man logical fallacies is not the way to do it.
Putting that aside, it was interesting to see the thought process used in arriving at decisions. It was hard for the team to arrive at a decision, because a consensus had to be arrived at when deciding how to implement the KDE PIM project. In a more formal team structure, a leader would make the decision and the team would have to live with the choice. In the KDE environment, greater buy-in is generated by having a consensus before beginning development, but at the expense of time in convincing others. Perhaps it would have been worthwhile to prototype different solutions and then obtain concrete metrics for going forward. On my last product we had a couple of options for ways to implement a design, so we prototyped the solutions to evaluate what would work best. Any thoughts?
Subscribe to:
Posts (Atom)