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