Public

Official blog and Leo's blog
  1. April 19th, 2009. Parallelizing the Web Browser (CodeCon '09). slides (ppt, pdf)
  2. April 1st, 2009. Parallelizing the Web Browser (HotPar '09). paper (pdf, bibtex), slides (ppt, pdf)
  3. January 8th, 2009. Parallelizing the Web Browser (ParLab Winter Retreat). slides (pdf)

A Parallel Web Browser

We're designing the core algorithms and infrastructure of future browsers. Computers are facing a power wall, so, if handhelds are really going to replace laptops, they need to get a lot faster. Sequential optimizations and distributed computing will play a part, but we can also utilize hardware advances: 4-8 cores that are multithreaded and support SIMD instructions. Browsers on handhelds are increasingly CPU bound, so we're redesigning the core browser infrastructure for better sequential and parallel performance. As we have to redesign the basics, this is a good chance to modernize the rest as well.

Plan

Our active targets are browser kernels: lexing, parsing, CSS selectors, CSS layout, and animation. After, we plan to examine parallel scripting in a way that integrates with our new libraries (e.g., concurrent DOM calls and JIT'd layout) and greater systems (below). Furthermore, we will combine our kernels into the skeleton of a new browser to expose integration issues. We are targeting web browsers as they provide a dominant, productive application environment: we will focus on standards compliant optimizations where possible, but standards might be broken and languages might not be productive. In these latter cases, we're more than willing to fix them.

Collaborators

The browser kernels will run as part of a greater system (in collaboration with the Par Lab, Samsung, and Webblaze). As our core stabilizes, we'll be thinking about:
  1. Tessellation OS A thin multicore operating system with resource partitioning.
  2. Lithe A hierarchical, cooperative hardware thread scheduler to enable mixing different parallelism frameworks without worrying about interference.
  3. Security Traditional browser security focuses on protecting lower-level abstractions like runtimes but barely protects actual application abstractions once communication between components inevitably occurs. We will combine operating-system provided separation notions (e.g., Chrome), object capabilities (e.g., Darpa Browser), and more specialized notions (advice membranes -- contact for more information).
  4. Manual Tuning and Autotuning There is a lot of room for general optimizations, but also many machine-specific ones.
  5. RAMP We're testing on a variety of hardware configurations, but simulators will enable us to explore many more.

Current contributors
Gradudate students: Leo Meyerovich, Seth Fowler
Undergraduates: James Ide

Previous contributors
Graduate students: Chris Jones (now @ Mozilla)
Undergraduates: Justin Bonar

We're always looking for collaborators, so please contact us! Parallelism in the consumer space, especially in handhelds, is a new area, so a willingness to explore is the main qualifier.

Code

Ours

Our work is BSD licensed. We're targetting x86 (TBB or Cilk++, unclear about SSE) internally but expect ARM ports (and may switch to ARM) once we have the hardware or help. No policy on GPUs yet -- likely CUDA or OpenCL.

  1. Lexer (currently specialized for Cell processors)
  2. Parser (current target)
  3. CSS selector engine -- Cilk++ and TBB implementations. Expects a dictionary of CSS rules and parsed HTML; annotates nodes with matching rules. Requires non-user agent rules and subsequent rule prioritization. Whittles down 80ms (on a Nehalem) naive algorithm to 1ms (4 hardware threads). working draft pdf

    Future optimizations: see document.

    Future features: further selectors, rule resolution, default properties, adaptive selectors.

  4. CSS 2.1 layout engine (current target). parallel css kernel semantics. A big chunk of this is actually font handling (how to call into FreeType2). We're not optimizing painting yet -- GPUs might enter the picture here (e.g., Cairo Glitz or something smarter).
Relevant software by others
  1. XML parser: ParaXML (+ XPath), ParaBix
  2. SIMD images, GPU fonts
  3. Dataflow scripting language: Flapjax for functional reactive web programming
  4. Data parallel scripting: Copperhead (Python/CUDA)
Last updated 09.23.09