Tessellation OS: Partition Management and Two-level Scheduling 1. Space-time Partitioning

Tessellation OS:
Partition Management and Two-level Scheduling
Juan A. Colmenares, Sarah Bird, Paul Pearce, and John Kubiatowicz
Parallel Computing
Laboratory
Par Lab, CS Division, University of California, Berkeley
1. Space-time Partitioning
Address Space A Address Space B
Cell
Task
A Spatial Partition (or Cell)
comprises a group of processors
acting within a hardware boundary
Each cell receives a vector of basic
resources
2nd-level Memory
Management
2nd-level
Scheduling
2. Partition-management Software Layers
–Some number of processors, a portion
of physical memory, a portion of
shared cache memory, and potentially
a fraction of memory bandwidth
Tessellation Kernel
(Partition Support)
Specification of physical
resources
Specification of timemultiplexing policies
CPU
CPU
CPU
CPU
10% of
bandwidth
Specification of required
services and QoSs
Policy Layer
L1
L1
L1
L1
L1
L1
–Exclusive access to other resources
(e.g., certain hardware devices and
raw storage partition)
–Guaranteed fractional services (i.e.,
QoS guarantees) from other partitions
(e.g., network service and file service)
L1 Interconnect
L2
Bank
L2
Bank
L2
Bank
L2
Bank
L2
Bank
L2
Bank
DRAM & I/O Interconnect
DRAM
DRAM
DRAM
DRAM
DRAM
Goals of Space-time Partitioning
 Provide responsiveness and/or QoS
guarantees and more predictable realtime behavior to (parts of) applications
 Achieve better handling of powerperformance tradeoffs
 Offer additional protection, faultcontainment, and security capabilities
Space
Time
–Partitioning adapts to needs of the system
–Some cells persist while others change with time
Cell2
Cell4
e.g., Network Service
Suspension
Time-slice size
1st -level
Scheduling
Cell3
Time
–Pinning (i.e., null policy)
–Time Triggering
–Time Fraction
–Round Robin
Mapping and
Time-Mux’ing Layer
 A cell contains channel endpoints to other cells
Many-core HW
Music
Program
CellX
• Preemptive
• Cooperative
 Implements adaptation policies, which
reflect global goals
 Does admission control (with help from
the Mapping and Time-Mux’ing Layer)
 Performs bin-packing like operation to
implement the Space-Time Resource
Graph
 Time-multiplexes cells at a coarse
granularity
Input
Output
Most of the
engine’s
functionality
Callback
Functions
2nd-level
Support
API
In cooperation with the Music
Apps Group, led by D. Wessel
F
Sound
card
Timer
Interrupt
Audio
Input
Filter
Parallel version of a
partition-based
convolution algorithm
Intermediate
Deadline
End-to-end Deadline
2nd-level
Scheduling
Timer(s)
Level 1: Coarse-grained resource allocation
and time-multiplexing at the cell level
Level 2: Fine-grained application-specific
scheduling within a cell
Network Service
 Implements operations to establish,
activate, and suspend cells, and to
create inter-cell channels and send and
receive messages through them
 Does performance and energy
accounting for cells
Mechanism Layer
Mechanism Layer
HW
Device
File Service
4. Future Demo Application
Policy Layer
Service 1
 Channels enable efficient and non-blocking
message passing
Basic time-mux’ing
policies for cells
/~/
Timer
Interrupt
–Channels allow an application in a cell to access
services and to interact with other applications
residing in other cells
–Message communication between cells is controlled
for security and QoS enforcement
Cell3
2nd-level
preemptive
scheduler
(Re)activation
Application B
Cell2
Space-Time
Resource
Graph
3. Two-level Scheduling
Spatial partitioning may vary over time
Cell1
Parent-Child
Spawning
Relationship
Mapping & Time-Multiplexing Layer
DRAM
(*) The bottom part of this diagram was adapted from Liu and Asanovic,
“Mitosys: ParLab Manycore OS Architecture,” Jan. 2008.
Application A
Cell1
(+)
Fraction of
memory
bandwidth
25% of
capacity
Cell3
Space
CPU
4 cores, 30% time
Cell
A cell may also receive
CPU
Illustrative Example
Cell’s
Specification
Set
2nd-level RT
scheduler A
Channel
F
2nd-level RT
scheduler B
Cell A
Cell B
Audio Processing & Synthesis Engine
Initial Cell
Shell
Additional Cells
The goal is to show that Tessellation can provide
acceptable performance and time predictability
Research supported by Microsoft (Award #024263) and Intel (Award #024894) funding and by matching funding by U.C. Discovery (Award #DIG0710227)