Musings on Design and Architecture with Randy

Shared Queue, Speculation, Circuits

2009-11-12T10:55:00.000-08:00

Shared Queue:
This paper dealt with how to design a shared queue, a data structure that can be used to better facilitate parallelism by allowing multiple processes to pull from a task queue concurrently. The paper went through some basic design steps by highlighting the necessity to define access to the queue and then deciding on concurrency control. Some code examples were included to better illustrate the design. The author also went into details such as blocking and non-blocking queues and specifics for their implementation.

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?

I think that there is much consternation over enqueing or dequeing because if these operations do not perform correctly, then the queue is essentially worthless. In a parallel data structure the biggest concern is contention; if two things try to queue or dequeue simultaneously and contention is not accounted for the queue could be compromised.

Speculation
This pattern discussed a system to enable concurrent execution in an otherwise serial task. By establishing predicates to determine whether or not assumed inputs were correct, overall flow can be broken into many chunks and run independently. When execution is complete, if the predicates still hold, then the results can be committed, and if not they can be rolled back. This may lead to some wasted cycles re-running failed executions, but successful runs will decrease overall processing time.

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?

A number of items come to mind here. First and foremost would be the overall design of the program itself. If there are many global dependencies which tend to vary, then an assumption can be made that there will be a high number of rollbacks, and thus speculation may not be the best approach. Additionally, the ease in which a program can be broken down into predicates / execution blocks is another idea to consider. Finally, the cost of recomputing failed chunks of execution should be pondered as well.

Circuits
This pattern felt relatively short on content and long in examples. To summarize, the goal is to allow for problems best handled at the bit level to be executed in the typical word-based environment. The general idea is to break down a problem such that the program input is consistent with the word size of the architecture being executed upon, and then applying bitwise funtions (bitwise ANDs, ORs, shifts, etc.) to each word.

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?

Personally, unless one of my problems was a derivative of the example given, I don't know how much assistance this pattern provides. I think the real gain here is the idea itself; at first glance, I might not have thought to match input with word sizes and execute, but now I might. The examples do a good job to re-inforce the idea. I think for what it is, the pattern does an adequate job of describing its purpose... I suppose sometimes it is best to be concise.

Loop Parallelism, Task Queue, Graph Partitioning

2009-11-09T22:42:00.000-08:00

Loop Parallelism
This paper discussed different ways to transform loops in order to speed up execution. The author discussed the advantages of loop parallelism by explaining first why transforming loops is a good way to achieve cost-effective speed-up (typically easy to make parallelizable, can consume a large amount of execution time, allow for incremental optimizations), then dove into different ways to determine where to optimize (execution analysis), and finally wrapped with different techniques to be applied (fusion, fission, peeling, etc.).

How do you feel about IDE code analysis tools? Do you prefer to analyze by hand or by tool?

Personally, I've never ended up using an IDE to analyze the execution time required by different parts of a particular program. However, I do have to say that I nearly always prefer an automated tool to something I have to do by hand. There are many cases in which computers are significantly faster at calculations than people; I say let them do the heavy lifting ;)

How do you feel about the statement "many optimizations must be made on many loops prior to achieving optimization?"

The statement probably has some merit in that many typical programs will not be hugely loop-based and thus, because a smaller fraction of time is spent in loops, it will require more work to achieve speed-up. However, Amdahl's law still remains true, and so if a large portion of execution time is in a loop it may one require minimal optimization to see some large ROI.

Task Queue
After having so many papers reference a task queue it was good to finally read about it (admittedly I should have been more proactive here). This pattern details how individual "tasks" (independently executable items of work) should be assigned between different processors. A few questions should be asked; the most critical, what kind of scheduling will be used (eager vs. lazy) and what kind of architecture should be used (centralized vs. distributed). In both debates, ease of implementation primarily seems to square off against potential bottlenecks down the line. This pattern seems well-suited to act as a scheduling mechanism for many, many other parallel patterns.

How to compare task queue with other distribution patterns e.g. fork / join and divide and conquer?
Maybe I'm entirely off base but I'm not convinced that task queue can't work together with fork / join and divide and conquer. It seems as if fork / join and divide and conquer simply state how to divide up work; at their base level, they certainly come to a point where they are executing individual independent units of work. Task queue is just determining what items are run on which processor, for the most part (as long as they are put in the queue properly). Might these patterns work together?

Graph Partitioning
Frankly, a majority of this paper read like a few pages straight out of some of my *73 classes (which brought back very poor memories which I'd tried to repress some time ago). This pattern went through how one might go about breaking down a task into a graph partitioning problem. The first step, assigning nodes and edges, seems fairly straight-forward. However, picking an algorithm to break the problem down to got complicated.

Have you encountered a situation where partitioning might be handy? If not, can you envision one?

I have, thankfully, never quite run into a problem which seems like it could be represented in this way (or at least, I don't think I have...). It seems as though it might have some usefulness in things such as network flow, however.

PRES

2009-11-09T22:21:00.000-08:00

One of the readings for tomorrow's lecture is PRES. PRES is a system designed to help developers debug concurrent programs. The motivation behind PRES is that many systems in use today designed to debug parallel programs is extremely slow, making it near impossible to debug in a production system (as it would be massively inconvenient to the customer). To alleviate this concern, PRES uses "sketch-based" replay in that only a subset of non-deterministic behavior is recorded per execution of the program. These partial sketches can then be "replayed" and passed through a feedback loop to help reproduce issues. This can be done at significantly lower overhead than other systems on the market today.

Frankly, I found PRES to be an impressive peice of work. I don't know that I would ever be able to come up with a system as novel as sketch-based replay. The most interesting peice of the software was the feedback cycle. By using replay stacks and flipping race conditions, replays which might otherwise be unuseful can be used as a basis for finding bugs quickly. Additionally, the different types of sketches (the global concurrency, code block, FUNC, SYS, etc.) levels of capture we an interesting idea. Finally, the results really spoke for themselves - the overhead of a basic pass (FUNC, SYS) were enough to reproduce bugs but not producing crippling overhead in a production run.

To answer one of the questions posed by the lecturer... (copy-paste issues here, essentially, how to design sequential vs concurrent replay systems): When all is said and done the approach is the same in both cases: capture non-deterministic input. However, this is significantly easier in a sequential program as the only thing that needs to be considered is initial state and input. In a parallel program other items which may execute in varying orders (such as thread interleaving) need to be captured, making this a much more difficult proposition.

Pipeline, Geometric Decomposition, Data Parallelism

2009-11-05T08:06:00.000-08:00

This set of patterns dealt mostly with the optimization of processing on sets of data. To answer Kurt's general questions:

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?

This question actually made me think for some time. Truthfully, besides a hybrid approach (which was touched on briefly in the Pipelines pattern), computer science seems to come down to two things: the data available in the system and the operations performed on it. As such I don't know what other opportunities that can be found.

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?

I've used the | operation in Linux before; that's about it.

What types of programs might any of these patterns be particularly useful for?

I could see the Pipeline pattern being useful for tasks such as rendering. Geometric data pattern might apply to profiling and data mining applications.

Pipeline
This pattern felt similar (if not identical) to pipes and filters except with a few references to hardware-based parallelism and loop optimization.

How does this relate to other parallel patterns we've discussed, in particular Discrete Event and Pipes and Filters?

It seems extraordinarily similar to Pipes and Filters, except with less emphasis on making layers re-arrangeable as Pipes and Filters seemed to recommend. Pipeline feels more like a set linear path to me.

Geometric Decomposition
This pattern dealt with breaking down large data sets for easier processing and exploiting parallelism.

Geometric decomposition is used in many of the patterns we've discussed. The authors discuss four key areas of geometric decomposition: data decomposition, data exchange, update operation, data distribution and task schedule. Are any of these categories particularly important to any of the patterns that use geometric decomposition? Are any of these categories particularly challenges for any of these patterns?

Data exchange was a big part of the task parallelism pattern. It can be challenging to analyze the optimal architecture to perform a certain task - e.g. should the data be fine-grained or coarse-grained, running on shared memory or over a network?

Data Parallelism
This "pattern" essentially recommends breaking down a data structure into a stream of operations.

How does this pattern relate to other parallel patterns, such as Geometric Decomposition or MapReduce?

Truth be told I had a hard time associating this to either. MapReduce is definitely a stream of operations, but I had always assumed it was performed over similar items. The way I read the data parallelism pattern it made it seem as if a structure was broken down, thus leaving parts which might not be identical and thus losing the opportunity to use a pattern like MapReduce.

Armstrong Thesis Chapter 6

2009-11-05T06:31:00.001-08:00

In the 6th chapter of the Armstrong thesis, we are shown how to create an application by assembling a number of components (server, event manager, etc.) into a single package. Joe begins by describing the behaviors of each component and their implementations, interfaces, etc. We then saw how a supervisor could be created to start / monitor / stop each component. Finally we were given an example of how the application as a whole runs. One of the things that struck me as I was reading this chapter was how easily it seemed a number of items could be composed into a coherent system without a deep understanding of each component. From an application perspective, if an expert programmer defines a number of behaviors, then anyone could come in and re-use the behaviors to create an application. Once applications have been created, they can be packaged into a higher level release. I think that this sort of model really allows for quick introduction of new systems, and also could help improve the quality of the software (should an expert programmer be responsible for implementing the complicated, low-level behavior).

1. 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?
Personally I didn't think the two were that similar. Event managers stored state and accepted incoming events, whereas server generators seemed to start processes. I think because the two are semantically different it makes sense t have a separate behavior for them.

2. How do you like/dislike the form in Erlang about writing the behaviour(module)s? How do you understand intentional programming to make system easier to understand?
I think intentional programming can really speed up the development cycle. By picking appropriate names, methods, etc, it is easy to understand the system.

4. After seeing how supervisor and three primitive servers work together. What do you learn from those servers about how to abstract out concurrency, or how to apply the error handling philosophy? If you are the one designing this system, how would you design the components (servers)? Anything you want to add, combine, split or remove from these three servers
I liked how a supervisor can simply list a number of components and then start / stop them at all. Once they're started, it seems as if they're executing concurrently. Because they are self-contained units which rely on message passing (as discussed before) concurrency isn't difficult, which is a big win.

5. 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 personally think it's a good thing as I mentioned above. By coming up with a small set of behaviors, rather than monolithic projects seen in other architectural styles, composition is encouraged, which I think can speed up the development cycle and bring other benefits.

Task parallelism, recursive splitting, and discrete events

2009-11-02T19:08:00.001-08:00

Task Parallelism:
This pattern describes how large tasks can be broken down into smaller problems and executed in parallel. It begins by understanding the concurrency characteristics of the algorithm at hand; that is, it evaluates opportunities for parallelism by breaking down the problem into discrete tasks at various levels. Next, the platform must be analyzed; large tasks require more overhead and cannot be executed well, for example, in a shared processor cache, and will require more network transmissions to coordinate. Finally, the pattern describes a number of ways in which the tasks identified in the first step can be mapped to the architectures described in the second step.

To touch on some of Gabriel's questions, out of the recommended approaches, I've only really tried to coordinate OS processes. I don't believe that hardware advances are necessarily slowing down progress on this front; instead, the advent of parallel computing and multicore chips allows for more low-level tasks to be run in parallel.

Recursive Splitting:
This pattern deals with solving tasks generated recursively. One of the keys to this algorithm is to be able to generate more than one task per split to allow for good parallel execution. First, a problem must be written such that it generates more than a single task per breakdown, as an example, quicksort. Next, these tasks must be balanced to ensure concurrent execution is executed in roughly equivalent time so that things can remain in sync. Next, an implementation (such as fork-join and task-queue) must be chosen. Finally, the problem is optimized by taking advantage of locality such that subtasks can be executed more quickly.

To answer some of Gabriel's questions, task granularity is controlled by chosing a method to break down problems in a balanced fashion. It doesn't seem like many dynamic programming problems would lend themselves well to this approach.

Discrete Events:
This pattern deals with problems which do not lend themselves well to the parallel opportunities provided by patterns like recursive splitting, because they typically do not have a set ordered pattern. To begin, a list of individual tasks (execution units) must be defined, and then a flow must be evaluated which satisfies the required order of execution. Finally, this ordering must be enforced while avoiding deadlocks.

To answer Gabriel's questions, I am more familiar with message passing as I have no experience with shared memory; as such, I prefer message passing formats :) I do agree that sometimes timeouts would be more efficient than deadlock detection. By enforcing deadlock detection, valuable processing resources can be wasted and execution can be slowed. There may be cases when this is ideal (large tasks might be more suited) but it seems for lots of small tasks this would only hold back execution.

Armstrong Chpt 5

2009-11-02T18:14:00.000-08:00

The 5th chapter of the Armstrong thesis dealt with fault tolerant systems and their design. Joe began by touching on a hierarchy of tasks, meaning that if a complicated task fails, a less complicated one should attempt to be run in its place. Next, supervision hierarchies were detailed, more specifically linear and AND/OR hierachies (which essentially look like a tree). Finally, the last bit section went into the description of an error and how exceptions can be handled moving up the a supervisor tree.

I found the most interesting section of this chapter to be the types of supervision hierarchies detailed. At first I questioned the necessity of having explicit supervisors for each worker, but after examining the situation in more depth realized that it is the supervisors which allow for errors in execution to be corrected (or at least compensated for), a primary tenent in a fault tolerant system. To speak to Ovidiu's question, I can certainly see an AND/OR hierarchy being used to control a map/reduce framework, as each individual task should be able to start / stop at will independent of other controls.

The concept of error handling was also interesting. Ovidiu posed the question of whether or not Erlang's heirarchies and language constructs made exception handling easier than traditional languages. When I compare this situation to Java, I am not entirely convinced much has changed. Java has the functionality to raise exceptions up the chain of command as well (e.g. one function call throws a particular exception, on detection of this exception the caller function can call a new exception, etc.). Does anyone have any insight as to why Erlang may be superior to this approach?

Other architectural patterns

2009-10-22T13:30:00.000-07:00

Dense linear algebra:
This pattern recommended a number of libraries and then provided guidance on what to do if starting from scratch. The basics of the algorithm were to use an outer as opposed to an inner product, and also to take advantage of caching in the system to optimize results.

Graph algorithm pattern:
This pattern dealt with problems which could be reduced to a graph. The pattern goes over the steps of how to apply a graph algorithm to a problem. First, it is important to recognize the most applicable graph structure to the problem. Next, data structures (temporary for traversal, permanent for structure) must be decided on. Finally, traversal algorithms must be chosen and applied.

Monte Carlo:
This pattern went over Monte Carlo problems and established a methodology to find do so efficiently. The Monte Carlo problem (new to me) is something which is hard to solve analytically, but easy to solve experimentally (e.g. calculating pi). This pattern details the importance of random number generation, moves on to detail how to run the experiments in a concurrent fashion, and finally goes over results aggregation.

Do you know these patterns, or are they new to you? If they are new, could you understand them? What questions did you have? What could the authors have done (more pictures, more examples, more definitions) to help you get it?
I had seen just about all the suggested algorithms in the graph theory pattern, though never laid out quite in the manner that was chosen. This was very easy for me to understand. I also had a fairly easy time understanding the Monte Carlo pattern as well, even though I had never seen it before. The authors did a fairly good job of going through the problem in detail and giving good examples. However, the dense linear algebra pattern was new to me and hard to understand. This may have been a byproduct of the fact that it is a bit more mathematically rigorous; however, I do believe some more work up front to explain outer products and how their blocking algorithm moved over data would have been beneficial.

How are computational patterns different from structural patterns? Is there a clear distinction, or a fuzzy one?
I think that if you were given two patterns, one computational and one structural, and told to guess, 95% of the time you'd be able to identify which was which (and thus the line is slightly fuzzy). To me, computational patterns thus far feel significantly more algorithmic than structural patterns. A structural pattern seems to be more of a guideline which you have to work to adapt, whereas while the computational patterns certainly need adapted a bit they had more of a "plug and play" feel to them.

Armstrong Chapter 4

2009-10-22T13:16:00.000-07:00

In the 4th chapter of Joe Armstrong's thesis paper, we dive a bit deeper into the world of Erlang. First, Joe discussed why concurrency should be abstracted away from the developer. Next, the idea of "everything as a process" held by Erlang was covered. Finally, both errors and intentional programing were covered as well.

I personally found the section dealing on crashes to be the most intriguing. The "let it fail" model is certainly an interesting proposition. One question raised in my mind was how the components brought down by crashes would be brought back online. However, the idea of having a supervisor component watch a worker and wait for a result while checking for crashes makes sense - in this type of format, both hardware and software crashes can be watched for, and gracefully handled. Additionally, the example given of abstracting concurrency into the low level components and letting less experienced developers only extend functionality is a good idea in my opinion. It creates more efficiency and better software.

Finally, to address one of the questions given by Ben, I think using intentional programming is a great thing and should be done more often. It helps to self-document and makes code significantly easier to maintain. This wasn't something I realized true benefit from until this was emphasized in Ralph's CS598rj course. We were working quickly in a small team, and I was quickly able to notice the fact that I was able to read my partners' code significantly faster than usual. This trend continued throughout the project.

Event-based Implicit Invocation and Map Reduce

2009-10-19T17:51:00.000-07:00

These readings gave us additional insight into two more patterns, event-based implicit invocation and map reduce. Event-based implicit invocation seemed familiar as it appears similar to the observer pattern, and I've worked with map reduce before and thus didn't learn too much new, instead reinforced my views on these two patterns.

1. How is this pattern related to the well-documented observer pattern and publisher/subscriber patterns? Are they the same? How are they different?
The pattern seems the same in that items need to register on what they are listening for and others to broadcast changes. The key difference seems to be the medium; instead of directly linking objects in the observer pattern, this pattern seems to utilize a more abstract "aether" concept where messages are sent to and assumed to come out the other side.

2. What are some advantages and disadvantages of implicit invocation versus explicit invocation?
Implicit seems as if it would require less work for broadcasters, as it simply announces items has changed and continues; however, this could be more taxing on the communication medium. Alternatively, explicit will likely offer more control for how broadcasters notify listeners, but with more coupling between the two (potentially bad).

3. What applications can benefit from a blocking vs. non-blocking event dispatching call?
Applications which use a blocking scheme could be more efficient when data access (e.g. file I/O) operations take place frequently and polling would simply waste resources. However, non-blocking dispatch calls will allow for greater throughput of the application so long as other tasks were available.

5. 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?
Messaging in what sense? Per language, many languages already offer such functionality (Smalltalk, Java). Abstracting a message broker to a more abstract sense has been done before as well, but it is hard to make general enough to suit all applications.

6. How should (map-reduce) failures and errors be handled? Should the framework handle errors, or the application developer?
I believe a great many of the advantages provided by map reduce are lost when the application developer is required to step in to address a failure; I believe the system should handle it. It would likely be able to do so more efficiently given that the management thread should have intimate knowledge of the worker pool already and should be able to redistribute the load.

3. Are there any interesting uses of map reduce anybody has come across?
I've only briefly touched on the papers put out by Google, which give examples on calculating page rank and the like; I've never seen this algorithm used in the field, though given my discipline that is not particularly surprising.

Armstrong Thesis Chp 2

2009-10-19T17:28:00.000-07:00

In the second chapter of Joe Armstrong's thesis, Joe begins by laying out the problem his team was trying to solve as well as the philosophy behind their decisions. He then goes into more detail around how the team went about concurrent programming - namely, how they decided on a model (Concurrency Oriented Programming Language, or COPL for short) and the characteristics and behaviors of this type of model. Joe finally went on to describe characteristics of the system being built, the COPL itself and other library requirements. The section of this paper I found the most interesting was the descriptions of how they designed COPL requirements. Creating a 1:1 mapping to a problem domain and the importance of achieving this type of mapping was something I hadn't considered before but makes good sense. Additionally, some of the semantics around message passing and the design descisions that led to these semantics (e.g. send and pray) were interesting as well.

1. In Section 2.1, Joe Armstrong lists six descriptions to characterize their software architecture: a problem domain, a philosophy, a set of construction guidelines, a set of pre-defined compnents, a way of describing things, and a way of configuring things. Would you leverage them to characterize an architecture that you are familiar with? If so, is there any description that you would like to add or remove?
I think this set of descriptions is sufficient. If I were going about the process of documenting an architecture I was familiar with, I don't know that I would necessarily go through all six of these descriptions; I think a lot of the value they add is in designing a system from the ground up, and I would definitely go about creating these if I were trying to do that.

2. Joe 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? Have you worked on a system with such architecture? What advantages or disadvantages does this type of system have?
I believe this is a pretty good way of facilitating parallelism. One of the obvious disadvantages might be the fact that everything must be sent via messages, which may lead to large packets and more overhead. However, it seems to greatly simplify how one thinks about parallelism in general, which is sure to provide great value. I have worked on this type of architecture before in a data exchange product, though it wasn't necessarily designed to be concurrent, and felt it did a great job of abstracting a number of key concepts.

3. Joe 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?
I think failing sooner rather than later allows for quicker recovery, and as such is probably a good thing. To enable it, good coping mechanisms must be in place to handle system errors.

4. Joe Armstrong coins the term concurrency oriented programming to describe a programming style which the structure o the program models the concurrent nature of the real world. What are your experience with concurrecy-centric programming? He also envisions that instead of the OS-centric support, a concurrency oriented language (COPL) itself provides process and concurrency management. What do you think about this concept? What do you think would be its pros and cons?
I haven't had much experience with a strict concurrency oriented programming - many of the applications I've worked on have not had parallelism as a primary requirement. However, I do think a concurrency oriented language is a good idea. Many languages today were built in the days of single-processor environments and don't take into account the advantages derived from parallelism.

5. What do you think about Joe 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 it is a good assumption to make, especially in a particularly distributed environment as I imagine his telecom system was. It is harder to work with asynchronous failable messaging systems, and to confirm message arrival one must send acknowledgements, adding overhead. However, asynchronous unreliable messaging also helps to isolate faults to a single process.

Patterns, patterns, patterns!

2009-10-15T10:49:00.000-07:00

In the reading for today's class, we revisited two old friends (Layered Architectures and Pipes and Filters) and met a new one (Iterative Refinement). It was interesting to read through the new, iterative pattern, though I could have used more concrete examples. I will now answer the questions posed by Prof. Johnson:

How do the two repeats differ from the first versions that you read?
They are shorter. Did they miss anything? Did they include something
that the first versions didn't? Did you learn anything from them? Do
you have any advice to the authors of these patterns?
As noted, the papers for today were significantly less detailed. I don't believe the authors necessarily missed any details, but their explanations certainly were not quite as clear. I think just about everything in the Layered Architecture paper was covered better in the previous reading, but I did appreciate the new details on task granularity and applicability of concurrency in the new Pipes and Filter discussion we read this week.

For the new pattern, have you seen programs that used it? If so, do
you have a good story to tell about it? What was hardest to
understand about this pattern?
I have never even heard of the iterative refinement pattern prior to reading this article; as such I have no good stories to share. The hardest part I have imagining is how steps are broken down and transformed into concurrent tasks. Off the top of my head, I have a hard time imagining what sort of computer science problems require a solution such as this; in fact, the given example didn't really do a great job explaining it for me either.

Chess

2009-10-15T06:09:00.000-07:00

The Chess paper described a framework developed by Microsoft and other researchers in order to debug "Heizenbugs," or errors which are produced by non-determinism and are hard to replicate. To do this, they implemented a small number of hooks to interfaces which are associated with parallel programming (e.g. spawning new threads, synchronization primitives, etc.) and logged data as it moved through the system. Some of the key features include the fact that not all events are logged (as it can be too costly) and that Chess is relatively lightweight, which reduces the chances that the debugging libraries themselves hide the bug. I found the paper to be an interesting read.

Q1: What is your experience with testing parallel programs? How do you personally test parallel programs?
I do not have much experience with testing parallel programs; typically, I would simply kick off a number of background processes and execute the program I'm looking to test again and again. This might work for a school course; it is less likely to be an acceptable method in a large, enterprise environment.

Q2. Is it important to find concurrency bugs, especially those thatare not exposed by stress tests running for several weeks without failing?
Definitely. Especially in today's world where uptime is king in the server market, millions of dollars can be lost if a critical system is down for only minutes. Given that servers are designed to be able to run for months or more, it is definitely a good idea to try to get rid of as many of these hard-to-find bugs as possible. The intended use of the program at test might factor into this decision as well.

Q3. CHESS is an example of a paradigm called "small-scope hypothesis": if a bug exists in a system, it can be exposed with a small number of threads and a small number of preemptions. Do you agree/disagree with the small scope hypothesis for testing parallel programs? Why?
I believe it makes sense. When one thinks about it, many (or at least of the ones I've seen) seem to be simply two threads interleaving incorrectly to form a bad race; there is no reason huge numbers of threads need to be spawned to analyze this.

Q4: CHESS is a testing framework that can be extended with custom monitors. The paper already mentions extensions such as memory-leak and data-race detectors. What other custom monitors/detectors for parallel programming would you like to see added on top of CHESS?
I don't have much familiarity with custom monitors for parallel programming and thus can't really say for sure.

Q5: Since CHESS understands the semantics of the synchronization primitives on a Windows platform, it can perform some optimizations (e.g., avoid exploring delays that are impossible). How resilient is the tool to an "incorrect" understanding of these synchronization primitives?
I think if full optimizations were enabled, then the program would certainly find itself vulnerable. However, it seemed as if some of these optimizations occur based on the isRelease and isWrite bits, and the authors state that by simply always setting these to true a full happens-before graph will be generated, hopefully avoiding these pitfalls.

Refactoring for Reentrancy

2009-10-13T07:51:00.000-07:00

I cannot say I was a huge fan of Refactoring for Reentrancy. The paper discussed an automated tool to assist users in making their programs reentrant, essentially meaning that shared state does not affect subsequent runs (same inputs should provide same outputs every time). The methods discussed in the paper made sense, as creating thread-local versions of all state variables and warning about potentially unsafe system calls is a good way to approach the problem. However, there were a number of concerns I had with the paper.

The first was solely the example they gave to make a program reentrant. In my opinion, there are times when shared state is good, and the example program they gave was one of them. The only reason the program wasn't reentrant as written was because of bizarre system.out.println() calls and an exception around initialized state which didn't really need to be thrown. I understand that it's just an example, but it really didn't help illustrate the concept at all.

Next is the fact that the program cannot do a good job handling system calls. For example, while the Reeentrance system will certainly warn the user about potential unsafe calls (e.g. to the network layer, a database, file ops, etc...) it is something entirely different to go about replacing these calls. These sorts of ops make up an extremely large portion of many programs, and so I think refactoring to eliminate these would be quite difficult.

Finally from a performance standpoint, the results were not convincing. While they did do a little explanation, their refactoring actually slowed down 40% of the benchmarks they ran.

I understand that it is sometimes necessary to put forth work such as this which might not yield immediate results and that might serve as an intermediary for a more influential paper. I also appreciate the fact that the authors attempted to tackle a problem which will certainly grow as more and more computers are executing on multiple cores. I just had a hard time gaining much enthusiasm about this approach.

Rereading the classics

2009-10-13T05:49:00.000-07:00

In chapter 14 of Beautiful Architecture, the authors begin by laying out the details of Smalltalk and Squeak to give good examples of an inheritance-based architecture. I gained most of my familiarity with Smalltalk through Prof. Johnson's CS598RJ course, in which we used the language to learn design patterns. Admittedly, at first, I was less than thrilled about having to learn a new language in order to show that I was able to grasp the concepts being taught. "Why can't I do this in C++?," I exclaimed. "Arhghghdhgghg!" However, after the first month or so as I became more familiar with the language, I noticed a trend - it became easier and easier, and also more intuitive, to write in the language. "Latent typing is great!" I thought to myself. "I can read my code like a novel! And the way things are laid out, inheritance just feels so right."

I think what I experienced in the class is something akin to the lesson taught at the end of the book chapter: that we should learn from the classics, and utilize their lessons pragmatically in the real world. Here, I would consider Squeak an example of a classic; I certainly wouldn't use it to design an enterprise electronic medical record system, but I will definitely apply the lessons I've learned using it to my future designs.

ReLooper

2009-10-08T06:50:00.000-07:00

I found the ReLooper paper to be an interesting read. As I feel that parallelism can be difficult to generate by hand, any automated tool to assist in converting a program from sequential to parallel can be extremely beneficial. The techniques used in ReLooper (code analysis for shared variables, inference on different loop types) were fascinating to think about, and the Java ParallelArray was new to me as well. To continue the discussion, I'll go to Danny's questions.

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?
The advantages of a refactoring are a lower base cost while still obtaining performance increases; however, with this approach, all opportunities for parallelism may not be discovered. For a re-architect, it is more difficult and time-consuming to produce the up-front work, but the end benefit should be better.

Q2. There are many libraries that target concurrency and parallelism
(e.g., Java's ParallelArray, Microsoft's TPL, Intel's TBB, OpenMP,
MPI, etc.). What are the advantages and disadvantages of using
parallel libraries?
I feel that using these libraries will help programmers to better implement parallelism in their code quickly and easily without worrying about some of the underlying issues, such as synchronization; however, at the same time, some opportunities for speed-up might be missed, and other opportunities for parallelism might not work well with these libraries.

Q3: The approach presented in the paper puts the programmer in the
driving seat: the programmer selects a snapshot of code, and a
refactoring. 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.
I feel each type of tool has it's place; a fully automated system requires less work, but cannot do much about opportunities which might have been lost (e.g. when a loop was written improperly with shared data, or could have been refactored easily). At the same time, using the semi-automated tool will take more time, but yield better results.

Q4: Some of the transformations presented in the paper make the code
harder to understand (e.g., replacing a loop with a parallel
operation). What are some approaches to unclutter the parallel code?
A well-thought out replacement system which takes whitespace and indentation into consideration would certainly go a long way. Additionally, an intelligent commenting system could help the user as well.

Q5: Automatic loop parallelization has been a long time topic in the
Fortran community, with compilers having various degrees of success.
Is this problem still relevant for Object-Oriented code? What is
different now?
I think the problem is certainly still relevant, just a bit more complex. OO programming more readily yields itself to shared objects which can be more difficult to detect (which is why the section in the ReLooper paper on determing shared objects was interesting to me) and account for when parallelizing code.

Q6: The paper presents some empirical evaluation to support the claim
that the tool is useful. What are some other factors that you would
have liked to see evaluated?
I would have liked to see data on execution on > 2-core machines as I believe these will be far more prevelant in the future, in order to better illustrate some of the performance benefits which could be gained. Comparison of your results against an automatic parallelization compiler (if such a thing exists in Java) would have been interesting as well.

Q7: The paper presents several program analyses to ensure that loop
iterations can run safely in parallel. Are you convinced that these
analyses are enough, in other words, can you think about examples that
would not be covered by the presented analyses?
The paper has done a pretty good job convincing me this is safe, and I'm having trouble thinking of any examples where this might fall through.

Functional vs. OO

2009-10-08T06:10:00.000-07:00

In Beautiful Architecture Chapter 13, the author highlighted some of the features of functional programming, and went on to make the argument that Object-Oriented programming could confer all of the same benefits while providing additional functionality and ease of use. I have to admit this topic is near and dear to my heart, as after a semester of OCaml in the programming languages and compilers class I was more than ready to return to the land of Java and C++. I found myself silently rooting for a composite pattern to be used to address the "take" functionality described at the beginning of the chapter, and cheering during the big reveal.

Personally, I think the author's decision to focus on the topics of reusability, reliability and extendability was the perfect choice. These days, many software projects are large and complex, and are being worked on by many different people. The argument on page 322 around needing "t times f" definitions for t combinators and f operations really hits home. With large projects with many developers, maintaining that kind of burden becomes a huge headache, especially when working on similar areas in parallel. Refactoring can also lead to bugs. Finally, I've always personally found that object-oriented programs are significantly easier to read and understand than functional programs - the implicit structure and ordering really help to speak to the design decisions made and illustrate component functionality.

Building Cathedrals

2009-10-06T07:01:00.000-07:00

In Beautiful Architecture Chapter 12, the author describes two large projects in the KDE world, Akonadi and ThreadWeaver. Akonadi is a framework built to provide personal information (access to items like e-mail and address books) whereas ThreadWeaver is a new way to program a GUI in a concurrent fashion. The author went into some detail about how a large number of individual contributors were able to pull together to build useful functionality.

Personally, the portion of the chapter I found most interesting was how the PIM team transitioned over the years. Given I've never directly worked on an open source project, all of my large-scale development work comes solely from within an organization, which surely has a different operating model than the original PIM team. I can certainly see why PIM in KDE floundered as it did for so long based on the operating mechanisms described - more specifically, long e-mails chains with occasional flame wars. However, I'm actually quite impressed that over the years, the team was able to evolve as it did. To be able to decide as a large group that re-architecting the platform was a necessity not only from an architectural standpoint but also from an organizational standpoint requires a fair amount of perception. To move from a model where the team doesn't particularly get along to a team able to work together in small code jamming sessions at conferences speaks volumes about how KDEPIM has matured.

Fork / Join

2009-10-01T14:20:00.000-07:00

I found the Fork / Join framework a compelling read. As may have been evidenced by my questions, I believe that as technology progresses, programmers will have to abstract more and more in order to program efficiently. In an ideal world, specialists could write packages for each layer of functionality (e.g. parallelism, security, I/O, etc.) and provide standard interfaces for application programmers to use. I'll stop here, as I'll be the presenter this evening, but look forward to reading other posts on the topic and discussing with you all.

Feature creep

2009-09-30T22:16:00.000-07:00

If nothing else, Beautiful Architecture introduced me to the wonderful world of Emacs; and alas, I had always been a vi guy before. I had no idea so many different features were packed into Emacs. I think the author makes some excellent points around extensibility and ease-of-use in a community-supported system. The low barrier of entry but powerful language of Emacs Lisp certainly contributed greatly to its success. To continue my discussion, I'll go to the questions posed by Eric.

* Is it possible for a system like Emacs to be created in a non-open source way?
If you mean would it have exploded with features and remained as popular? Doubtful. Even though I've never used it, I'd wager a significant sum of money the only reason it is as popular as it is is due to the support of the community continually adding features.

* What are some of the disadvantages of a system like Emacs?
I can imagine it can be a pain to maintain, though I did like the attitude of "if no one is going to maintain it, we'll drop it." Not a bad way to prune the code of unnecessary features!

* What architecture decisions have allowed Emacs to grow like it has?
It's built-in, easy to learn but difficult to master scripting language would probably be the biggest I can imagine.

* When is avoiding complexity a good/bad argument for implementation?
I think when performance is the #1 system characteristic then complexity becomes more acceptable. However, at just about any other time, complexity should be reduced as much as viable.

* Do you think Firefox will replace Emacs?
Not really, no :)

Your Pattern Language

2009-09-29T07:00:00.000-07:00

I found Our Pattern Language to be a good, if somewhat stunted, read. I think the authors have done a good job putting together what can be construed as a framework for developing well-designed parallel programs. At the same time, I'm a bit concerned they may have made the model a bit too rigid. Sometimes, the strict 4-developer hierarchy they've proposed just doesn't exist. However, I think the work that has been done is worthwhile, as it provides a good look at the many patterns associated in the parallel program space. To continue the discussion, I'll answer some of the questions posed by Fredrik.

1. What are the benefits of grouping the patterns? Is OPL's hierarchical grouping sensible?
The benefits are likely the fact that each level of developer (e.g. application programmer, parallel programming framework developer, etc) has a good idea of what patterns to look at that are most applicable to their roles. The hierarchy did seem to make sense, though it may have been a bit strict.

2. Are their patterns too coarse grained? The paper mention that some of the computational patterns may even be whole pattern languages of their own. Do you think some of the patterns in other groups are pattern languages as well?
I think the patterns listed were as coarse as they needed to be. The intent of the paper seemed to be to lay out a pattern framework by grouping sets of other design patterns, not necessarily creating a new pattern themselves (though by creating this framework, they essentially did create a parallel program pattern).

4. Do you agree that our challenges in programming parallel processors is because we are weak at architecting software in general. Or is it that we program the wrong way and lack the "right" programming environment. Or is it that we don't have any killer applications for personal computers that really need 100 cores?
I think that these days, there is simply so much going on in computer science that specialization is a good thing. It's hard for the typical application developer to understand all the naunces around parallelism. By creating frameworks as you will see in the fork / join model, I think we can help ourselves on this front.

5. Parallelism isn't a new thing and the world have been parallel for years (multitasked processes in operating systems, Google's data centers, Amazon's web store, web applications). Why is it suddenly a problem?
Because these were enterprise environments with special developers running on specialized equipment; most applications didn't need to be parallelized. However, today, my home PC has 4 cores, and I anticipate this trend to continue.

Compilin' with myself

2009-09-29T06:41:00.000-07:00

Chapter 10 of Beautiful Architecture dealt with Jikes RVM, which is a VM built in Java to run Java code. The author began by pointing out the benefits of a metacircular VM (more below), which, nearsofar as I can tell, means that it is written in the same language as the code it is executing (and can also compile itself). I found this to be a bit tougher than our typical read, but intriguing nonetheless. Some of the background info, such as the T-Diagram, was new to me, but was explained well and made a fair bit of sense. I also enjoyed the discussion of the memory management toolkit; garbage collection in Java has been a topic I had wanted to learn more about, and this helped in that regard. To continue the discussion, I'll answer the questions posed by Marcus.

1. what advantages do metacircular Vms have over common VMS? disadvantages?
There are a few advantages listed. First, it allows language developers to use features of the language they are responsible for, which can lead to optimization of those features as developers use them. Additionally, a self-hosted system doesn't suffer from the fact that bugs in a different language can affect them; the example given in the text is that a C++ environment could cause memory management issues which would crash the VM, whereas Jikes would not suffer from these issues. One disadvantage I could see is performance; running Jikes in an already interpreted environment will likely be slower than a native VM.

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?
I think it has its advantages and its disadvantages. "Green threading" as discussed in the book isn't a particularly poor idea, but as the author points out, as it hides what is happening from the processor, applications will quickly miss out on feature sets as we move to more parallel machines, and in this sense a custom API for threading in Jikes is a good idea. At the same time, moving away from the norm means one more thing for developers to learn.

Adaptive Object-Model Architectures

2009-09-24T12:13:00.000-07:00

I found this week's reading on Adaptive Object-Model Architectures to be rather intriguing. I had heard about the model before, but as mentioned by the paper had never been directly exposed myself or seen any good documentation around it. This paper really helped to clear up the subject for me.

Personally, I find the model to be a rather elegant solution to an interesting problem. Personally, I've taken courses in medical informatics around clinical decision support systems. In these courses, professors would extol the virtues of a system which was configurable by experts. These types of systems are easy to update and maintain, and I believe an adaptive object-model architecture would be the perfect implementation strategy to use. Forcing software engineers to write domain logic just doesn't make sense, and by allowing engineers to write up a system and let experts input the rules I think many problems are solved.

From a technical standpoint, I found the assigned questions to be rather difficult (and in fact like a quiz :( ) and so I'd rather speak a bit more about the TypeSquare model listed in the paper. At first I was a bit confused by the concept as a whole; upon further investigation, however, it became clear. A distinct boundary between objects and their types, as well as objects and their types, is an elegant solution to a complex problem. A collection of properties to abstract properties from an object itself also makes a lot of sense to me.

x86 in Java

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

Chapter 9 of Beautiful Architecture presented a topic I had never considered before: x86 emulation in Java. Though I was initially skeptical something like this could be efficiently executed, as I read through the chapter the techniques used by the author were sufficient to persuade me. Admittedly, I am still curious if systems like this are widely used in the real world; however, as I've learned some time ago executing on ideas which may not seem the most practical now can yield many benefits down the road. To continue this discussion I'll answer the questions posed by Alejandro Rodriguez.

1. What advantages do emulators have over VMs? What advantages do VMs have over emulators?
Emulators offer the advantage of no special hardware support in order to virtualize an environment. However, at the same time, most VMs will be able to execute far more efficiently than an emulator as an emulator requires translation, which takes time.

2. Why would one prefer to use a Java emulator like JPC over a C++ emulator like Bochs, and vice-versa?
To me this comes down to speed vs. security concerns. Java executes in a JVM, meaning that an additional layer of protection is offered between the system and the code executing on the emulator. However, if speed was of the essence, C++ would be faster (though less secure).

3. Are there any performance and/or security considerations the JPC design team missed?
I felt that the justification used by the author around security was sufficient; that is, you would have to first have a malicious program, then a bug in a JVM, then a bug in a host OS, in order to run an exploit. As for performance, the authors have obviously studied this for quite some time and I find it difficult to produce an off-the-cuff response to this question. Seems like they did a pretty good job to me.

4. Has anyone used exceptions for reasons other than reporting errors? How about redefining a JRE's class loader?
Like the authors, in certain projects I've used exceptions for handling non-standard scenarios which may not be classified solely as errors. As for writing a custom class loader, I can happily say I've never had to deal with that type of thing.

5. Would JPC be useful for other non-x86 architectures? If so, how?
JPC may be useful for non-x86 architectures in that it may allow them to run x86 applications. Should the non-x86 architecture have a native JVM, suddenly all x86 applications would be available for use.

6. For what purposes can you see yourself using an emulator like JPC? Any interesting uses on your mobile phone?
Personally, I can think of nothing I'd really like to use it for. The main points raised by the authors near the end of the chapter, portability of computing, would be a "nice to have" at work - the ability to only have terminals in cubes allowing me to quickly and easily swap desks without having to carry anything around would be grand. However, I don't think I'd be willing to handle the reduction in speed, and a laptop tends to work just fine. I can't think of any uses at home, nor on my cell phone especially given what the extra execution overhead would to do cell phone battery life.

Big Ball of Mud

2009-09-22T06:02:00.000-07:00

The Big Ball of Mud reading was an interesting contrast to our typical reading. Instead of focusing on good design patterns, it instead evaluated how bad designs come about. The authors seemed to do a good job understanding why bad design comes about - I've seen just about all of the reasons on a daily basis in my place of employment. Another interesting discussion within the paper was the fact that spaghetti code tends to stick around longer than well-designed code, which, while counter-intuitive, makes a lot of sense when thought about. Even past that, a few projects I've worked on had large chunks of dead code that we knew wasn't used, but were afraid to clean up for fear of something breaking down the line. It's easy to see why certain developers who have been around for a long time are worth their weight in gold in a system such as this. To further the discussion, I'll now answer the questions posed by the presenter.

The authors describe the big ball of mud as a “haphazardly structured, sprawling, sloppy, duct-tape and bailing wire, spaghetti code jungle.” Have you ever worked on a system like this? And if so, what forces led to the formation of this ball of mud?
Yes, I have worked on a system like this. The formation was much like the authors described - a relatively small system that grew via piecemeal as well as pressure to release quickly & fix bugs quickly.

Is it inevitable that the systems we work on will become big balls of mud? What can we do to prevent this from occurring?
In the right context I believe systems can avoid the big ball of mud syndrome. It would require a few key points. First, there would have to be support from management in order to prioritize the architecture of the product against external demands (very hard to do). Second, there would need to be a good architect to keep a clear vision. Finally, developers would have to buy into the system as well.

One of the underlying assumptions that the authors appear to make is that it costs more upfront to build a system with a solid architecture than one resembling a big ball of mud. Do you agree with this?
Yes, I do. It's easy to hack together a solution; to design something that is meant to last, it requires more foresight and talent, both of which cost time and money.

What are some ways that we can best manage piecemeal growth in order to keep it from turning into a big ball of mud?
Again, I feel a primary architect who can maintain a consistent vision for the product will be essential. Also, design must be stressed at the beginning of a growth phase, instead of a "kick it out the door" mentality.

The authors reference work by Kent Beck which states: “Make it work, Make it right, Make it fast.” What do you think about this approach?
I think you can pick two of the three ;) In all seriousness, the slogan may work for small projects, but I find it impossible to believe that that slogan is applicable to any sort of enterprise-level software.

In your experiences, how often is throwaway code actually thrown away? Is throwaway code valuable?
I'd say my own throw-away code is thrown away most of the time ( >= ~66%). In my experience, the key is to manage this process yourself; if you set expectations up front before showing it to others, and have a good process for re-writing good, final versions, it isn't that hard to keep throw-away code out of a product.

The paper talks about “sweeping it under the rug”. Is this ever a good thing?
I do. As the paper notes, sometimes it's too expensive to refactor a large portion of a product, but at the same time, it's too expensive to keep working with the same old ugly interface. The "sweep it under the rug" approach is a good compromise.

Have you ever worked on a project that went through reconstruction? If so, was the rebuilt product/system “successful”? What were some of the signs that reconstruction was necessary?
Only in my own personal experience. I put together some web software to play music streaming from my local machine out over the web so I could listen to my music at work. My reconstruction efforts were not deliberate, admittedly; my web server's hard drive failed and I didn't maintain proper backups at the time, as most of the code was throw-away. I'd like to think I would have redesigned it anyhow, but to be fair I'm not sure, so it was likely good that my hand was forced ;) When it came down to it, I noticed that I had been kludging interfaces from the specs I originally intended, bringing things further and further away from the original design. I think the hard drive failure was a good thing in the long term.

Guardian

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

In the eighth chapter of Beautiful Architecture, "Guardian: A Fault-tolerant Operating System," the author describes the operating system built to operate on Tandem's fault-tolerant hardware designs. It made for an interesting read - architectures have evolved greatly through the years, and I enjoyed reading about the design decisions made in order to ensure older, more unreliable hardware could be used to maintain a reliable system. Other facets of the design revolving around the limits of the current hardware (the 16-bit address space, for example) were novel as well, including the 4 types of address space (user code / data, system code / data) and one of the initial stacks designed. To continue the discussion, I'll answer the questions posed by the one, the only, ANDREEEEEEEW HOOOOOOOOOOLDER!

-What are some of advantages/disadvantages to Guardian's naming conventions?
I found it a bit bizarre that there was never much discussion around why the conventions given were chosen (unless I missed this entirely). Otherwise, the advantage was that there was a system in place to establish what names should look like; otherwise, one of the disadvantages could be the fact that it seemed a bit non-nonsensical.

-How our systems you worked on that had to be fault tolerant different/same from Guardian?
To be fair, I've never really designed many systems where fault tolerance was a particularly high priority. In fact, in many of the systems I've worked on, fault tolerance seemed to be one of the least considered performance characteristic.

-How secure was Guardian?
Not particularly, from what I could read. Simply failing to check for addressing exceptions allowed for privileged execution mode. However, when Guardian was designed, I doubt security was near the focus it is in systems today.

-How was the messaging system designed? How did it perform?
Like many other components of the system, it was designed to be fault-tolerant. It ran at a low level, transparent to the operating system. Its performance was primarily an asynchronous methodology.

-Why didn't this architecture become the standard for fault tolerant software?
As the authors mention, computer architecture became inherently more stable, and so tolerance became less critical; on top of this, duplication of architecture is expensive. I believe between these two factors the market moved away from Guardian as a solution.

It's like a cake

2009-09-17T06:11:00.000-07:00

The A System of Patterns - Layers reading assignment presented a well-known architectural style that many, if not all, computer science students have run across at some point in their lives. However, there was benefit to revisiting the topic as I have definitely picked up some new thoughts on a topic I believed I was already well-versed in. Some of the design and implementation techniques presented (e.g. yo-yo, top-down) were strategies I may have though about implicitly, but my understanding has definitely improved on this front. Additionally, some of the liabilities of the pattern including cascading changes in layers wasn't something that occurred to me up until reading this paper. I'll continue by answering the questions posed by the great Kaiser Villhelm III (Will Vesely).

With the evolution of mobile technologies more people expect to be able to access software from more devices, where do you see this expectation having the biggest impact on the architectural layers (ranging from close to the client to close to the hardware or anywhere in between)?

I think here we'll see changes closest to the transport layer. As new network types (standard cell [the name escapes me], 3G, etc) are developed, existing phones will probably just swap out their network interface while leaving the rest of the APIs alone. As an example, when the iPhone moved to the 3G platform, they didn't ask all their developers to re-write their code; instead, they simply swapped out a transportation layer and left the developer APIs in place, a good use of the layers pattern.

Many business applications or school projects get divided into layers, have you come across any particular stellar examples or some really egregious ones that violate or strangle meld the styles presented?

While I can't comment on the project itself, I have seen some projects at work become layered far more times than they benefited from. This causes the odd problem of having to traverse far too many layers to be able to perform basic functionality such as querying a database, and made it difficult to refactor as these data routes were fragile.

An earlier paper discussed doing your architecture and layering as you proceed through agile, and this paper gives a handy step-by-step breakdown of ways to approach this, but how simple do you feel it really is to perform these sorts of refactorings on projects? Would following some of the steps have helped make the process smoother?

I believe it depends on which program we're looking at. Some programs would probably lend themselves well to refactoring based on this pattern; however, I believe other types of architectures such as some of the examples stated in the reading (X window system) would be hard-pressed to truly refactor to this specification. Following the steps presented in this chapter would certainly have made original design easier, but the refactoring part? Probably not so much.

Virtualization

2009-09-16T18:07:00.000-07:00

It was good to see my old friend Xen once more in chapter 7 of Beautiful Architecture. We'd spent some time going over the concepts in CS523 as well, which provided a useful context. While a majority of the chapter was a repeat, I did enjoy the discussions around ring buffers and some of the history behind the development of Xen, both being areas I hadn't been exposed to previously. From here I'll try to answer the questions posed to the class by Patrick.

In virtualized systems, the hypervisor runs in the most privileged mode. So a challenge in architecting those systems is to handle how guess operating systems will executes privileged instructions. How was that done before Xen? How does Xen handle it? compare both methods in respect to performance?

Previously, virtualization platforms would scan running operating system code at runtime to find priviliged instructions and replace them. Xen, however, used the concept of paravirtualization and instead rewrote small sections of the Linux kernel to facilitate the execution of privileged instructions. While this took more effort up front, the performance of the Xen approach is significantly (if not exponentially) better.

What was the primary concern when designing the Xen architecture?

To me, the primary concern of the Xen development team was to couple the advantages of virtualization without and reduction in performance. All of their efforts around paravirtualizaton, ring buffers, shared devices and even the hardware support (more later) point to this fact.

What is the role of domain 0 in Xen?

Domain 0 acts as the manager in Xen, roughly equivalent to a host OS running a VMM in another paradigm. Additionally, it is through route 0 priviliged calls were executed through in certain versions of the software.

Most new processors have virtualization support that allows unmodified guess operating systems to run on the hypervisor. What are the major features that had to be added to Xen to support hardware virtual machines? How was this facilitated by the open source status of Xen?

Xen had to be able to listen to the exceptions generated by hardware that signify that a priviliged operation is being executed. Xen's hypervisor could then trap this instruction and process it as necessary, required no paravirtualization. Implementing this type of support was greatly helped by Xen's open source status as developers from IBM and AMD could contribute low-level code to properly interact with supported hardware.

What is the role of the IOMMU?

The concept of mapping memory in shadow pages tables is not a new concept for VMs; however, an IOMMU provides the capability to map virtual devices to hardware in a safe way. This allows for operations like DMA to execute as intended in a safe and efficient manner, increasing performance.

Facebookin'

2009-09-14T17:13:00.001-07:00

Chapter six of Beautiful Architecture was an extremely enlightening read about a service which has touched just about all of our lives in some way, shape or form. I found it particularly interesting how Facebook has developed a number of custom interfaces to allow developers to utilize its rich content while at the same time preserving data constraints, user privacy and a standard interface. To go alongside my reading of the chapter, I'll answer the questions posed by the burliest, the beastiest, the incorrigible Mr. Jason Danielson.

How are social networking sites, like Facebook, helpful to other applications?
The primary value in a social networking site is the data contained within. All of this data can be used to better target advertisements and learn about users. Additionally, a site like Facebook provides application developers an easy way to reach wide audiences.

How / why did Facebook open itself up to 3rd party applications?
Because it isn't only external applications that benefit by using Facebook for their applications - Facebook also can reach / capture many more users by providing a means for developers to write useful applications. Facebook achieved this by exposing it's data through a variety of web services.

How did FQL help to optimize Facebook service calls? Why was FQL particularly of value to developers?
FQL was beneficial to Facebook because it was a much more effective language with which to query, thus reducing the strain on Facebook's servers. This was a boon for developers as well, as it allowed them to maintain a standard interface they already know (SQL-esque) and also to not have to worry about fumbling around nonsensical data queries.

How did Facebook guarantee the privacy of its users even while opening up data to third party applications?
It has created a fairly straightforward opt-in system; by appending a session key to every request to an application along with the application ID, the system can deny requests from applications which the user has not enabled.

How did FBML help shape the current environment of third party integration with Facebook?

It allowed tight integration of applications by allowing developers a significant portion of control over the display of an application with custom code; at the same time, it rendered all data and executed all commands in a trusted environment.

Do you think FBJS is a fair compromise to Javascript for developers of applications on the Facebook platform? Why or why not?

I believe that FBJS is hugely fair to developers of applications. A developer must realize that his or her content must execute in a trusted manner. Many sites would accomplish something like this by simply disabling JS entirely (I bet any DOM commands I typed here wouldn't show up). Facebook went out of their way to give developers a degree of freedom they typically have not had on social networking sites. Developers should only be happy with this situation.

What do you think architectures such as the Facebook Platform mean for the future of online computing?

I believe these types of architectures are only going to grow stronger. Data repositories are a powerful thing. Executed well, they allow for a vast number of extremely beneficial services such as data mining, targeted advertising, collaboration, and much, much more. At the same time, executed poorly, these types of architectures can release vast amounts of sensitive data, and I feel that at some point in the near future this inevitability will shape the future of online computing as well.

Pipes & Filters

2009-09-14T16:36:00.000-07:00

I found the Pipes & Filters paper to be an interesting read. As Michael posited, it's a fairly common architecture and I have had some experience putting together systems in this manner. Our team used ChainBuilder, an open-source SOA environment based on Java / Eclipse, to build up a healthcare application. Essentially, much of the work was spent designing efficient filters and then connecting them with common pipes.

We quickly learned the value of designing re-useable filters after having to re-architect a number of components. Reading the paper prior to implementing this system would have been helpful :) However, I can imagine systems where a Pipes & Filters implementation would be less than ideal - for example, anything where throughput is critical (e.g. games) may suffer from having to push data through a number of layers.

Based on some of the points brought up in the paper itself, I think pipes and filters would produce more efficient parallelization on data sets which are not dependent on each other that can be executed in parallel. The best example I can think of would be something along the lines of Google's implementation of it's map reduce architecture - many machines running small independent tasks which were combined at the end to produce a final data set. By allowing each calculation to run in parallel and filtering down results based on the data set I believe some real performance gains could be realized in a situation such as this.

Finally, for active vs. passive filters, I think that active filters would work best in an application which was stream-based; for example, online video. Passive filters would be more suited for typical block data transfer (e.g. in an Ajax call to request information from a server).

Beautiful Architecture Ch 5

2009-09-10T07:46:00.000-07:00

I found this chapter to be an interesting read. As I first went through and the author was denouncing SOAP / WSDL contracts and trying to advocate the semantic web and REST, I was having a hard time accepting his views; after all, I'd done a fair amount of work that was pretty well executed within the SOAP / WSDL web service world (a large interoperability project). I can say the author did help to sway me a bit; however, I'm still not entirely convinced that the problem of businesses being able to search their data is solved by the model the author proposed. In the world I work in (healthcare) data definition contracts are critical as it's important to know which fields of data map where; by using something like the semantic web, loose data definitions, etc. we could never be sure and would put patients at risk.

To answer Will's questions on Beautiful Architecture chapter 5:

Why is it important to have different representations of the same data and to have it at the same name?
This allows different clients to take advantage of the data while maintaining a common interface. It makes it easier to search for and find the data and then utilize it.

REST imposes a lot of restrictions, namely only 4 verbs. How is this beneficial? Detrimental?
It's beneficial in that it is easier to learn and remember, it simplifies interfaces and also as pointed out by the author makes it easier to browse. However, at the same time, it certainly reduces the designer's ability to succinctly put together more complex operations which could instead require a combination of the REST primitives.

What are the implications of putting data in the forefront? Is this always a good approach?
The implication of putting data at the forefront means it may sacrifice functionality / performance of the system. Your interfaces will be different and they may not be as easily optimized for performance. I think that where performance is critical this may not be the best approach; however, practically, this is typically not the case and I think we could see a lot of benefit by moving to a data-first approach.

Architectin' mah Javas

2009-09-08T17:36:00.000-07:00

Here are some responses to the questions posed by Prof. Johnson around the ArchJava paper.

What are the advantages of making it an extension of Java?
First and foremost, Java is a popular language in use all over the globe; by creating this as an extension of Java, you are ensuring familiarity with a great number of users. Additionally, many easy-to-extend IDEs for Java (particularly Eclipse) would lend themselves well to creating an interface for this language, thus increasing potential user base and easing development. Finally, using Java as the language of choice meant that the authors of the paper did not have to re-invent their own compilers around a proprietary language, instead implementing some rules within a JVM instead.

What problems in Java does it solve?
As the authors described, it can support some best practices as far as coding is concerned. Admittedly I've written some statements which go a little something like this in my day:

myObject.getElement().getItem().displayOnScreen();

With the enforcement of connectivity principles provided by ArchJava, code would probably be written more properly coupled in ArchJava. Additionally, it would make producing accurate, up-to-date architecture diagrams a much more common occurence in software development, a practice which would only help.

If ArchJava were a mature product, would it solve the problems of the"Making Memories" chapter?
I hesitate to say that a mature implementation of ArchJava would "solve the problems" of the Making Memories chapter, as I believe the Making Memories program was well-designed by a number of intelligent developers. However, I do believe that ArchJava would have helped the developers of the system come up with more coherent, better documented code more quickly. As I mentioned above, ArchJava would do a great job of enforcing communication constraints, and an intelligent group of developers would most likely be able to use a product like ArchJava to increase the quality / decrease implementation of their products.

Making Memories

2009-09-08T12:01:00.000-07:00

To answer Prof. Johnson's questions around Beautiful Architecture chapter 4, "Making Memories":

- What problems did this architecture solve?
There were a number of problems this architecture addressed. Probably the most pressing was the fact that each studio would be spread out across the US with a fallible network connection. The decision to burn each studio's sessions and send them to a central production site daily via DVD was probably one of the most important design decisions made to solve this problem. Other problems addressed were portability / configuration of the interfaces (solved with a novel form / property model), transfer / storage among the local facility (solved with a central server approach) and finally how to consistently render the images themselves (solved with a large rendering farm and an embedded transformation scheme).

- What standard solutions did it use?
In terms of design patterns, common solutions used involved the "Application Facade" to help abstract the domain model, the command pattern to help display form elements, and the chain of responsibility pattern to launch and initialize clients. Additionally, the common framework Spring was used as well.

- What architectural styles are used?
While I'm still not an expert at picking out architecture styles, I did notice the "hub and spoke" model mentioned in (what I think was) the Boxology paper. By this I mean the central local studio server with RAID storage used to hold the images produced by the local studio client machines.

5 is my favorite number

2009-09-02T19:29:00.000-07:00

I will admit that my first experience with higher-level architectural modeling, Tuesday's Boxology paper, left me with a poor taste in my mouth. However, the 4+1 View Model of Software Architecture paper cleaned that right out like a handy piece of Orbit gum.

While I was reading the paper, it was clear to me how this technique could certainly help an individual or a team improve the way they designed their system architecture. Instead of trying to break down a system into prescribed definitions, the 4+1 model instead recommends taking key elements of design (logical, development, process, and physical views) and creating models for each. I can say for certainty that following this technique could have improved some of my own software projects in the past. By asking a developer to evaluate each element, the process ensures that a developer does not unknowingly sacrifice good design in one portion of design to improve it in another. For instance, it's common practice to draw out the logical view by itself; however, a process view or development view could offer insight not afforded by the logical view. Because a developer deliberately evaluates each view in this approach a better (or at least more informed) architecture is sure to follow.

Designing towards a game

2009-09-02T19:12:00.000-07:00

While reading chapter 3 of Beautiful Architecture I tried to ponder the question posed to us by Prof. Johnson via e-mail: "in what way is this architecture aimed at games?" Prior to delving into this, I think it's important to specify that an MMO is a special subset of games with distinctly different needs than, say, a FPS. With that in mind let's continue...

The first thought I had was echoed by the authors a number of times - latency and saleability are king. When looking at an MMO, demand can be be excruciatingly high, with hundreds of thousands of users in the same environment at a time. Without allowing for a large number of users at a time, most MMOs simply will not satisfy customer demands. Thus, scalability becomes one of the primary quality attributes of the system. Similarly, if a game suffers from high latency, users will not enjoy their experience. Thus I see these two quality attributes as being chosen and executed on specifically because this architecture is designed for an MMO game.

The second thought I had on this topic deals with developers. It is very difficult to build up an parallel architecture such as Darkstar while at the same time deploying vast amounts of content. In an MMO, content is king, as scalability and latency as discussed above won't matter if there is nothing to do in the game. I'd argue that building this system with developers in mind, more specifically allowing developers to code without focusing on the intracacies of parallelism, is one of the major reasons why this architecture is specifically suited for MMO's. True, one may not be able to squeak out quite as much performance as they would if they had designed the system themselves, but the reduced development time should make the sacrifice worthwhile.

Don't classify me!

2009-08-31T20:21:00.000-07:00

Perhaps it was only me, but I had a bit of trouble trying to go through A Field Guide to Boxology. That being said, one of the statements of the paper stuck out to me: in the conclusion, the authors state that "architectural styles are becoming the lingua franca of architecture-level design, in the same way that design patterns are moving to center stage in establishing the vocabulary and defining the solution space for finer-grained design problems."

I can certainly appreciate the fact that the authors attempted to begin creation of a classification scheme for higher-level architectural patterns. However, the authors state that design patterns are applied to fine-grain problems, and I believe that because these architectural patterns are applied to much broader systems they are inherently weaker (or perhaps, less useful). To me it seems as if it'd be significantly more difficult to come up with patterns that apply to an entire architecture as a whole which remain applicable broadly. My gut feel was not reinforced by looking at the accompanying table, which really to me didn't do a great job conveying meaning. However, this course is my first experience to higher-level patterns, and I'm hoping that over the course of the semester I'm shown why my reaction to this paper is incorrect ;)

Quick-n-dirty versus thought-out-and-clean

2009-08-31T19:20:00.000-07:00

As I was reading chapter 2 of Beautiful Architecture I came to the realization that there are many different programs around my place of employment which seem to follow the "Messy Metropolis" model. It's easy to look down on these practices, and Lord knows I certainly have. In a perfect developer's world, every project should look like Design Town.

However, as I tend to play devil's advocate in just about everything I do (my friends can vouch for this), I thought about another software company I recently had the chance to learn about. Funded by a number of private investors, this other company had appeared to follow the methodologies behind Design Town to a "t," with what can only be described as a beautiful architecture. The problem? They had spent 10 years putting their platform in place, and had yet to turn all their hard work into a viable product.

As I tend to play devil's advocate in everything I do, I am forced to ponder - is there a break-even point in the design world when it comes to this sort of thing? That is to say, is there a point up to which Messy Metropolis is a better business plan than Design Town? At what point does Messy Metropolis cease to be worthwhile, and when does Design Town begin to become worth the extra time up front?

A curious quality attribute scenario

2009-08-31T18:49:00.000-07:00

My momma always told me, "Better late than never..."

One of the quality attribute scenarios that really stuck out to me in Software Architecture In Practice chapter 4 was the modifiability (yes, Firefox, apparently that IS a word) scenario. Many of the other scenarios seemed to be fairly cohesive; that is, the source, stimulus, measure and so forth were related actors. However, in the modifiability scenario, the following examples were given:

A developer who wants to change functionality
A systems administrator wants to modify some server settings

To me, these two items are pretty disparate. Item 1 is more along the lines of what I'd expect - the desire to have code which responds well to changes. Item 2 to me seems more like a usability attribute. Was I the only one perplexed by this scenario?

A question regarding stakeholders

2009-08-26T19:32:00.000-07:00

I'd like to pose my thoughts on some of our readings in the form of a question. In the first chapter of Beautiful Architecture, the authors go through a typical list of stakeholders who should help to address quality concerns and functionality. For the most part, the list was fairly intuitive, mentioning roles such as Funders, Developers (developers, developers!) and users. However, one role that was mentioned stuck out in my mind: Project Managers.

The text used to describe the Project Manager's input was that they needed to "organize teams and plan iterations." Certainly these are valid concerns in the development of software. However, with their inclusion here, the authors seemed to imply that these concerns should help drive the decisions made around the architecture of software. Did this strike anyone else as strange? In my mind, while this input is helpful, I don't see how these items should contribute to the architecture of the software. The teams assembled to perform development and the timelines applied should be put in place to help support the quality concerns of the product, not the other way around. Can anyone think of any applicable counter-examples to this train of thought?

Hello, world!

2009-08-26T19:24:00.000-07:00

Have I successfully posted my feed to the CS527 planet? Only time will tell!