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 |