Algoritmos Multihilo
Introducción
Algoritmos Multihilo
• Hasta ahora los algoritmos que hemos visto son seriales ya que se ejecutan en modelo RAM (un solo procesador)
• Necesitamos extender modelo RAM para describir algoritmos que se ejecutan en paralelo
• La mayor parte de los dispositivos de cómputo actuales son multiprocesador
Modelos PRAM
• Hay varios tipos de modelos de computadoras que funcionan en paralelo
• Uno de los principales aspectos en que difieren es en como se intercambian mensajes
• Existen modelos de memoria compartida y los de memoria distribuida
• Los computadores actuales son de memoria compartida
Programación Multihilo Dinámica
• Generalmente nos basamos en una plataforma de concurrencia (capa de software)
• El lenguaje de programación (o una librería) nos provee extensiones simples en la forma de instrucciones de concurrencia parallel, spawn, and sync.
Spawn
• Spawn: Si spawn precede a una llamada a función, el procedimiento que ejecuta la llamada (el padre) sigue ejecutándose en paralelo con la subrutina creada (el hijo), en vez de esperar a que el hijo termine.
Spawn
• Spawn significa que pude ejecutarse en paralelo, no que es obligatorio
• En tiempo de ejecución, el scheduler decide que instrucciones se ejecutan de manera concurrente.
Sync
• La palabra reservada sync indica que un procedimiento debe esperar hasta que todos sus hijos creados completen sus tareas.
Parallel• Muchos algoritmos contienen lazos. • Si se utiliza la palabra reservada parallel antes de un lazo form, esto
indica que el cuerpo del lazo puede ser ejecutado en paralelo.
Cálculo de los Números Fibonacci Multihilo
• Los números Fibonacci son generados por la siguiente definición:
F0 = 0 F1 = 1para i > 1, Fi = Fi-1 + Fi-2
Algoritmo Fuerza Bruta
Algoritmo de Fuerza Bruta
Fibonacci Multihilo• Si lo queremos hacer multihilo este sería el algoritmo:
DAG del Algoritmo
• La ejecución multihilo puede comprenderse mejor con un grafo acícliclo dirigido (DAG) G=(V,E).
• Los vértices V en el gráfico son las instrucciones. • Los enlaces E representan la dependencia entre
las instrucciones.• Si un enlace (u,v) está en E significa que la
instrucción u debe ejecutarse antes de la instrucción v.
DAG
Strands
Loops Paralelos