The Good Soldier LMeyerov

The fallacy of race to halt: power measurements from vectorizing webpage layout and binary search

2012-01-31T01:12:00.001-08:00

An important rule of optimization is that you don't know if it worked until you've measured it. Parallel algorithms research, until recently, has violated this rule. Researchers typically report speedup (old time / new time) or scaling (sequential time / parallel time), but that is wrong. The main reason we even care about parallel algorithms is that parallel hardware might provide more performance per Watt (PPW) if we use it properly. Otherwise, we should just turn up the clock rate and forget about it.

One of the most efficient forms of parallelism is SIMD, so I finally had a good opportunity to measure PPW vs. speedup for an algorithms paper we're finishing. For example, for our SIMD webpage layout algorithm performance (top picture), our 5x of speedup comes with an 8.5x PPW increase. Likewise, we sped up the binary search algorithm you learn in school by 15.8x and with a corresponding improvement on PPW of 13.1x. The biggest PPW wins were consistently from SIMD evaluation.

The surprise is that not all speedups improve PPW. We often assume work-efficient algorithms (parallel asymptotics do not dominate sequential ones) will, at worst, not impact PPW. Such "race to halt" reasoning is a good intuition, but even "intuitive" cases can break it. For example, take a closer look at our binary search results. Cache line blocking, a common high performance computing trick for better data prefetching, gives speedups for our binary search algorithm (both eager and optimistic speculative variants), but decreases PPW for the optimistic case. Measuring cache line blocking energy consumption clearly shows it hurts performance -- but based on speedup numbers and conventional wisdom, I wouldn't have bet that way.

Note to self

2012-01-24T22:51:00.001-08:00

Note to self: remember to include the phrase "We are 4.9x faster than FAST, the recent binary search algorithm ..." into the paper rewrite.

Natbib for LNCS / splncs.bst

2011-12-30T13:44:00.000-08:00

It took me awhile to find this, but if you want to use \citeauthor, \citet macros from natbib, etc. for Springer / LNCS papers, use this package. If you aren't using these macros, you should: it will avoid heartache from misspelling author names. If you are not mentioning author names, this may also help put you into the habit.

\documentclass{llncs}
\usepackage[numbers]{natbib}
\bibliographystyle{splncsnat}

Springer, please fix this!

FTL: Fast Tree Language for synthesizing a parallel layout engine

2011-12-25T14:59:00.000-08:00

A radial layout widget declaratively specified in FTL being used to visualize file directory structure. Achieves 22fps through quadcore layout and GPU rendering. Check out the HTML5 version and source code.

We finally submitted a paper about FTL, our language for specifying layout languages and synthesizing a parallel evaluator. The paper is dense, so we'd appreciate feedback on what to cut and what to expand :)

Our systems goes all the way from a high-level language specification to an optimized browser layout engine. We had to solve two basic problems:

Strongly scaling the parallel tree traversals. Our specification analysis will take a language specification, such as for CSS, and find a sequence of parallel tree traversals that will lay out any document (the tree) in that language. However, we couldn't find any existing algorithms that would give you a 2x speedup on 2 cores, 4x speedup on 4 cores, etc. We ended up A) finding a mix of existing data layout optimizations (pointer compression, blocking, etc.) and B) inventing our own runtime task scheduler (semi-static scheduling that simulates work stealing to precompute a partitioning). Scaling plummets if you drop either. More fun, due to the locality benefits of data layout optimizations, we achieve superlinear speedups -- 9.2.x on 8 cores!
Generating the right sequence of tree traversals. While our system will automatically find parallelism in a declarative specification, it won't find all. For example, specifying how a box lays out its children by using absolute coordinates creates a global dependency, but specifying them as coordinates relative to the box and then stitching them together to get the absolute ones will break the dependency enough for our analysis. Programmers can write queries about the set of schedules inferable from a specification to help debug this sort of problem.

We found reasoning about schedules to be such a helpful programming tool that we incorporated it into our specification language. For example, it's very convenient to make rendering calls within a specification, e.g., "box(self.x,self.y,self.w,self.h,self.color)". The specification must take care to say what order to render boxes, such as the foreground text being above the background. Z indices are ambiguous due to overlap and monadically passing around the dependency is really painful. We can take a lesson from the current informal CSS standard, which specifies the document traversal order and then locally defines order within each node. Our solution is to allow functional specifications (the grammar) to be refined with traversal order constraints ("do rendering in an inorder traversal"). We can also catch specification changes that violate such a constraint!

Synthesizing schedules yields extra benefits. When synthesizing an implementation that talks to legacy code, this has the added benefit of making it easy to avoid parallel calls into non-reentrant libraries. Furthermore, many different traversals will implement the same specification: our synthesizer can generate them and autotune over them.

I'm working with some great undergrads to move forward on several fronts. At MSR, I wrote a proof-of-concept manual implementation that uses SIMD instructions for further speedups within a core: we're now automating it as a new FTL backend. Next, Thibaud Hottelier is writing a visualization language based on bidirectional constraints that compiles to FTL, which our undergrads are using to write some stunning demos. I already wrote one to animate inspecting file sizes on your hard drive (see picture above): we get 22fps for animating 20,000 files, and we should handle bigger data sets once I fix some segfaults. [For reference -- the HTML5 version is 8fps and, on my phone, 1fps]. Finally, we're pushing FTL's expressive limits by formalizing the CSS standard in it. Fun times ahead!

What to Implement

2011-09-12T12:40:00.000-07:00

A big chunk of the coding side of my thesis is writing a declarative spec of CSS and then automatically generating a fast/correct/instrumentable/etc. implementation from it. However, how much do I really need to implement? More generally, if you're making a tool to compute over webpage style, how much do you really care about? E.g., if you make a proxy-based layout optimizer, which features are important? Full compliance, ACID tests, etc. are often an overkill.

To help pick a subset to focus on, I ran a bunch of popular pages through my parallel browser skeleton and counted dynamic occurrences of CSS attributes. For example, if a browser or user defined style property is that images inside paragraphs get a blue border ("p img { border: blue; }"), and a gallery has 2 such pictures, that counts as 2 hits on feature "border".

For many features, the options -- e.g., blue vs. red, 10" vs. 20% -- are easy to handle. For others, the cases are a big deal: e.g., a table ("display: table") vs. word-wrapping box ("display: block"). So, for some of the more common features, I also broke down the cases.

The diagrams below show first the features and then, for a couple, the cases. It might be interesting to also do a log plot (power law, anyone?). Basically, you can get legible (but wonky) looking sites without much. To get pixel perfect... not so much.

**Note: this isn't terribly scientific. The sample size is small and on popular, professionally engineered sites. Likewise, many of the features are 'default' features set by the browser, and may even correspond to doing nothing. For a bigger scale, also check out Opera's MAMA analysis.

Advanced, Submitted... Time for new things!

2011-07-25T01:25:00.000-07:00

I passed my quals, and Todd Mytkowicz and I just submitted a fun paper on using SIMD instructions where you shouldn't. Maybe now I can start doing research again..

Particularly fun in our submission is a 4x speedup on a canonically sequential algorithm as well as some more browser hardware acceleration tricks. Weirdest yet, in our approach, the clustering ratio of how well you can relate objects in a data parallel computation is inversely proportional to our expected vector etc. speedup! Somehow, it all makes sense.

Sadly, we couldn't do our 2 coolest algorithms: one for legal reasons, the other because the vector hardware I have is missing a permute instruction. So goes.

New Berkeley Prelim Syllabus

2011-04-25T22:21:00.001-07:00

I volunteered to help rethink the language design portion of the Berkeley prelim syllabus this week. Increasing the challenge is that we're cutting down from 60+ articles from before to only 36. We're shooting for about 6 core technical papers, and hoping there will be overlap with other areas (e.g., semantics, type theory, verification, optimization).

For my first pass, I've been thinking:

macros
continuations: on implementing prolog in functional programming
meta object protocol + messages: mirrors
type-directed programming: more types for nested data parallel programming

Any ideas for particulars or topic areas? For macros, I had been considering Shriram's swine before perl or Adapting Object-Oriented Frameworks to FRP. There are also some lightweight but useful papers, such as Hoare's Hints on Programming-Language Design. I couldn't think of anything sufficiently motivated for laziness (e.g., stream processing is pretty weak and equational reasoning is iffy).

Fun exercise :)

I'll try to post soon about some of the fun PL design / analysis / optimization work I've been doing. We just finished a camera ready for a workshop but I won't be writing up any of my bigger papers (SIMD tree layouts, multicore scheduling, CSS semantics / layout engine synthesis, and adoption-oriented languages) until later this year. Need to kickstart the writing process :)

Topological Sort in Datalog

2011-04-02T18:38:00.000-07:00

As a neat trick, I've been spending the weekend rewriting our hundrends (thousands?) of lines of attribute grammar visit scheduling from Java to maybe 100 lines of Datalog. This isn't so much of a surprise: there's been a bunch of work showing how to declaratively describe program analyses with datalog (and optimally optimize it with BDDs, though those results are, unfortunately, more contentious).

Anyways, the core of an attribute grammar scheduler is a topological sort of dependencies. I found this difficult to write. Originally, I tried using a successor relation, where each step was the set of edges (or nodes) that are reachable from the previous. No go, and searching on the web, I didn't see anything else. So, here's another tact:

Given the data:

edge('aa', 'b').

edge('a', 'b').
edge('b', 'c').
edge('c', 'd').

edge('d', 'y').
edge('d', 'z').

edge('a', 'm').
edge('m', 'n').
edge('n', 'o').

edge('o', 'y').
edge('o', 'z').

node(?n) :- edge(?n, ?m).
node(?n) :- edge(?m, ?n).

We calculate the flows-to relation, and then, for each edge, propagate 1 + the label of the previous edge. Finally, we take the maximal incoming label for each node, and voila!

flows(?n, ?m) :- edge(?n, ?m).
flows(?n, ?m) :- flows(?n, ?x), flows(?x, ?m).
whenAll(?n, 0) :- node(?n), !edge(?m, ?n).
whenAll(?n, ?c) :- whenAll(?m, ?d), flows(?m, ?n), ?d + 1 = ?c.
when(?n, ?c) :- whenAll(?n, ?c), ?c + 1 = ?d, !whenAll(?n, ?d).

Testing the result:

?- when(?n, ?c).
Query: ?- when(?n, ?c). ==>> 10 rows in 0ms
Variables: ?n, ?c
('aa', 0)
('a', 0)
('b', 1)
('m', 1)
('c', 2)
('n', 2)
('d', 3)
('o', 3)
('y', 4)
('z', 4)

SIMTask parallelism and ConLangs

2011-01-27T22:10:00.000-08:00

Thought I'd post about two interesting things I've been looking at recently: running task parallel code using SIMD instructions and artificial human languages.

SIMTask Parallelism
First, while trying to make CSS layout engines ridiculously fast through hardware-oriented optimizations, I had the basic question: well, if it has multicore-friendly parallelism, why not SIMD-friendly parallelism? I wasn't sure how practical the question was, but as an academic experiment, it's a very interesting one about the nature of parallelism in 'real' hard-to-parallelize software (as opposed to, say, rendering and dense matrices). Looking at our task parallel formulation of CSS layout, we can say it's a combination of two patterns: a task-parallel decomposition roughly following the HTML tree, and a visitor pattern for dispatching different tasks based on the type of each tree node (paragraph, link, etc.). How do we use SIMD instructions for that?

Often, for SIMD instructions, we want something like basic reductions (e.g., scan operations): taking the sum of a list, max of a list. We don't see that a lot in webpages: you'll sum up the children in a node, but then do a lot of computation within the node (margin, padding, border, etc.). Even better for SIMD instructions are maps: add 10 to each width, divide every height by 3, etc. That sounds more close to what we want... except the visitor pattern thing: the data being computed on with the same instructions needs to be adjacent, but, unfortunately, if we look at the tree, different functions are being run on adjacent nodes!

Enter SIMTask parallelism. We can do some data mining on the tree to rearrange it in memory so that the same type of node is next to others of the same type. For example, we can collapse the webpage into a prefix tree and use that to have a different layout in memory: now the same types of nodes are next to each other physically. Because of the task parallelism (with some minor compiler trickery), we can actually run the code in this same rearranged order! For example, in a shopping cart, where each shopping cart item is a complicated subtree, but the subtrees are the same across items (just changing what picture, what text, etc.), all of the link nodes will be next to each other in memory, as will text, as will paragraph formatting, etc. SIMD instructions can be then used!

Anyways, we just submitted a fun vision paper about this. If you take a step back, what we're really saying is that task parallel code often isn't just good for multicores: with smarter frameworks and compilers, we can hope for exploiting some regularity in the task structure to get better memory effects (e.g., from flattening) and even potentially scale down the parallelism to use SIMD evaluation (including better branch prediction)! This is a big departure from current lightweight task parallel frameworks like Cilk/TBB, that, outside of some stack representation trickery, are really about lightweight runtimes and not heavy yet powerful code transformations.

Finally, if you're familiar with modern GPU architecture, this may sound familiar. Modern GPUs use something called a SIMThread model, which is somewhere between vector and threaded ones. Threads get bundled, and for the convergent threads in a bundle (i.e., branching the same way), you get parallel/vector execution. SIMThread = Same Instruction, Multiple Threads. SIMTasks are like that, but more software managed: SIMTasks are to SIMThreads as threads are to SIMThreads. Likewise, vectors < SIMThreads < threads, and reductions/scans < SIMTasks < tasks. Doing SIMTasks introduces a pretty interesting world of optimization; I did some neat tricks with memory layouts and even found opportunities for memoization across SIMTasks that you wouldn't get in normal tasks (in CSS, at least). If you haven't picked up on it now, SIMTask = Same Instruction, Multiple Tasks.

Should be able to put the paper out in a couple months either way. I'd like to report on the full results of the CSS side of things, but we didn't really fit that into this writeup and am not sure when we can (a bit more work to do, can use more automation, and deserves its own writeup -- maybe if we fit it into the Berkeley browser we'll be able to). Story of my life :)

ConLangs: Constructed Languages
A little more fun, I was browsing a bookstore and found a book about the rise of inventing languages: In the Land of Invented Languages. However, with maybe one exception, these weren't about languages for instructing computers: these are about languages for communicating between humans. We all know Esparanto and Klingon, and maybe even Hildegard's and Tolkein's (Tolkein made the elves' language, including their derivation, before the books!), but there have been symbol languages adopted for the deaf, and, even earlier, language invention was almost a gentleman's pursuit.

One was particularly fun: Laadan, a language from a woman's perspective. It stole a bit from Navajo, but apparently also has some novelties predicting some modern security and HCI research: for the grammar, terms are affixed both with emotion and source of authority!

I was really interested in the book as part of my "socio-PLT" kick (sociological approach to programming language theory): how is adopting Klingon or Logjam different from adopting brainfuck or Haskell?

Last class!

2010-12-01T22:09:00.000-08:00

I believe this will be my last class at Berkeley: Social and Organizational Issues of Information. Should be fun -- the main impetus being my questions about programming language adoption, but even that has been broadening recently.

In that spirit, a fun NY Times book review on 70's French sociology explaining hipsters, tastes, and, I posit, programming language popularity. It's on my To-Read list for as soon as I can track it down.

Proxies gaining traction... objects considered harmful?

2010-11-29T00:29:00.001-08:00

I saw that Brendan has started promoting proxies in his talks. Now that Mozilla's JS engine has a proxy primitive (essentially objects that support full overriding of meta object protocol interactions), Brendan stated that Firefox 4 code is apparently shifting to use them for securely connecting browser JS code In a security context, you need (1) a recursive pattern ("membranes") with double-sided protection but also (2) some way of securely injecting your policies into the wrappers (e.g.,for a whitelist, to prevent the whitelist object from leaking out and being hijacked). While Adrienne and I mostly focused on the web application scenario in our Object Views paper about extending a library that does (1) to also do (2), it equally applies to a browser security kernel employing the pattern. Indeed, one of our ultimate goals was for browser extensions!

There's also a fun implementation tidbit that popped out. Andreas implemented proxies using an indirection table similar to that for the 'becomes' operator in Smalltalk. For our approach to incorporating policies into wrappers in both a succinct and safe way, we used aspects as the interface. I previously showed 'becomes' and (ocap-style) aspects are the same thing. While not much is known in popular communities about 'becomes', aspects are fairly close to the ability to import antigravity. As noted on Brendan's blog, a world of known language abstractions are now possible for these objects: perhaps using regular objects should be considered harmful?

Finally, as I'm now apparently a performance person -- it would be interesting to compare the efficiency of Ben Lerner's JS aspect implementation for Spur (a tracing JS VM from MSR) to Gal's proxys. I'm still curious, especially once one takes tracing optimizations into account and typical boundary crossing rates, which is more efficient. As promoted in Joel's 2010 Usenix paper, objects should be closely associated with origins (i.e., taint field), and, as suggested in our W2SP paper, I'm particularly curious about creating origin-indexed views: putting 1 + 1 together, can we get dynamic security primitives for multiprincipal programming at no runtime overhead (modulo policy logic)?

Anyways, I've been mostly quiet about my work recently: I've stumbled upon a couple of big algorithm and related programming model results at MSR this fall so, once able, I'm looking forward to describing them. I'm starting again with the socio-PLT stuff so we'll see where that goes as well. Back in Berkeley in January; the next couple of months will be busy!

1/3rd solved

2010-09-28T22:54:00.000-07:00

The theory behind an LL(k) version of worst-case expressive typical-case efficient parsing is easy... almost a restatement of how to do LL(k):

The proper way to state this might be an interesting form of abstract interpretation, but, in that case, my arrows are upside down.

Now to earn the bacon by replacing the LLker boxes with LRker ones. Way better than proposal writing and apartment hunting. Tomorrow will be my last Philz coffee for a long time -- hello Seattle!

Affinity Matters

2010-09-23T14:45:00.000-07:00

Took me awhile to find this, but to pin the current thread to some core on Linux 2.6+ kernels:

cpu_set_t mask;
CPU_ZERO(&mask);
CPU_SET( SOME_CORE_INT, &mask);
int error = sched_setaffinity(0, sizeof mask, &mask);

Using this significantly improved the scaling of my multicore tree visitors. I still haven't found a good way to do it on OS X systems, which only seems to support affinity across units with distinct L2 caches.

I believe it's more general than pinning in that it could be used for affinity by setting multiple potential cores. Tuning for hyperthreads is iffy in that I believe the hardware context -> logical cpu mapping is unreliable (e.g., no guarantee the HTs are contiguously named).

Edit: also, all you need to do is link in -lpthread and include "pthread.h" ; no more funny business.

Back from San Diego

2010-09-08T20:40:00.001-07:00

Seth and I invented an awesome new multicore+simd parsing algorithm on the flight back. Sweet.

One scalable memory allocator later...

2010-09-06T01:38:00.000-07:00

... and we now have great utilization on a quadcore. Colors represent sequential workload times in milliseconds: we're trying to speed up a bunch of tiny passes.

The first two dips occur at socket jumps, the second dip worsens due to Amdahl's law (a buggy work partitioner), and from there the performance soon peaks before burning out.

An interesting challenge I don't see often discussed is that I'm benchmarking the solving time and I needed to pull quite a few tricks to warm up before then (time isn't included here). Some time before a pass actually starts, e.g., near the end of the previous pass, the final implementation should actually start warming it up. That's a tuning nightmare! However, more fun, I want to first experiment with tree SIMDization.

Parallel Attribute Grammars / Tree Stencil / Visitors

2010-08-27T00:59:00.000-07:00

Got my first parallelism results for the tree solving part of my work. When computing on a (task parallel) tree, if the tree is big or the the computations per node is large, parallelization is easy: just traverse and work steal (e.g, Intel's TBB or Cilk). However, we often have small calculations, such as computing a (tree) sum. Furthermore, we also want to do many macroscopic (tree-wide) optimizations like changing its layout for better memory access patterns. I spent most of the summer doing macroscopic sequential optimizations for my tree language but now also have finally achieved parallel speedups for a minimal CSS-like layout language (vertical boxes, horizontal boxes, and colors). It is a *very* minimal language, meaning a lightweight computation (4 tree traversals, each less than 1ms), so speedups are non-trivial. However, by having very lightweight traversals, adding additional passes now has less of a sting (giving leeway to both the flexibility of CSS and the quality of our attribute grammar -> tree stencil compiler).

4-pass grammar speedup (where one of the passes is followed by parallel font handling code, but not counted). Overheads of creating and destroying pthreads are not counted (later step will be to do standard pooling and warmup tricks).

An Undercited Paper

2010-08-02T17:16:00.000-07:00

Note: this is a rewrite of the original posting as the blogger interface confused me into thinking the edit an article button was just a comment button.

"NESL": Seminal work on data parallelism that handles regular structures like matrices very well. However, super common structures like trees, graphs, etc. are supported only in hard-to-read encoding or overly restricted (e.g., fixed depth) legible ones. Front page of google scholar: ~600 citations.

"Flattening Trees": shows that recursive types -- such as trees -- are no big deal to add at the interface level and that the flattening transformation can be modified to support them. ~22 citations and what seems like the real first step towards making flattening acceptable for general purpose languages. "More types for nested data parallel programming" finishes the job. (Nit: conflating nested data parallel with flattening is bad; these papers are really about the latter which is just *one* approach to the former).

Bonus read: "Inductive Graphs and Functional Graph Algorithms" shows how to (sequentially) support graphs. It's interesting in that 1) graph specialization is restricted to an ADT that could be optimized external to the language and 2) similarly, I suspect nested data parallelism can be reasonably achieved as library with it. At least for the near future, having the work be at the library level is a big deal: API changes are more forgiving.

Towards taming the web

2010-07-20T01:37:00.000-07:00

Happy to see resource blocking got slashdotted. Still far away from our default-deny vision @ W2SP, let alone what Ben wrote about with mutation event transforms and followed up on in our Oakland paper, but having the spotlight there helps force the issue.

Been in heads-down mode all summer experimenting on a new high-performance computing inspired language runtime; hopefully be able to say something interesting about that soon. Next few weeks should be fun: ~2 weeks in RI (+MA/NY?), a few days in the Maryland/DC area, a few more in Seattle+Redmond, and finally either Vancouver (CA) or Costa Rica. Assuming some experiments turn out well this week, that means I should have some downtime to hack on the language prediction stuff again!

Insprirational paper

2010-06-23T18:31:00.001-07:00

Sometimes (often?), I feel like there's a doubling distance on inspirational papers: the more you read, the less you get surprised. I've been increasingly disappointed in PL papers: while this is often due to a topic I'm not personally interested in (e.g., shape analysis), it is more often due to an incremental area (symbolic execution, dependent types, etc.) where the leaps are for practitioners in the field and don't open new doors or general perspectives for those not in the area.

So... I was very happy to stumble upon 'Accelerating and Adapting Precomputation Threads for Efficient Prefetching', which seems to be the current extent of a fascinating line of work.

Most general software has rampant L1/L2 cache misses. For example, while profiling WebKit (Google Chrome, Safari), 10% of the instructions in layout missed the L1 and required an L2 fetch: such occurrences have a ~10x penalty, meaning about 50% of the time would be spent doing nothing but waiting for data to transfer from L2 to L1/registers. Similarly, despite a large L2 cache on the test machine, 0.2% instructions missed the L2 cache, meaning 15% of the time was spent getting that data. That's a problem: most of webpage layout time, therefore, is spent moving data around and not actually computing anything.

Enter prefetching. It is a form of memory parallelism that mixes communication with computation: tell the computer to fetch data before you need it, so by the time you're ready to compute on it, it's there. Hardware prefetching does this automatically. When the computer is told to fetch one chunk of data, it'll also start grabbing ones that are next to it: so, if you're traversing an array linearly laid out in memory, when you finish with the first chunk and ask for the next, it'll already be there so you can start working on it immediately, and meanwhile the next chunk will be fetched for you, etc. Unfortunately, most general programs don't have regularly laid out data (e.g., they use trees instead of just arrays). One fix is software prefetching -- special commands to asynchronously load data at a specified location -- but that's often hard to use. For example, if you're traversing a tree, you'll want to prefetch a few nodes ahead -- but you'll only know the direct children! Prefetching is often too much of a pain for serious consideration, especially once you factor in software engineering concerns like code legibility and robustness.

This paper makes an interesting proposition: what if, on a concurrent hardware context, we simply start traversing the tree ahead of time, but don't do any actual work? Let's assume a fetch of a node takes the same time as the amount of work (arithmetic instructions etc.) on the node:

Time 0: computer does nothing, prefetcher requests node A, worker does nothing
Time 1: computer brings A, prefetcher requests node B, worker computes on A
Time 2: computer brings B, prefetcher requests node C, worker computes on B
...

Unfortunately, there are a lot of little details like what to do if the prefetcher gets ahead of the worker -- the cache is only so big, so this might actually cause problems! Similarly, if there isn't much work per fetch, the prefetcher will get behind schedule: software prefetching, if possible, is still useful as it generally supports multiple prefetches around the same time. The described paper focuses on automatic dynamic optimizations on hot traces with a prefetcher on a SMT core: they use a framework that records code that runs, and when it realizes a bunch repeats but with different data, takes action. This is really good for sequential loops over regular structures, such as iterating over a list with two alternating types of nodes), where they perform compiler analyses to achieve software prefetching, and, as long as computation time >= fetch time per datum, their worst case still eliminates fetch time.

There's a lot more to do: the idea is general (touch what you need ahead of time in a general concurrent thread) but their actual algorithm is very specialized. Browsers are beyond their obvious worst case. First, the worst case: the data structure is an unpredictable tree with computation time close to fetch time, so their compiler optimizations won't really work and their prefetcher will likely get behind schedule. The less obvious and really concerning part is that they assume you have a free SMT hardware context (waiting for a prefetch blocks the SMT hardware context from other use): we can perform our traversal in parallel and thus, in their approach, forced to choose between task parallelism (parallel traversal) and memory parallelism (concurrent prefetching)!

Like I wrote in the beginning: this paper is not just useful for a particular examined case but also inspirational. It opens doors. E.g., while I can't use their prefetching optimizations to keep the prefetcher from getting behind, I can likely use 'jump pointers' to point further ahead in a tree for a given node and then sleep, preventing blocking on the SMT thread. Similarly, task parallelism, typically using work-stealing, tries to use disjoint memory to prevent interference between tasks, but this suggests I might be better off interleaving traversals.

Anyways, fun stuff.

valgrind, kcachegrind for os 10.6

2010-06-13T21:28:00.000-07:00

In case any mac devs haven't noticed:

#use valgrind once 10.6 support is in the main branch
sudo port install valgrind-devel
sudo port install kcachegrind
sudo port install graphviz

The kcachegrind port seems a bit wonky -- I've had to run it with elevated privileges ('sudo kcachegrind ').

Life just got better. Still waiting for a VTune etc. port for OS X; multicore (esp. TBB) profiling is still too hard.

p(category | language)

2010-05-27T22:47:00.000-07:00

I've been data mining ~10 years of projects from sourceforge for awhile now to try to understand how languages spread and factors in people adopting them... It's been tricky, but I found the following charts pretty interesting:

(probability of the category for a project given the language)

(1: given a project with N developers, likelihood of being in a particular language, 2: likelihood of a project having N developers in language L)

(log number of developers with N projects)

(increasing use of a language for different tasks over 10 years -- 1: Java, 2: Python)

Next step: correlating factors to explain this stuff.

... and Oakland/W2SP are over

2010-05-20T22:04:00.000-07:00

Feel like I've been reading security papers long enough now that mind-blowing work is more rare. However, "Towards Static Flow-Based Declassification for Legacy and Untrusted Programs" felt like a good step forward and "Side-Channel Leaks in Web Applications: a Reality Today, a Challenge Tomorrow" seemed like it should have gotten some sort of award. New to me were the handling malicious hardware design (e.g., backdoor) talks, for which I still don't understand the threat model. I liked the solutions, but, for example, I wasn't sure why some couldn't have been recast as static verification problems pre-fab (at least one seemed well-suited for static verification instead of making new hardware to help check the hardware).

Our ConScript talk went smoothly (never spoke to such a large audience before, pretty intimidating, especially when it's the finger-jabbing security crowd!). Not much to report there -- some press, some emails after, and some people describing the talk to me later but not realizing I was the one who gave it ;-)

Today was W2SP and probably my favorite part of the whole thing. Gustav Rydstedt gave a hilarious (but scary) account of framebusting: not enough people do it and those that attempt it do it wrong. I didn't entirely buy the solution (e.g., it depends upon CSS-conformant browsers, which is questionable in mobile), but, then again, I'm a first principles guy, and that doesn't really work on the deployed web, while Gustav's solution does the important thing of taking care of most desktop users. Steve Hanna gave a cool account of attacks on postMessage usage (not sure I'm ready to call JS stored in a DB a problem, which accounted for the 2nd half of his talk). I wish his talk was a little longer because in his paper he started to talk about the principles behind his API fix suggestions. Brendan Meeder's talk was also interesting, particularly in how it exposed the basic problem that we don't know how important privacy attacks against basic social interactions despite them being fairly pervasive. Probably annoying for Brendan's otherwise intersting talk, this came up through tearing apart his evaluation criteria, but I don't think people appreciate the difficulty of this step.

Perhaps the most interesting talk was the keynote where Jermiah Grossman essentially provided empirical evidence that the web security model is broken on a mass scale. On the plus side, this means that all the automatic web bug finding guys should have great results for the next few years.

Our talk seemed to be amiably received. It and a CSP-like plea were the only concrete let's-do-it-right-from-the-bottom proposals and Terri Oda had something pretty in sync with Adobe's approach to languages (don't assume the developer is a coder). Unfortunately, modulo the above exceptions and a few others, I felt the overall week was woefully short on correct-by-constructions solutions and instead focused on band aids (though this is understandable for a security as opposed to SE or languages conference). This wasn't lost on others either -- the discussion at the end of W2SP essentially asked the same thing, should we have more of a focus on finding the 'right' solution or keep on keeping on?

Still piled under for the next ~5 days. Have a backlog of fascinating emails I still can't get to replying to and some code that I still don't have time to write :( May, you're such a strange beast.

Great OSQ

2010-05-16T08:41:00.000-07:00

Back from OSQ (Santa Cruz is a Good Thing) so now crunching on a term project, Oakland/W2SP talks, the parlab demo, and finding a place to live. Odd how not sleeping outside is fairly low on the list of priorities.

Perhaps the most interesting talks were Neil's and Peter's on the BOOM project where they've been experimenting with modal extensions to Datalog (time and/or location) as means to compiling declarative programs into distributed ones. A big motivation has been their work on declarative networking, applied to tasks like synthesizing CHORD, and their current work seems to be in a similar vein -- they can synthesize and potentially verify tricky protocols. It'll be interesting to see how this transitions from framework/protocol building to their goal of general application building. Another project briefly presented was Thorn (OOPSLA09, POPL2010) which takes a similar scripting position but trades in the declarative core for actors and gradual typing -- I've been more on this side for awhile (dealing with stratification etc. at a low-level is odd), but as observed in BOOM, I think we need a bit more abstraction help in handling modality. An interesting example of such an extension is Swarm's ability to move a thread of control to a particular location (e.g., the data's).

Much of the rest of the retreat was the usual symbolic execution for concurrency and security checking stuff (where are the correct-by-design people??). It was interesting to see Prateek et al take what Raluca and I had been hacking on a couple of years ago and take it to the next level, they seem to be getting a lot of traction! They were hit by the same event explosion problem so might be worth integrating our solution in, and the problem I've been most worried about -- server interactions -- still seems to be open. Prateek avoided it by scaling down the problem (client interactions) and assuming cooperation with the server (known login, stateless server or known reset, ...).

There was a lot of grumbling about impact and fundamental process from the verification crowd so I gave a short talk on sociology. It was about using insights from 'diffusion of innovation' studies to examine the social process of applying verification (my particular interest is in doing this for PLs, but that's for another day). Unfortunately, it was partially misunderstood by some: making our research tools popularly used is nice, but not what I was advocating, and I even agree with the seemingly contrarian position that research adoption shouldn't be an academic's focus. However, the sociology community has essentially given us criteria for what it means to be a socially acceptable innovation: I'm not advocating focusing research effort on deployment but deployability. What is an appropriate verification process? We might be making bad assumptions about what people can and cannot do and thus not only running the verification race one-legged but potentially may even be in the wrong race.

Back from WWW and the significance of social network research

2010-05-01T23:53:00.000-07:00

Came back from my first WWW conference. Given its broad scope, I wasn't sure of what to expect. Below are some notes on the good, the bad, and a bit of an insight I've had about all the social network research going on.

First, the good. As a researcher, often better than seeing a new solution is a new problem.

Gregory Conti talked about "Malicious Interface Design: Exploiting the User" -- how advertisers and complicit content providers work against users. Is there a social, economic, or technical defense against marketing? I don't even know where to begin, but at least awareness is rising.

Azarias Reda presented his work on "Distributing Private Data in Challenged Network Environments". Privacy seemed to be more about emphasizing the problem -- his talk was really about deploying an SMS-based interface for prefetching in (African) internet kiosks that have very limited bandwidth and thus can't handle synchronous (same browsing session) content requests.

I've been talking to people about poor connectivity for a couple of years now (... my housemate actively works in asynchronous long-range wireless etc.). My basic thought is that it's a multi-tiered problem. E.g., the poor bandwidth kiosk model doesn't seem architecturally challenged for most content: aggressive caching should eliminate most transfer (and most common threat models), and new data isn't that heavy. A bigger issue is how to do so given developers don't really follow pedagogy (don't separate or label cacheable content) and, in many regions, there is no or only occasional connectivity (think cell phones). I'd love to work on making an asynchronous and occasionally connected web -- imagine having a village-local cache of the entire web that gets updated whenever somebody drives through the town yet still supports AJAX through optimistic/predicative interfaces. So little time :(

Second, the bad. Given the shift to the web from desktops for modern applications, WWW is a sensible focal point for research in browser and web app software. Browser security was fairly well represented and of good quality (... and I generally found these talks to be the more rigorous ones in their sessions) -- WWW seems to be a strong home for them. Given the optimization challenges in browsers and the ubiquity of mobile but slow hardware, I wish there was a bigger emphasis on performance issues (Zhu Bin gave a good talk about incremental/cached computation across pages, was good to see someone do it -- looking forward to reading about the details). Finally, language and framework driven approaches were barely on the radar: OOPSLA, ICSE, CHI, OSDI etc. seem to suck in much of the talent in this space.

Overall, while search, semantic web and now social nets seem to be strong points for WWW, basic client & application systems are on a slippery slope. Security seems to be teetering on -- NDSS is becoming more webby, so it'll be interesting to see how that plays out for the non-Oakland/CCS/Usenix papers. There were a few points when there just weren't any technical papers about improving general web apps, whether in the application, protocol, or browser layer, which was surprising and should be easy to fix. There's also a new Usenix Web Apps conference.. becoming less and less clear what the appropriate venues are.

Finally, what's the deal with social network research? One data mining researcher I talked to simply dubbed it the next trendy thing (the previous being search). I disagree. At face value, I'm not particularly interested in extracting particular facts from the Facebook or Flickr social graph. That is almost just recasting the idea of "WebDB".

An insight comes from the reason we're seeing a lot of incremental papers, namely, that social network data is available (we can redub most of the research as "social network research of online communities"). I've been reading "Diffusion of Innovation", a high-level book surveying research in field named in the title, and its historical descriptions make the significance of this proliferation clear. The studies outlined in the book were hard to do as they required researchers to do arduous tasks like interview hundreds of farmers about they did or did not adopt some new strain of miracle crop, find out their circle of acquaintances, and only then begin statistical analysis. Now, you can just download it all. For example, my spider just finished downloading records about 250,000 users and their interactions on some website over a span of 10 years -- for a course project! The iterative scientific process has just been accelerated in a big way.

The point is that I think the field of sociology itself is undergoing a revolution. The 20th century provided a mathematical foundation (information theory, bayesian statistics, etc.) and the 21st century is bringing the data. It's already obvious with cognitive science -- the availability of statistical models and now data samples means 'soft' science is becoming a misnomer.

Off to North Carolina (WWW2010) and Boston/Providence

2010-04-26T23:50:00.000-07:00

Ras and I mostly ironed out our talk on mechanizing and parallelizing/optimizing CSS engines for browsers and our other talk on secure mashup abstractions and mechanisms is settling. Not sure who else will be at WWW2010, but worst-case scenario I foresee excessive sweet tea, historical linguistics analysis, and layout engine hacking as a reprieve from all this powerpoint and latex nonsense.

No significantly cool new results lately due to all this slide making. Working with Adam, who we're doing automatic incrementalization of CSS with, I realized that I can encode tables and floats in a fairly restricted attribute grammar language, so that was quite a relief. Quals proposal, here I come!