Atividade de Laboratório 4

Objetivos

O objetivo desta atividade é exercitar os conceitos de perfilamento de código vistos em aula.

Descrição

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:

• vTune - Intel: Vendida pela Intel. Existem versões para uso não comercial. Indicada para uso com os processadores da Intel.
• Code Analyst - AMD: Fornecida pela AMD. Indicada para uso com os processadores da AMD.
• Instruments - Apple: Fornecida com o pacote de desenvolvimento da Apple. Indicada para uso nos sistemas da Apple.
• perf - Linux: disponível nas distribuições mais comuns do Linux. Esta ferramenta já está instalada nas máquinas do laboratório, entretanto, caso você queira instalar em outra máquina, no Ubuntu, a ferramenta pode ser instalada com:

  apt-get install linux-tools-common
  apt-get install linux-tools-VER

  onde VER é a versão do kernel do Linux.

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

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 iniciar o vetor, a aplicação realiza a soma dos valores maior do que 128 RPT vezes. O programa pode ser encontrado em:

• Programa: kernel11-branch_prediction.c

Aviso importante

Neste experimento vamos desabilitar algumas otimizações do compilador, entretanto, algumas versões do GCC ignoram algumas das flags necessárias. Dessa forma, é importante utilizar um compilador compatível com o que está instalado no laboratório (GCC 7.3).

Detecção de código quente

A primeira tarefa 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 as otimizações de inlining, vetorização e if-conversion do compilador. Para compilar a programa com sem estas otimizações execute:

gcc -O3 kernel11-branch_prediction.c -fno-tree-loop-vectorize -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 a lista de funções mais quentes do programa de forma ordenada. Para tanto, basta executar

perf report

Com base no resultado observado com o perf, responda às seguintes perguntas:

• 1) Qual é a função mais quente do programa acima?
• 2) Qual a porcentagem de tempo que foi gasta na função mais quente?
• 3) Qual é o tempo total de execução do programa

Reproduza o experimento, mas desta vez não utilize a opção -fno-inline. Responda às seguintes perguntas:

• 4) Qual é o tempo total de execução do programa sem remover a otimização de inline?
• 5) Qual é a função mais quente do programa neste caso?
• 6) Qual a porcentagem de tempo que foi gasta na função mais quente?
• 7) Enumere suas hipóteses para explicar os resultados observados

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 não gera uma interrupção a cada falta na cache, e sim a cada N faltas na cache, onde N é 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: kernel4-mat_mul_naive.c.

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 (Para este experimento utilizae o código gerado com as flags -fno-tree-loop-vectorize, -fno-inline e -fno-if-conversion).

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

Agora compile o programa kernel11-branch_prediction.c 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-tree-loop-vectorize -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 branches,branch-misses ./kernel11-branch_prediction.sorted.x

• 8) Qual versão do programa é mais rápida?
• 9) Quantas vezes (aproximadamente) esta versão é mais rápida do que a outra?
• 10) Como estes dois programas se comparam em relação aos erros de predição de salto?

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 -fno-tree-loop-vectorize -fif-conversion -fno-inline -o kernel11-branch_prediction.ifc.x
gcc -O3 kernel11-branch_prediction.c -DSORT -fno-tree-loop-vectorize -fif-conversion -fno-inline -o kernel11-branch_prediction.sorted.ifc.x

Execute as aplicações geradas e compare o desempenho com as aplicações geradas anteriormente, sem a otimização if-conversion.

• 11) O que acontece com o desempenho do código quando a opção "-fif-conversion" é usada e o vetor não é ordenado (sem a opção -DSORT)?
• 12) O que acontece com o desempenho do código quando a opção "-fif-conversion" é usada e o vetor é ordenado (com a opção -DSORT)?
• 13) Qual é o número total de branches executados nos quatro casos a seguir: a) não ordenado + -fno-if-conversion; b) ordenado + -fno-if-conversion; c) não ordenado + -fif-conversion; d) ordenado + -fif-conversion?
• 14) Qual é o número total erros de predição de salto nos quatro casos a seguir: a) não ordenado + -fno-if-conversion; b) ordenado + -fno-if-conversion; c) não ordenado + -fif-conversion; d) ordenado + -fif-conversion?
• 15) Inspecione o código em linguagem de montagem e enumere suas hipóteses para explicar as diferenças de desempenho entre as versões otimizadas com e sem if-conversion.