Métricas de Performance

Medir a performance de um computador pode ser desafiante. Ao escolher entre diferentes computadores, encontrar aquele com a melhor performance para a tarefa é de extrema importância. Nesta secção, vamos definir a performance de um computador de uma forma quantitativa.

Fundamentos da Arquitetura de um Computador

Como já se sabe de IAC, um computador é constituído por vários elementos diferentes, como o processador, cache, memória (RAM), armazenamento, e vários periféricos, que, quando unidos, dão-nos um dispositivo funcional.

Dentro do processador (CPU), conseguimos identificar duas categorias de componentes:

  • o Datapath, que realiza as operações com dados, e, por isso, contém a ALU, Register File, Program Counter, etc.
  • a Control Unit, que trata de sequenciar o datapath, a memória, entre outros.

Debaixo do Nosso Programa

Agora que já visualizamos o que está na parte de hardware dos nossos computadores, temos que também ver o que se passa ao corrermos um programa.
Existem três camadas diferentes:

  • Application software: está escrita numa linguagem de alto nível, como C, Java, etc.;
  • System software: dividido entre o compilador, que traduz as linguagens de alto nível para código de máquina e o sistema operativo, que gere o input/output, memória e armazenamento assim como o escalonamento de tarefas e partilhas de recursos;
  • Hardware (processador, memória, I/O, etc.): onde realmente corre o nosso programa, após ser convertido para código máquina pelo compilador.

Níveis de Código

Usualmente escrevemos código numa linguagem de alto nível, como C, Java, Rust, etc., visto que torna o processo mais rápido, mais simples, e, muitas vezes, mais eficiente.

Quando queremos executar este programa, temos primeiro de o compilar. A tarefa do compilador é muito importante, visto que tem o objetivo de converter o nosso código de alto nível em assembly, uma representação textual das instruções do processador.
Poderíamos escrever código diretamente em assembly, mas, na maioria dos casos, isso seria ineficiente: tanto por ser muito mais trabalhoso de escrever, como por o compilador fazer um trabalho muito melhor a produzir assembly eficiente.

Finalmente, existe o assembler que codifica o assembly (ou gerado pelo compilador ou feito à mão pelo programador) em código máquina, isto é, 0s e 1s, que finalmente pode ser executado pelo hardware.

Dependendo da arquitetura do processador, o compilador irá produzir um resultado diferente, o que pode influenciar o tempo de execução, como veremos abaixo.

Performance

Existem diferentes maneiras de definir performance. Ao falarmos de um avião, podemos argumentar que um bom critério de performance é a sua velocidade máxima. Poderá também ser o número de passageiros que pode levar... ou aquele que consegue realizar uma maior viagem sem ter que reabastecer... O que é melhor depende das nossas necessidades e da situação em que nos encontramos, pelo que, por vezes, precisamos de fazer trade-offs entre as opções que temos.

Exemplo

Avaliando quatro aviões diferentes, será possível dizer, objetivamente, qual deles é o melhor?

Não! Como podemos ver, cada avião tem características muito diferentes e, enquanto pode ser melhor numa área, é, por outro lado, pior noutra. Logo, dependendo da situação em que nos encontrarmos e para o que queremos usar o nosso avião, a melhor escolha vai ser diferente.

Adaptando à nossa experiência enquanto programadores, precisamos de avaliar o que o cliente precisa ao invés daquilo que ele quer.

Tal como a performance de um avião, podemos definir a performance de um computador de diferentes maneiras. Para dois computadores a correr o mesmo programa, podemos dizer que o mais rápido é aquele que termina primeiro, isto é, aquele que tem menor tempo de resposta. Entre dois sistemas bancários, podemos dizer que o melhor é aquele que realiza mais operações por segundo, isto é, aquele que tem maior throughput.

Mas, a questão surge: como é que estes dois são afetados ao substituir um processador por outro mais rápido? E ao adicionar mais processadores para tarefas separadas? No primeiro caso, ambos melhoram. Contudo, no segundo caso, apenas o throughput aumenta.

Ao definir a performance de computadores, vamos ter em conta o tempo de resposta. Intuitivamente, de modo a maximizar a performance, teremos de minimizar o tempo de resposta. Definimos, então, performance como o inverso do tempo de execução.

PerformanceX=1Tempo de Execuc¸a˜oX\text{Performance}_X = \frac{1}{\text{Tempo de Execução}_X}

Por vezes, dizemos que o computador XX é nn vezes mais rápido do que o computador YY. Este conceito corresponde à noção de performance relativa. Definimos performance relativa, ou speedup, como o rácio entre duas performances.

SpeedUp=PerformanceXPerformanceY=Tempo de Execuc¸a˜oYTempo de Execuc¸a˜oX\op{SpeedUp} = \frac{\text{Performance}_X}{\text{Performance}_Y} = \frac{\text{Tempo de Execução}_Y}{\text{Tempo de Execução}_X}

Dica

Para não confundir qual dos valores é o XX ou o YY, basta relembrar que o speedup deve ser sempre 1\geq 1.

Exemplo

Se tivermos um processador AA que corre um programa em 10 segundos e um processador BB que corre o mesmo programa em 15 segundos, concluímos que o processador AA é melhor que o BB, já que tem um tempo de execução menor.

Mas quão mais rápido é? Para isso, podemos calcular o speedup:

SpeedUp=Tempo de Execuc¸a˜oBTempo de Execuc¸a˜oA=1510=1.5\op{SpeedUp} = \frac{\text{Tempo de Execução}_B}{\text{Tempo de Execução}_A} = \frac{15}{10} = 1.5

Assim, sabemos que o processador AA é 1.5 vezes mais rápido que o processador BB.

Medir Performance

Tempo

O tempo é a medida mais simples de performance de um computador. Contudo, o tempo de execução de um programa pode ser definido de maneiras diferentes.

O tempo total ou elapsed time corresponde à totalidade do tempo de resposta, incluindo processamento, operações de I/O (como esperar que o utilizador insira um valor), OS overhead, idle time, etc.
Resumidamente, é o tempo total desde o início até ao fim da execução do programa.

O tempo de CPU ou CPU time contém apenas o tempo gasto pelo CPU na computação da tarefa, não incluindo, por exemplo, o tempo de espera por uma operação I/O. O tempo de CPU pode ser também distinguido entre user CPU time e system CPU time.

Analogia

Se estivermos a analisar o tempo que se demorou a construir uma casa e chegarmos à conclusão de que desde o início da construção até à sua conclusão passaram 3 anos (elapsed time), podemos avaliar mais pormenorizadamente para discriminar quanto desse tempo é que de facto corresponde à construção da casa em si. Podemos vir a descobrir que, apesar de terem passado 3 anos, apenas 1 desses anos foi passado a construir a casa em si (CPU time), enquanto o resto foi gasto a arranjar material e em planeamento.

O mesmo se aplica ao nosso computador: apesar de termos passado um determinado intervalo de tempo a executar algo, apenas uma parte desse tempo é que foi gasta em processamento da tarefa.

Ciclos de Relógio

Embora para nós humanos, enquanto utilizadores de computadores, o tempo seja uma métrica importante, poderá ser apropriado pensar numa métrica que se aproprie do funcionamento básico do hardware.

Tal métrica é o número de ciclos de relógio. O relógio coordena os eventos que ocorrem no hardware. A cada intervalo de tempo destes dá-se o nome de períodos de relógio ou clock period. A frequência dos ciclos de relógio é chamada a frequência de relógio ou clock frequency/clock rate.

fclock=1Tclock[Hz]f_{\text{clock}} = \frac{1}{\smartcolor{green}{T_{\text{clock}}}} [\op{Hz}]
TCPU=#Clock Cycles×Tclock=#Clock CyclesfclockT_{\text{CPU}} = \#\text{Clock Cycles} \times \smartcolor{green}{T_{\text{clock}}} = \frac{\#\text{Clock Cycles}}{\smartcolor{blue}{f_{\text{clock}}}}

Podemos constatar que podemos aumentar a performance de um computador reduzindo o número de ciclos de relógio necessários para um programa ou aumentando a frequência do relógio.

Instruções

As equações acima não referem nada sobre o número de instruções necessárias para executar um programa. Contudo, ao compilar o código, o tempo que o computador demora a executá-lo depende desse número de instruções. Além disso, cada instrução pode necessitar de um diferente número de ciclos de relógio. Ao número de ciclos que uma instrução necessita chama-se CPI (cycles per instruction).

Podemos determinar quantos ciclos é que um programa executa, ao multiplicar o número de instruções pelos respetivos CPIs:

#Clock Cycles=i=1n(CPIi×#Instructionsi)\#\text{Clock Cycles} = \sum_{i=1}^n \left(\smartcolor{pink}{\op{CPI}_i} \times \#\text{Instructions}_i\right)

Exemplo

Considere-se um programa que executa as seguintes instruções, com os respetivos CPIs, num determinado processador:

A B C D
Número de Instruções 100 500 200 150
CPI 4 1 2 6
#Clock Cycles=100×4+500×1+200×2+150×6=2200\#\text{Clock Cycles} = 100 \times 4 + 500 \times 1 + 200 \times 2 + 150 \times 6 = 2200

Então, este processador necessita de 22002200 ciclos de relógio para executar este programa.

Define-se o número médio de ciclos por instrução ou average CPI (average cycles per instruction) como:

avg CPI=#Clock Cycles#Instructions\smartcolor{purple}{\text{avg CPI}} = \frac{\#\text{Clock Cycles}}{\#\text{Instructions}}

Exemplo

Continuando com o exemplo acima, sabemos que temos

100+500+200+150=950100 + 500 + 200 + 150 = 950

instruções.

Então, o average CPI vai ser:

avg CPI=2200950=2.32\smartcolor{purple}{\text{avg CPI}} = \frac{2200}{950} = 2.32

Assim, podemos derivar as seguintes expressões:

#Clock Cycles=#Instructions×CPI\#\text{Clock Cycles} = \# \text{Instructions} \times \smartcolor{purple}{\op{CPI}}
TCPU=#Instructions×CPI×Tclock=#Instructions×CPIfclock=#Clock Cycles×Tclock=#Clock Cyclesfclock\begin{darray}{rll} T_{\text{CPU}} &= \# \text{Instructions} \times \smartcolor{purple}{\op{CPI}} \times \smartcolor{green}{T_{\text{clock}}} &= \frac{\# \text{Instructions} \times \smartcolor{purple}{\op{CPI}}}{\smartcolor{blue}{f_{\text{clock}}}}\\\\ &= \#\text{Clock Cycles} \times \smartcolor{green}{T_{\text{clock}}} &= \frac{\# \text{Clock Cycles}}{\smartcolor{blue}{f_{\text{clock}}}} \end{darray}

Exemplo

Consideremos um processador AA com clock rate de 2GHz, e que demora 10 segundos de tempo de CPU a executar um certo programa.
Queremos desenhar um processador BB que demore 6 segundos de tempo de CPU a executar o mesmo programa, mas que necessite de 1.2 vezes mais ciclos de relógio. Qual será o clock rate do processador BB?

Começando por escrever a expressão da clock rate de BB, temos:

Clock RateB=#Clock CyclesBCPU TimeB=1.2×Clock CyclesA6s\text{Clock Rate}_B = \frac{\#\text{Clock Cycles}_B}{\text{CPU Time}_B} = \frac{1.2 \times \text{Clock Cycles}_A}{6 \op{s}}

No entanto, precisamos de descobrir quantos ciclos efetua o processador AA ao executar este programa:

#Clock CyclesA=CPU TimeA×Clock RateA=10s×2GHz=20×109\#\text{Clock Cycles}_A = \text{CPU Time}_A \times \text{Clock Rate}_A = 10 \op{s} \times 2 \op{GHz} = 20 \times 10^9
Clock RateB=1.2×20×1096s=24×1096s=4GHz\text{Clock Rate}_B = \frac{1.2 \times 20 \times 10^9}{6\op{s}} = \frac{24 \times 10^9}{6\op{s}} = 4\op{GHz}

Comparação da Performance

Ao avaliar a performance de um computador, é importante notar que comparar apenas uma destas métricas pode-nos levar a uma conclusão errada. Ao realizar estas comparações, devemos ter em conta o número de instruções, o CPI e a frequência de relógio.

Exemplo

Se nos questionarmos sobre qual operação é a mais rápida entre AND e a multiplicação, a resposta é que depende do processador.

Imaginemos que cada processador demora os seguintes ciclos de relógio a efetuar cada uma destas operações:

Operação AND Multiplicação
Processador AA 1 1
Processador BB 1 5

Conseguimos claramente ver que, no processador AA, ambas as operações demoram o mesmo tempo a ser executadas, enquanto no processador BB é evidente que a operação mais rápida é o AND.

Mas entre estes dois, qual será o mais rápido a efetuar multiplicações? Não é possível concluir nada, visto que depende da clock rate de cada processador.
Pode acontecer que o processador BB tenha uma clock rate suficientemente superior ao do processador AA, de forma a que execute os 5 ciclos de relógio em menos tempo que este executa um único ciclo de relógio.

Sumário da Performance

Conclui-se que a performance depende do:

  • Algoritmo: Afeta o número de instruções e possivelmente o CPI. Se um algoritmo utilizar muitas instruções de divisão, notáveis por serem instruções lentas, o CPI será maior.

  • Linguagem de Programação: Afeta o número de instruções e o CPI. Uma linguagem com bastantes abstrações, como o Java, utiliza muitas indirect calls, o que aumenta o CPI.

  • Compilador: Afeta o número de instruções e o CPI. O compilador determina a tradução do código fonte para instruções hardware. Pode-se dizer que tem, portanto, um trabalho muito complexo, que pode afetar o CPI de várias maneiras.

  • ISA (Instruction Set Architecture): Afeta o número de instruções, o CPI e o período de relógio. A arquitetura afeta os três aspetos da performance, pois condiciona as instruções necessárias, o custo de cada instrução e a frequência de relógio do processador.

Millions of Instructions per Second

Não Confundir

É importante não confundir o MIPS, Millions of Instructions per Second (métrica de performance), com o MIPS, Microprocessor without Interlocked Pipelined Stages (arquitetura de CPUs), que iremos abordar mais à frente nesta disciplina.

O MIPS, Millions of Instructions per Second, é uma métrica que pode ser usada para classificar a performance de um processador.
No entanto, esta não considera as diferenças entre os diferentes ISAs nem a diferença entre a complexidade das instruções (i.e. o CPI).

MIPS=Instruction CountExecution Time×106=Clock RateCPI×106\begin{aligned} \op{MIPS} &= \frac{\text{Instruction Count}}{\text{Execution Time} \times 10^6}\\\\ &= \frac{\text{Clock Rate}}{\op{CPI} \times 10^6} \end{aligned}

Floating Point Operations per Second

O FLOPS, Floating Point Operations per Second, é outra métrica utilizada na avaliação da performance de um processador. Enquanto que o MIPS se refere a qualquer instrução, o FLOPS refere-se apenas a instruções dos registos de vírgula flutuante e faz a distinção entre instruções de 64, 32 e 16 bits, sendo por isso uma métrica mais precisa.

Lei de Amdahl

A Lei de Amdahl defende que devemos tornar mais rápidas as operações mais comuns.

Um erro comum é pensar que uma melhoria de um aspeto do computador nos traz um crescimento linear da sua performance, o que nem sempre é verdade.

Lei de Amdahl

Timproved=Taffectedimprovement factor+Tunaffected=(fimprovement factor+(1f))×Toriginal\begin{aligned} T_{\text{improved}} &= \frac{T_{\text{affected}}}{\text{improvement factor}} + T_{\text{unaffected}}\\ &= \left(\frac{f}{\text{improvement factor}} + (1 - f)\right) \times T_{\text{original}} \end{aligned}
SpeedUp=ToriginalTimproved=1fimprovement factor+(1f)\op{SpeedUp} = \frac{T_{\text{original}}}{T_{\text{improved}}} = \frac{1}{\frac{f}{\text{improvement factor}} + (1-f)}

em que ff representa a fração do trabalho realizado pela componente melhorada, em relação à componente original.

Exemplo

Tomando como exemplo um programa com duas instruções arbitrárias A e B, tal que TA=0.5sT_{A} = 0.5\op{s}, NA=10N_{A} = 10, TB=1.5sT_{B} = 1.5\op{s} e NB=2N_{B} = 2.

Note-se que NATA=5s>NBTB=3sN_A \cdot T_A = 5\op{s} > N_B \cdot T_B = 3\op{s}.

Assim se tornarmos a instrução B 3 vezes mais rápida,

Timprovement=33+5=6sT_{\text{improvement}} = \frac{3}{3} + {5} = 6 \op{s}

o tempo total de execução do programa é 6 segundos.

Contudo, se tornarmos a instrução A 1.8 vezes mais rápida,

Timprovement=51.8+3=5.78sT_{\text{improvement}} = \frac{5}{1.8} + 3 = 5.78 \op{s}

o tempo total de execução do programa é 5.78 segundos!