Practical Abstractions for Dynamic and Parallel Software. Umut A. Acar talk.

Dynamic Part

Part of the focus is that as data changes, some computation on that data changes slowly over time, he discusses using a dynamic approach which does not recompute from scratch

Can make an intractable problem tractable, example in dynamic points forming convex hulls goes from years to seconds

Says dynamic algorithms designed for particular problems generally lags 10 years after static

Domains that allow dynamic algorithms are stable, which means that similar inputs yield similar computations (in terms of actual execution)

Idea is to represent execution as data structures that change over time

Idea is based on combination of computational models of Turing and Church, a tree that records all the processing performed

Idea is that it can be figured out what change in input causes changes in what parts of the execution tree, and only the modified part needs to be recomputed

Running time is proportional to the stability of the problem, how much execution is shared

Get two orders of magnitude saving in some cases

Run [specially annotated, and specially restructured] code through a special compiler that produces a self-adjusting executable

Because the computation is so fast (orders of magnitude), it has allowed for the solving of some open problems:

live computation of convex hulls in higher dimensions on dynamic data

Dynamic meshing: triangulate a dynamically changing 3d mesh s.t. no triangle has small angles (because small angles cause floating pt instability). Here the result is close to optimal (not manipluation of a shape, but deletion and random rea-dding of pts)

Probabilistic inference

Most of these results just leverage an existing result, figuring out that its stable, and then making it dynamic

Parallelism Part

Basic point is that the overhead involved in parallelizing code is actually significant, finding the tradeoff where parallelization actually pays off is called the Granularity-Control Problem

Have some methods that try to resolve the issue, speedups are significant, but not linear in number of additional cores

Dynamic Parallel

Dynamic and parallel issues are “duals” of the same problem

Can get the benefit of both by programming for just one

Looking at doing Map-Reduce by this method, needed to make it stable with a small change, then implemented it in Hadoop

Results for Hadoop just makes it faster, no end used changes needed.