ALEXANDRE DOS SANTOS MIGNON ML4JIT - UM ARCABOUC¸O PARA PESQUISA ´ COM APRENDIZADO DE MAQUINA EM COMPILADORES JIT Sa˜o Paulo 2017 ALEXANDRE DOS SANTOS MIGNON ML4JIT - UM ARCABOUC¸O PARA PESQUISA ´ COM APRENDIZADO DE MAQUINA EM COMPILADORES JIT Tese apresentada a` Escola Polit´ecnica da Universidade de S˜ao Paulo para obten¸ca˜o do T´ıtulo de Doutor em Ciˆencias. Sa˜o Paulo 2017 ALEXANDRE DOS SANTOS MIGNON ML4JIT - UM ARCABOUC¸O PARA PESQUISA ´ COM APRENDIZADO DE MAQUINA EM COMPILADORES JIT Tese apresentada a` Escola Polit´ecnica da Universidade de S˜ao Paulo para obten¸ca˜o do T´ıtulo de Doutor em Ciˆencias. ´ Area de Concentra¸ca˜o: Engenharia de Computa¸ca˜o e Sistemas Di- gitais Orientador: Prof. Dr. Ricardo Luis de Azevedo da Rocha Sa˜o Paulo 2017 Este exemplar foi revisado e corrigido em relação à versão original, sob responsabilidade única do autor e com a anuência de seu orientador. São Paulo, ______ de ____________________ de __________ Assinatura do autor: ________________________ Assinatura do orientador: ________________________ Catalogação-na-publicação Mignon, Alexandre dos Santos ML4JIT - Um Arcabouço para Pesquisa com Aprendizado de Máquina em Compiladores JIT / A. S. Mignon -- versão corr. -- São Paulo, 2017. 101 p. Tese (Doutorado) - Escola Politécnica da Universidade de São Paulo. Departamento de Engenharia de Computação e Sistemas Digitais. 1.Aprendizado de Máquina 2.Compiladores JIT 3.Otimização de Código I.Universidade de São Paulo. Escola Politécnica. Departamento de Engenharia de Computação e Sistemas Digitais II.t. RESUMO Determinar o melhor conjunto de otimiza¸co˜es para serem aplicadas a um programa tem sido o foco de pesquisas em otimiza¸ca˜o de compila¸c˜ao por d´ecadas. Em geral, o conjunto de otimiza¸co˜es ´e definido manualmente pelos desenvolvedores do compilador e aplicado a todos os programas. T´ecnicas de aprendizado de m´aquina supervisionado tˆem sido usadas para o desenvolvimento de heur´ısticas de otimiza¸c˜ao de c´odigo. Elas pretendem determinar o melhor conjunto de otimizac¸˜oes com o m´ınimo de interferˆencia humana. Este trabalho apresenta o ML4JIT, um arcabou¸co para pesquisa com aprendi- zado de m´aquina em compiladores JIT para a linguagem Java. O arcabou¸co permite que sejam realizadas pesquisas para encontrar uma melhor sintonia das otimiza¸co˜es espec´ıfica para cada m´etodo de um programa. Experimentos foram realizados para a valida¸ca˜o do arcabou¸co com o objetivo de verificar se com seu uso houve uma redu¸ca˜o no tempo de compila¸ca˜o dos m´etodos e tamb´em no tempo de execu¸c˜ao do programa. Palavras-Chave – otimiza¸ca˜o de co´digo, compiladores JIT, aprendizado de ma´quina. ABSTRACT Determining the best set of optimizations to be applied in a program has been the focusofresearchoncompileoptimizationfordecades. Ingeneral, thesetofoptimizationis manually defined by compiler developers and apply to all programs. Supervised machine learning techniques have been used for the development of code optimization heuristics. They intend to determine the best set of optimization with minimal human intervention. This work presents the ML4JIT, a framework for research with machine learning in JIT compilers for Java language. The framework allows research to be performed to better tunetheoptimizationsspecifictoeachmethodofaprogram. Experimentswereperformed forthevalidationoftheframeworkwiththeobjectiveofverifyingifitsusehadareduction in the compilation time of the methods and also in the execution time of the program. Keywords – code optimization, JIT compilers, machine learning. LISTA DE FIGURAS 1 Um compilador h´ıbrido. Adaptada de (AHO et al., 2006). . . . . . . . . . 23 2 Estrutura geral de um compilador com trˆes partes. Adaptada de (COO- PER; TORCZON, 2011). . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 3 M´odulos da estrutura de um compilador. Adaptada de (GRUNE et al., 2012). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 4 Cen´arios de compilac¸˜ao da Jikes RVM. Extra´ıda de (ARNOLD et al., 2000). 31 5 Processo de aprendizado ativo pool-based. Adaptada de (SETTLES, 2012). 37 6 Processo adaptado de aprendizado ativo para uso em compiladores. Adap- tada de (OGILVIE et al., 2017). . . . . . . . . . . . . . . . . . . . . . . . . 37 7 A interac¸˜ao entre o agente e o ambiente em aprendizado por refor¸co. . . . . 38 8 Rela¸c˜ao entre os componentes do arcabou¸co ML4JIT. . . . . . . . . . . . . 45 9 Principais recursos dispon´ıveis no ML4JIT. . . . . . . . . . . . . . . . . . . 45 10 Diagrama de estados do Sampler. . . . . . . . . . . . . . . . . . . . . . . . 51 11 Dinaˆmica operacional do agente. . . . . . . . . . . . . . . . . . . . . . . . . 62 12 Visa˜o geral da arquitetura do agente. . . . . . . . . . . . . . . . . . . . . . 62 13 Diagrama de classes do recurso Counter. . . . . . . . . . . . . . . . . . . . 63 14 Co´digo do m´etodo transform da classe CounterTransformer. . . . . . . . 64 15 Diagrama de classes do recurso Training. . . . . . . . . . . . . . . . . . . 64 16 Co´digo do m´etodo transform da classe TrainingTransformer. . . . . . . 65 17 Diagrama de classes do recurso Sampler. . . . . . . . . . . . . . . . . . . . 66 18 Co´digo do m´etodo transform da classe TrainingSamplingTransformer. . 67 19 Diagrama de classes do recurso Features Extractror. . . . . . . . . . . . 68 20 Arquitetura dos scripts. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 21 Diagrama da classes adicionadas e modificadas na Jikes RVM. . . . . . . . 71 22 Diagrama de classes da arquitetura proposta para aprendizado dinˆamico. . 73 23 Desempenho dos programas do benchmark JGF - Section 2 no n´ıvel de otimiza¸ca˜o O0 utilizando o classificador DecisionTreeClassifier. . . . . . . . 83 24 Desempenho dos programas do benchmark JGF - Section 2 no n´ıvel de otimiza¸ca˜o O0 utilizando o classificador KNeighborsClassifier. . . . . . . . 85 25 Desempenho dos programas do benchmark DaCapo no n´ıvel de otimizac¸˜ao O0 utilizando o classificador DecisionTreeClassifier. . . . . . . . . . . . . . 86 26 Desempenho dos programas do benchmark DaCapo no n´ıvel de otimizac¸˜ao O0 utilizando o classificador KNeighborsClassifier. . . . . . . . . . . . . . . 88 27 Desempenho dos programas do benchmark JGF - Section 2 no n´ıvel de otimiza¸ca˜o O1 utilizando o classificador DecisionTreeClassifier. . . . . . . . 89 28 Desempenho dos programas do benchmark JGF - Section 2 no n´ıvel de otimiza¸ca˜o O1 utilizando o classificador KNeighborsClassifier. . . . . . . . 91 29 Desempenho dos programas do benchmark DaCapo no n´ıvel de otimizac¸˜ao O1 utilizando o classificador DecisionTreeClassifier. . . . . . . . . . . . . . 92 30 Desempenho dos programas do benchmark DaCapo no n´ıvel de otimizac¸˜ao O1 utilizando o classificador KNeighborsClassifier. . . . . . . . . . . . . . . 94 LISTA DE TABELAS 1 Otimiza¸c˜oes da Jikes RVM. Extra´ıdas do help da Jikes RVM versa˜o 3.1.4. . 32 2 Conjunto de caracter´ısticas utilizadas para descrever um m´etodo. . . . . . 47 3 Parˆametros de configura¸ca˜o do agente. . . . . . . . . . . . . . . . . . . . . 53 4 Lista de nano-patterns apresentada em (SINGER et al., 2010). Os nomes em negrito foram adicionados em (MIGNON; ROCHA, 2017). . . . . . . . 57 5 Lista de padro˜es para a caracteriza¸ca˜o de m´etodos. . . . . . . . . . . . . . 58 6 Bibliotecas Python utilizadas no desenvolvimento e execu¸ca˜o dos scripts. . 78 7 Descri¸c˜ao dos programas do benchmark JGF - Section 2. Adaptada de (BULL et al., 2000). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 8 Descri¸c˜ao dos programas do benchmark DaCapo. . . . . . . . . . . . . . . 80 9 Otimiza¸co˜es da Jikes RVM utilizadas nos experimentos realizados. . . . . . 81 10 Informa¸co˜es retornadas pelos algoritmos de aprendizado de m´aquina utili- zados nos experimentos indicando quais otimiza¸co˜es devem ser habilitadas (1) ou desabilitadas (0) para o m´etodo SparseMatmult.test do programa Sparse do benchmark JGF - Section 2 no n´ıvel de otimiza¸c˜ao O0. . . . . . 82 11 Dados da mediana dos tempos de execuc¸˜ao e de compila¸c˜ao, em ms, dos programas do benchmark JGF - Section 2 no n´ıvel de otimiza¸c˜ao O0 uti- lizando o classificador DecisionTreeClassifier. A coluna ML apresenta a mediana dos tempos quando o programa foi executando com as heur´ısticas do algoritmo de aprendizado de ma´quina. A coluna STD ML apresenta o desvio padra˜o dessa mediana. A coluna REF apresenta a mediana dos tempos quando o programa foi executando com a configurac¸˜ao padra˜o. A coluna STD REF apresenta o desvio padra˜o dessa mediana. . . . . . . . . 83 12 Dados do desempenho dos programas do benchmark JGF - Section 2 no n´ıvel de otimizac¸˜ao O0 utilizando o classificador DecisionTreeClassifier. . . 83 13 Dados da mediana dos tempos de execuc¸˜ao e de compila¸c˜ao, em ms, dos programas do benchmark JGF - Section 2 no n´ıvel de otimiza¸ca˜o O0 utili- zando o classificador KNeighborsClassifier. A coluna ML apresenta a me- diana dos tempos quando o programa foi executando com as heur´ısticas do algoritmo de aprendizado de ma´quina. A coluna STD ML apresenta o desvio padra˜o dessa mediana. A coluna REF apresenta a mediana dos tempos quando o programa foi executando com a configurac¸˜ao padra˜o. A coluna STD REF apresenta o desvio padra˜o dessa mediana. . . . . . . . . 84 14 Dados do desempenho dos programas do benchmark JGF - Section 2 no n´ıvel de otimizac¸˜ao O0 utilizando o classificador KNeighborsClassifier. . . . 84 15 Dados da mediana dos tempos de execu¸c˜ao e de compila¸c˜ao, em ms, dos programas do benchmark DaCapo no n´ıvel de otimiza¸c˜ao O0 utilizando o classificador DecisionTreeClassifier. A coluna ML apresenta a mediana dos tempos quando o programa foi executando com as heur´ısticas do algoritmo de aprendizado de m´aquina. A coluna STD ML apresenta o desvio padr˜ao dessa mediana. A coluna REF apresenta a mediana dos tempos quando o programa foi executando com a configura¸ca˜o padra˜o. A coluna STD REF apresenta o desvio padra˜o dessa mediana. . . . . . . . . . . . . . . . . . . . 86 16 Dados do desempenho dos programas do benchmark DaCapo no n´ıvel de otimiza¸ca˜o O0 utilizando o classificador DecisionTreeClassifier. . . . . . . . 86 17 Dados da mediana dos tempos de execu¸c˜ao e de compila¸c˜ao, em ms, dos programas do benchmark DaCapo no n´ıvel de otimiza¸c˜ao O0 utilizando o classificador KNeighborsClassifier. A coluna ML apresenta a mediana dos tempos quando o programa foi executando com as heur´ısticas do algoritmo de aprendizado de m´aquina. A coluna STD ML apresenta o desvio padr˜ao dessa mediana. A coluna REF apresenta a mediana dos tempos quando o programa foi executando com a configura¸ca˜o padra˜o. A coluna STD REF apresenta o desvio padra˜o dessa mediana. . . . . . . . . . . . . . . . . . . . 87 18 Dados do desempenho dos programas do benchmark DaCapo no n´ıvel de otimiza¸ca˜o O0 utilizando o classificador KNeighborsClassifier. . . . . . . . 87