The trend toward manycore systems presents serious challenges for client devices. Users will expect better performance from applications as the number of cores increases; this expectation requires parallelizing client applications and exploiting parallelism that is likely to be fragile and easily disturbed by interference. At the same time, users have increased their appetite for responsive user interfaces and high-quality multimedia (e.g., videoconferencing, multi-player gaming, and music composition) with stringent real-time requirements; such needs are not well supported by today’s commodity operating systems.

Our charter is to investigate new structures for operating systems and multicore hardware that can simultaneously support real-time, responsive, and high-throughput parallel applications.

We hypothesize that a much wider variety of performance goals can be met by structuring the operating system around resource distribution, performance isolation, and QoS guarantees; such structuring is natural in a manycore environment. Our fundamental component is a resource-guaranteed "Cell" which provides guaranteed fractions of system resources (such as processors, cache, network or memory bandwidth, fractions of system services, etc). Processors within cells are gang scheduled. We believe that Cells should replace processes as the basic OS primitive for constructing applications.

Our new operating system is called Tessellation. Its name derives from our space-time partitioning approach that tessellates Cells across the space of hardware resources. Tessellation is targeted at both existing and future ManyCore hardware. Currently, it runs on Intel multicore hardware as well as the RAMP multicore emulation platform. Although not yet ready for "prime time", releases of Tessellation will be made available to developers at some point in the near future.

The basic Tessellation approach hinges on two fundamental ideas: Space-Time Partitioning (STP) and Two-Level Scheduling. Space-Time Partitioning exploits software layering and hardware mechanisms (when available) to provide guaranteed resources to Cells. Two-Level Scheduling separates global decisions about the allocation of resources to Cells from application-specific scheduling of resources within Cells. Once resources have been assigned to Cells, STP guarantees that user-level schedulers within Cells may utilize resources as they wish, without interference from other Cells or from the OS.

A spatial partition is a performance-isolated unit of resources maintained through a combination of software and hardware mechanisms. Managed resources include gang-scheduled hardware thread contexts, guaranteed fractions of shared resources (e.g. cache or memory bandwidth), access to OS services, and fractions of the energy budget. Support for STP consists of a combination of hardware and software mechanisms. The "Partition Mechanism Layer," which enforces partition boundaries, has some similarities to a hypervisor but with a crucial difference: its sole task is to provide performance-isolated, QoS-guaranteed containers for applications and OS services. Although Tessellation runs on existing multicore systems, we are actively investigating ways in which new hardware facilities can enhance the QoS provided to Cells.

Tessellation separates global decisions about resources allocation from local decisions about resource usage. The resource allocation process focuses on the impact of resources quantities on Cell execution, leaving the fine details about how to utilize these resources to application-specific schedulers. Tessellation changes resource distribution infrequently to amortize the cost of the decision-making process and to minimize interference with application-level scheduling.

The Cell-level scheduler runs at user-level and manages all resources within a Cell. Performance isolation between Cells guarantees that applications can get predictable and repeatable behavior, simplifying performance optimization and realtime scheduling. Central to Tessellation's aproach is the runtime framework, called Lithe, that permits construction of composable, application-specific schedulers.

Tessellation is funded through three sources: the ParLab, the University of California Discovery program, and through the Department of Energy. Details are given below.

In March 2007, Intel and Microsoft announced they would fund a Universal Parallel Computing Research Center (UPCRC) and invited the 25 top Computer Science departments to submit proposals. In August 2007, Intel and Microsoft told us that their technical committee had unanimously selected Berkeley as the top choice of the competition. The public announcement came March 2008, and included support for University of Illinois in addition to Berkeley. The five-year, $10M, UPCRC forms the foundation for the U.C. Berkeley Parallel Computing Laboratory, or Par Lab, a multidisciplinary research project exploring the future of parallel processing. This funding is Microsoft Award #024263 and Intel Award #024894.

Tessellation is the official OS of the ParLab. More information about ParLab can be can be found HERE

In addition to Intel and Microsoft, the ParLab is funded through a matching grant form the U.C. Discovery program. This funding is U.C. Discovery Award #DIG07-1022270.

Finally, Tessellation is independently funded through DOE ASCR FastOS Grant #DE-FG02-08ER25849.

The Tessellation research group has a variety of opportunities for people to contribute. This page will list some of them (and will change over time).

Since Tessellation OS is still in its early stages of development, we have a wide variety of interesting research topics that can lead to masters or PhD work. If you are a Berkeley graduate student, feel free to contact any of the members of our team (John Kubiatowicz, Juan Colmenares, etc). Further, you are always welcome at our research meetings.

The Tessellation group has a variety of opportunities for Berkeley undergraduates. Possible projects include porting/rewriting applications, working on parallel services, and detailed infrastructure development.

We currently have the following opportunities:

• Implement a user-space USB subsystem or GPU driver (link)
• Implement UEFI Support (link)
• Implement a POSIX shim (link)
• Port Python, SEJITS, and related libraries to Tessellation (link)
• Implement a user-space hard drive driver (link)
• Implement a shell application with job creation, job control and basic coreutils functionality (link)
• Implement a dynamic resource management infrastructure (link)

If you are interested in contributing in other ways, contact John Kubiatowicz (kubitron at cs.berkeley.edu)