Building distributed applications using Sinfonia

Authors: Marcos K. Aguilera, Christos Karamanolis, Arif Merchant, Mehul Shah, and Alistair Veitch

Paper: http://www.hpl.hp.com/techreports/2006/HPL-2006-147.pdf

So...this paper presents a system called Sinfonia that is designed to be intrastructure for building distributed systems. Sinfonia presents 3 features:

1. a global address space, sort of -- addresses are tuples of the form (node ID, address). Values can be read and written.
2. "minitransactions" -- minitransactions are transactions restricted to be short lived and consist of distinct read, compare, and write phases (in that order), and they may only manipulate values in the global address space
3. notifications -- a node may request to be notified when changes occur in the store in a particular range of addresses

I'm not clear enough on the distributed theory literature to be able to tell how interesting or novel their protocol is. I think it's uninteresting. More specifically, as most systems papers do, it describes the protocol in a rather ad-hoc manner that makes it difficult to get an overall feel for what is actually happening in the system. They spend a lot of time detailing a variant of two-phase commit wherein, oddly, the failure of a coordinator can be tolerated (i.e., the system won't block) but the failure of a participant can't. The rationale for this design decision is that the coordinator ends up being a client (i.e., application server) of the system, whereas the participants are actual Sinfonia nodes. It seems a bit odd to me that they designed a protocol that essentially tolerates no failures. This is supposedly not an issue given that Sinfonia nodes have hot-backups. Decisions within a minitransaction made by the primary are forwarded to the backup. I suppose I can buy this as a design decision if transactions are small and short-lived, but I don't really see why it's interesting.

Also, and as a side note, I'm always a bit dubious of the concept of backup servers. Are you really better off making a distinction between primary and backup servers as opposed to integrating all the servers you _would_ have employed as backups into the system itself? I.e., are you better off having n primaries and n backups instead of a system with 2n nodes? Seems like the latter would give you greater flexibility, in general, in allocating your resources. I suppose primary and backup are simply logical roles, and that any given physical server could play multiple roles at one time, but if you do that you might find yourself unintentionally compromising failure correlation assumptions (e.g., several of your logical backups live on a single physical machine that crashes, thus screwing you).

Anyway, moving on...the notifications don't seem that interesting except insofar as they interact with the minitransactions, except they don't really talk about this. As far as I can tell, the semantics of the notifications are very weak. If that's the case, would employing them in the same system as the mini-transactions undermine the supposedly strong semantics the mini-transactions are supposed to give you? I suppose if you treat notifications are purely advisory then you should be okay, but isn't that ultimately the same as interacting with a system that has the same weak semantics that you're trying to avoid?

Regardless, however, I suspect their system is very practical and works just fine. I just don't really see any new contribution here. The contribution would come in the form of easing application development and making ultimate end-systems more robust, but without a deployment in the real world to point to, that point is basically lost.

ORNL informal meeting notes (2)

Met with Ken Roche, physicist turned CS guy. Met him yesterday and wasn't diligent about taking notes immediately afterwards, so I'm sure I'll have forgotten things.

We had an interesting conversation I, sadly, didn't follow all of. The meeting reminded me how little math I actually know. Nonetheless, I could at least follow the system design aspects of what he was talking about. We spent some time talking about how in god's name you debug a program running on a hundreds-to-thousands of node supercomputer. They have some cute visualization tools that allow you to view the MPI wait times for each node in the cluster. Turns out that they saw, for instance, some outliers that limited the performance of the system. The results are actually the reverse of what one might naively expect: the outliers with very _low_ wait times are the ones holding up the pack (this immediately makes sense if you think about it: if there's an outlier with an exceptionally low wait time, everybody else may have been sitting there waiting on the slow poke who, of course, can immediately continue once he finishes with whatever he's doing). They suspect that the outlier may, in fact, be due to faulty hardware, particularly in the memory subsystem, which is interesting. I wouldn't expect that the memory interface for just one node could go bad, and specifically that it could go bad in a way that wouldn't crash the program. A little jarring.

Another interesting fact is that right now, although there are dual-core processors in Jaguar (they're hot rod supercomputer), the physical memory associated with the processor is strictly partitioned between the cores so as to preserve the programming model (I think...I was a little unclear on why they do this). Moreover, interrupts are handled only by the "master" core, so that for I/O, both cores may end up being blocked. This seems horribly inefficient given that the whole point of multi-core is fast communication between cores. They know this is inefficient. I'm not sure how they're going to fix it.

I think the issue is that they currently run this weird stripped-down, lean-and-mean OS known as Catamount (which amounts to Linux stripped of just about everything that makes it Linux) that doesn't have, for instance, virtual memory. I think this is what necessitates the strict partitioning.

Weird aside: there are apparently these physics guys at MIT (whose names I of course can't remember) that have designed their quantum mechanical simulators _from scratch_, _in assembly code_ in order to get every last ounce of performance out of the fuckers. That scares me. Those fuckers are crazy. Especially since they aren't even CS people. As Ken said, the computers were just an obstacle in the way of being able to get their physics results. I feel really, really dumb right about now...

Sequoia: Programming the Memory Hierarchy

Authors: Kayvon Fatahalian, Timothy J. Knight, Mike Houston, Mattan Erez, Daniel Reiter Horn, Larkhoon Leem, Ji Young Park, Manman Ren, Alex Aiken, William J. Dally, Pat Hanrahan

Paper: http://graphics.stanford.edu/papers/sequoia/sequoia_sc06.pdf

Sequoia is a compiler for parallel-processing machines. It is designed to be first and foremost portable between parallel machines with different memory hierarchies. This is not to say the language is arbitrarily general; a key assumption is that any Sequoia task is essentially recursively defined and that communication among nodes at the same level (and indeed between anything but a parent and its child) is explicitly forbidden. This allows the code to be customizable and portable.

An interesting feature that they don't spend much time talking about (I think because it's both implicity and not in and of itself very complicated) is the separation of the program logic from the specification of the machine. Basically, you embed parameters describing the size of memory chunks in your program, and then the compiler takes what amounts to a manifest describing your hardware and shoves in the relevant values. It's a cute idea.

Perhaps the way to do this kind of thing is specify different parts of the system in different places and then have something that synthesizes them at runtime depending on the conditions? Is that so vague as to be a totally useless question?

Compilation for Explicitly Managed Memory Hierarchies

Authors: Timothy J. Knight, Ji Young Park, Manman Ren, Mike Houston, Mattan Erez, Kayvon Fatahalian, Alex Aiken, William J. Dally, Pat Hanrahan

Paper: http://graphics.stanford.edu/papers/sequoia-compiler/sequoia_ppopp07.pdf

Cool little paper on optimizing IL code for parallel processors (ostensibly Cell). (As I read it, it became obvious I should have read the Sequoia paper first, but whatever). The interesting piece was the explicit modeling of memory as a tree. Consider, for instance, several processors each with their own local memory and then, say, a single shared main memory. The IL models operations based on this memory hierarchy, for example copying between memory layers, performing computation on a given layer, etc. It's not clear to me whether this does, in fact, model anything other than Cell (processor), but it's kind of a cool idea nonetheless.

I was less interested in the actual optimizations they did, which seem to give benefit to Sequoia programs, than I was in how they model their system (because I'm thinking about programming models for heterogeneous processing environments at the moment). They seem to do some fairly straightforward things like introducing dependencies to ensure orderings where needed, loop hoisting, copy elimination, etc.

ORNL informal meeting notes

Met with Olaf Storaasli, former NASA guy:

• got into FPGAs
• NASA likes 'em because they're more energy efficient
• if you do it right, you can get the whole chip active rather than just one part at a time as in microprocessors
• used on actual spacecraft
• btw, the way you deal with radiation is you reload the program twice a day...go figure.
  
• not clear how to program the buggers
• most work still done in VHDL
• some C-to-FPGA work done (I am skeptical of this approach)
• one guy did Matlab to FPGA (this seems a little cooler to me)
• new Crays ship with 2 FPGAs per processor

Privacy, Accuracy, and Consistency Too: A Holistic Solution to Contingency Table Release

Paper here: http://www.cs.princeton.edu/~satyen/papers/privacy.ps

I'll be honest: I saw a lot of greek symbols and ran away screaming, so I actually didn't get a whole lot out of this paper. This is doubly embarrassing as several authors are MSR-SVC-ers I know and love (Frank, Cynthia, Kunal).

Okay, so, the gist is that you want to release a "fuzzied" database with information about people in the form of "contingency tables," which are essentially histograms of various traits (think male vs. female, age ranges [20-29, 30-39, 40-49...], etc.). You want to maintain aggregate statistics about the data set without revealing information about particular people in the data set. The problem is that you want to maintain the accuracy of the data and keep it internally consistent in the process of making it private. This work focuses on keeping the data consistent.

The punchline is that instead of directly tweaking the data itself or the "marginals" (which they never define for us idiot-folk), they translate the data into the Fourier domain and tweak the data there. Turns out that has nice properties, though fuck me if I know even what that means or why it's true.

Supporting Ranking and Clustering as Generalized Order-By and Group-By

paper here: http://www-forward.cs.uiuc.edu/pubs/2007/clusterrank-sigmod07-lwlwc-mar07.pdf

I didn't get all the way through this paper...I'll admit it. But the idea here is to introduce an information retrieval-type operation into the standard SQL language. What the hell does that mean? Well, it seems to mean that they want to do some form of clustering. The example they give is realty. You'd like to look at a set of houses that are either lower-priced in the suburbs or higher-priced but with a nice view on the water. In this case, you want your query to return houses that fit into one of those clusters, and then you want to order houses within each cluster. So, they do it. And they are essentially running k-means with some weird little optimizations so that they don't have to materialize the entire database.

It was pointed out in the discussion that their semantics are weird and inexact. Which is to say: k-means is unstable, and it can give you different results running it multiple times on the same data. They take this instability and amplify it by doing what is essentially an approximation of k-means by creating centroids of (in some sense) adjacent tuples and then running k-means on the centroids. Problem is, I don't know how the approximation relates to the full k-means (which, again, has fuzzy semantics to begin with). So, I don't really know what guarantees I have on my results. Boo.