PDF de programación - Programación Paralela y Distribuida

Programación

Paralela y Distribuida

Cores, Threads and Nodes

Pedro Antonio Varo Herrero
[email protected]

 Pedro Antonio Varo Herrero

 Estudiante 4º Curso - Universidad de Sevilla
 Grado Ing. Informática –Tecnologías Informáticas, Rama de Computación.
 Investigaciones actuales:

 Técnicas de paralelización de algoritmos.
 Evolución de redes complejas.
 Paralelización en GP-GPU con Cuda y OpenCl.
 Simulación de fluidos con método SPH y Cuda/OpenCL.
 Algoritmos de Colonias de Hormigas.

Pedro Varo Herrero

@pevahe91

Pedro Varo Herrero – [email protected]

Contenidos

1. Que es la Programación Paralela.
2. Porque paralelizar.
3. Tipos de Paralelismos y arquitecturas.
4. Paradigma de Programación Paralela.
5. Librerías de Python: Cython+OpenMP, MPI4Py, PyCuda, PyOpenCL,

Que es

 Varios procesadores juntos para resolver uno o varios problemas.

Problems

Code/Algorithm Processeso

rs

Results

Porque paralelizar

Porque paralelizar

 Limitaciones físicas de sistemas secuenciales:



Topes frecuencia de

reloj

Más Frecuencia -> Más Temperatura y

Más Consumo

 Problemas de alta complejidad computacional:

 Simulación de sistemas físicos, biológicos…
 Volumen de datos con los que operar.
 Ingeniería, ciencia.

Tipos de Paralelismos y
arquitecturas.

Tipos de Paralelismos y
arquitecturas.

 Arquitecturas según instrucciones y datos:

 Taxonia de Flynn, 1972:

Instrucciones/Da
tos

Simples

Simples

Múltiples

Single Instr. Single

Data
(SISD)

Single Instr. Multiple

Data
(SIMD)

Múltiples

• Arquitecturas Paralelas -> SIMD , MIMD

Multiple Instr. Single

Multiple Instr. Multiple

Data
(MISD)

Data

(MIMD)

• SISD -> Antiguas arquitecturas de procesadores secuenciales.

• MISD -> distintas instrucciones a un mismo dato.

Single Instr. Multiple Data

(SIMD)

Multiple Instr. Multiple Data

(MIMD)

Inst.1

Inst.1

Inst.2

Inst.3

Inst.4

Data1

Data2

Data3

Data1

Data2

Data3

Data4

Single Instr. Multiple Data

(SIMD)

Inst.

1

Data1

Data2

Data3

Multiple Instr. Multiple Data

(MIMD)

Inst.

1

Inst.

2

Inst.

3

Inst.

4

Data1

Data2

Data3

Data4

Supercomputador Marenostrum - Barcelona

Clúster casero

Tipos de Paralelismos y arquitecturas.

 Arquitecturas según distribución de memoria:

Física/Lógica

Direcciones

Memoria compartida

Memoria
compartida

Memoria
Distribuida

Uniform Memory

Access
UMA

Non-Uniform Memory

Access
NUMA

Direcciones
Memoria
separadas

------

Memory Passing

Message

MPM

Uniform Memory Access

UMA

Non-Uniform Memory

Access
NUMA

Memory

Memory

Memory

Memory

Memory

Memory

Memory

Memory

Main
Memory

Memory Passing Message

MPM

MemoryMemoryMemoryMemoryMain MemoryMemoryMemoryMemoryMemoryUniform Memory

Access
UMA

Memory

Memory

Memory

Memory

Main Memory

MemoryMemoryMemoryMemoryMain MemoryNon-Uniform Memory

Access
NUMA

Memory

Memory

Memory

Memory

Cray CS300

MemoryMemoryMemoryMemoryMemory Passing

Message

MPM

Supercomputador Marenostrum -

Barcelona

Clúster casero

Paradigmas de Programación
Paralela

Paradigmas de Programación
Paralela

 Por manejo de Threads/Tareas.
 Por paso de mensajes.
 Hibrida: Threads + Paso de mensajes.

Memory

Red de

interconexión

MemoryParadigmas de Programación Paralela

 Por manejo de Threads:

 Usado con arquitecturas de Memoria compartida.
 Da comunicación entre threads en un procesador.
 Estandar : OpenMP (C/C++ ,Fortran) , CUDA, OpenCL.

Paradigmas de Programación Paralela

 Por paso de mensajes:
 Usado en arquitecturas de memoria distribuida.
 Da comunicación entre los distintos procesadores/nodos/maquinas del

sistema.

 Se crean distintas tareas, cada uno con su propio espacio de memoria.
 Los datos entre tareas, se comparten en el paso del mensaje.
 Código escalable.
 Estandar: MPI(C/C++,Fortran).

Red de

interconexión

Paradigmas de Programación Paralela

 Híbrida:

 Usa ambas arquitecturas.
 Para llegar desde nivel de nodo/maquina a nivel de hilo.
 Usa ambos: OpenMP/CUDA/OpenCL+MPI

Memory

MemoryLibrerías

Librerías

Multiprocessing

y

“Estándares” de librerías de

programación paralela

MPI4P

Py

P
y

Multiprocessing

GIL – Global Interpreter
Lock

 En Python la ejecución de Threads está controlada por el GIL(Global

Interpreter Lock).

 No permite que se ejecute mas de un Thread a la vez.

Sys setcheckinterval

Python Summer-School 2011 – UK University of St Andrews

Francesc Alted

https
://python.g-node.org/python-summerschool-2011/_media/materials/parallel/parallelcython.p
df

Multiprocessing

P
y

 Para ello Python nos ofrece el módulo Multiprocessing, basado en la

ejecución de distintos procesos en distintos cores.

 Cython extensión que permite escribir funciónes/módulos Python

con variaciones y compilarlo.

 Este código compilado , luego podemos llamarlo desde Python.

P
y

 Python con añadidos.

Escribimos
nuestro
código en
Cython

Compilamos

Ejecutamos

 Ahora podemos crearnos nuestros hilos y ejecutarlos.
 Podemos usar OpenMp importándolo en Cython.
 Y con esto nos saltamos el GIL.

 Que nos hace falta:

 Compilador de C/C++
 Python 2.6-3.3.2 (32 bits)
 Setup tools: https://pypi.python.org/pypi/setuptools
 Pypi: https://pypi.python.org/pypi
 Añadimos variable de entorno: C:\Python33\Scripts
 Ejecutamos pip install cython o easy_install cython

MPI4
Py Memory

data

Memory
data(copy)

CPU

CPU

message

 PyPar

 Proyecto de la Universidad Nacional de Australia.
 https://code.google.com/p/pypar/

 pyMPI

 Proyecto hecho por investigadores del

Lawrence Livermore National Laboratory , California

 http://pympi.sourceforge.net/index.html

 MPI4Py

 Proyecto de Lisandro Dalcin, basado en MPI-1/2
 Implementa la mayoría de funciones de MPI
 http://mpi4py.scipy.org/

Task 0

data

Task 1

data

network

messagenetworkMPI4

Py

MPI4

C

Py

PyPar MPI4Py pyMPIP SciPy.M

PI

8
967.00
4

Latency
23
Bandwit
508.97
h
2
 MPI4Py implementa la mayoría de

14
944.47
5

25
898.94
9

133
150.90
1

rutinas.

 PyPar, MPI4Py y SciPy dan mejores

resultados.

 Con PyPar tenemos menos control.
 Si sabemos MPI, MP4Py es trivial.

PyPar

MPI4Py

pyMPIP

SciPy.MPI

MPI_Send

MPI_Recv

MPI_Sendre

cv

MPI_Isend

MPI_Irecv

MPI_Bcast

MPI_Reduce

MPI_Allredu

MPI_Gather

MPI_Allgath

ce

er

MPI_Scatter

MPI_Alltoall









































































Comparativas de Trabajo de Fin de Master Universidad de

WENJING LIN – A comparison of existing python

Oslo por:

modules of MPI

Master i Anvendt matematikk og mekanikk
(Master de Matemáticas y Mecánica aplicada)

MPI4

Py

Imágenes de Trabajo de Fin de Master Universidad de

Master i Anvendt matematikk og mekanikk
(Master de Matemáticas y Mecánica aplicada)

Oslo por:

WENJING LIN

MPI4

Py

 MPI_Init -> Siempre y única la primera vez
 MPI_Finalize -> Última rutina
 MPI_Comm_size -> Nº procesos de un grupo.
 MPI_Comm_rank -> Devuelve rango(id).
 MPI_Send -> Enviar mensajes
 MPI_Recv -> Recibir mensajes

Funciones colectivas

MPI4

Py

 Que nos hace falta:

 Una versión de MPI, por ejemplo OpenMPI (

http://www.open-mpi.org/software/ompi/v1.6/).

 Compilador de C/C++
 Python 2.6-3.3.2 (32 bits)
 Setup tools: https://pypi.python.org/pypi/setuptools
 Pypi: https://pypi.python.org/pypi
 Ejecutamos comando : pip instal mpi4py o easy_install mpi4py

 Cálculo de Pi

Pi.py
from mpi4py import MPI
import numpy
import sys

print "Spawning MPI processes"
comm =
MPI.COMM_SELF.Spawn(sys.executable

, args=['CalcPi.py'] ,maxprocs=8)

N = numpy.array(100, 'i')
comm.Bcast([N, MPI.INT], root=MPI.ROOT)
PI = numpy.array(0.0, 'd')
comm.Reduce(None, [PI, MPI.DOUBLE],
op=MPI.SUM, root=MPI.ROOT)

print "Calculated value of PI is: %f16" %PI

MPI4

Py

CalcPi.py
from mpi4py import MPI
import numpy

comm = MPI.Comm.Get_parent()
size = comm.Get_size()
rank = comm.Get_rank()

N = numpy.array(0, dtype='i')
comm.Bcast([N, MPI.INT], root=0)
h = 1.0 / N; s = 0.0
for i in range(rank, N, size):

x = h * (i + 0.5)
s += 4.0 / (1.0 + x**2)

PI = numpy.array(s * h, dtype='d')
comm.Reduce([PI, MPI.DOUBLE], None,

op=MPI.SUM, root=0)

print "Disconnecting from rank %d"%rank
comm.Barrier()

comm.Disconnect()

Py

Py

Cores complejos, con muchas
instrucciones.

Cores simples, con instrucciones
limitadas.

• Grid de bloques de hilos.

• Bloques de hilos.

• Hilos máximos 512 por bloque.

Py

 CUDA(Compute Unified Device Architecture) creado por NVIDIA.
 PyCUDA proyecto de Andreas Klöckner.
 Wrapper de CUDA -> PyCUDA.
 http://mathema.tician.de/software/pycuda/

Idea

GPU Code

Python
Code

GPU

Compiler

Labor del humano, programador

GPU
Code

Results

GPU Binary

Máquina

Py

 OpenCL(Open Computing Language), creado por Apple y

desarrollada en conjunto AMD, Intel, IBM y Nvidia.

 Propuesta al Grupo Khronos para convertirla en estandar.
 Api para computación paralela en CPU y GPU.
 Wrapper de OpenCL -> PyOpenCL.
 http://mathema.tician.de/software/pyopencl/

Idea

Python
Code

GPU/CPU

Code

GPU /CPU
Compiler

Labor del humano,
programador

GPU/CPU

Code

Results

GPU/CPU

Binary

Máquina

Py

 Que nos hace falta:

Py

 CUDA/OpenCL:
 Python 3.3 (64 bits)
 PyCUDA: http://www.lfd.uci.edu/~gohlke/pythonlibs/
 Boost.Python:  

http://www.lfd.uci.edu/~gohlke/pythonlibs/#pycuda
 NumPy: http://www.lfd.uci.edu/~gohlke/pythonlibs/
 CUDA: https://developer.nvidia.com/cuda-downloads
 Setuptools: https://pypi.python.org/pypi/setuptools
 PyTools: http://pypi.python.org/pypi/pytools
 Visual C++ 2010

Py

Py

 “Pasos a seguir”:

 1. Inicializar Memoria en GPU
 2. Configurar Grid
 3. Lanzar Kernel

 3.1 Calcular ID del Hilo.
 3.2 Acceder a datos y cálculo.

 4. Traer Resultado

Py

Py

 Consideraciones de Rendimiento:

 1.- Lanzar cuantos más hilos mejor.
 2.- Mantener el SIMD/SIMT dentro de cada bloque.
 3.- Usar memoria compartida siempr