Cálculo en Tiempo Constante del producto de matrices booleanas en PRAM EREW
Héctor, para demostrar que el producto de dos matrices booleanas A y B de tamaño n × n puede calcularse en tiempo constante utilizando una PRAM de escritura común, necesitamos definir el modelo de PRAM que estamos utilizando y establecer cómo se organizarán los procesadores.
La PRAM (Parallel Random Access Machine) es un modelo teórico de cómputo paralelo que consiste en varios procesadores que comparten una memoria común y pueden acceder a ella simultáneamente. Hay varias variantes de PRAM, como EREW (Exclusive Read Exclusive Write), CREW (Concurrent Read Exclusive Write), etc.
Aquí presentaré una idea general para resolver el problema utilizando una PRAM EREW, en la que cada procesador puede leer desde la memoria común de manera exclusiva y escribir de manera exclusiva.
Idea general:
1. Organización de los procesadores:
- Asignaremos un procesador a cada posición de la matriz resultante C. Es decir, habrá n × n procesadores.
2. Cálculo paralelo:
- Cada procesador P_{i,j} calculará el elemento C[i,j] de la matriz resultante como el resultado de la operación lógica AND entre la fila i de la matriz A y la columna j de la matriz B.
C[i,j] = A[i,1] ∧ B[1,j] ∨ A[i,2] ∧ B[2,j] ∨ ... ∨ A[i,n] ∧ B[n,j]
3. Tiempo de ejecución constante:
- Dado que todas las operaciones lógicas y las lecturas de la memoria son operaciones O(1), y cada procesador realiza una cantidad constante de operaciones, el tiempo de ejecución total será constante.
Conclusión:
La idea principal aquí es que cada procesador está calculando un único elemento de la matriz resultante en paralelo. La operación lógica AND y la operación de lectura desde la memoria son operaciones O(1), por lo que, en total, el tiempo de ejecución es constante.
Es importante tener en cuenta que este enfoque se basa en el modelo específico de PRAM que estamos utilizando y en que la lectura y escritura en la memoria común son operaciones atómicas y rápidas.
