te
ck
m
9
elements
• I
b
to
a
IBM Research
The Virtualized Virtual Machine:
The Next Generation of Virtual Machine Technology
F
p
cl
g
David F Bacon
IBM T.J. Watson Research Center
s
November 5, 2003
• Confidentiality/date line: 13pt Arial Regular, white
© 2003 IBM
Corporation
• Copyright: 10pt Arial
te
Template release: Oct 02
For the latest, go to http://w3.ibm.com/ibm/presentations
elements
•I
b
to
an
IBM Research
The Virtual Machine
•B
n
1
s
9
m
Scheduler
k
Virtual Machine Definition
Lock
Mgr
Object
Model
Garbage
Collector
Compiler
Stack
Layout
Data
Layout
Instruction Set Architecture
© 2003 IBM Corporation
Optional slide number:
• Title/subtitle/confidentiality line: 10pt Arial Regular, white
• Copyright: 10pt
te
Template release: Oct 02
For the latest, go to http://w3.ibm.com/ibm/presentations
elements
•I
b
to
an
IBM Research
The Virtualized Virtual Machine
•B
n
1
s
9
m
Scheduler
k
Virtual Machine Definition
Lock
Mgr
Object
Model
Garbage
Collector
Compiler
Stack
Layout
Data
Layout
Instruction Set Architecture
© 2003 IBM Corporation
Optional slide number:
• Title/subtitle/confidentiality line: 10pt Arial Regular, white
• Copyright: 10pt
te
Template release: Oct 02
For the latest, go to http://w3.ibm.com/ibm/presentations
elements
•I
b
to
an
IBM Research
Virtualizing the Garbage Collector
•B
n
1
s
9
m
Scheduler
k
Virtual Machine Definition
Lock
Mgr
Object
Model
Garbage
Collector
Compiler
Stack
Layout
Data
Layout
Instruction Set Architecture
© 2003 IBM Corporation
Optional slide number:
• Title/subtitle/confidentiality line: 10pt Arial Regular, white
• Copyright: 10pt
te
Template release: Oct 02
For the latest, go to http://w3.ibm.com/ibm/presentations
elements
•I
b
to
an
IBM Research
Virtualizing the Garbage Collector
•B
n
1
s
k
9
m
Existing VMs support multiple collectors (static)
Can make selection dynamic [Soman et al ’04]
• Can switch during execution
• Based on profiling
Can generate new “algorithms” [Bacon et al ’04]
• Generate dynamically
• Respond to program characteristics
–
–
–
–
Mutation rate
Survival rate
Available memory and power
Heap topology
© 2003 IBM Corporation
Optional slide number:
• Title/subtitle/confidentiality line: 10pt Arial Regular, white
• Copyright: 10pt
Template release: Oct 02
For the latest, go to http://w3.ibm.com/ibm/presentations
elements
•I
b
to
an
IBM Research
te
Single Heap Collectors
•B
n
1
s
R
O
O
T
S
k
T
T
HEAP
Tracing (1960)
R
O
O
T
S
C
C
HEAP
Pure Reference Counting (1960)
9
m
R
O
O
T
S
C
T
HEAP
Partial Tracing (new)
R
O
O
T
S
T
C
HEAP
Deferred Reference Counting (1976)
© 2003 IBM Corporation
Optional slide number:
• Title/subtitle/confidentiality line: 10pt Arial Regular, white
• Copyright: 10pt
te
1
Template release: Oct 02
For the latest, go to http://w3.ibm.com/ibm/presentations
9
m
•I
b
to
an
IBM Research
Generational Collectors
T
T
s
k
elements
T
C
T
C
M
T
Generational (1984)
T
C
M
T
T
C
Ulterior Reference Counting (2003)
T
C
C
M
T
C
•B
n
C
M
T
T
“Redundant Reference Counting” “Inferior Reference Counting”
(new)
(new)
© 2003 IBM Corporation
Optional slide number:
• Title/subtitle/confidentiality line: 10pt Arial Regular, white
• Copyright: 10pt
te
Template release: Oct 02
For the latest, go to http://w3.ibm.com/ibm/presentations
elements
•I
b
to
an
IBM Research
Combining Design and Implementation Frameworks
1
s
k
9
m
Generating new algorithms easily
• Current state of the art: new collector in 30 minutes
Mechanically?
• Leverage frameworks
Online?
• Just In Time Garbage Collector generation
Adaptively?
• “Invalidate” collector and regenerate
© 2003 IBM Corporation
Optional slide number:
• Title/subtitle/confidentiality line: 10pt Arial Regular, white
• Copyright: 10pt
•B
n
te
Template release: Oct 02
For the latest, go to http://w3.ibm.com/ibm/presentations
elements
•I
b
to
an
IBM Research
Virtualizing the Object Model
•B
n
1
s
9
m
Scheduler
k
Virtual Machine Definition
Lock
Mgr
Object
Model
Garbage
Collector
Compiler
Stack
Layout
Data
Layout
Instruction Set Architecture
© 2003 IBM Corporation
Optional slide number:
• Title/subtitle/confidentiality line: 10pt Arial Regular, white
• Copyright: 10pt
te
Template release: Oct 02
For the latest, go to http://w3.ibm.com/ibm/presentations
elements
•I
b
to
an
IBM Research
Virtualizing the Object Model
•B
n
1
s
sync
hash
GC info
k
x
9
m
class pointer
field 1
field 2
© 2003 IBM Corporation
Optional slide number:
• Title/subtitle/confidentiality line: 10pt Arial Regular, white
• Copyright: 10pt
Template release: Oct 02
For the latest, go to http://w3.ibm.com/ibm/presentations
elements
•I
b
to
an
IBM Research
te
Many Small Objects of a Single Type
•B
n
1
PAGE
s
k
9
m
METADATA
f1
f2
f1
f2
f1
f2
f1
f2
f1
f2
f1
f2
f1
f2
f1
f2
f1
f2
f1
f2
f1
f2
f1
f2
f1
f2
f1
f2
f1
f2
f1
f2
f1
f2
f1
f2
f1
f2
f1
f2
f1
f2
f1
f2
f1
f2
f1
f2
class pointer
GC bits
hash codes
locks
© 2003 IBM Corporation
Optional slide number:
• Title/subtitle/confidentiality line: 10pt Arial Regular, white
• Copyright: 10pt
te
Template release: Oct 02
For the latest, go to http://w3.ibm.com/ibm/presentations
elements
•I
b
to
an
IBM Research
Virtualizing the Data Layout
•B
n
1
s
9
m
Scheduler
k
Virtual Machine Definition
Lock
Mgr
Object
Model
Garbage
Collector
Compiler
Stack
Layout
Data
Layout
Instruction Set Architecture
© 2003 IBM Corporation
Optional slide number:
• Title/subtitle/confidentiality line: 10pt Arial Regular, white
• Copyright: 10pt
Template release: Oct 02
For the latest, go to http://w3.ibm.com/ibm/presentations
s
k
•I
b
to
an
IBM Research
te
1
elements
Objects of Varying Size: char[ ]
h
e
l
l
o
w
o
r
l
d ﺽض
Default Representation: Unicode
he l l o
9
wo r l d
ﺽض
m
Big Character
Look-aside Table
(SW or HW)
Compressed Representation: Bytes
© 2003 IBM Corporation
Optional slide number:
• Title/subtitle/confidentiality line: 10pt Arial Regular, white
• Copyright: 10pt
•B
n
te
Template release: Oct 02
For the latest, go to http://w3.ibm.com/ibm/presentations
elements
•I
b
to
an
IBM Research
Virtualizing the Hardware
•B
n
1
s
9
m
Scheduler
k
Virtual Machine Definition
Lock
Mgr
Object
Model
Garbage
Collector
Compiler
Stack
Layout
Data
Layout
Instruction Set Architecture
© 2003 IBM Corporation
Optional slide number:
• Title/subtitle/confidentiality line: 10pt Arial Regular, white
• Copyright: 10pt
te
Template release: Oct 02
For the latest, go to http://w3.ibm.com/ibm/presentations
elements
•I
b
to
an
IBM Research
Kava: Enabling Dynamic Hardware
•B
n
1
s
k
9
m
Combine Java abstraction with VHDL precision
Eliminate primitive types (int, boolean, float)
• Instead define class int, float, etc. in java.lang
Object-orientation down to a single bit!
Allows user-defined primitives
• Efficient
• Flexible
Hardware flexibility
• Expose (MMX)
• Compile (float)
• JIT (point3D)
© 2003 IBM Corporation
Optional slide number:
• Title/subtitle/confidentiality line: 10pt Arial Regular, white
• Copyright: 10pt
te
1
s
k
9
Template release: Oct 02
For the latest, go to http://w3.ibm.com/ibm/presentations
elements
•I
b
to
an
IBM Research
Object-Oriented Bits
•B
n
enum bit {
zero, one;
public bit ~ this
public bit this & bit that
{ return not[this]; }
{ return and[this][that]; }
public bit sum(bit a, bit b) { return sum[this][a][b]; }
m
static final bit not[bit]
= {one, zero};
static final bit and[bit][bit]
= {{zero, zero}, {zero, one}};
static final bit sum[bit][bit][bit] = {{{zero,one}, {one, zero}},
{{one, zero}, {zero, one}}};
….
© 2003 IBM Corporation
Optional slide number:
• Title/subtitle/confidentiality line: 10pt Arial Regular, white
• Copyright: 10pt
Template release: Oct 02
For the latest, go to http://w3.ibm.com/ibm/presentations
elements
•I
b
to
an
IBM Research
te
Primitive Types: unsigned byte
•B
n
1
s
enum byteindex { b0, b1, b2, b3, b4, b5, b6, b7 };
final value ubyte {
private bit data[byteindex];
k
9
m
…
}
ubyte
data
bit[ ]
b0
b1
b2
b3
b4
b5
b6
b7
bit 1
bit 0
© 2003 IBM Corporation
Optional slide number:
• Title/subtitle/confidentiality line: 10pt Arial Regular, white
• Copyright: 10pt
te
Template release: Oct 02
For the latest, go to http://w3.ibm.com/ibm/presentations
elements
•I
b
to
an
IBM Research
Implementing Comparison
•B
n
1
s
k
9
m
public boolean this < ubyte that {
for each (byteindex x: byteindex.last…byteindex.first)
if (data[x] != that.data[x])
return data[x] < that.data[x];
return false;
}
© 2003 IBM Corporation
Optional slide number:
• Title/subtitle/confidentiality line: 10pt Arial Regular, white
• Copyright: 10pt
Template release: Oct 02
For the latest, go to http://w3.ibm.com/ibm/presentations
s
k
9
m
•I
b
to
an
IBM Research
te
1
elements
protected float add(float that) {
if (this.isNaN() || that.isNaN())
return propagateNaN(that);
fexponent exp;
if (this.exponent > that.exponent) {
fexponent diff = this.exponent - that.exponent;
if (this.isInfinity()) {
if (that.isInfinity() && this.sgn != that.sgn)
return NaN;
else
return this;
}
if (that.denormalized())
diff--;
else
thatman = thatman.setbit(ImplicitBit);
thatman = shiftAndJam(thatman, diff);
exp = this.exponent;
if (this.isZero() && that.isZero()) {
if (this.sgn == sign.minus && that.sgn == sign.minus)
return NEGATIVE_ZERO;
else
return POSITIVE_ZERO;
}
}
else {
fexponent diff = that.exponent - this.exponent;
uint thisman = this.mantissa.uintValue() << ComputeShift;
uint thatman = that.mantissa.uintValue() << ComputeShift;
if (this.denormalized())
diff--;
else
thisman = thisman.setbit(ImplicitBit);
if (this.exponent == that.exponent && this.exponent.denormalized())
return new float(this.sgn,
this.mantissa.carry(that.mantissa) == bit.zero ?
exponent.zero : exponent.one, this.mantissa + that.mantissa);
thisman = shiftAndJam(thisman, diff);
exp = that.exponent;
thisman = thisman.setbit(ImplicitBit);
thatman = thatman.setbit(ImplicitBit);
}
return roundAndPack(this.sgn, exp,
(thisman + thatman) << wordindex.bit1);
}
return roundAndPack(this.sgn, this.exponent,
(thisman + thatman) << wordindex.bit1);
}
© 2003 IBM Corporation
Optional slide number:
• Title/subtitle/confidentiality line: 10pt Arial Regular, white
• Copyright: 10pt
•B
n
Template release: Oct 02
For the latest, go to http://w3.ibm.com/ibm/presentations
s
What the Programmer Sees
point
ubyte
bit[ ]
x
data
x0
x1
x2
x3
x4
x5
x6
x7
y
k
9
m
•I
b
to
an
IBM Research
te
1
elements
ubyte
data
bit[ ]
x0
x1
x2
x3
x4
x5
x6
x7
bit 1
bit 0
•B
n
bit 1
bit 0
© 2003 IBM Corporation
Optional slide number:
• Title/subtitle/confidentiality line: 10pt Arial Regular, white
• Copyright: 10pt
Template release: Oct 02
For the latest, go to http://w3.ibm.com/ibm/presentations
elements
•I
b
to
an
IBM Research
te
What the Machine Sees
•B
n
1
s
k
point
x: ubyte
x7 x6 x5 x4 x3 x2 x1 x0
0 0 0 0 1 1 1 1
y: ubyte
x7 x6 x5 x4 x3 x2 x1 x0
0 0 0 0 1 1 1 1
9
m
point(15,15)
0000111100001111
(16-bit halfword)
© 2003 IBM Corporation
Optional slide number:
• Title/subtitle/confidentiality line: 10pt Arial Regular, white
• Copyright: 10pt
Template release: Oct 02
For the latest, go to http://w3.ibm.com/ibm/presentations
elements
•I
b
to
an
IBM Research
te
JITing the Instruction Set
•B
n
1
s
k
9
m
Interpret
Compile
Optimize
Re-program hardware
Programmable Functional Units
• Shift, mask, fill
• Modify/add ALU operations
© 2003 IBM Corporation
Optional slide number:
• Title/subtitle/confidentiality line: 10pt Arial Regular, white
• Copyright: 10pt
te
Template release: Oct 02
For the latest, go to http://w3.ibm.com/ibm/presentations
elements
•I
b
to
an
IBM Research
Next Level: Programmable Fabrics
•B
n
1
s
Fundamental property of hardware: finite
Imagine a CPU with an attached FPGA
“Compiling” a critical loop:
k
• No external dependencies
9
• Strip mine (finite bounds)
m
• Feed into FPGA compiler
• Reprogram FPGA fabric
• Re-JIT code to use new fabric operations
© 2003 IBM Corporation
Optional slide number:
• Title/subtitle/confidentiality line: 10pt Arial Regular, white
• Copyright: 10pt
Template release: Oct 02
For the latest, go to http://w3.ibm.com/ibm/presentations
elements
•I
b
to
an
IBM Research
te
Conclusions
•B
n
1
s
Virtual machine interfaces allow flexibility
But so far, we only exploit one dimension
Everything below the interface is malleable
Huge opportunity
k
• Innovation
9
• Performance
m
© 2003 IBM Corporation
Optional slide number:
• Title/subtitle/confidentiality line: 10pt Arial Regular, white
• Copyright: 10pt