Técnicas para desenvolvimento e aceleração de códigos científicos


Prof. Edson Borin
Instituto de Computação
Universidade Estadual de Campinas 		Raul Baldin
Faculdade de Engenharia Civil, Arquitetura e Urbanismo
Universidade Estadual de Campinas

Atividade Prática: Perfilamento de Código

Nesta atividade, exercitaremos os conceitos de perfilamento de código.

Conceitos Básicos

Conhecer o perfil (profile) de execução de um programa é de grande utilidade quando se deseja otimizar o desempenho do mesmo. Por exemplo, é muito útil conhecer qual função ou trecho de código toma a maior parte do tempo de execução da aplicação. Outra informação do perfil que pode ser útil, é a quantidade de instruções executadas por ciclo ou a taxa de faltas na cache (cache misses). O perfilamento, ou profiling, de um programa é o ato de se coletar o perfil de execução do mesmo.

Existem diversas ferramentas para se traçar o perfil de execução de um programa. Dentre eles:

Nesta atividade de laboratório, utilizaremos a ferramenta perf para traçar o perfil da aplicação.

Atividades

Para esta atividade, utilizaremos um programa que realiza a soma de todos os valores maiores do que 128 armazenados no vetor data. A aplicação inicia o vetor com dados aleatórios e, opcionalmente (mediante compilação com a opção -DSORT), ordena os dados do vetor. Após isso iniciar o vetor, a aplicação realiza a soma dos valores maior do que 128 RPT vezes. O programa pode ser encontrado em:

Detecção de código quente

A primeira atividade consiste em detectar qual porção da aplicação ocupa a maior parte do tempo de execução. Para isso, utilizaremos a ferramenta perf.

A ferramenta perf traça o perfil de execução do binário, portanto, o primeiro passo é compilar a aplicação. Neste primeiro experimento, vamos desabilitar a otimização inlining e a otimização if-conversion do compilador. Para compilar a programa com sem estas otimizações execute: 

gcc -O3 kernel11-branch_prediction.c -fno-inline -fno-if-conversion -o kernel11-branch_prediction.x

Após gerarmos o código binário, podemos executá-lo com o comando: 

./kernel11-branch_prediction.x

Para traçarmos o perfil do programa, basta executar a ferramenta perf da seguinte forma: 

perf record APPLICATION ARGUMENTS
ou seja, em nosso caso: 
perf record ./kernel11-branch_prediction.x

Por padrão, a ferramenta perf armazena os dados de perfil coletados no arquivo perf.data, dentro do mesmo diretório em que a mesma foi executada. O perf permite ao usuário modificar o nome deste arquivo (consulte o manual da ferramenta com o comando man perf-record).

A ferramenta perf report lê o conteúdo do arquivo perf.data e exibe de forma ordenada a lista de funções mais quentes do programa. Para tanto, basta executar 

perf report

Responda às seguintes perguntas:

Reproduza o experimento, mas desta vez não utilize a opção -fno-inline.

Detecção de código que causa faltas na cache

No exercício anterior nós detectamos as rotinas de código que ocupam a maior parte do tempo. Para realizar esta operação, a ferramenta perf solicita ao sistema operacional que a aplicação seja interrompida periodicamente. A cada interrupção, a ferramenta perf grava o endereço da instrução que estava sendo executada naquele instante. Ao fim da execução, a ferramenta perf grava as amostras de endereços coletados no arquivo perf.data. Este conjunto pode ser listado com a ferramenta perf script.

De posse das amostras no arquivo perf.data, a ferramenta perf report associa cada endereço com uma função do programa executado e exibe um relatório que indica a porcentagem de amostras em cada função.

Por padrão, a ferramenta perf solicita ao sistema operacional que as interrupções geradas periodicamente, ou seja, a cada intervalo de tempo. Entretanto, podemos solicitar ao sistema operacional que as interrupções sejam geradas em função de outros eventos, como faltas na cache (cache misses). O resultado é um conjunto de amostras de endereços de instruções que causam faltas da cache. Para tanto, basta utilizar a opção -e e especificar o evento de interesse. Por exemplo, o comando: 

perf record -e cache-misses ./kernel11-branch_prediction.x
grava os endereços das instruções que estão executando quando ocorrem faltas na cache. Para obter uma lista de eventos que podem ser utilizados execute a ferramenta perf list.

É importante observar que o sistema operacional não gera uma interrupção a cada falta na cache, e sim a cada X faltas na cache, onde X é um número pré-determinado pela ferramenta.

Novamente, você pode listar os eventos gravados com a ferramenta perf script e listar as funções que causam o maior número de faltas na cache com a ferramenta perf report. Tente identificar o trecho de código que causa o maior número de faltas na cache no código de multiplicação de matrizes ingênua.

Traçando o perfil de desempenho do código no hardware

A ferramenta perf stat pode ser usada para gerar um resumo dos eventos que ocorreram durante a execução. Para tanto, basta executar: 

perf stat APPLICATION ARGUMENTS
Como resultado, a ferramenta imprime um relatório de frequência de eventos ao término da aplicação. Os eventos de interesse também podem ser selecionados com a opção -e. Por exemplo, o comando: 
perf stat -e cache-references,cache-misses APPLICATION ARGUMENTS
lista o número de acessos à cache e o número de acessos que causaram falta na cache durante a execução do programa APPLICATION.

Utilize a ferramenta perf stat para monitorar o número total de saltos (branches) e o número de predições de salto erradas (branch-misses) que ocorreram durante a execução do programa ./kernel11-branch_prediction.x, gerado no primeiro passo. 

perf stat -e branches,branch-misses ./kernel11-branch_prediction.x

Agora compile o programa novamente, mas desta vez, habilite a ordenação dos dados do vetor com a opção -DSORT durante a compilação: 

gcc -O3 kernel11-branch_prediction.c -DSORT -fno-inline -fno-if-conversion -o kernel11-branch_prediction.sorted.x
esta versão do programa ordena os dados antes de realizar a soma dos valores maiores que 128 e deve causar menos erros de predição de saltos. Para uma explicação mais detalhada, leia http://stackoverflow.com/questions/11227809/why-is-processing-a-sorted-array-faster-than-an-unsorted-array

Utilize novamente a ferramenta perf stat para monitorar os erros de predição de salto, mas desta vez execute o novo código binário, que ordena o vetor. 

perf stat -e cache-references,cache-misses ./kernel11-branch_prediction.sorted.x

Realize os experimentos novamente, mas desta vez, habilite otimização if-conversion, ou seja, utilize a opção -fif-conversion durante a compilação. Algumas versões do compilador GCC habilitam esta otimização por padrão quando as flags -O3, -O2, -O1 ou -Os são selecionadas e não há necessidade de se incluir a opção -fif-conversion na linha de comando. Para compilar você pode executar: 

gcc -O3 kernel11-branch_prediction.c -fif-conversion -fno-inline -o kernel11-branch_prediction.ifc.x
gcc -O3 kernel11-branch_prediction.c -DSORT -fif-conversion -fno-inline -o kernel11-branch_prediction.sorted.ifc.x
Execute a aplicações gerada e compare o desempenho com as aplicações geradas anteriormente, sem a otimização if-conversion.

Desafio

Inspecione o código em linguagem de montagem e explique as diferenças de desempenho entre as versões otimizadas com e sem if-conversion.