lmeyerov at eecs dot berkeley dot edu
Par Lab | Soda Hall
Par Lab | Soda Hall
I work with Ras Bodik in the Par Lab on designing a parallel web browser and new programming languages. Previously, I was a member of Brown PLT with Shriram Krishnamurthi. I have also worked at a startup, Microsoft Research, Macromedia, Adobe's Advanced Technology Labs, and WBRU, a commercial radio station.
Most recently, I have been specifying and parallelizing CSS, designing clustered data parallel algorithms, and analyzing sociological principles of programming language adoption. For the first few years of graduate school, I worked on scriptable security policies for JavaScript applications, program analysis and meta-programming over AJAX applications, and simple application scripting.
The following languages are indicative of my vision for a better web:
Visual layout languages are important for running web browsers on mobile devices, but they are difficult to design, implement, and optimize. Our solution is the Fast Tree Language (FTL) layout engine generator. Given an attribute grammar defining the language's semantics and layout instances to profile, FTL outputs the first strongly scaling parallel layout engine.
Parallelizing the small tree traversals that characterize layout solving is challenging. We show how to combine existing techniques, and where needed, present new ones. First, to assist designing parallelizable specifications, we introduce a declarative query and constraint language over grammar evaluator schedules. Next, to help find the fastest evaluator schedule, we present how to synthesize a variety of attribute grammar evaluation orders. Third, as memory bottlenecks prevent scaling, FTL autotunes over data layout optimizations. Finally, for balanced, locality-aware, and low-overhead scheduling, FTL partitions the document tree among cores using a novel semi-static approximation of work stealing.
We measure strong scaling within 4% of ideal on a single-socket quad-core device, and, including data layout optimization, total speedup of 5.2x. On 2 sockets, total speedup is 9.3x and within 14% of the ideal.
Many data layout optimizations cluster data accesses and memory into high-locality groups in order to optimize for the memory hierarchy. In this paper, we demonstrate that similar clustering program transformations enable efficient vectorization. We call this approach clustered data parallelism (CDP). CDP enables fast and power-efficient parallelism by partitioning a data structure into clusters such that SIMD evaluation is efficient within a cluster.
We describe the CDP latent in three common computational patterns: map, reduce, and graph traversals. Demonstrating the benefits of CDP, we present case studies of instantiating the CDP patterns in order to design fast and power-efficient binary search and webpage layout algorithms. First, we increase binary search SIMD scalability by using CDP to expose speculative parallelism. Second, we achieve the first SIMD webpage layout algorithm by using CDP to eliminate heavy branching.
We report strong performance improvements. Targeting AVX, we see a 5.5X speedup and 6.9X performance/Watt increase over FAST, the previously fastest SIMD binary search algorithm. Running webpage layout with SSE4.2 instructions, we observe a 3.5X speedup and 3.6X performance/Watt increase over an already optimized baseline.
The adoption of data parallel primitives to increase multicore utilization presents an opportunity for aggressive compiler optimization. We examine computations over the tree abstract datatype (ADT) in particular.
For better utilization than approaches like flattening, we argue that transformations should specialize for common data and computation regularities. For example, we demonstrate a novel pattern that exploits regularity in node labeling as a SIMD parallelism opportunity, which we call SIMTask parallelism. For better applicability, we argue for better linguistic support of irregularity. For example, we show how the future primitive might be used to tolerate occasional data dependencies in an otherwise associative computation.
We validate our approach on two tree computations: RepMin, popular in the functional programming community, and \benchmark{intrinsic widths}, a stage of webpage layout in a prototype web browser. We show speedups over traditional versions of these computations of 124X and 10X, respectively.
The web browser is a CPU-intensive program. Especially on mobile devices, loading of webpages is too slow, spending much of its time in processing a document's appearance. Due to power constraints, most hardware improvements will come in the form of parallel architectures. This is also true of mobile devices such as phones. Current browsers, however, do not yet fully exploit hardware parallelism, so we are designing a parallel mobile browser. In this paper, we introduce new algorithms for CSS selector matching, layout solving, and font rendering, which represent key components for a fast layout engine. Evaluation on popular sites shows speedups as high as 80x. We also formulate layout solving with attribute grammars, enabling us to not only parallelize our algorithm but prove that it computes in O(log) time and without reflow.
We argue that the transition from laptops to handheld computers will happen only if we rethink the design of web browsers. Web browsers are an indispensable part of the end-user software stack but they are too inefficient for handhelds. While the laptop reused the software stack of its desktop ancestor, solid-state device trends suggest that today's browser designs will not become sufficiently (1) responsive and (2) energy-efficient. We argue that browser improvements must go beyond JavaScript JIT compilation and discuss how parallelism may help achieve these two goals. Motivated by a future browser-based application, we describe the preliminary design of our parallel browser, its work-efficient parallel algorithms, and an actor-based scripting language.
This paper presents Flapjax, a language designed for contemporary Web applications. These applications communicate with servers and have rich, interactive interfaces. Flapjax provides two key features that simplify writing these applications. First, it provides event streams, a uniform abstraction for communication within a program as well as with external Web services. Second, the language itself is reactive: it automatically tracks data dependencies and propagates updates along those dataflows. This allows developers to write reactive interfaces in a declarative and compositional style.
Flapjax is built on top of JavaScript. It runs on unmodified browsers and readily interoperates with existing JavaScript code. It is usable as either a programming language (that is compiled to JavaScript) or as a JavaScript library, and is designed for both uses. This paper presents the language, its design decisions, and illustrative examples drawn from several working Flapjax applications.
A fundamental part of the web experience is running metaprograms: extensions modify webpages, search engines index them, and end-user programming tools mash them up. Unfortunately, these tools generally break on AJAX applications because they fail to understand application structure and cope with application updates.
We present a GUI analysis tool that extracts a high-level interaction model of an application. Metaprograms are written with respect to the model instead of manual snapshots of an application. We demonstrate how it helps 2 scenarios. First, by inferring the structure of possible actions, we present a natural language interface for interpreting complex multi-step commands over arbitrary existing websites. Second, as commands are reused over time, we show how to detect when a previously working command will break or become ambigiuous in the face of updates to the underlying application. Furthermore, we can use our tool to heal the interpretations of the commands.
Our approach use abstract interpretation to learn a finite state model of a reactive system by dynamically watching user interactions. It is lightweight and precise without sacrificing recall.
Functional reactive abstractions over time have recently been shown to simplify the description of rich Internet applications, but usability difficulties in defining stateful functions, mixing imperative and functional reactive control sequences, and discerning the boundary for values between the time-varying and flat host domains continue to prevent adoption of transparent embeddings for mainstream languages. We present four novel extensions to previous embedding strategies to help simplify safe, reusable, first-class event handling in the dominant object-oriented rich Internet application language family. Putting these distinct extensions together, we lower previously unsurmounted barriers for introducing structured concurrency specification techniques into a typically ad-hoc yet important domain.
Much of the power of modern Web comes from the ability of a Web page to combine contents and JavaScript code from disparate servers on the same page. While the ability to create such mash-ups is attractive for both the user and the developer because of extra functionality, because of code inclusion, the hosting site effectively opens itself up for attacks and poor programming practices within every JavaScript library or API it chooses to use. In other words, expressiveness comes at the price of losing control. To regain the control, it is therefore valuable to provide means for the hosting page to restrict the behavior of the code that it may include.
This paper presents ConScript, an client-side advice implementation for security, built on top of Internet Explorer 8. ConScript allows the hosting page to express fine-grained application-specific security policies that are enforced at runtime. In addition to presenting 17 widely-ranging security and reliability policies that ConScript enables, we also show how policies can be generated automatically through static analysis of server-side code or runtime analysis of client-side code. We also present a type system that helps ensure correctness of ConScript policies. To show the practicality of ConScript in a range of settings, we compare the overhead of ConScript enforcement and conclude that it is significantly lower than that of other systems proposed in the literature, both on micro-benchmarks as well as large, widely-used applications such as MSN, GMail, Google Maps, and Live Desktop.
Browsers do not currently support the secure sharing of JavaScript objects between principals. We present this problem as the need for object views, which are consistent and controllable versions of objects. Multiple views can be made for the same object and customized for the recipients. We implement object views with a JavaScript library that wraps shared objects and interposes on all access attempts. The security challenge is to fully mediate access to objects shared through a view and prevent privilege escalation. We discuss how object views can be deployed in two settings: same-origin sharing with rewriting-based JavaScript isolation systems like Google Caja, and inter-origin sharing between browser frames over a message-passing channel.
To facilitate simple document sharing, we build a policy system for declaratively defining policies for document object views. Notably, our document policy system makes it possible to hide elements without breaking document structure invariants. We discuss how object views can be deployed in two settings: same-origin sharing with rewriting-based JavaScript isolation systems like Google Caja, and inter-origin sharing between browser frames over a message-passing channel.
For better application-level controls on mashups, we advocate extending the Single Origin Policy and associated primitives to support a cooperative model that allows applications to express explicit sharing policies over browser, Javascript, and physical resources.
First, we introduce an isolation model for content loading that is more complete than those of surveyed browser proposals. Second, we present new primitives to enable an application to secure its use of untrusted content by delegating browser, JavaScript, and physical resources in a fine-grained and reliable manner. Finally, essential to adoption, we propose an architecture based on designs for related abstractions with low performance and implementation costs.
We propose an approach to the consistent update problem of Abstract State Machines through a correctness preserving composition operator. Inconsistent updates are transparently isolated and cause local failure rather systemic failure. This is achieved by a source-to-source translation rather than changing the semantics of Abstract State Machines, thus preserving findings of previous studies on Abstract State Machines and allowing independently verified modules to be composed. Our approach is motivated by experiences with our complementary case study in describing dynamic security policies with Abstract State Machines in which we found the problem pervasive, stemming from a composition abstraction barrier. Previous efforts for supporting ASM composition are susceptible to the inconsistent update problem and may benefit from our approach.
Sensitive data are increasingly available on-line through the Web and other distributed protocols. This heightens the need to carefully control access to data. Control means not only preventing the leakage of data but also permitting access to necessary information. Indeed, the same datum is often treated differently depending on context.
System designers create policies to express conditions on the access to data. To reduce source clutter and improve maintenance, developers increasingly use domain-specific, declarative languages to express these policies. In turn, administrators need to analyze policies relative to properties, and to understand the effect of policy changes even in the absence of properties.
This paper presents Margrave, a software suite for analyzing role-based access-control policies. Margrave includes a verifier that analyzes policies written in the xacml lan- guage, translating them into a form of decision-diagram to answer queries. It also provides semantic differencing information between versions of policies. We have implemented these techniques and applied them to policies from a working software application.
Random fun and controversial talks @ Berkeley not covered by the above:
Transactions on the Web 2012, ASPLOS 2012, Software 2010, WebApps '10, APLAS 2008, ASPLOS 2008, PPDP 2007