pram
TRANSCRIPT
UNICIENCIA
INGENIERIA INFROMATICA
DOCENTE CLAUDIA LORENA DIAZ
RAM La Máquina de Acceso Aleatorio
(Random Access Machine) consta de una
memoria, unidad de control, un procesador y
un programa.
El modelo de cómputo secuencial aleatorio RAM consiste de:
1. Una memoria con N posiciones. N es un número arbitrario grande, pero
finito. Cada posición de memoria almacena un dato al que puede
accederse aleatoriamente usando una dirección única.
2. Un procesador operando bajo el control de un algoritmo secuencial. El
procesador es capaz de cargar y almacenar datos en la memoria, y
ejecutar operaciones aritméticas y lógicas básicas.
3. Una Unidad de Acceso a la Memoria MAU cuyo propósito es crear un
camino desde el procesador, a una posición arbitraria de la memoria.
Cada vez que el procesador desea leer o escribir a una posición de
memoria, proporciona a la MAU la dirección de dicha posición. Usando
esta dirección, se establece una conexión directa entre el procesador y
la posición de memoria.
Cada paso del algoritmo consiste de (hasta) tres fases:
1. Una fase de LECTURA, durante la cuál el procesador lee un dato desde
una posición arbitraria de la memoria en uno de sus registros internos,
2. Una fase de CÓMPUTO, durante la cuál el procesador realiza una
operación básica sobre los contenidos de uno o dos de sus registros, y
3. Una fase de ESCRITURA, durante la cuál el procesador escribe el
contenido de un registro en una posición de memoria arbitraria.
El tiempo y el espacio requerido
por un programa diseñado para
el modelo RAM se mide Mediante
el criterio de costo uniforme: en elque cada instrucción RAM
requiere una unidad de tiempo
para ejecutarse y cada registro
requiere una unidad de espacio.
T (n)
PRAM es un modelo de máquina abstractapropuesto, para diseñar algoritmos paralelos.
La Máquina Paralela de Acceso Aleatorio Consistede:
1. Un número de procesadores idénticos P[1], P[2], ...P[n] (del mismo tipo usado en la RAM) donde N es unnúmero arbitrario grande, pero finito.
2. Una memoria común (RAM) con M posiciones. M esen un número arbitrariamente grande pero finito, talque M >= N. Los N procesadores comparten esta
memoria común.
3. Una unidad de acceso a memoria (MAU) quepermite a los procesadores obtener acceso a la
memoria.
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 P1
es comunicado con otro procesador P2
siguiendo:
El procesador P1 escribe el dato en la
memoria global.
El procesador P2 lee el dado de la
memoria global.
La memoria compartida almacena datos y sirve como un medio de
comunicación entre los procesadores. Dos procesadores P[i] y P[j] que
deseen comunicarse pueden usar la memoria compartida como un pizarrón
de mensajes: por ejemplo, P[i] escribe un dato en la memoria (esto es,
publica algo en el pizarrón) y luego P[j] lee el dato. El modelo permite a
cada procesador tener su propio algoritmo.
Una aplicación interesante y útil de la PRAM ocurre cuando todos los
procesadores ejecutan el mismo algoritmo de forma síncrona. Este modo de
operación resulta sencillo para el diseño y análisis de algoritmos eficientes
para una multitud de problemas.
Cada paso de un algoritmo para la PRAM consiste de (hasta) tres fases:
1. Una fase de LECTURA, durante la cuál (hasta) N procesadores leen
simultáneamente desde (hasta) N posiciones de memoria. Cada procesador
lee una posición de memoria y almacena el valor obtenido en un registro
local,
2. Una fase de CÁLCULO, durante la cuál (hasta) N procesadores realizan
operaciones aritméticas o lógicas básicas sobre sus datos locales, y
3. Una fase de ESCRITURA, durante la cuál (hasta) N procesadores escriben
simultáneamente en (hasta) N posiciones de memoria. Cada procesador
escribe el valor contenido en un registro local en a lo sumo una posición de
memoria.
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.
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.
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.
