Download PLAPACK Parallel Linear Algrebra Package

PLAPACK
(Parallel Linear Algebra Package)
Jesús Cámara Moreno
Programación Paralela y Computación de
Altas Prestaciones
Indice
„
„
„
„
„
„
„
„
„
„
„
„
Introducción
Enfoque Adoptado
Redistribución, Duplicación y Reducción de Vectores
Inicialización de PLAPACK. Funciones.
Templates. Funciones.
Linear Algebra Objects. Funciones.
Operaciones Vector-Vector
Operaciones Matriz-Vector
Operaciones Matriz-Matriz
Otras Funciones
Bibliografía
Anexos
Introducción
„
PLAPACK es una librería desarrollada en la Universidad de Texas en
Austin para la implementación paralela de algoritmos y aplicaciones
de álgebra lineal sobre supercomputadores de memoria distribuida.
„
Permite a desarrolladores de librerías, científicos e ingenieros explotar
el enfoque natural de codificación de algoritmos por bloques.
„
Se centra más en la distribución de los datos Æ gran rendimiento y
menos programación por parte del usuario.
„
Se aplica principalmente en problemas de álgebra lineal densa.
„
Utiliza MPI debajo de la capa de comunicación de PLAPACK.
„
El cómputo local realizado por PLAPACK depende en gran medida de
las llamadas realizadas a operaciones implementadas por BLAS.
Introducción
„
PLAPACK no se debe confundir con una paralelización
de LAPACK o un reempaquetado de ScaLAPACK.
„
LAPACK es una librería de para álgebra lineal densa en
supercomputadores de memoria compartida. Hace uso
de los niveles 1, 2, y 3 de BLAS para lograr portabilidad.
„
ScaLAPACK surge del intento por portar LAPACK a
computadores de memoria distribuida, haciendo especial
hincapié en una máxima reutilización del código a través
de mínimos cambios en los componentes de LAPACK.
Introducción
¿Por qué surge PLAPACK?
„
Debido a la frustración del profesor Robert A. Van de Geijn en su
intento por enseñar en un curso de post-grado Técnicas Paralelas
para el desarrollo de Algoritmos Numéricos.
„
Podía explicar la implementación escalable de alto rendimiento de
algoritmos como Multiplicación de Matrices o la Factorización de
Cholesky sin llenar más de la mitad de una pizarra, pero la
presentación del código real paralelo requería una explicación de
llamadas a subrutinas con quince o treinta parámetros, por lo que el
blocking usado al describir el algoritmo (requerido para lograr un
alto rendimiento), no se traducía bien al código.
Enfoque Adoptado
„
PLAPACK intenta superar esta complejidad adoptando un
enfoque de programación basada en objetos (usada en
librerías de computación paralela de alto rendimiento
como PETSc o MPI) con el objetivo de crear un código
robusto y simplificar la implementación de la interfaz de la
librería.
„
Las descripciones de matrices distribuidas y vectores en
PLAPACK son almacenadas en objetos de álgebra lineal
(Linear Algebra Objects).
„
También permite la utilización de vistas (objetos
referenciados dentro de matrices distribuidas y vectores
para direccionar sub-bloques de matrices y vectores)Æ
traducción línea a línea de un algoritmo por bloques dado.
Enfoque Adoptado
„
Physically Based Matrix Distribution: distribución de los datos en una
malla de procesos mediante la separación de los vectores asociados al
problema y la asignación de sub-vectores a los nodos. La distribución de
la matriz es entonces inducida por la distribución de estos vectores.
„
Intento de crear interfaces más razonables entre aplicaciones y librerías
„
Ventajas:
…
…
Reduce el overhead de la comunicación.
Soporta y explota las comunicaciones colectivas requeridas para mejorar las
duplicaciones de datos necesarias al paralelizar algoritmos en álgebra lineal densa
… Enfoque por capas con operaciones de alto nivel para la implementación paralela de
operaciones comunes del tipo matriz-vector y matriz-matriz.
… Simplifica enormemente la implementación de la infraestructura Æ permite mucha
más generalidad en futuras ampliaciones.
… Reduce la cantidad de código requerido en comparación con otras librerías de álgebra
lineal densa.
Redistribución de Vectores
Scatter
Distribución de un vector como paso intermedio a través del cual la
redistribución de filas y columnas de las matrices puede ser implementada en
un enfoque de construcción de bloques.
Gather
Redistribución de Vectores
(Broadcast)
Scatter + Collect
Duplicación de Vectores
(MPI_Reduce_Scatter)
Distributed Reduction
Reducción de Vectores
Distributed Reduction
Reducción de Vectores
Aplicación de PBMD
„
„
Multiplicación Matriz-Vector: Ax = y
…
Se parte de que x e y éstán idénticamente distribuidos. Mediante la difusión
del vector x en columnas, se duplican todos los elementos necesarios de x
para que la multiplicación local matriz-vector de cada nodo puede comenzar.
…
Después de ejecutar esta multiplicación, como sólo una porción del vector y
se conoce dentro de cada nodo, se realiza una reducción distribuida
(MPI_Reduce_scatter) de los resultados locales parciales dentro de las filas
de los nodos, dejando la parte apropiada del vector y resultante en cada
nodo.
Multiplicación Matriz-Matriz:
…
La duplicación de vectores se realizaría duplicando la fila de la matriz dentro
de la fila de nodos y la columna de la matriz dentro de la columna de nodos.
Funciones de Inicialización
Funciones de Inicialización
Templates
„
En lugar de describir directamente la distribución de cada vector y
matriz individual, PLAPACK requiere que la distribución de los
vectores y matrices sea descrita mediante una plantilla (template)
„
La distribución del resto de vectores y matrices se realizará
indicando su alineación con respecto a estas plantillas.
„
p.e, si el primer elemento del vector es alineado con el elemento i
de la plantilla, el j-ésimo elemento será distribuido asignándolo al
mismo nodo que el i+j-ésimo elemento de la plantilla del vector.
„
La plantilla de la matriz es distribuida a los nodos inducida por la
plantilla del vector. El resto de matrices a ser distribuidas se alinean
con respecto a esta plantilla de la matriz.
Funciones sobre Plantillas
„
Devuelve un objeto de tipo template, que es un puntero
a la estructura de datos que contiene el mapeo de
vectores y matrices a la malla de nodos.
Funciones sobre Plantillas
„
Rutinas de consulta: usadas para consultar información
sobre la malla de nodos y la distribución de la plantilla.
Funciones sobre Plantillas
ejemplo
Linear Algebra Objects
„
„
Linear Algebra Objects = Matrices y Vectores distribuidos.
La información que describe a cada uno se codifica en un objeto.
Linear Algebra Objects
• Destructor de Objetos:
Funciones sobre LAO
„
Rutinas de consulta: usadas para consultar información de los LAO
creados e impedir que se pueda acceder directamente a la ED que
codifica cada objeto.
Funciones sobre LAO
Funciones sobre LAO
Funciones sobre LAO
„
Rutinas de Inicialización
Todas las rutinas de PLAPACK retornan un valor entero. Si es = 0 Æ la rutina
ha finalizado correctamente. Si es > 0 Æ la rutina no finalizó bien y si es < 0 Æ
hay algún warning.
Operaciones Vector-Vector
„
En PLAPACK, las operaciones vector-vector están estratificadas como sigue:
„
PLAPACK proporciona llamadas independientes de la plataforma de nivel 1
de BLAS mediante la adición del prefijo PLA_ y proporciona 2 capas más:
„
El nivel global se emplea como medio de comunicación primario para que
todos los nodos realicen simultáneamente la llamada a la función global, la
cual realiza la llamada a BLAS sobre los objetos distribuidos.
„
Cuando un nodo llama al nivel local, es equivalente a extraer la información
local de los objetos (tipo de datos, dimensiones y puntero al buffer) y a
realizar localmente la operación en cuestión llamando a funciones del nivel de
BLAS correspondiente precedidas por PLA_ (ejemplo)
Operaciones Vector-Vector
„
Copia:
„
Intercambio de Contenido (swap):
Operaciones Vector-Vector
„
Escalado de un Vector:
Operaciones Vector-Vector
„
Sumar un Vector a un Vector Escalado:
Operaciones Vector-Vector
„
Producto:
Operaciones Matriz-Vector
„
En PLAPACK, las operaciones vector-vector están estratificadas como sigue:
„
PLAPACK proporciona llamadas independientes de la plataforma de nivel 2
de BLAS mediante la adición del prefijo PLA_ y proporciona 2 capas más:
„
El nivel global se emplea como medio de comunicación primario para que
todos los nodos realicen simultáneamente la llamada a la función global, la
cual realiza la llamada a BLAS sobre los objetos distribuidos.
„
Cuando un nodo llama al nivel local, es equivalente a extraer la información
local de los objetos (tipo de datos, dimensiones y puntero al buffer) y a
realizar localmente la operación en cuestión llamando a funciones del nivel de
BLAS correspondiente precedidas por PLA_ (ejemplo)
Operaciones Matriz-Vector
„
Multiplicación General Matriz-Vector:
ejemplo
Operaciones Matriz-Vector
„
Multiplicación Martiz_Simétrica – Vector
Operaciones Matriz-Vector
„
Multiplicación Martiz_Triangular – Vector
Operaciones Matriz-Vector
„
Triangular Solve
Operaciones Matriz-Matriz
„
En PLAPACK, las operaciones vector-vector están estratificadas como sigue:
„
PLAPACK proporciona llamadas independientes de la plataforma de nivel 3
de BLAS mediante la adición del prefijo PLA_ y proporciona 2 capas más:
„
El nivel global se emplea como medio de comunicación primario para que
todos los nodos realicen simultáneamente la llamada a la función global, la
cual realiza la llamada a BLAS sobre los objetos distribuidos.
„
Cuando un nodo llama al nivel local, es equivalente a extraer la información
local de los objetos (tipo de datos, dimensiones y puntero al buffer) y a
realizar localmente la operación en cuestión llamando a funciones del nivel de
BLAS correspondiente precedidas por PLA_ (ejemplo)
Operaciones Matriz-Matriz
„
Multiplicación General de Matrices
Operaciones Matriz-Matriz
„
Multiplicación General de Matrices (cont.)
Operaciones Matriz-Matriz
„
Multiplicación Matriz_Simétrica-Matriz
Operaciones Matriz-Matriz
„
Multiplicación Matriz_Triangular-Matriz
Otras Funciones
„
Conversión de Tipos (casting)
„
Copiar Contenido (los objetos han de tener la misma dimensión)
Otras Funciones
„
Copia Especializada: copia solo la porción superior/inferior de una
matriz triangular o, más generalmente, la porción superior/inferior de
una matriz trapezoidal.
„
Se adopta que el objeto de entrada determina la forma de los datos
a copiar.
Otras Funciones
„
Copia Especializada
Bibliografía
„
Robert A. Van de Geijn, Using PLAPACK,
April,1997.
„
Página Principal (sw + documentación):
http://www.cs.utexas.edu/users/plapack/
„
Manual de Usuario (en html):
http://www.cs.utexas.edu/users/plapack/Gui
de/Guide_html.html
ANEXOS
Factorización de Cholesky
„ Inicialización de una Plantilla
„ Multiplicación Matriz-Vector
„ Resumen Rutinas PLAPACK
„
Factorización de Cholesky
„
Dada una matriz cuadrada simétrica positivamente
definida A, la factorización de Cholesky de A viene dada
por la expresión: A=LLT, donde L es triangular inferior.
Factorización de Cholesky
„
Implementación (machacando porción triangular inferior
de A con L):
„
Observaciones:
…
…
El algoritmo no indexa explícitamente elementos individuales de
la matriz original y referencia diferentes partes de la matriz
actual, no la original.
Los bloques son referencias dentro de la matriz original.
… Se calcula factorización de A22 recursivamente, produciendo L22
Factorización de Cholesky
„
Usando PLAPACK, el código paralelo necesario
para realizar la factorización sería:
Factorización de Cholesky
„
Toda la información descrita por A (sus datos y cómo se distribuye en los nodos) es
codificada en un objeto (estructura de datos) referenciado por a.
„
PLA_Obj_view_all crea una segunda referencia, acur, dentro de los mismos datos.
„
PLA_Obj_global_length extrae el tamaño actual de la matriz referenciada por acur
Si es cero, la recursión ha terminado.
„
La llamada a PLA_Obj_split_4 particiona la matriz, creando nuevas referencias para
los cuatro cuadrantes.
„
El elemento a11 es actualizado tomando su raíz cuadrada en la subrutina Take_sqrt.
„
a21 es escalado por 1/a11 llamando a PLA_Inv_scal y
„
Finalmente, la actualización de la matriz simétrica se logra mediante la llamada a
PLA_Syr, que establece la siguiene iteración, correspodiente con el siguiente nivel de
recursión en nuestro algoritmo original.
Inicializar una Plantilla
Volver
Multiplicación Matriz-Vector
Volver
Resumen de Rutinas PLAPACK
Resumen de Rutinas PLAPACK
Resumen de Rutinas PLAPACK
Resumen de Rutinas PLAPACK
Resumen de Rutinas PLAPACK
Resumen de Rutinas PLAPACK
Resumen de Rutinas PLAPACK
Resumen de Rutinas PLAPACK
Resumen de Rutinas PLAPACK