Método Específico de la compilación dinámica mediante regresión logística

Método Específico de la compilación dinámica mediante regresión logística
John Cavazos Michael F. P. O'Boyle
Miembro del HiPEAC
Instituto de Informática de Sistemas Arquitectura ( ICSA) , Facultad de Informática
Universidad de Edimburgo , Reino Unido
fjcavazos , mobg@inf.ed.ac.uk
abstracto
La determinación de la mejor serie de optimizaciones para aplicar a un programa de
ha sido un problema de larga data para los autores de compiladores . Para reducir
la complejidad de esta tarea, los enfoques existentes suelen aplicar el
mismo conjunto de optimizaciones a todos los procedimientos dentro de un programa, sin
lo que respecta a su estructura particular . En este trabajo se desarrolla un nuevo
enfoque c método especi ? que selecciona automáticamente las mejores optimizaciones
en una base por método dentro de un compilador dinámico . nuestro
enfoque utiliza la técnica de la máquina de aprendizaje de la regresión logística
para derivar automáticamente un modelo predictivo que determina qué
optimizaciones de aplicar sobre la base de las características de un método . Esta técnica
se ha implementado en el compilador JIT Jikes RVM Java. uso
este enfoque reduce el tiempo total de ejecución promedio de la
SPECjvm98 puntos de referencia en un 29 %. Cuando se aplica la misma heurística
al conjunto de pruebas DaCapo + , obtenemos un promedio del 33%
reducción sobre el ajuste O2 nivel predeterminado .
Categorías y Asunto Descriptores D.3 [Software ] : Programación
lenguas ; D.3.4 [ Lenguajes de programación ]: Procesadores ? ?
Compiladores , Optimización ; I.2.6 [ inteligencia artificial ] : Aprendizaje ? ?
inducción
Condiciones generales de rendimiento , Experimentación, Idiomas
Palabras clave de optimización del compilador , aprendizaje de máquina, Logística
Regresión , Java, Jikes RVM
1 . introducción
Seleccionar el mejor conjunto de optimizaciones para un programa ha sido la
enfoque de la optimización de la investigación compilación durante décadas. Ha sido
el objetivo a largo plazo de los autores de compiladores , para desarrollar una secuencia de
fases de optimización que analizar y , en su caso , transformar
el programa de modo que se reduce el tiempo de ejecución . Determinar
el mejor conjunto de optimizaciones y su orden , sin embargo , es notoriamente
dif ? culto . De hecho , Cooper et al . [ 9 , 2 ] han demostrado que la
mejor de pedido es dependiente del programa y que cualquier secuencia que sea
mejor para un programa es poco probable que sea la mejor para otro . ¿Qué
que nos gustaría es un mecanismo que selecciona automáticamente la mejor
secuencia de optimización para un programa en particular .
En la optimización de los compiladores , es una práctica estándar para aplicar el mismo
conjunto de optimizaciones fases en el mismo orden en cada procedimiento
El permiso para hacer copias digitales o impresas de parte o la totalidad de este trabajo para personal o
uso en el aula se otorguen sin cuota , siempre que las copias no se realicen o se distribuyan
por favor ? t o comercial ventaja y que las copias tienen esta notificación y la cita completa
en la página primera ? . Para copiar, volver a publicar , incluirlo en servidores o redistribuir
listas, se requiere especificación previa? permisos c y / o una tasa.
OOPSLA'06 22 de octubre ? 26 , 2006 , Portland , Oregon, EE.UU. .
derechos de autor
c 2006 ACM 1-59593-348-4/06/0010 . . . $ 5.00
o método dentro de un programa . Sin embargo, así como el mejor conjunto de
optimizaciones varía de un programa a otro [ 2 , 18 ] , se muestra
que el mejor conjunto de optimizaciones varía dentro de un programa, es decir , es
- método específico . Queremos un sistema que selecciona el mejor conjunto de
optimizaciones para porciones individuales de un programa , en lugar de la
mismo conjunto de todo un programa .
En este trabajo se desarrolla una nueva técnica c método especi ? Que automáticamente
selecciona el mejor conjunto de optimizaciones para las diferentes secciones
de un programa . Desarrollamos esta técnica dentro del entorno Jikes RVM
y determinar automáticamente los mejores optimizaciones en un
por base del método . En lugar de desarrollar una técnica artesanal
Para lograr esto, se hace uso de una técnica básica de aprendizaje automático
conocida como regresión logística [ 4 ] para determinar de forma automática lo que
optimizaciones son los mejores para cada método. Esto se logra mediante la formación
la técnica de ? ine en un conjunto de datos de entrenamiento que luego de forma automática
aprende una heurística de optimización .
Técnicas basadas en el aprendizaje de la máquina han recibido recientemente considerable
atención como un medio de optimización de rápido desarrollo
heurística [ 20 , 7 ] . Por desgracia , se han visto limitadas en gran medida
para sintonizar una optimización individual a menudo con resultados decepcionantes .
Por ejemplo , aunque Stephenson et al . [ 20 ] fueron capaces de
construir una heurística asignación del registro de forma automática utilizando la máquina
el aprendizaje , la heurística sólo fue capaz de conseguir una mejora modesta
sobre el registro del asignador heurística sintonizado a mano existente.
A lo mejor de nuestro conocimiento, este es el papel de primera ? De forma automática
aprender una estrategia general de compilación para porciones individuales
de un programa . Esto significa que nuestro esquema aprende qué optimizaciones
para aplicar en lugar de afinar heurística locales y lo hace en
un entorno de compilación dinámica . Además, se muestra signi ? Peralte
mejora del rendimiento a través de una recopilación de buena ingeniería existentes
sistema . Utilizando nuestro enfoque, para la máxima optimización
O2 establecer dentro Jikes RVM , reducimos el tiempo de ejecución total de un 29%
en promedio para el conjunto de referencia SPECjvm98 . esto aumenta
al 33 % en un conjunto de puntos de referencia incluidos DaCapo , SPECjbb2000 ,
y ipsixql . Este resultado es particularmente impresionante , al considerar
que el reciente trabajo en el desarrollo de modelos de predicción de la mano de
seleccione optimizaciones [ 24 ] logra mejoras en el rendimiento de
menos de 3 % en promedio .
El trabajo se organiza de la siguiente manera . Sección 2 proporciona la motivación
por qué optimizaciones ? c método especi- superan actual
enfoques . A continuación, en la sección 3 de una descripción de la forma en
regresión logística estándar puede saber si se aplica o no una
en particular la optimización de un método en particular . Sección 4 describe luego
la infraestructura experimental y metodología que es
seguido en el apartado 5 de una presentación de los resultados. Sección 6 proporciona
un análisis de por qué funciona de regresión logística. Sección 7 da
una breve reseña de la labor relacionada y es seguido en la Sección 8 por
algunas observaciones finales .
? ?
? ? ? ? ? ? ? ?
? ? ? ?
?
? ? ? ?


? ? ?
? ? ? ? ? ? ?
? ? ?
? ? ? ? ? ? ?
? ?
? ? ? ? ? ? ? ?
? ? ? ?
?
? ? ? ?


? ? ?
? ? ? ? ? ? ?
? ? ?
? ? ? ? ? ? ?
? ?
? ? ? ? ? ? ? ?
? ? ? ?
?
? ? ? ?


? ? ?
? ? ? ? ? ? ?
? ? ?
? ? ? ? ? ? ?
?
? ? ?
? ? ?
? ? ?
? ? ?
? ? ?
? ? ?
? ? ?
? ? ?
? ?
?
? ? ? ? ? ? "? ? #
$ ? ? ? % ? ? ? # ? $ ? $ ? ? ? % ? ? ? # ? $ ? $ ? ? ? % ? ? ? # ? $ ?
Figura 1 . Los resultados de la aplicación de la mejor configuración para cada método en relación con el ajuste por defecto para cada uno de los diferentes niveles de optimización .
El mejor programa para cada método se encuentra a través de la exploración exhaustiva de los niveles de optimización O0 y O1 . Para O2 nivel de optimización ,
tomamos la mejor configuración para cada método desde 1000 ajustes aleatorios evaluados. Tiempo total de ejecución = tiempo de compilación dinámica de funcionamiento +
tiempo .
2 . motivación
En esta sección se muestra que la selección de la mejor serie de optimizaciones en un
por base método tiene el potencial de signi ? cativamente mejorar el total de
tiempo de programas compilados dinámicamente en ejecución.
Potencial Se realizó un experimento inicial para determinar el alcance
en que los diferentes optimizaciones afectan el tiempo total de ejecución
de una aplicación compilada y ejecutada por el Jikes RVM Java JIT
compilador. Para cada método dentro de cada punto de referencia SPECjvm98 ,
hemos aplicado muchos ajustes de optimización diferentes y grabamos el
ajuste que dio el mejor tiempo total de ejecución en función de cada método.
Como Jikes RVM tiene múltiples niveles de optimización , hemos realizado
este experimento para los niveles de optimización O0 , O1 y O2 y el informe de
los resultados aquí .
Debido a la forma en que Jikes RVM se construye , no es posible
para cambiar arbitrariamente el orden en el que se aplican las optimizaciones .
En cambio, en contra? Ne nuestra búsqueda a sólo habilitar y deshabilitar las optimizaciones.
Por niveles de optimización O0 y O1 , que se aplican 4 y
9 optimizaciones por defecto , probamos todas las posibles enumeraciones de
estas optimizaciones , es decir , 24 = 16 ; 29 = 512 , respectivamente . Como el nivel
O2 se aplica 20 optimizaciones una enumeración exhaustiva de los 220
ajustes no era posible, en lugar enumeramos al azar 1000
diferentes contextos y grabaron su rendimiento. La Tabla 1 muestra
las optimizaciones que se aplican de forma predeterminada para estos tres diferentes
niveles de optimización .
Una vez que se han encontrado los mejores ajustes para cada método, a continuación, de forma dinámica
compilado y corrió cada programa utilizando la mejor optimización
ajustes para cada método . Figura 1 presenta los resultados de la selección
el mejor conjunto de optimizaciones en cada nivel de optimización en un per
base método para cada uno de los puntos de referencia SPECjvm98 . Como compilación
tiempo es dinámico y parte de la que en general el tiempo de ejecución
mostrar dos resultados de rendimiento : el tiempo y el tiempo total de ejecución. Correr
tiempo indica el punto de referencia veces seguidas sin compilación
tiempo, mientras que el tiempo total indica que los tiempos que se ejecuta con la compilación.
Los resultados se representan en relación con la heurística predeterminada existente
que debe aplicarse a todas las optimizaciones agrupados en que la optimización
nivel ( ver Tabla 1 ) .
En el caso de nivel de optimización O0 , no es , en promedio, un 4 %
reducción del tiempo total disponible y esto reduce al 2 % para O1 .
Sin embargo , en el caso de la optimización de nivel más alto de O2 , hay una
mejora del rendimiento signi ? peralte disponible. Selección de la derecha
optimización para cada método da una reducción media del 19% en
el tiempo de ejecución total.
Una misma talla no sirve para todos En cuanto a los resultados , se puede concluir
que los ajustes por defecto son pobres y que existe potencialmente
otro entorno que no es el método especi- ? c y sería un buen desempeño
en todos los otros puntos de referencia .
Para probar esta enumeramos todas las diferentes combinaciones posibles
de los 4 optimizaciones que se utilizan de forma predeterminada para la optimización
nivel O0 a intentar ? nd una configuración fija que si se aplica a todos los
métodos podrían proporcionar una mejora del rendimiento en el actual
default.1 De los 16 ajustes de optimización diferentes enumeramos ,
no lo hicimos ? nd una sola estafa ? guración que realizó fuera
el valor predeterminado actual . El valor predeterminado actual es , de hecho, la óptima? Ja
ajuste de los puntos de referencia SPECjvm98 .
Ahora, en la sección anterior hemos sido capaces de superar a la optimización
O0 para varios de los puntos de referencia que dan SPECjvm98
una reducción media en el tiempo de ejecución total de un 4%. Por lo tanto , una optimización
ajuste de sintonía para cada método es mejor que la óptima
? ja establecer a través de todo el programa. En otras palabras , para la
1 El nivel de optimización O0 es una optimización importante ya que es la ? Rst y
más utilizado ajuste de optimización durante la compilación de adaptación.
SPECjvm98 puntos de referencia un método especi ? Estrategia de c debe superar
cualquier estrategia c programa especi ? .
Conclusión En nuestros experimentos no lo hicimos ? Nd un único global
estableciendo que signi cativamente ? optimización mejora el rendimiento
del compilador de optimización JIT Jikes RVM . Sin embargo , la selección de un
diverso ajuste para cada método de optimización muestra el potencial
para entregar signi ? cativas ganancias .
Por tanto, el reto es desarrollar un modelo predictivo que
puede analizar cada método y seleccionar el conjunto de optimización que se
reducir el tiempo total de ejecución . Como estamos considerando JIT dinámico
compilación , la sobrecarga de esta heurística debe ser pequeño de otro modo
que compense los bene ? ts .
Un enfoque es artesanal una heurística basada en la experimentación
y análisis . Esto no es deseable por dos razones . En primer lugar , lo hará
ser una tarea ardua y Jikes RVM especi ? c . En segundo lugar , si la plataforma
se a los cambios, toda la puesta a punto de la heurística tendría
que ser repetido . En su lugar se utiliza un enfoque basado en el aprendizaje de máquinas
que aprende automáticamente una buena heurística . Esto tiene la ventaja
siendo de una técnica genérica que fácilmente los puertos a través de plataformas .
3 . enfoque
En esta sección se ofrece una descripción detallada de la forma de regresión logística
máquina de aprendizaje basado se utiliza para determinar una buena optimización
heurística para cada uno de los niveles de optimización O0 , O1 , O2 , y adaptativa
dentro Jikes RVM . La primera sección ? Esbozan las diferentes subactividades
que tendrá lugar cuando el aprendizaje y la implementación de una heurística
Esto es seguido por secciones que describen cómo generamos formación
datos , cómo extraer características de los métodos , y cómo estas características
y los datos de formación nos permiten aprender de una heurística que determina
si debe o no aplicar un conjunto de optimizaciones. Esto es seguido por
un ejemplo que muestra cómo se utiliza nuestro heurística aprendido en la práctica.
La figura 2 resume nuestro esquema .
3.1 Información general
Hay dos fases distintas , la capacitación y la implementación. formación
se produce una vez, fuera de línea, ? ? en la fábrica ? y es equivalente al tiempo
dedicado por los autores de compiladores que diseñan e implementan su optimización
heurística . El despliegue es el acto de aplicar la heurística
en tiempo de compilación dinámica . Como cualquier heurística aprendido incurre dinámico
general de compilación , es imperativo que sea tan barato
posible evaluar de otra manera su bene ejecución? t queda compensado
por su coste .
Dentro de la fase de entrenamiento , nosotros? Rst generamos una formación adecuada
los datos en función de si estamos tratando de mejorar la O0 , O1, o
Niveles de optimización de O2 dentro Jikes RVM . Los datos de la formación es
generado al azar por la aplicación de diferentes ajustes de optimización para
cada método dentro de cada programa de formación y la grabación de su
rendimiento en un método de base por el uso ? timers.We ne - grano también
derivar una breve descripción (llamado vector de características ) de cada método
para que más adelante podamos construir una función que toma el vector de características como
de entrada y proporciona el conjunto de optimizaciones que se debe aplicar
como salida.
Este modelo predictivo de una vez aprendido se instala en la Jikes
Compilador de RVM y utilizado en tiempo de ejecución como una heurística de optimización.
Las siguientes secciones describen estas etapas con mayor detalle
3.2 Generación de datos de entrenamiento
Nuestro objetivo es desarrollar una función, f , el cual, dado un nuevo método
descrito como el vector de características x , da salida un vector c de 1s y 0s cuyos
elementos determinan si se aplica o no la correspondiente
optimización:
f ( x) = c
1 . Entrenamiento ? ? En la fábrica ?
( a) Generar resultados de los datos de entrenamiento para O0 , O1, O2 o
i . Instrumento cada método de sincronización con las llamadas
ii . Para cada método de seleccionar al azar un conjunto de optimizaciones
y aplicar
iii . Grabar compilación dinámica , correr, y la ejecución total del
vez por forma
( b ) Generar características del método
i . Para cada método de calcular cada elemento de la característica
vector
ii . Función de grabación de vectores para cada método
( c ) Aprender un modelo que clasifica ? ES Características
i . Para cada método de seleccionar los ajustes de optimización
dentro del 1% de las mejores
ii . Generar una tabla donde cada vector de características es grabada
asociado con sus mejores ajustes de optimización .
iii . Para cada ajuste de optimización c determinar un probabilístico
función f que indica si un vector de características x debe
tener este conjunto de optimización o no.
iv . Salida este conjunto de funciones como la heurística aprendido
2 . despliegue
( a) Instale heurística aprendido en Jikes RVM
( b ) Para cada método compilado dinámicamente
i . Desde bytecodes generan un vector de características
ii . Utilice heurística para determinar qué optimizaciones para aplicar
y aplicarlos
Figura 2 . técnica general
Antes de que podamos hacer esto , tenemos que saber cómo los diferentes optimización
ajustes afectan el rendimiento. Por lo tanto, tratamos muchos diferentes
ajustes de optimización para ver cómo cada opción afecta al rendimiento
de cada método .
Para el problema de la optimización de los métodos de Java , podemos buscar el
todo el espacio de optimizaciones si el número de optimizaciones no es
prohibitivamente grande . En el caso de niveles de optimización O0 y O1 ,
Hay solamente 4 y 9 optimizaciones activadas de forma predeterminada que permite
enumeración exhaustiva . Medimos el tiempo para compilar un método
e instrumentado cada método con un contador de tiempo ne - grano ? para grabar la
cantidad de tiempo dedicado a ejecutar ese método. Por nivel de optimización
O2 , no podríamos enumerar exhaustiva toda la optimización posible
combinaciones ( O2 tiene 20 optimizaciones ) , por lo que para este nivel que elijamos
para evaluar un conjunto de 1000 configuraciones generadas aleatoriamente . Las optimizaciones
controlamos en cada nivel de optimización con nuestra logística
regresores se describen en la Tabla 1 .
Los mejores ajustes se registraron en un vector C para cada método .
El tamaño de c corresponde al número de optimizaciones disponibles
en cada nivel , es decir , tamaño 4 para O0 , 9 para O1 , y 20 para O2 .
3.3 Extracción de características
Una vez que tenemos ejemplos de buenos ajustes de optimización para diferentes
métodos que nos gustaría se correlacionan los ajustes con las características
de un método . Para ello es necesario describir cada método en
un suf ? forma suficientemente conciso , para permitir el aprendizaje de máquina estándar
técnicas a emplear .
Determinación de las propiedades de un método que predicen una optimización
mejora es dif ? tarea de culto. A medida que nos movemos en un dyOptimizations
significado
O0 Nivel de optimización
RAMA OPTS vueltas bajas en algunas optimizaciones simples sucursales
PROP constante de propagación constante Local
CSE local eliminación de subexpresiones comunes
PEDIDOS CÓDIGO Reordena los bloques básicos
O1 Nivel de optimización
COPIA PROP propagación copia local
Recursividad de cola recursión de cola
DIVISIÓN STATIC bloque básico división estática
RAMA OPTS MED optimizaciones sucursales más agresivos
OPTS SIMPLE Tipo BAJA apoyo, revisar los límites elim , deadcode
elim , etc
O2 Nivel de optimización
Ratos EN UNTILS intenta convertir a ratos en untils
BUCLE UNROLL Loop desenrollando
RAMA OPTS ALTOS optimizaciones sucursales Aún más agresivos
SIMPLE OPTS ALTA pase adicional de optimizaciones simples
ELIM CARGA eliminación de carga
RAMA REDUNDANT rama redundante eliminación
SSA Introduzca formulario SSA y realizar optimizaciones SSA
Plegado Expresión FOLD EXPRESIÓN
Propagación copia GLOBAL COPIA PROP Global
GLOBAL eliminación CSE subexpresiones comunes globales
COALESCE Coalescing etapa, requiere el formulario SSA
Tabla 1 . En esta tabla se describen todas las optimizaciones investigados.
Estas optimizaciones son todos de forma predeterminada para cada uno de los diferentes
niveles de optimización . Las optimizaciones en O1 nivel incluyen todos
optimizaciones a nivel O0 y optimizaciones en el O2 nivel incluyen
todas las optimizaciones a nivel O1 y O0 .
entorno de compilación namic elegimos características que son simples
para calcular y que nos pareció que eran pertinentes . Informática éstos
características requiere un solo pase el código de bytes del método . nosotros
calcular características después de procesos en línea se ha realizado .
La Tabla 2 muestra las 26 características utilizadas para describir cada método . la
valores de cada función será una entrada en la función 26 - elemento
vector x asociado con cada método . Los ? Rst 2 entradas son enteros
los valores de ? Ning el tamaño del código y los datos del método . la
próximo 6 son propiedades booleanas simples ( representados mediante 0 o 1 ) de
el método . Las funciones restantes son simplemente el porcentaje de
bytecodes que pertenecen a una categoría en particular . (por ejemplo , 30 % de cargas , 22 %
? punto otante , 5 % puntos de rendimiento , etc.)
Como un ejemplo , el vector de características para el método
bloque compress.Compressor.cl () es el siguiente vector .
[ 108 , 25, 0 , 0 , 0 , 0 , 1 , 0 ; 0:2 ; 0:0 ; 0:0 ; 0:0 ; 0:0 ; 0:0
Doce y doce ; 0:0 ; 0:08 ; 0:0 ; 0:0 ; 0:0 ; 0:2 ; doce y treinta y dos ; 0:08 ; 0:0 ]
En otras palabras , hay 108 bytes en este método , 25 octetos
asignado para los locales , etc Nosotros no hacemos ninguna afirmación de que este es el mejor
conjunto de características para describir un método. Es posible que un completamente
conjunto diferente de características daría un mejor rendimiento.
Sin embargo, nuestros regresores logisitic son capaces de aprender de forma automática
qué características son más importantes para cada uno de los diferentes optimizaciones .
Y, puesto que el cálculo de todas las características es muy barato (por lo general
menos de 1 % de tiempo de compilación de un método ) no hay necesidad de ? ltro
características a cabo sin importancia . El regresor logística lo hace automáticamente.
Los investigadores han ideado diferentes características [ 1 , 7 , 6 , 15 , 20 ] que
funcionado bien en otros problemas de optimización. Por ejemplo , de lunes a
Característica Significado
bytecodes Número de códigos de bytes en el
método
espacio lugareños Número de canales asignados para los locales
Método de sincronización se sincroniza
Método excepciones tiene el manejo de excepciones
código
Método de la hoja es una hoja (no contiene
llamadas )
? nal método se declara ? nal
Método privado se declara privada
Método estático se declara static
Categoría Fracción de bytecodes que ...
aload , astore montón de matriz y Tiendas
primitivo, siempre son cálculos primitivos o largas
(por ejemplo, iadd , fadd )
Compare son Compares (por ejemplo, LCMP , dcmpl )
rama son ramas (adelante /
atrás / cond / uncond )
JSR son un JSR
interruptor son un interruptor
poner / obtener son una PUT o GET
invocar son una INVOCACIÓN
nueva es un nuevo
arraylength son un ArrayLength
athrow , checkcast , monitorear son una Athrow , checkcast , o el monitor
múltiples newArray son un multi newArray
simple, largo, real son un simple, largas o Bienes Conversiones
Tabla 2 . Características de un método. Para reducir la longitud de la mesa
varias (diferentes) características han sido colocados en grupos lógicos.
sifort et al . [ 15 ] enfoque en la estructura de bucle como características en la predicción
si para desenrollar o no . En trabajos futuros, vamos a explorar el uso de otros
características tales como los presentados por Georges et al. [ 11 ] en combinación
con las características que se utilizó en este estudio .
3.4 El aprendizaje de un clasificador utilizando la regresión logística
Ahora estamos en la etapa en que tenemos, para cada método , una característica
vector x y un vector c que corresponde a los mejores ajustes para
ese método en particular . Dado un vector de características de un nuevo método
x deseamos desarrollar una función, f , que devuelve un buen conjunto de
c optimizaciones para aplicar a la misma.
clasificación
Nuestra tarea ahora se puede expresar como una clasifi cación problema : ¿un determinado
del método de vector de características x deberíamos aplicar una optimización especial
o no? Dado un n = 26 espacio dimensional de características , queremos
? ND de una curva o hiperplano que separa los puntos en cada uno
optimización está activada de aquellos en los que está apagado . Para ilustrar
esto, ver el ejemplo simple 2D muestra en la Figura 3 , donde cada uno
punto corresponde a un vector de características y deseamos ? nd una línea
que los separa en clases .
Aquí la línea B + XTW = 0 es el límite de decisión , en
los ejemplos un lado están clasi ? ed como 1s , y por el otro, 0s .
El parámetro b se limita a desplazar la frontera de decisión por una constante
cantidad . La orientación de la frontera de decisión se determina por
W que representa la normal a la hiperplano .
Sin embargo , en la práctica no existe una separación limpia entre
puntos . En su lugar , queremos asociar a cada punto una probabilidad
de si se debe aplicar una optimización . La técnica más simple
que logra esta es la regresión logística [ 4 ] y es un probabilístico
W 1 1
1 1
1
1
1
1
0
0
0
0
0
0
0
Figura 3 . La frontera de decisión separador lineal ( línea continua) . para
dos datos dimensionales , el límite de decisión es una línea .
extensión a la regresión lineal . Esto nos proporciona una ? Dencia estafa
medir en cuanto a lo bien que nuestra ? clasi caci on es .
regresión Logística
Deseamos determinar una función f que da la probabilidad de que
un método en particular debe tener un conjunto de optimizaciones habilitadas.
Tenemos un conjunto de hasta 20 optimizaciones para considerar , c, pero
para facilitar la presentación que inicialmente consideramos el caso de la determinación
la probabilidad de que sólo una optimización de C está habilitada , es decir , c = 1 .
Formalmente esto se expresa como :
p ( C = 1JX ) = f ( x ; w ) ( 1 )
donde p (c = 1JX ) es la probabilidad de que , dado un vector de características
x , la optimización de C está activado o encendido y f es alguna función
parametrizada por el peso w . Dado que la función f representa un
probabilidad , debe estar delimitado entre 0 y 1 .
Una de las opciones estándar de la función es la función sigmoidea ,
s ( y) = 1 = ( 1 + exp ( 􀀀 y) ) . Cuando el argumento de la función sigmoide
es positivo , la probabilidad de que el punto de entrada y pertenece a la clase
1 está por encima de 0,5 . Cuanto mayor es el valor del argumento , y, es decir, cuanto mayor es
la probabilidad de que sea clasi ? ed como teniendo el ajuste de optimización
c habilitado . Del mismo modo , los grandes valores negativos de x se implican que c es
discapacitados . ? Clasi caci basado en la regresión logística se describe como :
p ( C = 1JX ) = s ( b + XTW ) ( 2 )
donde b es una constante escalar , y w es un vector de pesos . Selección
los pesos w permite la selección de la frontera que separa
orientación y un mecanismo para indicar cómo mella en contra? estamos en este
clasificación de frontera ? catiónico. Cuanto mayor sea el peso , ? Dent más aire
estamos en el ? clasi caci on .
formación
Dado que la función sigmoide es una buena para clasificar los datos ,
ahora tenemos que derivar o aprenderlo. Por lo tanto, dado el conjunto de datos de entrenamiento D,
recopilada durante la anterior búsqueda exhaustiva o al azar , ¿cómo puede
ajustamos o aprendemos los pesos para obtener una buena clasificación ? catión ? suponiendo
que cada uno de los puntos de datos P ha sido dibujado de forma independiente
la probabilidad de que los datos pertenecen a una clase C Se da particular
por una fórmula estándar [ 4 ] :
P (D ) =
POJ
= 1
p ( c j jxj ) =
POJ
= 1
( p ( C = 1JX j ) ) CJ ? 1 􀀀 p ( C = 1jxj ) ?
1 􀀀 cj
( 3 )
donde xj es la j-ésima ( j 2 1 ; ::: ; P) vector de características seleccionado de
los datos de entrenamiento y cj es su mejor optimización correspondiente
ajuste de dicho vector de características . Si p ( D ) = 1, entonces tenemos un perfecto
? clasi caci y los datos son claramente separados . En la práctica debido a la
datos ruidoso que no logrará una ? clasi caci perfecto, pero en su lugar
deseen obtener la mejor clasificación posible ? catiónico. Si ajustamos los pesos
para maximizar p ( D) esto le dará la mejor hiperplano decisión.
Cada una de estas probabilidades P es una función del vector de peso
W , por lo que queremos seleccione w en el fin de maximizar P (D ) . Como los valores de
de p son pequeñas , es común [ 4 ] para trabajar con la L = LogP ( D) para
evitar errores de redondeo :
= L
på
j = 1
cj log p (c = 1JX j ) + ( 1 􀀀 cj ) log ? 1 􀀀 p ( c = 1JX j ) ? ( 4 )
y tratar de maximizar su lugar. ( L Maximizar = log (P ( D ) ) es
equivalente a maximizar P (D ) ) .
En el modelo de regresión logística , deseamos , por lo tanto ? Nd el
pesos W para maximizar :
L ( w , b) =
på
j = 1
registros cj (b + w T xj ) + ( 1 􀀀 cj ) log ? 1 􀀀 s ( b + w T xj ) ?
( 5 )
Desafortunadamente , esto no se puede lograr analíticamente y es normalmente
logrado mediante el uso de un solver iterativo basado en gradiente de ascenso ,
sobre la base de las derivadas parciales de L.2 se da El gradiente
por la siguiente ecuación :
NWL =
på
j = 1
( c j 􀀀 s (x j; w ) ) XJ ( 6 )
La derivada con respecto a los sesgos es la siguiente :
dl
db
=
på
j = 1
( c j 􀀀 s ( x j ; w ) ) ( 7 )
En otras palabras , seleccione un valor de w y actualizarla en la dirección de
ascenso. Si NW es la derivada parcial con respecto al vector w
luego actualizamos nuestros valores de w y b de la siguiente manera :
WNEW = w + hÑwL ( 8 )
bnew = b + h
dl
db
( 9 )
donde h , la tasa de aprendizaje es un pequeño escalar elegido suficientemente pequeño para
asegurar la convergencia del método .
Esto se repite hasta que no haya más cambios y tenemos
alcanzado el máximo. Al final de este proceso iterativo que tenemos
un juego de pesos y el desplazamiento que ofrece la mejor ? clasi caci on en un
determinado conjunto de entradas de entrenamiento. Se puede entonces ser utilizado como una función de la cual
determina para un conjunto de entrada de cuenta la probabilidad de que si una
optimización debe estar encendido o apagado.
3.5 despliegue
El paso NAL ? Implica la instalación de la función heurística en la
compilador y su uso durante la compilación dinámica. Cada método
que es compilado por el compilador de optimización se considera una posible
candidato para todas las optimizaciones . Calculamos características para el
método . Si la función heurística dice que debemos optimizar un método
con una optimización en particular , lo hacemos . Como una ilustración , cuando
aplicando el regresor logística para el vector de características de
compress.Compressor.cl bloque ( ) , devuelve un valor de
[ 1 ; 0 ; 1 ; 1 ; 0 ; 0 ; 0 ; 1 ; 1 ; 1 ; 1 ; 1 ; 1 ; 1 ; 1 ; 0 ; 1 ; 1 ; 1 ; 0 ]
que denota cuál de los 20 optimizaciones para aplicar con la asociada
probabilidades
2 como S0 ( x ) = s ( x ) ( 1 􀀀 s ( x ) ) ) , las derivadas parciales son fáciles de calcular
Descripción del Programa
comprimir versión Java de 129.compress de ESP 95
sistema experto jess Java
db construye y opera en una base de datos in-memory
fuente javac Java para compilador de bytecode en JDK 1.0.2
mpegaudio Decodifica un audio MPEG- 3 ? le
raytrace Un trazador de rayos que trabaja en una escena con un dinosaurio
jack A Java generador de análisis con el análisis léxico
Tabla 3 . Características de los puntos de referencia SPECjvm98 .
[ 0:7 ; 0:3 ; 0:8 ; 0:7 ; 0:4 ; 0:3 ; 0:1 ; 0:9 ; 0:7 ; 0:6 ;
0:6 ; 0:7 ; 0:9 ; 0:6 ; 0:6 ; 0:2 ; 0:6 ; 0:7 ; 0:7 ; 0:3 ] :
Esto significa que con una rama probabilidad de 70 % OPCNES BAJO
debe aplicarse y que con un 30 % de probabilidad de
PROP CONSTANTE debe aplicarse . En otras palabras se aplican rama
optimizaciones , pero no se aplican de propagación constante local para este
método .
4 . Infraestructura + Metodología
Aquí se describe la plataforma y los puntos de referencia utilizados, así como la
metodología empleada en nuestros experimentos .
4.1 Plataforma
Ponemos en práctica nuestra heurística aprendido en la investigación Jikes Virtual
Máquina [ 3 ] versión 2.3.3 para una arquitectura Intel x86. El Intel
procesador es una estación de trabajo de Red Hat Linux 2.6 GHz Pentium 4 basados
con 500M de RAM y una memoria caché de 512KB L1. Utilizamos los FastAdaptiveGenMS
Con? guración de Jikes RVM , lo que indica que el núcleo
máquina virtual fue compilado por el compilador de optimización , que un
sistema de optimización adaptativo está incluido en la máquina virtual ,
y se utilizó la marca de barrido recolector de basura generacional.
4.2 Puntos de referencia
Examinamos dos suites de benchmarks. El ? Primera es la SPECjvm98
puntos de referencia [ 19 ], que se ejecuta con el mayor tamaño del conjunto de datos
( denominado 100 ) . Estos puntos de referencia se describen en la Tabla 3 .
El segundo conjunto de programas consta de 5 programas de la
DaCapo conjunto de pruebas [ 5 ] , ipsixql y SPECjbb2000 y son
se describe en la Tabla 4 . Este conjunto de pruebas DaCapo es una colección
de los programas que se han utilizado para el vario rendimiento de Java diferente
estudios agregan en una suite de rendimiento . Corrimos el
DaCapo puntos de referencia en virtud de su configuración por defecto. También incluimos una
programa llamado ipsixql que realiza consultas XML y una modi ? ed
versión de SPECjbb2000 (por lo tanto , que se conoce como pseudojbb ) que
realiza un número? jado de las transacciones . Nos referimos a estos 7 puntos de referencia
colectivamente como DaCapo + .
4.3 Niveles de optimización
Corrimos experimentos en cada uno de los tres optimización diferente
niveles , es decir, O0 , O1 , y O2 , así como la compilación de adaptación
escenario . Cuando se ejecuta en un nivel de optimización en particular
compilamos todos los métodos utilizando sólo las optimizaciones disponibles en
ese nivel. El regresor logística elige qué subconjunto de estas optimizaciones
para aplicar a cada método está compilando .
A pesar de que los especímenes ? Entrenar mente sólo para el O0 , O1 y O2
niveles , también se evaluó la hipótesis adaptativa que utiliza cada
de estos tres niveles . Bajo el escenario de adaptación, todo de forma dinámica
métodos cargados se ? rst compilados por la línea de base no optimizador
compilador que convierte bytecodes directamente a código máquina sin
realizar ninguna optimización . El código resultante es lento , pero el
tiempos de compilación son rápidos. El sistema de optimización adaptativa,
Descripción del Programa
antlr Analiza uno o más gramática ? les y genera una
analizador y analizador léxico para cada
fop Toma un XSL -FO ? le, lo analiza y formatea ella,
generar un PDF? le
jython Interpreta una serie de programas en Python
pmd Analiza un conjunto de clases Java para una gama de fuentes
problemas de código
ps lee e interpreta un archivo PostScript ? le
ipsixql Realiza consultas en un documento XML persistente
? ed pseudojbb SPECjbb2000 modi para realizar una cantidad jos ?
del trabajo
Tabla 4 . Características de los puntos de referencia + DaCapo .
utiliza en línea profesional? ling para descubrir el subconjunto de los métodos en que un signi
? se está gastando la cantidad no puede de tiempo en marcha del programa. estos
? ? caliente ? métodos son entonces vuelven a compilar con el compilador de optimización .
Estos métodos son ? Rst compilado a nivel de optimización O0 , pero si
que siguen siendo importantes que se vuelven a compilar a nivel O1 y
? Finalmente a nivel de O2 si se justifica . Los niveles de optimización individuales
maquillaje el compilador de adaptación y por lo tanto es importante para sintonizar
estos niveles individuales correctamente. Cuando se utiliza la regresión logística bajo
el escenario de adaptación, se utilizó un regresor logística capacitado para
cada uno de los tres niveles de optimización diferentes .
4.4 Medición
Además de los diferentes escenarios del compilador también consideramos
dos criterios de optimización diferentes, a saber : el tiempo total y el funcionamiento
tiempo . El tiempo total es una combinación de funcionamiento y tiempo de compilación .
Como parte de la compilación es el tiempo de ejecución total de dinámica
compiladores y luego optimizando de tiempo total a tratar de minimizar su
costo combinado .
Sin embargo , cuando el programa es probable que se ejecute durante un considerable
longitud de tiempo , puede ser preferible para el usuario para reducir el
tiempo de funcionamiento a expensas de potencialmente mayor tiempo de compilación .
Por lo tanto, incluye el tiempo de funcionamiento para nuestros puntos de referencia que es
el tiempo de ejecución del programa sin tiempo de compilación. cada
punto de referencia se llevó a cabo varias veces y la ejecución mínimo
Se ha informado de tiempo . 3
4.5 Metodología de evaluación
Como es práctica habitual , aprendemos más de un conjunto de puntos de referencia ,
comúnmente conocida en la literatura de aprendizaje máquina que el
conjunto de entrenamiento. A continuación, probamos el rendimiento de nuestra heurística sintonizado
sobre otro? ? invisible ? serie de puntos de referencia , que no hemos sintonizado
para , conocido como el banco de pruebas. Estos se consiguen en dos por separado
experimentos .











veces.
para





















Por lo tanto



decisión .




5 . Resultados











El costo de




Los resultados














promedio.




respectivamente .











promedio.



















tiempo .
Por lo tanto ,





Los resultados son



















? ?
? ? ? ? ? ? ? ?
? ? ? ?
?
? ? ? ?


? ? ?
? ? ? ? ? ? ?
? ? ?
? ? ? ? ? ? ?
?
? ? ?
? ? ?
? ? ?
? ? ?
? ? ?
? ? ?
? ? ?
? ? ?
? ? ?
?
? ? ?
 
#

? ?
? ? ? ? ? ? ? ?
? ? ? ?
?
? ? ? ?


? ? ?
? ? ? ? ? ? ?
? ? ?
? ? ? ? ? ? ?
?
? ? ?
? ? ?
? ? ?
? ? ?
? ? ?
? ? ?
? ? ?
? ? ?
? ? ?
?
? ? ?
 
#

? ?
? ? ? ? ? ? ? ?
? ? ? ?
?
? ? ? ?


? ? ?
? ? ? ? ? ? ?
? ? ?
? ? ? ? ? ? ?
?
? ? ?
? ? ?
? ? ?
? ? ?
? ? ?
? ? ?
? ? ?
? ? ?
? ? ?
?
? ? ?
 
#

? ?
? ? ? ? ? ? ? ?
? ? ? ?
?
? ? ? ?


? ? ?
? ? ? ? ? ? ?
? ? ?
? ? ? ? ? ? ?
?
? ? ?
? ? ?
? ? ?
? ? ?
? ? ?
? ? ?
? ? ?
? ? ?
? ? ?
?
? ? ?
 ? ? ? ? ?
? ? ? ? ? ?

Figura 4 .








En contraste ,









6 . discusión









? ?
? ? ?
? ? ? ? ? ?
?

? ?

? ? ? ?
? ? ? ?
? ? ? ?
? ? ? ? ? ? ?
? ? ? ? ?
?
?
? ? ?
? ? ?
? ? ?
? ? ?
? ? ?
? ? ?
? ?


?
? ? ?
# ?
Y ? ? ? ? ? ? ' ?
?

? ?
? ? ?
? ? ? ? ? ?
?

? ?

? ? ? ?
? ? ? ?
? ? ? ?
? ? ? ? ? ? ?
? ? ? ? ?
?
?
? ? ?
? ? ?
? ? ?
? ? ?
? ? ?
? ? ?
? ?


?
? ? ?
? ? ?
# ?
Y ? ? ? ? ? ? ' ?
?

? ?
? ? ?
? ? ? ? ? ?
?

? ?

? ? ? ?
? ? ? ?
? ? ? ?
? ? ? ? ? ? ?
? ? ? ? ?
?
?
? ? ?
? ? ?
? ? ?
? ? ?
? ? ?
? ? ?
? ?


?
? ? ?
# ?
Y ? ? ? ? ? ? ' ?
?

? ?
? ? ?
? ? ? ? ? ?
?

? ?
? ?
?
? ? ? ?
? ? ? ?
? ? ? ? ? ?

? ? ? ? ? ?
?
? ? ?
? ? ?
? ? ?
? ? ?
? ? ?
? ? ?
? ? ?
? ?

?
? ? ?
"




Figura 5 .



punto de referencia .






esto indica








Esto es debido a la

















































Tabla 7 .

7 .










heurística .

En contraste ,
En segundo lugar,
















grupo .










ellos










Ellos mostraron








orden.










Cooper et al .


programa .





este







aplicado .














Sin embargo ,




este






Sin embargo ,









ajuste.








modelos .


decisiones .










auditoría.


ellos


fases .









8 . Conclusiones






Para nuestra










9 . Agradecimientos

además,



Referencias

uso







2004 .




IBM











2006 .


aprendizaje .






























en













IEEE

estadístico



2004 .




aprendizaje .





2005 .






En Actas de la


Prensa .

...