Reduzindo o Overhead Imposto pela Compilação Dinâmica

Reduzindo o Overhead Imposto pela CompilacaoDinamica

XI Mostra de Trabalhos de Informatica

Anderson Faustino, Maycon Sambinelli, Rodrigo Hubner

Universidade Estadual de Maringa

17 de setembro de 2009

Anderson Faustino, Maycon Sambinelli, Rodrigo Hubner Reduzindo o Overhead Imposto pela Compilacao Dinamica

Conteudo

Introducao

Motivacao

O Compilador YAPc

Sistema YAP+ Prolog

A Arquitetura do Compilador YAPc

O Novo Mecanismo de Compilacao Dinamica do YAP+ Prolog

Testes de Avaliacao

Conclusao


Introducao

Compiladores que geram codigo nativo dinamicamente, melhoramconsideravelmente o desempenho da aplicacao, mas incluem ooverhead em tempo de compilacao.

O objetivo deste trabalho e de minimizar o overhead imposto pelacompilacao dinamica, explorando arquiteturas multinucleo paraeste fim.


Motivacao

Prolog e uma linguagem declarativa amplamente utilizada eseu desempenho e um objeto de estudo muito importante;

Sistemas Prolog compilam para codigo nativo afim demelhorar o desempenho, o que pode ser caro, pois baseiam-sena analise global e/ou na intervencao do usuario;

E desenvolvido um trabalho a partir do YAP Prolog, o YAP+Prolog, que utiliza o compilador dinamico YAPc, afim deexplorar arquitetura multinucleo, focando um maiordesempenho principalmente de grandes aplicacoes;


O Compilador YAPc

Um compilador dinamico para Prolog;

Utiliza informacoes sobre os tipos dos dados;

Dois objetivos principais: Desempenho e Manutenabilidade;

Focar os componentes mais importantes do programa atravesde uma interpretacao previa, permite identificar caracterısticasimportantes afim de gerar um codigo optimizado;

A compilacao dinamica para Prolog e importante por doismotivos: Permite identificar regioes mais utilizadas nocodigo (hot-spots) e possibilita ter maiores informacoes sobreargumentos de cada procedimento (difıcil em uma linguagemnao tipada e com varias formas de uso).


Sistema YAP+ PrologCaracterısticas

Faz uso do compilador JIT;

Primeiro interpreta as clausulas em tempo de execucao edepois gera codigo nativo para as mais executadas;

A compilacao dinamica definir argumentos de um predicado edetermina quais partes da aplicacao devem ser otimizadas;

Um predicado invocado pela primeira vez e sempreinterpretado. Se executado frequentemente, ele e compilado eotimizado;

Processo de compilacao:


Sistema YAP+ PrologA Compilacao Dinamica

Para descobrir as oportunidades de compilacao, o sistema devedecidir:

Quando compilar - Determinar o tempo a ser esperado paraque as clausulas candidatas sejam compiladas;

O que compilar - E verificado a clausula cujo o contadoratingiu o limite. Como uma clausula pode ser muito simples,e verificado tambem a clausula que a chamou. Deve satisfazeras seguintes condicoes:

1o contador > MinInvocacoes;2o tamanho >= TamLimite;

Quais caminhos compilar - UItiliza-se uma tecnica baseadaem regioes, permitindo identificar as porcoes de codigos maisvisitadas em tempo de execucao, evitando a geracao decodigo fora das regioes selecionadas ate o codigo serrealmente executado.



E o compilador que quando acionado, gera o codigo nativo parapartes do programa que sao frequentementes executados. Suascaracterısticas sao:

Emprega algoritmos simples - Reduz pausas no processo decompilacao;

E adaptavel as caracterısticas do programa -Caracterısticas que determinam o fluxo de execucao entre asfases, para alcancar um bom desempenho;

Diminui as pausas do sistema de compilacao - Compilaapenas os caminhos executados;

Gera codigo compacto - Gera codigo nativo apenas para asregioes realmente executadas.



A representacao seguinte da arquitetura do compilador dividida emfront-end e back-end


Sistema YAP+ PrologO Novo Mecanismo de Compilacao Dinamica

Durante a execucao o interpretador verifica se para cadaclausula existe uma versao otimizada de acordo com oscriterios;

A otimizacao realizada e armazenada na area de codigosnativos, indicando que para o predicado atual existe umaversao otimizada;

A parte nao otimizada nao e descartada pois ainda podemocorrer depuracoes;

A execucao de um predicado e a sua compilacao que dainterpretacao da lugar a compilacao;


Sistema YAP+ PrologO Novo Mecanismo de Compilacao Dinamica

A arquitetura do sistema YAP+ possui os seguintes componentes:

Gerente de Fluxos. Gerencia a concorrencia de diferentesfluxos de execucao. Prove um mecanismo baseado e lockspara sincronizar os fluxos, motivo pelo qual nao e precisointerromper a execucao;

Motor de Execucao. Papel de executar todo o programa.Quando existe uma compilacao a ser realizada e ativado oMotor de Compilacao atraves de um sinal do sistema;

Motor de Compilacao. Compila as clausas indicadas.


YAP+ - Avaliacao

Programas utilizados para os testes de avaliacao:

append: Insere N elementos no inıcio de uma outra lista;

naive reverse: Inverte uma lista com N elementos;

zebra: quebra cabeca logico baseado em restricoes que eresolvido por busca exaustiva;

hanoi: Torre de hanoi contendo 3 pinos e N discos;

quick sort: Ordenacao de N elementos pelo metodo quicksort;

tak: Programa altamente recursivo, que e controlado poroperacoes inteiras.

Os teste foram realizados em uma maquina Intel Core 2 Duo 1.66Ghz com 2 Gb de memoria, rodando em Linux.


YAP+ versus YAP

Avaliacao com o objetivo de identificar a aceleracao obtida atravesde chamadas a codigo nativo. Configuracao utilizada:

Cadas programa e chamado 1000 vezes. Tempo de execucao:1000 x tempo do programa;

Tempo de execucao e a media entre 5 execucoes;

O limite para cada invocacao da compilacao dinamica foi de1.000 chamadas;

Todas as otimizacoes e o coletor de lixo estavam ligados.

Os testes foram realizados em uma maquina Intel Core 2 Duo 1.66Ghz com 2 Gb de memoria, rodando em Linux.


YAP+ versus YAP

Entradas para os programas:

Tempo de execucao dos programas em segundos e a aceleracaoobtida utilizando o compilador YAPc:


Impacto do YAPc no Ambiente de Execucao

Programas invocados uma vez e aumento das entradas. Diminui otempo de execucao e aumenta o de compilacao. Entradas:

Analisando o desempenho do YAP+:


Analise do Compilador YAPc

Tempo gasto pelo compilador em milissegundos, que variabastante dependendo das caracterısticas de cada programa:

O maior custo esta na fase de alocacao dos registradores queconsome entre 50,12% e 83,72% do tempo de compilacao.


Nova Analise dos Programas Testes

Testes realizados para o novo sistema YAP+ que explora asarquiteturas multinucleos com a mesma configuracao utilizada noultimo teste:

Explorar arquiteturas multinucleo reduz o impacto do sistema decompilacao no ambiente de execucao.


Conclusao

Como visto, para programas pequenos o YAP+ nem sempre obteveum desempenho melhor, pois programas pequenos acionam muitasvezes o sistema de compilacao.

A reestruturacao do sistema YAP+ possui a vantagem de explorararquiteturas emergentes e possiblitou avaliar situacoes crıticas parao sistema YAP+.


Technology

Reduzindo o Overhead Imposto pela Compilação Dinâmica