Comparação: MATMUL versus DGEMM (Multiplicação de Matrizes)

Neste post é feita uma comparação de tempo de processamento (utilizando a função CPU_TIME) entre multiplicações de matrizes quadradas utilizando a função intrínseca MATMUL e a subrotina DGEMM da biblioteca IMSL.

Os dois casos explicados a seguir foram feitos para TAM = 1000, ou seja, para matrizes de tamanho 1000 x 1000.

PRIMEIRO CASO
Para o primeiro caso, as matrizes a serem multiplicadas (A*B) são definidas como:
DO i=1,TAM
DO j=1,TAM
A(i,j) = i + j
B(i,j) = i + j
END DO
END DO

SEGUNDO CASO
Para o segundo caso, as matrizes a serem multiplicadas (A*B) são definidas como:
DO i=1,TAM
DO j=1,TAM
A(i,j) = i - j
B(i,j) = i + j
END DO
END DO



RESULTADOS

Os resultados estão resumidos no seguinte gráfico:

Para os dois casos estudados, MATMUL foi cerca de 5 vezes mais lento que DGEMM.

CONCLUSÕES

Caso você tenha acesso à biblioteca IMSL, vale a pena gastar um pouco de tempo substituindo a função MATMUL pela DGEMM em todos os seus programas que utilizem multiplicação de matrizes.

Caso não tenha acesso a esta biblioteca, vale a pena ver se há outra subrotina que você possa utilizar no lugar da MATMUL e fazer uma breve comparação entre elas.

Comparação (de velocidade de processamento): mesclando código .FOR + .F90, usando ou não subrotinas (funções)...

O QUE É COMPARADO?

Neste post são comparados alguns resultados (de tempo de processamento) para a realização de um conjunto determinado de operações, englobando os casos a seguir. Todos os exemplos foram desenvolvidos utilizando o Compaq Visual Fortran 6.6.


1. F90
O código é todo escrito em Fortran 90. São feitos dois arquivos, MAIN.F90 e FUNC.F90. O programa MAIN chama a função presente em FUNC.F90 um total de NUM_ITE vezes, e repete o procedimento um total de NUM_REPETICOES vezes, obtendo a média do tempo de processamento.


2. F90 + FOR
Semelhante ao caso .F90, sendo que o arquivo MAIN é um .F90, e o arquivo FUNC é um .FOR (formato fixo).


3. F90 Direto
O arquivo FUNC deixa de existir, as operações são inseridas no arquivo MAIN diretamente. O código é todo escrito em F90.


4. FOR Direto
Semelhante ao F90 Direto, mas o código é todo escrito em formato fixo (.FOR).


5. F90 mesclado
Todo o código do arquivo FUNC é inserido após o fim do programa MAIN, de forma que se trabalha com uma subrotina (função) à parte, mas tanto o programa quanto a função ficam presentes no mesmo arquivo. Todo o código é escrito em formato livre (.F90).


6. FOR mesclado
Semelhante ao F90 mesclado, mas o código é escrito em formato fixo.





QUAIS SÃO AS OPERAÇÕES EFETUADAS?


Foram executados três exemplos com diferentes conjuntos de operações, para todos os casos NUM_REPETICOES = 3 (para efetuar a média de tempo de processamento).



PRIMEIRO CONJUNTO DE OPERAÇÕES
Y = X**2
Y = Y + 0.02D0
NUM_ITE = 1E9



SEGUNDO CONJUNTO DE OPERAÇÕES
Y = X**2
Y = Y + 0.02D0
Y = SQRT(Y)
Y = Y/2.25D0
NUM_ITE = 5E8



TERCEIRO CONJUNTO DE OPERAÇÕES
Y = X**2.2D0
Y = Y + 0.0225D0
Y = SQRT(Y)
Y = SIN(Y)
Y = Y/2.25673D0
Y = COS(Y)
NUM_ITE = 5E7






QUAIS FORAM OS RESULTADOS?



O tempo de processamento para cada caso é mostrado na figura abaixo.

CONCLUSÕES

Para os casos estudados:

1 - Mesclar códigos escritos em .FOR com códigos em .F90 não leva a grandes diferenças de custo computacional.

2 - Utilizar subrotinas (funções) em diferentes arquivos ou mescladas num mesmo arquivo não leva a grandes diferenças também.

3 - Efetuar as operações diretamente no código principal é mais rápido do que efetuar as operações em subrotinas (funções) à parte. No entanto, à medida que a complexidade das operações aumenta, o custo de chamada da função perde importância.

Portanto, para grandes problemas (com operações complexas) a clareza de código obtida utilizando subrotinas supera de longe o acréscimo de custo computacional.

4 - Para problemas mais complexos (conjunto de operações 3) todos os seis casos apresentaram praticamente o mesmo custo computacional.

-------------------- x ----------------------- x -----------------------

Comparação - ACESSANDO MATRIZES... (RANK 2 ARRAYS)

Acho que muitos já devem saber (ou ter ouvido falar) que o fortran guarda matrizes na memória "coluna por coluna". Dessa forma, o acesso às mesmas deve ser feito também coluna por coluna, para maior velocidade de execução. O conceito de coluna varia um pouco quando se trabalha com matrizes de mais de duas dimensões, mas de uma forma geral os loops mais internos devem se referir à dimensão mais à esquerda da matriz.
Por exemplo, com uma matriz de três dimensões se teria:

!LOOP mais rápido
DO K=1,N3
DO J=1,N2
DO I=1,N1
A(I,J,K) = ...
END DO
END DO
END DO

Qualquer alteração da ordem desses LOOPs resulta num código mais lento.

Tomando-se o caso de duas dimensões apenas, qual seria a diferença de velocidade do loop mais rápido para o mais lento?

Na busca por respostas para essa pergunta, foi desenvolvido um pequeno projeto no Compaq Visual Fortran 6.6 ( 288Kb). Para uma matriz A de dimensão NxN, onde N=5000, foram rodados 20 vezes os códigos que permitiram colocar o valor de cada elemento da matriz como sendo
A(I,J) = A(I,J) + I**2 + J**2,
acessando linha por linha (mais lento) e coluna por coluna (mais rápido).
O tempo médio e o tempo médio relativo foram obtidos para comparação.
Os resultados foram os seguintes:

Ou seja, para este caso específico a diferença já mostrou ser muito grande. O acesso coluna por coluna chega a ser quase 5 vezes mais rápido que o acesso linha por linha. Um bom motivo para varrer seus códigos-fonte e excluir os loops coluna por coluna deles sempre que possível.

CONCLUSÃO da comparação - LOOPs (DO x DO WHILE x DO "INFINITO")

Após a exposição do caso (http://fortranbr.blogspot.com/2009/06/comparacao-loops-do-x-do-while-x-do.html) e a apresentação de um resultado, seguiu-se longa discussão na comunidade Fortran Brasil. O mesmo projeto foi testado com diferentes casos e diferentes compiladores. Agradecimentos ao pessoal que participou da discussão na comunidade, em especial ao Alexandre, que foi o "causador" da mesma.

ALGUMAS CONCLUSÕES...
O tipo de loop mais rápido varia com os códigos executados no loop e depende também do compilador. De qualquer forma, nos casos em que o DO WHILE foi melhor que os outros, os outros ficaram muito próximos. E no geral o loop do tipo DO foi o que se saiu melhor, pois ele é o mais rápido em alguns casos, e nas vezes que não é ainda assim fica bem próximo do melhor.

Esse loop seria definido genericamente por:
CASO 1 : LOOP DO
DO I=1,N
.
.
.
END DO

E seria "o mais rápido" dos três casos verificados.

Comparação - LOOPs (DO x DO WHILE x DO "INFINITO")

Efetuei uma pequena comparação entre Loops utilizando DO, DO WHILE e DO "INFINITO", baseada na afirmação de Francisco Franco, proprietário da comunidade do orkut Fortran Brasil [], de que o DO WHILE é mais lento que os outros dois.
Os Loops em estudo são definidos genericamente da seguinte forma, onde N é um inteiro:

CASO 1 : LOOP DO
DO I=1,N
.
.
.
END DO

CASO 2 : LOOP DO WHILE
DO WHILE (I<=N) .
.
.
I = I + 1
END DO

CASO 3 : LOOP DO "INFINITO"
LOOP1 : DO
.
.
.
I = I + 1
IF (I==N) EXIT LOOP1
END DO LOOP1

Os resultados INICIAIS encontrados, apresentados na tabela abaixo, confirmaram que o DO WHILE é mais lento que os outros loops acima mostrados.

A tabela mostra os valores obtidos para uma função qualquer, comprovando que a mesma coisa estava sendo calculada nos três casos. Foram feitos dois loops, um dentro do outro, com N=25000, ou seja, 625 milhões de cálculos da função (X = X + (-1**J)*X/N, onde J varia em um dos loops). Tomou-se um tempo relativo ao tempo do Loop Do "Infinito".
Constatou-se PARA ESTE N ESPECÍFICO que o caso 2 demora cerca de 2% a mais de tempo do que a referência, enquanto que o caso 3 leva cerca de 0,7%.

O estudo foi feito utilizando o Compaq Visual Fortran 6.6, e o projeto completo está disponível para download aqui (294Kb).

ATUALIZAÇÃO:
Este mesmo post gerou discussões e mais discussões na comunidade supracitada. Algumas conclusões podem ser vistas AQUI.

Otimização de códigos FORTRAN

Guia RÁPIDO de OTIMIZAÇÃO de códigos FORTRAN visando maior VELOCIDADE de execução...
Detalhes muito interessantes que encontrei no site da Pós Graduação em Engenharia Civil da UFRGS. Vale a pena dar uma lida:
http://www.cpgec.ufrgs.br/masuero/otimizacao/otimizacao.htm .