Transcript Operating System Support for Application-Specific Speculation

Operating System Support for
Application-Specific Speculation
Benjamin Wester
Peter Chen and Jason Flinn
University of Michigan
TIME
Speculative Execution
Predict A
A
 Sequential dependent tasks
 Predict results of Task A
to break dependence
 Execute Task B in parallel
 Isolate all effects
 Correct prediction: commit
 Wrong prediction: abort
B
B
EuroSys 2011
2
Speculation Everywhere!







Discrete event simulation
I/O prefetching
Distributed shared memory
Distributed file systems
Deadlock detection
Remote displays
Web page pre-rendering
EuroSys 2011
3
Speculation as a Service to Apps
How is this system designed?
In what ways can it be customized for an app?
How can those customizations be specified?
EuroSys 2011
4
Outline





Introduction
Designing Speculation as a Service
Implementation
Evaluation
Conclusion
EuroSys 2011
5
Design 1: In-App Speculation
+ Complete semantic info
+ Predict arbitrary app
operations
+ Safe operations allowed
Data
Data
App 2
App 1
‒ No reuse: significant
development needed
‒ Scope is limited: unsafe
operations block
EuroSys 2011
6
Design 2: Generic OS Speculation
+ Apps need no modifications
+ Wide scope: unsafe
operations taint
App 1
App 2
OS
‒ Lacks semantic
understanding of app
‒ Predict system calls only
‒ Handle application
conservatively
EuroSys 2011
7
Separate Mechanism and Policy
Mechanism implements isolation
Policy describes customizations
Best of both extremes
 Mechanism built in OS
o Common implementation
o Wide scope
 Policy specified in Applications
o Expose semantic information
EuroSys 2011
8
Design 3: Expose Predictions
App 2
App 1
+ Predict arbitrary app
operations
+ Reuse OS mechanism
(with app assistance)
+ Wide scope for taint
propagation
‒ Limited semantic info
OS
‒ Speculative external output
never allowed
‒ Commit on identical results
EuroSys 2011
9
Design 4: Expose Safety
App 2
App 1
+ Predict arbitrary app
operations
+ Reuse OS mechanism
(with app assistance)
+ Wide scope for taint
propagation
+ More semantic info
OS
+ Allow safe output
+ Commit on equivalent results
EuroSys 2011
10
Customizable Policy
 Creation
o What tasks are predictable
o How to predict them
 Output
o What output is safe to allow
 Commit
o Which results are acceptable to commit
EuroSys 2011
11
Outline





Introduction
Designing Speculation as an OS Service
Implementation
Evaluation
Conclusion
EuroSys 2011
12
Implementation
 Mechanism built in OS
o Based on Speculator kernel
o Checkpoints & logs processes, files, IPC, etc.
 Policies expressed using system call API
EuroSys 2011
13
TIME
spec_fork()
spec_fork
predict A
Speculative
Process
A
Control
Process
B
commit
abort
C
B
EuroSys 2011
14
API Example
int main() {
int x;
int prediction = get_prediction();
if (spec_fork() == SPECULATIVE) {
x = prediction;
} else {
x = slow_function();
if (equiv(x, prediction))
commit();
else
abort();
}
set_output_policy(stdout, ALLOW);
printf(“%d”, x);
}
EuroSys 2011
Creation Policy
Commit Policy
Output Policy
15
Outline





Introduction
Designing Speculation as an OS Service
Implementation
Evaluation
Conclusion
EuroSys 2011
16
Evaluation
Can apps effectively use API
to increase parallelism?
Case studies
1. Predictive application launching in Bash
2. SSL certificate checks in Firefox
3. Replicated service in PBFT-CS
EuroSys 2011
17
TIME
App 1: Predictive Launching in Bash
Run program
Check command
grep foo –r .
Output Policy:
Safe X11 Messages: Allow
EuroSys 2011
…finished
bwester $ ▌
Creation Policy:
Use machine learning
to predict user input
…finished
bwester $ grep foo –r .
▌
Commit Policy:
Normalize user input
before comparison
18
How Much Work Can Be Hidden?
Speculative
6
Prompt
Run Time (seconds)
TIME
Non-Speculative
Get cmd
45
Prompt
5
4
3
Spec.
Execute
cmd
2
1
0
Get cmd
Execute
Execute
cmd
EuroSys 2011
19
How Much Work Can Be Hidden?
6
Prompt
Run Time (seconds)
TIME
Non-Speculative
Get cmd
Up to
45 86% hidden
Speculative
Prompt
5
4
3
Spec.
Execute
cmd
2
1
0
Get cmd
Execute
Execute
cmd
EuroSys 2011
20
TIME
App 2: Firefox SSL Connections
Creation Policy:
Predict certificate isOpen
valid https://
Web
Server
Output Policy:
Alow SSL connection
Check cert.
Validation
Server
GetValidate
session key
Request page
GET /index.html?id=0123Output Policy:
Block private data
Done
EuroSys 2011
21
Connection Latency Hidden?
https://
Check cert.
Session key
Speculative
Connect Time (milliseconds)
TIME
Non-Speculative
600
https://
500
Check cert.
400
Session key
300
200
100
Validate
Request
0
Request
Done
Done
EuroSys 2011
22
Connection Latency Hidden?
https://
Check cert.
Session key
Speculative
Connect Time (milliseconds)
TIME
Non-Speculative
600
Avg 60ms hidden
https://
500
Check cert.
400
Session key
300
200
100
Validate
Request
0
Request
Done
Done
EuroSys 2011
23
TIME
App 3: PBFT-CS Protocol
Creation Policy:
Agree on 1st reply
Send Request
Request
(Reply, sig1)
Distributed
Replicated
Service
Check reply
(Reply, sig2)
Check reply
Output Policy:
PBFT-CS Messages: Allow
Work…
EuroSys 2011
24
Improved Client Throughput?
Speculative
900
Request1
1st Reply
Verify
Request2
Request1
800
Client Ops per Second
TIME
Non-Speculative
700
600
1st Reply
500
Request2
400
Null requests
300
200
1st Reply
100
0
0
1st Reply
Verify
0.5
1
1.5
Latency between replicas
(milliseconds)
EuroSys 2011
2
25
Improved Client Throughput?
Request1
1st Reply
Verify
Request2
Request1
800
700
600
1st Reply
500
Request2
400
Null requests
300
200
1st Reply
100
Verify
0
0
1st Reply
Speculative
1.9x Throughput
900
Client Ops per Second
TIME
Non-Speculative
0.5
1
1.5
Latency between replicas
(milliseconds)
EuroSys 2011
2
26
Cost of Generic Mechanism
900
Client Ops per Second
800
700
600
500
400
App-specific Mech
Shared OS Mech
Non-speculative
Null requests
300
200
100
0
0
0.5
1
1.5
Latency between replicas
(milliseconds)
EuroSys 2011
2
27
Cost of Generic Mechanism
App-specific:
8% faster
900
Client Ops per Second
800
700
600
500
400
App-specific Mech
Shared OS Mech
Non-speculative
Null requests
300
200
100
0
0
0.5
1
1.5
Latency between replicas
(milliseconds)
EuroSys 2011
2
28
Conclusion
 Mechanism
o Common: checkpoints, output buffering, taint propagation
o Implemented in OS
 Policy
o App-specific: Controls creation, output, and commit
o Implemented in applications
 Demonstrated with 3 case studies
o Improved parallelism
o Small overhead relative to app-specific mechanism
Questions?
EuroSys 2011
29