Accuracy-Aware Program Transformations for Energy-Efficient Computing
Accuracy-Aware
Program Transformations
Sasa Misailovic
MIT CSAIL
Collaborators
Martin Rinard
, Michael Carbin,
Stelios Sidiroglou, Henry Hoffmann,
Deokhwan Kim, Fan Long, Daniel Roy,
Zeyuan Allen Zhu, Michael Kling,
Jonathan Kelner, Anant Agarwal
Trade Accuracy
Trade Accuracy
for Energy and Performance
for Energy and Performance
[Rinard ICS’06, OOPSLA’07; Misailovic, Sidiroglou, Hoffmann, Rinard ICSE’10; Carbin, Rinard, ISSTA’10; Hoffmann, Sidiroglou,
Carbin, Misailovic, Agarwal, Rinard ASPLOS’11; Sidiroglou, Misailovic, Hoffmann, Rinard FSE’11; Misailovic, Roy, Rinard, SAS‘11;
Zhu, Misailovic, Kelner, Rinard POPL’12; Carbin, Kim, Misailovic, Rinard PLDI’12; Misailovic, Sidiroglou, Rinard, RACES‘12;
Misailovic, Kim, Rinard TECS PEC’13; Carbin, Kim, Misailovic, Rinard PEPM’13; Carbin, Misailovic, Rinard, OOPSLA ‘13; …]
Harness Approximate Computing
How to
systematically
generate
approximate programs?
How to
predict accuracy
of the results of
approximate programs?
How to
find the most profitable
approximate programs?
Automated Transformations
Probabilistic Reasoning
Explicit Search and
Mathematical Optimization
Transformations
Do less work
•
Loop perforation
•
Sampling, Task skipping
for (i = 0; i < n;
i += 2
)
{ … }r =
var
+.
2;
lock(x)
;
function();
unlock(x)
;
Do different kind of work
•
Randomized substitution
Exploit Execution Environment
•
Unreliable operation placement
•
Unreliable memory regions, Lock elision
Where
and
when
should we
apply the transformations?
What are the
benefits
and
costs
?
Optimization Framework
•
F
ind Candidates
for Transformation
•
A
nalyze Effects of the
Transformations
•
N
avigate Tradeoff Space
F
ind Transformation Candidates:
•
Profile program to find time-consuming for loops
A
nalyze the Effects of Transformation:
•
Performance: Compare execution times
•
Accuracy: Compare the quality of the results
•
Safety: memory safety, well formed output
N
avigate Tradeoff Space:
•
Combine multiple perforatable loops
Prioritize loops by their individual performance and accuracy
Greedy or Exhaustive Search with Pruning
Explicit Search Algorithm for Perforation
[Misailovic, Sidiroglou, Hoffmann, Rinard ICSE’10; Hoffmann, Sidiroglou, Carbin, Misailovic,
Agarwal, Rinard ASPLOS’11; Sidiroglou, Misailovic, Hoffmann, Rinard FSE’11]
x264 Cumulative Loop Scores
Mean Normalized Time
Accuracy loss (%)
Computational Kernels:
Several perforatable computations
execute for the majority of the time
Computational
patterns:
•
Distance metrics
•
Data Statistics
•
Iteration steps
•
Monte-Carlo
Next Step: Analyses with Guarantees
Accuracy analysis:
Results valid for a whole
range of inputs, not just those used in testing
Navigation:
Explore the space of transformed
programs to find those with optimal tradeoffs
Accuracy Analysis:
Probabilistic Reasoning
[Misailovic, Roy, Rinard SAS ’11
;
Zhu, Misailovic, Kelner, Rinard POPL ’12;
Misailovic, Sidiroglou, Rinard, RACES ‘12, Misailovic, Kim, Rinard TECS PEC ’13,
Carbin, Misailovic, Rinard, OOPSLA ’13, Misailovic, Rinard WACAS ‘14,
Misailovic, Carbin, Achour, Qi, Rinard MIT-TR ‘14]
Optimization of Map-Fold Computations
outList =
Map
(
Func(x),
inputList
)
[Zhu, Misailovic, Kelner, Rinard POPL 2012; Misailovic, Rinard WACAS 2014]
Optimization of Map-Fold Computations
Linear + Dynamic programming
[Zhu, Misailovic, Kelner, Rinard POPL 2012; Misailovic, Rinard WACAS 2014]
float<
0.99*R(x)
>
f
(float
in unrel
x
)
{y = g(x) +. h(x);
return
y *. y;
}
Chisel:
Automatic Generation of
Approximate Rely Programs
[Misailovic, Carbin, Achour, Qi, Rinard MIT-TR 14]
Chisel:
Automatic Generation of
Approximate Rely Programs
Integer Linear Programming
[Misailovic, Carbin, Achour, Qi, Rinard MIT-TR 14]
Navigate Search Space:
Mathematical Optimization
[Zhu, Misailovic, Kelner, Rinard POPL ’12; Misailovic, Rinard WACAS ‘14
Misailovic, Carbin, Achour, Qi, Rinard, MIT-TR ‘14]
Looking Forward
Fully Exploit Optimization Opportunities:
both application- and hardware-level transformations
Reasoning About Uncertainty:
•
logic-based techniques
•
probabilistic techniques
•
empirical techniques
Practical Aspects:
provide intuition and control
for developers and domain experts
Takeaway
Emerging trend of
approximate
programs and devices
Accuracy-aware transformations are powerful tool
•
Improve performance
•
Reduce energy consumption
•
Facilitate dynamic adaptation and
software specialization
Interaction of program analysis and search techniques
to find
profitable, safe, and predictable
tradeoffs
Takeaway
Accuracy-aware transformations
•
Improve performance
•
Reduce energy consumption
•
Facilitate dynamic adaptation
and software specialization
Program analysis and search
can help find
profitable, safe,
and predictable
tradeoffs
Takeaway
Accuracy-aware transformations
•
Improve performance
•
Reduce energy consumption
•
Facilitate dynamic adaptation
and software specialization
Program analysis and search
can help find
profitable, safe,
and predictable
tradeoffs
Explore the concept of accuracy-aware program transformations led by Sasa Misailovic and collaborators at MIT CSAIL. The research focuses on trading accuracy for energy and performance, harnessing approximate computing, and applying automated transformations in program optimization. Discover how to systematically generate approximate programs, predict accuracy, and find profitable approximations through probabilistic reasoning and mathematical optimization techniques.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Accuracy-Aware Program Transformations Sasa Misailovic MIT CSAIL
Collaborators Martin Rinard, Michael Carbin, Stelios Sidiroglou, Henry Hoffmann, Deokhwan Kim, Fan Long, Daniel Roy, Zeyuan Allen Zhu, Michael Kling, Jonathan Kelner, Anant Agarwal
Trade Accuracy for Energy and Performance [Rinard ICS 06, OOPSLA 07; Misailovic, Sidiroglou, Hoffmann, Rinard ICSE 10; Carbin, Rinard, ISSTA 10; Hoffmann, Sidiroglou, Carbin, Misailovic, Agarwal, Rinard ASPLOS 11; Sidiroglou, Misailovic, Hoffmann, Rinard FSE 11; Misailovic, Roy, Rinard, SAS 11; Zhu, Misailovic, Kelner, Rinard POPL 12; Carbin, Kim, Misailovic, Rinard PLDI 12; Misailovic, Sidiroglou, Rinard, RACES 12; Misailovic, Kim, Rinard TECS PEC 13; Carbin, Kim, Misailovic, Rinard PEPM 13; Carbin, Misailovic, Rinard, OOPSLA 13; ]
Harness Approximate Computing How to systematicallygenerate approximate programs? Automated Transformations How to predict accuracy of the results of approximate programs? Probabilistic Reasoning How to find the most profitable approximate programs? Explicit Search and Mathematical Optimization
Transformations Do less work Loop perforation Sampling, Task skipping for (i = 0; i < n; i += 2) { } Do different kind of work Randomized substitution r = f_0(x) ? f_1(x); Exploit Execution Environment Unreliable operation placement Unreliable memory regions, Lock elision r = var +. 2;
Where and when should we apply the transformations? What are the benefits and costs?
for (i = 0; i < n; i++) { } for (i = 0; i < n; i += 2) { } Optimization Framework Find Candidates for Transformation Analyze Effects of the Transformations Navigate Tradeoff Space ccc
[Misailovic, Sidiroglou, Hoffmann, Rinard ICSE10; Hoffmann, Sidiroglou, Carbin, Misailovic, Agarwal, Rinard ASPLOS 11; Sidiroglou, Misailovic, Hoffmann, Rinard FSE 11] Explicit Search Algorithm for Perforation Find Transformation Candidates: Profile program to find time-consuming for loops Analyze the Effects of Transformation: Performance: Compare execution times Accuracy: Compare the quality of the results Safety: memory safety, well formed output Navigate Tradeoff Space: Combine multiple perforatable loops Prioritize loops by their individual performance and accuracy Greedy or Exhaustive Search with Pruning
x264 Cumulative Loop Scores Mean Normalized Time Accuracy loss (%)
Computational Kernels: Several perforatable computations execute for the majority of the time Computational patterns: Distance metrics Data Statistics Iteration steps Monte-Carlo # Perforatable Loops 14 Benchmark % Time X264 > 60% Bodytrack 8 > 75% Swaptions 4 > 99% Ferret 2 > 40% Blackscholes 1 > 98% Canneal 1 > 5% Streamcluster 1 > 98%
Next Step: Analyses with Guarantees Accuracy analysis: Results valid for a whole range of inputs, not just those used in testing Navigation: Explore the space of transformed programs to find those with optimal tradeoffs
Accuracy Analysis: Probabilistic Reasoning For approximate program configuration For approximate program configuration ? ?? ??? ??? (?) > ? < ? [Misailovic, Roy, Rinard SAS 11; Zhu, Misailovic, Kelner, Rinard POPL 12; Misailovic, Sidiroglou, Rinard, RACES 12, Misailovic, Kim, Rinard TECS PEC 13, Carbin, Misailovic, Rinard, OOPSLA 13, Misailovic, Rinard WACAS 14, Misailovic, Carbin, Achour, Qi, Rinard MIT-TR 14]
[Zhu, Misailovic, Kelner, Rinard POPL 2012; Misailovic, Rinard WACAS 2014] Optimization of Map-Fold Computations outList = Map ( Func(x), Func0: ( 0,T0) Func1: ( 1,T1) Func2: ( 2,T2) inputList ) Accuracy Requirement: ? outList ?? ? ? > ? < ?
[Zhu, Misailovic, Kelner, Rinard POPL 2012; Misailovic, Rinard WACAS 2014] Optimization of Map-Fold Computations Func0: ( 0,T0) Func1: ( 1,T1) Func2: ( 2,T2) Configuration: ?0 , ?1 , ?2 Probability to execute each version of Func Range: ?? 0,1 , Sum: ?0+ ?1+ ?2= 1 outList= Map( Func0(x) ?? Func1(x) ? ? Accuracy Loss Constraint: ?0 ?0+ ?1 ?1+ ?2 ?2 ?? Func2(x) , Goal: ??? ?0??0+ ?1??1+ ?2??2 inputList ) Linear + Dynamic programming
[Misailovic, Carbin, Achour, Qi, Rinard MIT-TR 14] Chisel: Automatic Generation of Approximate Rely Programs Developer s reliability specification float<0.99*R(x)> f(float in unrel x) { y = g(x) +. h(x); return y *. y; } Variable and Operation Annotations
[Misailovic, Carbin, Achour, Qi, Rinard MIT-TR 14] Chisel: Automatic Generation of Approximate Rely Programs Developer s specification Configuration: 0 , 1 , 2 Unreliable variable or unreliable operation Range: ? 0,1 float<0.99*R(x)> f(float x ? ) { Reliability Constraint: 0log??+ 1log?++ 2log? log0.99 y = g(x) + ? h(x); Goal: return y * ? } y; ??? 0??+ 1?++ 2? Integer Linear Programming
Navigate Search Space: Mathematical Optimization Find configuration Find configuration ? = (??, ,??) ??? ? Performance(?) s. t. s. t. ?? Res Res (?) > ? < ? [Zhu, Misailovic, Kelner, Rinard POPL 12; Misailovic, Rinard WACAS 14 Misailovic, Carbin, Achour, Qi, Rinard, MIT-TR 14]
Looking Forward Fully Exploit Optimization Opportunities: both application- and hardware-level transformations Reasoning About Uncertainty: logic-based techniques probabilistic techniques empirical techniques Practical Aspects: provide intuition and control for developers and domain experts
Takeaway Accuracy-aware transformations Improve performance Reduce energy consumption Facilitate dynamic adaptation and software specialization Program analysis and search can help find profitable, safe, and predictable tradeoffs
Takeaway Accuracy-aware transformations Improve performance Reduce energy consumption Facilitate dynamic adaptation and software specialization Program analysis and search can help find profitable, safe, and predictable tradeoffs
