En esta página, aprenderás cómo la ejecución de múltiples programas en paralelo puede reducir el tiempo total que se tarda en ejecutar un algoritmo.
En Snap!, estás acostumbrado a ver un montón de programas que se ejecutan de forma independiente, que pueden o no estar asociados con diferentes objetos. Esto es una especie de computación en paralelo. Así que, si tuviéramos un ordenador diferente para cada objeto, eso sería el verdadero paralelismo. Tal como es, solo hay un ordenador, y divide su atención entre los procesos ejecutando un poco de uno y luego ejecutando un poco del siguiente. Específicamente, cambia en la parte inferior de los bucles (por siempre, repetir, etc.).
Esta sección cubre dos modelos de computación:
Puedes comparar la eficiencia de dos soluciones algorítmicas diferentes a un problema comparando el tiempo que les toma realizar la misma tarea.
El tiempo de ejecución de un algoritmo secuencial es la suma de los tiempos de ejecución de todos sus pasos.
cuando yo recibo ocurren en paralelo, no una después de la otra.
Transmitir y esperar hasta que todas las tareas que comenzaron han terminado.
Computación distribuida (distributed computing) es una forma de computación paralela que utiliza múltiples computadoras (tal vez incluso se extienda por todo el mundo).
Escribir un programa que no hace nada más que esperar es, por supuesto, poco realista, pero lo que es realista es que en la mayoría de los problemas, no hay una solución que sea puramente paralela. Alguna parte de la computación tiene que hacerse de forma secuencial. En la pregunta previa, la parte secuencial es modelada por esperar 6 segs. El paralelismo con este tonto ejemplo se siente trivial, pero imagina que trabajas para Google. Millones de consultas de búsqueda y ediciones de páginas web han ocurrido hoy en día, y es tu trabajo tener que procesarlos. Si no tuvieran enormes instalaciones de servidores con miles de computadoras en cada edificio, no podrían seguir el ritmo en absoluto. La informática distribuida te permite escalar a problemas muy grandes.
Como un ejemplo más específico, supongamos que quieres saber la longitud media de las palabras de una lista de 100.000 palabras. Puedes dividir la tarea entre varias computadoras (uno para cada letra de inicio). Cada computadora suma las longitudes de todas las palabras que se le asignan (todas las palabras "A", todas las palabras "B", etc.). Luego una computadora tiene que sumar los 26 resultados parciales y dividirlos por el número total de palabras para encontrar el promedio. Para calcular el tiempo de ejecución de esta solución paralela, añadirías el tiempo de ejecución de la parte paralela más larga (el tiempo de ejecución de la letra con más palabras) al tiempo de ejecución de la parte secuencial (sumando los 26 resultados parciales y dividiendo la suma por el número total de palabras).
Debido a que cada cómputo incluye una porción secuencial, hay un límite de cuánto puede acelerar una tarea al agregar procesadores.
Un procesador (processor) es una pieza de circuitos dentro de una computadora que procesa las instrucciones de los programas de computación.
Créditos de la imagen: Wikipedia usuario Solipsist
| Número de procesadores | Tiempo total requerido | Tipo de solución |
|---|---|---|
| 1 | 61 minutos (1 hr + 1 min) | solución secuencial |
| 2 | 31 minutos (30 min + 1 min) | soluciones paralelas |
| 3 | ||
| 4 | ||
| 10 | ||
| 20 | ||
| 30 | ||
| 60 | ||
| 120 | ||
| 240 | ||
| 480 |
¿Cuántos procesadores crees que vale la pena tener para este problema?
Los programadores se refieren a la aceleración (speedup) de la solución paralela para describir cuántas veces más rápido se compara la solución paralela con la solución secuencial:
\text{aceleración} = \frac{\text{tiempo secuencial}}{\text{tiemo paralelo}}
El hardware de la computadora es muy fiable; es raro que se averíe mientras estás ejecutando un programa. Pero en la computación distribuida con decenas de miles de computadoras trabajando en el mismo problema, es probable que uno de ellos falle. (Si la probabilidad de que una computadora falle durante la ejecución de un programa es de 0,0001 y utilizas 10.000 computadoras, entonces la probabilidad de que uno de ellos falle es de alrededor de 0,368, aproximadamente ¡un tercio de las veces!) Por lo tanto, el software tiene que compensar comprobando que las máquinas están funcionando y reasignando las tareas de una computadora que ha fallado a una que funciona.
Además, cuando se hacen las cosas en paralelo, los procesos paralelos pueden interferir entre sí.
Si una persona retira dinero de un cajero automático al mismo tiempo que otra persona en un cajero automático diferente retira dinero de la misma cuenta, podrías encontrarte con una situación como la siguiente:
 |
Cajero automático 1 | Cajero automático 2 |
|---|---|---|
| Busca el saldo ($100) | ||
| Busca el saldo ($100) | ||
| Revisa si la cantidad requerida ($40) está disponible | ||
| Ajusta el saldo ($60) | ||
| Reparte el dinero | ||
| Revisa si la cantidad requerida ($20) está disponible | ||
| Ajusta el saldo ($80) | ||
| Reparte el dinero |
Debido a que el cajero automático 2 cambió el saldo de la cuenta después de que el cajero automático 1 buscó el saldo, el cajero automático 1 no sabía que el saldo había sido cambiado. La cuenta bancaria terminó con un saldo de 80 dólares, aunque empezó con 100 dólares y se retiró un total de 60 dólares.
Por estas y otras razones, un programa paralelo es más difícil de escribir y depurar que un programa secuencial.
Identifica algunos beneficios y desafíos potenciales de la computación paralela y distribuida.
Transmitir y esperar espera hasta que todas las tareas que comenzó han terminado.