programaci n orientada a bloques
TRANSCRIPT
ProgramacionOrientada aBloques
Julio J. AguilaG.
Introduccion
Bibliotecasnumericas
Algoritmosbasicos paramatrices
Programacion Orientada a Bloques
Adaptacion: Julio J. Aguila G.1
Autores: Enriques Arias2, Diego Cazorla1
1Departamento de Ingenierıa en Computacion-UMAG2Departamento de Sistemas Informaticos-UCLM
martes 10 de marzo de 2015
Julio J. Aguila G. (UMAG) Programacion Orientada a Bloques martes 10 de marzo de 2015 1 / 37
ProgramacionOrientada aBloques
Julio J. AguilaG.
Introduccion
Bibliotecasnumericas
Algoritmosbasicos paramatrices
1 Introduccion
2 Bibliotecas numericas
3 Algoritmos basicos para matrices
Julio J. Aguila G. (UMAG) Programacion Orientada a Bloques martes 10 de marzo de 2015 2 / 37
ProgramacionOrientada aBloques
Julio J. AguilaG.
Introduccion
Bibliotecasnumericas
Algoritmosbasicos paramatrices
Introduccion
1 Introduccion
2 Bibliotecas numericas
3 Algoritmos basicos para matrices
Julio J. Aguila G. (UMAG) Programacion Orientada a Bloques martes 10 de marzo de 2015 3 / 37
ProgramacionOrientada aBloques
Julio J. AguilaG.
Introduccion
Bibliotecasnumericas
Algoritmosbasicos paramatrices
Introduccion
Objetivo
Incremento de las prestaciones de los algoritmos secuencialeshabituales mediante la optimizacion en el uso de la jerarquıa dememoria, de tal manera que se reduzca el trafico entre elsistema de memoria central y el sistema de antememoria(cache).
Julio J. Aguila G. (UMAG) Programacion Orientada a Bloques martes 10 de marzo de 2015 4 / 37
ProgramacionOrientada aBloques
Julio J. AguilaG.
Introduccion
Bibliotecasnumericas
Algoritmosbasicos paramatrices
Introduccion
Ambito de aplicacion
Sistemas monoprocesadores.
Sistemas multiprocesadores con memoria compartida.
Julio J. Aguila G. (UMAG) Programacion Orientada a Bloques martes 10 de marzo de 2015 5 / 37
ProgramacionOrientada aBloques
Julio J. AguilaG.
Introduccion
Bibliotecasnumericas
Algoritmosbasicos paramatrices
Introduccion
Motivacion
Las aplicaciones pueden clasificarse en tres categorıas enfuncion de los recursos computacionales que requieren:
Limitadas por la E/S: requieren realizar muchasoperaciones de E/S.
Limitadas por la memoria central: requieren un usointensivo del sistema de memoria central. Los problemasrelacionados con el algebra lineal pertenecen a estacategorıa.
Limitadas por el procesador: requieren un uso intensivo delprocesador.
Julio J. Aguila G. (UMAG) Programacion Orientada a Bloques martes 10 de marzo de 2015 6 / 37
ProgramacionOrientada aBloques
Julio J. AguilaG.
Introduccion
Bibliotecasnumericas
Algoritmosbasicos paramatrices
Introduccion
La diferencia entre la velocidad del procesador y la velocidad deacceso a la memoria central es cada vez mayor. En loscomputadores actuales el cuello de botella suele estar en elacceso al sistema de memoria central.
Es necesario redisenar los algoritmos para intentar conseguirque el lımite resida en el procesador y no en el sistema dememoria central.
Julio J. Aguila G. (UMAG) Programacion Orientada a Bloques martes 10 de marzo de 2015 7 / 37
ProgramacionOrientada aBloques
Julio J. AguilaG.
Introduccion
Bibliotecasnumericas
Algoritmosbasicos paramatrices
Introduccion
Niveles habituales de la jerarquıa de memoria
Registros de memoria del procesador.
Memoria dentro del circuito del procesador (cache-on-chipo L1).
Memoria externa al circuito del procesador (cache L2).
Memoria principal o RAM.
Memoria en disco o memoria virtual (disco duro).
Objetivo
Minimizar el trafico de datos entre la memoria principal y lacache.
Julio J. Aguila G. (UMAG) Programacion Orientada a Bloques martes 10 de marzo de 2015 8 / 37
ProgramacionOrientada aBloques
Julio J. AguilaG.
Introduccion
Bibliotecasnumericas
Algoritmosbasicos paramatrices
Bibliotecas numericas
1 Introduccion
2 Bibliotecas numericas
3 Algoritmos basicos para matrices
Julio J. Aguila G. (UMAG) Programacion Orientada a Bloques martes 10 de marzo de 2015 9 / 37
ProgramacionOrientada aBloques
Julio J. AguilaG.
Introduccion
Bibliotecasnumericas
Algoritmosbasicos paramatrices
Bibliotecas numericas
Aplicaciones
Gran numero de aplicaciones en Ciencias e Ingenierıapuede reducirse a la resolucion de problemas numericosalgebraicos.
La mayor parte de los problemas del algebra lineal puedeformularse en funcion de unas pocas operaciones basicas:producto de matrices, resolucion de sistemas, etc.
Una implementacion eficiente de estas operaciones permiteobtener buenas prestaciones en numerosos problemas.
Julio J. Aguila G. (UMAG) Programacion Orientada a Bloques martes 10 de marzo de 2015 10 / 37
ProgramacionOrientada aBloques
Julio J. AguilaG.
Introduccion
Bibliotecasnumericas
Algoritmosbasicos paramatrices
Bibliotecas numericas
En los anos 70 un grupo de investigadores desarrolla unconjunto de rutinas que implementan las operaciones mashabituales relacionadas con vectores.
BLAS: Basic Linear Algebra Subroutines.
Esta primera implementacion de BLAS serebautizo posteriormente como BLAS level 1 (BLAS-1)porque el costo de las operaciones es de O(n) flops.
Julio J. Aguila G. (UMAG) Programacion Orientada a Bloques martes 10 de marzo de 2015 11 / 37
ProgramacionOrientada aBloques
Julio J. AguilaG.
Introduccion
Bibliotecasnumericas
Algoritmosbasicos paramatrices
Bibliotecas numericas
Ventajas de BLAS
Estabilidad numerica: se tiene en cuenta aspectosmatematicos y de precision del computador que elprogramador no suele considerar.
Portabilidad de los programas.
Legibilidad de los programas.
Julio J. Aguila G. (UMAG) Programacion Orientada a Bloques martes 10 de marzo de 2015 12 / 37
ProgramacionOrientada aBloques
Julio J. AguilaG.
Introduccion
Bibliotecasnumericas
Algoritmosbasicos paramatrices
Bibliotecas numericas
En los anos 80 se desarrollaron BLAS-2 y BLAS-3 (1990).
BLAS level 2 and 3
BLAS level 2 (BLAS-2): considera las operacionesmatriz-vector mas habituales.
BLAS level 3 (BLAS-3): considera operacionesmatriz-matriz.
Julio J. Aguila G. (UMAG) Programacion Orientada a Bloques martes 10 de marzo de 2015 13 / 37
ProgramacionOrientada aBloques
Julio J. AguilaG.
Introduccion
Bibliotecasnumericas
Algoritmosbasicos paramatrices
Bibliotecas numericas
Julio J. Aguila G. (UMAG) Programacion Orientada a Bloques martes 10 de marzo de 2015 14 / 37
ProgramacionOrientada aBloques
Julio J. AguilaG.
Introduccion
Bibliotecasnumericas
Algoritmosbasicos paramatrices
Algoritmos basicos para matrices
1 Introduccion
2 Bibliotecas numericas
3 Algoritmos basicos para matrices
Julio J. Aguila G. (UMAG) Programacion Orientada a Bloques martes 10 de marzo de 2015 15 / 37
ProgramacionOrientada aBloques
Julio J. AguilaG.
Introduccion
Bibliotecasnumericas
Algoritmosbasicos paramatrices
Algoritmos basicos para matrices
Notacion matricial: matriz de dimension m × n
A ∈ ℜm×n
⇐⇒ A = (aij) =
a11 . . . a1n...
. . ....
am1 . . . amn
, aij ∈ ℜ.
Los elementos de la matriz pueden denotarse mediante:
aij , [A]ij , A(i , j).
Julio J. Aguila G. (UMAG) Programacion Orientada a Bloques martes 10 de marzo de 2015 16 / 37
ProgramacionOrientada aBloques
Julio J. AguilaG.
Introduccion
Bibliotecasnumericas
Algoritmosbasicos paramatrices
Algoritmos basicos para matrices
Operaciones con matrices
Transposicion:C = AT
⇒ cij = aji .
Suma:C = A+ B ⇒ cij = aij + bij .
Producto escalar-matriz con α ∈ ℜ:
C = αA ⇒ cij = αaij .
Producto matriz-matriz con A ∈ ℜm×r ∧ B ∈ ℜr×n:
C = AB ⇒ cij =k=r∑
k=1
aikbkj , C ∈ ℜm×n
.
Julio J. Aguila G. (UMAG) Programacion Orientada a Bloques martes 10 de marzo de 2015 17 / 37
ProgramacionOrientada aBloques
Julio J. AguilaG.
Introduccion
Bibliotecasnumericas
Algoritmosbasicos paramatrices
Algoritmos basicos para matrices
Notacion vectorial: vector de dimension n
x ∈ ℜn
⇐⇒ x =
x1...xn
, xi ∈ ℜ.
Los elementos de x pueden denotarse xi o x(i).
Se identifica ℜn con ℜn×1, es decir, se considera vectores
columna.
Un vector fila se representa mediante xT .
Si se hubiera considerado ℜ1×n se tendrıa vectores fila:
x ∈ ℜ1×n
⇐⇒ x =(
x1 . . . xn)
.
Julio J. Aguila G. (UMAG) Programacion Orientada a Bloques martes 10 de marzo de 2015 18 / 37
ProgramacionOrientada aBloques
Julio J. AguilaG.
Introduccion
Bibliotecasnumericas
Algoritmosbasicos paramatrices
Algoritmos basicos para matrices
Operaciones con vectores
Producto escalar-vector con α ∈ ℜ:
z = αx ⇒ zi = αxi .
Suma:z = x + y ⇒ zi = xi + yi .
Producto escalar (dot product) con x ∈ ℜn ∧ y ∈ ℜn:
c = xT y ⇒ c =
i=n∑
i=1
xiyi , c ∈ ℜ.
Producto interno:
z = x · y ⇒ zi = xiyi .
Saxpy (scalar alpha x plus y) con α ∈ ℜ:
z = αx + y ⇒ zi = αxi + yi .
Julio J. Aguila G. (UMAG) Programacion Orientada a Bloques martes 10 de marzo de 2015 19 / 37
ProgramacionOrientada aBloques
Julio J. AguilaG.
Introduccion
Bibliotecasnumericas
Algoritmosbasicos paramatrices
Algoritmos basicos para matrices
Operaciones con vectores y matrices
Producto externo de vectores (outer product) conx ∈ ℜm ∧ y ∈ ℜn:
A = xyT ⇒ aij = xiyj , A ∈ ℜm×n
.
Producto matriz-vector con A ∈ ℜm×n ∧ x ∈ ℜn:
z = Ax ⇒ zi =
k=n∑
k=1
aikxk , z ∈ ℜm.
Gaxpy (general A x plus y) conA ∈ ℜm×n ∧ x ∈ ℜn ∧ y ∈ ℜm:
z = Ax + y ⇒ zi =k=n∑
k=1
aikxk + yi , z ∈ ℜm.
Julio J. Aguila G. (UMAG) Programacion Orientada a Bloques martes 10 de marzo de 2015 20 / 37
ProgramacionOrientada aBloques
Julio J. AguilaG.
Introduccion
Bibliotecasnumericas
Algoritmosbasicos paramatrices
Algoritmos basicos para matrices
Dados los vectores x ∈ ℜn e y ∈ ℜn, el siguiente algoritmocalcula c ∈ ℜ como c = xT y .
Algoritmo dot (producto escalar): c = xT y
function: c = dot( x, y)c = 0n = length(x)for i = 1:n
c = c + x(i) * y(i)end
end dot
Es una operacion O(n), lineal en la dimension del vector.
Julio J. Aguila G. (UMAG) Programacion Orientada a Bloques martes 10 de marzo de 2015 21 / 37
ProgramacionOrientada aBloques
Julio J. AguilaG.
Introduccion
Bibliotecasnumericas
Algoritmosbasicos paramatrices
Algoritmos basicos para matrices
Dados los vectores x ∈ ℜn e y ∈ ℜn, y un escalar α ∈ ℜ, elsiguiente algoritmo calcula el vector z ∈ ℜn como z = αx + y .
Algoritmo saxpy (scalar alpha x plus y): z = αx + y
function: z = saxpy( α, x, y)n = length(x)for i = 1:n
z(i) = α * x(i) + y(i)end
end saxpy
Es tambien una operacion O(n), lineal en la dimension delvector.
Julio J. Aguila G. (UMAG) Programacion Orientada a Bloques martes 10 de marzo de 2015 22 / 37
ProgramacionOrientada aBloques
Julio J. AguilaG.
Introduccion
Bibliotecasnumericas
Algoritmosbasicos paramatrices
Algoritmos basicos para matrices
Dados los vectores x ∈ ℜm e y ∈ ℜn, el siguiente algoritmocalcula la matriz A ∈ ℜm×n como A = xyT .
Algoritmo outer (producto externo de vectores): A = xyT
function: A = outer ij( x, y)m = length(x)n = length(y)for i = 1:m
for j = 1:nA(i,j) = x(i) * y(j)
end
end
end outer ij
Es una operacion O(m2). Hay una version por columnasouter ji, intercambiando el orden de los bucles. ¿Lo puedevisualizar?
Julio J. Aguila G. (UMAG) Programacion Orientada a Bloques martes 10 de marzo de 2015 23 / 37
ProgramacionOrientada aBloques
Julio J. AguilaG.
Introduccion
Bibliotecasnumericas
Algoritmosbasicos paramatrices
Algoritmos basicos para matrices
Dados una matriz A ∈ ℜm×n y un vector x ∈ ℜn, el siguientealgoritmo calcula el vector z ∈ ℜm como z = Ax , recorriendo lamatriz A por filas.
Algoritmo matvec (producto matriz-vector): z = Ax
function: z = matvec ij( A, x)m = rows(A)n = cols(A)z(1:m) = 0for i = 1:m
for j = 1:nz(i) = z(i) + A(i,j) * x(j)
end
end
end matvec ij
Es una operacion O(m2). Hay una version por columnasmatvec ji, intercambiando el orden de los bucles.
Julio J. Aguila G. (UMAG) Programacion Orientada a Bloques martes 10 de marzo de 2015 24 / 37
ProgramacionOrientada aBloques
Julio J. AguilaG.
Introduccion
Bibliotecasnumericas
Algoritmosbasicos paramatrices
Algoritmos basicos para matrices
Una matriz puede representarse como una pila de vectores fila:
A ∈ ℜm×n
⇐⇒ A =
a1T
...am
T
, ak ∈ ℜ
n.
Algoritmo matvec (producto matriz-vector): z = Ax
function: z = matvec ij( A, x)m = rows(A)z(1:m) = 0for i = 1:m
z(i) = aiT x ⇒ producto escalar (dot)
end
end matvec ij
Notese que en cada iteracion, la expresion implica a los nelementos de cada vector.
Julio J. Aguila G. (UMAG) Programacion Orientada a Bloques martes 10 de marzo de 2015 25 / 37
ProgramacionOrientada aBloques
Julio J. AguilaG.
Introduccion
Bibliotecasnumericas
Algoritmosbasicos paramatrices
Algoritmos basicos para matrices
Una matriz puede representarse como un conjunto de vectorescolumna:
A ∈ ℜm×n
⇐⇒ A =(
a1 . . . an)
, ak ∈ ℜm.
Algoritmo matvec (producto matriz-vector): z = Ax
function: z = matvec ji( A, x)m = rows(A)n = cols(A)z(1:m) = 0for j = 1:n
z = x(j)aj + z ⇒ saxpyend
end matvec ji
Notese que en cada iteracion, los m elementos de z actuancomo acumuladores.
Julio J. Aguila G. (UMAG) Programacion Orientada a Bloques martes 10 de marzo de 2015 26 / 37
ProgramacionOrientada aBloques
Julio J. AguilaG.
Introduccion
Bibliotecasnumericas
Algoritmosbasicos paramatrices
Algoritmos basicos para matrices
La notacion dos puntos (colon notation)
Permite representar filas y columnas de una matriz conuna notacion simplificada.
La fila k-esima de una matriz A ∈ ℜm×n se representamediante:
A(k , :) =(
ak1 . . . akn)
.
La columna k-esima de una matriz A ∈ ℜm×n serepresenta mediante:
A(:, k) =
a1k...
amk
.
Julio J. Aguila G. (UMAG) Programacion Orientada a Bloques martes 10 de marzo de 2015 27 / 37
ProgramacionOrientada aBloques
Julio J. AguilaG.
Introduccion
Bibliotecasnumericas
Algoritmosbasicos paramatrices
Algoritmos basicos para matrices
Utilizando la notacion dos puntos, los algoritmos del productomatriz-vector se pueden denotar de la siguiente forma:
matvec ij
for i = 1:mz(i) = A(i,:) x
end
O tambien:
for i = 1:mz(i) = dot(A(i,:),x)
end
matvec ji
z(1:m) = 0for j = 1:n
z = x(j) A(:,j) + zend
O tambien:
z(1:m) = 0for j = 1:n
z = saxpy( x(j), A(:,j), z)end
Julio J. Aguila G. (UMAG) Programacion Orientada a Bloques martes 10 de marzo de 2015 28 / 37
ProgramacionOrientada aBloques
Julio J. AguilaG.
Introduccion
Bibliotecasnumericas
Algoritmosbasicos paramatrices
Algoritmos basicos para matrices
Acceso a matrices por filas/columnas
La diferencia entre matvec ij y matvec ji es el modo deacceso a la matriz. Dependiendo del lenguaje utilizadosera preferible utilizar un acceso por filas (matvec ij) o porcolumnas (matvec ji). Por ejemplo:
Por filas (row major): es el que utiliza C.
Por columnas (column major): es el que utiliza Fortran.
Julio J. Aguila G. (UMAG) Programacion Orientada a Bloques martes 10 de marzo de 2015 29 / 37
ProgramacionOrientada aBloques
Julio J. AguilaG.
Introduccion
Bibliotecasnumericas
Algoritmosbasicos paramatrices
Algoritmos basicos para matrices
Dados los vectores x ∈ ℜn e y ∈ ℜm, y una matriz A ∈ ℜm×n,el siguiente algoritmo calcula el vector z ∈ ℜm comoz = Ax + y .
Algoritmo gaxpy (general A x plus y): z = Ax + y
function: z = gaxpy( A, x, y)n = cols(A)z = yfor j = 1:n
z = A(:,j) x(j) + z ⇒ saxpyend
end gaxpy
Notese que el vector z se actualiza con cada iteracion medianteuna secuencia de operaciones saxpy. Ası, gaxpy es unageneralizacion de saxpy.
Julio J. Aguila G. (UMAG) Programacion Orientada a Bloques martes 10 de marzo de 2015 30 / 37
ProgramacionOrientada aBloques
Julio J. AguilaG.
Introduccion
Bibliotecasnumericas
Algoritmosbasicos paramatrices
Algoritmos basicos para matrices
Nivel de una operacion
dot y saxpy son ejemplos de operaciones de nivel 1. Estasoperaciones son lineales en la dimension de la operacion:O(n).
gaxpy es de nivel 2. Es cuadratica en la cantidad de datosO(m × n) y tambien cuadratica en la cantidad de trabajoO(m × n).
Operaciones de nivel 3 son aquellas que implican productosmatriz-matriz. Estas operaciones son cuadraticas en lacantidad de datos y cubicas en la cantidad de trabajo.
Julio J. Aguila G. (UMAG) Programacion Orientada a Bloques martes 10 de marzo de 2015 31 / 37
ProgramacionOrientada aBloques
Julio J. AguilaG.
Introduccion
Bibliotecasnumericas
Algoritmosbasicos paramatrices
Algoritmos basicos para matrices
Dadas dos matrices 2× 2, A y B , el calculo del producto dematrices C = AB puede realizarse por diferentesprocedimientos.
Version producto escalar (dot)
(
1 23 4
) (
5 67 8
)
=
(
1 · 5 + 2 · 7 1 · 6 + 2 · 83 · 5 + 4 · 7 3 · 6 + 4 · 8
)
Version saxpy
(
1 23 4
) (
5 67 8
)
=
(
5
(
13
)
+ 7
(
24
)
5
(
13
)
+ 7
(
24
) )
Version producto externo (outer)
(
1 23 4
) (
5 67 8
)
=
(
13
)
(
5 6)
+
(
24
)
(
7 8)
Julio J. Aguila G. (UMAG) Programacion Orientada a Bloques martes 10 de marzo de 2015 32 / 37
ProgramacionOrientada aBloques
Julio J. AguilaG.
Introduccion
Bibliotecasnumericas
Algoritmosbasicos paramatrices
Algoritmos basicos para matrices
Dadas dos matrices, A ∈ ℜm×r y B ∈ ℜr×n, se calcula la matrizC = AB mediante la operacion producto escalar (dot) entre lasfilas de A y las columnas de B . Este es el metodo tradicional.
Algoritmo matmat ijk
function: C = matmat ijk( A, B)m = rows(A)r = cols(A)n = cols(B)C(1:m,1:n) = 0for i = 1:m
for j = 1:nfor k = 1:r
C(i,j) = C(i,j) + A(i,k) * B(k,j)end
end
end
end matmat ijk
Julio J. Aguila G. (UMAG) Programacion Orientada a Bloques martes 10 de marzo de 2015 33 / 37
ProgramacionOrientada aBloques
Julio J. AguilaG.
Introduccion
Bibliotecasnumericas
Algoritmosbasicos paramatrices
Algoritmos basicos para matrices
Dadas dos matrices, A ∈ ℜm×r y B ∈ ℜr×n, se calcula lamatriz C = AB como una combinacion lineal de columnas de A
mediante la operacion gaxpy.
Algoritmo matmat jki
function: C = matmat jki( A, B)m = rows(A)r = cols(A)n = cols(B)C(1:m,1:n) = 0for j = 1:n
for k = 1:rfor i = 1:m
C(i,j) = C(i,j) + A(i,k) * B(k,j)end
end
end
end matmat jki
Julio J. Aguila G. (UMAG) Programacion Orientada a Bloques martes 10 de marzo de 2015 34 / 37
ProgramacionOrientada aBloques
Julio J. AguilaG.
Introduccion
Bibliotecasnumericas
Algoritmosbasicos paramatrices
Algoritmos basicos para matrices
Dadas dos matrices, A ∈ ℜm×r y B ∈ ℜr×n, se calcula lamatriz C = AB como el producto externo de C = C + akbk
T ,mediante la operacion outer.
Algoritmo matmat kji
function: C = matmat kji( A, B)m = rows(A)r = cols(A)n = cols(B)C(1:m,1:n) = 0for k = 1:r
for j = 1:nfor i = 1:m
C(i,j) = C(i,j) + A(i,k) * B(k,j)end
end
end
end matmat kji
Julio J. Aguila G. (UMAG) Programacion Orientada a Bloques martes 10 de marzo de 2015 35 / 37
ProgramacionOrientada aBloques
Julio J. AguilaG.
Introduccion
Bibliotecasnumericas
Algoritmosbasicos paramatrices
Algoritmos basicos para matrices
En multiplicaciones matriz-vector tenemos 2 bucles y 2!formas de ordenarlos.
En multiplicaciones matriz-matriz tenemos 3 bucles y 3!formas de ordenarlos.
Orden Bucle Bucle Acceso endel bucle interno medio bucle interno
ijk dot vector × matriz A filas, B columnasjik dot matriz × vector A filas, B columnasikj saxpy gaxpy fila B filasjki saxpy gaxpy columna A columnaskij saxpy outer fila B filaskji saxpy outer columna A columnas
Julio J. Aguila G. (UMAG) Programacion Orientada a Bloques martes 10 de marzo de 2015 36 / 37
ProgramacionOrientada aBloques
Julio J. AguilaG.
Introduccion
Bibliotecasnumericas
Algoritmosbasicos paramatrices
Algoritmos basicos para matrices
Programacion Orientada a Bloques
Adaptacion: Julio J. Aguila G.1
Autores: Enriques Arias2, Diego Cazorla1
1Departamento de Ingenierıa en Computacion-UMAG2Departamento de Sistemas Informaticos-UCLM
martes 10 de marzo de 2015
Julio J. Aguila G. (UMAG) Programacion Orientada a Bloques martes 10 de marzo de 2015 37 / 37