PRAM es una extensión del modelo del
modelo clásico de computación
secuencial RAM dirigido hacia
computadoras secuenciales.
Una RAM consta de una memoria,
unidad de control, un procesador y un
programa.
El tiempo y el espacio requerido por un
programa diseñado para el modelo RAM se
puede medir de dos formas:
Mediante el criterio de costo uniforme:
en el que cada instrucción RAM requiere
una unidad de tiempo para ejecutarse y
cada registro requiere una unidad de
espacio.
El criterio de coste logarítmico: que
tiene en cuenta que una palabra de
memoria tiene una capacidad de
almacenamiento limitada.
PRAM
PRAM es un modelo de máquina abstracta
propuesto por Fortune y Wyllie, para
diseñar
algoritmos
dirigidos
a
computadoras paralelas.
PRAM se caracteriza porque que elimina el
enfoque
hacia
puntos
como
la
sincronización y la comunicación, para
explotar la concurrencia.
Todos los procesadores están conectados
en paralelo con la memoria global. Esta
memoria es compartida con todos los
procesadores. A esto se le conoce también
como modelo de memoria compartida.
Todos los procesadores trabajan
síncronamente con un reloj común. Cada
procesador es capaz de acceder
(lectura/escritura) a la memoria. La
comunicación entre procesadores es a
través de la memoria.
Esto significa que el dato de un procesador
Pi es comunicado con otro procesador Pj
siguiendo:
El procesador Pi escribe el dato en la
memoria global.
El procesador Pj lee el dado de la memoria
global.
En su forma original consta de: un
conjunto de procesadores {P0, P1,...},
una memoria global, un conjunto de
registros de entrada y un programa finito.
Hablando de Taxonomía de Flynn, PRAM
se puede clasificar hacia máquinas MIMD
(los
procesadores
pueden
estar
ejecutando diferentes instrucciones en un
instante dado, pero todos ellos tardan el
mismo número de ciclos en ejecutarlas).
Cada procesador tiene un
acumulador (A),
una memoria local (Ri),
un contador de programa
(PC)
una bandera (F) que
indica si el procesador
está trabajando o no.
El programa consiste en
una secuencia de
instrucciones.
READ
FORK
HALT
Ejemplo : Reducción paralela
Ejemplo
Dado un arreglo A de n 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.
Características:
 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.
 Comparten una única señal de reloj que permite
ejecutar instrucciones de forma síncrona.
 Resolución de conflictos de acceso concurrente a
una posición de memoria.
En el modelo PRAM existen 4 tipos de arquitecturas,
dependiendo la capacidad de que más de un procesador
pueda leer o escribir a una localidad de memoria.
 EREW Lectura Exclusiva/ Escritura Exclusiva
Exclusive Read Exclusive Write
 CREW Lectura Concurrente/ Escritura Exclusiva
Concurrent Read Exclusive Write
 ERCW Lectura exclusiva/escritura concurrente
Exclusive Read Concurrent Write
 CRCW Lectura concurrente/ escritura concurrente
Concurrent Read Concurrent Write
Desventaja:
Las peticiones simultáneas procedentes
de los diferentes procesadores pueden
ocasionar que alguna de ellas tenga que
esperar (tiempo de latencia).
Ejecución de un programa A en una
PRAM
Se reproducen k copias: A1, A2, …, Ak
Cada paso o unidad de tiempo consta
de:
* Fase de lectura
* Fase de cálculo
* Fase de escritura
 El idea es que el primer procesador activa al
segundo y, en el paso general, el número de
procesadores activos es doblado haciendo que
cada uno de los procesadores activos active a
uno diferente.
 Puesto que al comienzo hay un sólo
procesador activo, la ejecución de un
programa PRAM tiene dos fases:
En la primera es activado el número total de
procesadores requeridos
En la segunda, estos procesadores realizan la
computación paralela ejecutando las sentencias
de asignación interiores en tiempo constante
Las escrituras realizadas por un proceso,
son recibidas por el resto en el orden en
el cual éstas fueron ejecutadas, no
obstante, las escrituras realizadas por
diferentes procesos pueden ser vistas en
órdenes diferentes por todos ellos
EJEMPLO
Extensiones de PRAM
 El modelo APRAM es una variante asíncrona del PRAM. En este
esquema el tiempo de computación es medido en rounds, donde
un round es el tiempo requerido por cada procesador para
ejecutar al menos una instrucción.
 El modelo BPRAM es una variante del PRAM donde las
comunicaciones con la memoria son en bloques de datos en lugar
de escrituras/lecturas de datos individuales.
 En la variante LPRAM cada procesador cuenta con una memoria
local que puede usar de igual manera que usa la memoria global.
En este modelo hay dos latencias diferentes: una será el tiempo
de acceder a la memoria local (se considera de una unidad de
tiempo) y la otra será el tiempo de acceder a la memoria global.
 La variante WPRAM considera una memoria
compartida de dos tipos: una memoria compartida
global, con un tiempo de acceso uniforme para todos
los nodos, y una memoria compartida local donde los
datos compartidos se encuentran en un nodo concreto.
 YPRAM plantea un modelo descomponible
recursivamente en 2 grupos de máquinas, siendo cada
grupo equivalente a una submáquina. Dentro de cada
submáquina los procesos tienen periodos de
computación y periodos de accesos a la memoria
perteneciente a dicha submáquina.
 HPRAM consiste en una jerarquía dinámicamente
configurable de PRAMs síncronas que operan
asíncronamente entre ellas. Al igual que en la variante
YPRAM, se modela una memoria multinivel.
El PRAM reset
Sigue estos pasos:
1. Apaga la computadora.
2. Localiza las teclas de Comando (manzana), Opción (alt), P y
R. Tendrás que presionar estas teclas simultáneamente en el
paso 4. Recomiendo 2 manos .
3. Enciende la computadora.
4. Presiona y mantén presionadas las teclas de ComandoOpción-P-R. Debes presionar esta combinación antes de que
la pantalla gris aparezca.
5. Mantén presionadas las teclas hasta que la computadora se
reinicie y escuches el sonido de inicio por segunda vez.
6. Suelta las teclas.
 En algunos casos lo que se puede perder al
hacer un reset del PRAM son configuraciones
como la fecha y hora de tu computadora. En los
modelos más nuevos esto no sucede.
 Tener en cuenta que en algunos equipos los
ajustes de fecha y hora pueden cambiar. En
cuanto a la PRAM también hay que comentar que
en algunas actualizaciones se reinicia como
proceso normal de la propia actualización, algo
que en ocasiones les extraña a los usuarios pues
ven como tras terminar el proceso y volver a
encender
el
equipo
esos
valores
antes
mencionados les varían.
Exclusive Read, Concurrent Write
Lectura exclusiva / Escritura
concurrente
Durante una unidad de
tiempo, varios procesadores
pueden escribir en
determinadas posiciones de
memoria pero solo un
procesador puede leerlas
Sólo un proceso puede leer y
todos los procesos pueden escribir
en forma simultanea
Puede generar inconsistencia de
información
Puede caer en el dead-lock
(candado mortal)
Dead-lock
Cuando
dos
procesos
están
ejecutándose,
y
requieren
intercambiar recursos entre sí para
continuar.
 Los procesos esperan la liberación
del recurso, que nunca será
realizada; como no hay ningún
resultado, esto conduce a un
estado de dead-lock
EJEMPLO:
Puede ocurrir, en un restaurante, en mesa
circular, si todos quieren tomar el tenedor
de la derecha y, a la vez un cuchillo el de la
izquierda.
La comida terminará en estado de deadlock.
Ejemplo:
Deadlock
 En un puente donde sólo exista un carril pero se
reciban autos de ambos carriles, es decir, que
permita el flujo en ambos sentidos, si en algún
momento ambos autos quieran cruzar al mismo
tiempo se encontrarán en la situación de que
ninguno de los dos podrá pasar, por lo cual se
detendrá el flujo hasta que alguno de los dos
restaure su posición, es decir, que alguno de los
dos retroceda y deje pasar al otro.
Ejemplo: Deadlock
 Dos procesos desean imprimir cada uno un enorme
archivo en cinta. El proceso A solicita el permiso para
utilizar la impresora, el cual se le concede. Es entonces
cuando el proceso B solicita permiso para utilizar la
unidad de cinta y se le otorga. El proceso A solicita
entonces la unidad de cinta, pero la solicitud es
denegada hasta que B la libere. Por desgracia, en este
momento, en vez de liberar unidad de cinta, B solicita la
impresora. Los procesos se bloquean en ese momento y
permanecen así por siempre.
Protocolo de arbitraje
 Resolución de conflicto por igualdad (ECR). El valor a escribir
es igual en todos los procesadores.
 Resolución de conflicto por prioridad (PCR). El que tiene el
identificador de mayor prioridad.
 Resolución de conflicto arbitrario (ACR). Sólo uno logra
escribir.
 Combining PRAM. El dato a escribir es una combinación
lineal de todos.
 Weak. Puede escribir simultáneamente en la misma posición,
sólo si el valor que escribe es un 0.
 Strong. El valor que se escribe es el mayor (o de forma
equivalente el menor).
Ejemplo: ERCW
 El presente ejemplo se basa en la arquitectura
ERCW que versa sobre la múltiple escritura y
exclusiva lectura, se tiene un jefe de
departamento que desea conocer el reporte
mensual de sus empleados, en los que cada
empleado realiza su aporte y al final todos
generan el reporte para el jefe, sin embargo,
sólo él puede hacer la lectura del mismo y
hasta que lo termine de revisar, alguien más
podrá observarlo, por ejemplo el dueño de la
compañía o los socios.
Preguntas:
Descargar

pram - WordPress.com