Download - Modelado de rutinas de álgebra lineal
![Page 1: Modelado de rutinas de álgebra lineal](https://reader031.vdocumento.com/reader031/viewer/2022011905/61d6f81f97ca8912a115a55a/html5/thumbnails/1.jpg)
1
Modelado de rutinas de álgebra lineal
El modelado es necesario para predecir el tiempo de ejecución y seleccionar: El número de procesos El número de procesadores Qué procesadores La topología (p.e: número de filas y columnas de procesos) La asignación de procesos a procesadores El tamaño de bloque computacional (en algoritmos de
álgebra lineal) El tamaño de bloque de comunicación El algoritmo (polialgoritmos) La rutina o librería (polilibrerías)
![Page 2: Modelado de rutinas de álgebra lineal](https://reader031.vdocumento.com/reader031/viewer/2022011905/61d6f81f97ca8912a115a55a/html5/thumbnails/2.jpg)
2
Coste de un programa paralelo:
: tiempo aritmético: tiempo de comunicación: overhead, por sincronización, desbalanceo,
creación de procesos, ...: overlapping de comunicación y computación
Modelado de rutinas de álgebra lineal
overlapoverheadcommarithparallel ttttt −++=aritht
commtoverheadt
overlapt
![Page 3: Modelado de rutinas de álgebra lineal](https://reader031.vdocumento.com/reader031/viewer/2022011905/61d6f81f97ca8912a115a55a/html5/thumbnails/3.jpg)
3
Estimación del tiempo:
Considerando computación divididas en un número de pasos independientes:
y para cada parte de la fórmula el tiempo del proceso con mayor coste.
Modelado de rutinas de álgebra lineal
commarithparallel ttt +=
...2,2,1,1, ++++= commarithcommarithparallel ttttt
![Page 4: Modelado de rutinas de álgebra lineal](https://reader031.vdocumento.com/reader031/viewer/2022011905/61d6f81f97ca8912a115a55a/html5/thumbnails/4.jpg)
4
El tiempo depende del tamaño del problema (n) y del sistema (p):
y también de algunos ALGORITHMIC PARAMETERS, como el tamaño de bloque (b) y el número de filas (r) y de columnas (c) de procesadores, en algoritmos para malla de procesos
Modelado de rutinas de álgebra lineal
),( pnt parallel
),,,( crbnt parallel
![Page 5: Modelado de rutinas de álgebra lineal](https://reader031.vdocumento.com/reader031/viewer/2022011905/61d6f81f97ca8912a115a55a/html5/thumbnails/5.jpg)
5
Y de algunos SYSTEM PARAMETERS que reflejan las características de computación y comunicación del sistema.
Típicamente son el coste de una operación aritmética (tc) y el start-up (ts) y el word-
sending time (tw)
Modelado de rutinas de álgebra lineal
),,( SPAPnt parallel
![Page 6: Modelado de rutinas de álgebra lineal](https://reader031.vdocumento.com/reader031/viewer/2022011905/61d6f81f97ca8912a115a55a/html5/thumbnails/6.jpg)
6
La idea de parametrización de las rutinas para tomar decisiones aparece en:
La propuesta de trabajo de LAPACK:Demmel, Dongarra: ScaLAPACK proposal 2004 En HeteroScaLAPACK:Ravi Reddy, Alexey Lastovetsky:
HeteroMPI+ScaLAPACK: Towards a ScaLAPACK (Dense Linear Solvers) for Heterogeneous Networks of Computers. HiPC 2006, Bangalore
Modelado de rutinas de álgebra lineal
![Page 7: Modelado de rutinas de álgebra lineal](https://reader031.vdocumento.com/reader031/viewer/2022011905/61d6f81f97ca8912a115a55a/html5/thumbnails/7.jpg)
7
Factorización LU (Golub - Van Loan):
=
Paso 1: (factorización LU sin bloques)
Paso 2: (sistema triangular inferior múltiple)
Paso 3: (sistema triangular superior múltiple)
Paso 4: (actualización de bloques sur-este)
Modelado de rutinas de álgebra lineal
A11
A22
A33A32A31
A23A21
A13A12 L11
L22
L33L32L31
L21
U11
U22
U33
U23
U13U12
111111 ULA =ii ULA 1111 =
1111 ULA ii =jiijij ULAA 11−=
![Page 8: Modelado de rutinas de álgebra lineal](https://reader031.vdocumento.com/reader031/viewer/2022011905/61d6f81f97ca8912a115a55a/html5/thumbnails/8.jpg)
8
Tiempo de ejecución:
si los bloques son de tamaño 1, las operaciones son sobre elementos individuales, pero si el tamaño de bloques es b, el coste es:
con k3 y k2 el coste de operaciones realizadas con BLAS 3 y BLAS 2
Modelado de rutinas de álgebra lineal
3
32)( nnt tcsequential =
nbbnnnt kkksequential2
23
33
3 31
32)( ++=
![Page 9: Modelado de rutinas de álgebra lineal](https://reader031.vdocumento.com/reader031/viewer/2022011905/61d6f81f97ca8912a115a55a/html5/thumbnails/9.jpg)
9
Pero el coste de operaciones del mismo nivel es también diferente, y se podría modelar el tiempo añadiendo más parámetros:
de este modo, aumenta el número de SYSTEM PARAMETERS (uno por cada rutina básica), y ...
Modelado de rutinas de álgebra lineal
nbbnnnt kkk dgetfdtrsmdgemmsequential2
2_23
_33
_3 31
32)( ++=
![Page 10: Modelado de rutinas de álgebra lineal](https://reader031.vdocumento.com/reader031/viewer/2022011905/61d6f81f97ca8912a115a55a/html5/thumbnails/10.jpg)
10
El valor de cada System Parameter puede depender del tamaño del problema (n) y del valor de los Algorithmic Parameters (b)
La fórmula queda en la forma:
y lo que queremos es obtener los valores de AP con los que se obtiene el menor tiempo de ejecución teórico
Modelado de rutinas de álgebra lineal
nbbnbnbnnbnbnt kkk dgetfdtrsmdgemmsequential2
2_23
_33
_3 31),(),(
32),(),( ++=
)),(,,( APnSPAPnt
![Page 11: Modelado de rutinas de álgebra lineal](https://reader031.vdocumento.com/reader031/viewer/2022011905/61d6f81f97ca8912a115a55a/html5/thumbnails/11.jpg)
11
El valor de los System Parameters se puede obtener Con rutinas de instalación asociadas a cada rutina
de álgebra lineal Utilizando información obtenida en la instalación
de las librerías en el sistema, generando una jerarquía de librerías con autooptimización
En tiempo de ejecución testeando las condiciones del sistema antes de llamar a la rutina (sistemas de carga variable)
Modelado de rutinas de álgebra lineal
![Page 12: Modelado de rutinas de álgebra lineal](https://reader031.vdocumento.com/reader031/viewer/2022011905/61d6f81f97ca8912a115a55a/html5/thumbnails/12.jpg)
12
Los valores se pueden obtener como valores simples (método tradicional) o como función de los Algorithmic Parameters: Se almacena una tabla multidimensional con valores que
son función del tamaño del problema y de los Algorithmic Parameters
Se hace un ajuste por mínimos cuadrados y se guardan los valores de las constantes
Cuando se resuelve un problema para una cierta entrada se utilizan los valores de los System Parameteres estimados, y se resuelve con los valores de los Algorithmic Parameters con que se predice el menor tiempo de ejecución
Modelado de rutinas de álgebra lineal
![Page 13: Modelado de rutinas de álgebra lineal](https://reader031.vdocumento.com/reader031/viewer/2022011905/61d6f81f97ca8912a115a55a/html5/thumbnails/13.jpg)
13
Coste de factorización LU paralela por bloques:
Algorithmic Parameters:tamaño de bloque: b
malla 2D de p procesos: p = r ×c, d=max(r,c)
System Parameters:coste de operaciones aritméticas: k2,getf2 k3,trsmm k3,gemm
parámetros de comunicación: ts tw
Modelado de rutinas de álgebra lineal
nkbnbkp
crp
nkT getftrsmgemmARI 2,222
,3
3
,3 31
32 +++=
pdnt
bndtT wsCOM
222 +=
![Page 14: Modelado de rutinas de álgebra lineal](https://reader031.vdocumento.com/reader031/viewer/2022011905/61d6f81f97ca8912a115a55a/html5/thumbnails/14.jpg)
14
Coste de factorización QR paralela por bloques:
Algorithmic Parameters:tamaño de bloque: b
malla 2D de p procesos: p = r ×c
System Parameters:coste de operaciónes aritméticas: k2,geqr2 k2,larft k3,gemm k3,trmm
parámetros de comunicación: ts tw
Modelado de rutinas de álgebra lineal
r
bkn
rbkn
c
bkn
p
knT
larftgeqrtrmmgemm
ARI
,22
2,22,3
2,3
3
21
41
34
+++=
( )( ) ( )
+
++−+
++= pnb
rr
cr
rrntcrb
bntT wsCOM logloglog12
2log2log32 2
2
![Page 15: Modelado de rutinas de álgebra lineal](https://reader031.vdocumento.com/reader031/viewer/2022011905/61d6f81f97ca8912a115a55a/html5/thumbnails/15.jpg)
15
La misma operación básica aparece en diferentes rutinas: la información generada para una rutina o para una librería, puede ser almacenada y utilizada para otra rutina o libreríaes necesario un formato común para almacenar la información
Modelado de rutinas de álgebra lineal
![Page 16: Modelado de rutinas de álgebra lineal](https://reader031.vdocumento.com/reader031/viewer/2022011905/61d6f81f97ca8912a115a55a/html5/thumbnails/16.jpg)
16
Modelado de rutinas de álgebra lineal
IBMSP2. 8 processors 0,00
10,00
20,00
30,00
40,00
50,00
60,00
70,00
80,00
512 1024 1536 2048 2560 3072 3584
problem size
time
(sec
onds
)
mean
model
optimum
Factorización QR paralela
“ mean” : media de los tiempos de ejecución con valores representativos de los Algorithmic Parameters (tiempo que podría obtener un usuario no experto)
“ optimum” : el menor tiempo obtenido con ejecuciones variando los valores de los Algorithmic Parameters
“ model” : el tiempo con los valores de los Algorithmic Parameters seleccionados por el modelo
![Page 17: Modelado de rutinas de álgebra lineal](https://reader031.vdocumento.com/reader031/viewer/2022011905/61d6f81f97ca8912a115a55a/html5/thumbnails/17.jpg)
17
En la fórmula de la factorización LU paralela por bloques
los valores de losSystem Parameters (k2,getf2 , k3,trsmm , k3,gemm , ts , tw) se estiman en función del tamaño de la entrada (n) y de los Algorithmic Parameters (b, r, c)
Rutinas de instalación
ncrbnkbncrbnbkp
crp
ncrbnkcrbnT getftrsmgemmARI ),,,(31),,,(),,,(
32),,,( 2,2
22,3
3
,3 +++=
pdncrbnt
bndcrbntcrbnT wsCOM
22),,,(2),,,(),,,( +=
![Page 18: Modelado de rutinas de álgebra lineal](https://reader031.vdocumento.com/reader031/viewer/2022011905/61d6f81f97ca8912a115a55a/html5/thumbnails/18.jpg)
18
Rutinas de instalaciónEjecutando en tiempo de instalación Rutinas de
Instalación asociadas a la rutina de álgebra lineal,y almacenando la información generada para utilizarla
en tiempo de ejecución
⇒Cada rutina de álgebra lineal debe diseñarse
con sus rutinas de instalación y el proceso de instalación
o construir una capa de instalación sobre una librería ya existente
![Page 19: Modelado de rutinas de álgebra lineal](https://reader031.vdocumento.com/reader031/viewer/2022011905/61d6f81f97ca8912a115a55a/html5/thumbnails/19.jpg)
19
Se estima con multiplicaciones matriz-matriz y actualizaciones de tamaño (n/r ×b) × (b ×n/c)
El tamaño de las matrices varía a lo largo de la ejecución: se pueden estimar valores diferentes para tamaños distintos, y en la fórmula se puede contemplar el uso de distintos valores dividiendo la fórmula en distintas partes
Rutinas de instalación),,,(,3 crbnk gemm
![Page 20: Modelado de rutinas de álgebra lineal](https://reader031.vdocumento.com/reader031/viewer/2022011905/61d6f81f97ca8912a115a55a/html5/thumbnails/20.jpg)
20
y aparecen en comunicaciones de tres tipos,
en una se difunde en una fila un bloque b ×b, y el parámetro depende de b c
en otra se difunde en una columna un bloque b ×b, y el parámetro depende de b y r
y en otra, se difunden bloques b ×n/c y n/r ×b en cada una de las filas y columnas, y el parámetro depende de n, b, r y c
Rutinas de instalación),,,( crbnts ),,,( crbntw
![Page 21: Modelado de rutinas de álgebra lineal](https://reader031.vdocumento.com/reader031/viewer/2022011905/61d6f81f97ca8912a115a55a/html5/thumbnails/21.jpg)
21
En la práctica cada System Parameter depende de un número reducido de Algorithmic Parameters, pero esto se conoce tras completar la instalación.
El diseñador de la rutina diseña también la instalación, y puede diseñar el proceso de instalación utilizando su experiencia.
Puede también diseñarse un proceso de instalación que permita la intervención del system manager.
Rutinas de instalación
![Page 22: Modelado de rutinas de álgebra lineal](https://reader031.vdocumento.com/reader031/viewer/2022011905/61d6f81f97ca8912a115a55a/html5/thumbnails/22.jpg)
22
Algunos resultados en diferentes sistemas (físicos y lógicos)Valores de k3_DTRMM ( ≈ k3_DGEMM) en las diferentes plataformas (microsegundos)
Rutinas de instalación
0.00250.00250.00300.0070512,.., 4096macBLASR10K
0.00180.00180.00190.0023512,.., 4096macBLASPPC
0.00300.00300.00330.0038512,.., 4096ATLASPIII
0.01500.00500.0025
0.01400.00500.0025
0.01300.00500.0032
0.01200.00600.0040
512,.., 4096512,.., 4096512,.., 4096
refBLASmacBLAS
ATLAS
SUN5
0.02800.01100.0060
0.02200.01100.0060
0.02000.01100.0060
0.02000.01200.0070
512,.., 4096512,.., 4096512,.., 4096
refBLASmacBLAS
ATLAS
SUN1
128643216nSystem
Block size
![Page 23: Modelado de rutinas de álgebra lineal](https://reader031.vdocumento.com/reader031/viewer/2022011905/61d6f81f97ca8912a115a55a/html5/thumbnails/23.jpg)
23
Rutinas de instalaciónValores de k2_DGEQR2 ( ≈ k2_DLARFT) en diferentes plataformas (microsegundos)
0.0250512,.., 4096macBLASR10K
0.0100512,.., 4096macBLASPPC
0.0150512,.., 4096ATLASPIII
0.00500.03000.0500
512,.., 4096512,.., 4096512,.., 4096
refBLASmacBLAS
ATLAS
SUN5
0.02000.05000.0700
512,.., 4096512,.., 4096512,.., 4096
refBLASmacBLAS
ATLAS
SUN1
128643216nSystem
Block size
![Page 24: Modelado de rutinas de álgebra lineal](https://reader031.vdocumento.com/reader031/viewer/2022011905/61d6f81f97ca8912a115a55a/html5/thumbnails/24.jpg)
24
Normalmente los valores de los parámetros de comunicación se estiman bien con un ping-pong
Rutinas de instalación
20 / 0.1512,.., 4096Mac-MPIOrigin 2K
75 / 0.3512,.., 4096Mac-MPIIBM-SP2
60 / 0.7512,.., 4096MPICHcPIII
170 / 7.0512,.., 4096MPICHcSUN1
128643216nSystem
Block size
![Page 25: Modelado de rutinas de álgebra lineal](https://reader031.vdocumento.com/reader031/viewer/2022011905/61d6f81f97ca8912a115a55a/html5/thumbnails/25.jpg)
25
Modelling the Linear Algebra Routine
(LAR)
Obtaining information from
the System
Selectionof
parameters values
Executionof LAR
DESIGN
INSTALLATION
RUNTI
ME
Rutinas con autooptimización
![Page 26: Modelado de rutinas de álgebra lineal](https://reader031.vdocumento.com/reader031/viewer/2022011905/61d6f81f97ca8912a115a55a/html5/thumbnails/26.jpg)
26
DISEÑO
DESIGN
LAR: Linear Algebra RoutineMade by the LAR Designer
Example of LAR: Parallel Block LU factorisation
LAR
![Page 27: Modelado de rutinas de álgebra lineal](https://reader031.vdocumento.com/reader031/viewer/2022011905/61d6f81f97ca8912a115a55a/html5/thumbnails/27.jpg)
27
Modelado de LAR
DESIGN
LAR
Modellingthe LAR
MODEL
![Page 28: Modelado de rutinas de álgebra lineal](https://reader031.vdocumento.com/reader031/viewer/2022011905/61d6f81f97ca8912a115a55a/html5/thumbnails/28.jpg)
28
Modelado de LAR
DESIGN
MODELTexec = f (SP, AP, n)
SP: System Parameters AP: Algorithmic Parameters n : Problem size
Made by the LAR-DesignerOnly once per LAR
LAR
Modellingthe LAR
MODEL
![Page 29: Modelado de rutinas de álgebra lineal](https://reader031.vdocumento.com/reader031/viewer/2022011905/61d6f81f97ca8912a115a55a/html5/thumbnails/29.jpg)
29
Modelado de LAR
DESIGN
SP: k3, k2, ts, tw
AP: p = r x c, bn : Problem size
MODEL LAR: Parallel Block LU factorisation
LAR
Modellingthe LAR
MODEL
![Page 30: Modelado de rutinas de álgebra lineal](https://reader031.vdocumento.com/reader031/viewer/2022011905/61d6f81f97ca8912a115a55a/html5/thumbnails/30.jpg)
30
Implementación de los estimadores
DESIGN
LAR
Modellingthe LAR
MODEL
Implementationof SPEstimators
SPEstimators
![Page 31: Modelado de rutinas de álgebra lineal](https://reader031.vdocumento.com/reader031/viewer/2022011905/61d6f81f97ca8912a115a55a/html5/thumbnails/31.jpg)
31
Implementación de los estimadores
DESIGN
LAR
Modellingthe LAR
MODEL
Implementationof SPEstimators
SPEstimators
Estimators of Arithmetic-SPComputation Kernel of the LARSimilar storage schemeSimilar quantity of data
Estimators of Communication-SP Communication Kernel of the LAR Similar kind of communicationSimilar quantity of data
![Page 32: Modelado de rutinas de álgebra lineal](https://reader031.vdocumento.com/reader031/viewer/2022011905/61d6f81f97ca8912a115a55a/html5/thumbnails/32.jpg)
32
INSTALACIÓN
INSTALLATION
LAR
Modellingthe LAR
MODEL
Implementationof SPEstimators
SPEstimators
DESIGN
Installation ProcessOnly once per PlatformGuided by the System Manager
![Page 33: Modelado de rutinas de álgebra lineal](https://reader031.vdocumento.com/reader031/viewer/2022011905/61d6f81f97ca8912a115a55a/html5/thumbnails/33.jpg)
33
Estimación estática de los SP
INSTALLATION
LAR
Modellingthe LAR
MODEL
Implementationof SP
EstimatorsSPEstimators
Estimationof StaticSP
StaticSPFile
Basic Libraries InstallationFile
DESIGN
![Page 34: Modelado de rutinas de álgebra lineal](https://reader031.vdocumento.com/reader031/viewer/2022011905/61d6f81f97ca8912a115a55a/html5/thumbnails/34.jpg)
34
Estimación estática de los SP
INSTALLATION
LAR
Modellingthe LAR
MODEL
Implementationof SP
EstimatorsSPEstimators
Estimationof StaticSP
StaticSPFile
Basic Libraries InstallationFile
DESIGN
Basic LibrariesBasic Communication Library:
MPI PVM
Basic Linear Algebra Library: referenceBLAS
machinespecificBLASATLAS
Installation FileSP values are obtained using the information (n and AP values) of this file.
![Page 35: Modelado de rutinas de álgebra lineal](https://reader031.vdocumento.com/reader031/viewer/2022011905/61d6f81f97ca8912a115a55a/html5/thumbnails/35.jpg)
35
Estimación estática de los SPLAR
Modellingthe LAR
MODEL
Implementationof SPEstimators
SPEstimators
Estimationof StaticSP
StaticSPFile
Basic Libraries InstallationFile
DESIGN
INSTALLATION
Estimation of the StaticSP twstatic (in µsec)
Message size (Kbytes) 32 256 1024 2048twstatic 0.700 0.690 0.680 0.675
Platform: Cluster of Pentium III + Fast Ethernet
Basic Libraries: ATLAS and MPI
Estimation of the StaticSP k3static (in µsec)
Block size 16 32 64 128k3static 0.0038 0.0033 0.0030 0.0027
![Page 36: Modelado de rutinas de álgebra lineal](https://reader031.vdocumento.com/reader031/viewer/2022011905/61d6f81f97ca8912a115a55a/html5/thumbnails/36.jpg)
36
EJECUCIÓN
INSTALLATION
LAR
Modellingthe LAR
MODEL
Implementationof SP
EstimatorsSPEstimators
Estimationof StaticSP
StaticSPFile
Basic Libraries InstallationFile
DESIGN
RUNTIME
![Page 37: Modelado de rutinas de álgebra lineal](https://reader031.vdocumento.com/reader031/viewer/2022011905/61d6f81f97ca8912a115a55a/html5/thumbnails/37.jpg)
37
Selección de AP óptimos
INSTALLATION
LAR
Modellingthe LAR
MODEL
Implementationof SP
EstimatorsSPEstimators
Estimationof StaticSP
StaticSPFile
Basic Libraries InstallationFile
OptimumAP
Selectionof Optimum AP
DESIGN
RUNTIME
![Page 38: Modelado de rutinas de álgebra lineal](https://reader031.vdocumento.com/reader031/viewer/2022011905/61d6f81f97ca8912a115a55a/html5/thumbnails/38.jpg)
38
Ejecución
INSTALLATION
LAR
Modellingthe LAR
MODEL
Implementationof SP
EstimatorsSPEstimators
Estimationof StaticSP
StaticSPFile
Basic Libraries InstallationFile
OptimumAP
Selectionof Optimum AP
Executionof LAR
DESIGN
RUNTIME
![Page 39: Modelado de rutinas de álgebra lineal](https://reader031.vdocumento.com/reader031/viewer/2022011905/61d6f81f97ca8912a115a55a/html5/thumbnails/39.jpg)
39
Rutinas con autooptimizaciónExperimentosLAR: factorización LU por bloques.Plataformas: IBM SP2,
SGI Origin 2000, NoW
Librarías básicas: reference BLAS, machine BLAS, ATLAS
![Page 40: Modelado de rutinas de álgebra lineal](https://reader031.vdocumento.com/reader031/viewer/2022011905/61d6f81f97ca8912a115a55a/html5/thumbnails/40.jpg)
40
Rutinas con autooptimización
LU en IBM SP2
Cociente entre el tiempode ejecución con los parámetros seleccionadospor el modelo y el menortiempo de ejecuciónexperimental
0
0,2
0,4
0,6
0,8
1
1,2
1,4
5121024
15362048
25603072
3584
SEQPAR4PAR8
![Page 41: Modelado de rutinas de álgebra lineal](https://reader031.vdocumento.com/reader031/viewer/2022011905/61d6f81f97ca8912a115a55a/html5/thumbnails/41.jpg)
41
Rutinas con autooptimizaciónLU en Origin 2000
Cociente entre el tiempode ejecución con los parámetros seleccionadospor el modelo y el menortiempo de ejecuciónexperimental
0
0,2
0,4
0,6
0,8
1
1,2
1,4
5121024
15362048
25603072
3584
SEQPAR4PAR8PAR16
![Page 42: Modelado de rutinas de álgebra lineal](https://reader031.vdocumento.com/reader031/viewer/2022011905/61d6f81f97ca8912a115a55a/html5/thumbnails/42.jpg)
42
Rutinas con autooptimizaciónLU en NoW
Cociente entre el tiempode ejecución con los parámetros seleccionadospor el modelo y el menortiempo de ejecuciónexperimental
0,96
0,98
1
1,02
1,04
1,06
1,08
1,1
512 1024 1536 2048
SEQ BLASSEQ ATLASPAR4 BLASPAR4 ATLAS
![Page 43: Modelado de rutinas de álgebra lineal](https://reader031.vdocumento.com/reader031/viewer/2022011905/61d6f81f97ca8912a115a55a/html5/thumbnails/43.jpg)
43
Modificación de la jerarquía de librerías En distintas rutinas aparecen repetidas
operaciones básicas: LU:
QR:
nkbnbkp
crp
nkT getftrsmgemmARI 2,222
,3
3
,3 31
32 +++=
pdnt
bndtT wsCOM
222 +=
r
bkn
rbkn
c
bkn
p
knT
larftgeqrtrmmgemm
ARI
,22
2,22,3
2,3
3
21
41
34
+++=
( )( ) ( )
+
++−+
++= pnb
rr
cr
rrntcrb
bntT wsCOM logloglog12
2log2log32 2
2
![Page 44: Modelado de rutinas de álgebra lineal](https://reader031.vdocumento.com/reader031/viewer/2022011905/61d6f81f97ca8912a115a55a/html5/thumbnails/44.jpg)
44
Modificación de la jerarquía de librerías
La información que se genera al instalar una rutina se puede usar para otra rutina diferente: ts y tw se obtienen cuando se instala la
librería de comunicación (MPI, PVM, … ) K3,gemm se obtiene cuando se instala la
librería computacional básica (BLAS, ATLAS, … )
![Page 45: Modelado de rutinas de álgebra lineal](https://reader031.vdocumento.com/reader031/viewer/2022011905/61d6f81f97ca8912a115a55a/html5/thumbnails/45.jpg)
45
Modificación de la jerarquía de librerías
El método debe ser válido para la librería que estamos desarrollando pero también para otras que se desarrollen en el futuro. Decidir: Tipo de experimentos Formato en que se almacenan los datos
debería decidirlo la comunidad de álgebra lineal paralela
… y podría cambiar la jerarquía de librerías clásica
![Page 46: Modelado de rutinas de álgebra lineal](https://reader031.vdocumento.com/reader031/viewer/2022011905/61d6f81f97ca8912a115a55a/html5/thumbnails/46.jpg)
46
Modificación de la jerarquía de librerías
Jerarquía clásica delibrerías paralelasde álgebra lineal
ScaLAPACK
LAPACK
BLAS
PBLAS
BLACS
Communications
![Page 47: Modelado de rutinas de álgebra lineal](https://reader031.vdocumento.com/reader031/viewer/2022011905/61d6f81f97ca8912a115a55a/html5/thumbnails/47.jpg)
47
Modificación de la jerarquía de librerías
Incluir informaciónde instalación enlos niveles másbajos de la jerarquía
ScaLAPACK
LAPACK
BLAS
PBLAS
BLACS
CommunicationsSelfOptimisation
Information SelfOptimisation Information
![Page 48: Modelado de rutinas de álgebra lineal](https://reader031.vdocumento.com/reader031/viewer/2022011905/61d6f81f97ca8912a115a55a/html5/thumbnails/48.jpg)
48
Modificación de la jerarquía de librerías
Al instalar libreríasen niveles superioresse puede usar lainformación previa,y se genera nuevainformación
ScaLAPACK
LAPACK
BLAS
PBLAS
BLACS
CommunicationsSelfOptimisation
Information
SelfOptimisation Information
SelfOptimisation Information
SelfOptimisation Information
![Page 49: Modelado de rutinas de álgebra lineal](https://reader031.vdocumento.com/reader031/viewer/2022011905/61d6f81f97ca8912a115a55a/html5/thumbnails/49.jpg)
49
Modificación de la jerarquía de librerías
Y lo mismo paraniveles mayores
ScaLAPACK
LAPACK
BLAS
PBLAS
BLACS
CommunicationsSelfOptimisation
Information SelfOptimisation Information
SelfOptimisation Information
SelfOptimisation Information
SelfOptimisation Information
SelfOptimisation Information
![Page 50: Modelado de rutinas de álgebra lineal](https://reader031.vdocumento.com/reader031/viewer/2022011905/61d6f81f97ca8912a115a55a/html5/thumbnails/50.jpg)
50
ScaLAPACKSelfOptimisation
Information
Inverse Eigenvalue ProblemLeast Square ProblemPDE SolverSelfOptimisation
InformationSelfOptimisation
InformationSelfOptimisation
Information
Modificación de la jerarquía de librerías
Y con nuevaslibrerías que sepuedan desarrollar
LAPACK
BLAS
PBLAS
BLACS
CommunicationsSelfOptimisation
Information SelfOptimisation Information
SelfOptimisation Information
SelfOptimisation Information
SelfOptimisation Information
![Page 51: Modelado de rutinas de álgebra lineal](https://reader031.vdocumento.com/reader031/viewer/2022011905/61d6f81f97ca8912a115a55a/html5/thumbnails/51.jpg)
51
Modificación de la jerarquía de librerías
Movimientode información entre rutinasen diferentes niveles de lajerarquía
GETRF from LAPACK (level 1)
GETRF_manager
k3_information
Model
GETRF {
}
GEMM from BLAS (level 0)
GEMM_manager
k3_information
Model
GEMM {
}
23
333
2 nbknkTexec +=
332 nkTexec =
![Page 52: Modelado de rutinas de álgebra lineal](https://reader031.vdocumento.com/reader031/viewer/2022011905/61d6f81f97ca8912a115a55a/html5/thumbnails/52.jpg)
52
Modificación de la jerarquía de librerías
Movimientode información entre rutinasen diferentes niveles de lajerarquía
![Page 53: Modelado de rutinas de álgebra lineal](https://reader031.vdocumento.com/reader031/viewer/2022011905/61d6f81f97ca8912a115a55a/html5/thumbnails/53.jpg)
53
Modificación de la jerarquía de librerías
Movimientode información entre rutinasen diferentes niveles de lajerarquía
![Page 54: Modelado de rutinas de álgebra lineal](https://reader031.vdocumento.com/reader031/viewer/2022011905/61d6f81f97ca8912a115a55a/html5/thumbnails/54.jpg)
54
Modificación de la jerarquía de librerías
Arquitectura deun Self OptimizedLinear AlgebraRoutine manager
SP1_information
SP1_manager
Installation_SP1_values
AP1 .......... APz
n1 SP11,1 .... SP1
1,z
nw SP1w,1 .... SP1
w,z
Current_SP1_values
AP1 .......... APz
nc SP1c,1 .... SP1
c,z
SP1_information
SP1_manager
Installation_SP1_values
AP1 .......... APz
n1 SP11,1 .... SP1
1,z
nw SP1w,1 .... SP1
w,z
Current_SP1_values
AP1 .......... APz
nc SP1c,1 .... SP1
c,z
. . .
LAR(n, AP){
...}
Model
Texec = f (SP,AP, n)SP = f(AP,n)
Installation_information
n1 ... nw
AP1
...APz
Current_problem_sizenc
Current_system_informationCurrent_CPUs_availability
%CPU1 ... %CPUp
Current_network_availability
% net11 ...%net1p
...% netP1 ..%netpp
SOLAR_manager
Optimum_AP AP0
SP1_information
SP1_manager
Installation_SP1_values
AP1 .......... APz
n1 SP11,1 .... SP1
1,z
nw SP1w,1 .... SP1
w,z
Current_SP1_values
AP1 .......... APz
nc SP1c,1 .... SP1
c,z
SPt_information
SPt_manager
Installation_SP1_values
AP1 .......... APz
n1 SPt1,1 .... SPt
1,z
nw SPtw,1 .... SPt
w,z
Current_SP1_values
AP1 .......... APz
nc SPtc,1 .... SPt
c,z
![Page 55: Modelado de rutinas de álgebra lineal](https://reader031.vdocumento.com/reader031/viewer/2022011905/61d6f81f97ca8912a115a55a/html5/thumbnails/55.jpg)
55
Polilibrerías Puede haber disponibles diferentes librerías
básicas: BLAS de referencia, específico de la máquina,
ATLAS, ... MPICH, MPI específico del sistema, PVM, ... LAPACK de referencia, específico, ... ScaLAPACK, PLAPACK, ...
⇒ usar diferentes librerías para desarrollar una polilibrería
![Page 56: Modelado de rutinas de álgebra lineal](https://reader031.vdocumento.com/reader031/viewer/2022011905/61d6f81f97ca8912a115a55a/html5/thumbnails/56.jpg)
56
PolilibreríasJerarquía clásica de librerías de álgebra lineal
ScaLAPACK
LAPACK
BLAS
PBLAS
BLACS
MPI, PVM, ...
![Page 57: Modelado de rutinas de álgebra lineal](https://reader031.vdocumento.com/reader031/viewer/2022011905/61d6f81f97ca8912a115a55a/html5/thumbnails/57.jpg)
57
PolilibreríasPosible jerarquía de polilibrerías de álgebra lineal paralela
ScaLAPACK
LAPACK PBLAS
BLACS
MPI, PVM, ...
ref. BLAS
mac. BLAS
ATLAS
![Page 58: Modelado de rutinas de álgebra lineal](https://reader031.vdocumento.com/reader031/viewer/2022011905/61d6f81f97ca8912a115a55a/html5/thumbnails/58.jpg)
58
PolilibreríasPosible jerarquía de polilibrerías de álgebra lineal paralela
ScaLAPACK
LAPACK PBLAS
BLACS
ref. BLAS
mac. BLAS
ATLASmac. MPI
LAM
MPICH
PVM
![Page 59: Modelado de rutinas de álgebra lineal](https://reader031.vdocumento.com/reader031/viewer/2022011905/61d6f81f97ca8912a115a55a/html5/thumbnails/59.jpg)
59
PolilibreríasPosible jerarquía de polilibrerías de álgebra lineal paralela
ScaLAPACKmac. LAPACK
PBLAS
BLACS
ref. BLAS
mac. BLAS
ATLASmac. MPI
LAM
MPICH
PVM
ESSL
ref. LAPACK
![Page 60: Modelado de rutinas de álgebra lineal](https://reader031.vdocumento.com/reader031/viewer/2022011905/61d6f81f97ca8912a115a55a/html5/thumbnails/60.jpg)
60
Polilibrerías
BLACS
PBLAS
ref. BLAS
mac. BLAS
ATLASmac. MPI
LAM
MPICH
PVM
mac. LAPACK
ESSL
ref. LAPACK
mac. ScaLAPACK
ESSL
ref. ScaLAPACK
![Page 61: Modelado de rutinas de álgebra lineal](https://reader031.vdocumento.com/reader031/viewer/2022011905/61d6f81f97ca8912a115a55a/html5/thumbnails/61.jpg)
61
Polilibrerías Ventajas de las polilibrerías:
Puede no haber una librería optimizada para el sistema
Pueden cambiar las características del sistema Qué librería es mejor puede variar con la rutina y el
sistema También con el tamaño del problema o la forma de
almacenamiento de los datos En sistemas heterogéneos con el procesador en que
se ejecuta la rutina
![Page 62: Modelado de rutinas de álgebra lineal](https://reader031.vdocumento.com/reader031/viewer/2022011905/61d6f81f97ca8912a115a55a/html5/thumbnails/62.jpg)
62
Polilibrerías: ArquitecturaLibrary_1
![Page 63: Modelado de rutinas de álgebra lineal](https://reader031.vdocumento.com/reader031/viewer/2022011905/61d6f81f97ca8912a115a55a/html5/thumbnails/63.jpg)
63
Polilibrerías: ArquitecturaLibrary_1
LIF_1
Installation
![Page 64: Modelado de rutinas de álgebra lineal](https://reader031.vdocumento.com/reader031/viewer/2022011905/61d6f81f97ca8912a115a55a/html5/thumbnails/64.jpg)
64
Polilibrerías: ArquitecturaLibrary_1
LIF_1
Installation
X MflopsX MflopsX Mflops80
X MflopsX MflopsX Mflops40n
X MflopsX MflopsX Mflops20
804020
m
Routine: DGEMM
![Page 65: Modelado de rutinas de álgebra lineal](https://reader031.vdocumento.com/reader031/viewer/2022011905/61d6f81f97ca8912a115a55a/html5/thumbnails/65.jpg)
65
Polilibrerías: ArquitecturaLibrary_1
LIF_1
Installation
X MflopsX MflopsX Mflops400
X MflopsX MflopsX Mflops200n
X MflopsX MflopsX Mflops100
2001001
Leading dimension
Routine: DROT
![Page 66: Modelado de rutinas de álgebra lineal](https://reader031.vdocumento.com/reader031/viewer/2022011905/61d6f81f97ca8912a115a55a/html5/thumbnails/66.jpg)
66
Polilibrerías: ArquitecturaLibrary_2Library_1
LIF_1
Installation
![Page 67: Modelado de rutinas de álgebra lineal](https://reader031.vdocumento.com/reader031/viewer/2022011905/61d6f81f97ca8912a115a55a/html5/thumbnails/67.jpg)
67
Polilibrerías: ArquitecturaLibrary_2
LIF_2
Library_1
LIF_1
Installation Installation
![Page 68: Modelado de rutinas de álgebra lineal](https://reader031.vdocumento.com/reader031/viewer/2022011905/61d6f81f97ca8912a115a55a/html5/thumbnails/68.jpg)
68
Polilibrerías: ArquitecturaLibrary_2
LIF_2
Library_3Library_1
LIF_1
Installation Installation
![Page 69: Modelado de rutinas de álgebra lineal](https://reader031.vdocumento.com/reader031/viewer/2022011905/61d6f81f97ca8912a115a55a/html5/thumbnails/69.jpg)
69
Polilibrerías: ArquitecturaLibrary_2
LIF_2
Library_3
LIF_3
Installation
Library_1
LIF_1
Installation Installation
![Page 70: Modelado de rutinas de álgebra lineal](https://reader031.vdocumento.com/reader031/viewer/2022011905/61d6f81f97ca8912a115a55a/html5/thumbnails/70.jpg)
70
Polilibrerías: Arquitectura
PolyLibrary
interface routine_1interface routine_2
...
Library_2
LIF_2
Library_3
LIF_3
Installation
Library_1
LIF_1
Installation Installation
![Page 71: Modelado de rutinas de álgebra lineal](https://reader031.vdocumento.com/reader031/viewer/2022011905/61d6f81f97ca8912a115a55a/html5/thumbnails/71.jpg)
71
Polilibrerías: Arquitectura
PolyLibrary
interface routine_1interface routine_2
...
interface routine_1 if n<value call routine_1 from Library_1 else depending on data storage call routine_1 from Library_1 or call routine_1 from Library_2 ...
Library_2
LIF_2
Library_3
LIF_3
Installation
Library_1
LIF_1
Installation Installation
![Page 72: Modelado de rutinas de álgebra lineal](https://reader031.vdocumento.com/reader031/viewer/2022011905/61d6f81f97ca8912a115a55a/html5/thumbnails/72.jpg)
72
Polilibrerías Rutinas de diferentes niveles en la jerarquía:
Nivel inferior: multiplicación GEMM Nivel medio: factorizaciones LU y QR Nivel superior:
Algoritmo Lift&Project para el problema inverso aditivo de valores propios
Algoritmo para el problema de mínimos cuadrados de matrices Toeplitz
Plataformas: SGI Origin 2000, IBM-SP2, redes de procesadores (SUN, PC+Ethernet, FastE, Myrinet)
![Page 73: Modelado de rutinas de álgebra lineal](https://reader031.vdocumento.com/reader031/viewer/2022011905/61d6f81f97ca8912a115a55a/html5/thumbnails/73.jpg)
73
Polilibrerías: experimentos GEMMRutina: GEMM (multiplicación matriz-matriz)
Plataforma: 5 SUN Ultra 1 / 1 SUN Ultra 5
Librerías:refBLAS macBLASATLAS1 ATLAS2 ATLAS5
Algoritmos y Parámetros: Strassen nivel de recursiónpor bloques tamaño de bloquemétodo directo
![Page 74: Modelado de rutinas de álgebra lineal](https://reader031.vdocumento.com/reader031/viewer/2022011905/61d6f81f97ca8912a115a55a/html5/thumbnails/74.jpg)
74
Polilibrerías: experimentos GEMMMATRIX-MATRIX MULTIPLICATION INTERFACE:if processor is SUN Ultra 5 if problem-size<600
solve using ATLAS5 and Strassen method with base size half of problem size
else if problem-size<1000solve using ATLAS5 and block method with block size 400
elsesolve using ATLAS5 and Strassen method with base size half of problem size
endifelse if processor is SUN Ultra 1 if problem-size<600 solve using ATLAS5 and direct method else if problem-size<1000
solve using ATLAS5 and Strassen method with base size half of problem size
else solve using ATLAS5 and direct method endifendif
![Page 75: Modelado de rutinas de álgebra lineal](https://reader031.vdocumento.com/reader031/viewer/2022011905/61d6f81f97ca8912a115a55a/html5/thumbnails/75.jpg)
75
Polilibrerías: experimentos GEMM
20.03ATL5
bloques400
12.53ATL2Strass
2
4.68ATL5Strass
2
1.06ATL5
directo
0.04ATL5
directo
TiempoLibreríaMétodoParámetro
Low
31.0213.504.831.060.04TiempoATLAS5Directo
26.57ATL5Strass
2
12.58ATL5Strass
2
4.68ATL5Strass
2
1.11ATL5
bloques400
0.04ATL5Strass
2
TiempoLibreríaMétodoParámetro
Mod
160014001000600200
n
![Page 76: Modelado de rutinas de álgebra lineal](https://reader031.vdocumento.com/reader031/viewer/2022011905/61d6f81f97ca8912a115a55a/html5/thumbnails/76.jpg)
76
Polilibrerías: experimentos L&P
Rutina: Lift-and-Project para el problema inverso aditivo de valores propios
Plataforma: dual Pentium III
Combinaciones de librerías:
RLAPACK de referencia y BLAS instalado que usa threadsLa_Re+B_In_Th
LAPACK de referencia y BLAS para Pentium II que usa threads
La_Re+B_II_Th
LAPACK y BLAS instalados, que usan threadsLa_In_Th+B_In_Th
LAPACK de referencia y el BLAS instaladoLa_Re+B_In
LAPACK de referencia y BLAS para PentiumIILa_Re+B_II
LAPACK de referencia y BLAS para PentiumIII La_Re+B_III
LAPACK y BLAS instaladas en el sistema y supuestamente optimizadas para él
La_In+B_In
![Page 77: Modelado de rutinas de álgebra lineal](https://reader031.vdocumento.com/reader031/viewer/2022011905/61d6f81f97ca8912a115a55a/html5/thumbnails/77.jpg)
77
Coste teórico del algoritmos secuencial:
Parámetros del sistema:ksyev LAPACK
k3, gemm k3, diaggemm BLAS-3
k1,dot k1,scal k1,axpy BLAS-1
Polilibrerías: experimentos L&P
+
++ 3
,3,32322 nkkkiter diaggemmgemmsyev
( ) 222,1
2,1,1,1 22 nLkLnkLnkkkiter sumdotaxpyscaldot ++++
![Page 78: Modelado de rutinas de álgebra lineal](https://reader031.vdocumento.com/reader031/viewer/2022011905/61d6f81f97ca8912a115a55a/html5/thumbnails/78.jpg)
78
Polilibrerías: experimentos L&P
Lowest
Lowest with threads
La_Re
La_Re
La_In_Th
Lowest no threads
La_Re
La_Re
La_Re
La_In
197.069.996.660.62165.8112.861.10
281.709.996.660.62249.5913.711.10
290.6811.9013.740.62249.5913.711.10B_In_Th
288.669.996.660.79254.3415.681.16B_II_Th
308.8012.3414.130.66266.6313.921.10B_In_Th
201.6410.4410.520.83165.8112.861.16
497.5918.03123.731.21336.4916.411.69B_In
293.8510.4410.520.86255.2015.651.16B_II
264.8910.4626.700.83210.8514.871.16B_III
294.3214.2298.790.94165.8112.861.69B_In
TOTALZKAOAMATMATMATEIGEIGENADKTRACE