Algorítmica paralela
Modelos ideales de una implantación paralela
PRAM
De circuitos
Redes
Compleijidad de los algoritmos paralelos
Métricas para determinar su desempeño
Modelos ideales de una implantación paralela
Se consideran a las computadoras sin restricción
En el número de procesadores
En el acceso físico a la memoria para leer o escribir datos
Modelos ideales de una implantación paralela
Con los modelos se obtiene:
Las partes o segmentos que se pueden ejecutar en paralelo
La dependencia de los datos en el proceso de cálculo
El tiempo ideal de la ejecución paralela
El número de procesadores requeridos para alcanzar ese tiempo de ejecución ideal.
Modelo PRAM (Parallel Random Access Machine)
Es una máquina ideal de p procesadores con una memoria global.
Cada procesador puede realizar en un ciclo:
una lectura
una escritura
una operación de cómputo.
Modelo PRAM (Parallel Random Access Machine)
En el modelo de memoria global compartida se debe de especificar cómo se hacen las lecturas y escrituras concurrentes en la misma localidad.
Lectura exclusiva (ER)
Escritura exclusiva (EW)
Lectura concurrente (CR)
Escritura concurrente (CW)
Modelo PRAM (Parallel Random Access Machine)
Los modelos PRAM se clasifican de acuerdo a las formas de actualización de la memoria, en:
EREW (Exclusive Read, Exclusive Write)
ERCW (Exclusive Read, Concurrent Write)
CREW (Concurrent Read, Exclusive Write)
CRCW (Concurrent Read, Concurrent Write)
Modelo PRAM (Parallel Random Access Machine)
Modelo PRAM CRCW
Común: Todas las escrituras simultáneas almacenan el mismo valor en la localidad de memoria seleccionada.
Arbitraria: Cualquiera de los valores escritos permanece, aquí no se puede saber que procesador escribió de los que intentaron.
Prioritaria: El procesador de mayor prioridad será el que logrará escribir en la memoria.
Modelo PRAM (Parallel Random Access Machine)
Encontrar el número mayor del arreglo A={5, 6, 9, 2, 9, 7, 8, 3} con PRAM-CRCW
Seudocódigo Pasos de ejecución
n = longitud de (A) (1)
en paralelo i = 0 … n-1 hacer
m[i] = V (1)
en paralelo i, j = 0 … n-1 hacer
sí A[i] < A[j] entonces m[i] = F (2)
en paralelo i = 0 … n 1 hacer
sí m[i] = V entonces (1)
max = A[i] (1)
Página siguiente |