Utilización del Paralelismo Multihebra en el Precondicionado y la
Resolución Iterativa de Sistemas Lineales DispersosUtilización del
Paralelismo Multihebra en el Precondicionado y la Resolución
Iterativa de Sistemas Lineales Dispersos
Alberto Fco. Martín Huertas
Introducción y motivación
Ax = b
donde
A ∈ R n,n matriz SDP, dispersa y de gran dimensión (n ≥
O(105))
x ∈ R n vector de incógnitas
b ∈ R n vector de términos independientes
La resolución de este problema . . .
Surge en multitud de problemas de aplicación científicos e
ingenieriles → principalmente problemas gobernados por EDPs
Parte computacionalmente más costosa de todo el proceso
Defensa Tesis Doctoral 2 A.F. Martín
Introducción y motivación
Métodos de resolución
Los métodos de resolución de Ax = b se dividen en Directos
La gran mayoría basados en la eliminación Gaussiana
Requerimientos computacionales y de memoria crecen no
linealmente
Escalan pobremente para resolver EDPs tridimensionales
Más robustos, no fallan habitualmente
Iterativos Variedad abrumadora de métodos y técnicas
(estacionarios, Krylov, AMG . . .)
Requerimientos computacionales y de memoria más moderados
Menos fiables: pueden converger lentamente e incluso diverger
Robustez/eficiencia/escalabilidad mejorada mediante
precondicionadores
Introducción y motivación
La biblioteca ILUPACK
Resolución de Ax = b mediante los métodos de la biblioteca
ILUPACK
Enfoque algebraico (aplicable a problemas arbitrarios)
Precondicionadores multinivel a partir de ILUs basadas en la
inversa
Métodos iterativos basados en la generación de subespacios de
Krylov
Para el caso SDP: precondicionadores LDLT multinivel + método
PCG
Eficiente para varios problemas científicos de gran dimensión
No incluye precondicionadores ni resolutores paralelos
Una versión paralela de ILUPACK permitiría . . .
Reducir el tiempo de computación de los problemas actuales
Resolver problemas con un mayor grado de realismo y precisión
Defensa Tesis Doctoral 4 A.F. Martín
Introducción y motivación
Objetivo general
OBJETIVO GENERAL
Analizar el paralelismo de tareas intrínseco en los métodos de la
biblioteca ILUPACK y evaluar experimentalmente, a partir de
implementaciones paralelas, si este grado de paralelismo es
suficiente para su ejecución eficiente sobre multiprocesadores con
memoria compartida
Defensa Tesis Doctoral 5 A.F. Martín
Introducción y motivación
16-64 CPUs proporcionan capacidad computacional suficiente para
muchas aplicaciones de interés científico
Arquitectura de los nodos de multiprocesadores masivamente
paralelos (multiprocesadores con memoria distribuida)
Auge de los procesadores multinúcleo en el área HPC
Defensa Tesis Doctoral 6 A.F. Martín
Introducción y motivación
3 Identificación de concurrencia en los precondicionadores LDLT
multinivel
4 Cálculo paralelo de precondicionadores LDLT multinivel
5 Resolución iterativa paralela del sistema precondicionado
6 Evaluación experimental del proceso global de resolución
7 Conclusiones y líneas abiertas
Defensa Tesis Doctoral 7 A.F. Martín
Enfoque algebraico de precondicionado de ILUPACK
Índice
3 Identificación de concurrencia en los precondicionadores LDLT
multinivel
4 Cálculo paralelo de precondicionadores LDLT multinivel
5 Resolución iterativa paralela del sistema precondicionado
6 Evaluación experimental del proceso global de resolución
7 Conclusiones y líneas abiertas
Defensa Tesis Doctoral 8 A.F. Martín
Enfoque algebraico de precondicionado de ILUPACK
Factorizaciones incompletas LDLT
La factorización LDLT dispersa de A ∈ R n,n se define como
A = LDLT ,
donde L ∈ R n,n es triangular inferior unidad dispersa, y D ∈
R
n,n
A = LDLT + R,
donde R ∈ R n,n es la matriz de error que contiene aquellos
elementos
“pequeños” de L descartados durante el proceso (p.e., |lij |≤ τ
)
M−1 = (LDLT )−1 se aplica sobre el sistema original Ax = b para
mejorar su condicionamiento y acelerar convergencia del método
PCG
Defensa Tesis Doctoral 9 A.F. Martín
Enfoque algebraico de precondicionado de ILUPACK
Factorizaciones incompletas LDLT basadas en la inversa
El método PCG converge rápidamente si sistema precondicionado
“cerca” de I
D−1/2L−1AL−T D−1/2 = I + D−1/2 L−1RL−T
R
Los precondicionadores de ILUPACK se construyen a partir de
factorizaciones incompletas LDLT basadas en la inversa
A→ (
)−1 ≤ κ
Dos argumentos a favor de este tipo de factorizaciones: R ≤ κ2R
Conexión con los métodos algebraicos multinivel → valores moderados
de κ (p.e., κ = 5) apropiados para EDPs
En la práctica es necesario emplear pivotamiento para satisfacer
L−1 ≤ κ
Defensa Tesis Doctoral 10 A.F. Martín
Enfoque algebraico de precondicionado de ILUPACK
Factorizaciones incompletas LDLT basadas en la inversa
El método PCG converge rápidamente si sistema precondicionado
“cerca” de I
D−1/2L−1AL−T D−1/2 = I + D−1/2 L−1RL−T
R
Los precondicionadores de ILUPACK se construyen a partir de
factorizaciones incompletas LDLT basadas en la inversa
A→ (
)−1 ≤ κ
Dos argumentos a favor de este tipo de factorizaciones: R ≤ κ2R
Conexión con los métodos algebraicos multinivel → valores moderados
de κ (p.e., κ = 5) apropiados para EDPs
En la práctica es necesario emplear pivotamiento para satisfacer
L−1 ≤ κ
Defensa Tesis Doctoral 10 A.F. Martín
Enfoque algebraico de precondicionado de ILUPACK
Factorizaciones incompletas LDLT basadas en la inversa
El método PCG converge rápidamente si sistema precondicionado
“cerca” de I
D−1/2L−1AL−T D−1/2 = I + D−1/2 L−1RL−T
R
Los precondicionadores de ILUPACK se construyen a partir de
factorizaciones incompletas LDLT basadas en la inversa
A→ (
)−1 ≤ κ
Dos argumentos a favor de este tipo de factorizaciones: R ≤ κ2R
Conexión con los métodos algebraicos multinivel → valores moderados
de κ (p.e., κ = 5) apropiados para EDPs
En la práctica es necesario emplear pivotamiento para satisfacer
L−1 ≤ κ
Defensa Tesis Doctoral 10 A.F. Martín
Enfoque algebraico de precondicionado de ILUPACK
Factorizaciones incompletas LDLT basadas en la inversa
El método PCG converge rápidamente si sistema precondicionado
“cerca” de I
D−1/2L−1AL−T D−1/2 = I + D−1/2 L−1RL−T
R
Los precondicionadores de ILUPACK se construyen a partir de
factorizaciones incompletas LDLT basadas en la inversa
A→ (
)−1 ≤ κ
Dos argumentos a favor de este tipo de factorizaciones: R ≤ κ2R
Conexión con los métodos algebraicos multinivel → valores moderados
de κ (p.e., κ = 5) apropiados para EDPs
En la práctica es necesario emplear pivotamiento para satisfacer
L−1 ≤ κ
Defensa Tesis Doctoral 10 A.F. Martín
Enfoque algebraico de precondicionado de ILUPACK
Factorizaciones incompletas LDLT basadas en la inversa
El método PCG converge rápidamente si sistema precondicionado
“cerca” de I
D−1/2L−1AL−T D−1/2 = I + D−1/2 L−1RL−T
R
Los precondicionadores de ILUPACK se construyen a partir de
factorizaciones incompletas LDLT basadas en la inversa
A→ (
)−1 ≤ κ
Dos argumentos a favor de este tipo de factorizaciones: R ≤ κ2R
Conexión con los métodos algebraicos multinivel → valores moderados
de κ (p.e., κ = 5) apropiados para EDPs
En la práctica es necesario emplear pivotamiento para satisfacer
L−1 ≤ κ
Defensa Tesis Doctoral 10 A.F. Martín
Enfoque algebraico de precondicionado de ILUPACK
Factorizaciones incompletas LDLT basadas en la inversa
El método PCG converge rápidamente si sistema precondicionado
“cerca” de I
D−1/2L−1AL−T D−1/2 = I + D−1/2 L−1RL−T
R
Los precondicionadores de ILUPACK se construyen a partir de
factorizaciones incompletas LDLT basadas en la inversa
A→ (
)−1 ≤ κ
Dos argumentos a favor de este tipo de factorizaciones: R ≤ κ2R
Conexión con los métodos algebraicos multinivel → valores moderados
de κ (p.e., κ = 5) apropiados para EDPs
En la práctica es necesario emplear pivotamiento para satisfacer
L−1 ≤ κ
Defensa Tesis Doctoral 10 A.F. Martín
Enfoque algebraico de precondicionado de ILUPACK
Factorizaciones incompletas LDLT basadas en la inversa
El método PCG converge rápidamente si sistema precondicionado
“cerca” de I
D−1/2L−1AL−T D−1/2 = I + D−1/2 L−1RL−T
R
Los precondicionadores de ILUPACK se construyen a partir de
factorizaciones incompletas LDLT basadas en la inversa
A→ (
)−1 ≤ κ
Dos argumentos a favor de este tipo de factorizaciones: R ≤ κ2R
Conexión con los métodos algebraicos multinivel → valores moderados
de κ (p.e., κ = 5) apropiados para EDPs
En la práctica es necesario emplear pivotamiento para satisfacer
L−1 ≤ κ
Defensa Tesis Doctoral 10 A.F. Martín
Enfoque algebraico de precondicionado de ILUPACK
Cálculo de factorizaciones incompletas LDLT basadas en la
inversa
El núcleo de factorización incompleta LDLT de ILUPACK . . .
Se basa en la variante de Crout (nueva columna/fila de L/LT por
iteración)
Incorpora pivotamiento basado en la inversa para satisfacer L−1 ≤
κ
Finaliza cuando el bloque intacto sólo contiene pivotes rechazados,
calculando complemento de Schur correspondiente a la eliminación de
los pivotes aceptados
Defensa Tesis Doctoral 11 A.F. Martín
Enfoque algebraico de precondicionado de ILUPACK
Cálculo de factorizaciones incompletas LDLT basadas en la
inversa
PT AP =
/ κ
El método se reinicia con SC construyendo una jerarquía multinivel
de aproximaciones
Defensa Tesis Doctoral 12 A.F. Martín
Enfoque algebraico de precondicionado de ILUPACK
Cálculo de factorizaciones incompletas LDLT basadas en la
inversa
PT AP =
/ κ
El método se reinicia con SC construyendo una jerarquía multinivel
de aproximaciones
Defensa Tesis Doctoral 13 A.F. Martín
Enfoque algebraico de precondicionado de ILUPACK
Cálculo de precondicionadores LDLT multinivel
Entrada : A
1. Calcular y aplicar la matriz de escalado diagonal D, A→ DAD =
A
2. Calcular y aplicar la permutación para reducción de llenado P,
A→ PT AP = A (utilizando p.e., AMD, MLND, o RCM)
3. Calcular la factorización aproximada por bloques
PT AP =
)
4. Repetir los pasos 1, 2 y 3 con A ≡ SC hasta que SC desaparezca o
sea lo “suficientemente denso”
5. Si SC es lo “suficientemente denso”, calcular SC = LCDCLT C
utilizando un núcleo
de factorización para matrices densas
Defensa Tesis Doctoral 14 A.F. Martín
Enfoque algebraico de precondicionado de ILUPACK
Cálculo de precondicionadores LDLT multinivel
Entrada : A
1. Calcular y aplicar la matriz de escalado diagonal D, A→ DAD =
A
2. Calcular y aplicar la permutación para reducción de llenado P,
A→ PT AP = A (utilizando p.e., AMD, MLND, o RCM)
3. Calcular la factorización aproximada por bloques
PT AP =
)
4. Repetir los pasos 1, 2 y 3 con A ≡ SC hasta que SC desaparezca o
sea lo “suficientemente denso”
5. Si SC es lo “suficientemente denso”, calcular SC = LCDCLT C
utilizando un núcleo
de factorización para matrices densas
Defensa Tesis Doctoral 14 A.F. Martín
Enfoque algebraico de precondicionado de ILUPACK
Cálculo de precondicionadores LDLT multinivel
Entrada : A
1. Calcular y aplicar la matriz de escalado diagonal D, A→ DAD =
A
2. Calcular y aplicar la permutación para reducción de llenado P,
A→ PT AP = A (utilizando p.e., AMD, MLND, o RCM)
3. Calcular la factorización aproximada por bloques
PT AP =
)
4. Repetir los pasos 1, 2 y 3 con A ≡ SC hasta que SC desaparezca o
sea lo “suficientemente denso”
5. Si SC es lo “suficientemente denso”, calcular SC = LCDCLT C
utilizando un núcleo
de factorización para matrices densas
Defensa Tesis Doctoral 14 A.F. Martín
Enfoque algebraico de precondicionado de ILUPACK
Cálculo de precondicionadores LDLT multinivel
Entrada : A
1. Calcular y aplicar la matriz de escalado diagonal D, A→ DAD =
A
2. Calcular y aplicar la permutación para reducción de llenado P,
A→ PT AP = A (utilizando p.e., AMD, MLND, o RCM)
3. Calcular la factorización aproximada por bloques
PT AP =
)
4. Repetir los pasos 1, 2 y 3 con A ≡ SC hasta que SC desaparezca o
sea lo “suficientemente denso”
5. Si SC es lo “suficientemente denso”, calcular SC = LCDCLT C
utilizando un núcleo
de factorización para matrices densas
Defensa Tesis Doctoral 14 A.F. Martín
Enfoque algebraico de precondicionado de ILUPACK
Cálculo de precondicionadores LDLT multinivel
Entrada : A
1. Calcular y aplicar la matriz de escalado diagonal D, A→ DAD =
A
2. Calcular y aplicar la permutación para reducción de llenado P,
A→ PT AP = A (utilizando p.e., AMD, MLND, o RCM)
3. Calcular la factorización aproximada por bloques
PT AP =
)
4. Repetir los pasos 1, 2 y 3 con A ≡ SC hasta que SC desaparezca o
sea lo “suficientemente denso”
5. Si SC es lo “suficientemente denso”, calcular SC = LCDCLT C
utilizando un núcleo
de factorización para matrices densas
Defensa Tesis Doctoral 14 A.F. Martín
Enfoque algebraico de precondicionado de ILUPACK
Cálculo de precondicionadores LDLT multinivel
Entrada : A
1. Calcular y aplicar la matriz de escalado diagonal D, A→ DAD =
A
2. Calcular y aplicar la permutación para reducción de llenado P,
A→ PT AP = A (utilizando p.e., AMD, MLND, o RCM)
3. Calcular la factorización aproximada por bloques
PT AP =
)
4. Repetir los pasos 1, 2 y 3 con A ≡ SC hasta que SC desaparezca o
sea lo “suficientemente denso”
5. Si SC es lo “suficientemente denso”, calcular SC = LCDCLT C
utilizando un núcleo
de factorización para matrices densas
Defensa Tesis Doctoral 14 A.F. Martín
Enfoque algebraico de precondicionado de ILUPACK
Cálculo de precondicionadores LDLT multinivel
Precondicionador LDLT multinivel de −u = f discretizada mediante
malla de diferencias finitas de tamaño 127× 127
0 5000 10000 15000
ILUPACK multilevel preconditioner (7 levels)
Con MLND, κ = 5 y τ = 10−3 el método construye jerarquía con 7
niveles
Defensa Tesis Doctoral 15 A.F. Martín
Identificación de concurrencia
3 Identificación de concurrencia en los precondicionadores LDLT
multinivel
4 Cálculo paralelo de precondicionadores LDLT multinivel
5 Resolución iterativa paralela del sistema precondicionado
6 Evaluación experimental del proceso global de resolución
7 Conclusiones y líneas abiertas
Defensa Tesis Doctoral 16 A.F. Martín
Identificación de concurrencia
Identificación de concurrencia
Ingrediente Objetivo
Etapa inicial de particionado de G(A) (basada en la disección
anidada)
Obtener una reordenación inicial de la ma- triz del sistema A → ΠT
AΠ apropiada para la identificación de concurrencia
Transformación del algoritmo básico
Diseñar una variante algorítmica que ex- ponga un alto grado de
concurrencia du- rante la construcción del precondicionador LDLT
multinivel de ΠT AΠ
Defensa Tesis Doctoral 17 A.F. Martín
Identificación de concurrencia
S(1,1)
Aplica recursivamente heurísticos para el cálculo de separadores de
vértices → variantes multinivel rápidas y eficientes disponibles en
METIS o SCOTCH
Equilibra tamaño de subgrafos independientes y minimiza el de los
separadores
Obtiene una reordenación para reducción de llenado apropiada para
la factorización paralela (directa o incompleta) de matrices
dispersas simétricas
Defensa Tesis Doctoral 18 A.F. Martín
Identificación de concurrencia
Identificación de concurrencia
Identificación de concurrencia
Identificación de concurrencia
Identificación de concurrencia
Identificación de concurrencia
Identificación de concurrencia
Identificación de concurrencia
Identificación de concurrencia
Identificación de concurrencia
Identificación de concurrencia
Identificación de concurrencia
Identificación de concurrencia
Identificación de concurrencia
Identificación de concurrencia
Identificación de concurrencia
Identificación de concurrencia
Identificación de concurrencia
Identificación de concurrencia
Identificación de concurrencia
Identificación de concurrencia
Identificación de concurrencia
(
para fase = l, . . . , 1 hacer
1. Calcular y aplicar al bloque AX la matriz de escalado diagonal y
la permutación para reducción de llenado (
PX 0 0 I
)(
(
+
A ≡ SC ≡
SC desaparezca o sea “suficientemente denso” , si fase = 1
4.
(
, si fase < 1
Calcular SC = LCDC LT C , cuando SC sea lo “suficientemente denso”
, si fase = 1
fin para
Identificación de concurrencia
(
para fase = l, . . . , 1 hacer
1. Calcular y aplicar al bloque AX la matriz de escalado diagonal y
la permutación para reducción de llenado (
PX 0 0 I
)(
(
+
A ≡ SC ≡
SC desaparezca o sea “suficientemente denso” , si fase = 1
4.
(
, si fase < 1
Calcular SC = LCDC LT C , cuando SC sea lo “suficientemente denso”
, si fase = 1
fin para
Identificación de concurrencia
(
para fase = l, . . . , 1 hacer
1. Calcular y aplicar al bloque AX la matriz de escalado diagonal y
la permutación para reducción de llenado (
PX 0 0 I
)(
(
+
A ≡ SC ≡
SC desaparezca o sea “suficientemente denso” , si fase = 1
4.
(
, si fase < 1
Calcular SC = LCDC LT C , cuando SC sea lo “suficientemente denso”
, si fase = 1
fin para
Identificación de concurrencia
(
para fase = l, . . . , 1 hacer
1. Calcular y aplicar al bloque AX la matriz de escalado diagonal y
la permutación para reducción de llenado (
PX 0 0 I
)(
(
+
A ≡ SC ≡
SC desaparezca o sea “suficientemente denso” , si fase = 1
4.
(
, si fase < 1
Calcular SC = LCDC LT C , cuando SC sea lo “suficientemente denso”
, si fase = 1
fin para
Identificación de concurrencia
Identificación de concurrencia
Identificación de concurrencia
Identificación de concurrencia
Identificación de concurrencia
Identificación de concurrencia
Identificación de concurrencia
Índice
3 Identificación de concurrencia en los precondicionadores LDLT
multinivel
4 Cálculo paralelo de precondicionadores LDLT multinivel
5 Resolución iterativa paralela del sistema precondicionado
6 Evaluación experimental del proceso global de resolución
7 Conclusiones y líneas abiertas
Defensa Tesis Doctoral 22 A.F. Martín
Cálculo paralelo de precondicionadores LDLT multinivel
Aprovechamiento del paralelismo de tareas
Contribuciones de (3, 2) a (2, 1)
Contribuciones de (3, 2) a (1, 1)
A(3,4)
bloques locales de contribución
ΠT AΠ se descompone en una suma de submatrices, una submatriz por
tarea hoja
Los bloques locales de contribución de una submatriz/tarea
almacenan las actualizaciones de la tarea sobre los bloques
correspondientes a sus ancestros
Defensa Tesis Doctoral 23 A.F. Martín
Cálculo paralelo de precondicionadores LDLT multinivel
Aprovechamiento del paralelismo de tareas
El núcleo de factorización incompleta LDLT local . . .
Rechaza pivotes a la pos. de la última fil./col. del bloque que
factoriza la tarea
Finaliza si la parte intacta de este bloque sólo contiene pivotes
rechazados
Extiende cálculo del complemento de Schur a los bloques locales de
contribución
Defensa Tesis Doctoral 24 A.F. Martín
Cálculo paralelo de precondicionadores LDLT multinivel
Aprovechamiento del paralelismo de tareas
Cuando el número de pivotes rechazados es lo “suficientemente
pequeño”
La tarea “envía” complemento de Schur calculado localmente a su
padre
Defensa Tesis Doctoral 25 A.F. Martín
Cálculo paralelo de precondicionadores LDLT multinivel
Aprovechamiento del paralelismo de tareas
(3,2)
(3,1)
(2,1)
(3,2)
A(2,1) A(2,1)
El padre construye una nueva submatriz a partir de los complementos
de Schur calculados localmente por sus hijos
Esta submatriz se obtiene a partir de los elementos pivote
rechazados por sus hijos y una acumulación de sus bloques de
contribución
Defensa Tesis Doctoral 26 A.F. Martín
Cálculo paralelo de precondicionadores LDLT multinivel
Especificación del algoritmo paralelo
Las computaciones de una tarea hoja (l , j) se expresan
algorítmicamente como
1. Construir sumando A(l,j) a partir de ΠT AΠ
2. Calcular y aplicar la matriz de escalado diagonal D(l,j), A(l,j)
→ D(l,j)A(l,j)D(l,j) = A(l,j), a los bloques que factoriza la
tarea
3. Calcular y aplicar la permutación para reducción de llenado
P(l,j), A(l,j) → (P(l,j))T A(l,j)P(l,j) = A(l,j) a los bloques que
factoriza la tarea
4. Calcular la factorización aproximada por bloques (basada en la
inversa) de los bloques que factoriza la tarea
5. Repetir los pasos 2, 3 y 4 hasta que el número de elementos
pivote rechazados sea lo “suficientemente pequeño”
6. “Enviar” complemento de Schur calculado localmente al
padre
Defensa Tesis Doctoral 27 A.F. Martín
Cálculo paralelo de precondicionadores LDLT multinivel
Especificación del algoritmo paralelo
Las computaciones de una tarea con hijos de un nivel intermedio (i
, j) como
1. Construir sumando A(i,j) a partir de los complementos de Schur
calculados localmente por sus hijos
2. Calcular y aplicar la matriz de escalado diagonal D(i,j), A(i,j)
→ D(i,j)A(i,j)D(i,j) = A(i,j), a los bloques que factoriza la
tarea
3. Calcular y aplicar la permutación para reducción de llenado
P(i,j), A(i,j) → (P(i,j))T A(i,j)P(i,j) = A(i,j) a los bloques que
factoriza la tarea
4. Calcular la factorización aproximada por bloques (basada en la
inversa) de los bloques que factoriza la tarea
5. Repetir los pasos 2, 3 y 4 hasta que el número de elementos
pivote rechazados sea lo “suficientemente pequeño”
6. “Enviar” complemento de Schur calculado localmente al
padre
Defensa Tesis Doctoral 28 A.F. Martín
Cálculo paralelo de precondicionadores LDLT multinivel
Especificación del algoritmo paralelo
Las computaciones de la tarea raíz (1, 1) como . . .
1. Construir sumando A(1,1) a partir de los complementos de Schur
calculados localmente por sus hijos
2. Calcular y aplicar la matriz de escalado diagonal D(1,1), A(1,1)
→ D(1,1)A(1,1)D(i,j) = A(1,1)
3. Calcular y aplicar la permutación para reducción de llenado
P(1,1), A(1,1) → (P(1,1))T A(1,1)P(1,1) = A(1,1)
4. Calcular la factorización aproximada por bloques (basada en la
inversa) de A(1,1)
5. Repetir los pasos 2, 3 y 4 hasta que el complemento de Schur SC
sea un bloque vacío o lo “suficientemente denso”
6. Si SC es lo “suficientemente denso”, calcular SC = LCDCLT C
utilizando un núcleo
de factorización para matrices densas
Defensa Tesis Doctoral 29 A.F. Martín
Cálculo paralelo de precondicionadores LDLT multinivel
Especificación del algoritmo paralelo
Para completar la especificación del algoritmo paralelo es
necesario . . .
Describir criterios para guiar el proceso recursivo de disección →
¿ cómo fijar el número de niveles/hojas del árbol ?
Describir estrategias de mapeado y planificación → ¿cuándo se
ejecuta una tarea? → ¿qué procesador ejecuta una tarea?
Defensa Tesis Doctoral 30 A.F. Martín
Cálculo paralelo de precondicionadores LDLT multinivel
Construcción del árbol de dependencias entre tareas
Objetivo: partir hojas que concentren “potencialmente” mayor carga
computacional # aristas del subgrafo independiente, |E(i,j)|, como
estimación de su coste
Criterio: partir tarea hoja si |E(i,j)|/|E| > 1 f , con f
parámetro preestablecido
Valores de f en el intervalo [p,3p] apropiados (más hojas que
procesadores)
(1,1)
Construcción del árbol de dependencias entre tareas
Objetivo: partir hojas que concentren “potencialmente” mayor carga
computacional # aristas del subgrafo independiente, |E(i,j)|, como
estimación de su coste
Criterio: partir tarea hoja si |E(i,j)|/|E| > 1 f , con f
parámetro preestablecido
Valores de f en el intervalo [p,3p] apropiados (más hojas que
procesadores)
(1,1)
Construcción del árbol de dependencias entre tareas
Objetivo: partir hojas que concentren “potencialmente” mayor carga
computacional # aristas del subgrafo independiente, |E(i,j)|, como
estimación de su coste
Criterio: partir tarea hoja si |E(i,j)|/|E| > 1 f , con f
parámetro preestablecido
Valores de f en el intervalo [p,3p] apropiados (más hojas que
procesadores)
(1,1)
Defensa Tesis Doctoral 33 A.F. Martín
Cálculo paralelo de precondicionadores LDLT multinivel
Planificación dinámica
Planificación dinámica
Disponible No disponible
Finalizado En ejecución
Cola de tareas disponibles
Tareas disponibles A ejecución
Hebra 0 Hebra 1
La cola se inicializa con las hojas en orden decreciente por
#aristas
Defensa Tesis Doctoral 34 A.F. Martín
Cálculo paralelo de precondicionadores LDLT multinivel
Planificación dinámica
Defensa Tesis Doctoral 34 A.F. Martín
Cálculo paralelo de precondicionadores LDLT multinivel
Planificación dinámica
T2 T1
T4 T5
Defensa Tesis Doctoral 34 A.F. Martín
Cálculo paralelo de precondicionadores LDLT multinivel
Planificación dinámica
Defensa Tesis Doctoral 34 A.F. Martín
Cálculo paralelo de precondicionadores LDLT multinivel
Planificación dinámica
Defensa Tesis Doctoral 34 A.F. Martín
Cálculo paralelo de precondicionadores LDLT multinivel
Planificación dinámica
Defensa Tesis Doctoral 34 A.F. Martín
Cálculo paralelo de precondicionadores LDLT multinivel
Planificación dinámica
Planificación dinámica
T5 T4
Defensa Tesis Doctoral 34 A.F. Martín
Cálculo paralelo de precondicionadores LDLT multinivel
Planificación dinámica [ Π , T ]← disección_anidada(G(A), f )
Q ← { hojas(T ) } inicializar Q con tareas hoja deT en orden
decreciente por #aristas
marcar todas las tareas de T como no ejecutadas
Inicio región paralela crear grupo de procesos pid← obtener_pid()
obtener identificador de proceso
repetir mientras Q no esté vacía hacer
tid← desencolar(Q) extraer tarea ejecutable de la cabeza deQ
map [ tid ]← pid procesopid a cargo de la tareatid
construir_sumando(tid) construir sumando correspondiente atid
calcular_factorización(tid) calcular factorizaciónLDLT multinivel
local
marcar tid como ejecutada
si se han resuelto las dependencias de padre(tid) entonces
encolar(padre(tid), Q) insertar nueva tarea ejecutable en la cola
deQ
fin si
fin mientras
Fin región paralela
Planificación dinámica
SGI Altix 350 + bmwcra_1 + p = 8 f = 1,00 p f = 1,125 p
f = 1,25 p f = 2,00 p
Defensa Tesis Doctoral 36 A.F. Martín
Cálculo paralelo de precondicionadores LDLT multinivel
Problema de aplicación
Consideramos la resolución numérica de la EDP tridimensional
−∇ · K (x, y , z) ∇u(x, y , z) = f ,
en , donde los coeficientes K (x, y , z) ∈ R 3×3 son positivos y
aleatorios en
Para la discretización . . .
Elementos finitos lineales
reemplazado por malla inicial generada por NETGEN → 5 niveles de
mallado predefinidos: VC, C, M, F, VF → Malla inicial refinada
hasta tres veces
Problema de aplicación
Consideramos 12 matrices SDP de prueba para nuestro estudio
experimental
Id. Código Nivel de mallado # refs. n nnz(A) nnz(A)/n 1 VC very
coarse 0 1.709 16.669 9,75 2 C coarse 0 9.583 112.563 11,75 3 M
moderate 0 32.429 412.251 12,71 4 F fine 0 101.296 1.368.594 13,51
5 VC2 very coarse 2 271.272 3.686.268 13,59 6 M1 moderate 1 297.927
4.134.255 13,88 7 VF very fine 0 658.609 9.294.721 14,11 8 F1 fine
1 882.824 12.562.880 14,23 9 C2 coarse 2 906.882 12.854.824 14,17
10 VC3 very coarse 3 2.382.864 34.128.924 14,32 11 M2 moderate 2
2.539.954 36.768.808 14,48 12 VF1 very fine 1 5.413.520 78.935.174
14,58
Defensa Tesis Doctoral 38 A.F. Martín
Cálculo paralelo de precondicionadores LDLT multinivel
Marco de trabajo experimental
Plataforma experimental: multiprocesador ccNUMA SGI Altix 350
8 nodos, 2 procesadores/nodo, Intel Itanium
[email protected] GHz 32 GBytes de
RAM (4 GBytes/nodo) Topología: anillo, enlaces bidireccionales SGI
Numalink
Etapa inicial de particionado SCOTCH (versión 5.0.6RC16)
Compiladores de Intel para C (versión 9.0)
Cálculo del precondicionador LDLT multinivel y método PCG ILUPACK
(versión 2.1) Compiladores de Intel para C y Fortran77 (versión
9.0) Soporte de estos compiladores a la revisión 2.5 de OpenMP
Computaciones numéricas en aritmética IEEE 754 de doble precisión
Una hebra/CPU, las hebras no migran durante la ejecución
Defensa Tesis Doctoral 39 A.F. Martín
Cálculo paralelo de precondicionadores LDLT multinivel
Configuración de los algoritmos
f ∈ [p : 1,50 p] −→
Cálculo del precondicionador LDLT multinivel p = 1, 2,4, 8 y 16
hebras/procesadores HAMD heurístico de reordenación local para
reducción de llenado κ = 5 y τ = 10−2
Resolución iterativa del sistema precondicionado x (0) = 0 solución
inicial del método PCG b escogido artificialmente para que x sea el
vector unidad Criterio de convergencia: x − x (i)A/x − x (0)A /
10−8
p = 1, 2,4, 8 y 16 hebras/procesadores Mapeado estático con ajustes
para resolución regresiva
Defensa Tesis Doctoral 40 A.F. Martín
Cálculo paralelo de precondicionadores LDLT multinivel
Aceleración paralela
1 2 3 4 5 6 7 8 9 10 11 12
2
4
6
8
10
12
14
16
18
Rendimiento paralelo precondicionador LDLT multinivel
p=2, f in [p,1.5p] p=2, f=c p=4, f in [p,1.5p] p=4, f=c p=8, f in
[p,1.5p] p=8, f=c p=16, f in [p,1.5p] p=16, f=c
Defensa Tesis Doctoral 41 A.F. Martín
Cálculo paralelo de precondicionadores LDLT multinivel
Sobrecostes asociados a la extracción del paralelismo de
tareas
1 2 3 4 5 6 7 8 9 10 11 12
0.8
1
1.2
1.4
1.6
1.8
2
Coste computacional relativo precondicionador LDLT multinivel
f=1 f=2 f=2.5 f=3 f=4 f=5 f=6 f=8 f=10 f=12 f=16 f=20 f=24
Sobrecoste computacional
Sobrecostes asociados a la extracción del paralelismo de
tareas
1 2 3 4 5 6 7 8 9 10 11 12
1
1.5
2
2.5
3
3.5
4
4.5
Consumo relativo memoria precondicionador LDLT multinivel
p=1, f=1 p=2, f=p p=2, f=px1.25 p=2, f=px1.5 p=4, f=p p=4, f=px1.25
p=4, f=px1.5 p=8, f=p p=8, f=px1.25 p=8, f=px1.5 p=16, f=p p=16,
f=px1.25 p=16, f=px1.5
Sobrecoste de memoria
Factor de llenado – nnz(M) nnz(A)
0 5 10 15 20 25
1.4
1.6
1.8
2
2.2
2.4
2.6
Comparativa ILUPACK secuencial vs. paralelo
VC C M F VC2 M1 VF F1 C2 VC3 M2 VF1
Valor del parámetro f
Defensa Tesis Doctoral 44 A.F. Martín
Cálculo paralelo de precondicionadores LDLT multinivel
Comparación numérica precondicionadores secuencial y paralelo
−u = f (coef. discont.) y malla de diferencias finitas 200 ×
200
Precondicionador secuencial Precondicionador paralelo
Defensa Tesis Doctoral 45 A.F. Martín
Cálculo paralelo de precondicionadores LDLT multinivel
Comparación numérica precondicionadores secuencial y paralelo
−u = f (coef. discont.) y malla de diferencias finitas 200 ×
200
0 20 40 60 80 100 120 140 160 180 200 0
20
40
60
80
100
120
140
160
180
200
nivel 2 −> 3
0 20 40 60 80 100 120 140 160 180 200 0
20
40
60
80
100
120
140
160
180
200
Defensa Tesis Doctoral 45 A.F. Martín
Cálculo paralelo de precondicionadores LDLT multinivel
Comparación numérica precondicionadores secuencial y paralelo
−u = f (coef. discont.) y malla de diferencias finitas 200 ×
200
0 20 40 60 80 100 120 140 160 180 200 0
20
40
60
80
100
120
140
160
180
200
nivel 3 −> 4
0 20 40 60 80 100 120 140 160 180 200 0
20
40
60
80
100
120
140
160
180
200
Defensa Tesis Doctoral 45 A.F. Martín
Cálculo paralelo de precondicionadores LDLT multinivel
Comparación numérica precondicionadores secuencial y paralelo
−u = f (coef. discont.) y malla de diferencias finitas 200 ×
200
0 20 40 60 80 100 120 140 160 180 200 0
20
40
60
80
100
120
140
160
180
200
nivel 4 −> 5
0 20 40 60 80 100 120 140 160 180 200 0
20
40
60
80
100
120
140
160
180
200
Índice
3 Identificación de concurrencia en los precondicionadores LDLT
multinivel
4 Cálculo paralelo de precondicionadores LDLT multinivel
5 Resolución iterativa paralela del sistema precondicionado
6 Evaluación experimental del proceso global de resolución
7 Conclusiones y líneas abiertas
Defensa Tesis Doctoral 46 A.F. Martín
Resolución iterativa paralela del sistema precondicionado
El método PCG
Fijar una solución inicial x del sistema Ax = b ≡ (ΠT AΠ)(ΠT x) =
(ΠT b)
q ← Ax Producto de una matriz dispersa por un vector
r ← b − q Actualización de un vector
Resolver Mz = r Aplicación del precondicionador
σ1 ← rT z Producto escalar
p ← z
for i = 0, 1, . . ., hasta convergencia do δ ← pT q Producto
escalar
α← σ1/δ
Resolver Mz = r Aplicación del precondicionador
σ2 ← rT z Producto escalar
β ← σ2/σ1; σ1 ← σ2
q ← Ap Producto de una matriz dispersa por un vector
end x ← Πx
Resolución progresiva y regresiva paralelas
Resolver Mz = r
ObtenerObtener
Mapeado y planificación de tareas a procesos
Resolver Mz = r
Computaciones limitadas por el acceso a memoria
Cuando se emplean estrategias dinámicas de mapeado y planificación
el sobrecoste asociado al movimiento de datos entre cachés y
memoria es alto
Estudio experimental revela que este sobrecoste no se puede
amortizar con las ventajas que ofrecen las estrategias dinámicas de
planificación
Solución: mapeado estático de tareas a procesos → los procesos
ejecutan repetidamente las mismas tareas
Escogemos mapeado que resulta del cálculo paralelo del
precondicionador
Defensa Tesis Doctoral 49 A.F. Martín
Resolución iterativa paralela del sistema precondicionado
Mapeado y planificación en la resolución regresiva
Los procesos priorizan la ejecución de las tareas con hijos frente
a las hojas
T3
T1
P0
T2
P1
Mapeado y planificación en la resolución regresiva
Causa potencial de procesos ociosos: cuando se resuelven las
dependencias de una tarea con hijos, el proceso a cargo de ésta
puede estar ejecutando una hoja
T3
T1
P0
T2
P1
Mapeado y planificación en la resolución regresiva
Solución: el proceso que resuelve sus dependencias se encarga de su
ejecución
T3
T1
P0
T2
P1
Mapeado y planificación en la resolución regresiva
Solución: mapeado estático + ajustes durante la ejecución
T3
T1
P0
T2
P1
Mapeado y planificación en la resolución regresiva
−u = f (coef. discont.) y malla de diferencias finitas 1000×
1000
0 5 10 15 20 25 30 35 40 45 50 0.9
1
1.1
1.2
1.3
1.4
1.5
1.6
1.7
1.8
f = 16 p = 16
Defensa Tesis Doctoral 54 A.F. Martín
Resolución iterativa paralela del sistema precondicionado
Problema de aplicación
Consideramos la resolución numérica de la EDP tridimensional
−∇ · K (x, y , z) ∇u(x, y , z) = f ,
en , donde los coeficientes K (x, y , z) ∈ R 3×3 son positivos y
aleatorios en
Para la discretización . . .
Elementos finitos lineales
reemplazado por malla inicial generada por NETGEN → 5 niveles de
mallado predefinidos: VC, C, M, F, VF → Malla inicial refinada
hasta tres veces
Problema de aplicación
Consideramos 12 matrices SDP de prueba para nuestro estudio
experimental
Id. Código Nivel de mallado # refs. n nnz(A) nnz(A)/n 1 VC very
coarse 0 1.709 16.669 9,75 2 C coarse 0 9.583 112.563 11,75 3 M
moderate 0 32.429 412.251 12,71 4 F fine 0 101.296 1.368.594 13,51
5 VC2 very coarse 2 271.272 3.686.268 13,59 6 M1 moderate 1 297.927
4.134.255 13,88 7 VF very fine 0 658.609 9.294.721 14,11 8 F1 fine
1 882.824 12.562.880 14,23 9 C2 coarse 2 906.882 12.854.824 14,17
10 VC3 very coarse 3 2.382.864 34.128.924 14,32 11 M2 moderate 2
2.539.954 36.768.808 14,48 12 VF1 very fine 1 5.413.520 78.935.174
14,58
Defensa Tesis Doctoral 56 A.F. Martín
Resolución iterativa paralela del sistema precondicionado
Configuración de los algoritmos
f ∈ [p : 1,50 p] −→
Cálculo del precondicionador LDLT multinivel p = 1, 2,4, 8 y 16
hebras/procesadores HAMD heurístico de reordenación local para
reducción de llenado κ = 5 y τ = 10−2
Resolución iterativa del sistema precondicionado x (0) = 0 solución
inicial del método PCG b escogido artificialmente para que x sea el
vector unidad Criterio de convergencia: x − x (i)A/x − x (0)A /
10−8
p = 1, 2,4, 8 y 16 hebras/procesadores Mapeado estático con ajustes
para resolución regresiva
Defensa Tesis Doctoral 57 A.F. Martín
Resolución iterativa paralela del sistema precondicionado
Aceleración paralela del método PCG
1 2 3 4 5 6 7 8 9 10 11 12
2
4
6
8
10
12
14
16
18
Rendimiento paralelo metodo PCG
p=2, f in [p,1.5p] p=2, f=c p=4, f in [p,1.5p] p=4, f=c p=8, f in
[p,1.5p] p=8, f=c p=16, f in [p,1.5p] p=16, f=c
Defensa Tesis Doctoral 58 A.F. Martín
Resolución iterativa paralela del sistema precondicionado
Sobrecostes asociados a la extracción del paralelismo de
tareas
1 2 3 4 5 6 7 8 9 10 11 12
1
1.5
2
2.5
3
3.5
Coste computacional relativo metodo PCG
f=1 f=2 f=2.5 f=3 f=4 f=5 f=6 f=8 f=10 f=12 f=16 f=20 f=24
Sobrecoste computacional
0 5 10 15 20 25 10
20
30
40
50
60
70 Comparativa ILUPACK secuencial vs. paralelo
VC C M F VC2 M1 VF F1 C2 VC3 M2 VF1
N úm
er o
de ite
ra ci
on es
m ét
od o
P C
Error relativo – x−x(i)2 x2
0 5 10 15 20 25 10
−15
Comparativa ILUPACK secuencial vs. paralelo
VC C M F VC2 M1 VF F1 C2 VC3 M2 VF1
E rr
or re
la tiv
o – x −
x (i )
2 x
Evaluación experimental del proceso global de resolución
Índice
3 Identificación de concurrencia en los precondicionadores LDLT
multinivel
4 Cálculo paralelo de precondicionadores LDLT multinivel
5 Resolución iterativa paralela del sistema precondicionado
6 Evaluación experimental del proceso global de resolución
7 Conclusiones y líneas abiertas
Defensa Tesis Doctoral 62 A.F. Martín
Evaluación experimental del proceso global de resolución
Dos posibles soluciones para la etapa inicial de particionado
ND-HAMD-A ND-HAMD-B
Evaluación experimental del proceso global de resolución
Tiempo de ejecución
100
200
300
400
500
600
700
800
900
1000
#procesadores
Comparativa ND−HAMD−A vs. ND−HAMD−B para very_fine_refined
ND−HAMD−A_MLND ND−HAMD−A_MIC ND−HAMD−A_PCG ND−HAMD−B_MLND
ND−HAMD−B_MIC ND−HAMD−B_PCG
n=5,413,520
Evaluación experimental del proceso global de resolución
PT-SCOTCH y ParMETIS: particionado en paralelo de matrices
dispersas
ND-HAMD-B
S(1,1)
Evaluación experimental del proceso global de resolución
Tiempo de ejecución
100
200
300
400
500
600
700
800
#procesadores
PT−SCOTCH_MLND PT−SCOTCH_MIC PT−SCOTCH_PCG ParMETIS_MLND
ParMETIS_MIC ParMETIS_PCG
n=5,413,520
Conclusiones y líneas abiertas
3 Identificación de concurrencia en los precondicionadores LDLT
multinivel
4 Cálculo paralelo de precondicionadores LDLT multinivel
5 Resolución iterativa paralela del sistema precondicionado
6 Evaluación experimental del proceso global de resolución
7 Conclusiones y líneas abiertas
Defensa Tesis Doctoral 67 A.F. Martín
Conclusiones y líneas abiertas
Nueva variante algorítmica con paralelismo implícito para la
construcción y aplicación de precondicionadores LDLT
multinivel
Aprovechamiento de este paralelismo a partir del árbol de
dependencias entre tareas y ejecución del mismo mediante
estrategias dinámicas de mapeado y planificación
Extensión de esta aproximación para la aplicación del
precondicionador y el resto de operaciones del método PCG
Implementación de los algoritmos paralelos siguiendo los principios
de diseño de la biblioteca ILUPACK y OpenMP para aprovechar el
modelo de programación paralela de variables compartidas
Evaluación experimental detallada del rendimiento de los algoritmos
paralelos desarrollados para resolver varias EDPs 2D y 3D en un
multiprocesador con memoria compartida comercial (con los
particionados calculados por SCOTCH, ParMETIS y PT-SCOTCH)
Evaluación experimental general con una miscelánea de sistemas
irregulares, provenientes de diversas áreas de aplicación
Defensa Tesis Doctoral 68 A.F. Martín
Conclusiones y líneas abiertas
Nueva variante algorítmica con paralelismo implícito para la
construcción y aplicación de precondicionadores LDLT
multinivel
Aprovechamiento de este paralelismo a partir del árbol de
dependencias entre tareas y ejecución del mismo mediante
estrategias dinámicas de mapeado y planificación
Extensión de esta aproximación para la aplicación del
precondicionador y el resto de operaciones del método PCG
Implementación de los algoritmos paralelos siguiendo los principios
de diseño de la biblioteca ILUPACK y OpenMP para aprovechar el
modelo de programación paralela de variables compartidas
Evaluación experimental detallada del rendimiento de los algoritmos
paralelos desarrollados para resolver varias EDPs 2D y 3D en un
multiprocesador con memoria compartida comercial (con los
particionados calculados por SCOTCH, ParMETIS y PT-SCOTCH)
Evaluación experimental general con una miscelánea de sistemas
irregulares, provenientes de diversas áreas de aplicación
Defensa Tesis Doctoral 68 A.F. Martín
Conclusiones y líneas abiertas
Nueva variante algorítmica con paralelismo implícito para la
construcción y aplicación de precondicionadores LDLT
multinivel
Aprovechamiento de este paralelismo a partir del árbol de
dependencias entre tareas y ejecución del mismo mediante
estrategias dinámicas de mapeado y planificación
Extensión de esta aproximación para la aplicación del
precondicionador y el resto de operaciones del método PCG
Implementación de los algoritmos paralelos siguiendo los principios
de diseño de la biblioteca ILUPACK y OpenMP para aprovechar el
modelo de programación paralela de variables compartidas
Evaluación experimental detallada del rendimiento de los algoritmos
paralelos desarrollados para resolver varias EDPs 2D y 3D en un
multiprocesador con memoria compartida comercial (con los
particionados calculados por SCOTCH, ParMETIS y PT-SCOTCH)
Evaluación experimental general con una miscelánea de sistemas
irregulares, provenientes de diversas áreas de aplicación
Defensa Tesis Doctoral 68 A.F. Martín
Conclusiones y líneas abiertas
Nueva variante algorítmica con paralelismo implícito para la
construcción y aplicación de precondicionadores LDLT
multinivel
Aprovechamiento de este paralelismo a partir del árbol de
dependencias entre tareas y ejecución del mismo mediante
estrategias dinámicas de mapeado y planificación
Extensión de esta aproximación para la aplicación del
precondicionador y el resto de operaciones del método PCG
Implementación de los algoritmos paralelos siguiendo los principios
de diseño de la biblioteca ILUPACK y OpenMP para aprovechar el
modelo de programación paralela de variables compartidas
Evaluación experimental detallada del rendimiento de los algoritmos
paralelos desarrollados para resolver varias EDPs 2D y 3D en un
multiprocesador con memoria compartida comercial (con los
particionados calculados por SCOTCH, ParMETIS y PT-SCOTCH)
Evaluación experimental general con una miscelánea de sistemas
irregulares, provenientes de diversas áreas de aplicación
Defensa Tesis Doctoral 68 A.F. Martín
Conclusiones y líneas abiertas
Nueva variante algorítmica con paralelismo implícito para la
construcción y aplicación de precondicionadores LDLT
multinivel
Aprovechamiento de este paralelismo a partir del árbol de
dependencias entre tareas y ejecución del mismo mediante
estrategias dinámicas de mapeado y planificación
Extensión de esta aproximación para la aplicación del
precondicionador y el resto de operaciones del método PCG
Implementación de los algoritmos paralelos siguiendo los principios
de diseño de la biblioteca ILUPACK y OpenMP para aprovechar el
modelo de programación paralela de variables compartidas
Evaluación experimental detallada del rendimiento de los algoritmos
paralelos desarrollados para resolver varias EDPs 2D y 3D en un
multiprocesador con memoria compartida comercial (con los
particionados calculados por SCOTCH, ParMETIS y PT-SCOTCH)
Evaluación experimental general con una miscelánea de sistemas
irregulares, provenientes de diversas áreas de aplicación
Defensa Tesis Doctoral 68 A.F. Martín
Conclusiones y líneas abiertas
Nueva variante algorítmica con paralelismo implícito para la
construcción y aplicación de precondicionadores LDLT
multinivel
Aprovechamiento de este paralelismo a partir del árbol de
dependencias entre tareas y ejecución del mismo mediante
estrategias dinámicas de mapeado y planificación
Extensión de esta aproximación para la aplicación del
precondicionador y el resto de operaciones del método PCG
Implementación de los algoritmos paralelos siguiendo los principios
de diseño de la biblioteca ILUPACK y OpenMP para aprovechar el
modelo de programación paralela de variables compartidas
Evaluación experimental detallada del rendimiento de los algoritmos
paralelos desarrollados para resolver varias EDPs 2D y 3D en un
multiprocesador con memoria compartida comercial (con los
particionados calculados por SCOTCH, ParMETIS y PT-SCOTCH)
Evaluación experimental general con una miscelánea de sistemas
irregulares, provenientes de diversas áreas de aplicación
Defensa Tesis Doctoral 68 A.F. Martín
Conclusiones y líneas abiertas
Conclusiones del estudio experimental
La eficiencia paralela de la aproximación propuesta depende de: →
distribución del coste entre los niveles del árbol → balance entre
beneficios y sobrecostes del paralelismo
Alto grado de eficiencia paralela para resolver los sistemas
ligados a una EDP 3D en un multiprocesador con memoria compartida
comercial
La planificación dinámica aumenta eficiencia siempre que la mejora
en el equilibrio de carga se pueda amortizar con sobrecostes del
paralelismo de tareas
El mapeado de tareas a procesos que resulta del cálculo del
precondicionador también resulta apropiado para su aplicación. Los
ajustes que realiza la resolución regresiva en este mapeado mejoran
su rendimiento en muchos casos
El enfoque de paralelización preserva la semántica de las técnicas
de precondicionado de ILUPACK (bajo grado de sensibilidad del
#iter. al #CPUs)
El enfoque de paralelización obtiene eficiencias paralelas notables
con los particionados calculados por ParMETIS y PT-SCOTCH
Defensa Tesis Doctoral 69 A.F. Martín
Conclusiones y líneas abiertas
Conclusiones del estudio experimental
La eficiencia paralela de la aproximación propuesta depende de: →
distribución del coste entre los niveles del árbol → balance entre
beneficios y sobrecostes del paralelismo
Alto grado de eficiencia paralela para resolver los sistemas
ligados a una EDP 3D en un multiprocesador con memoria compartida
comercial
La planificación dinámica aumenta eficiencia siempre que la mejora
en el equilibrio de carga se pueda amortizar con sobrecostes del
paralelismo de tareas
El mapeado de tareas a procesos que resulta del cálculo del
precondicionador también resulta apropiado para su aplicación. Los
ajustes que realiza la resolución regresiva en este mapeado mejoran
su rendimiento en muchos casos
El enfoque de paralelización preserva la semántica de las técnicas
de precondicionado de ILUPACK (bajo grado de sensibilidad del
#iter. al #CPUs)
El enfoque de paralelización obtiene eficiencias paralelas notables
con los particionados calculados por ParMETIS y PT-SCOTCH
Defensa Tesis Doctoral 69 A.F. Martín
Conclusiones y líneas abiertas
Conclusiones del estudio experimental
La eficiencia paralela de la aproximación propuesta depende de: →
distribución del coste entre los niveles del árbol → balance entre
beneficios y sobrecostes del paralelismo
Alto grado de eficiencia paralela para resolver los sistemas
ligados a una EDP 3D en un multiprocesador con memoria compartida
comercial
La planificación dinámica aumenta eficiencia siempre que la mejora
en el equilibrio de carga se pueda amortizar con sobrecostes del
paralelismo de tareas
El mapeado de tareas a procesos que resulta del cálculo del
precondicionador también resulta apropiado para su aplicación. Los
ajustes que realiza la resolución regresiva en este mapeado mejoran
su rendimiento en muchos casos
El enfoque de paralelización preserva la semántica de las técnicas
de precondicionado de ILUPACK (bajo grado de sensibilidad del
#iter. al #CPUs)
El enfoque de paralelización obtiene eficiencias paralelas notables
con los particionados calculados por ParMETIS y PT-SCOTCH
Defensa Tesis Doctoral 69 A.F. Martín
Conclusiones y líneas abiertas
Conclusiones del estudio experimental
La eficiencia paralela de la aproximación propuesta depende de: →
distribución del coste entre los niveles del árbol → balance entre
beneficios y sobrecostes del paralelismo
Alto grado de eficiencia paralela para resolver los sistemas
ligados a una EDP 3D en un multiprocesador con memoria compartida
comercial
La planificación dinámica aumenta eficiencia siempre que la mejora
en el equilibrio de carga se pueda amortizar con sobrecostes del
paralelismo de tareas
El mapeado de tareas a procesos que resulta del cálculo del
precondicionador también resulta apropiado para su aplicación. Los
ajustes que realiza la resolución regresiva en este mapeado mejoran
su rendimiento en muchos casos
El enfoque de paralelización preserva la semántica de las técnicas
de precondicionado de ILUPACK (bajo grado de sensibilidad del
#iter. al #CPUs)
El enfoque de paralelización obtiene eficiencias paralelas notables
con los particionados calculados por ParMETIS y PT-SCOTCH
Defensa Tesis Doctoral 69 A.F. Martín
Conclusiones y líneas abiertas
Conclusiones del estudio experimental
La eficiencia paralela de la aproximación propuesta depende de: →
distribución del coste entre los niveles del árbol → balance entre
beneficios y sobrecostes del paralelismo
Alto grado de eficiencia paralela para resolver los sistemas
ligados a una EDP 3D en un multiprocesador con memoria compartida
comercial
La planificación dinámica aumenta eficiencia siempre que la mejora
en el equilibrio de carga se pueda amortizar con sobrecostes del
paralelismo de tareas
El mapeado de tareas a procesos que resulta del cálculo del
precondicionador también resulta apropiado para su aplicación. Los
ajustes que realiza la resolución regresiva en este mapeado mejoran
su rendimiento en muchos casos
El enfoque de paralelización preserva la semántica de las técnicas
de precondicionado de ILUPACK (bajo grado de sensibilidad del
#iter. al #CPUs)
El enfoque de paralelización obtiene eficiencias paralelas notables
con los particionados calculados por ParMETIS y PT-SCOTCH
Defensa Tesis Doctoral 69 A.F. Martín
Conclusiones y líneas abiertas
Conclusiones del estudio experimental
La eficiencia paralela de la aproximación propuesta depende de: →
distribución del coste entre los niveles del árbol → balance entre
beneficios y sobrecostes del paralelismo
Alto grado de eficiencia paralela para resolver los sistemas
ligados a una EDP 3D en un multiprocesador con memoria compartida
comercial
La planificación dinámica aumenta eficiencia siempre que la mejora
en el equilibrio de carga se pueda amortizar con sobrecostes del
paralelismo de tareas
El mapeado de tareas a procesos que resulta del cálculo del
precondicionador también resulta apropiado para su aplicación. Los
ajustes que realiza la resolución regresiva en este mapeado mejoran
su rendimiento en muchos casos
El enfoque de paralelización preserva la semántica de las técnicas
de precondicionado de ILUPACK (bajo grado de sensibilidad del
#iter. al #CPUs)
El enfoque de paralelización obtiene eficiencias paralelas notables
con los particionados calculados por ParMETIS y PT-SCOTCH
Defensa Tesis Doctoral 69 A.F. Martín
Conclusiones y líneas abiertas
REVISTAS
ALIAGA, J. I., BOLLHÖFER, M., MARTÍN, A. F., AND QUINTANA-ORTÍ, E.
S.
Exploiting Thread-Level Parallelism in the Iterative Solution of
Sparse Linear Systems. Parallel Computing, pp. 1–23 En revisión (1a
revisión, abril 2010; 2a revisión).
Defensa Tesis Doctoral 70 A.F. Martín
Conclusiones y líneas abiertas
ACTAS DE CONFERENCIAS INTERNACIONALES
ALIAGA, J. I., BOLLHÖFER, M., MARTÍN, A. F., AND QUINTANA-ORTÍ, E.
S.
Parallelization of Multilevel Preconditioners Constructed from
Inverse-Based ILUs on SMMs In Parallel Computing: Architectures,
Algorithms and Applications (2007), C. Bischof et. al., Eds., vol.
38 of Advances in Parallel Computing, pp. 287–294. PARCO’07, Jülich
(Alemania).
ALIAGA, J. I., BOLLHÖFER, M., MARTÍN, A. F., AND QUINTANA-ORTÍ, E.
S.
Design, Tuning and Evaluation of Parallel Multilevel ILU
Preconditioners. In High Performance Computing for Computational
Science - VECPAR 2008 (2008), J. Palma et. al., Eds., vol. 5336 of
Lecture Notes in Computer Science, Springer, pp. 314–327.
VECPAR’08, Toulouse (Francia).
ALIAGA, J. I., BOLLHÖFER, M., MARTÍN, A. F., AND QUINTANA-ORTÍ, E.
S.
Scheduling Strategies for Parallel Sparse Backward/Forward
Substitution. In 9-th International Workshop on State-of-the-Art in
Scientific and Parallel Computing (2008). En revisión.
ALIAGA, J. I., BOLLHÖFER, M., MARTÍN, A. F., AND QUINTANA-ORTÍ, E.
S.
Recent advances in the parallel iterative solution of large-scale
sparse linear systems. In 9th International Conference on
Computational and Mathematical Methods in Science and Engineering
(2009), vol. 1, pp. 68–72. CMMSE’09, Gijón (España).
ALIAGA, J. I., BOLLHÖFER, M., MARTÍN, A. F., AND QUINTANA-ORTÍ, E.
S.
Evaluation of Parallel Sparse Matrix Partitioning Sw for Parallel
Multilevel ILU Preconditioning on SMMs In Parallel Computing: From
Multicores and GPU’s to Petascale (2009), B. Chapman et. al., Eds.,
vol. 19 of Advances in Parallel Computing, pp. 125–132. PARCO’09,
Lyon (Francia).
ALIAGA, J. I., BOLLHÖFER, M., MARTÍN, A. F., AND QUINTANA-ORTÍ, E.
S.
Parallelization of Multilevel ILU Preconditioners on
Distributed-Memory Multiprocessors. In PARA 2010: State of the Art
in Scientific and Parallel Computing (2010). En revisión.
Defensa Tesis Doctoral 71 A.F. Martín
Conclusiones y líneas abiertas
ACTAS DE CONFERENCIAS NACIONALES
ALIAGA, J. I., MARTÍN, A. F., AND QUINTANA-ORTÍ, E. S.
Optimización de algoritmos de álgebra lineal dispersa para MMCs
mediante KOJAK y VAMPIR. In XVIII Jornadas de Paralelismo (2007),
pp. 759–766. Zaragoza (España).
ALIAGA, J. I., MARTÍN, A. F., AND QUINTANA-ORTÍ, E. S.
Scheduling strategies for parallel sparse linear algebra
computacions on multithreaded architectures. In XIX Jornadas de
Paralelismo (2008), pp. 51–56. Castellón (España).
ALIAGA, J. I., MARTÍN, A. F., AND QUINTANA-ORTÍ, E. S.
Avances en la Resolución Paralela de Sistemas de Ecuaciones
Lineales Precondicionados mediante factorizaciones ILU Multinivel.
In Congreso de Métodos Numéricos en Ingeniería (2009), p. 338.
METNUM’09. Barcelona (España).
PONENCIAS EN CONFERENCIAS INTERNACIONALES
ALIAGA, J. I., BOLLHÖFER, M., MARTÍN, A. F., AND QUINTANA-ORTÍ, E.
S.
Parallel Multilevel ILU Preconditioners. 5th International Workshop
on Parallel Matrix Algorithms and Applications. Junio, 2008.
Neuchâtel (Suiza).
ALIAGA, J. I., BOLLHÖFER, M., MARTÍN, A. F., AND QUINTANA-ORTÍ, E.
S.
Parallel Preconditioning based on ILUPACK for Multithreaded
Architectures. SIAM Conference on Computational Science and
Engineering. Marzo, 2009. Miami (EE.UU).
Defensa Tesis Doctoral 72 A.F. Martín
Conclusiones y líneas abiertas
Líneas abiertas de investigación
Integrar códigos en la versión 2.3 de la biblioteca ILUPACK
Desarrollar algoritmos y sw. paralelos para el cálculo de la
disección anidada en multiprocesadores con memoria compartida y
procesadores multinúcleo
Aplicar códigos desarrollados para resolver otros problemas reales
de interés científico e ingenieril
Desarrollar algoritmos y sw. paralelos de resolución, basados en el
enfoque de ILUPACK, para multiprocesadores con memoria
distribuida
Extender enfoque de paralelización para casos más generales
(simétrico indefinido y no simétrico pero estructuralmente
simétrico)
Defensa Tesis Doctoral 73 A.F. Martín
Conclusiones y líneas abiertas
Utilización del Paralelismo Multihebra en el Precondicionado y la
Resolución Iterativa de Sistemas Lineales Dispersos
Alberto Fco. Martín Huertas
Introducción y motivación
Identificación de concurrencia en los precondicionadores LDLT
multinivel
Cálculo paralelo de precondicionadores LDLT multinivel
Resolución iterativa paralela del sistema precondicionado
Evaluación experimental del proceso global de resolución
Conclusiones y líneas abiertas