PGI

Introdução

A empresa americana Portland Group, Inc. (http://www.pgroup.com/) produz uma série de compiladores paralelizadores voltados para máquinas multiprocessadas da família x86. Os compiladores e ferramentas PGI estão disponíveis tanto na versão "single-processor", onde atuam como compiladores otimizadores, como na versão "parallel", onde destacam-se por oferecerem suporte à paralelização automática.

Primeiramente, esses compiladores foram desenvolvidos para o sistema operacional Linux86, mas suportam também Solaris86 e, recentemente, Windows NT. Estes compiladores são utilizados no mais rápido computador existente hoje, usado pelo Departamento de Energia dos Estados Unidos e que está instalado no "Sandia National Laboratories".

A linha de produtos da PGI está subdividida da seguinte forma:

• PGHPF Workstation - HPF com SMP nativo e "parallel Fortran 90 compiler"
• PGF77 Workstation - compilador SMP FORTRAN 77
• PGC++ Workstation - compilador SMP C++
• PGCC Workstation - compilador SMP ANSI C
• PGPROF Workstation - analisador de performance gráfico

O pacote PGI é distribuído por ftp (ftp://ftp.pgroup.com/x86/). Pode-se adquirir o pacote livremente através da rede, entretanto, o mesmo somente funcionará durante 30 dias e, além disso, emitirá mensagens na tela a cada vez que for usado. Após alguns dias, um tempo de espera é introduzido no início de cada programa, dificultando seu uso. Isso tudo é feito com o intuito de obrigar o usuário a comprar uma licença.

Após obter o arquivo do pacote desejado, deve-se seguir os seguintes passos para sua instalação:

1. Criar o diretório onde deseja-se instalar o pacote. As opções mais comuns para isso são /usr/pgi ou /usr/local/pgi, mas a instalação pode ser feita em qualquer diretório onde se tenha as devidas permissões de acesso. É importante notar que o diretório tenha as permissões de leitura, escrita e execução habilitadas para o usuário que está fazendo a instalação. Caso isso não se verifique, pode-se usar os comandos chmod e chown para fazer os ajustes necessários.
2. Os passos seguintes assumem que a instalação é feita no diretório /usr/pgi. Ajuste a variável de ambiente PGI para o diretório onde será feita a instalação:

• csh: setenv PGI /usr/pgi
• sh ou ksh: PGI=/usr/pgi
• export PGI

1. arquivo obtido por ftp deve ser descompactado. Isso deve ser feito com o comando gunzip e depois tar:

• gunzip <tarfile>.tar.gz
• tar xpf <tarfile>.tar

1. Note que o pacote não pode ser instalado no mesmo diretório onde é descompactado o arquivo tar. Logo, é recomendável que o arquivo anterior seja descompactado no diretório /tmp ou em outro lugar que não o diretório apontado pela variável PGI.
2. pacote inteiro deve caber em 25Mb, mas aproximadamente 50Mb são necessários durante sua instalação. Após o término desse processo, pode-se apagar os arquivos criados no diretório temporário.
3. No diretório onde foi descompactado o arquivo, deve-se executar o script de instalação que acompanha o pacote:

• ./install

1. script de instalação irá listar os produtos que estão disponíveis e o usuário será obrigado a escolher apenas um (o que ele estiver instalando). Da mesma forma será necessário informar o nome do diretório onde será feita a instalação. Depois da instalação do software, o script fará algumas customizações específicas do sistema sobre o qual está rodando e depois entrar na fase de licença.
2. Os produtos da PGI utilizam o gerenciador de licenças FLEXlm da Globetrotter Software. Uma vez que os produtos são limitados a uma única máquina e usuário, não há necessidade de serem executados servidores de licença.
3. O script de licença pede que sejam fornecidos o nome do usuário, o username e o e-mail. Depois disso, é criada uma licença provisória de 15 dias e impressa uma mensagem na tela que deverá ser copiada e enviada para o e-mail license@pgroup.com
4. Essa mesma mensagem também será salva no arquivo $PGI/license.info.
5. Após essas informações serem enviadas para a PGI, será fornecida uma licença permanente. Uma vez obtida essa licença, essa deve ser gravada no arquivo $PGI/license.dat.

Juntamente com o pacote PGI, é fornecido uma vasta documentação de todas as funcionalidades dos compiladores. Todas essas informações estão em formato HTML e podem ser recuperadas com um comando do tipo:

        netscape $PGI/doc/pgi.index.html

Tanto com a licença provisória, ou com a definitiva, são necessários alguns comando para acessar os programas do pacote:

        setenv PGI /usr/pgi
        set path = ( $PGI/linux86/bin $path )
        setenv MANPATH "$MANPATH":$PGI/man

Ou no caso de o shell utilizado ser o ksh:

        PGI=/usr/pgi
        export PGI
        PATH=$PGI/linux86/bin:$PATH
        export PATH
        MANPATH=$MANPATH:$PGI/man
        export MANPATH

Note que os comandos acima assumem que o produto instalado é a versão Linux86 dos pacotes. Como o pacote existe também para Solaris86, deve-se fazer a substituição nos diretórios. O usuário deve também colocar esses comandos nos arquivos de startup de suas seções.

O usuário pode verificar a versão dos produtos instalados apenas adicionando as opções "-dryrun -V" a qualquer um dos programas contidos no pacote. Essa opção também faz com que seja mostrado ao usuário todos os passos que compõem a compilação e a ligação dos programas:

• Para o Fortran 77, use "pgf77 -dryrun -V x.f".
• Para o Fortran 90, use "pgf90 -dryrun -V x.f".
• Para o HPF, use "pghpf -dryrun -V x.f".
• Para o C++, use "pgCC -dryrun -V x.c".
• Para o C, use "pgcc -dryrun -V x.c".

Implementação das Threads do compilador

Os compiladores PGI Linux usam a biblioteca de threads Linuxthreads criada por Xavier Leroy para realizar o multiprocessamento. Esta biblioteca implementa a API Posix 1003.1c para threads e roda em qualquer sistema Linux com kernel 2.0.0 ou mais recente (que suporte multiprocessamento) e uma adequada biblioteca C (reentrante). Este pacote é necessário também para o caso de o usuário desejar fazer a paralelização de seus programas diretamente. Está disponível em ftp://ftp.pgroup.com/x86/linux86-patches/linuxthreads-0.6.tar.gz.

A implementação das LinuxThreads segue o modelo "um-para-um", onde cada threads é efetivamente um processo separado no kernel. Portanto, o escalonamento das threads se dá da mesma maneira que o escalonamento de processos usuais. As threads são criadas com a chamada de sistema clone() do Linux, uma generalização do fork() que permite ao novo processo compartilhar o espaço de memória, descritores de arquivo e manipuladores de sinal da thread pai. Segundo o autor, as vantagens deste modelo incluem:

• overhead mínimo em multiprocessamento intensivo (uma thread por processador);
• overhead mínimo em operações de I/O;
• implementação simples e robusta (o escalonador do kernel faz a maior parte do trabalho).

Durante a implementação, foram considerados ainda outros dois modelos. No modelo "muitos-para-um", as threads são implementadas em nível de usuário. Portanto, as trocas de contexto entre as threads devem ser feitas neste nível. As threads são vistas pelo kernel como um único processo. Este modelo foi totalmente descartado, pois ele não tira vantagem do multiprocessamento e dificulta a implementação do controle de acesso nas operações de I/O. Há várias bibliotecas de threads que utilizam este modelo, mas em geral são deficientes em funcionalidade, desempenho e/ou robustez.

O outro modelo "muitos-para-muitos" é uma combinação dos outros dois modelos, procurando combinar as vantagens de cada um. Há vários processos rodando em nível de kernel, cada um com um escalonador em nível de usuário que seleciona as threads do usuário. A maioria dos sistemas comerciais Unix implementa threads POSIX desta forma (Solaris, Digital Unix, IRIX). Embora seja melhor do que o modelo escolhido pelo LinuxThreads, é bem mais difícil de implementar e exigiria mudanças no kernel do Linux.

Otimizações

Os compiladores PGI possuem várias otimizações de código. Podem ser, em um primeiro momento, otimizadas para gerar código para a arquitetura existente. Com o flag "p6", por exemplo, o código será otimizado para Pentium PRO e Pentium II.

Basicamente existem três níveis de otimização que podem ser invocados na linha de comando durante a compilação pelo flag "-O". O nível 0 não provê nenhuma otimização, gerando o código normalmente. Este nível deve ser utilizado, por exemplo, para possibilitar a depuração. O nível 1 provê otimizações locais e o nível 2 otimizações globais. Geralmente as otimizações globais têm um resultado melhor, porém, em algumas exceções, pode ser mais eficiente um código otimizado pelo nível O1. Além destes níveis, existem parâmetros para fazer Otimizações de laços (por vetorização, paralelização ou unrolling) e inclusão de funções dentro do código (função inline).

Otimização Local (-O1)

Otimiza muito bem códigos que são muito irregulares e que não contenham muitos desvios provocados por comandos do tipo If-Then-Else ou laços como For-Do, While-Do. Otimiza apenas blocos de instruções, sendo estes compreendidos como trechos de códigos sem desvios do fluxo de instruções.

As otimizações feitas são:

• Algebraic identity removal: substitui operações algébricas pelo seu resultado. Operações como, por exemplo, "A+0" ou "A*1" serão substituídas por "A".
• Common Subexpression Elimination: procura por expressões matemáticas repetidas, como por exemplo: "A=B*C+X+B*C" que pode ser otimizada por: "Temp=B*C; A=Temp+X+Temp".
• Constant folding: resolve operações com constantes. Por exemplo, "A=1+3+5" será substituído por "A=9".
• Redundant Load e Store Elimination: remove instruções aritméticas que tem seu efeito anulado pela instrução seguinte. Ex. A=B+C; A=B+2, neste caso o compilador elimina a primeira instrução (A=B+C).
• Strength reduction: tenta substituir operações matemáticas por equivalentes com custo de processamento menor. Por exemplo, substituir a multiplicação por 4 por dois shift-left do número.

Este tipo de otimização analisa especialmente as regiões de interações (loops). Oferece um melhor resultado para códigos com muitas iterações e estas regulares e curtas. São feitas as seguintes otimizações neste nível:

• Branch to Branch Elimination: procura eliminar desvios desnecessários, ou simplificá-los.
• Constant propagation: substitui constantes pelo seu valor. Na Tabela 1 podemos ver um exemplo.

• Copy Propagation: substitui uma variável por uma cópia sua para possibilitar a remoção de variáveis. Ex: Tabela 2: Depois da otimização a atribuição X=T3 pode ser removida.

• Dead Store Elimination: elimina armazenamento de variáveis que o programa não precisa mais. Os códigos otimizados mostrados nos exemplos acima são exemplos de variáveis sem uso. Em ambos a variável "X" não é mais usada e pode ser removida.
• Global Register Allocation: utiliza registradores para manipular dados muito usados. O custo de acesso a um registrador é bem menor que o acesso à memória. Assim sendo, tem-se um ganho de desempenho satisfatório se dedicar-se um registrador para uma variável muito utilizada.
• Invariant Code Motion: transfere códigos dentro de laços que fazem a mesma coisa em todas as iterações para antes do laço, executando-o uma única vez.
• Induction Variable Elimination: Localiza variáveis que são incrementadas constantemente dentro dos laços e simplifica estas incrementações.

• Unreachable Code Elimination: Remove códigos que não serão executados.

Outra otimização disponível é a possibilidade de vetorizar-se iterações dos laços.

Parâmetro: -Mvect
 

• Loop interchange: troca a ordem dos laços, deixando o maior como mais externo.

Paralelização de laços

Possibilita dividir laços em partes e enviá-las para cada processador executá-las. Deve se ter cuidado ao utilizar esta opção pois o overhead gerado para gerenciar a troca de informações entre os processadores envolvidos pode ser maior que o ganho obtido.

Parâmetro: -Mconcur

Unrolling de laços

Possibilita executar mais de uma iteração por laço.

Parâmetro: -Munroll

Otimização por inclusão de Função inline

Coloca o código da função no lugar de sua chamada, aumentando a performance pelo fato de não haver desvios, melhorando a possibilidade das outras otimizações terem sucesso. Também aumenta o tamanho do código.

Otimizações padrão

As técnicas de otimizações usadas pelos compiladores PGI dependem dos parâmetros passados na linha de comando e alguns podem ser ignorados pelo uso de outros. Por exemplo, se usar a opção -Mvect que tenta vetorizar laços, o nível de otimização automaticamente passa a ser o global (-O2), mesmo que exista uma parâmetro com otimização menor. Se não for usado nenhuma opção de otimização, o nível padrão será o nível 1. A Tabela 6 mostra o nível de otimização empregado para os diversos parâmetros passados.

PGPROF - PGI Profiler

O pgprof é um dos módulos distribuídos com os compiladores PGI e tem como objetivo oferecer meios de analisar o desempenho dos programas paralelos gerados com estes compiladores. Tanto programas em C, como em C++ e em Fortran podem ser analisados. Com as análises é possível encontrar pontos onde o desempenho do programa pode ser melhorado e assim otimizar a execução.

O pgprof funciona apenas como um visualizador dos dados que são recolhidos durante a execução dos programas e gravados num arquivo chamado pgprof.out. São exibidas estatísticas que levam em conta o tempo de execução de linhas de programas e subrotinas. A visualização é feita graficamente, mas é possível rodar o pgprof também em linha de comando. A segunda opção é utilizada principalmente quando não há interface gráfica disponível, como em sessões de login remoto.

O processo completo de profiling é formado basicamente por três partes: compilação, execução e análise.

Compilação

Para utilizar o pgprof é necessário informar a opção Mprof=func ou Mprof=lines durante a compilação dos programas. Com a primeira opção se tem o registro da execução em nível de rotinas, enquanto na segunda se tem tanto em termos de rotinas como em linhas de código. O código é então instrumentado com as rotinas de coleta de dados.

Execução

Durante a execução, o profiler coleta vários dados a respeito do programa que está rodando e os salva num arquivo (pgprof.out). Em geral, são registrados o número de chamadas às funções e o tempo de execução de determinadas porções de código. O tempo de execução dos programas cresce bastante quando este trabalho é realizado. Nos exemplos mostrados a seguir pode ser constatado que o tempo de execução fica várias vezes maior. O aumento do tempo depende muito dos dados que devem ser coletados. Por exemplo, se o programa realiza muitas chamadas a subrotinas, o tempo de coleta dos dados tende a aumentar.

Análise

Na fase de análise são apresentados os dados coletados durante a execução. A análise é feita principalmente através de gráficos que apresentam estatísticas sobre diversos tipos de dados coletados. Os principais tipos de estatísticas são os seguintes:

• bytes, bytes recebidos e bytes enviados: usados somente com o compilador HPF (não estão disponíveis para o pgcc e o pgCC, portanto), indicam o número de bytes enviados e recebidos por uma função ou linha de programa;
• contagem: número de vezes que uma função ou linha de código é executada;
• chamadas: número de vezes que uma função é chamada;
• cobertura: percentagem de linhas de uma função que foram executadas pelo menos uma vez;
• mensagens, mensagens recebidas e enviadas: somente para profiles do HPF, informa o número de mensagens recebidas e enviadas por uma função ou linha do programa;
• custo de função: soma das diferenças entre o tempo de saída e de entrada de todas as chamadas a determinada função;
• tempo de função: custo de uma função, desconsiderando o custo das funções chamadas dentro da função;
• tempo de linha: custo de execução de uma linha de código, isto é, a soma de todos os tempos gastos na execução desta linha de código.

Os problemas existentes com a execução do profiling é a intromissão que isto causa na execução dos programas. Como visto, o tempo de execução dos programas cresce muito com esta opção. Outro problema apontado na documentação da ferramenta é a baixa precisão do relógio de algumas arquiteturas de hardware. Quando a precisão não é grande, são necessários vários segundos de CPU para que uma análise mais correta seja feita. Caso contrário, pode haver distorções.

A análise dos dados fica prejudicada também quando há grande otimização de código. Em certos casos fica difícil se associar o número da linha do código fonte ao código que realmente está executando. Devido a otimizações, pode não haver correspondência biunívoca entre linhas de código e código objeto.

Embora os programas estejam rodando em ambientes com múltiplos processadores, programas paralelos criados com o uso de diretivas ou da opção -Mconcur terão registrados apenas os tempos da thread mestre.

Avaliação

A fim de se fazer uma pequena avaliação do compilador, foram testadas duas aplicações com grande potencial de paralelismo:

• Mandelbrot: clássico fractal de Mandelbrot. O algoritmo foi implementado desde o início;
• Raytracer: implementação do algoritmo raytracing de computação gráfica. O programa usado foi adaptado a partir de um já existente.

A obtenção dos tempos a seguir foi feita através da inserção de rotinas de cálculo do tempo em meio ao código da aplicação. Somente o tempo de execução do laço paralelizado foi medido, evitando a interferência de outras partes do código que não tivessem sido paralelizadas e por isso pudessem interferir na análise do tempo.

Como dado adicional, para analisar o nível de interferência do sistema de monitoração, os mesmos tempos foram calculados também quando escolhida a opção de coleta de dados para análise do pgprof. Todos os testes foram executados em um computador PC com dois processadores Pentium Pro com clock de 200 MHz.

Para se compilar estes programas e obter o máximo de paralelismo foram necessárias pequenas alterações nos seus códigos fontes. Tais alterações foram feitas para que se evitassem dependências em laços e se facilitasse ao compilador a descoberta de porções de código paralelizáveis.

Fractal de Mandelbrot

Código Fonte

O programa foi inicialmente desenvolvido para funcionar de maneira seqüencial. Após o teste do funcionamento nesta situação, ele foi compilado com as opções de paralelização. Entretanto, além disso foi necessário se alterar o código fonte, pois somente com as opções de compilação o compilador não era capaz de detectar todos os laços que poderiam ser paralelizados.

Neste exemplo, para que o laço principal fosse paralelizado, no lugar do código do laço foi colocada uma chamada a uma função e o programa foi compilado com a opção -Mconcur=call. Com esta opção, o compilador gera código que executa as várias iterações do laço em paralelo. No código do fractal, o laço principal ficou dessa maneira:

for (y = 0; y < height; y++)
{
    f(iteracoes, x1, y1, x2, y2, y);
}

Como a função f pode ser executada independentemente de outras chamadas, o código pode ser paralelizado.

#include <sys/time.h>
#include <stdio.h>
 
#define INIT_X1 ((long double) -2)
#define INIT_Y1 ((long double) -1)
#define INIT_X2 ((long double) 1)
#define INIT_Y2 ((long double) 1)
#define ITER 150
 
int fractal[1024][768];
int width;
int height;
 
/* limites reais do fractal */
long double mx1, my1, mx2, my2;
int iter; /* numero de iteracoes */
 
void
f(int iteracoes, long double x1, long double y1, long double x2,
long double y2, int y)
{
    long double s, t, a, b, z;
    int x;
    int k;
    struct timeval tp1, tp2;
    int sec, usec;
    long double h, w;
    h = (long double) height / (y1 - y2);
    w = (long double) width / (x2 - x1);
    t = (long double) y / h + y2;
    for (x = 0; x < width; x++)
    {
        s = (long double) x / w + x1;
        a = s;
        b = t;
        for (k = iteracoes; k; --k)
        {
            z = a * a - b * b + s;
            b = 2 * a * b + t;
            if ((a * a + b * b) > 4)
                break;
            a = z;
        }
    fractal[x][y] = k;
    }
}

void mandelbrot(int iteracoes, long double x1, long double y1, long double x2,
long double y2)
{
    long double s, t, a, b, z;
    int x, y, k, count;
    int sec, usec;
    struct timeval tp1, tp2;
    long double h, w;
     
    gettimeofday(&tp1, NULL);
    printf("Initial time = (%i s, %i us)\n", tp1.tv_sec, tp1.tv_usec);
    h = (long double) height / (y1 - y2);
    w = (long double) width / (x2 - x1);
     
    for (count = 0; count < 10; count++)
        for (y = 0; y < height; y++)
            {
                f(iteracoes, x1, y1, x2, y2, y);
            }
    gettimeofday(&tp2, NULL);
    printf("Final time = (%i s, %i us)\n", tp2.tv_sec, tp2.tv_usec);
    sec = tp2.tv_sec - tp1.tv_sec;
    usec = tp2.tv_usec - tp1.tv_usec;
    if (usec < 0)
    {
        usec += 1000000L;
        sec -= 1;
    }
    printf("** Time = %i s, %i us\n", sec, usec);
}

int
main(argc, argv)
int argc;
char *argv[];
{
    int color;
    int i;
     
    width = 300;
    height = 200;
    color = 0;
    iter = 2000;
    i = 0;
    while (++i < argc)
    {
        if (argv[i][0] == '-')
        {
            if (!strcmp(&argv[i][1], "w"))
                width = atoi(argv[++i]);
            else
                if (!strcmp(&argv[i][1], "h"))
                    height = atoi(argv[++i]);
                else
                    if (!strcmp(&argv[i][1], "c"))
                        color = atoi(argv[++i]);
                    else
                        if (!strcmp(&argv[i][1], "i"))
                            iter = atoi(argv[++i]);
                        else
                            if (!strcmp(&argv[i][1], "h"))
                            {
                                printf("Usage: %s [-w <width] [-h <height>] [-c <color=0,1>] [-i iterations>] [-h]\n", argv[0]);
                                printf("-w\tscreen width\n");
                                printf("-h\tscreen height\n");
                                printf("-c\tuse colors (0=gray, 1=color)\n");
                                printf("-i\tinitial number of iterations\n");
                                printf("-h\tthis help\n");
                                printf("Type %s -h for help\n", argv[0]);
                                exit(0);
                            }
                            else
                                printf("Option %s unrecognized\n", argv[i]);
        }
    }
    mx1 = INIT_X1;
    my1 = INIT_Y1;
    mx2 = INIT_X2;
    my2 = INIT_Y2;
     
    mandelbrot(iter, mx1, my1, mx2, my2);
}

Tempos medidos

Os tempos foram medidos através de instrumentação no próprio programa. Isto foi feito para que se medisse apenas a porção de código de interesse, ou seja, o laço principal do programa que foi paralelizado. Para cada número de iterações (número de vezes que o laço principal do programa é executado), foram tomadas medidas de três execuções do programa inteiro. O valor apresentado na tabela é uma média aritmética desses três valores.
 

iter	seqüenc	paralelizado - 1 CPU		2 CPUs		speedup
		normal	profiling	normal	profiling	seq	normal	profiling
1	5,9002	6,3233	24,4688	3,2749	12,8849	1,8016	1,9309	1,8990
2	11,7991	12,6381	42,6776	6,4850	21,8958	1,8194	1,9488	1,9491
3	17,7011	18,9482	64,2260	13,0204	43,7087	1,3595	1,5321	1,4394
4	23,5311	25,2840	85,3383	12,9069	43,6796	1,8231	1,9590	1,9537
5	29,2945	31,5943	106,7044	19,4334	65,6776	1,5074	1,6258	1,6247
6	35,1479	37,9064	128,1446	19,4268	65,4433	1,8092	1,9512	1,9581
7	41,3924	44,2088	149,3315	25,8060	86,4653	1,6040	1,7131	1,7271
8	46,8590	50,4773	170,4758	25,5337	86,2736	1,8352	1,9769	1,9760
9	52,7512	56,7881	191,7492	32,0816	107,8831	1,6443	1,7701	1,7774
10	58,5693	63,8537	213,5277	32,4585	107,7064	1,8044	1,9672	1,9825

A coluna seqüenc exibe os tempos para o programa compilado sem opção de otimização. O speedup seq é calculado se dividindo este tempo pelo tempo de execução do programa em duas CPUs. Já o speedup normal e profiling são calculados se dividindo os tempo das execuções do código paralelizado em 1 CPU pelo tempo das 2 CPUs, sem e com profiling, respectivamente.

Como era de se esperar, os tempos de execução do programa compilado sem opções de otimização foram menores do que os tempos para a execução do programa paralelizado mas que rodou em apenas uma CPU. Pode-se verificar que a diferença ficou em torno de 10%.

Analisando-se o gráfico do speedup do algoritmo de Mandelbrot, percebe-se um comportamento estranho. Nos tempos de execução na Tabela 7, tem-se que o tempo de execução do programa para x iterações, com x ímpar, é praticamente o mesmo tempo para x + 1 iterações. Isto se deve à maneira como a paralelização do laço ocorre. No programa se tem o seguinte laço:

for (count = 0; count < 10; count++)
    for (y = 0; y < height; y++)
    {
        f(iteracoes, x1, y1, x2, y2, y);
    }

A variável count indica o número de iterações do laço (no caso 10 iterações). Quando fez a paralelização, o compilador tomou o laço mais externo, isto é, o laço que controla o número de iterações. Portanto, quando o número de iterações é ímpar, a distribuição das tarefas será desigual entre os processadores e o tempo de execução total levará em conta o tempo do processador que recebeu a maior quantidade de trabalho.

Quando o número de iterações é pequeno, a diferença no speedup é maior. Entretanto, à medida que este número cresce, a diferença de trabalho entre os processadores fica proporcionalmente menor e a diferença de speedup não se ressalta de maneira tão significativa como acontece com um número pequeno de iterações.

Raytracer

Código Fonte

O código fonte deste programa já estava disponível e funcionando seqüencialmente. Apenas foram feitas pequenas modificações para que passasse a utilizar mais de uma CPU.

#include <sys/time.h>
#include <stdio.h>
#include "typedefs.h"
#include "maindecl.h"
 
double line[SCREENHEIGHT][SCREENWIDTH][3];
 
void f(int line_y, int pixel_x, t_3d scrnx, t_3d scrny, t_3d firstray)
{
    t_3d ray;
    t_color color;
    double dis;
     
    ray.x = firstray.x + pixel_x*scrnx.x - line_y*scrny.x;
    ray.y = firstray.y + pixel_x*scrnx.y - line_y*scrny.y;
    ray.z = firstray.z + pixel_x*scrnx.z - line_y*scrny.z;
    normalize(&ray);
     
    /* raio atual */
    color = background;
    dis = intersect(-1, &eyep, &ray, &color);
    line[line_y][pixel_x][0] = color.r;
    line[line_y][pixel_x][1] = color.g;
    line[line_y][pixel_x][2] = color.b;
}

void main(void)
{
    int line_y, pixel_x;
    t_3d scrnx, scrny, firstray;
    struct timeval tp1, tp2;
    int sec, usec;
    int i;
     
    setup();
    viewing(&scrnx, &scrny, &firstray);
    startpic(outfilename, sizey, sizex);
    gettimeofday(&tp1, NULL);
    printf("Initial time = (%i s, %i us)\n", tp1.tv_sec, tp1.tv_usec);
    for (i = 0; i < 10; i++)
        for (line_y = 0; line_y < sizey; line_y++)
        {
            for (pixel_x = 0; pixel_x < sizex; pixel_x++)
            {
                f(line_y, pixel_x, scrnx, scrny, firstray);
            }
        }
    gettimeofday(&tp2, NULL);
    printf("Final time = (%i s, %i us)\n", tp2.tv_sec, tp2.tv_usec);
    sec = tp2.tv_sec - tp1.tv_sec;
    usec = tp2.tv_usec - tp1.tv_usec;
    if (usec < 0)
    {
        usec += 1000000L;
        sec -= 1;
    }
    printf("** Time = %i s, %i us\n", sec, usec);
    printf("Writing output file...");
     
#pragma noconcur
    /* evita que o loop seja paralelizado (devido aos problemas com a libc) */
    for (line_y = 0; line_y < sizey; line_y++)
    {
        linepic(line[line_y]);
    }
    printf(".ok\n");
    endpic();
}

Estatísticas

Como no caso do exemplo anterior, foram executados testes que envolviam a repetição do laço principal do programa variando de 1 a 10 vezes. Para cada teste, foram tomadas as medidas de três execuções e foi calculada a média aritmética entre essas medidas.
 

iter	seqüenc	paralelizado - 1 CPU		2 CPUs		speedup
		normal	profiling	normal	profiling	seq	normal	profiling
1	1,7894	1,5886	7,6951	0,5612	3,7576	3,1885	2,8307	2,0479
2	2,9147	2,2780	15,2379	1,4857	7,4986	1,9618	1,5333	2,0320
3	3,4987	3,4119	22,4843	2,6187	15,2084	1,3360	1,3029	1,4784
4	4,3418	3,9945	29,9408	2,7394	15,2037	1,5849	1,4582	1,9693
5	5,1778	4,9630	37,4001	3,5488	22,7892	1,4590	1,3985	1,6411
6	6,2556	5,9366	44,8678	3,6503	22,8354	1,7137	1,6263	1,9648
7	6,9870	6,9054	52,3345	4,1865	30,3938	1,6689	1,6495	1,7245
8	7,9712	7,9012	59,7899	4,1521	30,3468	1,9200	1,9029	1,9702
9	8,9614	8,8540	67,2544	5,4027	38,2625	1,6587	1,6388	1,7577
10	9,9403	9,8441	74,7648	5,3505	38,1951	1,8578	1,8399	1,9574

Fator curioso nos resultados de speedup está no fato de haver speedups maiores do que 2, isto é, maior do que o próprio número de CPUS. Entretanto, isto pode ser explicado pelo fato de o tempo de execução ter sido muito pequeno (aconteceu quando o número de iterações foi 1), portanto não tendo valor significativo para análise. À medida que o número de iterações e o tempo de execução crescem, os valores resultantes passam a ser considerados válidos e dentro da faixa esperada.

Analisando-se o gráfico da Figura 6, percebe-se também o mesmo fenômeno ocorrido no gráfico do speedup do programa do fractal de Mandelbrot. Novamente, foi paralelizado laço mais externo que contabilizava o número de iterações, fazendo com que um número ímpar de iterações causasse uma distribuição de tarefas desigual para os dois processadores.

Problemas encontrados

Durante a realização dos testes de paralelização, houve problemas com a execução correta dos programas paralelizados quando estavam envolvidas nos laços instruções de entrada e saída. Os resultados se tornaram totalmente imprevisíveis quando se paralelizaram loops com saída para disco e vídeo. Em alguns casos, o resultado final foi incorreto e em outros a execução foi abortada de forma anormal. Quando a paralelização foi desabilitada para tal laço, a execução passou a ser feita normalmente.

Na documentação da biblioteca LinuxThreads, usada pelo compilador PGI, foram encontradas as respostas para estes problemas. Tanto a biblioteca C padrão como os arquivos binários do X Windows deveriam suportar as threads. No caso da biblioteca C, uma nova versão deveria ser instalada (glibc 2). O X Windows deveria ser recompilado com a opção -D_REENTRANT, que instrui o compilador a fazer as alterações corretas para que o código gerado funcione bem em conjunto com as threads. Como o ambiente utilizado para o teste do compilador não é "thread-safe", tais problemas ocorreram.

Conclusão

Apesar de realizar paralelização implícita, o programador ainda deve conhecer as características do seu programa e do compilador a fim de obter o maior desempenho possível. Em muitos casos é necessário ainda que o programador efetue pequenas alterações no código a fim de adequá-lo às otimizações do compilador.

Em relação ao desempenho, pode-se comprovar através dos exemplos que o código gerado foi realmente mais eficiente. Quando a aplicação é adequada ao processamento paralelo, a eficiência fica próxima da eficiência ótima.

Embora o pgCC seja compilador de C++, isto é, orientado a objeto, as otimizações realizadas restringem-se aos laços e estruturas vetoriais. Assim, a distribuição não ocorre em nível de objeto, mas em nível de código fonte, ou seja, as otimizações são as mesmas realizadas pelo compilador C.