Instituto de Física de São Carlos - IFSCUniversidade de São Paulo - USP

Francisco Aparecido RodriguesOrientador: Gonzalo Travieso

Técnicas de orientação ao objeto para computação

científica paralela

Introdução

MOTIVAÇÃO

A construção de programas paralelos que ofereçam alto desempenho é complexa

A interface de uso que muitas bibliotecas numéricas paralelas oferecem é pouco amigável

OBJETIVOS

Desenvolver uma biblioteca paralela que ofereça alto desempenho e que possua uma interface amigável

IntroduçãoIN

TR

OD

UÇ

ÃO

Os computadores paralelos são usados para suprir as necessidades que os computadores seqüenciais não conseguem.

“Um computador paralelo é uma coleção de elementos de processamento que se comunicam e cooperam na resolução de grandes problemas de forma rápida”

(Almasi)

Computação paralelaIN

TR

OD

UÇ

ÃO

Grupo de computadores completos interconectados com sistema operacional distribuído

Oferecem

Escalabilidade absoluta

Escalabilidade incremental

Alta disponibilidade

Melhor relação custo desempenho

ClustersIN

TR

OD

UÇ

ÃO

Maneira mais comum:

Utilizando uma linguagem seqüencial conjuntamente com uma biblioteca paralela que permita a troca de mensagens.

PVM – Paralell Virtual Machine

MPI – Message Passing Interface

Desenvolvimento de softwares paralelosIN

TR

OD

UÇ

ÃO

Bibliotecas Paralelas

Padrão de biblioteca de passagem de mensagem para sistemas paralelos.

Baseado na troca de mensagem entre processadores através das diretivas send/receive

O MPI é baseado em 4 conceitos:1. Processos2. Comunicadores3. Mensagens4. Tipos de dados

O programador deve especificar: Instante em que uma comunicação deve ocorrer

Quais tipos de dados devem ser enviados A comunicação é bloqueante ou não?

MPI – Message Passing InterfaceM

PI

Bibliotecas numéricasB

IBLIO

TEC

AS

NU

MÉR

ICA

S BLAS (Basic Linear Algebra Subprogram)

LAPACK (Linear Algebra Package)

Biblioteca de Álgebra Linear para cálculo de problemas de autovalores, sistemas lineares e problemas de mínimos quadrados paraworkstations e sistemas SPMD,

SCALAPACK (Scalabe LAPACK)

Biblioteca de Álgebra Linear análoga ao LAPACK para computadores de memória distribuída.

Bibliotecas de rotinas similares às do LAPACK

Escrito em FORTRAN

Utiliza passagem de mensagem via MPI ou PVM

Oferece alta perfomance em rotinas de álgebra linear em computadores MIMD Necessita de duas blibliotecas adicionais:

PBLAS (Parallel BLAS)Contém rotinas básicas de álgebra linear para processamento paralelo

BLACS (Basic Linear Algebra Communication Subprogram)Biblioteca de rotinas sícronas de send/receive que usam passagem de mensagem

CaracterísticasS

caLA

PA

CK

EstruturaS

caLA

PA

CK

ScaLAPACK

PBLAS

LAPACK

BLACS

MPI/PVM

BLAS

LOCAL

GLOBAL

Grade de processadoresS

caLA

PA

CK

Exemplo

Distribuição em blocos 1 x 1Exemplo: N = 16 e P = 4Grade: 2 X 2

Distribuição da MatrizS

caLA

PA

CK

P0 P1

P2 P3

MATRIZ GRADE

A11 A12 A13 A14

A21 A22 A23 A24

A31 A32 A33 A34

A41 A42 A43 A44

A11 A13 A12 A14

A31 A33 A32 A34

A21 A23 A22 A24

A41 A43 A42 A44

UtilizaçãoS

caLA

PA

CK

Passos para chamar as rotinas

1 - Inicializar a grade de processadores CALL SLINIT( ... ) CALL BLACS_GRIDINFO( ...)

2 - Distribuir a matriz na grade de processadores

e inicializar os descritores de array CALL DESCINIT( ... )

3 - Chamar a rotina do ScaLAPACK CALL PDSYEVX( ... )

4 - Liberar a grade de processos CALL BLACS_EXIT( ... )

Divididas em três grupos

1. Driver Routines

Resolvem um problema completamente.

Equações lineares, problemas de mínimos quadrados, problemas de autovalores, etc.

2. Computational Routines

Realizam uma computação distinta

Equações lineares, fatorização ortogonal e problemas de mínimos quadrados (fatorização QR, LQ, QR com pivotamento, fatorização ortogonal completa), etc.

3. Auxiliary routines

Rotinas usadas nas subtarefas e algoritimos de particionamento

RotinasS

caLA

PA

CK

PXYYZZZ

P: A primeira letra é para diferenciar das rotinas do LAPACK

X: A segunda letra indica o tipo de dado S : Real D : Double C : Complex Z : Double Complex

YY: As duas próximas indicam o tipo da matriz : Ex: SY – simétrica HE – hermitiana TR – triangular

ZZZ: As três últimas indicam a computação

Exemplos:

PDTRSVX – rotina para resolver sistemas de equações lineares com matrizes triangulares

PDSYEVX – rotina para calcular autovalores e autovetores de uma matriz simétrica double

PSGEBRD – rotina que realiza uma redução bidiagonal de uma matriz geral single

Nomenclatura das rotinasS

caLA

PA

CK

Orientação ao Objeto

O termo orientação a objetos significa organizar o mundo real como uma coleção de objetos que incorporam estrutura de dados e um conjunto de operações que manipulam estes dados.

Todas as linguagens orientadas a objetos possuem três características básicas:

1. Encapsulação

2. Herança

3. Polimorfismo

ConceitosO

rien

tação a

o O

bje

to

É um tipo de dado, como os já conhecidos, para declarar variáveis

Uma variável de uma classe é chamada de Objeto.

Definir uma classe não cria um objeto, assim como um tipo de variável NÃO é uma variável

ClassesO

rien

tação a

o o

bje

to

É uma entidade lógica que contém dados e código para manipular esses dados

ObjetosO

rien

tação a

o O

bje

to

Class Carros {Cambio, acelerador, voltante, ...

public:Acelerar ( );Frear ( );Trocar_marcha ( );Virar_esquerda ( );...

};Class Carros BMW;

HerançaO

rien

tação a

o O

bje

to É o processo em que um objeto pode adquirir as características de outro objeto

VEÍCULOS (SUPERCLASSE)

CLASSE CARROS CLASSE MOTOS

AcelerarFrear

Virar para esq....

Matrizes podem ser representadas como uma abstração de problemas de álgebra linear

Uma matriz específica seria um objeto da classe e as operações sobre elas os métodos da classe

Matrizes e objetosO

rien

tação a

o O

bje

to

Biblioteca desenvolvida

Oferece rotinas para matrizes:

Simétricas com simples precisão

Simétricas com dupla precisão

Hermitianas com simples precisão

Hermitianas com dupla precisão

Parallel Object Oriented Linear AlgebraP

OO

LA

Li

Métodos oferecidos

Acesso por índice global / local

Cálculo de autovalores e/ou autovetores

Atribuição e redistribuição de matrizes

Adição de matrizes

Subtração de matrizes

Multiplicação de matrizes

Facilidades oferecidas

Interface amigável

Encapsulação dos dados, ou seja, interface independente da implementação

Simplificação de uso

CaracterísticasP

OO

LA

Li

Interface e métodosP

OO

LA

Li

template<typename elem_type, typename precision_type>class DistMat{ public: DistMat ( const int M, const int N, const Grid &g,

const int MB = 1, const int NB = 1 ); DistMat ( const DistMat<elem_type,precision_type> &A ); elem_type *local_matrix(); int rows(); int cols(); int block_rows(); int block_cols(); int local_rows(); int local_cols(); elem_type &operator()( const int I, const int J ); elem_type &local( const int i, const int j ); virtual void eigen( precision_type *eigenval) = 0; virtual void eigen( precision_type *eigenval, int il,

int iu) = 0;...

virtual ~DistMat();};

Interface e métodosP

OO

LA

Li

class FloatSymmetric : public DistMat<float,float>{ public: FloatSymmetric (const FloatSymmetric &A)

DistMat<float,float>(A); FloatSymmetric(const int M, const int N, Grid &g,const int MB = 1,

const int NB = 1 ):DistMat<float,float>(M,N,g,MB,NB); FloatSymmetric &operator=( FloatSymmetric A ); friend FloatSymmetric operator+( FloatSymmetric A, FloatSymmetric B); friend FloatSymmetric operator-( FloatSymmetric A,

FloatSymmetric B); friend FloatSymmetric operator*( FloatSymmetric A,

FloatSymmetric B); void eigen( float *eigenval ); void eigen( float *eigenval, int il, int iu ); void eigen( float *eigenval, float vl, float vu ); void eigen( float *eigenval,

DistMat<float,float> &eigenvec ); void eigen( float *eigenval, DistMat<float,float> &eigenvec, int il, int iu ); void eigen( float *eigenval, DistMat<float,float> &eigenvec, float vl, float vu ); ~FloatSymmetric(){};}

Análise de desempenho

Algoritmo

I. Iniciar a grade de processadores

II. Distribuir a matriz hamiltoniana

III. Diagonalizar a matriz

IV. Liberar a grade de processadores

Objetivo Comparar o código desenvolvido usando o ScaLAPACK e a biblioteca POOLALi

Problema de física do estado sólidoA

nálise d

e d

esem

pen

ho

Utilizando o ScaLAPACK

Inicialização da grade de processadoresA

nálise d

e d

esem

pen

ho int main(int argc, char *argv[])

{ int rank, nprocs, zero = 0, context, less_one = -1; int nprow, npcol, myrow, mycol; char erre = 'R'; MPI_Init(&argc,&argv); blacs_pinfo__(&rank,&nprocs); blacs_get__(&less_one, &zero, &context); nprow = (int) sqrt(nprocs); while (( nprow!=1 ) && ((nprocs \ nprow) != 0)) nprow--; npcol = (int) (nprocs/nprow); blacs_gridinit__(&context, &erre, &nprow, &npcol); blacs_gridinfo__(&context, &nprow, &npcol, &myrow,

&mycol); blacs_exit__(&zero); return 0;}

Inicialização da grade de processadoresA

nálise d

e d

esem

pen

ho

Utilizando a POOLALi

#include "grid.h"

int main(int argc, char *argv[]){ Parallel p(argc, argv); Grid g(p); return 0;}

Distribuição da matrizA

nálise d

e d

esem

pen

ho

Utilizando o ScaLAPACK

// ... definição dos valores associados à matriz ...// I, J -> Global// i,j -> localfor( I = 0; I < N; I++) { for( J = 0; J < N; J++)

{....value = Hamilton(I,J,n);l = (int)(floor( I/(nprow*mb) ) );m = (int)(floor( J/(npcol*nb) ) );x = I % mb;y = J % nb;i = l*mb + x;j = m*nb + y;if ( ( j*lrow + i ) < lrow*lcol )

ml[ j*lrow + i] = value;...}

}

#include "lib/grid.h"#include "lib/dsymmetric.h"...DoubleSymmetric Matrix(N,N,g,8,8), for( int I = 0; I < N; I++)

{ for( int J=0; J< N; J++)

...Matrix(I,J) = Hamilton(I,J,n);...

}}

Distribuição da matrizA

nálise d

e d

esem

pen

ho

Utilizando a POOLALi

... // declaração das variáveis de entrada na funçãostatic int lwork = -1, liwork = -1;double *work, tmpwork;int *iwork, tmpiwork;ifail = new int[n];iclustr = new int[2*nprow*npcol];gap = new double[nprow*npcol];pdsyevx_(&jobz, &range, &uplo, &n, ml, &ia, &ja, desca, &vl,

&vu, &il, &iu, &abstol,&n_aut, &n_vec, eigenval, &orfac, z, &iz, &jz, descz, &tmpwork, &lwork, &tmpiwork, &liwork, ifail, iclustr, gap, &info);

lwork = int(2*tmpwork);liwork =tmpiwork;work = new double[lwork];iwork = new int[liwork];pdsyevx_(&jobz, &range, &uplo, &n, ml, &ia, &ja, desca, &vl,

&vu, &il, &iu, &abstol,&n_aut, &n_vec, eigenval,&orfac,z, &iz, &jz, descz, work, &lwork, iwork, &liwork, ifail, iclustr, gap, &info);

...

Diagonalização da matrizA

nálise d

e d

esem

pen

ho

Utilizando o ScaLAPACK

Diagonalização da matrizA

nálise d

e d

esem

pen

ho

Utilizando a POOLALi

#include "lib/grid.h"#include "lib/dsymmetric.h"...DoubleSymmetric Matrix(N,N,g,8,8), Vec(N,N,g,8,8);...double *eigenval;eigenval = new (double)[N];Matrix.eigen(eigenval, Vec);...

Comparação de desempenhoA

nálise d

e d

esem

pen

ho

Comparação de desempenhoA

nálise d

e d

esem

pen

ho

Comparação de desempenhoA

nálise d

e d

esem

pen

ho

Conclusão

A utilização de orientação ao objeto ofereceu:

Alto nível de abstração

Interface amigável

Nomenclatura dos métodos é mais intuitiva que as rotinas do ScaLAPACK

Não ofereceu perda de desempenho em relação ao ScaLAPACK

ConclusõesC

on

clu

sões

Extensão da POOLALi para todos os métodos oferecidos pelo ScaLAPACK

Sistemas Lineares, problemas de mínimos quadrados, fatorização LU, inversão matricial, etc

Criação de classes para outros tipos de matrizes

De banda, tridiagonais, ortogonais, triangulares, unitárias, esparsas

Implementação de métodos não oferecidos pelo ScaLAPACK

Equações diferenciais, estatística, visão, etc.

Trabalhos futurosC

on

clu

sões