Optimización automática de programas



Descargar 20,11 Kb.
Fecha de conversión21.07.2017
Tamaño20,11 Kb.

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

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)

Sintaxis


  • ::= ( ... )
  • ::=
  • (define ( ) )
  • ::= ...
  • ::=
  • |
  • | (if )
  • | (call )
  • | ( )
  • ::= ...
  • ::= | (quote )
  • ::= car | cdr | cons | = | + | ...

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)

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

Especialización de puntos del programa

  • Puntos del programa especializados
    • se nombran (f,vs), donde f es el nombre original de la función y vs la lista de parámetros estáticos
    • a menudo se crean también versiones especializadas para (if e1 e2 e3) si e1 es dinámico

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:

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

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
    • Dominio abstracto: {S,D}
    • S: valor estático
    • D: valor dinámico

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

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)

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)

Dominios y órdenes

  • Dominios:
    • t  BindingTime = {S,D}
    •   BTEnv = [BindingTime]
    • div  Monodivision = FuncName  BTEnv
  • Órdenes:
    • sobre BindingTime:
    • t ≤ t’  t = S o t = t’ (≤: menos dinámico)
    • sobre BTEnv:
    • (s1,...,sn) ≤ (t1,...tn)  si ≤ ti i=1,...,n
    • sobre divisiones:
    • div1 ≤ div2  div1(f) ≤ div2(f) para toda f

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)

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

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

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]] 

El requerimiento de congruencia

  • Se debe cumplir:
    • si 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
  • Generalizando:
    • (div fk) = Ui=1,…,n Bv[[ei]](div fi) fk
    • para k = 1,…,n

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)

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

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

4.3. Incluyendo anotaciones

  • Empleamos una sintaxis a 2 niveles:
  • ::=
  • |
  • | (ifs )
  • | (ifd )
  • | (calls )
  • | (calld )
  • | (s )
  • | (d )
  • | (lift )
  • ::= ...

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
      • (xs1 ... xsm) son los parámetros estáticos,
      • (xd1 ... xdk) son los parámetros dinámicos y
      • eann es el cuerpo de la función anotado

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

De divisiones a anotaciones (3)

  • ¿Cuando hay que usar el nuevo operador lift?
    • cuando e es una expresión estática que aparece en un “contexto dinámico”, e.g.:
      • 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)

Ejercicio 5.1 (b)

  • Anotad el programa
    • (define (power x n)
    • (if (= n 0)
    • 1
    • (* x (call power x (- n 1)))
    • )
    • )
  • empleando la información obtenida en el BTA del Ejercicio 5.1 (a)

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)

función specialize

  • specialize pgm vs =
  • let
  • (define (f1 _ _) : _) = pgm
  • in
  • complete [(f1 vs)] [] pgm

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

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)

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
  • calls f es ed => let (es’++ed’) = reducelist (es++ed) env pgm
  • in ’call (f,es’) ed’

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)

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

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),

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

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) x = x * (power,2) x
    • (power,2) x = x * (power,1) x
    • (power,1) x = x * (power,0) x
    • (power,0) x = 1
  • A partir de aquí el post-proceso tratará de obtener:
    • (power,3) x = x * x * x * 1

Estrategias unfolding on-the-fly

  • No unfolding
  • 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

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)

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…


La base de datos está protegida por derechos de autor ©absta.info 2016
enviar mensaje

    Página principal