Barr e Hickman (1993) apresentam uma discuss˜ao sobre medidas de desempenho para algoritmos paralelos. V´arias m´etricas da eficiˆencia de implementa¸c˜oes paralelas resultam em dificuldades de medi¸c˜ao e compara¸c˜ao, decorrentes das limita¸c˜oes impos-
6.5 Medidas de Desempenho Metodologia de Experimenta¸c˜ao
tas pelas diferentes arquiteturas das m´aquinas, os diferentes projetos de m´aquinas, a natureza estoc´astica de alguns algoritmos paralelos e as oportunidades inerentes para a introdu¸c˜ao de vieses. O speedup ´e uma medida amplamente utilizada para descrever a eficiˆencia conseguida sobre o processamento serial pelo uso de v´arios processadores.
Alba e Luque (2006) argumentam que conclus˜oes diferentes podem ser inferidas dos mesmos resultados, dependendo da medida usada e de como essa medida ´e aplicada. A seguir s˜ao descritas algumas medidas de desempenho para metaheur´ısticas paralelas.
Speedup
O speedup apresenta o quanto um algoritmo paralelo ´e mais r´apido que o melhor algoritmo sequencial correspondente. Para algoritmos paralelos determin´ısticos, o spe- edup ´e dado pela raz˜ao T1/Tm, onde m ´e o n´umero de processos, T1 e Tm s˜ao os
tempos de execu¸c˜ao do algoritmo sequencial e do algoritmo paralelo com m processos, respectivamente.
Para algoritmos estoc´asticos como os AE, essa defini¸c˜ao de speedup n˜ao pode ser aplicada diretamente. Como os tempos de execu¸c˜ao dos AE podem variar, ´e necess´ario repetir as execu¸c˜oes, e estimar o tempo a ser utilizado no c´alculo do speedup.
O speedup sm para um AEP ´e a raz˜ao da m´edia dos tempos de execu¸c˜ao com um
processo T1 e da m´edia dos tempos de execu¸c˜ao com m processos Tm, como ´e mostrado
a seguir. sm = T1 Tm = ( Pk i=1T1i)/k (Ppj=1Tmj)/p (6.1) onde T1i e Tmj correspondem aos tempos de processamento total (wall clock time) para
cada uma das k execu¸c˜oes com um processo (corresponde `a execu¸c˜ao sequencial) e p execu¸c˜oes paralelas com m processos, respectivamente.
Os valores de sm podem ser interpretados da seguinte maneira: (1) sm = 1 significa
que n˜ao houve ganho de desempenho na vers˜ao paralela; (2) sm = m significa acelera¸c˜ao
linear; (3) sm > m acelera¸c˜ao superlinear; e (4) sm < 1 acelera¸c˜ao sublinear – houve
perdas com a paraleliza¸c˜ao.
Alba (2002) desenvolve defini¸c˜oes de speedup baseado em como os valores de T1 e
Tm s˜ao entendidos, como mostra a Tabela 6.1.
O tipo I – Speedup Forte – compara o tempo de processamento paralelo contra o algoritmo sequencial mais eficiente conhecido. Essa ´e a defini¸c˜ao mais exata de speedup,
Metodologia de Experimenta¸c˜ao 6.5 Medidas de Desempenho
I. Speedup forte II. Speedup fraco
A. Speedup com melhor solu¸c˜ao 1. Versus panmixia
2. Ortodoxo
B. Speedup com esfor¸co predefinido
Tabela 6.1: Taxonomia das medidas de speedup propostas por Alba (Alba, 2002).
por´em esse tipo quase n˜ao ´e usado, dada a dificuldade em se encontrar o atual algoritmo mais eficiente.
O tipo II – Speedup Fraco – compara o tempo do algoritmo paralelo desenvolvido por um pesquisador contra seu pr´oprio algoritmo sequencial. Nesse caso, dois crit´erios de parada poss´ıveis para o algoritmo determinam os subtipos A e B: parada ao encontrar a solu¸c˜ao ´otima ou pr´oxima da ´otima e parada por atingir um esfor¸co predefinido.
Para o tipo II.A – Speedup com melhor solu¸c˜ao – existem duas variantes: Ver- sus Panmixia e Ortodoxo. O Versus Panmixia ´e quando se compara o tempo de um algoritmo paralelo contra o algoritmo sequencial canˆonico, ou seja, compara dois algo- ritmos diferentes. O Ortodoxo ´e quando se compara o tempo de um algoritmo paralelo rodando em um processador, com o mesmo algoritmo rodando em m processadores, isto ´e, o mesmo algoritmo ´e comparado. Neste trabalho, o speedup utilizado ´e do tipo Ortodoxo.
Alba (2002) descarta o tipo II.B – Speedup com esfor¸co predefinido –, porque ´e con- tra o intuito do speedup comparar algoritmos que n˜ao produzam resultados de mesma acur´acia.
Barr e Hickman (1993) apresentam uma taxonomia diferente: (1) Speedup – mede a raz˜ao entre o tempo do c´odigo serial mais r´apido em uma m´aquina paralela e o tempo do c´odigo paralelo usando m processadores na mesma m´aquina paralela; (2) Speedup Relativa – ´e a raz˜ao entre o tempo de execu¸c˜ao serial do c´odigo paralelo em um processador e o tempo de execu¸c˜ao do c´odigo paralelo em m processadores – similar ao tipo II.A.2 – ortodoxo – da Tabela 6.1; e (3) Speedup Absoluto – compara o tempo serial mais r´apido em qualquer m´aquina e o tempo paralelo em m processadores – similar ao tipo I da Tabela 6.1.
Alba et al. (2013) recomendam que o AEP deveria computar solu¸c˜oes com mesma precis˜ao que o algoritmo sequencial. Essa precis˜ao pode ser a da solu¸c˜ao ´otima, se co-
6.5 Medidas de Desempenho Metodologia de Experimenta¸c˜ao
nhecida, ou uma solu¸c˜ao aproximada, desde que ambos algoritmos produzam a solu¸c˜ao de mesma precis˜ao. O crit´erio de parada dos algoritmos sequencial e paralelo deve ser encontrar a mesma solu¸c˜ao. Os autores tamb´em aconselham a execu¸c˜ao do mesmo algo- ritmo paralelo para obter os tempos sequenciais e paralelos, onde os tempos sequenciais s˜ao obtidos com a execu¸c˜ao do AEP com apenas um processo. Desta forma, tem-se um speedup v´alido, pr´atico (n˜ao ´e necess´ario o melhor algoritmo sequencial conhecido) e ortodoxo (mesmo c´odigo, mesma precis˜ao).
Speedup com Medianas
Touati et al. (2013) apresentam um metodologia de avalia¸c˜ao de desempenho ba- seada no c´alculo do speedup com as medianas dos tempos de execu¸c˜ao observados, ao inv´es de usar a m´edia. Os autores argumentam que ´e preciso controlar a variabilidade dos tempos de execu¸c˜ao e a mediana ´e robusta a pontos discrepantes. Cabe ressaltar que o teorema do limite central n˜ao se aplica `a mediana, mas se aplica `a m´edia (ver Se¸c˜ao 6.6.1).
Eficiˆencia
A eficiˆencia em mede a fra¸c˜ao de tempo que um processador ´e de fato utilizado, e
´e dada pela normaliza¸c˜ao da speedup sm, como mostra a Equa¸c˜ao 6.2.
em =
sm
m (6.2)
Idealmente o valor de em deveria ser 1, mas existe o tempo gasto para comunica¸c˜ao,
aloca¸c˜ao de mem´oria, por exemplo, e o seu valor nunca chega a 1, a n˜ao ser quando ocorre speedup superlinear, no qual em passa a ser maior que 1.
Fra¸c˜ao Serial
A fra¸c˜ao serial mede a propor¸c˜ao do algoritmo que ´e inerentemente sequencial, como mostra a Equa¸c˜ao 6.3:
fm =
1/sm− 1/m
1 − 1/m (6.3)
Numa situa¸c˜ao ideal, o valor da fra¸c˜ao serial deveria se manter constante para diferentes valores de m. Se o valor de speedup ´e pequeno, dado que a perda de eficiˆencia
Metodologia de Experimenta¸c˜ao 6.5 Medidas de Desempenho
´e causada pelo paralelismo limitado do algoritmo, ainda assim pode se considerar o resultado como bom se fm for constante para diferentes valores de m. Por outro lado,
um aumento suave de fm ´e um aviso de que a granularidade das tarefas paralelas ´e
muito fina. E se fm diminuir `a medida que m aumentar, significa que o speedup est´a se
tornando superlinear. Se ocorre uma acelera¸c˜ao superlinear ent˜ao o valor de fm ficar´a
negativo.
Eficiˆencia Incremental
A eficiˆencia incremental (Equa¸c˜ao 6.4) mostra a fra¸c˜ao de melhoria do tempo pela adi¸c˜ao de outro processador. ´E usada quando o tempo de um ´unico processador ´e desco- nhecido. Essa medida foi generalizada (Equa¸c˜ao 6.5) para medir a melhoria alcan¸cada pelo aumento do n´umero de processadores de n para m.
iem = (m − 1) · E[Tm−1 ] m · E[Tm] (6.4) giem,n = n · E[T n] m · E[Tm] (6.5)
Speedup Escal´avel
As m´etricas anteriores mostram melhorias no desempenho proveniente da adi¸c˜ao de elementos de processamento, por´em n˜ao medem a utiliza¸c˜ao da mem´oria dispon´ıvel. A speedup escal´avel (Equa¸c˜ao 6.6) dimensiona a utiliza¸c˜ao completa dos recursos da m´aquina.
ssm =
E[T1,nm]
E[Tm,nm]
, (6.6)
onde n ´e o tamanho do maior problema que pode ser armazenado na mem´oria associada a um processador, E[T1,nm] ´e o tempo de execu¸c˜ao m´edio necess´ario para 1 processador
resolver problema de tamanho nm, e E[Tm,nm] ´e o tempo de execu¸c˜ao m´edio necess´ario
para m processadores resolverem problema de tamanho nm. A sua maior desvantagem ´e que estimar com precis˜ao o tempo serial ´e dif´ıcil e ´e impratic´avel para muitos problemas (Alba, 2005).