cepba - upc universitat politècnica de catalunya
TRANSCRIPT
![Page 1: CEPBA - UPC Universitat Politècnica de Catalunya](https://reader036.vdocumento.com/reader036/viewer/2022072718/62e07ade68672f40900cdb81/html5/thumbnails/1.jpg)
1
D A CCEPBA
![Page 2: CEPBA - UPC Universitat Politècnica de Catalunya](https://reader036.vdocumento.com/reader036/viewer/2022072718/62e07ade68672f40900cdb81/html5/thumbnails/2.jpg)
2
D A CCEPBA
Programación paraAltas Prestacionesen el Origin 2000
Febrero 1998
![Page 3: CEPBA - UPC Universitat Politècnica de Catalunya](https://reader036.vdocumento.com/reader036/viewer/2022072718/62e07ade68672f40900cdb81/html5/thumbnails/3.jpg)
Contenido
TEMA 1: Introducción a los Sistemas Multiprocesadores
❑ Multiprocesadores estilo Von Neumann
❑ Modelos de Organización
❑ Modelos de Programación
❑ Clasificación de los Multiprocesadores
❑ ¿Por qué Sistemas Multiprocesadores?
❑ Problemas y Retos
TEMA2: El Origin 2000
❑ Características Generales
❑ Organización del Nodo
❑ Organización de la Red
❑ El Procesador R10000
❑ Memorias Cache
❑ El TLB
❑ Caches y TLB en el R10000
❑ Minimizar Fallos de Cache y TLB
❑ Coherencia de Memoria
3
D A CCEPBA
![Page 4: CEPBA - UPC Universitat Politècnica de Catalunya](https://reader036.vdocumento.com/reader036/viewer/2022072718/62e07ade68672f40900cdb81/html5/thumbnails/4.jpg)
TEMA 3: Programación Eficiente en el Origin 2000
❑ Modelo de Programación
❑ Objetivos del Diseño de Algoritmos
❑ Fuentes de Ineficiencia
✓ Operaciones aritméticas innecesarias
✓ Accesos a memoria
✓ Fracción serie
✓ Sobrecarga de paralelización
✓ Desequilibrio de carga
✓ Sobrecarga de sincronización
TEMA 4: Optimización del Código New-dim
❑ Aspectos Generales
❑ Reducción de los Fallos de TLB
❑ Eliminacion de Operaciones Innecesarias
❑ Paralelización
4
D A CCEPBA
![Page 5: CEPBA - UPC Universitat Politècnica de Catalunya](https://reader036.vdocumento.com/reader036/viewer/2022072718/62e07ade68672f40900cdb81/html5/thumbnails/5.jpg)
5
D A CCEPBA
![Page 6: CEPBA - UPC Universitat Politècnica de Catalunya](https://reader036.vdocumento.com/reader036/viewer/2022072718/62e07ade68672f40900cdb81/html5/thumbnails/6.jpg)
6
D A CCEPBA
Planificación del Curso
EJERCICIO 1
TEMA 3: Programación
TEMA 4: New-dim
EJERCICIO 2
Martes Miércoles9:30
11:00
11:30
13:00
15:00
16:00
17:00
TEMA 2: El Origin 2000
TEMA 1: Introducción TEMA 3: Programación
12:00
![Page 7: CEPBA - UPC Universitat Politècnica de Catalunya](https://reader036.vdocumento.com/reader036/viewer/2022072718/62e07ade68672f40900cdb81/html5/thumbnails/7.jpg)
7
D A CCEPBA
Introducción a losSistemas Multiprocesadores
❑ Multiprocesadores estilo Von Neumann
❑ Modelos de Organización
❑ Modelos de Programación
❑ Clasificación de los Multiprocesadores
❑ ¿Por qué Sistemas Multiprocesadores?
❑ Problemas y Retos
![Page 8: CEPBA - UPC Universitat Politècnica de Catalunya](https://reader036.vdocumento.com/reader036/viewer/2022072718/62e07ade68672f40900cdb81/html5/thumbnails/8.jpg)
8
D A CCEPBA
Multiprocesadores estilo Von Neumann
Memoria
Procesador
E/S
Computador Von Neumann
Memoria
P1
E/S
Multiprocesador Von Neumann
P1P2
Pn
![Page 9: CEPBA - UPC Universitat Politècnica de Catalunya](https://reader036.vdocumento.com/reader036/viewer/2022072718/62e07ade68672f40900cdb81/html5/thumbnails/9.jpg)
9
D A CCEPBA
Otros Tipos de Multiprocesadores
❑ Multiprocesadores de Reducción
❑ Multiprocesadores de Flujo de Datos
❑ Redes Neuronales
![Page 10: CEPBA - UPC Universitat Politècnica de Catalunya](https://reader036.vdocumento.com/reader036/viewer/2022072718/62e07ade68672f40900cdb81/html5/thumbnails/10.jpg)
10
D A CCEPBA
Objetivos de un Multiprocesador
❑ Acelerar la ejecución de aplicaciones (orientados aspeed-up). SUPERCOMPUTACION.
❑ Ejecutar más aplicaciones por unidad de tiempo(orientados al throughput).
![Page 11: CEPBA - UPC Universitat Politècnica de Catalunya](https://reader036.vdocumento.com/reader036/viewer/2022072718/62e07ade68672f40900cdb81/html5/thumbnails/11.jpg)
11
D A CCEPBA
Modelos de Organización
❑ Multiprocesadores con Memoria Compartida
La red de interconexión permite a cualquier procesador acceder acualquier posición de memoria.
Memoria
Red de interconexión
P1 P2 Pn...
![Page 12: CEPBA - UPC Universitat Politècnica de Catalunya](https://reader036.vdocumento.com/reader036/viewer/2022072718/62e07ade68672f40900cdb81/html5/thumbnails/12.jpg)
12
D A CCEPBA
Modelos de Organización
❑ Multiprocesadores con Memoria Compartida
ProblemaLa red de interconexión representa un cuello de botella que impideque esta organización sea escalable.
Memoria
P1 P2 Pn...
Bus Común
Árbitro
![Page 13: CEPBA - UPC Universitat Politècnica de Catalunya](https://reader036.vdocumento.com/reader036/viewer/2022072718/62e07ade68672f40900cdb81/html5/thumbnails/13.jpg)
13
D A CCEPBA
Modelos de Organización
❑ Multiprocesadores con Memoria Distribuida
La red de interconexión permite a cualquier procesador comunicarsecon cualquiera de los procesadores del sistema.
P1 P2 Pn
M1 M2 Mn
Red de Interconexión
...
...
![Page 14: CEPBA - UPC Universitat Politècnica de Catalunya](https://reader036.vdocumento.com/reader036/viewer/2022072718/62e07ade68672f40900cdb81/html5/thumbnails/14.jpg)
14
D A CCEPBA
Modelos de Organización
❑ Multiprocesadores con Memoria Distribuida
La organización puede ser escalable en la medida en que losprogramas realicen comunicaciones locales.
P P P
M M MM
P
![Page 15: CEPBA - UPC Universitat Politècnica de Catalunya](https://reader036.vdocumento.com/reader036/viewer/2022072718/62e07ade68672f40900cdb81/html5/thumbnails/15.jpg)
15
D A CCEPBA
Modelos de Programación
❑ Programación Secuencial
Este es el modelo de programación ideal. Sin embargo, la tecnologíade compilación no permite todavía obtener un buen rendimiento delos sistemas multiprocesador (en particular, de los que tienenmemoria distribuida).
CODIGO SECUENCIALFORTRAN
COMPILADORPARALELIZADOR
CODIGO PARALELO
![Page 16: CEPBA - UPC Universitat Politècnica de Catalunya](https://reader036.vdocumento.com/reader036/viewer/2022072718/62e07ade68672f40900cdb81/html5/thumbnails/16.jpg)
16
D A CCEPBA
Modelos de Programación
❑ Programación Secuencial + Librería de RutinasParalelas
Limita el uso del sistema multiprocesador.
Estación deTrabajo
Multiprocesador
Código Fortran...
call MatMul...
Librería Paralela.....
![Page 17: CEPBA - UPC Universitat Politècnica de Catalunya](https://reader036.vdocumento.com/reader036/viewer/2022072718/62e07ade68672f40900cdb81/html5/thumbnails/17.jpg)
17
D A CCEPBA
Modelos de Programación
❑ El Modelo de Variables Compartidas
Las operaciones se descomponen en tareas.Los datos son compartidos por todas las tareas.Se requieren primitivas de sincronización para:
✓ Señalización✓ Acceso Exclusivo
a
b
c a
b
c
a=2*b
c=2*a
a=2*bc=2*asyncsync
TAREAs
DATOS DATOS
OPERACIONES
![Page 18: CEPBA - UPC Universitat Politècnica de Catalunya](https://reader036.vdocumento.com/reader036/viewer/2022072718/62e07ade68672f40900cdb81/html5/thumbnails/18.jpg)
18
D A CCEPBA
Modelos de Programación
❑ El Modelo de Paso de Mensajes
Las operaciones Y LOS DATOS se descomponen en procesos.Los procesos sólo tienen acceso directo a los datos privados(locales).Los datos no locales se acceden mediante intercambio de mensajesentre los procesos.
a
b
c a
b
a=2*b
c=2*a
a=2*bc=2*asend(a)
receive (a)
proceso
DATOS DATOS
OPERACIONES
c
![Page 19: CEPBA - UPC Universitat Politècnica de Catalunya](https://reader036.vdocumento.com/reader036/viewer/2022072718/62e07ade68672f40900cdb81/html5/thumbnails/19.jpg)
19
D A CCEPBA
Clasificación de los Multiprocesadores
PROGRAMACIÓN
RGANIZACIÓN
Variables Compartidas Paso de Mensajes
MemoriaCompartida
MemoriaDistribuida
SMP(Symmetric Multiprocessors)
Combinación natural
Poco escalable
Fácil de programar
DSM(Distributed Shared Memory)
Programación fácil
Escalable
Implementacióndifícil
Multicomputer
Combinación natural
Programación difícil
Escalable
?
Poco escalable
Programación difícilO
![Page 20: CEPBA - UPC Universitat Politècnica de Catalunya](https://reader036.vdocumento.com/reader036/viewer/2022072718/62e07ade68672f40900cdb81/html5/thumbnails/20.jpg)
20
D A CCEPBA
¿Por qué Sistemas Multiprocesadores?
Está ampliamente aceptado que los sistemas multiprocesadores (enparticular, los de memoria distribuida) representan uno de loscaminos más razonables para seguir aumentando la potencia decálculo de los computadores
Problemas y Retos
❑ HardwareBuscar organizaciones del sistema que permitan al software obteneruna fracción significativa de la velocidad máxima del sistema.
❑ Aplicaciones y AlgoritmosIdentificar aplicaciones críticas que pueden beneficiarse del uso delos sistemas multiprocesadores.Encontrar algoritmos paralelos eficientes para resolver los núcleoscomputacionales más habituales.
❑ HerramientasDesarrollar herramientas (modelos de programación, compiladores,depuradores, monitorizadores de rendimiento, etc) que faciliten eluso del sistema.
![Page 21: CEPBA - UPC Universitat Politècnica de Catalunya](https://reader036.vdocumento.com/reader036/viewer/2022072718/62e07ade68672f40900cdb81/html5/thumbnails/21.jpg)
21
D A CCEPBA
El Origin 2000
❑ Características Generales
❑ Organización del Nodo
❑ Organización de la Red
❑ El Procesador R10000
❑ Memorias Cache
❑ El TLB
❑ Caches y TLB en el R10000
❑ Minimizar Fallos de Cache y TLB
❑ Coherencia de Memoria
![Page 22: CEPBA - UPC Universitat Politècnica de Catalunya](https://reader036.vdocumento.com/reader036/viewer/2022072718/62e07ade68672f40900cdb81/html5/thumbnails/22.jpg)
22
D A CCEPBA
Características Generales
Organización DSM (Distributed Shared Memory):
✓ Modelo de programación: variable compartidas
✓ Memoria físicamente distribuida
También soporta otros modelos de programación:
✓ Paso de mensajes
✓ Programación secuencial con compiladorparalelizador
NI
PM
NI
PM
NI
PM
NI
PM
RED
Espacio de memoria compartido
load (X)
X
![Page 23: CEPBA - UPC Universitat Politècnica de Catalunya](https://reader036.vdocumento.com/reader036/viewer/2022072718/62e07ade68672f40900cdb81/html5/thumbnails/23.jpg)
23
D A CCEPBA
Organización del Nodo
RED
Nodo
I/O Local Switch (HUB)
Memoria
R10000
Cache
R10000
Cache
![Page 24: CEPBA - UPC Universitat Politècnica de Catalunya](https://reader036.vdocumento.com/reader036/viewer/2022072718/62e07ade68672f40900cdb81/html5/thumbnails/24.jpg)
Organización de la Red
P P
Mem
HUB
P P
Mem
HUB
PP
Mem
HU
B
P P
Mem
HUB
PP
Mem
HU
B
PP
Mem
HUB
PP
Mem
HU
BR R
Router
2 Procesadores4 Procesadores
8 Procesadores
24
D A CCEPBA
![Page 25: CEPBA - UPC Universitat Politècnica de Catalunya](https://reader036.vdocumento.com/reader036/viewer/2022072718/62e07ade68672f40900cdb81/html5/thumbnails/25.jpg)
Organización de la Red
RN
N
R N
N
RN
N
R N
N
RN
N
R N
N
RN
N
R N
N
RN
N
R N
N
RN
N
R N
N
RN
N
R N
N
RN
N
R N
N
64 Procesadores
25
D A CCEPBA
![Page 26: CEPBA - UPC Universitat Politècnica de Catalunya](https://reader036.vdocumento.com/reader036/viewer/2022072718/62e07ade68672f40900cdb81/html5/thumbnails/26.jpg)
El Procesador R10000
Otras características del procesador:
✓ Arquitectura superescalar: hasta 4 instrucciones porciclo
✓ Ejecución especulativa de saltos✓ Ejecución fuera de orden✓ Caches de datos no bloqueantes✓ Dos contadores de eventos
R10000
32 KB I-cache (L1)
2-way set associative
128- byte cache lines
32 KB D-cache (L1)
2-way set associative write-back
32- byte cache lines
TLB
64 entries
even/odd pages
Unified Secondary cache (L2, off-chip)
1, 2, or 4 MB
2-way set associative write-back
128- byte cache lines
26
D A CCEPBA
![Page 27: CEPBA - UPC Universitat Politècnica de Catalunya](https://reader036.vdocumento.com/reader036/viewer/2022072718/62e07ade68672f40900cdb81/html5/thumbnails/27.jpg)
Memorias Cache
❑ Principio Básico
✓ Futuros accesos a @5 serán atendidos a granvelocidad (localidad temporal)
✓ Futuros accesos a datos cercanos a @5 (@4, @6 ó@7) serán atendidos a gran velocidad (localidadespacial)
P
load (@5)
Cache
linea
Memoria Principal
54
67
27
D A CCEPBA
![Page 28: CEPBA - UPC Universitat Politècnica de Catalunya](https://reader036.vdocumento.com/reader036/viewer/2022072718/62e07ade68672f40900cdb81/html5/thumbnails/28.jpg)
Memorias Cache
❑ Asociatividad: Two-way set associative
linea
Memoria PrincipalCache
0123
Conjunto
28
D A CCEPBA
![Page 29: CEPBA - UPC Universitat Politècnica de Catalunya](https://reader036.vdocumento.com/reader036/viewer/2022072718/62e07ade68672f40900cdb81/html5/thumbnails/29.jpg)
29
D A CCEPBA
El TLB
❑ Traducción de direcciones
P
Espacio lógico dedireccionamiento
@Página
Memoria
Física
Trama
![Page 30: CEPBA - UPC Universitat Politècnica de Catalunya](https://reader036.vdocumento.com/reader036/viewer/2022072718/62e07ade68672f40900cdb81/html5/thumbnails/30.jpg)
El TLB
❑ Traducción de direcciones
P Desplazamientodentro de la página
@ lógica
Número de página
Tabla de páginas
EN MEMORIA
i
Número de trama en laque está la página i
@ física
Memoria
Física
30
D A CCEPBA
![Page 31: CEPBA - UPC Universitat Politècnica de Catalunya](https://reader036.vdocumento.com/reader036/viewer/2022072718/62e07ade68672f40900cdb81/html5/thumbnails/31.jpg)
El TLB
❑ Funcionamiento del TLB
✓ El TLB contiene la información necesaria pararealizar la traducción de algunas de las páginas delprograma: las más recientemente accedidas.
✓ Si la página que se accede está en el TLB, latraducción se hace rápida. Si no está, la traducciónse hace lenta.
P Desplazamientodentro de la página
@ lógica
Número de página
@ física
TLB
Página Trama
31
D A CCEPBA
![Page 32: CEPBA - UPC Universitat Politècnica de Catalunya](https://reader036.vdocumento.com/reader036/viewer/2022072718/62e07ade68672f40900cdb81/html5/thumbnails/32.jpg)
32
D A CCEPBA
Caches y TLB del R10000
512 conjuntos
two-way set associative
en cada línea caben 4 real*8
Cache L1
16K conjuntos
two-way set associative
en cada línea caben 16 real*8
Cache L2
TLB
64 entradas even/oddTamaño de página 2K real*8
![Page 33: CEPBA - UPC Universitat Politècnica de Catalunya](https://reader036.vdocumento.com/reader036/viewer/2022072718/62e07ade68672f40900cdb81/html5/thumbnails/33.jpg)
33
D A CCEPBA
Minimizar de Fallos de Cache y TLB
❑ Acceder a posiciones consecutivas de memoria
Mal
Linea L1
Linea L2
Página
Bien
![Page 34: CEPBA - UPC Universitat Politècnica de Catalunya](https://reader036.vdocumento.com/reader036/viewer/2022072718/62e07ade68672f40900cdb81/html5/thumbnails/34.jpg)
Minimizar Fallos de Cache y TLB
❑ Almacenamiento de matrices en Fortran
DOUBLE PRECISION A(4,3)A(1,1)
A(2,1)
A(3,1)
A(4,1)
A(1,2)
A(2,2)
A(3,2)
A(4,2)
A(1,3)
A(2,3)
A(3,3)
A(4,3)
DOUBLE PRECISION A(3,3,2)
A(1,1,1)
A(2,1,1)
A(3,1,1)
A(1,2,1)
A(2,2,1)
A(3,2,1)
A(1,3,1)
A(2,3,1)
A(3,3,1)
A(1,1,2)
A(2,1,2)
A(3,1,2)
A(1,2,2)
A(2,2,2)
A(3,2,2)
A(1,3,2)
A(2,3,2)
A(3,3,2)
34
D A CCEPBA
![Page 35: CEPBA - UPC Universitat Politècnica de Catalunya](https://reader036.vdocumento.com/reader036/viewer/2022072718/62e07ade68672f40900cdb81/html5/thumbnails/35.jpg)
Coherencia de Memoria
❑ El Problema de la Coherencia de Memoria
Red de interconexión
P1 P2 Pn...
x
x
Red de interconexión
P1 P2 Pn...
x
x x
Red de interconexión
P1 P2 Pn...
x
x x’
Red de interconexión
P1 P2 Pn...
x
x x’
(a) P1 lee X (b) P2 lee X
(c) P2 escribe X (d) P1 lee el valor obsoleto de X
35
D A CCEPBA
![Page 36: CEPBA - UPC Universitat Politècnica de Catalunya](https://reader036.vdocumento.com/reader036/viewer/2022072718/62e07ade68672f40900cdb81/html5/thumbnails/36.jpg)
36
D A CCEPBA
Coherencia de Memoria
❑ Mecanismo de invalidación
P
Cache
write (x)
x
Nodo
RED
invalidar todas lascopias de la linea L
Linea L
![Page 37: CEPBA - UPC Universitat Politècnica de Catalunya](https://reader036.vdocumento.com/reader036/viewer/2022072718/62e07ade68672f40900cdb81/html5/thumbnails/37.jpg)
37
D A CCEPBA
Coherencia de Memoria
❑ Compartición falsa
P1
Cache
write (x)
x
P2
Cache
read (x+1)
x x+1L L
invalidar linea L
![Page 38: CEPBA - UPC Universitat Politècnica de Catalunya](https://reader036.vdocumento.com/reader036/viewer/2022072718/62e07ade68672f40900cdb81/html5/thumbnails/38.jpg)
38
D A CCEPBA
![Page 39: CEPBA - UPC Universitat Politècnica de Catalunya](https://reader036.vdocumento.com/reader036/viewer/2022072718/62e07ade68672f40900cdb81/html5/thumbnails/39.jpg)
39
D A CCEPBA
EJERCICIO 1
Ejercicio 1.1
Hacer una copia de practica1.f para no perder la versión original.
Compilar el programa (sin la llamada aiterar_filas_2), con las opciones:
%f77 -O0 practica1.f -o practica1
Obtener el tiempo de ejecución correspondiente a N=6000, mediante el comando:
%time practica1
Usar el comando:
%perfex -a -y practica1
para obtener una estimación de los fallos de TLB y caches L1 y L2, y su contribución al tiempo
de ejecución.
![Page 40: CEPBA - UPC Universitat Politècnica de Catalunya](https://reader036.vdocumento.com/reader036/viewer/2022072718/62e07ade68672f40900cdb81/html5/thumbnails/40.jpg)
40
D A CCEPBA
Ejercicio 1.2
Hacer una estimación del número de fallos de TLB, L1 y L2, correspondientes a la rutina
inicializar.
Contabilizar los fallos anteriores mediante los comandos:
%ssrun -tlb_hwc practica1
%prof practica1.tlb_hwc.xxxx
para los fallos de TLB,
%ssrun -dc_hwc practica1
%prof practica1.dc_hwc.xxxx
para los fallos de L1, y
%ssrun -dsc_hwc practica1
%prof practica1.dsc_hwc.xxxx
para los fallos de L2.
![Page 41: CEPBA - UPC Universitat Politècnica de Catalunya](https://reader036.vdocumento.com/reader036/viewer/2022072718/62e07ade68672f40900cdb81/html5/thumbnails/41.jpg)
41
D A CCEPBA
Ejercicio 1.3
Reescribir las rutinasinicializar y iterar_filas para que la matriz se acceda por columnas. Res-
ponder ahora a las mismas preguntas formuladas en el ejercicio 1.1.
Ejercicio 1.4
Substituimos ahora la rutinaiterar_filas por iterar_filas_2. Hacer una estimación del número
de fallos de L1, en función de k, para N=6000. Confirmar la previsión midiendo los fallos L1
para k=4, 14, 18, 26 y 60.
![Page 42: CEPBA - UPC Universitat Politècnica de Catalunya](https://reader036.vdocumento.com/reader036/viewer/2022072718/62e07ade68672f40900cdb81/html5/thumbnails/42.jpg)
42
D A CCEPBA
Ejercicio 1.5
Modificar adecuadamente el valor de la constantefilas para evitar los autoconflictos en L1.
Medir ahora los fallos para los mismos valores de k que se ha usado en el ejercicio 1.4. Qué
ocurre si k>64?.
Ejercicio 1.6
Recuperar la versión original del programa y compilar con la opción:
%f77 -O3 practica1.f -o practica1
Tomar ahora el tiempo de ejecución. Analizar en el listado adjunto las optimizaciones realiza-
das por el compilador.
![Page 43: CEPBA - UPC Universitat Politècnica de Catalunya](https://reader036.vdocumento.com/reader036/viewer/2022072718/62e07ade68672f40900cdb81/html5/thumbnails/43.jpg)
43
D A CCEPBA
CODIGO ORIGINAL
implicit noneinteger filas, columnasparameter (filas=6400, columnas=600)
double precision matriz (filas,columnas)integer N
write *,’N ?’read *,Ncall inicializar (matriz,N)
C call iterar_filas (matriz,N)C call iterar_filas_2 (matriz,N)
write *,matriz (3,3)end
subroutine inicializar (matriz,N)integer filas, columnasparameter (filas=6000, columnas=800)double precision matriz (filas , columnas)integer N
integer i,jdo i=1,N
do j=1, columnasmatriz (i,j) = i*0.8 + j*2.4
enddoenddoend
subroutine iterar_filas (matriz,N)implicit noneinteger filas, columnasparameter (filas=6000, columnas=800)double precision matriz (filas,columnas)integer N
integer i,j,iter
do iter=1,10do i=1,N
do j=2, columnas-1matriz (i,j) = 0.3*(matriz(i,j)+matriz(i,j+1) + matriz (i,j-1))
enddoenddo
enddoend
![Page 44: CEPBA - UPC Universitat Politècnica de Catalunya](https://reader036.vdocumento.com/reader036/viewer/2022072718/62e07ade68672f40900cdb81/html5/thumbnails/44.jpg)
44
D A CCEPBA
subroutine iterar_filas_2 (matriz,N)implicit noneinteger filas, columnasparameter (filas=6000, columnas=800)double precision matriz (filas,columnas)integer N
integer i,j,iter,jj,k
k = 60do iter=1,10
do jj=2, columnas-1,kdo i=1,N
do j=jj, min(jj+K-1,columnas-1)matriz (i,j) = 0.3*(matriz(i,j)+matriz(i,j+1) + matriz (i,j-1)) enddo
enddoenddo
enddoend
![Page 45: CEPBA - UPC Universitat Politècnica de Catalunya](https://reader036.vdocumento.com/reader036/viewer/2022072718/62e07ade68672f40900cdb81/html5/thumbnails/45.jpg)
45
D A
CC
EP
BA
SUBROUTINE inicializar(matriz, N)POINTER(se1_F4, deref_se1_F4)C
DO tile2i = 1, N, 495 se1__$stk = INTRN_U4READSTACKPOINTER() se1_F4 = ALLOCA(((MIN((tile2i + 494), N) -(tile2i + -1)) * 4)) DO i = tile2i, MIN((tile2i + 494), N), 1 deref_se1_F4((i - tile2i) + 1) = (REAL(i) * 8.0000001192E-01) END DO DO j0 = 1, 800, 1 matriz_1 = (REAL(j0) * 2.4000000954) DO i0 = tile2i, MIN((tile2i + 494), N), 1 matriz(i0, j0) = DBLE((deref_se1_F4((i0 - tile2i) + 1) + matriz_1)) END DO END DO tmp0 = INTRN_U4I4SETSTACKPOINTER(se1__$stk)END DORETURN
![Page 46: CEPBA - UPC Universitat Politècnica de Catalunya](https://reader036.vdocumento.com/reader036/viewer/2022072718/62e07ade68672f40900cdb81/html5/thumbnails/46.jpg)
46
D A
CC
EP
BA
SUBROUTINE iterar_filas(matriz, N)DO iter = 1, 10, 1 DO tile2i = 1, N, 1200 DO j = 2, 790, 10 DO i = tile2i, MIN((tile2i + 1199), N), 1 matriz(i, j) = (((matriz(i, j + -1) +(matriz(i, j) + matriz(i, j + 1)))) * 2.9999999999999999D-01) matriz(i, j + 1) = (((matriz(i, j) +(matriz(i, j + 2) + matriz(i, j + 1)))) * 2.9999999999999999D-01) matriz(i, j + 2) = (((matriz(i, j + 1) +(matriz(i, j + 2) + matriz(i, j + 3)))) * 2.9999999999999999D-01) matriz(i, j + 3) = (((matriz(i, j + 2) +(matriz(i, j + 3) + matriz(i, j + 4)))) * 2.9999999999999999D-01) matriz(i, j + 4) = (((matriz(i, j + 3) +(matriz(i, j + 4) + matriz(i, j + 5)))) * 2.9999999999999999D-01) matriz(i, j + 5) = (((matriz(i, j + 4) +(matriz(i, j + 5) + matriz(i, j + 6)))) * 2.9999999999999999D-01) matriz(i, j + 6) = (((matriz(i, j + 5) +(matriz(i, j + 6) + matriz(i, j + 7)))) * 2.9999999999999999D-01) matriz(i, j + 7) = (((matriz(i, j + 6) +(matriz(i, j + 7) + matriz(i, j + 8)))) * 2.9999999999999999D-01) matriz(i, j + 8) = (((matriz(i, j + 7) +(matriz(i, j + 8) + matriz(i, j + 9)))) * 2.9999999999999999D-01) matriz(i, j + 9) = (((matriz(i, j + 8) +(matriz(i, j + 9) + matriz(i, j + 10)))) * 2.9999999999999999D-01) END DO END DO DO wd_j = 792, 799, 2 DO i0 = tile2i, MIN((tile2i + 1199), N), 1 matriz(i0, wd_j) = (((matriz(i0, wd_j + -1) +(matriz(i0, wd_j) + matriz(i0, wd_j + 1)))) * 2.9999999999999999D-01)
matriz(i0, wd_j + 1) = (((matriz(i0, wd_j) +(matriz(i0, wd_j + 2) + matriz(i0, wd_j + 1)))) * 2.9999999999999999D-01) END DO END DO END DOEND DORETURNEND ! iterar_filas
![Page 47: CEPBA - UPC Universitat Politècnica de Catalunya](https://reader036.vdocumento.com/reader036/viewer/2022072718/62e07ade68672f40900cdb81/html5/thumbnails/47.jpg)
47
D A CCEPBA
Programación Eficienteen el Origin 2000
❑ Modelo de Programación
❑ Objetivos del Diseño de Algoritmos
❑ Fuentes de Ineficiencia
✓ Operaciones aritméticas innecesarias
✓ Accesos a memoria
✓ Fracción serie
✓ Sobrecarga de paralelización
✓ Desequilibrio de carga
✓ Sobrecarga de sincronización
![Page 48: CEPBA - UPC Universitat Politècnica de Catalunya](https://reader036.vdocumento.com/reader036/viewer/2022072718/62e07ade68672f40900cdb81/html5/thumbnails/48.jpg)
48
D A CCEPBA
Modelo de Programación
❑ Fortran 77 + directivas para:✓ Identificar bucles paralelos✓ Sincronizar iteraciones no paralelas✓ Asignar iteraciones paralelas a procesadores
(planificación)
DO I=1,N
V(I) = W(I) + V(I-1)
ENDDO
DO I=1,M
X = D(I)**2
Y = X+X
DO J=I, ITOP
A(I,J) = B(I,J)*C(I,J)*X+Y
ENDDO
ENDDO
DO I=1,N
tmp = W(I) + V(I)*A(I,4)
TOTAL = TOTAL + tmp
ENDDO
C$DOACROSS LOCAL (I,J,X,Y) MP_SCHEDTYPE = INTERLEAVED
Identificación de bucle paralelo
Planificación
C$DOACROSS LOCAL (I,tmp) REDUCTION (TOTAL)
Sincronización para iteracionesno paralelas
![Page 49: CEPBA - UPC Universitat Politècnica de Catalunya](https://reader036.vdocumento.com/reader036/viewer/2022072718/62e07ade68672f40900cdb81/html5/thumbnails/49.jpg)
49
D A CCEPBA
Modelo de Programación
❑ Bucles paralelos✓ Las iteraciones pueden ejecutarse en cualquier
orden sin que varie el resultado final
✓ Las iteraciones escriben sobre posicionesdiferentes de memoria
DO I=1,N
V(I) = W(I) + V(I-1)
ENDDO
V(1) = W(1) + V(0)
V(2) = W(2) + V(1)
V(3) = W(3) + V(2)
.
.
V(k) = W(k) + V(k-1)
V(k+1) = W(k+1) + V(k)
.
Iteraciones dependientes(no paralelas)
![Page 50: CEPBA - UPC Universitat Politècnica de Catalunya](https://reader036.vdocumento.com/reader036/viewer/2022072718/62e07ade68672f40900cdb81/html5/thumbnails/50.jpg)
Modelo de Programación
❑ Bucles paralelos
DO I=1,M
X = D(I)**2
Y = X+X
DO J=I, ITOP
A(I,J) = B(I,J)*C(I,J)*X+Y
ENDDO
ENDDO
X = D(k)**2
Y = X+X
DO J=I, ITOP
A(k,J) = B(k,J)*C(k,J)*X+Y
ENDDO
X = D(k+1)**2
Y = X+X
DO J=I, ITOP
A(k+1,J) = B(k+1,J)*C(k+1,J)*X+Y
ENDDO
Iteraciones independientes(paralelas)
variables locales I,J, X e Y
DO I=1,M
X = D(I)**2
Y = X+X
DO J=I, ITOP
A(I,J) = B(I,J)*C(I,J)*X+Y
ENDDO
ENDDO
C$DOACROSS LOCAL (I,J,X,Y)
50
D A CCEPBA
![Page 51: CEPBA - UPC Universitat Politècnica de Catalunya](https://reader036.vdocumento.com/reader036/viewer/2022072718/62e07ade68672f40900cdb81/html5/thumbnails/51.jpg)
51
D A CCEPBA
Modelo de Programación
❑ Bucles “casi” paralelos
DO I=1,N
tmp = W(I) + V(I)*A(I,4)
TOTAL = TOTAL + tmp
ENDDO
DO I=1,N
tmp = W(I) + V(I)*A(I,4)
TOTAL = TOTAL + tmp
ENDDO
tmp = W(1) + V(1)*A(1,4)
TOTAL = TOTAL + tmp
tmp = W(2) + V(2)*A(2,4)
TOTAL = TOTAL + tmp
tmp = W(3) + V(3)*A(3,4)
TOTAL = TOTAL + tmp
tmp = W(4) + V(4)*A(4,4)
TOTAL = TOTAL + tmp
TOTAL
Iteraciones “casi independientes”(sincronización para acceso excluyente)
C$DOACROSS LOCAL (I,tmp) REDUCTION (TOTAL)
variables locales I,tmp
sincronización parareducción sobre TOTAL
![Page 52: CEPBA - UPC Universitat Politècnica de Catalunya](https://reader036.vdocumento.com/reader036/viewer/2022072718/62e07ade68672f40900cdb81/html5/thumbnails/52.jpg)
Modelo de Programación
❑ Planificación de bucles
1 MInteraciones del bucle I
Procesadores
DO I=1,M
X = D(I)**2
Y = X+X
DO J=I, ITOP
A(I,J) = B(I,J)*C(I,J)*X+Y
ENDDO
ENDDO
2
Número de operacionesen cada iteración
Planificación(INTERLEAVED)
C$DOACROSS LOCAL (I,J,X,Y) MP_SCHEDTYPE = INTERLEAVED
52
D A CCEPBA
![Page 53: CEPBA - UPC Universitat Politècnica de Catalunya](https://reader036.vdocumento.com/reader036/viewer/2022072718/62e07ade68672f40900cdb81/html5/thumbnails/53.jpg)
Objetivos del Diseño de Algoritmos Paralelos
❑ Ineficiencias en los algoritmos paralelos
❑ Objetivo en el diseño de algoritmos paralelos✓ Minimizar las ineficiencias
❑ Fuentes de ineficiencia✓ Operaciones aritméticas innecesarias✓ Accesos a los datos✓ Fracción serie✓ Sobrecarga de paralelización✓ Desequilibrio de carga✓ Sobrecarga de sincronización
Tp
W tc×p
--------------- O p( )+=
Tiempo usandop procesadores
Número mínimo de operaciones
Ineficiencias
aritméticas
Tiempo de una operación aritmética
53
D A CCEPBA
![Page 54: CEPBA - UPC Universitat Politècnica de Catalunya](https://reader036.vdocumento.com/reader036/viewer/2022072718/62e07ade68672f40900cdb81/html5/thumbnails/54.jpg)
Fuentes de Ineficiencia
❑ Operaciones aritméticas innecesarias
✓ La mejora representa una reducción del 66% en eltiempo de ejecución
SIGVMMX=0.0IX=5A = 1E-3/PTH(IX)B= 6*(PTH(IX)/10.)/(PTH(IX)**3)DO I=-5,5 SIG1=A*FORCE(1)+2*FORCE(4)*I*B SIG2=A*FORCE(2)+2*FORCE(5)*I*B SIG12=A*FORCE(3)+FORCE(6)*I*B
SIG13=6E-3*FORCE(7)*(1-(I/5.)**2)/4/PTH(IX) SIG23=6E-3*FORCE(8)*(1-(I/5.)**2)/4/PTH(IX)SIG_VM=SIG1**2+SIG2**2+(SIG1-SIG2)**2+6*(SIG12+SIG13+SIG23)**2IF (SIG_VM.GT.SIGVMMX) SIGVMMX=SIG_VM
END DOSM1=FTY(IX)/1.1/(SQRT(SIGVMMX)/SQRT(2.))-1.
SIGVMMX=-1.E20IX=5DO I=-5,5
SIG1(I+6)=1E-3*FORCE(1)/PTH(IX)+12*FORCE(4)*(I*PTH(IX)/10.)(PTH(IX)**3)SIG2(I+6)=1E-3*FORCE(2)/PTH(IX)+12*FORCE(5)*(I*PTH(IX)/10.)/(PTH(IX)**3)SIG12(I+6)=1E-3*FORCE(3)/PTH(IX)+6*FORCE(6)*(I*PTH(IX)/10.)/(PTH(IX)**3)SIG13(I+6)=6E-3*FORCE(7)*(1-(I/5.)**2)/4/PTH(IX)SIG23(I+6)=6E-3*FORCE(8)*(1-(I/5.)**2)/4/PTH(IX)SIG_VM(I+6)=SQRT(SIG1(I+6)**2+SIG2(I+6)**2+(SIG1(I+6)-
SIG2(I+6))**2+6*(SIG12(I+6)+SIG13(I+6)+SIG23(I+6))**2)/SQRT(2.)IF (SIG_VM(I+6).GT.SIGVMMX) SIGVMMX=SIG_VM(I+6)
END DOSM1=FTY(IX)/1.1/SIGVMMX-1.
Código original
Código mejorado
54
D A CCEPBA
![Page 55: CEPBA - UPC Universitat Politècnica de Catalunya](https://reader036.vdocumento.com/reader036/viewer/2022072718/62e07ade68672f40900cdb81/html5/thumbnails/55.jpg)
55
D A CCEPBA
Fuentes de Ineficiencia
❑ Accesos a memoriaCódigos de ejemplo
REAL*8 A
DIMENSION A (2000,2000)
DO I=1, N
DO J=1,N
A(I,J) = I*0.8+J*1.3
ENDDO
ENDDO
REAL*8 A
DIMENSION A (2000,2000)
DO J=1, N
DO I=1,N
A(I,J) = I*0.8+J*1.3
ENDDO
ENDDO
Código 1 Código 2(acceso por filas) (acceso por columnas)
![Page 56: CEPBA - UPC Universitat Politècnica de Catalunya](https://reader036.vdocumento.com/reader036/viewer/2022072718/62e07ade68672f40900cdb81/html5/thumbnails/56.jpg)
56
D A CCEPBA
Fuentes de Ineficiencia
❑ Accesos a memoriaMedidas
Código 1N=1000
Código 2N=1000
Código 1N=2000
Código 2N=2000
tiempo
TLB
L1
L2
![Page 57: CEPBA - UPC Universitat Politècnica de Catalunya](https://reader036.vdocumento.com/reader036/viewer/2022072718/62e07ade68672f40900cdb81/html5/thumbnails/57.jpg)
57
D A CCEPBA
Fuentes de Ineficiencia
❑ Accesos a memoriaConclusión
ObservaciónEn ocaciones, el compilador hace las transformaciones de códigonecesarias para optimizar accesos (por ejemplo, intercambio debucles).
Acceder a las matrices según la LEADING DIMENSION:
DIMENSION MATRIZ (dim1, dim2, ...., dimN)
Leading dimension (en FORTRAN)
![Page 58: CEPBA - UPC Universitat Politècnica de Catalunya](https://reader036.vdocumento.com/reader036/viewer/2022072718/62e07ade68672f40900cdb81/html5/thumbnails/58.jpg)
58
D A CCEPBA
Fuentes de Ineficiencia
❑ Fracción serieEjecución serie Ejecución paralela
Fracción serie (Ws)
Fracción paralela (Wp)
W = Ws + Wp
Tp
Wp tc×p
------------------ Ws tc×+=
1 + Wp/Ws
T1/Tp
P
Ley de Amdahl
![Page 59: CEPBA - UPC Universitat Politècnica de Catalunya](https://reader036.vdocumento.com/reader036/viewer/2022072718/62e07ade68672f40900cdb81/html5/thumbnails/59.jpg)
59
D A CCEPBA
Fuentes de Ineficiencia
❑ Fracción serieConclusión
Optimizar TODAS las secciones del programa que consumanuna fracción importante del tiempo de ejecución
“Olvidarse” de las secciones que consumen una fracciónpequeña del tiempo de ejecución
![Page 60: CEPBA - UPC Universitat Politècnica de Catalunya](https://reader036.vdocumento.com/reader036/viewer/2022072718/62e07ade68672f40900cdb81/html5/thumbnails/60.jpg)
60
D A CCEPBA
Fuentes de Ineficiencia
❑ Sobrecarga de paralelización
Ejecución serie Ejecución paralela
Fracción serie
Iteraciones paralelas
Sobrecarga deparalelización
![Page 61: CEPBA - UPC Universitat Politècnica de Catalunya](https://reader036.vdocumento.com/reader036/viewer/2022072718/62e07ade68672f40900cdb81/html5/thumbnails/61.jpg)
61
D A CCEPBA
Fuentes de Ineficiencia
❑ Sobrecarga de paralelizaciónCódigo de ejemplo
Tiempos de ejecución
DO J=1, N
DO K=1,N
C$DOACROSS LOCAL (I)
DO I = 1, N
C(I,J) = C(I,J)+A(I,K)+(B(K,J)
ENDDO
ENDDO
ENDDO
C$DOACROSS LOCAL (J,K,I)
DO J=1, N
DO K=1,N
DO I = 1, N
C(I,J) = C(I,J)+A(I,K)+(B(K,J)
ENDDO
ENDDO
ENDDO
Código 1 Código 2
N=500 N=700 N=900
Código 1, P=1 2.81s 9.29s 30.13s
Código 1, P=4 5.64s 11.44s 20.15s
Código 2, P=1 1.14s 3.13s 6.66s
Código 2, P=4 0.60s 1.13s 1.87s
Por qué sondiferentes?
Sobrecarga deparalelización≈ 1.5 × 10−5s
![Page 62: CEPBA - UPC Universitat Politècnica de Catalunya](https://reader036.vdocumento.com/reader036/viewer/2022072718/62e07ade68672f40900cdb81/html5/thumbnails/62.jpg)
62
D A CCEPBA
Fuentes de Ineficiencia
❑ Sobrecarga de paralelizaciónConclusión
ObservaciónLa técnica del intercambio de bucles puede permitir trasladar el bucleparalelo más adecuado al nivel más externo de la anidación
No paralelizar bucles con poco trabajo (menos de 1000operaciones)
En bucles anidados, paralelizar bucles externos
![Page 63: CEPBA - UPC Universitat Politècnica de Catalunya](https://reader036.vdocumento.com/reader036/viewer/2022072718/62e07ade68672f40900cdb81/html5/thumbnails/63.jpg)
63
D A CCEPBA
Fuentes de Ineficiencia
❑ Desequilibrio de carga
Ejecución serie Ejecución paralela
Fracción serie
Iteraciones paralelas
![Page 64: CEPBA - UPC Universitat Politècnica de Catalunya](https://reader036.vdocumento.com/reader036/viewer/2022072718/62e07ade68672f40900cdb81/html5/thumbnails/64.jpg)
64
D A CCEPBA
Fuentes de Ineficiencia
❑ Desequilibrio de cargaNúmero de iteraciones del bucle paralelizado no múltiplo del númerode procesadores
Ejemplo
Ejecución serie: 5 × 1s = 5s
Ejecución óptima con 4 procesadores : 5s/4 = 1.25s
Paralelización del bucle I con 4 procesadores:
Paralelización del bucle J con 4 procesadores:
DO I=1, 5
DO J=1,100
Work
ENDDO
ENDDO
DO J=1,1000
Work
ENDDO
Bucles paralelos y NO intercambiables
Cada iteración del bucle Itarda 1s.
1.5 105–s× 5
4--- 1s+ 2s≈
5 1.5 105–s× 1s
4-----+
× 1.25s≈
![Page 65: CEPBA - UPC Universitat Politècnica de Catalunya](https://reader036.vdocumento.com/reader036/viewer/2022072718/62e07ade68672f40900cdb81/html5/thumbnails/65.jpg)
65
D A CCEPBA
Fuentes de Ineficiencia
❑ Desequilibrio de cargaMala distribución de las iteraciones paralelas entre los procesadores
1 MInteraciones paralelas
Procesadores
2
Número de operacionesen cada iteración
![Page 66: CEPBA - UPC Universitat Politècnica de Catalunya](https://reader036.vdocumento.com/reader036/viewer/2022072718/62e07ade68672f40900cdb81/html5/thumbnails/66.jpg)
66
D A CCEPBA
Fuentes de Ineficiencia
❑ Desequilibrio de cargaDirectivas para planificación de bucles: SIMPLE
✓ Es la opción por omisión✓ Es la opción adecuada cuando el coste de cada
iteración es constante✓ Tiene poca sobrecarga de planificación (tiempo
empleado por el procesador para identificar eltrabajo que le ha sido asignado)
C$DOACROSS LOCAL (i) MP_SCHEDTYPE =SIMPLEDO i=1,N
trabajo (i)ENDDO
N1
Procesadores
Sobrecarga deplanificación
Sobrecarga deparalelización
![Page 67: CEPBA - UPC Universitat Politècnica de Catalunya](https://reader036.vdocumento.com/reader036/viewer/2022072718/62e07ade68672f40900cdb81/html5/thumbnails/67.jpg)
67
D A CCEPBA
Fuentes de Ineficiencia
❑ Desequilibrio de cargaDirectivas para planificación de bucles; INTERLEAVED
✓ Es la opción adecuada cuando el coste de cadaiteración es creciente o decreciente
✓ Tiene poca sobrecarga de planificación (igual queen la opción SIMPLE)
Procesadores
C$DOACROSS LOCAL (i) MP_SCHEDTYPE = INTERLEAVEDDO i=1,N
trabajo (i)ENDDO
N1
![Page 68: CEPBA - UPC Universitat Politècnica de Catalunya](https://reader036.vdocumento.com/reader036/viewer/2022072718/62e07ade68672f40900cdb81/html5/thumbnails/68.jpg)
Fuentes de Ineficiencia
❑ Desequilibrio de cargaDirectivas para planificación de bucles: DYNAMIC
✓ Es la opción adecuada cuando el coste de cadaiteración es imprevisible
✓ Tiene alta sobrecarga de planificación
C$DOACROSS LOCAL (i) MP_SCHEDTYPE =DYNAMICDO i=1,N
trabajo (i)ENDDO
N1
Procesadores
Sobrecarga deplanificación
Sobrecarga deparalelización
68
D A CCEPBA
![Page 69: CEPBA - UPC Universitat Politècnica de Catalunya](https://reader036.vdocumento.com/reader036/viewer/2022072718/62e07ade68672f40900cdb81/html5/thumbnails/69.jpg)
Fuentes de Ineficiencia
❑ Desequilibrio de cargaDirectivas para planificación de bucles: GSS
✓ Adecuada cuando el coste de cada iteración esimprevisible
✓ Permite un compromiso entre equilibrio de carga(mejor que SIMPLE o INTERLEAVED) y sobrecargade planificación (mejor que DYNAMIC)
C$DOACROSS LOCAL (i) MP_SCHEDTYPE =GSSDO i=1,N
trabajo (i)ENDDO
N1
Procesadores
Sobrecarga deplanificación
Sobrecarga deparalelización
69
D A CCEPBA
![Page 70: CEPBA - UPC Universitat Politècnica de Catalunya](https://reader036.vdocumento.com/reader036/viewer/2022072718/62e07ade68672f40900cdb81/html5/thumbnails/70.jpg)
70
D A CCEPBA
Fuentes de Ineficiencia
❑ Desequilibrio de cargaCódigos de ejemplo
✓ El bucle J es paralelo✓ El coste las iteraciones del bucle J es creciente
C$DOACROSS LOCAL(J,ITOP,I,K,MAX,TMP)
C$& MP_SCHEDTYPE= SIMPLE / INTERLEAVED
DO J=1,N
ITOP = (N+J)/2
DO I=1, ITOP
MAX = I
DO K=I+1, ITOP
IF (MATRIZ (K,J) .GT. MATRIZ (MAX,J)) THEN
MAX = K
ENDIF
ENDDO
TMP = MATRIZ (I,J)
MATRIZ (I,J) = MATRIZ (MAX,J)
MATRIZ (MAX,J) = TMP
ENDDO
ENDDO
Bucle J
Ordenar cadauna de las columnas
![Page 71: CEPBA - UPC Universitat Politècnica de Catalunya](https://reader036.vdocumento.com/reader036/viewer/2022072718/62e07ade68672f40900cdb81/html5/thumbnails/71.jpg)
71
D A CCEPBA
Fuentes de Ineficiencia
❑ Desequilibrio de cargaResultados para N=1000
P
Velocidad (T1/TP)
INTERLEAVED
SIMPLE
![Page 72: CEPBA - UPC Universitat Politècnica de Catalunya](https://reader036.vdocumento.com/reader036/viewer/2022072718/62e07ade68672f40900cdb81/html5/thumbnails/72.jpg)
72
D A CCEPBA
Fuentes de Ineficiencia
❑ Desequilibrio de cargaHerramienta par tomar medidas
% ssrun -pcsamp programa
Genera un fichero programa.pcsamp.xxxx por cada procesadorinvolucrado.
% prof programa.pcsamp.xxxx
Muestra el tiempo de ejecución empleado en cada rutina, por elprocesador correspondiente al fichero programa.pcsamp.xxxx
![Page 73: CEPBA - UPC Universitat Politècnica de Catalunya](https://reader036.vdocumento.com/reader036/viewer/2022072718/62e07ade68672f40900cdb81/html5/thumbnails/73.jpg)
73
D A CCEPBA
Fuentes de Ineficiencia
❑ Desequilibrio de cargaMedidas para N=1000 y P=4
1.8
2.8
3.8
5.1
tiempo
1 2 3 4
SIMPLE
3.4
1 2 3 4
INTERLEAVED
3.4 3.4 3.4
![Page 74: CEPBA - UPC Universitat Politècnica de Catalunya](https://reader036.vdocumento.com/reader036/viewer/2022072718/62e07ade68672f40900cdb81/html5/thumbnails/74.jpg)
74
D A CCEPBA
Fuentes de Ineficiencia
❑ Desequilibrio de cargaCódigos de ejemplo
C$DOACROSS LOCAL(J,ITOP,I,K,MAX,TMP)
C$& MP_SCHEDTYPE= SIMPLE / INTERLEAVED/DYNAMIC
DO J=1,N
DO I=1, ITOP (J)
MAX = I
DO K=I+1, ITOP (J)
IF (MATRIZ (K,J) .GT. MATRIZ (MAX,J)) THEN
MAX = K
ENDIF
ENDDO
TMP = MATRIZ (I,J)
MATRIZ (I,J) = MATRIZ (MAX,J)
MATRIZ (MAX,J) = TMP
ENDDO
ENDDO
Bucle J
ITOP (J)
Una de cada 4 iteracionesno hace nada
![Page 75: CEPBA - UPC Universitat Politècnica de Catalunya](https://reader036.vdocumento.com/reader036/viewer/2022072718/62e07ade68672f40900cdb81/html5/thumbnails/75.jpg)
75
D A CCEPBA
Fuentes de Ineficiencia
❑ Desequilibrio de cargaResultados para N=1000, P=4
1.4
2.1
2.9
3.7
1 2 3 4
SIMPLE
3.4
1 2 3 4
INTERLEAVED
3.4 3.4
2.6
1 2 3 4
DYNAMIC
2.6 2.6 2.6
![Page 76: CEPBA - UPC Universitat Politècnica de Catalunya](https://reader036.vdocumento.com/reader036/viewer/2022072718/62e07ade68672f40900cdb81/html5/thumbnails/76.jpg)
76
D A CCEPBA
Fuentes de Ineficiencia
❑ Desequilibrio de cargaCódigos de ejemplo
C$DOACROSS LOCAL (I,K) MP_SCHEDTYPE = DYNAMIC / GSS
DO I=1, N
IF ((I .GE. N/4) .AND. ( MOD (I,4) .NE. 0)) THEN
DO K = 1, 10000
A(I) = B(I) + C(I) + A(I)
ENDDO
ENDIF
ENDDO
Bucle I
![Page 77: CEPBA - UPC Universitat Politècnica de Catalunya](https://reader036.vdocumento.com/reader036/viewer/2022072718/62e07ade68672f40900cdb81/html5/thumbnails/77.jpg)
77
D A CCEPBA
Fuentes de Ineficiencia
❑ Desequilibrio de cargaResultados para N=1000000
P
Velocidad (T1/TP)
GSS
DYNAMIC
![Page 78: CEPBA - UPC Universitat Politècnica de Catalunya](https://reader036.vdocumento.com/reader036/viewer/2022072718/62e07ade68672f40900cdb81/html5/thumbnails/78.jpg)
78
D A CCEPBA
Fuentes de Ineficiencia
❑ Desequilibrio de cargaConclusión
Utilizar la estrategia de planificación adecuada:
Coste de iteración constante: SIMPLE
Coste de iteración (de)creciente: INTERLEAVED
Coste de iteración imprevisible ypocas iteraciones: DYNAMIC
Coste de iteración imprevisible ymuchas iteraciones: GSS
Evitar paralelizar bucles con un número pequeño de iteracionesno divisible por el número de procesadores.
![Page 79: CEPBA - UPC Universitat Politècnica de Catalunya](https://reader036.vdocumento.com/reader036/viewer/2022072718/62e07ade68672f40900cdb81/html5/thumbnails/79.jpg)
79
D A CCEPBA
Fuentes de Ineficiencia
❑ Accesos a memoria: compartición falsaEjemplo
Mecanismo para medir invalidaciones externas
% perfex -e 13 programa
N
Ordenar cada una de las filasMisma linea L1
Misma linea L2
![Page 80: CEPBA - UPC Universitat Politècnica de Catalunya](https://reader036.vdocumento.com/reader036/viewer/2022072718/62e07ade68672f40900cdb81/html5/thumbnails/80.jpg)
80
D A CCEPBA
Fuentes de Ineficiencia
❑ Accesos a memoria: compartición falsaCódigo
C$DOACROSS LOCAL(J,ITOP,I,K,TMP)
C$& MP_SCHEDTYPE= SIMPLE / INTERLEAVED
DO I=1,N
DO J=1, ITOP (I)
DO K=J+1, ITOP (I)
IF (MATRIZ (I,K) .GT. MATRIZ (I,J)) THEN
TMP = MATRIZ (I,J)
MATRIZ (I,J) = MATRIZ (I,K)
MATRIZ (I,K) = TMP
ENDIF
ENDDO
ENDDO
ENDDO
![Page 81: CEPBA - UPC Universitat Politècnica de Catalunya](https://reader036.vdocumento.com/reader036/viewer/2022072718/62e07ade68672f40900cdb81/html5/thumbnails/81.jpg)
81
D A CCEPBA
Fuentes de Ineficiencia
❑ Accesos a memoria: compartición falsaResultados para N=1000 y P=4
Mecanismo para mitigar la compartición falsa
C$DOACROSS MP_SCHEDTYPE = INTERLEAVED CHUNK=16
Resultados para N=1000 y P=4
Fallos L2 Tiempo
Secuencial 87000 48 s
SIMPLE, P=4 79000 19 s
INTERLEAVED, P=4 75 M 71 s
Fallos L2 Tiempo
INTERLEAVED CHUNK=16, P=4 21 M 33 s
INTERLEAVED CHUNK=30, P=4 9 M 18 s
INTERLEAVED CHUNK=40, P=4 2.7 M 14 s
INTERLEAVED CHUNK=50, P=4 800000 14 s
![Page 82: CEPBA - UPC Universitat Politècnica de Catalunya](https://reader036.vdocumento.com/reader036/viewer/2022072718/62e07ade68672f40900cdb81/html5/thumbnails/82.jpg)
82
D A CCEPBA
Fuentes de Ineficiencia
❑ Accesos a memoria: compartición falsaCon frecuencia, la compartición falsa puede reducirse reorgani-zando en código y/o las estructuras de datos
C$DOACROSS LOCAL(J,ITOP,I,K,TMP,MAX)
C$& MP_SCHEDTYPE= SIMPLE / INTERLEAVED
DO I=1,N
DO J=1, ITOP (I)
MAX = J
TMP = MATRIZ (I,J)
DO K=J+1, ITOP (I)
IF (MATRIZ (I,K) .GT. TMP) THEN
TMP = MATRIZ (I,K)
MAX = K
ENDIF
ENDDO
TMP = MATRIZ (I,J)
MATRIZ (I,J) = MATRIZ (I,K)
MATRIZ (I,K) = TMP
ENDDO
ENDDO
![Page 83: CEPBA - UPC Universitat Politècnica de Catalunya](https://reader036.vdocumento.com/reader036/viewer/2022072718/62e07ade68672f40900cdb81/html5/thumbnails/83.jpg)
83
D A CCEPBA
Fuentes de Ineficiencia
❑ Accesos a memoria: compartición falsaResultados para N=1000 y P=4
Fallos L2 Tiempo
INTERLEAVED CHUNK=16, P=4 350000 13 s
INTERLEAVED CHUNK=50, P=4 159000 14 s
INTERLEAVED CHUNK=4, P=4 1.5 M 15 s
![Page 84: CEPBA - UPC Universitat Politècnica de Catalunya](https://reader036.vdocumento.com/reader036/viewer/2022072718/62e07ade68672f40900cdb81/html5/thumbnails/84.jpg)
84
D A CCEPBA
Fuentes de Ineficiencia
❑ Accesos a memoria: compartición falsaConclusión
En caso de compartición falsa:
Utilizar CHUNK con las estrategias INTERLEAVED y DYNAMIC
Reorganizar código y/o estructuras de datos
![Page 85: CEPBA - UPC Universitat Politècnica de Catalunya](https://reader036.vdocumento.com/reader036/viewer/2022072718/62e07ade68672f40900cdb81/html5/thumbnails/85.jpg)
85
D A CCEPBA
Fuentes de Ineficiencia
❑ Sobrecarga de sincronizaciónCódigo ejemplo
C$DOACROSS LOCAL(J,ITOP,I,K,M,TMP)
C$& REDUCTION (MAXIMO)
C$& MP_SCHEDTYPE= INTERLEAVED
DO J=1,N
ITOP = (N+J)/2
DO I=1, ITOP
M = I
DO K=I+1, ITOP
IF (MATRIZ (K,J) .GT. MATRIZ (M,J)) THEN
M = K
ENDIF
ENDDO
TMP = MATRIZ (I,J)
MATRIZ (I,J) = MATRIZ (M,J)
MATRIZ (M,J) = TMP
ENDDO
MAXIMO = MAX (MAXIMO, MATRIZ (1,J))
ENDDO
Bucle J
Ordenar cadauna de las columnas
![Page 86: CEPBA - UPC Universitat Politècnica de Catalunya](https://reader036.vdocumento.com/reader036/viewer/2022072718/62e07ade68672f40900cdb81/html5/thumbnails/86.jpg)
86
D A CCEPBA
Fuentes de Ineficiencia
❑ Sobrecarga de sincronizaciónResultados
✓ No se aprecia una diferencia significativa en tiempode ejecución con respecto al código que no calculael máximo total (baja sobrecarga de sincronización)
Uso de la directiva REDUCTION
Puede usarse con las siguientes operaciones:
✓ SUMA✓ PRODUCTO✓ MINIMO✓ MAXIMO
![Page 87: CEPBA - UPC Universitat Politècnica de Catalunya](https://reader036.vdocumento.com/reader036/viewer/2022072718/62e07ade68672f40900cdb81/html5/thumbnails/87.jpg)
87
D A CCEPBA
EJERCICIO 2
Ejercicio 2.1
Compilar el programapractica2.f, con las opciones:
%f77 -O3 practica2.f -o practica12
Usando las herramientas adecuadas, medir el tiempo empleado en cada una de las rutinas y
hacer un diagnóstico de posibles ineficiencas debidas a fallos de TLB y caches.
Ejercicio 2.2
Hacer las modificaciones de código y estructuras de datos necesarias para resolver los proble-
mas detectados en el ejercicio 2.1.
![Page 88: CEPBA - UPC Universitat Politècnica de Catalunya](https://reader036.vdocumento.com/reader036/viewer/2022072718/62e07ade68672f40900cdb81/html5/thumbnails/88.jpg)
88
D A CCEPBA
Ejercicio 2.3
Poner el valor 500 a la constanteNiter de las rutinasmodif1 y modif2.
Insertar la directiva apropiada para paralelizar la rutinamodif1. Compilar el código con el
comando:
%f77 -O3 -mp practica2.f -o practica12
Analizar el equilibrio de carga y la sobrecarga de planificación de la solución propuesta.
Ejercicio 2.4
Insertar la directiva apropiada para paralelizar la rutinamodif2. Analizar el equilibrio de carga
y la sobrecarga de planificación de la solución propuesta.
Ejercicio 2.5
Insertar la directiva apropiada para paralelizar la rutinasumar. Analizar el equilibrio de carga y
la sobrecarga de planificación de la solución propuesta.
![Page 89: CEPBA - UPC Universitat Politècnica de Catalunya](https://reader036.vdocumento.com/reader036/viewer/2022072718/62e07ade68672f40900cdb81/html5/thumbnails/89.jpg)
89
D A CCEPBA
CODIGO ORIGINAL
implicit none
integer maxelem, maxi, maxjparameter (maxelem = 15000, maxi = 16, maxj = 16)
real*8 estdimension est (maxelem,maxi,maxj)integer tipeldimension tipel (maxelem)real*8 suma
integer k
call leer (est,tipel)write *, ‘fin leer’call modif1 (est)write *, ‘fin modif1’call modif2 (est,tipel)write *, ‘fin modif2’call sumar (est,tipel,suma)write *, ‘fin modif2’write *, sumaend
real*8 function elemento (el,i,j)integer el,i,jelemento = el*(i-j)/1000.0end
integer function tipo (el)integer elinteger kk = int(el/1900)if ((k .eq. 0) .OR. (k .eq. 2)) then
tipo= 0else
tipo = kendifend
![Page 90: CEPBA - UPC Universitat Politècnica de Catalunya](https://reader036.vdocumento.com/reader036/viewer/2022072718/62e07ade68672f40900cdb81/html5/thumbnails/90.jpg)
90
D A CCEPBA
subroutine leer (est,tipel)implicit noneinteger maxelem, maxi, maxjparameter (maxelem = 15000, maxi = 16, maxj = 16)
real*8 estdimension est (maxelem,maxi,maxj)integer tipeldimension tipel (maxelem)
integer el,i,jreal*8 elementointeger tipo
do el=1,maxelemdo i=1,maxi
do j=1,maxj est(el,i,j ) = elemento (el,i,j)enddo
enddotipel (el)= tipo (el)
enddoend
subroutine modif1 (est)implicit noneinteger maxelem, maxi, maxjparameter (maxelem = 15000, maxi = 16, maxj = 16)
integer niterparameter (niter=10)
real*8 estdimension est (maxelem, maxi,maxj)
integer el,i,jreal*8 coldimension col(maxj)integer kreal*8 coef
![Page 91: CEPBA - UPC Universitat Politècnica de Catalunya](https://reader036.vdocumento.com/reader036/viewer/2022072718/62e07ade68672f40900cdb81/html5/thumbnails/91.jpg)
91
D A CCEPBA
do el=1,maxelem do k=1,niter
coef = 0.do j=1,maxj
col (j) = 0.do i=1,maxi
col(j) = col(j) + est(el,i,j)coef = coef + est(el,i,j)
enddoenddoif (coef .lt. 0) then
do j=1,maxj do i=1,maxi est(el,i,j)= est (el,i,j) + col (j) enddoenddo
elsedo j=1,maxj do i=1,maxi est(el,i,j)= est (el,i,j) - col (j) enddoenddo
endif enddoenddoend
subroutine modif2 (est, tipel)implicit noneinteger maxelem, maxi, maxjparameter (maxelem = 15000, maxi = 16, maxj = 16)
integer niterparameter (niter=10)
real*8 estdimension est (maxelem,maxi,maxj)integer tipeldimension tipel (maxelem)
integer el,i,j,iter
![Page 92: CEPBA - UPC Universitat Politècnica de Catalunya](https://reader036.vdocumento.com/reader036/viewer/2022072718/62e07ade68672f40900cdb81/html5/thumbnails/92.jpg)
92
D A CCEPBA
do el=1,maxelem if (tipel(el) .ne. 0) then
do iter=1,niter do j=2,maxj-1
do i=2,maxi-1est(el,i,j)= est(el,i,j)+est(el,i,j-1)+est(el,i,j+1)est(el,i,j)=(est(el,i,j)+est(el,i-1,j)+est(el,i+1,j))*0.2
enddoenddo
enddoendif
enddoend
subroutine sumar (est, tipel,suma)implicit noneinteger maxelem, maxi, maxjparameter (maxelem = 15000, maxi = 16, maxj = 16)real*8 estdimension est (maxelem,maxi,maxj)integer tipeldimension tipel (maxelem)real*8 sumareal*8 suma_pdimension suma_p (maxi)integer el,i,j
do i=1, maxisuma_p(i) = 0
do el=1, maxelemif (tipel(el) .ne. 0) then
do j=1, maxjsuma_p(i) = suma_p(i) + est(el,i,j)
enddoendif
enddoenddosuma = 0.do i=1, maxi suma = suma + suma_p (i)enddoend
![Page 93: CEPBA - UPC Universitat Politècnica de Catalunya](https://reader036.vdocumento.com/reader036/viewer/2022072718/62e07ade68672f40900cdb81/html5/thumbnails/93.jpg)
93
D A CCEPBA
Optimización del Código New-dim
❑ Aspectos Generales
❑ Reducción de los Fallos de TLB
❑ Eliminacion de Operaciones Innecesarias
❑ Paralelización
![Page 94: CEPBA - UPC Universitat Politècnica de Catalunya](https://reader036.vdocumento.com/reader036/viewer/2022072718/62e07ade68672f40900cdb81/html5/thumbnails/94.jpg)
94
D A CCEPBA
Aspectos Generales
❑ Resultados de la optimización
Código original
Reducción de
fallos de TLB
Eliminación de
operaciones innecesarias
Paralelización
para 8 procesadores
Código optimizado
24:00:00
tiempo de ejecución
4:17:07
1:12:21
0:10:50
Divide el tiempo por 5.71
Divide el tiempo por 3.48
Divide el tiempo por 6.68
![Page 95: CEPBA - UPC Universitat Politècnica de Catalunya](https://reader036.vdocumento.com/reader036/viewer/2022072718/62e07ade68672f40900cdb81/html5/thumbnails/95.jpg)
95
D A CCEPBA
Aspectos Generales
❑ Análisis del código original
UNITCASESELEM_SELECELEM_ULOADSLOAD_CASESPID_DATADYN_SIGN
WRITE_OUT
LOAD_COEFF
9 segundos 24 horas
![Page 96: CEPBA - UPC Universitat Politècnica de Catalunya](https://reader036.vdocumento.com/reader036/viewer/2022072718/62e07ade68672f40900cdb81/html5/thumbnails/96.jpg)
96
D A CCEPBA
Aspectos Generales
❑ Estructura de LOAD_COEFF
DO JCASE=1,NCASESDO I_DYN=1,N_DYN_CASES
DO I_SBC=1,N_DYN_COMBDO I_LAT=0,N_LAT
DO I_DF=1,N_DFDO I_ENG=1,N_ENG
DO IEL=1,NELSELfase (a): producto de matriz por vector
IF cond1 THEN
fase (b): IF cond2 THEN
CALL THPLATE_MS
ELSE
CALL SANDWICH_MS
ENDIF
fase (c): IF (vector(IEL) .GT. SM1) THEN
vectores (IEL) = ......
ENDIF
ENDIF
producto de matriz por vector
IF cond2 THEN
CALL THPLATE_MS
ELSE
CALL SANDWICH_MS
ENDIFIF (CORE (IEL) .GT. SM1) THEN
LC (IEL) = ......
DC (IEL) = ......
ENDIF
22937× NCASES× NELSELiteraciones
![Page 97: CEPBA - UPC Universitat Politècnica de Catalunya](https://reader036.vdocumento.com/reader036/viewer/2022072718/62e07ade68672f40900cdb81/html5/thumbnails/97.jpg)
97
D A CCEPBA
Aspectos Generales
❑ Coste de la rutina LOAD_COEFF
DO JCASE=1,NCASES
DO I_DYN=1,N_DYN_CASES
DO I_SBC=1,N_DYN_COMB
DO I_LAT=0,N_LAT
DO I_DF=1,N_DF
DO I_ENG=1,N_ENG
DO IEL=1,NELSEL
fase (a)
CALL THPLATE
fase (c)
coste_t = 71.0
DO JCASE=1,NCASES
DO I_DYN=1,N_DYN_CASES
DO I_SBC=1,N_DYN_COMB
DO I_LAT=0,N_LAT
DO I_DF=1,N_DF
DO I_ENG=1,N_ENG
DO IEL=1,NELSEL
fase (a)
CALL SANDWICH
fase (c)
coste_s = 70.55
DO JCASE=1,NCASES
DO I_DYN=1,N_DYN_CASES
DO I_SBC=1,N_DYN_COMB
DO I_LAT=0,N_LAT
DO I_DF=1,N_DF
DO I_ENG=1,N_ENG
DO IEL=1,NELSEL
fase (a)
coste_e = 55.0
![Page 98: CEPBA - UPC Universitat Politècnica de Catalunya](https://reader036.vdocumento.com/reader036/viewer/2022072718/62e07ade68672f40900cdb81/html5/thumbnails/98.jpg)
98
D A
CC
EP
BA
Aspectos G
enerales
❑P
rimer análisis
(perfex -a -y new-dim
)%
perfex -a -y new-dim
WARNING: Multiplexing events to project totals--inaccuracy possible.
Based on 195 MHz IP27
Typical Event Counter Name Counter Value Time(sec)===================================================================0 Cycles....................................... 6253742080 32.07
16 Cycles....................................... 625374208032.07047223 TLB misses.................................... 149723216 52.282 Issued loads................................. 1934377792 9.91
25 Primary data cache misses..................... 139268688 6.4318 Graduated loads.............................. 1036942976 5.316 Decoded branches.............................. 765756384 3.92
21 Graduated floating point instructions......... 437530528 2.243 Issued stores................................. 424030848 2.17
19 Graduated stores.............................. 291896848 1.4924 Mispredicted branches.......................... 34131072 0.2422 Quadwords written back from primary data cache. 10250336 0.2026 Secondary data cache misses...................... 261568 0.109 Primary instruction cache misses................. 729712 0.067 Quadwords written back from scache.............. 1157952 0.03
10 Secondary instruction cache misses................. 2688 0.00
![Page 99: CEPBA - UPC Universitat Politècnica de Catalunya](https://reader036.vdocumento.com/reader036/viewer/2022072718/62e07ade68672f40900cdb81/html5/thumbnails/99.jpg)
99
D A CCEPBA
Reducción de los Fallos de TLB
❑ Identificación de las causas%ssrun -tlb_hwc new-dim%prof new-dim.tlb_hwc.xxxx -h
Profile listing generated Thu Feb 12 11:55:51 1998 with: prof new-dim.tlb_hwc.m19034 -h-----------------------------------------------------------
Counter : TLB missesCounter overflow value: 257Total number of ovfls : 580567CPU : R10000FPU : R10010Clock : 195.0MHzNumber of CPUs : 32
-------------------------------------------------------- -p[rocedures] using counter overflow. Sorted in descending order by the number of overflowsin each procedure. Unexecuted or inlined procedures are excluded.--------------------------------------------------------
overflows(%) cum overflows(%) procedure (dso:file)
565358( 97.4) 565358( 97.4) LOAD_COEFF 15197( 2.6) 580555(100.0) SANDWICH_MS 5( 0.0) 580560(100.0) ELEM_ULOADS 3( 0.0) 580563(100.0) rd_F 1( 0.0) 580564(100.0) do_fio64_mp 1( 0.0) 580565(100.0) rd_ned 1( 0.0) 580566(100.0) f_duped 1( 0.0) 580567(100.0) WRITE_OUT
580567(100.0) TOTAL
![Page 100: CEPBA - UPC Universitat Politècnica de Catalunya](https://reader036.vdocumento.com/reader036/viewer/2022072718/62e07ade68672f40900cdb81/html5/thumbnails/100.jpg)
100
D A CCEPBA
Reducción de los Fallos de TLB
❑ Identificación de las causas
--------------------------------------------------------------- -h[eavy] using counter overflow. Sorted in descending order by the number of overflowsin each line. Lines with no overflows are excluded.---------------------------------------------------------------
overflows(%) cum overflows(%) procedure (file:line)
90850( 15.6) 90850( 15.6) LOAD_COEFF (new1-dim.f:1055) 66683( 11.5) 157533( 27.1) LOAD_COEFF (new1-dim.f:1080) 65730( 11.3) 223263( 38.5) LOAD_COEFF (new1-dim.f:1049) 27161( 4.7) 250424( 43.1) LOAD_COEFF (new1-dim.f:1061) 26923( 4.6) 277347( 47.8) LOAD_COEFF (new1-dim.f:1075) 26168( 4.5) 303515( 52.3) LOAD_COEFF (new1-dim.f:1073) 25015( 4.3) 328530( 56.6) LOAD_COEFF (new1-dim.f:1063) 24834( 4.3) 353364( 60.9) LOAD_COEFF (new1-dim.f:1062) 24670( 4.2) 378034( 65.1) LOAD_COEFF (new1-dim.f:1067) 24332( 4.2) 402366( 69.3) LOAD_COEFF (new1-dim.f:1065) 24272( 4.2) 426638( 73.5) LOAD_COEFF (new1-dim.f:1064) 23625( 4.1) 450263( 77.6) LOAD_COEFF (new1-dim.f:1066) 23530( 4.1) 473793( 81.6) LOAD_COEFF (new1-dim.f:1068) 18814( 3.2) 492607( 84.8) LOAD_COEFF (new1-dim.f:1044) 17672( 3.0) 510279( 87.9) LOAD_COEFF (new1-dim.f:1074) 9133( 1.6) 519412( 89.5) LOAD_COEFF (new1-dim.f:1089) 6389( 1.1) 525801( 90.6) LOAD_COEFF (new1-dim.f:1099)
![Page 101: CEPBA - UPC Universitat Politècnica de Catalunya](https://reader036.vdocumento.com/reader036/viewer/2022072718/62e07ade68672f40900cdb81/html5/thumbnails/101.jpg)
101
D A CCEPBA
Reducción de los Fallos de TLB
❑ Identificación de las causas
DO J=1,8
TFORCE(J)=TFORCE(J)+XCFORCE(17)*EFORSEL(IEL,17,J)
TFORCE(J)=TFORCE(J)+XCFORCE(18)*EFORSEL(IEL,18,J)
TFORCE(J)=TFORCE(J)+XCFORCE(20)*EFORSEL(IEL,20,J)
TFORCE(J)=TFORCE(J)+XCFORCE(21)*EFORSEL(IEL,21,J)
TFORCE(J)=TFORCE(J)+XCFORCE(23)*EFORSEL(IEL,23,J)
TFORCE(J)=TFORCE(J)+XCFORCE(24)*EFORSEL(IEL,24,J)
TFORCE(J)=TFORCE(J)+XCFORCE(26)*EFORSEL(IEL,26,J)
TFORCE(J)=TFORCE(J)+XCFORCE(27)*EFORSEL(IEL,27,J)
ENDDO
Posiciones consecutivasde memoria
EFORSEL
4000
Elementos en páginasdistintas
IEL
j
![Page 102: CEPBA - UPC Universitat Politècnica de Catalunya](https://reader036.vdocumento.com/reader036/viewer/2022072718/62e07ade68672f40900cdb81/html5/thumbnails/102.jpg)
102
D A CCEPBA
Reducción de los Fallos de TLB
❑ Reorganización de la matriz
C DECLARACION ORIGINAL
REAL*8 EFORSEL
DIMENSION EFORSEL(NELE,NSBCASE,8)
C NUEVA DECLARACION
REAL*8 EFORSEL
DIMENSION EFORSEL(NSBCASE,8,NELE)
Posiciones consecutivasde memoria
EFORSEL
Elementos en la mismapágina
IEL
j
![Page 103: CEPBA - UPC Universitat Politècnica de Catalunya](https://reader036.vdocumento.com/reader036/viewer/2022072718/62e07ade68672f40900cdb81/html5/thumbnails/103.jpg)
103
D A CCEPBA
Reducción de los Fallos de TLB
❑ Mejora
coste_t coste_s coste_e caso
Original 71 70.5 55.0 24:00:00
Reducción fallos TLB 12.4 13.6 2.48 4:12:07
![Page 104: CEPBA - UPC Universitat Politècnica de Catalunya](https://reader036.vdocumento.com/reader036/viewer/2022072718/62e07ade68672f40900cdb81/html5/thumbnails/104.jpg)
104
D A CCEPBA
Eliminación de Operaciones Innecesarias
❑ Mejora de THPLATE_MS✓ Extracción de invariantes de bucle✓ Conversión de vectores en escalares
SIGVMMX=0.0IX=5A = 1E-3/PTH(IX)B= 6*(PTH(IX)/10.)/(PTH(IX)**3)DO I=-5,5 SIG1=A*FORCE(1)+2*FORCE(4)*I*B SIG2=A*FORCE(2)+2*FORCE(5)*I*B SIG12=A*FORCE(3)+FORCE(6)*I*B
SIG13=6E-3*FORCE(7)*(1-(I/5.)**2)/4/PTH(IX) SIG23=6E-3*FORCE(8)*(1-(I/5.)**2)/4/PTH(IX)SIG_VM=SIG1**2+SIG2**2+(SIG1-SIG2)**2+6*(SIG12+SIG13+SIG23)**2IF (SIG_VM.GT.SIGVMMX) SIGVMMX=SIG_VM
END DOSM1=FTY(IX)/1.1/(SQRT(SIGVMMX)/SQRT(2.))-1.
SIGVMMX=-1.E20IX=5DO I=-5,5
SIG1(I+6)=1E-3*FORCE(1)/PTH(IX)+12*FORCE(4)*(I*PTH(IX)/10.)(PTH(IX)**3)SIG2(I+6)=1E-3*FORCE(2)/PTH(IX)+12*FORCE(5)*(I*PTH(IX)/10.)/(PTH(IX)**3)SIG12(I+6)=1E-3*FORCE(3)/PTH(IX)+6*FORCE(6)*(I*PTH(IX)/10.)/(PTH(IX)**3)SIG13(I+6)=6E-3*FORCE(7)*(1-(I/5.)**2)/4/PTH(IX)SIG23(I+6)=6E-3*FORCE(8)*(1-(I/5.)**2)/4/PTH(IX)SIG_VM(I+6)=SQRT(SIG1(I+6)**2+SIG2(I+6)**2+(SIG1(I+6)-
SIG2(I+6))**2+6*(SIG12(I+6)+SIG13(I+6)+SIG23(I+6))**2)/SQRT(2.)IF (SIG_VM(I+6).GT.SIGVMMX) SIGVMMX=SIG_VM(I+6)
END DOSM1=FTY(IX)/1.1/SIGVMMX-1.
Código original
Código mejorado
![Page 105: CEPBA - UPC Universitat Politècnica de Catalunya](https://reader036.vdocumento.com/reader036/viewer/2022072718/62e07ade68672f40900cdb81/html5/thumbnails/105.jpg)
105
D A CCEPBA
Eliminación de Operaciones Innecesarias
❑ Mejora de SANDWICH_MS✓ Extracción de invariantes de bucle✓ Conversión de vectores en escalares✓ Desarrollo de bucles con dos iteraciones
DO I=1,2 DO J=1,NTLAM(IX)
IF (I_PLY(IX,J).EQ.1) GOTO 5000SIG1(I,J)=(SIG(IX,1,1,J)*FX(I)+SIG(IX,2,1,J)*FY(I)+SIG(IX,3,1,J)*FXY(I))/1.E3SIG2(I,J)=(SIG(IX,1,2,J)*FX(I)+SIG(IX,2,2,J)*FY(I)+SIG(IX,3,2,J)*FXY(I))/1.E3SIG3(I,J)=(SIG(IX,1,3,J)*FX(I)+SIG(IX,2,3,J)*FY(I)+SIG(IX,3,3,J)*FXY(I))/1.E3A=F11(IX,J)*SIG1(I,J)**2+F22(IX,J)*SIG2(I,J)**2+F66(IX,J)*SIG3(I,J)**2+
2.*F12(IX,J)*SIG1(I,J)*SIG2(I,J)B=F1(IX,J)*SIG1(I,J)+F2(IX,J)*SIG2(I,J)C=-1ROOT=(-B+SQRT(B**2-4.*A*C))/(2.*A)IF (ROOT.LE.FS_MIN) FS_MIN=ROOT
5000 ENDDO ENDDO SM2=FS_MIN/1.25-1.
DO J=1,NTLAM(IX)IF (I_PLY(IX,J).NE.1) THEN
S1=(SIG(1,1,J,IX)*FX(1)+SIG(2,1,J,IX)*FY(1)+SIG(3,1,J,IX)*FXY(1))S2=(SIG(1,2,J,IX)*FX(1)+SIG(2,2,J,IX)*FY(1)+SIG(3,2,J,IX)*FXY(1))S3=(SIG(1,3,J,IX)*FX(1)+SIG(2,3,J,IX)*FY(1)+SIG(3,3,J,IX)*FXY(1))A=F11(J,IX)*S1**2+F22(J,IX)*S2**2+F66(J,IX)*S3**2+2.*F12(J,IX)*S1*S2B=F1(J,IX)*S1+F2(J,IX)*S2C=-1ROOT=1.E3*(-B+SQRT(B**2-4.*A*C))/(2.*A)IF (ROOT.LE.FS_MIN) FS_MIN=ROOT
S1=(SIG(1,1,J,IX)*FX(2)+SIG(2,1,J,IX)*FY(2)+SIG(3,1,J,IX)*FXY(2))S2=(SIG(1,2,J,IX)*FX(2)+SIG(2,2,J,IX)*FY(2)+SIG(3,2,J,IX)*FXY(2))
Código original
Código mejorado
![Page 106: CEPBA - UPC Universitat Politècnica de Catalunya](https://reader036.vdocumento.com/reader036/viewer/2022072718/62e07ade68672f40900cdb81/html5/thumbnails/106.jpg)
106
D A CCEPBA
Eliminación de Operaciones Innecesarias
❑ Reorganización de los buclesOrganización original
DO JCASE=1,NCASES
DO I_DF=1,N_DFXFORCE (28,29,30) =DO I_ENG=1,N_ENG
DO IEL=1,NELSEL
×=TFORCE XFORCE
EFORSELfase (a)
IEL
![Page 107: CEPBA - UPC Universitat Politècnica de Catalunya](https://reader036.vdocumento.com/reader036/viewer/2022072718/62e07ade68672f40900cdb81/html5/thumbnails/107.jpg)
107
D A CCEPBA
Eliminación de Operaciones Innecesarias
❑ Reorganización de los buclesNueva organización
DO JCASE=1,NCASESDO IEL=1,NELSEL
DO I_DF=1,N_DF
×=TFDF XFORCE
EFORSEL
IEL
=
++++
TFORCE
TFDF
DO I_ENG=1,N_ENG
![Page 108: CEPBA - UPC Universitat Politècnica de Catalunya](https://reader036.vdocumento.com/reader036/viewer/2022072718/62e07ade68672f40900cdb81/html5/thumbnails/108.jpg)
108
D A CCEPBA
Reducción de los Fallos de TLB
❑ Mejora
coste_t coste_s coste_e caso
Original 71 70.5 55.0 24:00:00
Reducción fallos TLB 12.4 13.6 2.48 4:12:07
Mejora THPLATE 7.44
Mejora SANDWICH 8.06
Reorg. bucles 5.58 4.96 0.62 1:12:21
![Page 109: CEPBA - UPC Universitat Politècnica de Catalunya](https://reader036.vdocumento.com/reader036/viewer/2022072718/62e07ade68672f40900cdb81/html5/thumbnails/109.jpg)
109
D A CCEPBA
Paralelización
❑ Análisis previo
DO JCASE=1,NCASESDO IEL=1,NELSEL
DO I_DYN=1,N_DYN_CASESDO I_SBC=1,N_DYN_COMB
DO I_LAT=0,N_LATDO I_DF=1,N_DF
DO I_ENG=1,N_ENG
producto de matriz por vector
IF cond1 THEN
IF cond2 THEN
CALL THPLATE_MS
ELSE
CALL SANDWICH_MS
ENDIF
IF (vector(IEL) .GT. SM1) THEN
vectores (IEL) = ......
ENDIF
suma de vectores
IF cond2 THEN
CALL THPLATE_MS
ELSE
CALL SANDWICH_MS
ENDIF
IF (CORE (IEL) .GT. SM1) THEN
LC (IEL) = ......
DC (IEL) = ......
ENDIF
DO IEL=1,NELSEL
Bucle paralelo
Iteracionesde costevariable
![Page 110: CEPBA - UPC Universitat Politècnica de Catalunya](https://reader036.vdocumento.com/reader036/viewer/2022072718/62e07ade68672f40900cdb81/html5/thumbnails/110.jpg)
110
D A CCEPBA
Paralelización
❑ Directiva de paralelización
C$DOACROSS LOCAL (IEL, J, a, TFORCE_JCASE, TFORCE_I_SBC,
C$& TFORCE_I_LAT, TFORCE_I_ENG, TFORCE_I_DF, TFORCE,
C$& I_DYN, N_DYN_COMB, I_SBC, I_LAT, I_DF, I_ENG,
C$& X15,X16,X19,X22,X25,X17,X18,X20,X21,X23,X24,X26,
C$& X27,X13,X14,
C$& CORE_BYPASS, FACING_BYPASS, J_C, SM1, SM2,H,
C$& S1,S2,S3,IX,TX,TY,CFI,FX,FY,FXY, SIGVM, FSM,B,C,ROOT,FS_MIN,
C$& SIGVMMX,SIG1,SIG2,SIG12,SIG13,SIG23,SIG_VM,I)
C$& MP_SCHEDTYPE=SIMPLE
DO IEL=1, NELSEL
![Page 111: CEPBA - UPC Universitat Politècnica de Catalunya](https://reader036.vdocumento.com/reader036/viewer/2022072718/62e07ade68672f40900cdb81/html5/thumbnails/111.jpg)
111
D A CCEPBA
Paralelización
❑ Planificación estática
✓ Desequilibrio de carga
10
20
30
40
50
60
62 segundos
32 segundos
8 procesadores1 8
4 procesadores1 4
tiempo (segundos)
Cálculo
Inactividad
44 segundos (OPTIMO)
22 segundos (OPTIMO)
![Page 112: CEPBA - UPC Universitat Politècnica de Catalunya](https://reader036.vdocumento.com/reader036/viewer/2022072718/62e07ade68672f40900cdb81/html5/thumbnails/112.jpg)
112
D A CCEPBA
Paralelización
❑ Medida de la actividad de los procesadores%ssrun -pcsamp new-dim%prof new-dim.pcsamp.xxxx
----------------------------------------------------------Profile listing generated Thu Feb 12 16:34:29 1998 with:prof new-dim.pcsamp.p16894----------------------------------------------------------
samples time CPU FPU Clock N-cpu S-interval Countsize 3202 32.02s R10000 R10010 195.0MHz 31 10.0ms 2(bytes)
Each sample covers 4 bytes for every 10.0ms ( 0.03% of 32.0200s)
------------------------------------------------------ -p[rocedures] using pc-sampling. Sorted in descending order by the number of samples in each procedure. Unexecuted or inlined procedures are excluded.-----------------------------------------------------
samples time(%) cum time(%) procedure (dso:file)
3049 30.49s( 95.2) 30.49s( 95.2) __mpdo_load_coeff_1 153 1.53s( 4.8) 32.02s(100.0) __mp_slave_wait_for_work
3202 32.02s(100.0) 32.02s(100.0) TOTAL
![Page 113: CEPBA - UPC Universitat Politècnica de Catalunya](https://reader036.vdocumento.com/reader036/viewer/2022072718/62e07ade68672f40900cdb81/html5/thumbnails/113.jpg)
113
D A CCEPBA
Paralelización
❑ Planificación dinámica pura
✓ Compartición falsa
10
20
30
40
50
60
90 segundos
79 segundos
8 procesadores1 8
4 procesadores1 4
tiempo (segundos)
Cálculo
Sobrecarga70
80
90
planificación
![Page 114: CEPBA - UPC Universitat Politècnica de Catalunya](https://reader036.vdocumento.com/reader036/viewer/2022072718/62e07ade68672f40900cdb81/html5/thumbnails/114.jpg)
114
D A CCEPBA
Paralelización
❑ Compartición falsa
LC DC SB
IEL
Linea decache L2
16
![Page 115: CEPBA - UPC Universitat Politècnica de Catalunya](https://reader036.vdocumento.com/reader036/viewer/2022072718/62e07ade68672f40900cdb81/html5/thumbnails/115.jpg)
115
D A CCEPBA
Paralelización
❑ Planificación dinámica CHUNK=16
✓ Crece el desequilibrio de carga
✓ Crece la sobrecarga de planificación
10
20
30
40
50
57 segundos
30 segundos
8 procesadores1 8
4 procesadores1 4
tiempo (segundos)
Cálculo
Sobrecargaplanificación
![Page 116: CEPBA - UPC Universitat Politècnica de Catalunya](https://reader036.vdocumento.com/reader036/viewer/2022072718/62e07ade68672f40900cdb81/html5/thumbnails/116.jpg)
116
D A CCEPBA
Paralelización
❑ Reorganización de las estructuras de datos
IEL
16
LCDCSC
Linea decache L2
![Page 117: CEPBA - UPC Universitat Politècnica de Catalunya](https://reader036.vdocumento.com/reader036/viewer/2022072718/62e07ade68672f40900cdb81/html5/thumbnails/117.jpg)
117
D A CCEPBA
Paralelización
❑ Planificación dinámica pura
10
20
30
22 segundos
8 procesadores1 8
tiempo (segundos)
Cálculo
Sobrecargaplanificación
![Page 118: CEPBA - UPC Universitat Politècnica de Catalunya](https://reader036.vdocumento.com/reader036/viewer/2022072718/62e07ade68672f40900cdb81/html5/thumbnails/118.jpg)
118
D A CCEPBA
Paralelización
❑ Mejora
coste_t coste_s coste_e caso
Original 71 70.5 55.0 24:00:00
Reducción fallos TLB 12.4 13.6 2.48 4:12:07
Mejora THPLATE 7.44
Mejora SANDWICH 8.06
Reorg. bucles 5.58 4.96 0.62 1:12:21
Paralelización (P=8) 0:10:50