Transcript ADT_UAB_PGCS

Paradyn Week
April 30, 2007
Automatic Performance Tuning:
Automatic Development of Tunlets
Universitat Autònoma de Barcelona
Paola Caymes Scutari
Genaro Costa, Ihab Salawdeh, Alexandre Guevara
Anna Morajko, Eduardo César, Andreu Moreno, Josep Jorba
Tomàs Margalef, Joan Sorribes, Emilio Luque
Universitat Autònoma de Barcelona
Outline

Introduction




Automatic Development of Tunlets






MATE
Tunlets
Our work
Motivation
Abstractions and Methodology
Tunlet Specification Language
Tunlet Generator
Use Case
Conclusions
Outline

Introduction




Automatic Development of Tunlets






MATE
Tunlets
Our work
Motivation
Abstractions and Methodology
Tunlet Specification Language
Tunlet Generator
Use Case
Conclusions
Introduction
Parallel/Distributed Computing

High performance



Developers must optimize application performance to
provide efficient and useful applications
Application behavior may change on input data or
environment
Difficult task especially for non-expert users
MATE

Monitoring, Analysis and Tuning Environment

Dynamic automatic tuning of parallel/distributed
applications
Application development
Application
Source
Execution
Modifications
DynInst
Performance data
Instrumentation
Monitoring
Events
Tuning
Performance
analysis
Problem /
Solution
MATE: Tunlets
Analysis phase includes knowledge about possible
performance problems in the applications.
“TUNLETS”
Analyzer
How to determine
problems and
solutions?
Tunle
Tunlet
t
What to modify?
When?
Where?
Performance
model
What to
measure?
Where?
Measure
points
Tuning
points/actions
MATE (III)

Key question:
What can be tuned in an application?
Application code

Application specific code

Frameworks - Skeletons
API
Framework
code
API

Standard and custom libraries (API+code)

Operating system libraries (API+code)

Hardware
Libraries code
OS API
Operating System
kernel
Hardware
What are we working on?
Application code
API
Performance models for patterns
Framework
code
Performance models for libraries
API
Libraries code
OS API
Operating System
kernel
Execution
Hardware
Measure points MATE
extensions:
Monitoring
Tunlets Specification
Performance
model
Tuning point,
action, sync
Grid
Tuning
Performance
analysis
Outline

Introduction




Automatic Development of Tunlets






MATE
Tunlets
Our work
Motivation
Abstractions and Methodology
Tunlet Specification Language
Tunlet Generator
Use Case
Conclusions
Motivation
User
Application
Framework
Application
MATE
Tunlet
Tunlet
…
Tunlet
Motivation
User
Application
Framework
MATE
Tunlet
…
Tunlet
Application
Automate
Tunlet
Automatic Development of Tunlets

We propose a methodology to:

add new tunlets to overcome different
performance problems

avoid the user to enter in implementations details
of MATE

allow users to develop their applications without
restrictions
Automatic Development of Tunlets
Performance Model
Programming
Model
Parameters
p1, p 2 ...
performance
problem
pi
Mathematical Model
e1 ... ej
Tunlet Specification
Measure Points
p1, p2 ... pi
Performance Functions
f1 ... fj
Tuning Actions/Points
a 1 ... ak
tp1 ... tph
Execution
Tuning
Monitoring
Performance
Analysis
Tunlet ... Tunlet
Automatic Generation
Automatic Development of Tunlets
Performance Model
Programming
Model
Parameters
p1, p 2 ...
performance
problem
pi
Mathematical Model
e1 ... ej
Tunlet Specification
Measure Points
p1, p2 ... pi
Performance Functions
f1 ... fj
Tuning Actions/Points
a 1 ... ak
tp1 ... tph
Execution
Tuning
Monitoring
Performance
Analysis
Tunlet ... Tunlet
Automatic Generation
Automatic Development of Tunlets
Performance Model
Programming
Model
Parameters
p1, p 2 ...
performance
problem
pi
Mathematical Model
e1 ... ej
Tunlet Specification
Measure Points
p1, p2 ... pi
Performance Functions
f1 ... fj
Tuning Actions/Points
a 1 ... ak
tp1 ... tph
Execution
Tuning
Monitoring
Performance
Analysis
Tunlet ... Tunlet
Automatic Generation
Automatic Development of Tunlets
Application
Programming
Model
Performance Model
Parameters
p1, p 2 ...
performance
problem
pi
Mathematical Model
e1 ... ej
Tunlet Specification
Measure Points
p1, p2 ... pi
Performance Functions
f1 ... fj
Tuning Actions/Points
a 1 ... ak
tp1 ... tph
Execution
Tuning
Monitoring
Performance
Analysis
Tunlet ... Tunlet
Automatic Generation
Automatic Development of Tunlets
Application
Programming
Model
Performance Model
Parameters
p1, p 2 ...
performance
problem
pi
Mathematical Model
e1 ... ej
Tunlet Specification
Measure Points
p1, p2 ... pi
Performance Functions
f1 ... fj
Tuning Actions/Points
a 1 ... ak
tp1 ... tph
Execution
Tuning
Monitoring
Performance
Analysis
Tunlet ... Tunlet
Automatic Generation
Automatic Development of Tunlets

Abstractions

Tunlet




Performance Model



Measure point
Performance model
Tuning point
Performance parameters
Performance functions
Application





Actor
Event
Variable
Value
Attribute
Abstractions
Actors
Process_1
Variables
Values
Process_2
Process_3
Data a,b,c,d...
...
int i
Data a,b,c,d...
...
int i
Data d...
...
Res f_1(Data d)
{
...
}
g_1(Data d,int x)
{
...
}
h_1(Data e)
{
...
}
...
...
f_i(Data r, Data r1)
{
...
}
g_j(Data r)
{
...
}
main()
{
...
r=f_1(a)
...
f_i(c,d)
...
}
main()
{
...
g_1(b,i)
...
g_j(d)
...
}
main()
{
...
h_1()
...
}
Events
Methodology
1.
To provide a performance model (PM)
1.
2.
2.
To understand the performance model
1.
3.
Mainly the performance parameters
To interpret the PM in the application
1.
2.
4.
Pre-existing model
Ad hoc model
Identifying the events
Identifying the variables and values
To identify the actors in the application
Methodology II

Events




Variables and Values




Function
Entry or Exit
Attributes
Variable, parameter or result
Name
Data Type
Actor






Name
Class
Exe
Min/Max
Completion Condition
Attributes
Process_3
Data d...
...
h_1(Data e)
{
...
}
h_3()
{//final processing
//in the iteration
...
}
main()
{
while(!end)
{
...
h_1(x)
...
h_3()
}
}
Methodology II

Events




Variables and Values




Function
Entry or Exit
Attributes
Variable, parameter or result
Name
Data Type
Actor






Name
Class
Exe
Min/Max
Completion Condition
Attributes
Process_3
Data d...
...
h_1(Data e)
{
...
}
h_3()
{//final processing
//in the iteration
...
}
main()
{
while(!end)
{
...
h_1(x)
...
h_3()
}
}
Methodology II

Events




Variables and Values




Function
Entry or Exit
Attributes
Variable, parameter or result
Name
Data Type
Actor






Name
Class
Exe
Min/Max
Completion Condition
Attributes
Process_3
Data d...
...
h_1(Data e)
{
...
}
Data h_3()
{//final processing
//in the iteration
...
}
main()
{
while(!end)
{
...
h_1(x)
...
h_3()
}
}
Methodology II

Events




Variables and Values




Function
Entry or Exit
Attributes
Variable, parameter or result
Name
Data Type
Actor






Name
Class
Exe
Min/Max
Completion Condition
Attributes
Process_3
Data d...
...
h_1(Data e)
{
...
}
h_3()
{//final processing
//in the iteration
...
}
main()
{
while(!end)
{
...
h_1(x)
...
h_3()
}
}
Automatic development of Tunlets
Performance Model
Application
Parameters
p1, p 2 ... pi
Mathematical Model
f1 (pm,...,pn) ... fk (pm,...,pn)
Model Evaluation
r1 ... rk
Abstractions
Tunlet Specification
Measure Points
p1, p2 ... pi
Performance Functions
f1 ... fj
Tuning Actions/Points
a1 ... ak
tp1 ... tph
Formalize using our
Tunlet Specification Language
Tunlet Specification Language
What should be included?
Analyzer
Tunlet
Tunle
Tunlet
t
name:
Performance
model
Measure
points
comment:
Tuning
points/actions
Measure points
What,
where?
How?
Performance functions
What?
When?
Where?
Tuning points
Tunlet Specification Language
Tunlet
name:
Analyzer
comment:
Tunle
Tunlet
t
Performance
model
Measure
points
Tuning
points/actions
What?
where?
How?
What?
When?
Where?
Measure points
variables
actors
events
iteration info
performance params.
Performance functions
Tuning points
Tunlet Specification Language
Tunlet
name:
Analyzer
comment:
Tunle
Tunlet
t
Performance
model
Measure
points
Tuning
points/actions
What?
where?
Measure points
Performance functions
f1()
How?
…
What?
When?
Where?
fn()
Tuning points
Tunlet Specification Language
Tunlet
name:
Analyzer
comment:
Tunle
Tunlet
t
Performance
model
Measure
points
Tuning
points/actions
What?
where?
Measure points
Performance functions
How?
Tuning points
What?
When?
Where?
point1
…
pointn
Tunlet Specification Language
Analyzer
Tunlet
Tunle
Tunlet
t
name:
Performance
model
Measure
points
comment:
Tuning
points/actions
Measure points
What,
where?
How?
Performance functions
What?
When?
Where?
Tuning points
Tunlet Generation
<Tunlet name=“” comment=“” />
Tunlet
name:
<Measure points>
…
comment:
</Measure points>
Flex + DOM
Measure points
<Performance functions>
…
…
Performance functions
</Performance functions>
…
<Tuning points>
…
Tuning points
…
</Tuning points>
XSLT
Tunlet.h
Tunlet.cpp
Stats.h
Stats.cpp
Outline

Introduction




Automatic Development of Tunlets






MATE
Tunlets
Our work
Motivation
Abstractions and Methodology
Tunlet Specification Language
Tunlet Generator
Use Case
Conclusions
Example: number of workers

Framework + MATE

Define the tunlet basing
on the classes of the
framework.
Analyzer
Analyzer
Tunle
Tunlet
t
Performance
Model
Measure
points
Tuning
points/
actions

Adapt the
framework to
allow tuning of
the applications
via MATE
Example: number of workers

Framework + MATE

Define the tunlet basing
on the classes of the
framework.
(

*
V

Tc
)
Nopt 
Where...
tl = latency
λ = inverse bandwidth
V = data volume
Tc= computing time
Analyzer
Analyzer
Tunle
Tunlet
t
Performance
Model
Measure
points
tl
Tuning
points/
actions

Adapt the
framework to
allow tuning of
the applications
via MATE
Example: number of workers

Framework + MATE

Analyzer
Analyzer
Performance
Model
Measure
points
Events
Variables
• Entry(Computing)
• argvData
• Exit(Computing)
• ResSize
• Exit(iteration)
tl
Tunle
Tunlet
t
Define the tunlet basing
on the classes of the
framework.
• Entry(iteration)
Nopt  ( *V  Tc )
Tuning
points/
actions
Actors
• Master
• Worker

Adapt the
framework to
allow tuning of
the applications
via MATE
Example: number of workers

Framework + MATE

Define the tunlet basing
on the classes of the
framework.
Analyzer
Analyzer
Nopt  ( *V  Tc )
tl
Tunle
Tunlet
t
Performance
Model
Measure
points
Tuning
points/
actions

Adapt the
framework to
allow tuning of
the applications
via MATE
Example: number of workers

Framework + MATE

Define the tunlet basing
on the classes of the
framework.
Analyzer
Analyzer
Nopt  ( *V  Tc )
tl
Tunle
Tunlet
t
Performance
Model
Measure
points
Tuning
points/
actions
Variable
• Nopt

Adapt the
framework to
allow tuning of
the applications
via MATE
Example: number of workers

Framework + MATE

Define the tunlet basing
on the classes of the
framework.
Analyzer
Analyzer
Nopt  ( *V  Tc )
tl
Tunle
Tunlet
t
Performance
Model
Measure
points
Tuning
points/
actions

Adapt the
framework to
allow tuning of
the applications
via MATE
Number of workers: Specification
Tunlet
name:numworkers
comment:tunlet to tune the
number of workers
Measure points
variables
argvData
ResSize
nopt
events
IterationStarts
IterationFinishes
WStartsT
WFinishesT
actors
master
worker
performance model parameters
n
tl
lambda
Vt
Ct
Performance Functions
int pf()
{return (int)sqrt((lambda*Vt+Ct)/tl);}
Tuning Points
nopt
Outline

Introduction




Automatic Development of Tunlets






MATE
Tunlets
Our work
Motivation
Abstractions and Methodology
Tunlet Specification Language
Tunlet Generator
Use Case
Conclusions
Conclusions

We defined/developed:



Methodology to define tunlets
Tunlet Specification Language
Automatic Tunlet Generator
In this way, we make MATE (dynamicautomatic tuning) easier and transparent to
the user.
Automatic Performance Tuning:
Automatic Development of Tunlets
Paola Caymes Scutari
Thank you…