desempenho de sistemas de irrigação pivô central - LSCAD

GERAÇÃO DE BACK-END LLVM E EXPERIMENTOS COM GERAÇÃO DE
CÓDIGO PARA O PROCESSADOR ρ-VEX
Ricardo Espindola de Aguiar1 Ricardo Ribeiro dos Santos2
1
Aluno do Curso de Engenharia de Computação da UFMS, bolsista de Iniciação Científica CNPq – PIBIC
2012/13
2
Professor da UFMS, Faculdade de Computação; e-mail: [email protected]
Resumo: Este trabalho teve por objetivo analisar os impactos do algoritmo de escalonamento
de instruções e alocação de registradores baseado no isomorfismo de subgrafos, além de
validar e avaliar o back-end LLVM implementado para o processador ρ-vex. Para a análise do
algoritmo de isomorfismo de subgrafos, que foi implementado no back-end LLVM para o
processador MIPS, foi utilizado o simulador implementado sobre a linguagem de descrição de
processadores ArchC. A simulação dos programas gerados utilizando esse algoritmo foi
comparada com a dos programas gerados utilizando algoritmos clássicos presentes no LLVM,
greedy e linearscan. Para a validação e avaliação do back-end LLVM para ρ-vex foi utilizado
o conjunto de ferramentas para arquiteturas VLIW VEX Toolchain. A validação foi feita
comparando-se o valor de retorno dos programas gerados com os compiladores LLVM, GCC
e VEX C Compiler (presente no VEX Toolchain). A avaliação do back-end foi feita
comparando-se os programas gerados com o LLVM e VEX C Compiler. Os resultados dos
experimentos de análise do algoritmo de isomorfismo de subgrafos mostram um desempenho
similar dos programas gerados pelos três algoritmos, com pequeno ganho que se deve à
passagem de parâmetros utilizando registradores e utilização de registradores além da
definição da ABI. Os resultados dos experimentos com o back-end LLVM para o ρ-vex
mostram que a maioria dos programas tem desempenho inferior em relação ao VEX C
Compiler, pois este compilador gera código para arquiteturas VEX em geral, não
considerando as limitações que o processador ρ-vex tem em relação à ISA VEX. Já os casos
em que o LLVM tem desempenho superior ocorrem devido à taxa de OPI dos programas ser
maior que daqueles gerados com o VEX C Compiler.
Palavras-chave: isomorfismo de subgrafos, VLIW, experimentos
1. INTRODUÇÃO
A geração de código eficiente é um problema bastante conhecido das áreas de
compiladores e arquitetura de computadores. Um outro desafio é fornecer ferramentas que
possam gerar código para processadores. Assim, se faz necessário otimizar etapas dessas
ferramentas na geração de código, que no contexto deste trabalho, são o escalonamento de
instruções e alocação de registradores [3].
O escalonamento de instruções tem por objetivo atribuir operações do programa aos
recursos físicos do processador, de tal forma que este os execute em uma determinada ordem.
A alocação de registradores consiste em mapear os registradores virtuais nos
registradores físicos da arquitetura alvo. Quando não há registradores disponíveis, deve-se
carregar o conteúdo de um registrador na memória (load), e depois de usá-lo recuperar seu
conteúdo (store). Esse processo é chamado de spill e o que se busca com um bom alocador de
registradores é diminuir o spill, pois assim diminui o número de instruções e acessos à
memória.
Uma ferramenta muito útil para geração de código é o LLVM (Low Level Virtual
Machine) [1], uma plataforma de compilação de código aberto com o propósito de ser um
compilador multiuso, com diversas ferramentas reutilizáveis.
Assim, este trabalho teve por objetivo a validação de back-end e avaliação de
desempenho de um algoritmo integrado de escalonamento de instruções e alocação de
registradores, junto à infraestrutura do back-end da plataforma de compilação LLVM.
Especificamente, foi avaliado o algoritmo de escalonamento de instruções e alocação de
registradores baseado no isomorfismo de subgrafos [4,5] implementado no back-end LLVM
para o processador MIPS, além de ter sido validado e avaliado o back-end LLVM
implementado para o processador reconfigurável VLIW (Very Long Instruction Word) ρ-vex
[2,7].
2. MATERIAL E MÉTODOS
Este trabalho foi desenvolvido no Laboratório de Sistemas Computacionais de Alto
Desempenho (LSCAD) da UFMS em Campo Grande, e foi dividido em duas partes: 1)
análise de desempenho do algoritmo de escalonamento de instruções e alocação de
registradores baseado no isomorfismo de subgrafos; 2) validação e avaliação do back-end
LLVM para o processador ρ-vex. Antes de se adentrar no desenvolvimento do trabalho, será
dada uma breve explicação sobre o funcionamento do LLVM.
2.1 Infraestrutura de compilação LLVM
No começo dos anos 2000, a maioria dos compiladores era modelada de forma que seu
uso era muito específico, ou seja, compilava determinada linguagem para determinada
arquitetura. Além disso, o reúso de ferramentas de um compilador estático para um
compilador não-estático era difícil. Os poucos compiladores que fugiam à essa regra tinham o
código pouco compartilhado. Diante disso nasceu o LLVM, uma coleção modular de
componentes reutilizáveis para construção de compiladores e ferramentas para análise e
otimização de código executável. O que permite o reúso de código no LLVM é a utilização de
uma linguagem intermediária (LLVM IR) na fase do otimizador, entre as fases do front-end e
back-end do compilador. Assim, para gerar código a partir de uma linguagem específica é
necessário implementar apenas o front-end, e analogamente, para se gerar código para uma
arquitetura específica implementa-se apenas o back-end, ao invés do compilador inteiro. A
Figura 1 apresenta de maneira simples a organização funcional do compilador LLVM.
Figura 1: Organização do Front-end e Back-end da infraestrutura LLVM
Um back-end LLVM consiste em um conjunto de componentes reutilizáveis
responsáveis por transformar o código na representação intermediária em código assembly ou
diretamente em código binário executável. A Figura 2 mostra os estágios do back-end LLVM
para geração de código.
Figura 2: Estágios do back-end LLVM na geração de código
O entendimento detalhado do funcionamento do LLVM foi essencial para o
desenvolvimento do trabalho.
2.2 Análise de desempenho do algoritmo de escalonamento de instruções e
alocação de registradores baseado no isomorfismo de subgrafos
Nesta seção será apresentado o problema do isomorfismo de subgrafos, bem como a
metodologia utilizada para se atingir os objetivos referentes ao algoritmo.
2.2.1 Algoritmo de escalonamento de instruções e alocação de registradores
baseado no isomorfismo de subgrafos
No problema de isomorfismo de grafos, dois grafos G₁= (V₁, E₁) e G₂= (V₂, E₂) são
ditos isomorfos, denotado por G₁  G₂, se existe uma bijeção φ: V₁ → V₂ tal que, para todo
par de vértices vi, vj ∈ V₁ vale que (vi, vj) ∈ E₁ se e somente se (φ(vi), φ(vj)) ∈ E₂. No
problema de isomorfismo de subgrafos, o grafo G₁ = (V₁, E₁) é isomorfo ao grafo G₂ = (V₂,
E₂) se existe um subgrafo de G₂, por exemplo, G'₂, tal que G₁  G'₂. No contexto deste
relatório, denomina-se G₁ de grafo de entrada e G₂ de grafo base. [4]
(a) Grafo G₁
(b) Grafo G₂
(c) Grafo G'₂
Figura 3: Exemplo de isomorfismo de subgrafos [4]
O grafo base é um grafo que representa a arquitetura alvo. A Figura 4 mostra o grafo
base referente à arquitetura MIPS. Para simplificar, foram representados apenas quatro
registradores e as duas unidades funcionais. O grafo base é redimensionado quando um
subgrafo isomorfo ao grafo de entrada não é encontrado, de modo a aumentar as chances de se
obter o isomorfismo.
Figura 4: Grafo base do MIPS representado com quatro registradores [5]
A Figura 5 mostra o isomorfismo entre o DAG do trecho de código abaixo e um
subgrafo do grafo base. DAGs (Directed Acyclic Graph) são grafos dirigidos que não
possuem ciclos. Utilizando a ordenação topológica no DAG, tem-se que suas arestas apontam
sempre para frente.
Código:
(a)
addu
$2, $3, $4
and
$6, $2, $5
Grafo de entrada
(b) Grafo base do MIPS
(c) Grafo resultante
Figura 5: Exemplo de isomorfismo de subgrafos no grafo base do MIPS
Os vértices quadrados do DAG de entrada representam as instruções e os vértices
circulares representam os registradores que são dados como fonte e destino das instruções.
Observe que o grafo base da arquitetura teve de ser redimensionado de forma que pudesse
haver um subgrafo isomorfo ao DAG de entrada. [5]
2.2.2 Metodologia para análise de desempenho
Os experimentos foram realizados com programas dos Benchmarks SimpleBench e
Shootout, e foram compilados utilizando o compilador LLVM build 2.9 e gerados
considerando o back-end disponibilizado para o processador MIPS. Os programas gerados
utilizando o algoritmo de isomorfismo de subgrafos foram comparados com aqueles gerados
utilizando dois algoritmos clássicos presentes no LLVM, greedy e linearscan. A execução do
código dos programas foi realizada utilizando-se um simulador MIPS implementado sobre a
linguagem de descrição de processadores ArchC [8], onde foi adicionado código para
contagem da quantidade de instruções loads e stores executadas.
Os passos da simulação são mostrados na Figura 6. O arquivo assembly gerado pelo
LLVM é passado como parâmetro para um cross-compiler, que gera o arquivo executável a
ser usado na simulação.
Figura 6: Fluxo da simulação dos programas
2.3 Validação e avaliação do back-end LLVM para o processador ρ-vex
Nesta seção serão mostrados os métodos utilizados para a validação e avaliação
do back-end LLVM para o ρ-vex.
2.3.1 O processador ρ-vex
O ρ-vex é um processador VLIW (Very Long Instruction Word) de código aberto, que
permite a extensibilidade de sua arquitetura junto a operações reconfiguráveis. A arquitetura
do processador ρ-vex é baseada na ISA (Instruction Set Architecture) VEX (VLIW Example).
O processador ρ-vex implementa uma arquitetura Harvard (memória de dados é
separada fisicamente da memória de instruções), não possui unidade de gerenciamento de
memória nem unidade para cálculo de números de ponto-flutuante, o endereçamento na
memória é realizado com referências absolutas, não há implementação de caches, mecanismos
de predição de desvios e não há registradores distribuídos.
A microarquitetura do ρ-vex, mostrada na Figura 7, consiste em uma via de dados de
quatro estágios, onde operações são buscadas, decodificadas e despachadas para unidades de
execução individuais. Após processadas, os resultados das instruções são armazenados na
memória de dados ou conjunto de registradores. O ρ-vex dispõe das seguintes unidades
funcionais: quatro unidades lógicas e aritméticas (ALUs), duas unidades de multiplicação 16
por 32 bits (MULs), uma unidade de controle (CTRL) e uma unidade de memória (MEM).
Figura 7: Organização do processador ρ-vex
2.3.2 Metodologia para validação e avaliação do back-end
O processo de validação do back-end consistiu na geração de código para programas
do Benchmark Trimaran Compiler Suite (Simple Benchmarks) e implementações de
algoritmos clássicos de ordenação e manipulação de estrutura de dados. Os experimentos
foram realizados utilizando o VEX Toolchain (disponiblizado pela HP) [6], um conjunto de
ferramentas de geração de código e simulação, que contém um compilador C, bibliotecas
ANSI C, ferramentas para facilitar o profiling de código, um simulador em software e o
montador ρ-ASM. Assim, foram comparados os programas gerados com o back-end LLVM
para o processador ρ-vex e com o compilador C presente no VEX Toolchain. A Figura 8
apresenta o fluxo de validação do back-end LLVM.
Figura 8: Fluxo de validação do back-end LLVM para o ρ-vex
Um programa em C é compilado com o GCC, LLVM e VEX C Compiler. O GCC já
emite um binário executável, enquanto que os outros compiladores emitem códigos assembly,
que serão as entradas do simulador VEX. A Figura 9 mostra os passos realizados pra se gerar
um binário executável para a arquitetura da máquina na qual está instalado o VEX Toolchain.
Figura 9: Fluxo da geração de executável no VEX Toolchain
O assembly é traduzido em um arquivo cs.c (simulador compilado VEX). Este arquivo
é então passado como parâmetro para o GCC, onde é criado um arquivo objeto. Finalmente, o
compilador CC recebe o arquivo objeto e gera o binário executável.
Depois desse processo, os programas foram depurados com o GDB e tiveram suas
saídas comparadas. Para que um programa fosse considerado válido, sua saída deveria ser
igual à saída dos programas gerados com o GCC e VEX C Compiler.
Os dados para a avaliação de desempenho foram obtidos mediante análise do código
assembly e de arquivos gerados pelo próprio simulador após a execução dos programas.
3. RESULTADOS E DISCUSSÃO
Esta seção apresenta os resultados obtidos sobre a análise de desempenho do
algoritmo de escalonamento de instruções e alocação de registradores baseado no isomofismo
de subgrafos e sobre a avaliação do back-end LLVM para o processador ρ-vex.
3.1 Resultados da análise de desempenho do algoritmo de isomorfismo de
subgrafos
Os resultados são apresentados na Tabela 1 e mostram o número de instruções load e
store e a quantidade total de instruções executadas. Assim, é possível analisar o desempenho
dos programas em cada um dos algoritmos de escalonamento de instruções e alocação de
registradores adotados, bem como validar o código gerado por esses algoritmos.
Nesse experimento, todas as métricas tiveram resultado igual em três programas
(hello, eight e ifthen). Nos demais há uma pequena diferença entre o algoritmo do
isomorfismo e os outros dois algoritmos, que se deve ao fato de algumas chamadas de funções
nos programas gerados com o isomorfismo obterem seus parâmetros diretamente dos
registradores ao invés da pilha e utilizarem registradores além da definição da ABI
(Application Binary Interface).
Tabela 1: Resultados da execução dos programas compilados com o LLVM.
Programa
fib2
hello
nestedloop
dag
eight
ifthen
local_var_test
Algoritmo
Instruções Executadas
Loads
Stores
Isomorphism
4113
482
405
Greedy
4115
522
445
Linearscan
4115
522
445
Isomorphism
1184
182
167
Greedy
1184
182
167
Linearscan
1184
182
167
Isomorphism
842161063
219
213
Greedy
842162640
347
326
Linearscan
842162640
347
326
Isomorphism
8204
0
0
Greedy
8458
0
0
Linearscan
8458
0
0
Isomorphism
11095
0
0
Greedy
11095
0
0
Linearscan
11095
0
0
Isomorphism
270028
0
0
Greedy
270028
0
0
Linearscan
270028
0
0
Isomorphism
3473
442
375
Greedy
3675
455
388
Linearscan
3673
455
388
Portanto, os resultados mostram que os programas gerados com o algoritmo de
isomorfismo de subgrafos têm desempenho similar àqueles gerados com outros algoritmos
clássicos.
3.2 Resultados da avaliação do back-end LLVM para o ρ-vex
A Tabela 2 apresenta os resultados de caracterização e desempenho sobre os códigos
gerados pelo LLVM e pelo VEX C Compiler. Todos os programas presentes na Tabela 2
foram validados.
O motivo dos programas gerados pelo back-end LLVM obterem pior desempenho
(counting_sort, dag, fib_mem, floyd_warshall, ifthen, local_var_test, longlong, mm_dyn e
struct_test) é que alguns desses programas apresentam operações de divisão e módulo que
não são suportadas pelo back-end LLVM por não serem totalmente executadas pelo ρ-vex.
Portanto, quando possível, são realizadas algumas manipulações a fim de substituir essas
operações por operações mais simples, gerando, assim, mais instruções. Além disso, outro
fator que afetou os resultados é em relação aos imediatos maiores que nove bits. Tais
imediatos não são suportados pelo ρ-vex, mas são definidos pela ISA VEX. Assim, quando
ocorrem, são realizadas manipulações para transferir o valor do imediato para um registrador,
o que gera mais instruções.
Os casos em que o LLVM apresenta desempenho melhor (binary_tree,
double_linked_list, linked_list e parms_test) se devem ao fato do código gerado pelo LLVM
obter uma taxa de OPI (operações por instrução) maior que o gerado pelo VEX C Compiler, o
que ocasiona menos misses na cache. O número maior de OPI se deve às inserções de
instruções NOP pelo compilador do VEX Toolchain, que ocorre quando há conflito de dados
nas instruções de memória load (2 NOPs) e de comparação (1 NOP).
Tabela 2: Resultados dos programas compilados com o LLVM e o VEX C Compiler.
Programas
Compilador
binary_tree
LLVM
1418
609
809
1,4
9,09
2,77
VEX C Compiler
1446
575
871
1,27
5,75
2,17
LLVM
1631
793
838
1,37
3,98
2,69
VEX C Compiler
1431
551
880
1,48
4,61
4,48
LLVM
10370
8849
1521
1,43
50
0,2
VEX C Compiler
7681
6416
1265
2,39
50
0,23
LLVM
14495
12600
1895
1,41
0,17
0,17
VEX C Compiler
16814
14306
2508
1,38
0,22
0,19
counting_sort
dag
double_linked_list
Total de Ciclos de Ciclos
Ciclos Execução de Stall
OPI
Miss
Miss Memória
Memória de de Instruções
Dados (%)
(%)
fib_mem
floyd_warshall
ifthen
linked_list
local_var_test
longlong
mm_dyn
nested
parms_test
struct_test
LLVM
977
383
594
1,44
6,92
2,27
VEX C Compiler
859
267
592
1,43
6,82
2,82
LLVM
4170
3168
1002
1,42
1,95
0,75
VEX C Compiler
2939
1965
974
1,48
2,12
1,02
LLVM
430537
370037
60500
1,5
50
0
VEX C Compiler
220530
200031
20499
3,38
50
0,01
LLVM
51608
46811
4797
1,44
0,05
0,04
VEX C Compiler
58500
52931
5569
1,22
0,07
0,04
LLVM
1447
745
702
1,59
8,33
1,08
VEX C Compiler
1173
473
700
1,69
8,26
1,22
LLVM
440
32
408
2
29,41
26,32
VEX C Compiler
387
24
363
1
50
22,22
LLVM
1944
1053
891
1,76
4,46
1,5
VEX C Compiler
1828
905
923
2,05
4,2
1,84
LLVM
2591
1612
979
1,3
17,02
1,01
VEX C Compiler
1810
865
945
2,13
17,02
1,33
LLVM
445
37
408
1,93
21,74
26,32
VEX C Compiler
447
39
408
1,76
21,74
25
LLVM
508
94
414
1,21
10,2
11,9
VEX C Compiler
412
44
368
1,57
50
12,5
Apesar dos resultados mostrarem um desempenho melhor do compilador VEX C,
nota-se um potencial do back-end LLVM para arquiteturas VLIW.
4. CONCLUSÕES
Este relatório final apresentou a análise de desempenho do algoritmo de
escalonamento de instruções e alocação de registradores baseado no isomorfismo de
subgrafos e a validação e avaliação do back-end LLVM para o processador VLIW ρ-vex.
Em relação à análise de desempenho do algoritmo de isomorfismo, os resultados
mostram que o algoritmo, mesmo em programas menores, pode se beneficiar de algumas
situações como a passagem de parâmetros por registradores e não pela pilha.
Quanto à validação e avaliação do back-end LLVM, mesmo com desempenho pior na
maioria dos programas, é possível se perceber um grande potencial, uma vez que as
limitações do ρ-vex afetaram bastante os resultados.
Como trabalho futuro a este projeto, pretende-se integrar e avaliar o algoritmo de
escalonamento de instruções e alocação de registradores baseado no isomorfismo de
subgrafos no back-end LLVM implementado para o processador ρ-vex.
5. REFERÊNCIAS
[1] Lattner C. LLVM. In: A. Brown, G. Wilson. The Architecture of Open Source
Applications: Elegance, Evolution, and a Few Fearless Hacks. Creative Commons, 2011.
[2] T. van As, “ρ-VEX: A Reconfigurable and Extensible VLIW Processor”, Master's thesis,
Delft University of Technology, 2008. Faculty of Electrical Engineering, Mathematics and
Computer Science.
[3] L. Santos Silva. Algoritmos para escalonamento de instruções e alocação de registradores
na infraestrutura LLVM. Qualificação de Mestrado, Faculdade de Computação –
Universidade Federal de Mato Grosso do Sul.
[4] R. Santos, R. Azevedo, e G. Araujo. Instruction Scheduling Based on Subgraph
Isomorphism for a High Performance Computer Processor. Journal of Universal Computer
Science, 14(21):3465-3480, 2008.
[5] Silva, Lucas; Silva, Richard; Santos, Ricardo. An Integrated Technique for Instruction
Scheduling and Register Allocation Based on Subgraph Isomorphism. In: Proc. of the 16th
Brazilian Symposium on Programming Languages, 2012, Natal, Brazil.
[6] Hewlett-Packard Laboratories, “VEX Toolchain”. Disponível em:
hhtp://www.hpl.hp.com/downloads/vex/, Março 2011.
[7] J. A. Fisher, P. Faraboschi, and C. Young, Embedded Computing: A VLIW Approach to
Architecture, Compilers and Tools. Elsevier, 2005.
[8] T. A. Team, “The ArchC Architecture Description Language”. Disponível em:
http://www.archc.sourceforge.net/index.html, Fevereito 2013.
6. PRODUTOS ALCANÇADOS
Resumo aceito para apresentação na modalidade pôster na IV Escola Regional de Informática
(ERI), Três Lagoas/MS, agosto/2013.