PRAM

PRAM

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.

PRAMPRAM 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.

READFORK HALT

Ejemplo : Reducción paralela

EjemploDado 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 ExclusivaExclusive 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 concurrenteConcurrent 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 PRAMSe 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

El PRAM reset

Es un procedimiento para borrar los valores actuales de ciertas memorias y devolverle los valores predeterminados de fábrica. Esto es muy necesario cuando se cree que algunos de los valores se han corrompido.

La PRAM es un área de la memoria que guarda la siguiente información:Ajuste del reloj alarmaUbicación de la impresora serieVelocidad de repetición de tecladoRetardo de repeticiónVolumen del altavozSonido de Atención (pitido)Tiempo de parpadeo (velocidad) del punto de inserción Escala del ratón (velocidad del ratón)Disco de arranqueFrecuencia de parpadeo del menúProfundidad del monitor

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 Comando-Opció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.

ERCW

Exclusive Read, Concurrent WriteLectura 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-lockCuando 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:

¿Cuál es la función del PRAM reset? Por que se menciona que el modelo ERCW puede

generar inconsistencia de información? Describe que entiendes por

interbloqueo ¿Como ejemplificarías el estado Dead-look en un

ejemplo ?

Explica mediante un ejemplo la arquitectura ERCW del modelo PRAM.

Dentro de los protocolos de arbitraje que se mencionaron en la arquitectura ERCW menciona una situación computacional en la que alguno de estos protocolos sea utilizado. (elige al menos dos protocolos)