Optimización automática de
programas
Tema 4: Evaluación parcial offline
4.1. Conceptos básicos
4.2. Binding-time analysis (BTA)
4.3. Incluyendo anotaciones
4.4. Algoritmo de especialización
4.5. Unfolding
Optimización automática de programas (OAP)
Germán Vidal
1
4.1. Conceptos básicos
• Objetivo del tema:
 definir
un evaluador parcial offline para un lenguaje
funcional de primer orden sencillo (un subconjunto de
Scheme)
• La ventaja de considerar programas Scheme (o Lisp) es
que el parsing es muy sencillo
 cada
elemento del lenguaje va precedido por una “etiqueta”,
e.g., call, if, quote, etc
• Asumimos que la ejecución del programa siempre
comienza con una llamada a la primera función
 la
llamada “goal function” (como main en C)
Optimización automática de programas (OAP)
Germán Vidal
2
Sintaxis
<Program> ::= (<Equation> ... <Equation>)
<Equation> ::=
(define (<FuncName> <VarList>) <Expr>)
<VarList> ::= <Var> ... <Var>
<Expr>
::= <Constant>
| <Var>
| (if <Expr> <Expr> <Expr>)
| (call <FuncName> <ArgList>)
| (<Op> <ArgList>)
<ArgList> ::= <Expr> ... <Expr>
<Constant> ::= <Numeral> | (quote <Value>)
<Op>
::= car | cdr | cons | = | + | ...
Optimización automática de programas (OAP)
Germán Vidal
3
Puntos del programa y divisiones
• Puntos del programa
 cada
nombre de función representa un “punto del
programa”
• División
 clasificación
de cada parámetro de una función
como estático o dinámico
 puede ser monovariante (una división por función)
o polivariante (más de una división por función)
 consideraremos divisiones monovariantes
(las polivariantes se podrían simular creando copias
de las funciones)
Optimización automática de programas (OAP)
Germán Vidal
4
Congruencia
• Decimos que una división es congruente si
 el
valor de un parámetro estático viene determinado
únicamente por parámetros estáticos
 si un parámetro depende al menos de un parámetro
dinámico, entonces debe ser también dinámico
Optimización automática de programas (OAP)
Germán Vidal
5
Especialización de puntos del programa
• Puntos del programa especializados
nombran (f,vs), donde f es el nombre original
de la función y vs la lista de parámetros estáticos
 se
a
menudo se crean también versiones especializadas
para (if e1 e2 e3) si e1 es dinámico
Optimización automática de programas (OAP)
Germán Vidal
6
Compresión de transiciones
• La “compresión de transiciones” se corresponde
con el desplegado de una función (unfolding)
 puede
ser “on-the-fly” o
 como un post-proceso
• En cualquier caso, se debe evitar:
 unfolding
infinito
 duplicación de código o computaciones
 producir más llamadas residuales de las necesarias
Optimización automática de programas (OAP)
Germán Vidal
7
Estrategias para el unfolding on-the-fly
• No unfolding
 pobre
especialización, ya que todas las llamadas a
función se consideran dinámicas
• Desplegar sólo las llamadas a función cuyos
argumentos sean todos estáticos
 buenos
resultados, aunque sigue habiendo riesgo de
no terminación…
Elegimos esta opción
Optimización automática de programas (OAP)
Germán Vidal
8
Binding-time analysis
• Proceso:
 toma
un programa y la división para la función
principal y devuelve una división congruente para
todas las funciones del programa
• Se define como una instancia del marco de
interpretación abstracta
abstracto: {S,D}
 S: valor estático
 D: valor dinámico
 Dominio
Optimización automática de programas (OAP)
Germán Vidal
9
Anotaciones
• Generamos anotaciones a partir del las divisiones
 la
división nos dice si un parámetro es estático o
dinámico
 las anotaciones nos dicen cómo debe evaluarse cada
expresión del programa
• En realidad ambas cosas representan la misma
información
 es
decir, las anotaciones no son realmente necesarias,
pero simplifican el proceso de evaluación parcial
• División congruente  anotación consistente
Optimización automática de programas (OAP)
Germán Vidal
10
Anotaciones: sintaxis
• Para expresar las anotaciones se suele emplear un
lenguaje a dos niveles
 se
crean dos versiones de cada construcción del
lenguaje (condicional, llamada a función, etc)
 la versión estática se emplea para indicar que debe
evaluarse en tiempo de evaluación parcial
 la versión dinámica se emplea para indicar que la
expresión debe debe “residualizarse” (continuando
con la evaluación parcial de los argumentos)
Optimización automática de programas (OAP)
Germán Vidal
11
4.2. Binding-Time Analysis (BTA)
• Sólo monovariante
 i.e.,
una división para cada función
• Basado en interpretación abstracta
 dominio
abstracto: {S,D}
• Datos de entrada:
(define (f1 x11 ... x1a1) e1)
...
(define (fn xn1 ... xnan) en)
y
τ1 (binding-times para f1)
Optimización automática de programas (OAP)
Germán Vidal
12
Dominios y órdenes
• Dominios:
t  BindingTime
  BTEnv
div  Monodivision
= {S,D}
= [BindingTime]
= FuncName  BTEnv
• Órdenes:
 sobre
BindingTime:
t ≤ t’  t = S o t = t’ (≤: menos dinámico)
 sobre
BTEnv:
(s1,...,sn) ≤ (t1,...tn)  si ≤ ti
 sobre
i=1,...,n
divisiones:
div1 ≤ div2  div1(f) ≤ div2(f) para toda f
Optimización automática de programas (OAP)
Germán Vidal
13
Objetivo del análisis
• Encontrar la división
 congruente
 menos
dinámica (con el orden ≤)
• Pensad que, por ejemplo, la división
divi = [D,D,…,D]
siempre es congruente (pero no sirve para nada)
• Usaremos el lub :
S  S = S
S  D = D  S = D  D = D
(y su extensión a BTEnv y divisiones)
Optimización automática de programas (OAP)
Germán Vidal
14
Funciones
• Funciones del análisis:
Bv[[e]]: BTEnv  FuncName  BTEnv
dada
una expresión, un BTEnv y un nombre de
función, nos dice cuál debería ser el BTEnv de
dicha función de acuerdo a las llamadas que
aparecen en la expresión
Be[[e]]: BTEnv  BindingTime
dada
una expresión y un BTEnv, nos dice si la
expresión es estática o dinámica
Optimización automática de programas (OAP)
Germán Vidal
15
Función Bv[[e]]
Bv[[c]]  g = (S,...,S)
Bv[[xj]]  g = (S,...,S)
Bv[[if e1 e2 e3]]  g = Bv[[e1]]  g
 Bv[[e2]]  g  Bv[[e3]]  g
Bv[[call f e1 ... en]]  g =
t  (Be[[e1]],...,Be[[en]]]) if f=g
t
if f ≠g
where t = Bv[[e1]]  g ... Bv[[en]]  g
Bv[[op e1 ... en]]  g =
Bv[[e1]]  g  ...  Bv[[en]]  g
Optimización automática de programas (OAP)
Germán Vidal
16
Función Be[[e]]
Be[[c]]  = S
Be[[xj]]  = tj where  = (t1,..., tn)
Be[[if e1 e2 e3]] 
= Be[[e1]]   Be[[e2]]   Be[[e3]] 
Be[[call f e1 ... en]] 
= Be[[e1]]  ... Be[[en]] 
Be[[op e1 ... en]] 
= Be[[e1]]   ...  Be[[en]] 
Optimización automática de programas (OAP)
Germán Vidal
17
El requerimiento de congruencia
• Se debe cumplir:
hay alguna llamada a una función g cuyo
argumento n es dinámico, entonces el parámetro n de
g debe ser dinámico:
(div g) = Ui=1,…,n Bv[[ei]](div fi) g
donde f1,…,fn son las funciones del programa y
e1,…,en son las partes derechas
 si
• Generalizando:
(div fk) = Ui=1,…,n Bv[[ei]](div fi) fk
para k = 1,…,n
Optimización automática de programas (OAP)
Germán Vidal
18
Algoritmo BTA
• Sirve para obtener la “mejor” división congruente
(es decir, la menos dinámica)
• Proceso iterativo: div0 ≤ div1 ≤ div2 ≤ …
(1) Inicio:
div0 = [f1  , f2  (S,…,S),…,fn  (S,…,S)]
(2) Computamos divj:
Ui=1,…,n Bv[[ei]](divj-1 fi) fk, k = 1,…,n
(3) Si divj = divj-1  STOP
si no  vuelta al paso (2)
Optimización automática de programas (OAP)
Germán Vidal
19
Algoritmo BTA
• La terminación está garantizada…
 ¿por
que?
• OJO: hay un error en el libro:
 la
función f1 es una excepción:
(divj f1) =

U
Ui=1,…,n Bv[[ei]](divj-1 fi) f1
Optimización automática de programas (OAP)
Germán Vidal
20
Ejercicio 5.1 (a)
• Calculad el resultado del BTA para el programa
(define (power x n)
(if (= n 0)
1
(* x (call power x (- n 1)))
)
)
con x dinámica y n estática
Optimización automática de programas (OAP)
Germán Vidal
21
4.3. Incluyendo anotaciones
• Empleamos una sintaxis a 2 niveles:
<Expr> ::= <Constant>
| <Var>
| (ifs <Expr> <Expr> <Expr>)
| (ifd <Expr> <Expr> <Expr>)
| (calls <FuncName> <SDArgList>)
| (calld <FuncName> <SDArgList>)
| (<Op>s <ArgList>)
| (<Op>d <ArgList>)
| (lift <Expr>)
<SDArgList> ::= <ArgList> ... <ArgList>
Optimización automática de programas (OAP)
Germán Vidal
22
De divisiones a anotaciones (1)
• Realizamos los siguientes pasos:
 cada
función
(define (f x1 ... xa) e)
 se
tranforma en
(define (f (xs1 ... xsm) (xd1 ... xdk)) eann)
 donde
son los parámetros estáticos,
 (xd1 ... xdk) son los parámetros dinámicos y
 eann es el cuerpo de la función anotado
 (xs1 ... xsm)
Optimización automática de programas (OAP)
Germán Vidal
23
De divisiones a anotaciones (2)
• La expresión anotada eann se obtiene así:
 llamadas
a función (call g e1 ... ea):
 (calls g (e1 … ea) ()) si todos los args son estáticos
 (calld g (es1 … esm) (ed1 … edk)) en otro caso
 condicionales (if e1 e2 e3):
 (ifs e1 e2 e3) si e1 es estático
 (ifd e1 e2 e3) si e1 es dinámico
 operaciones (op e1 … en):
 (ops e1 … en) si e1 … en son todos estáticos
 (opd e1 … en) en otro caso
Optimización automática de programas (OAP)
Germán Vidal
24
De divisiones a anotaciones (3)
• ¿Cuando hay que usar el nuevo operador lift?
e es una expresión estática que aparece en un
“contexto dinámico”, e.g.:
 cuando
los argumentos de un calld / opd / ifd
las alternativas de un ifs que está dentro de un contexto
dinámico
el cuerpo de la función principal
el cuerpo de una función con al menos un parámetro
dinámico
…
 en
estos casos, reemplazamos e con (lift e)
Optimización automática de programas (OAP)
Germán Vidal
25
Ejercicio 5.1 (b)
• Anotad el programa
(define (power x n)
(if (= n 0)
1
(* x (call power x (- n 1)))
)
)
• (define (power (n) (x)) // Lista de parametros (S) (D)
•
(ifs (=s n 0) // Be n es S // el igual es estatico tambien
•
1
•
(*d x (calld power (-s n 1) (x)))))
empleando la información obtenida en el BTA del
Ejercicio 5.1 (a)
Optimización automática de programas (OAP)
Germán Vidal
26
4.4. Algoritmo de especialización
• Datos de entrada:
programa
anotado
valores de los parámetros estáticos de f1
• El algoritmo se basa en tres funciones:
 specialize:
inicialización
 complete: nivel “global” (proceso iterativo)
 reduce: nivel “local” (reducción simbólica)
Optimización automática de programas (OAP)
Germán Vidal
27
función specialize
specialize pgm vs =
let
(define (f1 _ _) : _) = pgm
in
complete [(f1 vs)] [] pgm
Optimización automática de programas (OAP)
Germán Vidal
28
función complete
complete pending marked pgm =
if pending==[] then []
else
let (f vs) ‘in’ pending
(define (f xs xd) e) = lookup f pgm
evs = reduce e (xs++xd,vs++xd) pgm
nmarked = (f vs) : marked
npending = pending
U (successors evs) – nmarked
newdef = define ((f,vs) xd) evs)
in newdef : complete npending nmarked pgm
Optimización automática de programas (OAP)
Germán Vidal
29
función reduce (1)
reduce e env pgm =
case e of
Number n => n
Quote c => c
Var x => lookup x env
ifs e1 e2 e3 => if (reduce e1 env pgm)
then (reduce e2 env pgm)
else (reduce e3 env pgm)
ifd e1 e2 e3 => ’if (reduce e1 env pgm)
then (reduce e2 env pgm)
else (reduce e3 env pgm)
Optimización automática de programas (OAP)
Germán Vidal
30
función reduce (2)
reduce e env pgm =
case e of
...
calls f es ed =>
let (define (f xs xd) ef) = lookup f pgm
res = reducelist (es++ed) env pgm
in reduce ef (xs++xd,res) pgm
calld f es ed => let (es’++ed’) =
reducelist (es++ed) env pgm
in ’call (f,es’) ed’
Optimización automática de programas (OAP)
Germán Vidal
31
función reduce (3)
reduce e env pgm =
case e of
...
ops es =>
let res = reducelist es env pgm
in op res
opd es =>
let res = reducelist es env pgm
in ’op res
lift e’ => ’quote (reduce e’ env pgm)
Optimización automática de programas (OAP)
Germán Vidal
32
Ejercicio 5.1 (c)
• Obtener la versión especializada del programa del
Ejercicio 5.1 (a) usando el programa anotado del
Ejercicio 5.1 (b) y el valor n=3
Optimización automática de programas (OAP)
Germán Vidal
33
4.5. Unfolding
• Tipos de unfolding:
on-the-fly:
realizamos el desplegado de
(algunas) llamadas en la función reduce
post-proceso: reduce nunca realiza el
desplegado de una llamada a función (es decir,
no existe el caso calls),
Optimización automática de programas (OAP)
Germán Vidal
34
Unfolding on-the-fly
• Permite obtener programas más
especializados (y menos funciones
residuales)
• Pero se corre un mayor riesgo de que el
proceso no termine…
• Ejemplo:
(power,3) x = x * x * x * 1
Optimización automática de programas (OAP)
Germán Vidal
35
Unfolding como post-proceso
• Suele haber mucho menos riesgo de no
terminación
• Pero los programas están menos especializados y
tienen más reglas residuales…
• Ejemplo:
(power,3)
(power,2)
(power,1)
(power,0)
x
x
x
x
=
=
=
=
x * (power,2) x
x * (power,1) x
x * (power,0) x
1
• A partir de aquí el post-proceso tratará de
obtener:
(power,3) x = x * x * x * 1
Optimización automática de programas (OAP)
Germán Vidal
36
Estrategias unfolding on-the-fly
• No unfolding
 seguro,
pero muy poco preciso
• Desplegar sólo las llamadas que tengan únicamente
argumentos estáticos
 suele
terminar, pero no siempre; buenos resultados en la mayor
parte de los casos
• Uso de un wfo/wqo sobre argumentos estáticos
 termina
en el 99% de los casos; mejores resultados!
• Desplegar las llamadas que no estén dentro de un if
dinámico
 muy
buenos resultados en ejemplos “realistas”, no hay
garantías de terminación
Optimización automática de programas (OAP)
Germán Vidal
37
Ejercicio 5.2 (a)
• Obtened la especialización del programa
(define (ack m n)
(if (= m 0)
(+ n 1)
(if (= n 0)
(ack (- m 1) 1)
(ack (- m 1) (ack m (- n 1)))
)))
con m estática (m=2) y n dinámica
(usamos la estrategia de unfolding de reduce)
Optimización automática de programas (OAP)
Germán Vidal
38
Ejercicio 5.2 (b)
• ¿Qué problema tiene la estrategia de unfolding
on-the-fly empleada?
 Determina
una estrategia de unfolding que de un
resultado mejor…
 Especializa de nuevo el programa usando dicha
estrategia
• Supongamos que ahora especializamos el
programa con m dinámica y n estática
 Explica
por qué un BTA da resultados tan
innecesariamente malos
 Esboza una posible solución…
Optimización automática de programas (OAP)
Germán Vidal
39
Descargar

Javascript & DHTML