Parallel Web Browser: Project Overview

Motivation The web browser has popularized smart phones but failed to gain dominance as an application platform in this computer class because browsers are too slow on power-constrained mobile devices. As a result, mobile applications are developed in less productive frameworks such as Android, iPhone SDK, or Silverlight. Our browser project (i) develops technologies for acceleration of web browsers with the goal of making them suitable for Web 2.0 mobile applications; (ii) designs a mobile software stack that will serve both mobile applications and future mobile browsers; and (iii) develops a coordination language for client-side applications.

Analysis Our project started by analyzing wireless networking trends, especially effects of latency on offloading browser computation to the cloud (interactive tasks must run on the browser), and the CMOS energy trends. Most notable results from our analysis phase are: We identified seven representative future browser applications [1]. We performed performance analysis of today’s browsers, identified their bottlenecks (almost all must be parallelized) [2], and pointed out problems with well-established browser benchmarks [3]. We identified the sources and magnitude of the abstraction tax in browser programming overhead [4]. We pointed out limitations of JIT compilation in improving browser performance, motivating the need for a new programming language [5]. We identified three sources of high-level client-side concurrency [6]. Finally, we defined the parallelization approach followed by our project [7].

Design of Parallel Algorithms After bottlenecks were identified, we addressed them with new parallel algorithms. We designed and evaluated the first efficient parallel lexical analyzer [8], described in [9]. We designed algorithms for translating the (backtracking) regexes to regular expressions, enabling parallelization of regexes [10]. We designed a parallel parser algorithms with nearly perfect speedup on four cores. We designed, evaluated, and distributed a parallel and locality-improving algorithm for CSS selector matching, obtaining about 60-fold speedup on 4 cores [2, also ongoing]. We formalized the CSS layout semantics with attribute grammars, discovering specification ambiguity and contradictions, and opportunities for speculation and parallelism [2, also ongoing]. We developed a speculative CSS layout algorithm for pages with float elements [2].

Future Mobile Application Stack Note that our browser parallelization work excludes (direct) parallelization of JavaScript. We believe that dynamically typed language with embedded DSLs makes effective parallelization impractical [5]. Instead, we propose to turn the browser into an application platform by developing a new language that both raises the level of abstraction and allows compilation into efficient code. We designed an initial draft of a browser productivity language that uniformly supports programming of layouts and events based on bidirectional constraints, using a media player as a case study [15]. We developed a compiler for L3, a subset of this language. The compiler is a synthesizer for modular constraints. We developed an synthesizer of layout engines that turns an attribute grammar into an efficient parallel code. We developed layout optimizations, such as efficient data structures and a semi-static work stealing for parallel layout engines.

[1] C. G. Jones, L. Meyerovich, R. Liu, and R. Bodik. Future browser applications. http://parlab.eecs.berkeley.edu/wiki/internal/apps/browser/browser application domain, 2008

[2] L. A. Meyerovich and R. Bod´ ık. Fast and parallel webpage layout, WWW, pages 711–720. ACM, 2010.

[3] C. G. Jones and R. Bodik. Analysis of browser string benchmarks. http://parallelbrowser.blogspot.com/2008/10/in-firefox-string-and-regexp.html, 2008

[4] J. Galenson, C. Jones, and J. Lo. Toward a browser os: designing a next-generation mobile OS with web technologies. CS262 graduate course project report, EECS Department, University of California, Berkeley, Dec 2008.

[5] R. Bodik, J. Bonnar, and D. Kimelman. Productivity programming for future computers. In PLDI FIT, 2009.

[6] J. Ide, R. Bodik, and D. Kimelman. Concurrency concerns in rich internet applications. In Exploiting Concurrency Efficiently and Correctly – (EC)2 , CAV 2009 Workshop, Grenoble, France, June 2009.

[7] C. Jones, R. Liu, L. Meyerovich, K. Asanovic, and R. Bodik. Parallelizing the web browser. Usenix HotPar, Berkeley, CA, June 2009.

[8] C. G. Jones and R. Bodik. Paralell lexical analysis. http://www.cs.berkeley.edu/~bodik/Files/2008/mozilla-talk-2008-01.pdf, seminar at Intel, 2007

[9] P. Prabhu, G. Ramalingam, and K. Vaswani. Safe programmable speculative parallelism. In Programming Language Design and Implementation (PLDI). ACM, jun 2010.

[10] J. Galenson and C. Jones. Theoretical analysis of regexes with an eye towards their parallelization. CS263 graduate course project report, EECS Department, University of California, Berkeley, Dec 2008

About

News
Course on program synthesis
9/2/2012

Emina Torlak and I have given an invited tutorial at CAV 2012. The tutorial is being expanded this semester into a graduate course, which you can follow as we add lectures and homeworks. CAV tutorial slides: (ppt, pdf, screencast). The graduate course.

Postdoc position position in synthetic biology
8/13/2012

We are looking for postdocs in synthetic biology. We need curious, well-rounded computer scientists with expertise in algorithms, hacking, and with interest in biology.

NSF Expedition in Computing for program synthesis
4/3/2012

The multi-university ExCAPE project aims to change computer programming from the tedious task to one in which a programmer and an "automated program synthesis tool" collaborate to generate software that meets its specifications.

Looking for a postdoc position?
4/3/2012

We are looking for postdocs in program synthesis and computer-aided programming.

2nd Dagstuhl Seminar in Program Synthesis
4/9/2012

Several communities related to synthesis of programs and other computational artifacts will meet again in wine cellars of the castle.

Layout based on BASIC by Download Website Templates