jdd-cs527

Branch-and-Bound / Graphical Model / Structured Grids

2009-11-11T18:22:00.000-08:00

Branch and Bound
This is another "pattern" that we are studying that does not quite strike me as a "pattern" but more of an algorithmic method. I have studied Branch and Bound in AI courses before, but never really considered it a pattern. Never the less, I suppose this paper does a reasonable job in explaining what it is, why it is necessary and how it would be used.
I suppose beyond the traditional branch and bound algorithm, this paper does give some incite as to how such an algorithm could be carried out efficiently through concurrency. I would have liked this pattern to focus much more on the concurrency aspect of Branch and Bounding or perhaps on some structures that may be especially useful for managing the branch and bound scenario in a parallel environment.

Graphical Models
Whoa. What is the deal here. I have found my self skipping to the "examples" section first to get a feel for what the pattern is talking about before heading back to read the rest of it. This time I was welcomed with a lovely "..." and no real examples. I guess that's all I could expect from a 3 page paper. The problem statement of this paper does not seem to have anything to do with the rest of the paper itself. "We can’t measure everything we need to know, and measurements are always noisy. How do we make use of the measurements we can perform to understand our data?" but then the paper discusses the graphic model behind probability. I guess there is some correlation, but man the authors of this are sure making you work to pick up on what they are trying to get across here.

Structured Grids
This one discusses how a "matrix-like" data structure can be exploited for parallelism. I see at the end of the paper they mention how geometric decomposition is a related pattern, but all in all i think this pattern IS just a specific instance of geometric decomposition. I think the solution of this paper was weak and hard to follow (although I guess there were a lot of pretty pictures!) and the math-heavy sections detracted from conveying the overall idea. I think they could have gone over how structured grids specifically allowed better processing over a geometric decomposition solution.

Shared Queue/Speculation/Circuits

2009-11-11T13:34:00.000-08:00

Shared Queue:

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?
The focus of a queue lies in the enqueuing and dequeuing of its elements because this is the only place where concurrency can corrupt the elements of a queue. If a enqueue is not set up in a thread-safe way, it is possible that data is put in out of order or worse lost all together and likewise with the dequeue.

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?
I think this question answers itself. Someone may opt for a less efficient implementation BECAUSE the concerns are already outlined with sample code available and this means that the developer would not have to worry about thinking through all the intricacies and it would probably be, in general, easier to implement than some complex solution.

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 think one important aspect of an application that would need to be present to make speculation be a feasible option is the opportunity for sequel tasks to actually not be sequential in nature all of the time. The paper talks about how the pattern attempts to run sequential tasks in parallel and then check predicts to see if the output was still valid or not. If it is not possible for sequential tasks to be executed without knowing the output of the previous step (which I'm guessing is the case for a vast majority of the time.) then this pattern is completely unusable unless there is some accurate way of guessing what the out put of each step would be.

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?
Given an infinite number of processors, we could simply run the last step with every possible input and we would be able to calculate the n-step sequential chain in only one step, however there would be EXTREME waste in processing, and it may not be so easily to validate that the correct input was selected as the guess. Therefore to make this pattern work we need to be able to reasonably guess inputs and efficiently determine if an output is valid at a stage. This leads me to believe that speculation may be better implemented in a domain that is already well established in which expected inputs and outputs are already well known.

Circuits:

Was this pattern what you expected from the name?
No. I think this was a terrible name for this pattern. I suggest as a better one "parallel bit wise manipulation"

It seems like a great deal of this pattern is described through examples of clever transformations for specific problems. Do these examples give you enough information to go about applying this pattern to a problem dissimilar to the given examples? Can you think of a way of describing these transformations at a more abstract yet actionable level than the examples do?
I found this pattern very hard to follow in the general sense. I could see what they were doing in Gray codes and the other examples they talked about, but I have a hard time envisioning how I would use this for anything other than what was already described in this paper.

Loop Parallelism, Task Queue, Graph Partitioning

2009-11-08T16:53:00.001-08:00

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?
The approach listed in the paper made a lot of sense to me. Identify areas where you are most likely to make a impact (Amdahl's Law) then analyze and sequentially improve those areas. I have found myself searching for areas that would be easily parallelizable and then working on those only to find a lack of overall application improvement.

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)?
I would have to go with the obvious and say automatic discovery is better than manual, however I must admit that I haven't spent too much time on making applications more efficient. I think there is rarely a monetarily justifiable reason to do so in industry and most of the time of enineers goes to adding features that can be sold right away.

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?
I would have to say that it depends on the loops you are trying to improve upon. If the loops are simple and related, it may be possible to achieve great improvements quickly and trivially. However, the more intertwined and complex the loops and their data become, the more difficult it must be to parallelize them. I can only imagine the upkeep of such parallized complex loops would be absurd to put it nicely.

Task Queue Implementation Pattern
------------------------------
How would you compare the Task Queue pattern to other similar distribution patterns like divide-and-conquer and fork/join pattern?
I think task queue makes a lot of since. It is also talking about dividing and conquering a task, but gives more direction on how to do it. There is some queue (or perhaps distributed multiple queues) and new tasks are put in and taken out from these as resources or tasks become available. Makes sense, right?

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'm having a hard time coming up with a situation when I could have personally put this pattern into use. I think this is probably more useful in complex mathematically situations probably relevant for lab experiments, simulations, data mining, etc. but maybe not so much in end user focused applications. Also this pattern didn't even really strike me as a pattern at all, but more of an algorithm for splitting graphs apart. The line is starting to blur on what is a software pattern and what is a mathematical idea.

PRES: Probabilistic Replay with Execution Sketching on Multiprocessors

2009-11-08T16:31:00.000-08:00

- What do you expect from a debugging tool?
I would expect a debugging tool to help me examine the internal state of my application throughout the execution of it.

- What debugging tools do you usually use? What are good and bad about them?
I usually use Eclipse running in debug mode and sometimes have to rely on dumping to log files for some tricking multi-threaded issues. Eclipse (and similar IDE based debuggers) are good because you can request the value of a variable at explicit times and step through an execution of the program to see how methods, messages, variables, whatever, interact with each other. However, they are bad for concurrent programming debugging. There is generally only two choices in debugging a concurrent application in an IDE and both result in an unnatural run of the application. The first is to let all threads go while you are stepping through one thread: this can produce bizarre behavior as the program may be expecting the threads to keep up with each other. Another is to halt the application completely as you walk through one thread but this also can lead to strange behavior as you are forcing other processes that would have normally been executing to wait. Neither of these approaches do well in reproducing strange concurrent behavior. Simply dumping out put (i.e. the old "print line" approach) across many threads help to see the actual behavior of a concurrent application but does not do well do help you do anything about it. Log files can also get clunky very quickly and even after reproducing a concurrent issue with log file dumping on, it can be difficult to trace through the thread executions that caused that issue.

- What are the challenges of debugging a sequential program? What are
additional challenges of debugging a parallel program?
Debugging a sequential program is easy with an IDE or similar, just give a known input with an expected out put, and step through the application to see how the input is processed and where it becomes inconsistent with what was expected. Debugging parallel programs is much harder as the thread interleavings, share memory states, etc. are all variable and dependent on each other.

- How important is replay for debugging?
It is very important to be able to reproduce a bug to fix it. Without being able to reproduce it, you really have no way of knowing when its fixed or what caused the issue in the first place.

- If you need to design a deterministic replay system, how are you
going to do it for sequential programs? Does it work for parallel
programs? If now, how to make it work?
For sequential programs, you can simply take state snap shots at various points in the program that would give enough information to known whats going on. Then the replay would just insert that snapshot back into the system and let it play out again. Because sequential programs are (barring some weird hardware behavior) for the most part deterministic, they should be relatively easy to replay. The same idea holes for parallel programs, but they just require much more state to be recording to accurately reproduce and replay the state of the system. The PRES project detailed out many "sketching" ideas that purposed just what needed to be recorded at a minimum to be able to quickly replay a concurrency issue.

Armstrong Thesis Chap 6

2009-11-04T18:49:00.000-08:00

gen_server and gen_event seem to be similar in form and behaviour, what are the differences between them? Why do we need a separate behavior that can be emulated with gen_server?
--I think the gen_event is basically a server that is specifically set up as a "subscriber" or "observer" for events. I guess a reason to have specific servers dedicated as listening to and responding events as opposed to a traditional server (which i'm guessing sits and waits for requests and responds directly too them) is if you wanted to have entitys waiting for system triggers or similar. They could be listening passively for most events but then WHAM when the right one comes they pounce. Also if the gen_event are set asside specifically for things like logging, perhaps we can leave some of these out of our servers to better isolate functionality.

What do you think about the benefits that Joe mentions at the end about small and fixed set of behaviours? Any more benefits? Or maybe some disadvantages?
--I think these benefits do ring true. Similar to design patterns as a whole, a small and fixed set of behaviors gives programmers a language to discuss things quickly and concisely without wasting a lot of time redefining similar terms and processes over and over again. Also keeping the design simple and reusing well tested components is very valuable. I know I have come up with some pretty wacky and over the top designs for things (see my previous post) that were entirely uneccessary but just seemed like a good idea at the time to either flex my ego or try to show off some new technology or idea.

Pipeline, Decomposition, Data Parallelism

2009-11-04T18:34:00.000-08:00

Are you a pipeline?
Did we already do you?
Parallel, I guess...

--------------------------

In this set, we discuss how to achieve parallelism by dividing up your data, or by dividing up your calculations. Are there any other kinds of parallelism, or can all parallel design patterns be placed into these two categories?
--It seems to me that these are a pretty exhaustive set of actions. If attempting to perform some tasks and gain performance on it, it seems to me that you can only break up the tasks into smaller tasks (dividing up your data) or performing the tasks at the same time (dividing up your calculations). I can't think of any other ways to parallelize something.

Have you used any of these? If you have, have you found them particularly useful? Challenging to work with? If you have any experience, what were their advantages or limitations?
What types of programs might any of these patterns be particularly useful for?
--This may sound ridiculous but I think I stumbled on all 3 of these patterns in one fell swoop a few years back (they are kind of related after all). I was attempting to make a log analyzing application for massive log files. I just had an input stream of the file and read in a little bit, made a "chunk" of it and spawned a new thread to process that "chunk" (geomeric decomposition). This thread would, in turn, complete some first pass processing and pass to another thread for the next phase and so on (pipeline). I'm not sure if this approach was particularly useful or not, I think if I were going for speed it may have been faster to load everything into main memory and perform all the operations real quick than all this complicated thread message passing. It was confusing and certain points of aggregated data that needed synchronization slowed down the system considerably. One advantage that I found, however, was that the memory foot print during any given time was very small compared to the amount of data I was processing and the gui response time was very quick (i was charting some data and I could see new points being added at extremely rapid rates). I think these patterns are more useful when there is just TONs of data such that even several hundred aggregation points would still shadow in comparison to the calculations being done.

Armstrong Thesis 5

2009-11-02T21:02:00.000-08:00

Supervision hierarchies:
------------------------
Erlang’s supervision hierarchy proposes two flavors of supervisors:
AND and OR supervisors.
- To which kind of applications does each of them apply?
AND supervisors apply to applications which require many dependent processes to run successfully and OR supervisors apply more to applications with independent processes in which restarting one would not affect the others.

Recursive restart ability is the ability of a system to tolerate restarts
at multiple levels. Erlang, through its supervision hierarchies, implements
recursive restart ability.
- Would you say that the supervision hierarchy mechanism in Erlang
makes restarts cheap? Does it also improve fault tolerance? Can you
please explain why?
It can make restarts relatively cheap by allowing restarts to occur only at the necessary level. I don't think a restart can be truly considered cheap at any amount though, but the layered approach allows some waste to be avoided. As far as improving fault tolerance, I think the supervision hierarchy can improve fault tolerance by increases the number of eyes looking for a fault.

- How does module granularity in the supervision hierarchy affect
the fault tolerance of the system?
More supervisors and more layers means a restart can be made more local to the fault but also means more management overhead.

Error handling and error interpretation:
----------------------------------------
Joe Armstrong defines an error as the deviation between the observed
behavior of a system and the desired behavior of a system. However,
building real systems is complicated by the fact that the programmer
often does not have a complete specification, but only some general
notion as to what constitutes an error, and what does not.
- How does Erlang deal with this issue in its error handling model?
If it doesn't meet the specification, throw an exception!

For each Erlang task, a supervisor will assign a worker to try to
achieve the goals implied by the task. Supervisors detect exceptions
generated by workers and are able to start, stop and restart them.
- Considering that with all the language support that Erlang provides
for this feature, the programmer still needs to implement the
supervisors and to plan for failure, would you still think that it's
safe to say that this approach is more robust than the traditional ones?
I don't know about "traditional ones" but I think a similar scheme could be mocked up in almost any language and doesn't necessarily have to be done in Erlang. Erlang does, however, seem to give good language level support for this type of system.

Task Parallelism, Recursive Splitting and Discrete Event patterns

2009-11-02T20:21:00.000-08:00

Task Parallelism
The Task Parallelism pattern gave some interesting in site on cost of synchronization management vs. granularity of the task management for different parallel environments (over a network, across an OS, etc.). Other than the numbers and graphs though, I'm not sure this pattern offered anything new that we haven't already discussed in this course so far. It is clear that for tasks to be able to effectively work in parallel, they must be of a nature that they can work together without knowledge of what any of the other tasks are doing and also require minimal coordination among them such that the cost of management does not outweigh the benefit of the parallelization. As Gabriel purports in his questions on this topic, I agree that for truly significant improvements in parallelization of software there needs to be a change in hardware support. For as the paper shows, the cost of synchronization at the hardware level is much cheaper than that at the network level.

Recursive Splitting
This pattern suggests that to keep hardware utility high, recursive problems need to split to not just simpler cases and eventually to a base case, but to more and more cases each time. Here Gabriel asks "The authors mention that the ideas behind the Fork/Join and Task-queue strategy patterns are essential to any developer who wants an efficient implementation of the Recursive Splitting pattern. Why?" My answer to this is that the key to successfully using recursively splitting for any type of performance gain requires efficient hand offs and reductions when the splitting occurs, or else all benefit from it will be lost to the overhead of aggregating the data at the end and the Fork/Join and Task-queue strategies give efficient methods for just this.

Discrete Event
I think the main difference between this pattern and the "Event based, Implicit Invocation" pattern is simply how the events are processed. This pattern gives more thought to things such as event ordered and how it could be handled if events are processed out of order (roll it back like Walmart's prices or be super cautious). I think timeouts to detect deadlock could be reasonable and certainly seems easier from an implementation standpoint. There is of course the fear that something would "timeout" that would have actually finished at some point and there is wasted and redone computation.

Monte Carlo, Graphs and Dense Linear Algebra oh my!

2009-10-21T20:30:00.000-07:00

Is it guess and check
to which my life reduces?
Oh, Monte Carlo!

----------------------------

Do you know these patterns, or are they new to you?

I don't know any of these patterns as patterns persay, but at least I was familiar with Graphs and Linear algebra. For example, I am aware of graphs. I have a general idea of what you can do with them. I am aware of Linear Algebra. These (and I'm assuming Monte Carlo as well, although I must, in shame, admit that I had not heard of Monte Carlo) have probably been around for quite some time though, much beyond the patterns.

If they are new, could you understand them?

I think I got a good understanding of Monte Carlo from this paper. I purport that humans are simple one giant 4 billion process Monte Carlo simulation of "life" and giant godly Reduce function is agregating our results as we die.

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

To me it sees that Structoral Patterns help define how you set up a program and Computation Patterns help to define how to actually solve a program. For example, MapReduce ( a structural pattern, or now that I think about it... was that a computational pattern.. I guess it actually is solving something now isn't it.... I suppose it is a pretty clear distinction between Computational and Structural.) was used to help run Monte Carlo experiments. Likewise, Divide and Conquer (copmutational?) and Composite (structural) help to define how to solve Graphing algorithms.

Armstrong Thesis ch4

2009-10-21T20:17:00.000-07:00

The author states that it is impossible to write concurrent code in a side effect free manner. Do you agree?

I don't think with our current programming languages we can write concurrent code in a side effect free manner. All concurrency needs to be thought out and planned for at this point, which undoubtedly affects the design, the code and the behavior of the application. Perhaps one day this can be automated through some new innovative programming languages, in which case writing concurrent code would be just like writing serial code and there would be no such new side effects.

Would there be any difficulties of following the error handling recommendations (let another process fix it, supervisors, let it crash) in another language than Erlang?

I think time outs could probably at least simulate the implementation of these recommendations in any other concurrency capable programming language.

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

Intentional programming is VERY important when it comes to maintenance. I've worked on a few projects with pretty cryptic code and not only did it not make the actual functionality very difficult to follow, it also made the intended functionality very difficult to follow. This, in turn, gave rise to doubts of the actual behavior of the program was expected and according to design or of it was a bug. Intentional programming is useful in that programmers beyond the original can glance over source code and know by method names and coding style if the actual code matches what the expected should be and can help build confidence that the program is running per specification.

Event-based Implicit Invocation AND Map-reduce

2009-10-19T21:18:00.000-07:00

Event-based implicit invocation

How is this pattern related to the well-documented observer pattern and publisher/subscriber patterns? Are they the same? How are they different?

I think Event-based implicit invocation IS essentially the observer / publisher/subscribe pattern. One difference does appear to be that rather than observers subscribing to subjects directly, this paper discussion some middle-layer "medium" to help pass around events and balance the load of massive subscriptions and event passing.

What are some advantages and disadvantages of implicit invocation versus explicit invocation?

Implicit invocation is easy: you just dump an event out there and pretty much that's the end of it. If someone is interested in it they will have subscribed to receive that event. Explicit invocation requires a little bit more knowledge about the observers from the subject so that they can actually make the explicit invocation. However, both pretty much achieve the same result.

What applications can benefit from a blocking vs. non-blocking event dispatching call?

Applications that can send messages without caring if they're heard in some reasonable amount of time can use non-blocking event dispatching calls because they don't need to wait for a response. More communication critical applications should probably make blocking calls to allow for proper time outs / error handling

There are many messaging middleware products available - should there be a messaging standard so that all applications can talk with each other, instead of relying on a message broker middle-man?

A standard message protocol would allow third party apps to message each other more seamlessly. I'm sure some such standards do exist (possibly for particular fields) and can name at least one in the field of medical imaging: DICOM . DICOM allows entities to message each other for connectivity and perform a limited range of functions (query / retrieve images, store images, etc.)

Map Reduce

Map reduce is essentially just a big parallel divide / conquer / aggregate.

I think failures should be handled by the system and invisible to the user. In fact one of the key benefits of Map Reduce, in my opinion, is that users only need to define the map and reduce methods. This allows for, as the paper says, "domain experts (as opposed to parallel computing gurus) to implement highly scalable programs based on this pattern."

Armstrong Thesis Ch. 2

2009-10-19T20:33:00.000-07:00

Armstrong advocates an architecture of inter-process communication solely via messages with no data sharing as the way to construct fault isolating systems. He claims this architecture also faciliates parallelism. What do you think? What advantages or disadvantages does this type of system have?

I think the inter-process communication does help isolate faults because it isolates the processes from corrupting each others data via some shared data. This in itself helps to facilitate parallelism because one process going down cannot take down the entire system. There may be some additional overhead to retrieve remote variables through message passing rather than directly through some shared memory access

Armstrong describes "fast-fail" processes as a mean for fault isolation and a way to ease fault management. A process should halt on encountering a failure. What do you think about this idea? What needs to be done to enable it?

"Fast-fail" is critical for fault isolation and management because it can prevent (to some degree) the spreading of false data and false system state (that a node is not failed when it actually is.) However, to enable "fast-fail" there would need to be some way of detecting failures and a method for letting a node know that is has failed. This would have to be handled with care so that people do not maleciously tell nodes they have failed as a denial of service attack or do not mistakenly tell a good node that it has gone bad.

What do you think about Armstrong's deicision of treaing the messaging layer as unreliable? What are the tradeoffs behind this decision? How does it affect the implementation of the modules that relies on it to communicate?

I think the choice to treat the messaging layer as unreliable helps in connectivity problem detection. If a messaging system was assumed to be reliable but a node was down, it would be difficult to detect. By requiring ACK messages to verify your message has been received you know that the message was receive and the connection is reliable. Of course this adds much overhead to simple message passing, to sit and wait for an ACK and (possibly) resend again unneccessarily.

Chess

2009-10-14T20:24:00.000-07:00

your move heisenbug
"Okay, rook to king's pawn 3"
shall we start over?

---

Wow a paper from microsoft research.

The Chess method of systematically testing different thread interleavings to try to reproduce intterleaving dependent faulty behavior is a good idea and I am impressed by some of the claims they make about finding new bugs in several well know systems.

I also find it interesting how they trimmed back the massive tree of interleaving combinations to keep the system interactively fast. I wonder if there are more bugs to be uncovered, though, in even the rare "pruned out" interleavings. I do think they make a rather bold claim in the beginning when they say the paper offers "the ability to consistantly reproduce crashing bugs of unknown cause". I'm guessing they can still only reproduce a small portion of such crashing bugs and extensive validation cycles of software would still be neccessary. (Or even if not neccessary, forced upon by the government.)

OPL Architectural Patterns (Layers, Pipe-n-Filter, Iterative Refinement)

2009-10-14T17:59:00.000-07:00

How do the two repeats differ from the first versions that you read?
These new versions of Layered Systems and Pipe-n-Filter Systems read more like recipes and less like the theory of version from before. It's just a quick, down and dirty "This is the problem that it solves and this is why you would want to do it."

They are shorter. Did they miss anything?
I actually don't think these versions missed anything. In my opinion the previous versions were way to long and detailed and easy to get lost. Even though these are way shorter, I think they are very focused on describing the ideas behind Layers and Pipes to an extent that a reader may be able to recognize it in a system on which they had worked on.

Did they include something that the first versions didn't?
I was already pretty familiar with the ideas behind both of these architectures and I think both gave a necessary amount of information to describe the patterns. Nothing seemed really unique among these new version over before although there was a VERY SLIGHT lean towards how the architectures lent themselves to be useful in parallel processing.

Did you learn anything from them?
To be honest, I did not pick up anything new from these new descriptions of Layered Architectures or Pipe-n-Filter architectures.

Do you have any advice to the authors of these patterns?
I would advise to try to speak more to how these architectures could be used or modified to use parallel computing to its advantage more explicitly. For example, the layered systems paper could talk about how each layer could itself consist of multiple cores or how many layers could be represented with one core each all one one machine.

For the new pattern, have you seen programs that used it?
I have not actually heard of the iterative refinement pattern before this paper.

What was hardest to understand about this pattern?
The hardest part to understand about the iterative refinement pattern is when it could be useful. I know they had some high level examples such as that it "is very common in drug discovery". I know this will sound contradictory to my above about the conciseness as a virtue nature of the other two patterns (maybe because I already feel like I know enough about them) but I think more detail and explicit illustration of how to use this pattern could be of use.

Refactoring for Reentrancy

2009-10-12T16:00:00.000-07:00

Ah Reentrancy
Oh Wait. Let me start again.
Ah Reentrancy.

-----

It's getting harder and harder to write about these "Eclipse parallelism automatic refactoring plugins" see through concurrent libraries, and relooper.

Summarizing the main points of this (and other) paper[s].

Most current programs are not in the best shape for the new wave of multi-core processors
Programs either need to be re-engineered from the ground up with concurrency in mind or refactored
Refactoring is manual and tedious with a small return on investment and large chance of introducing errors
Automatic tools can make refactoring easier with fewer errors

Refactoring for Reentrancy lists a few simple steps to make a program safe to run multiple times concurrently on different data sets my removing dependency on global state. (Taken directly from section 2 of the paper)

Removal of non-re-entrant access to library global state
Encapsulation of static fields in the application in getter/setter methods
Replacing static initializers with explicit lazy initialization
Replacing global state with thread-local state
Transforming the application to use a fresh thread for each section

The benchmark re-factoring applications show only slight improvement on speed in some cases which reinforces my previous conclusion that its probably best to stick to library re-factoring for now.

The one aspect of Reentrancy that differs, in my opinion, from the other methods for parallel performance improvements so far is that Reentrancy does not address only speed (in fact speed is only a side effect) but rather safety. Before multi-core machines, it may not have been possible to run the same program multiple times in parallel and so such considerations were unnecessary but now as this becomes a possibility we may find that programs we once considered thread safe can now cause unpredictible behavior when ran too close together.

BA 14: Rereading the classics

2009-10-12T15:10:00.000-07:00

This chapter throws together some final thoughts on Software (and "Brick and Mortar") Architecture while citing many different pertinent books on the subject.

There was also a nice little overview of several major aspects of Smalltalk and how those feature relate to other programming languages (for example the implicit type nature as it relates to C++ templates and Java generics and how inheritance can lead to nonsensical methods which should be errored out or subclassResponsibility'd or shouldNotImplement'd)

The chapter ends with a pretty relevant line: "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."

Programs can be beautiful but if they aren't functional they are worthless. There is a lot to be said for a functional program, but a functional program that is easy to maintain and change with the wind is like a well built house with a beautiful view.

BA 13: OO VS Functional

2009-10-07T20:05:00.000-07:00

What types of problems lend themselves to a Functional Solution?
Functional Solutions are well suited for mathematical problems that do not have a world state but simply calculate a result or end point.

What types of problems lend themselves to an Object-Oriented Solution?
Object-Oriented Solutions, on the other hand, are well suited for simulations. Objects can hold onto state and can represent things occurring in real life. Other objects can then interact with each other, each representing their own, and collectively, a world, state.

Is the Functional universe more flexible from a software Architecture point of view? If so, how; and of not, why?
It is flexible in some ways in that you can always just take any function and pass it to another function to wrap additional functionality around it. However, in my opinion functional programming (although I must admit I'm a youngster and have never used it myself) seems like it could get complicated to see what's reallying going on in a section of code.

Is Object-Oriented environment more manageable as a system grows towards the enterprise level? If so, how; and of not, why?
I would argue that Object-Oriented environments ARE more manageable as systems grow larger. There is easy addition and manipulation of large portions of functionality simply by adding new classes, inheriting, changing implementations of parent methods or over writing inherited methods, etc.

Also particularly of note in this chapter, I thought the "agents" were a good discussion of marrying the two paradigms.

ReLooper: Refactoring for Loop Parallelism

2009-10-06T16:13:00.000-07:00

First an executive summary of the article:

Some loops provide an opportunity for improved performance on multi-core systems via parallelism. However not all loops are safe to parallelise and manually parallelising loops in a safe way can be tedious, complicated and error-prone. Therefore, tools that help to automate the process, like ReLoop, can be useful to quickly gain some performance on current programs.

--

I agree that parallelising loops of existing projects can gain some performance on multi-core systems. However I also agree that "Just as ParallelArray is not the only class in the Java concurrent libraries, ReLooper is not the only tool needed to parallelize Java Programs." It seems to me that the automation provided by ReLooper only gives quick and dirty performance improvements in trivial cases (such as performing some aggregate calculation on every element in an array without any IO). However I think a lot of loops written to not iterate over all elements of an array or vector but rather look for a certain element in an array and break out upon finding it or perform some alternate behavior on exceptions, etc. I think ReLooper and similar tools may provide some marginal improvement in terms of general day to day application programming (although I do see perhaps more use in a calculation intense applications) but I think a more powerful stab against the evil of serialized programs would be to focus our time and energy into something that can be used much more frequently (like in automated parallel libraries). Relooper seems to me to be like one of those "spending 90% of your time on 10% of the code" type of situations.

BA 12: When the Bazaar sets out to build cathedrals

2009-10-05T19:52:00.001-07:00

What can we learn from decision making?

Obviously there are times in the life of any project where important, "life"-altering decisions have to be made. In the case of KDE, one such choice was to port KDE3 to use the QT4 libraries or to completely re-architecture KDE from the ground up. I think it is important to take such an opportunity, take in as many aspects one can gather and make a decision and stick with it. Probably if there was some good reason for going in a certain direction at the time of making the decision, you can't be in too bad shape, right? I think a bigger danger is hesitating to make any decision at all and letting the project die.

Do Cathedral type projects need this type of decision making in the middle of construction of the projects?

Of course "cathedral type" projects need this type of decision making (I'm assuming by cathedral type here we mean traditional commercial software). However the difference is that usually such decisions are made (for better or for worse) by executives and not by the developers directly. This can result in the reasons for such a decision being more political or financial than technical, which can, in turn, lead to problems and remorse afterwards when it is learned that the decision was made for the wrong reasons.

What are the strengths of the Bazaar Structure that out build the cathedral structures that we have known?

Bazaar structures have several key strengths that were detailed in this chapter. Firstly, authors are contributing out of a want to create the next best software, rather than out of pressure and deadlines in a job they are not necessarily so passionate about. Also, code from contributors is constantly under scrutiny of many other brilliant minds and if anything less than near-perfect is found, it will be quickly replaced with a better version. (With these points in mind the author argues that the quality of open source software projects is actually much higher than that of commercial projects. I could see it.)

Refactoring Sequential Java Code for Concurrency via Concurrent Libraries

2009-10-04T21:07:00.000-07:00

Surely it is faster
if you all go together
so what's stopping you

----

Q1. Sometimes it is possible to retrofit parallelism by refactoring an existing sequential application. Other times the whole system needs to be re-architected for parallelism. What are the advantages/disadvantages of these approaches? When would you do one over the other?

Refactoring existing sequential applications can be done partially using tools like Concurrencer as discussed in this paper. Additionally the logic is pretty much in place and the project can be brought up to be parallel piece by piece without every having a period of non-functioning software. On the other hand, completely re-architecting for parallelism would bring the program to a halt until all functionality had been reengineered. As the paper mentions, manual refactoring is tedious and error-prone and automatic factoring is simply not to a level of perfection yet. Therefore it would only be advantageous to refactoring an existing sequential application if the logic behind the application was such that gave way easily to parallelism (such as a divide and conquer algorithm). Otherwise improvements sought after by parallelising the program may not be so easily seen without a complete re-architecturing of the application to "force" areas to be parallel in areas that may not have been so obvious that they even could be parallel in the original implementation.

Q2. There are many libraries that target concurrency and parallelism(e.g., Java's ForkJoinTask, Microsoft's TPL, Intel's TBB, OpenMP, MPI,etc.). What are the advantages and disadvantages of using parallel libraries?

Parallel libraries are advantageous in that they are already thread-safe and optimized for you (hopefully) and that over time they will automatically get better and can improve your code without further alterations to your code itself. Disadvantages of using parallel libraries are that they may not necessarily do everything that you require and sometimes they could be more general than needed for your exact domain, which could lead to some sacrificing of performance / optimization.
Q3: The approach presented in the paper puts the programmer in the driving seat: the programmer selects a snapshot of code, and are factoring. The process is semi-automated, but not fully automatic.Compare and contrast the refactoring approach with a fully automatic approach, like the one used in automatic parallelizing compilers.

Fully automatic parallelization is probably useful in that it does not even require the programmer to be aware of it and many opportunities can be exploited for parallelism that would probably be missed by most programmers. On the other hand, automatic parallelisations can only be of use when the parallelizing application can be absolutely positive that the code is parallelizable, which will lead the compiler or other automatic tool to be unnecessarily conservative. Semi-automatic approaches like Concurrencer allow for a little bit more guessing on what can and cannot be parallelized with the user acting as a safety net.

Q6: The paper presents some empirical evaluation to support the claim that these automated refactorings are useful. What are some other factors that you would have liked to see evaluated?

I think obviously speed up is the most important factor in this paper, which was covered for some case studies with 2 and 4 cores. An additional factor that I would have liked to see, however, is the "bloat" factor of the code. If these automated refactorings sped up the code by cores* .75) but exploded the code to be 10 times as big (I'm especially hesitant after the merge sort example on page 7) The speed up may just not be worth the cost in maintainability. But I guess that bloated code may just be the price we pay for retroactively fitting old code and old languages to be parallel with our multi core systems today.

BA Chapter 11: GNU Emacs

2009-09-30T19:44:00.000-07:00

* Is it possible for a system like Emacs to be created in a non-opensource way?

I think it is possible for a well-architected and feature rich text editing application could be created in a non-opensource way. However, I think the heart of your question is if a compariable text editing application were made non-opensource, would it be as long lasting and adapting. I think the answer here is a resounding no. In the chapter they mention how packages are included only in the main distribution of emacs so long as the author of that package is willing to maintain it and become a regular maintainer. Additionally new features are created by users and a complex system of here-say and telephone so that by the time a feature is decided to be added to a main distribution it is already well tested and used rather than just some frill of a fat guy smoking a huge cigar behind an equally huge (if not even huger) desk. I think non-opensource projects fail to have this long term, customer-driven development and support stigma that opensource projects have.

* What are some of the disadvantages of a system like Emacs?

The biggest disadvantages I see with Emacs are its steep learning curve and buried deep-ness of its feature set. For example, I didn't even know it could do anything beyond copy/paste/open/save of text files before I read this article and so I had discounted it as completely inferior to vi and others.

* What architecture decisions have allowed Emacs to grow like ithas?

The fact that they kept the model. view, controller mechanism simple and efficient (having the view redraw the model automatically when waiting for character input only, for example) allowed users to in turn keep their add-ons clean and simple without worrying about optimization issues and similar. Also the easy extension by individual users and the strong community surrounding it helped Emacs to grow explosively.

* When is avoiding complexity a good/bad argument forimplementation?

Avoiding complexity is a good argument for implementation when the gains seen by the added complexity are not that great but the long term sustainability of keeping it simple are easily seen. On the contrary, avoiding complexity is not a good argument for implementation when there is really no intention for extension and/or an optimization is neccessary that can only be achieved through some complex course.

* Do you think Firefox will replace Emacs?

I think Firefox could become a new community driven sensation for developing javascript / web applications but I don't think it can REPLACE Emacs. Let's make sure we're comparing apples to apples here.

A Java Fork/Join Framework

2009-09-29T14:34:00.000-07:00

make a fork in time
to break your trouble in two
but be sure to join!

---

- As multi-core processors increase in popularity, do you think we'll see more
languages implement functionality to support fork / join programs? Can you
think of other languages which already have implemented these types of
interfaces?

I think it fork / join type programs make a natural fit with multi-core machines and I fully expect not only more language implementations of this paradigm, but further work in these implementations. Further machine and algorithm-independent improvements; further improvements in programmers thinking that will make complex tasks more easily broken up into smaller ones; basically a shift in every aspect of how we do things today to be more aimed to multicore.

- One reason to implement functionality like that proposed in the paper is to
allow developers to easily abstract parallelism and focus on other portions of
their code. However, at the same time, using this approach forces developers
to forgo writing their own mechanisms to handle parallelism, which means
giving up opportunities to optimize for their own needs and perhaps
decreasing performance. Do you feel this trade-off is worthwhile?

We talked about in a previous class discussion the delicate balance between the time it takes to build something from the ground up that is only EXACTLY what you need to avoid any unnecessary overhead wasted on generality etc. and the little time it takes to just take a more general library. Clearly the authors of this article feel that their solution is more specialized for Fork/Join than the Java thread libraries. However, there are probably more specific applications that would be even more efficient yet if users didn't started from scratch (or wrote the whole thing assembly!) There's got to be some end point though. The FJTask framework appears to be greatly superior to Java threads for a number of specific cases. I think if programs fit the description closely of what FJTask was created for (lots of parallel, granular tasks) then this may be a good solution but the more variance or complexity from this simple problem description would warrant much more debate on the use / consequences of this framework.

- Along the same lines, do you feel the fork / join interface proposed by the
author is intuitive? Can you see yourself writing code which might take
advantage of this functionality?

I do think the fork / join is intuitive. I could see it being useful for some of the algorithms we discussed in cs473. Personally, my code is not actually that intense on the processor so I think this may be over kill for me.

- The author briefly discusses some of the downsides of implementing this
interface in Java as opposed to C++, e.g. not being able to directly access OS
threading mechanisms. Additionally, forced garbage collection, while more
convenient, may be less optimal than handling memory management directly.
Do you think a similar, faster interface could be developed for C++ or another
language?

Of course. The benefits vs. downsides of Java has come up in many other of our discussions already and I believe the main points still hold here. See the discussion on JPC for more details.

- The work-scheduler algorithm of stealing work using FIFO and processing
work with LIFO seems to work well for most tasks. Can you think of any
examples where this may lead to poor performance?

If the number of small tasks keep coming and coming and coming it is possible that larger tasks would never be "stolen" and could end up being starved.

BA10: Strength of Metacircular Virtual Machines: Jikes RVM

2009-09-27T18:25:00.000-07:00

1. what advantages do metacicular Vms have over common VMS?disadvantages?

One main advantage for the developpers who are writing and testing the metacircular VMS is that they can find bugs and efficiency trips in both their application and in the VMS itself. Fixes for these can then often be translated to the program or back to the VMS rather than being an isolated enhancement for one of two unrelated languages. Likewise there are many more advanced libraries and functions of the newer programming languages like Java, and the runtime, being written in the same language as the application, would have full range of access to all of the libraries and abstractions that are available to the application. Finally there would no longer be a layer of communication neccessary between the Java byte codes of the application and the other langauge to process it. The VMS would simply have access to the byte code just as its own byte code.

The biggest disadvantage of self-hosting in a newer language like Java is probably the lack of maturity in the area. Sure Java has long been used, but it may not be stable enough in the new areas that may need to be brought to light for self-hosting. On the other more mature langauges like C have been used for a long time for running hosted languages like Java and could be thus considered very mature.

2. Jikes implemented its own threading model. this was done because operating systems didn't support threads as well as they do today. is this choice still a wise one? why or why not?

About the "green threading": I suppose at the time (1998ish, amirite?) there wasn't much OS support for monsterous threading. However, I would contend that now there is very good OS support, and that "green threading" techniques are probably no longer neccessary and lead only to re-invention and unneccessary work.

Our Pattern Language

2009-09-27T18:04:00.000-07:00

the more they learn about
the less they are concerned
except what they do

-------------

I think the idea of grouping patterns into layers makes sense. It allows programmers to specialize on a particular level in the hierarchy and master the when and why of it. Quite like the evolution of man (to which my haiku above refers), in the beginning everyone had very generalized roles: defend yourself, defend your family, eat, mate, survive. But slowly as the different tasks of man became more complex such that one man could not master them all to a sufficient level, people begin to take up specialized roles. 1 as a healer, one as a blacksmith. Fast forward a long time and the roles get more and more specialized, not longer a healer is special enough but now a brain trama surgeon specializing in tumor removal. This is an entire profession. Now let's swing it back to patterns and specialization. The more complex we get with our tasks, the more of a need there is to specialize -> This is the benefit of classifying patterns into different groupings.

As for the OPL's heirarchitcal grouping, the Architectural and Computational make good sense to me. These are clearly applicible to nearly all systems at the present and I forsee them being of use for a long time. I do not quite see to the extent of the authors of this article a need for so much focus on parellel processing. I do agree that it is of importance now, but to give "Concurrent Execution patterns" the same weight as "Architectural Patterns" and "Computational Patterns" seems a bit premature to me.

The Adaptive Object Model Architectural Style

2009-09-23T17:21:00.000-07:00

1. Does an Adaptive Object Model support the ability for an Object to dynamically change its TypeObject?

Sure why not. If the programmers abstract out the details of its classes, TypeObject could be a bare bones collection of, essentially, properties. Changing an objects TypeObject could be as simple as setting these attributes to reflect those of a different object. This seems to be analogous to having everything (or almost everything) specified as strategy patterns.

2. The Type Object pattern (PLPD3) states that an Object may delegate type behavior to its TypeObject and may decide to perform additional operations before and after delegating the request (Decorator, GoF95).

a. How is delegation implemented from an Object to TypeObject?

Because an Object can have a reference to a TypeObject, objects can simply make calls to the TypeObjects that they represent. The template pattern could even be implemented to leave hooks before and after TypeObject behavior in some cases to easily open up Object specific behavior before and after.

b. How is delegation handled if Question 1 is true?

I don't think the delegation is changed. If TypeObjects are abstract enough, there could be lots of "delegate methods" available to all the TypeObjects. Although now that I think about it, it may not make so much sense to change your TypeObject. If the TypeObject is not exactly what you want, why not just define a new Utopian one -> If in Utopia, why move to Ohio? Am I right, folks?

c. How can you avoid an Object having a tight coupling (knowledge of interfaces, semantics, behavior, etc.) with its TypeObject?

If the TypeObject handles those couplings, the Object will only have to know about the TypeObject. The TypeObject can then, in turn, handle all of these responsibilities through delegation.

3. How is versioning handled by an Adaptive Object Model?

a. How is versioning handled if Question 1 is true?

AOM Objects and Object types can have properties and / or attributes related to versioning. As new representations of Objects become better and better defined, old ones can be deprecated. There can even be a useInstead attribute or something that, once a new version of a class or object is defined, gets set to tell old objects that they are in the deprecated area and should convert to XX as soon as possible. The paper suggests using some interpreter to literally decide which version of an object to use and / or what behavior corresponds to it.

b. What is the granularity for determining a new Object or TypeObject version?

I think a new version of an Object or TypeObject is only justified once the connotation of that Object or Type object has changed. It wouldn't make sense to toss in a new version into the mix when the Object is still representing the same thing. If the object is expanded to include some new functionality or some new relationship, the idea of the Object has changed and thus a new version could be justified. (although it may make more sense to make a new class all together)

4. How do you guard against an explosion of new types in an Adaptive Object Model?

I believe this would have to be handled by process. You don't want to limit the ability to add new types that are legitimate, so any hard and fast rules implemented in software (like no more than 3 subclasses of any class, or no more than 100 classes total) would simply be too draconian. I think new types should be peer reviewed and frequently consolidated and garbage collected through meetings of domain experts to guard against the explosion of user defined type.