![Page 1: Sistemas Operativos II MC. Daniel Fajardo Delgado INSTITUTO TECNOLÓGICO DE CD. GUZMÁN 1o de Mayo de 2004](https://reader036.vdocumento.com/reader036/viewer/2022062322/5665b4421a28abb57c907b64/html5/thumbnails/1.jpg)
Sistemas Operativos IISistemas Operativos II
MC. Daniel Fajardo Delgado
INSTITUTO TECNOLÓGICO DE CD. GUZMÁNINSTITUTO TECNOLÓGICO DE CD. GUZMÁN
1o de Mayo de 2004
![Page 2: Sistemas Operativos II MC. Daniel Fajardo Delgado INSTITUTO TECNOLÓGICO DE CD. GUZMÁN 1o de Mayo de 2004](https://reader036.vdocumento.com/reader036/viewer/2022062322/5665b4421a28abb57c907b64/html5/thumbnails/2.jpg)
COMPUTACIÓN PARALELA
![Page 3: Sistemas Operativos II MC. Daniel Fajardo Delgado INSTITUTO TECNOLÓGICO DE CD. GUZMÁN 1o de Mayo de 2004](https://reader036.vdocumento.com/reader036/viewer/2022062322/5665b4421a28abb57c907b64/html5/thumbnails/3.jpg)
Existe demanda de rapidez computacional...
- Predicción numérica del clima.- Modelación de estructuras de ADN.- Predicción de movimientos de cuerpos astronómicos en el espacio.- Realidad virtual.- ... the grand challenge problems
Los cálculos deben ser completados en un periodo de tiempo “razonable”.
Para incrementar la rapidez computacional básicamente: Se divide el problema en partes, donde cada parte se desarrolla en un procesador separado en paralelo.
Escribir programas de esa forma ~> parallel programmingLa plataforma donde se desarrolla ~> parallel computerLa ciencia que engloba ésto ~> parallel computing
![Page 4: Sistemas Operativos II MC. Daniel Fajardo Delgado INSTITUTO TECNOLÓGICO DE CD. GUZMÁN 1o de Mayo de 2004](https://reader036.vdocumento.com/reader036/viewer/2022062322/5665b4421a28abb57c907b64/html5/thumbnails/4.jpg)
Además de incrementar la rapidez para resolver un problema:
- Permite obtener una solución con mayor precisión del problema.
Las computadoras paralelas no son una idea nueva...
- 1958 Gill (parallel programming)- 1959 Holland (parallel computer)- 1963 Conway (diseño de una parallel computer y su programación)- ... 1996 Flynn y Rudd (el futuro es paralelismo)
![Page 5: Sistemas Operativos II MC. Daniel Fajardo Delgado INSTITUTO TECNOLÓGICO DE CD. GUZMÁN 1o de Mayo de 2004](https://reader036.vdocumento.com/reader036/viewer/2022062322/5665b4421a28abb57c907b64/html5/thumbnails/5.jpg)
Computadora paralela. Colección de procesadores interconectados en cierta forma para coordinar tareas e intercambiar información.
Sistema distribuido. Colección de procesadores distribuidos en una gran área geográfica.
Los factores que contribuyen al desarrollo del procesamiento paralelo:
- Hardware barato- Alta escala de integración- Limitaciones físicas de procesadores
![Page 6: Sistemas Operativos II MC. Daniel Fajardo Delgado INSTITUTO TECNOLÓGICO DE CD. GUZMÁN 1o de Mayo de 2004](https://reader036.vdocumento.com/reader036/viewer/2022062322/5665b4421a28abb57c907b64/html5/thumbnails/6.jpg)
TIPOS DE COMPUTADORAS PARALELAS
Memoria principal
Procesador
Una computadora convencional consiste de un procesador ejecutando un programa almacenado en memoria principal. Cada localidad de memoria principal en todas las computadoras es localizada mediante un número llamado dirección de memoria ( 0 – {2^n - 1})
Instrucciones del procesador.
Los datos van y vienen al procesador.
![Page 7: Sistemas Operativos II MC. Daniel Fajardo Delgado INSTITUTO TECNOLÓGICO DE CD. GUZMÁN 1o de Mayo de 2004](https://reader036.vdocumento.com/reader036/viewer/2022062322/5665b4421a28abb57c907b64/html5/thumbnails/7.jpg)
Red de interconexión
Módulos de memoria
Procesadores
Un espacio de direcciones
Sistema multiprocesador de memoria compartida
![Page 8: Sistemas Operativos II MC. Daniel Fajardo Delgado INSTITUTO TECNOLÓGICO DE CD. GUZMÁN 1o de Mayo de 2004](https://reader036.vdocumento.com/reader036/viewer/2022062322/5665b4421a28abb57c907b64/html5/thumbnails/8.jpg)
Red de interconexión
Computadoras
Memoria local
Procesador
Mensajes
Multicomputadora de paso de mensajes
![Page 9: Sistemas Operativos II MC. Daniel Fajardo Delgado INSTITUTO TECNOLÓGICO DE CD. GUZMÁN 1o de Mayo de 2004](https://reader036.vdocumento.com/reader036/viewer/2022062322/5665b4421a28abb57c907b64/html5/thumbnails/9.jpg)
Red de interconexión
Memoria distribuida
Procesador
Mensajes
Memoria distribuida-compartida
![Page 10: Sistemas Operativos II MC. Daniel Fajardo Delgado INSTITUTO TECNOLÓGICO DE CD. GUZMÁN 1o de Mayo de 2004](https://reader036.vdocumento.com/reader036/viewer/2022062322/5665b4421a28abb57c907b64/html5/thumbnails/10.jpg)
TAXONOMIA DE FLYNN
~> Fue introducida en 1972 y es una de las taxonomías más conocidas sobre arquitectura de computadoras.
~> Michael Flynn clasificó las arquitecturas en 4 categorías basadas sobre la presencia de uno o múltiples apuntadores a instrucciones y datos.
Un apuntador a instrucción es un conjunto de instrucciones secuenciales a ser ejecutadas por sólo un procesador.
El apuntador a datos es un flujo secuencial de datos solicitados mediante un apuntador a instrucción.
![Page 11: Sistemas Operativos II MC. Daniel Fajardo Delgado INSTITUTO TECNOLÓGICO DE CD. GUZMÁN 1o de Mayo de 2004](https://reader036.vdocumento.com/reader036/viewer/2022062322/5665b4421a28abb57c907b64/html5/thumbnails/11.jpg)
Las 4 categorias de Flynn son las siguientes:
1. SISD (Single Instruction stream – Single Data stream).~> Es el concepto de la computadora secuencial de Von Neumann~> Sólo una instrucción es ejecutada a la vez~> Las máquinas SISD son de propósito general como las pc que
normalmente utilizamos (aunque incluso las pc de hoy en día utilizan grados pequeños de paralelismo).
2. MISD (Multiple Instruction stream – Single Data stream).~> Varias instrucciones operan sobre un conjunto simple de datos.~> Distintas unidades de procesamiento reciben instrucciones
distintas de operación sobre el mismo dato. (Es impráctico o imposible).~> Existen algunas arquitecturas pipelined como el Systolic Array.
![Page 12: Sistemas Operativos II MC. Daniel Fajardo Delgado INSTITUTO TECNOLÓGICO DE CD. GUZMÁN 1o de Mayo de 2004](https://reader036.vdocumento.com/reader036/viewer/2022062322/5665b4421a28abb57c907b64/html5/thumbnails/12.jpg)
3. SIMD (Single Instruction stream – Multiple Data stream).~> Sólo una instrucción es aplicada a datos diferentes al mismo
tiempo.~> Unidades sepadaras de procesamiento son llamadas por una
unidad simple de control.~> La misma operación es desarrollada en un momento dado
sobre un conjunto grande de datos.
4. MIMD (Multiple Instruction stream – Multiple Data stream).~> Incluye máquinas con varias unidades de procesamiento.~> Múltiples instrucciones pueden ser aplicadas a distintos datos
simultaneamente.~> Multiprocesadores.~> Multicomputadoras.
![Page 13: Sistemas Operativos II MC. Daniel Fajardo Delgado INSTITUTO TECNOLÓGICO DE CD. GUZMÁN 1o de Mayo de 2004](https://reader036.vdocumento.com/reader036/viewer/2022062322/5665b4421a28abb57c907b64/html5/thumbnails/13.jpg)
ACELERACIÓN, EFICIENCIA Y REDUNDANCIA
Speedup (Sp, Aceleración):El factor dado por el tiempo necesario para resolver un problema
dado usando el mejor algoritmo secuencial conocido y el tiempo necesario para resolver el mismo problema por un algoritmo paralelo usando p procesadores.
Sea:
Ts(N) tiempo requerido para resolver un problema de tamaño N por el mejor algoritmo secuencial.
Tp(N) tiempo necesario para que el algoritmo paralelo usando p procesadores resuelva el mismo problema de tamaño N.
EntoncesSp = Ts(N) / Tp(N)
![Page 14: Sistemas Operativos II MC. Daniel Fajardo Delgado INSTITUTO TECNOLÓGICO DE CD. GUZMÁN 1o de Mayo de 2004](https://reader036.vdocumento.com/reader036/viewer/2022062322/5665b4421a28abb57c907b64/html5/thumbnails/14.jpg)
Tal que:1 <= Sp <= p
Debido a la pérdida de tiempo en operaciones de:
- Sincronización
- Comunicación
- overhead
Si Sp > p se le llama speedup superlineal.
![Page 15: Sistemas Operativos II MC. Daniel Fajardo Delgado INSTITUTO TECNOLÓGICO DE CD. GUZMÁN 1o de Mayo de 2004](https://reader036.vdocumento.com/reader036/viewer/2022062322/5665b4421a28abb57c907b64/html5/thumbnails/15.jpg)
Eficiencia (Ep)
La eficiencia de un algoritmo paralelo se define como el factor dado por el factor de aceleración y el número de procesadores.
Ep = Sp / p
0 < Ep <= 1
Redundancia (Rp)
La redundancia de un algoritmo paralelo se define como el factor dado por el número total de operaciones realizadas usando p procesadores (Op) y el número de operaciones realizadas usando un procesador.
Rp = Op / O1
Rp >= 1
![Page 16: Sistemas Operativos II MC. Daniel Fajardo Delgado INSTITUTO TECNOLÓGICO DE CD. GUZMÁN 1o de Mayo de 2004](https://reader036.vdocumento.com/reader036/viewer/2022062322/5665b4421a28abb57c907b64/html5/thumbnails/16.jpg)
LEY DE AMDAHL
Un número pequeño de operaciones secuenciales puede limitar el factor de aceleración de un algoritmo paralelo.
Sea s el tiempo de ejecución de la parte secuencial del algoritmo. Sea p el tiempo de ejecutar la parte paralela del algoritmo.
s + p = 1 que es la unidad del algoritmo completo. Así s y p son fracciones del cálculo total.
Para n número de procesadores, se tiene:
s + p 1Sp = -------------- = --------------- s + p/n s + (1-s)/n
![Page 17: Sistemas Operativos II MC. Daniel Fajardo Delgado INSTITUTO TECNOLÓGICO DE CD. GUZMÁN 1o de Mayo de 2004](https://reader036.vdocumento.com/reader036/viewer/2022062322/5665b4421a28abb57c907b64/html5/thumbnails/17.jpg)
Corolario de la ley de Amdahl.
Un pequeño número de operaciones secuenciales puede limitar de manera significativa el speedup alcanzado por un algoritmo paralelo.
![Page 18: Sistemas Operativos II MC. Daniel Fajardo Delgado INSTITUTO TECNOLÓGICO DE CD. GUZMÁN 1o de Mayo de 2004](https://reader036.vdocumento.com/reader036/viewer/2022062322/5665b4421a28abb57c907b64/html5/thumbnails/18.jpg)
MODELS FORPARALLEL COMPUTATION
Susanne E. Hambrusch
![Page 19: Sistemas Operativos II MC. Daniel Fajardo Delgado INSTITUTO TECNOLÓGICO DE CD. GUZMÁN 1o de Mayo de 2004](https://reader036.vdocumento.com/reader036/viewer/2022062322/5665b4421a28abb57c907b64/html5/thumbnails/19.jpg)
MODELOS PARALELOS
~> Son mucho más complejos que los modelos secuenciales (RAM)
~> Es deseable que los modelos (paralelos) tengan las siguientes características:
* Simples
* Independientes del hardware
* Implementables
![Page 20: Sistemas Operativos II MC. Daniel Fajardo Delgado INSTITUTO TECNOLÓGICO DE CD. GUZMÁN 1o de Mayo de 2004](https://reader036.vdocumento.com/reader036/viewer/2022062322/5665b4421a28abb57c907b64/html5/thumbnails/20.jpg)
RAM. Random Access Machine
PRAM. Parallel Random Access Machine
P M
P1 P2 P3 P4 Pn
M
![Page 21: Sistemas Operativos II MC. Daniel Fajardo Delgado INSTITUTO TECNOLÓGICO DE CD. GUZMÁN 1o de Mayo de 2004](https://reader036.vdocumento.com/reader036/viewer/2022062322/5665b4421a28abb57c907b64/html5/thumbnails/21.jpg)
Grafos Acíclicos Dirigidos (DAG's)
Entradas. Las hojas del árbol.
Operación. Nodos con aristas de entrada.
Salidas. Nodos sin aristas de salida.
Indegree (Grado de entrada). # de aristas que entran a un nodo.
Outdegree (Grado de salida). # de aristas que salen de un nodo.
- No se permiten saltos.- Se fijan restricciones de precedencia (orden de ejecución).- Independiente del hardware.
![Page 22: Sistemas Operativos II MC. Daniel Fajardo Delgado INSTITUTO TECNOLÓGICO DE CD. GUZMÁN 1o de Mayo de 2004](https://reader036.vdocumento.com/reader036/viewer/2022062322/5665b4421a28abb57c907b64/html5/thumbnails/22.jpg)
A1
+
A2
+
A3
+
A4
+
A5
+
+ +
A1 A2 A3 A4
![Page 23: Sistemas Operativos II MC. Daniel Fajardo Delgado INSTITUTO TECNOLÓGICO DE CD. GUZMÁN 1o de Mayo de 2004](https://reader036.vdocumento.com/reader036/viewer/2022062322/5665b4421a28abb57c907b64/html5/thumbnails/23.jpg)
Modelo de RED
Están muy relacionados al hardware
Modelo Log P
![Page 24: Sistemas Operativos II MC. Daniel Fajardo Delgado INSTITUTO TECNOLÓGICO DE CD. GUZMÁN 1o de Mayo de 2004](https://reader036.vdocumento.com/reader036/viewer/2022062322/5665b4421a28abb57c907b64/html5/thumbnails/24.jpg)
Modelo PRAM (Parallel Random Access Machine)
- Existen p procesadores
- Cada procesador tiene memoria local
- Cada procesador comparte un espacio de memoria común
- Cada procesador puede acceder a la memoria compartida para leer o escribir en una cierta dirección de memoria.
![Page 25: Sistemas Operativos II MC. Daniel Fajardo Delgado INSTITUTO TECNOLÓGICO DE CD. GUZMÁN 1o de Mayo de 2004](https://reader036.vdocumento.com/reader036/viewer/2022062322/5665b4421a28abb57c907b64/html5/thumbnails/25.jpg)
Existen distintas clasificaciones de poder dentro del modelo:
EREW(Exclusive Read, Exclusive Write). No se permiten las lecturas y escrituras simultaneas a una misma dirección de memoria. Es el modelo más restrictivo y el más próximo a las máquinas actuales.
CREW (Concurrent Read, Exclusive Write). No se permiten las escrituras simultaneas a una misma dirección de memoria; sólo las lecturas simultaneas son permitidas.
ERCW (Exclusive Read, Concurrent Write). El acceso en lectura a la memoria compartida es exclusivo; sólo las escrituras simultaneas a una misma dirección en memoria son permitidas.
CRCW (Concurrent Read, Concurrent Write). Las escrituras y lecturas simultáneas a una misma dirección de memoria son permitidas.
![Page 26: Sistemas Operativos II MC. Daniel Fajardo Delgado INSTITUTO TECNOLÓGICO DE CD. GUZMÁN 1o de Mayo de 2004](https://reader036.vdocumento.com/reader036/viewer/2022062322/5665b4421a28abb57c907b64/html5/thumbnails/26.jpg)
EREW
CREW
ERCW
CRCW
Fácil de implementar
Difícil de implementar
Menor poder computacional
Mayor poder computacional
Poder computacional en la PRAM
![Page 27: Sistemas Operativos II MC. Daniel Fajardo Delgado INSTITUTO TECNOLÓGICO DE CD. GUZMÁN 1o de Mayo de 2004](https://reader036.vdocumento.com/reader036/viewer/2022062322/5665b4421a28abb57c907b64/html5/thumbnails/27.jpg)
Ejemplo 1: Reducción paralela
![Page 28: Sistemas Operativos II MC. Daniel Fajardo Delgado INSTITUTO TECNOLÓGICO DE CD. GUZMÁN 1o de Mayo de 2004](https://reader036.vdocumento.com/reader036/viewer/2022062322/5665b4421a28abb57c907b64/html5/thumbnails/28.jpg)
PROBLEMA 1.
Dado un arreglo A de n = 2^k números, y una PRAM con n procesadores {P1, P2, ..., Pn}, se desea calcular la suma S = A(1) + A(2) + ... + A(n). Cada procesador Pi ejecuta el mismo algoritmo.
?
![Page 29: Sistemas Operativos II MC. Daniel Fajardo Delgado INSTITUTO TECNOLÓGICO DE CD. GUZMÁN 1o de Mayo de 2004](https://reader036.vdocumento.com/reader036/viewer/2022062322/5665b4421a28abb57c907b64/html5/thumbnails/29.jpg)
Algoritmo en PRAM
Input: Un arreglo A de orden n = 2^k almacenados en memoria compartida de una PRAM con n procesadores. Las variables locales inicializadas son n y el número de procesador i.
Output: La suma de las entradas de A almacenados en la localidad de compartida S. El arreglo A mantiene sus valores iniciales.
Begin1. read (A(i), a)2. write (a, B(i))3. for h = 1 to log n do
if(i <= n / 2^h) thenbegin
read(B(2i – 1), x)read(B(2i), y)Set z:= x + ywrite(z, B(i))
end4. if i = 1 then write(z, S)
end
![Page 30: Sistemas Operativos II MC. Daniel Fajardo Delgado INSTITUTO TECNOLÓGICO DE CD. GUZMÁN 1o de Mayo de 2004](https://reader036.vdocumento.com/reader036/viewer/2022062322/5665b4421a28abb57c907b64/html5/thumbnails/30.jpg)
![Page 31: Sistemas Operativos II MC. Daniel Fajardo Delgado INSTITUTO TECNOLÓGICO DE CD. GUZMÁN 1o de Mayo de 2004](https://reader036.vdocumento.com/reader036/viewer/2022062322/5665b4421a28abb57c907b64/html5/thumbnails/31.jpg)
Algoritmo en PRAM
Begin1. read (A(i), a) O(1)
u.t.2. write (a, B(i)) O(1)
u.t.3. for h = 1 to log n do O(log n)
u.t.if(i <= n / 2^h) thenbegin
read(B(2i – 1), x)read(B(2i), y)Set z:= x + ywrite(z, B(i))
end4. if i = 1 then write(z, S) O(1) u.t.
end
![Page 32: Sistemas Operativos II MC. Daniel Fajardo Delgado INSTITUTO TECNOLÓGICO DE CD. GUZMÁN 1o de Mayo de 2004](https://reader036.vdocumento.com/reader036/viewer/2022062322/5665b4421a28abb57c907b64/html5/thumbnails/32.jpg)
Cómo sería el BROADCAST ???
![Page 33: Sistemas Operativos II MC. Daniel Fajardo Delgado INSTITUTO TECNOLÓGICO DE CD. GUZMÁN 1o de Mayo de 2004](https://reader036.vdocumento.com/reader036/viewer/2022062322/5665b4421a28abb57c907b64/html5/thumbnails/33.jpg)
PROBLEMA 2. Suma de prefijos (prefix sum)
Sea {x1, x2, ..., xn} un conjunto de elementos y sea “*” una operación binaria asociativa
=> la suma de prefijos S es una secuencia tal que
S = x1 * x2 * ... * xi para 1 <= i <= n
?
![Page 34: Sistemas Operativos II MC. Daniel Fajardo Delgado INSTITUTO TECNOLÓGICO DE CD. GUZMÁN 1o de Mayo de 2004](https://reader036.vdocumento.com/reader036/viewer/2022062322/5665b4421a28abb57c907b64/html5/thumbnails/34.jpg)
Algoritmo en PRAM
Input: Un arreglo de n = 2^k elementos (x1, x2, ..., xn) donde k es un entero no negativo.
Output: La suma de prefijos sumai, para 1 <= i <= n.
Begin1. if n = 1 then{ set sumai:=x1; exit }2. for 1 <= i <= n/2 pardo
set yi := x_{2i-1} * x_{2i}3. Recursivamente, calcula la suma de prefijos de
{y1, y2, ..., y_{n/2} } y se almacenan en z1, z2, ...,z_{n/2}
4. for 1 <= i <= n pardo{i even : set sumai := z_{i/2}i = 1 : set suma1 := x1i odd > 1 : set sumai := z_{(i-1)/2} + xi
}end
![Page 35: Sistemas Operativos II MC. Daniel Fajardo Delgado INSTITUTO TECNOLÓGICO DE CD. GUZMÁN 1o de Mayo de 2004](https://reader036.vdocumento.com/reader036/viewer/2022062322/5665b4421a28abb57c907b64/html5/thumbnails/35.jpg)
TOP500 http://www.top500.org