lmeyerov at eecs dot berkeley dot edu
Par Lab | 565 Soda Hall
Par Lab | 565 Soda Hall
Leo Meyerovich
CS Graduate Student -- Peon Extraordinaire
CS Graduate Student -- Peon Extraordinaire
I work with Ras Bodik in the Par Lab on a parallel web browser and related programming language challenges. 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.
My following languages paint a brighter future for the web:
Finally, causing some excitement, see our work on
Socio-PLT: Sociology for Programming Languages!
Ping me if we coincide!
Collaborators will also be showcasing Superconductor at Khronos, Intel's TechFest, SIGGRAPH, and other upcoming events.
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.
We examine how to synthesize a parallel schedule of structured traversals over trees. In our system, programs are declaratively specified as attribute grammars and parallel traversals for GPUs and multicore CPUs are defined by a compiler. Our synthesizer automatically, correctly, and quickly schedules the attribute grammar.
Scheduling impacts performance and software integration. We therefore introduce a declarative language of schedules where programmers may sketch any part of the schedule and the synthesizer will complete the rest. For the same motivation, the synthesizer answers debugging queries about if and how schedules may be completed and enumerates scheduling choices for autotuning.
This paper presents our cubic-time schedule synthesizer, and its support for finding, specifying, debugging, and autotuning schedules. We evaluate our approach with two case studies. First, we created the first parallel schedule for a large fragment of CSS and report a 3X speedup on multicore hardware. Second, we created a GPU-accelerated visualization language for real-time interactive animations of over 100,000 nodes.
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.
Language designers optimize features for adoption, yet research provides little guidance. Worse, optimizing for adoption leads to foregoing the suggestions that research does provide. For example, advanced type systems are breaking ground in guaranteeing correctness, yet after 30 years, we rarely see even ML-style type inference. As Erik Meijer relates, if the mountain will not come to Mohammed, then Mohammed must go to the mountain [1]. To do so, we ask: how can researchers explicitly optimize for adoptiblity to improve the value proposition of our work?
We propose three constructive steps towards adoption-oriented language design. Designing for adoption takes many forms because adoption itself is multifaceted: it is a desirable result, an exploitable process, and applies to both languages and features. Driven by our survey of social science literature on adoption [2] and our analysis of adoption factors for over 200,000 projects and 15,000 developers [3,4,5], we identify three constructive areas of adoption-oriented design:
I. Feature Streamlining: Improving adoptability of a feature
II. Language Targeting: Improving the adoptability of a language
III. Network Effect Constructs: Designing features that improve with adoption
Some programming languages become widely popular while others fail to grow beyond their niche or disappear altogether. This paper uses survey methodology to identify the factors that lead to language adoption. We analyze large datasets, including over 200,000 SourceForge projects and multiple surveys of 1,000-13,000 programmers. Using this data, we establish baseline quantitative models of the language adoption process.
We report several prominent findings. First, language adoption does not have a long tail; a small number of languages account for most language use. Second, intrinsic features have only secondary importance in adoption. Open source library availability is the most influential factor in selecting a language for a project. Social extrinsic factors such as existing team experience also rate highly. Languages features such as performance and semantics do not. Third, developers will steadily learn and forget languages, but only of a limited variety. Developers select more varied languages if their education exposed them to different language families. Finally, when considering intrinsic aspects of languages, developers prioritize expressivity over correctness. They perceive static types as more valuable for properties such as the former rather than for correctness checking.
Fueled by the web, open source, and the mainstreaming of programming, software research is undergoing an empirical revolution. In this project, we use data from these sources to examine basic and sensitive issues about programming languages. For example, we found developers negatively correlate static types with code reuse, which challenges typical research assumptions about module systems. This work is part of our on-going effort to understand and exploit the relationship between social phenomena and programming languages.
This website showcases some of our early experiences in large-scale and cross-language quantitative analysis. It presents early interactive visualizations that we -- and you -- can use to explore one of our data sets.
We present cross-sectional analyses of programming language use and reflect upon our experience in doing so. In particular, we directly analyze groups of 1,500-13,000 developers by using questionnaires and 260,000 developers indirectly so by mining 210,000 software repositories. Our analysis reveals programming language adoption phenomena surrounding developer age, birth year, workplace, and software repository preference.
We find that survey methods are increasingly accessible and relevant, but there are distinctive problems in examining developers and code repositories. We show that analyzing software repositories suffers from sample bias problems similar to those encountered when directly polling developers. Such bias limits the general validity of research claims based on analysis of software repositories. We aid future empirical researchers by describing concrete practices and opportunities to improve the results of developer and software repository surveys.
Why do some programming languages fail and others succeed? What does the answer tell us about programming language design, implementation, and principles? To help answer these and other questions, we argue for a sociologically-grounded programming language theory: socio-PLT.
Researchers in the social sciences have studied adoption in many contexts. We show how their findings are applicable to programming language design. For example, many programming language features provide benefits that programmers cannot directly or immediately observe and therefore may not find compelling. From clean water to safe sex, the health community has long examined how to surmount similar observability barriers. We use such results from outside of programming language theory to frame a research agenda that should help us understand the social foundations of languages. Finally, we examine implications of our approach, such as for the design space of language features and the assessment of scientific research into programming languages.
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.