LINPACK

O benchmark LINPACK é um dos mais utilizados atualmente para medir a performance de supercomputadores (HPC). Um dos motivos para sua popularidade é o fato de ele ser utilizado para medir o desempenho dos 500 supercomputadores atualmente com maior capacidade de processamento (TOP500).
Em sua versão original, ele consiste de um pacote com um conjunto de sub-rotinas para solução de equações de sistemas lineares.
A versão utilizada no TOP500 é uma modificação do Linpack para computadores de memória distribuida, o HPL - High-Performance Linpack. O HPL resolve um sistema de equações linear denso e randômico com aritmética de precisão dupla (64bits). O algoritmo é explicado detalhadamente abaixo.

Algoritmo

O HPL possui diversas configurações diferentes. Para tornar o benchmark mais flexível optou-se por deixar a configuração a cargo do usuário, de modo que ele possa escolher a configuração ideal para a arquitetura utilizada de modo a otimizar o desempenho. Todas as configurações são equivalentes em termos de precisão numerica.

Algoritmo principal

O algoritmo principal consiste na resolução de um sistema linear de ordem n do tipo Ax=b. Primeiramente computa-se a fatoração LU com pivoteamento parcial de linhas da matriz de coeficientes [A b] = [[L,U] y]. Como a matriz triangular inferior L é aplicada em b conforme a fatoração progride, a solução x é obtida resolvendo o sistema triangular superior Ux=y. A matriz triangular inferior L é deixada sem pivoteamento e o array de pivôs não é retornado.

Os dados são distribuidos em uma grade de processos bidimensional de tamanho P x Q de acordo com um esquema cíclico em bloco (block-cyclic). Isto garante um bom balanceamento de carga, assim como a escalabilidade do algoritmo. A matriz de coeficientes n x n+1 é primeiro particionada logicamente em nb x nb blocos, que são ciclicamente distribuidos na grade de processos P x Q. Isto é feito em ambas as dimensões da matriz.

mat2.jpg

Foi escolhida a implementação mais simples da decomposição (fatoração) de Cholesky, conhecida como 'right-looking variant', para o laço principal da fatoração LU. Isso significa que a cada iteração do laço, um painel de nb colunas é fatorado, e a submatriz resultante é atualizada. Deste modo a computação é logicamente particionada com o mesmo tamanho de bloco nb que foi usado para a distribuição dos dados.

-------------------------------------------------------------

Fatoração dos Painéis

Em uma determinada iteração do laço, e por causa da propriedade cartesiana do esquema de distribuição, a fatoração de cada painel ocorre em uma coluna de processos. Esta parte da computação é uma parte crítica do algoritmo. O usuário deve escolher entre três variações de métodos de decomposição de matrizes: Crout, left e right looking variant. O programa permite também que o usuário escolha em quantos sub-painéis o painél atual deve ser dividido durante a recursão. Além disso, é possível selecionar em tempo de execução o critério de parada da recursão em termo do numero de colunas que faltam ser fatorizadas. Quando esse limite é alcaçado, o sub-painel será então fatorizado utilizando uma das três variações (crout, left ou right-looking). Finalmente, para cada coluna do painel que o pivô busca, as operações de troca (swap) e broadcast da linha do pivô são combinadas em um único passo na comunicação. Uma redução de troca binária (binary-exchange) do tipo leave-on-all executa essas três operações ao mesmo tempo.

-------------------------------------------------------------

Comunicação - Transmissão dos Painéis

Quando a fatoração dos painéis tiver sido computada, este painel de colunas é enviado às colunas dos outros processos. Existem muitos algoritmos de broadcast possíveis, e o Linpack oferece 6 variações para serem escolhidas. Estas variações são descritas abaixo assumindo que o processo 0 é o processo fonte (source) que acabou de realizar a computação do painel. Por conveniencia -> significará "envia para".
  • Increasing-ring: 0 -> 1; 1 -> 2; 2 -> 3 e assim sucessivamente. Este algoritmo é o mais clássico; ele tem a desvantagem que o processo 1 precisa enviar uma mensagem.
1ring.jpg
  • Increasing-ring (modificado): 0 -> 1; 0 -> 2; 2 -> 3 e assim sucessivamente. O processo 0 envia duas mensagens e o processo 1 apenas recebe uma mensagem. Este algoritmo é quase sempre melhor que os outros, se não o melhor de todos.
1rinM.jpg
  • Increasing-2-ring: Os Q processos são divididos em duas partes: 0 -> 1 e 0 -> Q/2; Então os processos 1 e Q/2 atuam como fontes de dois anéis (rings): 1 -> 2, Q/2 -> Q/2+1; 2 -> 3, Q/2+1 -> to Q/2+2 e assim sucessivamente. A vantagem deste algoritmo é a redução do tempo em que o último processo receberá o painel, ao passo que a desvantagem é que o processo 0 deve enviar duas mensagens.
2ring.jpg
  • Increasing-2-ring (modificado): Primeiramente 0 -> 1, então os Q-1 processos restantes são divididos em duas partes iguais: 0 -> 2 e 0 -> Q/2; Os processos 2 e Q/2 funcionam como fontes de dois anéis: 2 -> 3, Q/2 -> Q/2+1; 3 -> 4, Q/2+1 -> Q/2+2 e assim sucessivamente. Este algoritmo é um dos melhores juntamente com o increasing-ring modificado.
2rinM.jpg

Referências

HPL Algorithm

Last edited Mar 7, 2008 at 1:10 AM by dfconrad, version 6

Comments

No comments yet.