algoritmos matriciales paralelos y librerías para … · sistemas lineales, mínimos cuadrados,...

Algoritmos Matriciales Paralelos y Librerías para Matrices

Estructuradas

Murcia, Noviembre 2011 Antonio M. Vidal

[email protected]://www.inco2.upv.es/

Contenido• Introducción: De los algoritmos a las librerías• Librerías matriciales y arquitecturas• Librerías de Álgebra Lineal Numérica

– LAPACK– ScaLAPACK– La colección ACTS

• Descomposición QR: aproximación secuencial y paralela • La librería StructPack

– Algoritmos– Funcionalidades

• Conclusiones

• De los algoritmos a las librerías: Un ejemplo sencillo n

n xxxxx ℜ∈+++= ,... 222

21

Algoritmo:

sqrt(Norm)Normend

NormNorm 32for

Norm

2

21

=

+=

=

=

ixni

x,...,,

El algoritmo fracasa si se quiere calcular, en simple precisión,la norma del vector

3222120 ,]10 10 10[ ℜ∈= xx T

Solución

nn xxx

xx

xxxx ℜ∈

++++

+

= ,...1...

2

max

2

max

2

2

max

1max

{ }iixx maxmax =

REAL FUNCTION SNRM2(N,X,INCX)* .. Scalar Arguments ..INTEGER INCX,N* ..* .. Array Arguments ..REAL X(*)* ..** Purpose* =======** SNRM2 returns the euclidean norm of a vector via the function* name, so that** SNRM2 := sqrt( x'*x ).** Further Details* ===============** -- This version written on 25-October-1982.* Modified on 14-October-1993 to inline the call to SLASSQ.* Sven Hammarling, Nag Ltd.** =====================================================================** .. Parameters ..REAL ONE,ZEROPARAMETER (ONE=1.0E+0,ZERO=0.0E+0)* ..* .. Local Scalars ..REAL ABSXI,NORM,SCALE,SSQINTEGER IX* ..* .. Intrinsic Functions ..INTRINSIC ABS,SQRT

• Implementación del BLAS 1

* ..IF (N.LT.1 .OR. INCX.LT.1) THEN

NORM = ZEROELSE IF (N.EQ.1) THEN

NORM = ABS(X(1))ELSE

SCALE = ZEROSSQ = ONE

DO 10 IX = 1,1 + (N-1)*INCX,INCXIF (X(IX).NE.ZERO) THEN

ABSXI = ABS(X(IX))IF (SCALE.LT.ABSXI) THEN

SSQ = ONE + SSQ* (SCALE/ABSXI)**2SCALE = ABSXI

ELSESSQ = SSQ + (ABSXI/SCALE)**2

END IFEND IF

10 CONTINUENORM = SCALE*SQRT(SSQ)

END IF*SNRM2 = NORMRETURN** End of SNRM2.*END

• Implementación del BLAS 1

+

+

+

=

+

++

1

11

2

4

3

2

4

2

2

4

1

2

4

1

2

1

3

2

1

2

xx

xx

xx

xx

xx

xx

Beneficios•Robustez•Precisión•Eficiencia

¿Por qué usar librerías matriciales?

• Desde los principios de la computación científica se entendió la necesidad de utilizar librerías numéricas y matriciales

• Objetivos:– Legibilidad– Eficiencia– Portabilidad– Fiabilidad: calidad de código– No reprogramar códigos sencillos: organización por

niveles

Librerías matriciales y arquitecturas•Computadores secuenciales: …-1980Librerías: Legilibilidad, robustez, portabilidadLINPACK, EISPACK,…

•Operaciones vector-vector: BLAS 1 (1973-1977)

xjaj

* +xjaj b+xjaj

b•Aprovechamiento de las unidades funcionales pipeline: máquinas vectorialesOperaciones matriz-vector: BLAS 2 (1988)

Librerías matriciales y arquitecturas•Optimización del uso de la jerarquía de memoriasUtilización de múltiples procesadores: Operaciones matriz-matriz. Organización por bloques.BLAS 3. (1990)

Memoria masiva (disco)

P: Procesador

C: Cache

Memoria central

P

C

P

C

P

C

•LAPACK: Librería secuencial/paralela (memoria compartida). (1992)Sistemas lineales, Mínimos cuadrados, Valores y vectores propios y singulares, Descomposiciones matriciales

Librerías matriciales y arquitecturas

•LAPACK: Librería secuencial/paralela (memoria compartida). (1992)Conjunto de subrutinas que resuelven:Sistemas lineales, Mínimos cuadrados, Valores y vectores propios y singulares, Descomposiciones matriciales

http://www.netlib.org/lapack/

Implementation Guide for LAPACKUT, CS-90-101, April 1990.E. Anderson and J. Dongarra

LAPACK: A Portable Linear Algebra Library for High-PerformanceComputersUT, CS-90-105, May 1990.E. Anderson, Z. Bai, C. Bischof, J. Demmel, J. Dongarra, J. DuCroz,A. Greenbaum, S. Hammarling, A. McKenney, D. Sorensen

Librerías matriciales y arquitecturas

LAPACK: Librería secuencial/paralela (memoria compartida). (1992)

Filosofía: Algoritmos orientados a bloques•Basados en BLAS•Eficiencia•Portabilidad

Tipos de matrices:•Densas.•Banda.•Reales y complejas.

Utilizable sobre:•Computadores secuenciales.•Multiprocesadores con Memoria compartida

Se trata de emplear como filosofía de diseño:

Núcleos computacionales básicos

Operaciones vector-vectorOperaciones matriz-vectorOperaciones matriz-matriz

Rutinas de alto nivelResolución de sistemasCálculo de valores propiosCálculo de valores singularesDescomposiciones matriciales

Para diseñar algoritmos tipo LAPACK hay que organizar el problemas de forma tal que pueda ser resuelto mediante llamadas a los núcleos computacionales básicos.

BLAS LAPACK

Lineae Algebre PACKBasic Linear Algebra Subprograms


Tipos de rutinas:Rutinas Driver: Resuelve un problema completo (sistemas de ecuaciones)Rutinas computacionales: Realizan una tarea computacional (Desc. LU)Rutinas auxiliares: Realizan una subtarea o trabajo de menor nivel.

Formato de rutinas driver y computacionales: XYYZZZX: Tipo de datos:

S : REALD : DOUBLE PRECISIONC : COMPLEXZ : DOUBLE COMPLEX

YY: Tipo de matrizBD bidiagonalGB general bandGE general (no simétrica, rectangular,..)…..

ZZZ: Operación:SV: sistemas de ecuacionesEV: valores propios ...


Librerías para el modelo de paso de mensajesLa librería ScaLAPACK ( Scalable Linear Algebra Package)

(1995)

• Librería de rutinas de algebra lineal numérica, para ordenadores de memoria distribuida con paso de mensajes.

• Capacidades similares al LAPACK: Sistemas lineales, Mínimos cuadrados, Valores y vectores propios y singulares, Descomposiciones matriciales

• Objetivos:• Eficiencia• Escalabilidad• Fiabilidad• Portabilidad• Flexibilidad• Facilidad de uso

La librería Scalapack. Filosofía y entorno.Se trata de emplear la misma filosofía de diseño que en el LAPACK:

Núcleos computacionales básicos

Operaciones vector-vectorOperaciones matriz-vectorOperaciones matriz-matriz

Rutinas de alto nivelResolución de sistemasCálculo de valores propiosCálculo de valores singularesDescomposiciones matriciales

Problema: Hay que diseñar algoritmos distribuidos para los núcleos computacionales básicos, por ello es necesario un nivel más dedicado a las comunicaciones específicas que se utilizan en estos programas

BLACS PBLAS ScaLAPACKBasic Linear Algebra CommunicationSubprograms

Scalable LAPACKParallel Basic Linear Algebra Subprograms

Scalapack

Global

Local

Scalapack

Pblas

Lapack

Blas

Blacs

Entorno de pasode mensajes(PVM, MPI, ...)

BLACS•Librería de comunicaciones para aplicaciones de algebra líneal,a ejecutarse en multiprocesadores con paso de mensajes.

•Puede funcionar indistintamente sobre PVM, MPI u otras librerías de paso de mensajes.

•Fácil de programar, portable (Clusters de PSs/Workstations, Thinking Machine CM-5, IBM SP series, Cray T3X, Intel IPSC2, IPSC/860, Delta, Paragon, ...

PBLASParallel Basic Linear Algebra Subprograms

Librería de rutinas que implementan versiones paralelas de las rutinas del BLAS para memoria distribuida con paso de mensajes

•Nivel 1: operaciones Vector-Vectory a x + y +

•Nivel 2: operaciones Matriz-Vector y a A x + b y

+•Nivel 3: operaciones Matriz-MatrizC a A B + b C

+

Objetivos:•Portabilidad•Altas prestaciones y escalabilidad•Facilidad de uso

SCALAPACKPrestaciones

Factores que pueden afectar a las prestaciones:

• Topología• Tamaño de bloque• Dimensiones de la malla de procesos•Su eficiencia depende de las implementaciones de BLACS y PBLAS

Para un problema determinado es necesario estudiar los valores óptimos de estos parámetros

Estado actual: Existen implementaciones buenas pero su utilización se hace complicada. No se han desarrollado todas las rutinas que tiene el LAPACK.

Información sobre ScaLAPACKhttp://www.netlib.org/scalapack/slug/index.html

La colección ACTShttp://acts.nersc.gov

• The Advanced CompuTational Software (ACTS) Collection is a set ofsoftware tools for computational sciences. The starting point for thecollection was the former Advanced Computational Testing andSimulation Toolkit Project. The purpose of the ACTS Collection is toaccelerate the adoption and use of advanced computing by theDepartment of Energy programs for their mission-critical problems. While DOE has been motivated to develop the tools for its ownprograms, it also encourages their adoption and use by non-DOE computational efforts. The ACTS Collection Project disseminatesinformation about the tools, both inside and outside the DOE community. In addition, it focuses on the installation, maintenance andsupport of the tools on DOE's computing facilities.

La colección ACTS

La colección ACTShttp://acts.nersc.gov/tools.html

Como se diseñan e implementan algoritmos secuenciales / paralelos para una librería tipo LAPACK / ScaLAPACK?

Trabajo matemático: elegir el mejor método

Trabajo computacional: analizar sus posibilidades computacionales en cuanto a prestaciones como eficiencia, robustez, precisión, análisis de error…

Trabajo de implementación: seguir una metodología de implementación precisa y contrastada

Ejemplo: Descomposición QR en LAPACK /ScaLAPACK

Descomposición QRDeseamos obtener una nueva descomposición de una matriz A∈ℜ mxn , en la forma:

Puede utilizarse también para resolver sistemas de ecuaciones lineales generales

bQRxbQRxbAx T=⇔=⇔=

superiorr triangula, y )( ortogonal , con , 1 RQQQQRA Tmm −× =ℜ∈=

Las transformaciones ortogonales conserva la 2-norma vectorial:

22)()( xxxQxQxQxQxQx TTTT ====

La descomposición QR se puede calcular independientemente de las dimensiones de A

INTRODUCCIÓN

A ∈ℜ∈ℜ mxnmxn,,

m>nm>n

Q∈ℜm×m R ∈ℜm×n

A ∈ℜ∈ℜ mxnmxn,,

m<nm<n

Q∈ℜm×m R ∈ℜm×n

0

0

La descomposición QR se puede calcular de muchas formas:

INTRODUCCIÓN

1) Basada en Reflexiones de Householder

2) Basada en Rotaciones de Givens

3) Basada en la ortonormalización modificada de Gram- Schmidt

4) Basada en rotaciones “rápidas” de Givens

Estudiaremos la más eficiente en el caso general

Sea v en ℜn distinto de 0. Las Reflexiones de Householder son matrices en ℜn×n de la forma:

1) Cada P es una modificación de la identidad de rango, 1 Simétrica y Ortogonal

2) Si y=Px, y se obtiene reflejando x sobre el subespacio Rango{v}⊥.(Complemento ortogonal de rango de v)

v·vv·vIP T

T

2−=Matriz de rango 1

Número

v x

Px

⊥}{vspan

Reflexiones de Householder

Utilización para hacer 0s en ciertas componentes de un vector:

Sea x ∈ ℜn , queremos construir una matriz de HouseholderP tal que Px=α· e1 (Todas las componentes de Px son 0 excepto la primera).

Escogemos el vector v como: v=x ± ||x||2e1. Es fácilcomprobar que, construyendo P con este vector v, Pxtiene todas sus componentes iguales a 0, excepto la primera.


Ejemplo:

=

1513

x

=

1519

vTomamos

−−−−−−−−−−−−−

=−=

5351952954515539945927

541

2v·v

v·vIP t

t

−

=

0006

Px

12exxv +=


1) Como veremos a continuación, sólo se calcula el vector v y el factor β=(vtv)/2; en aplicaciones prácticas, NUNCA se calcula la matriz P.

2) En la fórmula v=x ± ||x||2e1, el signo se selecciona para minimizar el error de redondeo.

3) El vector v se puede normalizar para que v(1)=1; de esa forma, se puede almacenar la parte importante del vector v (v(2:n)) en la parte de x donde se han hecho los ceros (x(2:n)).En este caso

21112

2 1 ,/ ,/con ,** *u,uuuuvvuuuIP T ====−= ττ

Reflexiones de HouseholderDetalles de implementación.

Algoritmo de triangularización de Householder

kjk

j

AHk: A,...,n-j,jk

jH,...,n-,j

* columna la Modifica 11 Para

columna la en ceros hace que , ,Hoseholder de Matriz la Calcula 110 Para

←+=

=

kkkkxx

xxx

xxxxxx

xxxx

xxx

j

xxxx

xx

xxx

Flopsnmn

32 :Coste 2

−

Partimos de una matriz ejemplo 6*5

Descomposición QR basada en Householder(1)

=

xxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

A

Mediante una reflexión, hacemos ceros en la primera columna

=

xxxxxxxxxxxxxxxxxxxxxxxxx

A·H

00000

1

Luego repetimos el mismo proceso, con cada columna para hacerla triangular superior:


=

xxxxxxxxxxxxxxxxxxxxxxxxx

A·H

00000

1

=

xxxxxxxxxxxxxxxxxxxxx

A·H·H

00000000

0

12 L

=

000000000

00000

0

12345

xxxxxxxxxxxxxxx

A·H·H·H·H·H


=

000000000

00000

0

12345

xxxxxxxxxxxxxxx

A·H·H·H·H·H

RAQt =·

tQHHHHH =12345 ····

Hi ortogonales => Q ortogonal

QRA =

Q ortogonal

Organización por bloquesCaso de 2 columnas

))(()()( 21212122211121TTTT zzzzzzzzIPP ττττ +−−=

[ ] [ ]

[ ]

[ ]212221

1211

2222211212211111

2

1222112221111

2

12121

2

1

,tt

con zzZtt

T

zztzztzztzztI

zzztztztztI

zzTzzIZZT

ZZ

I

TTTT

T

T

T

TTT

=

=

−−−−=

=

++−

=

−=

−

021 =⇒ t

Organización por bloques

=

2221

1211

AAAA

A

[ ]

2221212

2221211

22

12222121

2

1

22

12

22

1221

2

1

22

12

22

1221

++

−

=+

−

=

−=

−=

=

)()()((

)()()(

AZAZTZAZAZTZ

AA

AZAZTZZ

AA

A

AA

ZZTZZ

IAA

ZTZIAA

PPA

TTT

TTTTTT

TTTTTT

)2(2122221111 ;; RPPAzzIPzzIP TT =−=−= ττ

[ ]ARR =)2(

Las operaciones de actualización se pueden hacer utilizando BLAS3 ya que son productos matrizXmatriz

Organización por bloquesCaso general

[ ]

=

−=−=

kk

k

k

TTTr

t

ttttt

TZZTZZ

IZTZIPPP....

...

...

con ,... 222

11211

212

121

)2(21

22221111

...;...;;

RPPPAzzIPzzIPzzIP

k

Tkkkk

TT

=−=−=−= τττ

R1

Z(1))2(AA(1) A(2)

Organización por bloques)1()1()1()1( ,, : ar Householde derización triangulalaAplicar 1. TRZCalcularA

( ) )2()1()1()1()2()2( *** : Actualizar 2. AZTZIAA T−=

A(1) A(2)

R(1)

Z(1))2(A

Las operaciones de actualización se pueden hacer utilizando BLAS3 ya que son productos matrizXmatriz

Paralelización del Algoritmo de Householder en el Modelo de Paso de Mensajes

Objetivo: Diseñar un algoritmo paralelo óptimo para triangularizar una matriz en un multicomputador

P0 P1 Pp-2 Pp-1

Reloj

Red de interconexión

Memoria local

Programa(0)

Datos(0)

Memoria localDatos(1)

…

Programa(1)

Datos(p-2)

Memoria local

Programa(p-2)

Datos(p-1)Memoria local

Programa(p-1)

Características:Entorno de paso de mensajes (MPI)Se conoce el tiempo de ejecución de 1 Flop (operación elemental

en coma flotante:+,-,*,:)Enviar un mensaje de N palabras desde un nodo a otro (o a otros)

tiene un coste de Nτ+β, con τ y β conocidos (τ=tw y β=ts)

CAsolCAp tttttt +≅−+≅

Grafo de dependencias

N(j)=Norm(j); F(j,k)=Fact(j,k); C(j,k)=Cmod(j,k)

1)(,...,1,0, Columnas ocesador Pr

−=+→

→

pnrirpi

PjColumna jMODp

Distribución cíclica: suponiendo n=k*p

Idea básica del algoritmo

Para cada columna1. Calcular los parámetros de la

transformación de Householder (sólo el procesador que la contiene)

2. Difundir los parámetros al resto de procesadores

3. Actualizar las restantes columnas (cada procesador sólo las que contiene)

P0 P1 P2 P3

Red de interconexión

0 4 8 1 5 9 2 6 10 3 7 11

Algoritmo paralelo

EN PARALELO: PARA pr=0,1,…,p-1

En Ppr:

PARA j=0,1,…,n-1

SI jMODp=pr (*columna j pertenece a Ppr *)

ENTONCES

Norm(j)

Difunde parámetros (* vj, bj*)

EN OTRO CASO

Espera parámetros

FIN SI

PARA k=j,j+1,…,n-1

SI kMODp=pr (*columna k pertenece a Ppr *)

ENTONCES

Fact(j,k)

Cmod(j,k)

FIN SI

FIN PARA

FIN PARA

FIN PARA

Coste:FlopsnmpntA )3/)(/2( 2 −=

[ ]DIFDIFC nnmnpt βτ +−= )2/( 2

Algoritmo de triangularización de Householder orientado por bloques

[ ] mxnnb

jMODpj

AAAA

PAtbnnb

ℜ∈=

→=

−110 ,...,,

, ,/

P0 P1 P2 P3 P0 P1 P2 P3

[ ]

finparafinpara

finsi

AZTZIAActualiza

prkMODpSinbjjkPara

finsi

TZEsperacasootroen

TZDifunde

TZcalculaAizaTriangularprjMODpSi

nbjPara

PEnpprPara

kT

jjjk

jj

jj

jjj

pr

1,...,2,1

,

,

, y

1,...,1,0

: 1,...,1,0

−=

=−++=

=−=

−=

Prestaciones del algoritmo

DIFDIFBLASp tbnnmnFlopnmntbFlopnm

pn

tbT βτ

+−+

−+

−+= )

2(

22

3)

212( 3

2

Flopnmp

pFlopnmntb

dtbdTp

−

+

−

=⇒=

24

230

β

Referencias

• LAPACK: http://www.netlib.org/lapack/

• ScaLAPACK: http://www.netlib.org/scalapack/

• BLAS: http://www.netlib.org/blas/

• StructPack: http://www.inco2.upv.es/structpack.html

• “Matrix Computations”. G.Golub & C.Van Loan. 3rd Ed. John Hopkins Univ. Press. 1996

• “Fast Reliable Algorithms for Matrices with Structure”. T.Kailath & A.H.Sayed. SIAM 1999

algoritmos matriciales paralelos y librerías para … · sistemas lineales, mínimos cuadrados,...

Documents