Estudo de um Caso
Para estudar a viabilidade de um sistema automático para otimização de localidade de dados e de paralelismo, executamos uma análise detalhada de um problema específico: uma multiplicação de matrizes não quadradas. Então, adotamos o seguinte caso de estudo: "qual a melhor versão paralela para um programa de multiplicação de duas matrizes não quadradas de dimensões 1024128 e 128256".

O estudo foi realizado em uma máquina Silicon Graphics Power Series 4D/480 VGX e os programas foram compilados com o cc sem opção de otimização. A contagem de tempo foi obtida com o uso da chamada times.

Aplicando apenas a transformação de loop interchange, obtemos as 6 possíveis permutações dos 3 loops que implementam a multiplicação de matrizes. Todas estas versões podem ter seus loops externos paralelizados.

Aplicando-se as características deste programa no sistema em desenvolvimento, obtivemos a seguinte saída para o valor do custo da janela de referências:
Tabela 1 - Custo de cada uma das versões do programa em estudo. 
versão   ijk       ikj        jik       jki       kij       kji
custo   33.155    33.153    263.425   263.429   132.225   132.233
E executando-se cada uma das versões em uma máquina real, obtivemos os seguintes tempos de execução em função do número de processadores utilizados. O gráfico 1 resume estes números.
Tabela 2 - Tempo de execução de cada uma das versões do programa em estudo (em seg). 
  versão
   x no             1     2      3      4      5      6     7      8      
processadores
                                                                     
    ijk           65.53 33.32  22.29  16.72  13.57  11.40  9.86   8.62
    ikj           36.42 18.21  12.19   9.27   7.52   6.39  5.50   4.82
    jik           71.45 36.32  24.36  18.42  14.86  13.30  11.68  9.55
    jki          151.85 90.93  67.07  60.50  55.38  55.67  52.18  46.62
    kij          148.66 78.15  56.17  43.44  38.81  32.84  29.21  24.73
    kji          258.54 140.80 105.25 87.04  80.01  72.07  66.41  60.36
Comparando os resultados das tabelas 1 e 2 vemos que nosso sistema identificou corretamente a versão ikj como a melhor dentre todas. Mas houve um erro em relação às versões jik/jki e kij/kji. A explicação para isto é o fato das versões kij/kji necessitarem usar mecanismos de exclusão mútua para atualização da matriz produto; isto causado por uma série de dependências de dados existentes nestas versões, o que não há nas outras. Isto causou a estimativa de um valor de custo menor.

Analisando-se a curva de speed-up correspondente (gráfico 2), vemos que a versão ikj é a que apresenta melhores características de escalabilidade.

O gráfico 3 mostra a curva de eficiência, e mais uma vez, a versão ikj é a que possui um melhor aproveitamento dos processadores.

Assim, podemos dizer que a estratégia é funcional, bastando que sejam propostos novos componentes à função custo que englobem os aspectos relacionados à paralelização do programa. Esforços neste sentidos estão sendo conduzidos e novos resultados são esperados em breve.
Pedro Vaz Artigas
E-mail: artigas@lsi.usp.br

LSI Laboratory of Integrated Systems