DISEÑO DE ALGORITMO PARALELOS

Universisdad de Los Andes Facultad de Ingeniería Escuela de Sistemas








Diseño de Algoritmos Paralelos
Prof. Gilberto Díaz
gilberto@ula.ve







Departamento de Computación, Escuela de Sistemas, Facultad de Ingeniería
Universidad de Los Andes, Mérida 5101 Venezuela
Diseño de Algoritmos Paralelos








Antes de mostrar los detalles de MPI debemos
realizaralgunas consideraciones sobre el diseño de algoritmos paralelos.



Diseñar algoritmos paralelos no es tarea fácil y es un proceso altamente creativo.



Inicialmente se deben explorar los aspectos independientes de la máquina



Los aspectos específicos a la máquina deben ser dejados para más tarde.






Depto Computación – Escuela de Sistemas – Universidad de Los Andes –Mérida – Venezuela - Gilberto Diaz
Diseño de Algoritmos Paralelos








El diseño involucra cuatro etapas las cuales se
presentan como secuenciales pero que en la práctica no lo son.



Particionamiento
Comunicación Agrupamiento Asignación



















Depto Computación – Escuela de Sistemas – Universidad de Los Andes – Mérida – Venezuela - Gilberto DiazDiseño de Algoritmos Paralelos








Particionamiento: El cómputo y los datos sobre
los cuales se opera se descomponen en tareas. Se ignoran aspectos como el número de procesadores de la máquina a usar y se concentra la atención en explotar oportunidades de paralelismo.

























Depto Computación – Escuela de Sistemas – Universidad de LosAndes – Mérida – Venezuela - Gilberto Diaz
Diseño de Algoritmos Paralelos








Comunicación: Se determina la comunicación
requerida para coordinar las tareas.



Se definen estructuras y algoritmos de comunicación.




























Depto Computación – Escuela de Sistemas – Universidad de Los Andes – Mérida – Venezuela - Gilberto DiazDiseño de Algoritmos Paralelos








Agrupamiento: El resultado de las dos etapas
anteriores es evaluado en términos de eficiencia y costos de implementación.



De ser necesario, se agrupan tareas pequeñas en tareas más grandes.

























Depto Computación – Escuela de Sistemas – Universidad de Los Andes – Mérida – Venezuela - GilbertoDiaz
Diseño de Algoritmos Paralelos








Asignación: Cada tarea es asignada a un
procesador tratando de maximizar la utilización de los procesadores y de reducir el costo de comunicación.



La asignación puede ser estática (se establece antes de la ejecución del programa) o en tiempo de ejecución mediante algoritmos de balanceo de carga.















DeptoComputación – Escuela de Sistemas – Universidad de Los Andes – Mérida – Venezuela - Gilberto Diaz
Diseño de Algoritmos Paralelos


Gráficamente tenemos


Problema





Partición Comunicación




















Asignación
Agrupación










Depto Computación – Escuela de Sistemas – Universidad de Los Andes – Mérida – Venezuela - Gilberto DiazDiseño de Algoritmos Paralelos








En la etapa de partición se buscan
oportunidades de paralelismo y se trata de subdividir el problema lo más finamente posible, es decir; que la granuralidad sea fina.



Un grano es una medidad del trabajo computacional a realizar.






















Depto Computación – Escuela de Sistemas – Universidad de Los Andes –Mérida – Venezuela - Gilberto Diaz
Diseño de Algoritmos Paralelos








Evaluaciones futuras podrán llevar a aglomerar
tareas y descartar ciertas posibilidades de paralelismo. Una buen particionamiento divide tanto los cómputos como los datos.



Descomposición funcional



Descomposición de dominio



















Depto Computación – Escuela de...