Contenido principal
Principios de ciencias de la computación avanzados (AP Computer Science Principles)
Curso: Principios de ciencias de la computación avanzados (AP Computer Science Principles) > Unidad 4
Lección 4: Computación paralela y distribuidaComputación paralela
Una forma de acelerar algunos tipos de algoritmos es usar computación paralela, para distribuir el algoritmo sobre multiples procesadores que corren simultáneamente.
Computación secuencial
El modelo estándar de programación es el de computación secuencial: la computadora ejecuta cada operación del programa en orden, una a la vez.
Considera este programa que procesa imágenes y reporta cuántas son de gatos:
images ← [ "pet1.jpg", "pet2.jpg", "pet3.jpg", "pet4.jpg"]
numCats ← 0
FOR EACH image IN images
{
foundCat ← detectCat(image)
IF foundCat
{
numCats ← numCats + 1
}
}El programa comienza con una lista de nombres de archivos y una variable para almacenar el número de imágenes de gatos, inicializada a 0. Un bucle itera sobre la lista invocando repetidamente a una función que detecta si la imagen tiene un gato y actualiza la variable.
A continuación, una visualización del programa ejecutando sobre cuatro imágenes.
Ahora analicemos el programa más a fondo, anotando en cada operación cuántos segundos tarda y cuántas veces fue llamada.
| Tiempo | Llamadas | Operación |
|---|---|---|
| 3 | 1 | images ← [ "pet1.jpg", "pet2.jpg", "pet3.jpg", "pet4.jpg"] |
| 1 | 1 | numCats ← 0 |
| 1 | 4 | FOR EACH image IN images |
| 10 | 4 | foundCat ← detectCat(image) |
| 1 | 4 | IF foundCat |
| 2 | 4 | numCats ← numCats + 1 |
Nota: los valores en la columna de tiempo son inventados, el tiempo actual variaría basado en la implementación de este pseudocódigo y el hardware en el que corre
Podemos calcular el tiempo total si multiplicamos el número de segundos para cada operación por el número de llamadas y sumamos los resultados. Para este programa, eso sería:
Esta línea de tiempo visualiza el tiempo que tarda la computadora:
Computación paralela
El modelo secuencial asume que solamente una operación puede ser ejecutada a la vez, y eso es cierto para una sola computadora con un solo procesador. Sin embargo, la mayoría de las computadoras modernas tienen procesadores multi-núcleo, donde cada núcleo puede ejecutar operaciones de forma independiente.
Los procesadores multinúcleo pueden aprovechar la computación paralela, un modelo computacional que divide los programas en operaciones secuenciales más pequeñas y las ejecuta en paralelo.
¿Podemos modificar el programa de detección de gatos para que algunas de sus operaciones puedan ejecutarse en paralelo? Sí, solo si hay operaciones que no son dependientes entre sí.
🤔 Dale otro vistazo al programa y mira si puedes identificar operaciones que no necesitan ejecutarse secuencialmente.
Para este programa, podríamos paralelizar las operaciones dentro del bucle, ya que la función
detectCat no depende de los resultados de otras llamadas a detectCat. Esto significa decirle a la computadora que estas líneas de código pueden ser ejecutadas en paralelo. foundCat ← detectCat(image)
IF foundCat
{
numCats ← numCats + 1
}Los mecanismos exactos para paralelizar un programa dependen del lenguaje de programación y entorno computacional específicos, lo cual no exploraremos aquí.
Aquí hay una visualización del programa ejecutando esas operaciones en paralelo:
¿Cuánto tiempo tomará ejecutar el programa ahora? Recuerda el análisis anterior:
| Tiempo | Llamadas | Operación |
|---|---|---|
| 3 | 1 | images ← [ "pet1.jpg", "pet2.jpg", "pet3.jpg", "pet4.jpg"] |
| 1 | 1 | numCats ← 0 |
| 1 | 4 | FOR EACH image IN images |
| 10 | 4 | foundCat ← detectCat(image) |
| 1 | 4 | IF foundCat |
| 2 | 4 | numCats ← numCats + 1 |
Las operaciones no paralelizadas tardan el mismo tiempo que antes:
El tiempo empleado por las operaciones paralelizadas depende del número de procesadores paralelos que ejecutan operaciones a la vez. Si ejecutamos este programa en una computadora con 4 núcleos, entonces cada núcleo puede procesar una de las 4 imágenes, por lo que la porción paralela solo usará el tiempo que toma una sola imagen:
Esta línea de tiempo visualiza el tiempo que tarda una computadora que divide el programa en 4 procesos:
Comparar ejecución secuencial vs. paralela
Una forma de evaluar los beneficios de paralelizar un programa es medir la aceleración: la razón del tiempo que toma ejecutar el programa secuencialmente entre el tiempo que toma ejecutar el programa paralelizado.
Nuestro programa ejemplo de detección de gatos tarda 60 segundos en ejecutar secuencialmente. Cuando se ejecuta en paralelo en cuatro procesadores, y cada imagen requiere 14 segundos, el programa tarda 18 segundos en ejecutar. Calculamos la aceleración al dividir 60 entre 18:
No logramos una aceleración exacta de 4, aún con ese número de procesadores. La porción secuencial inicial todavía tarda el mismo tiempo en ejecutar, incluso con infinitos procesadores. Así, esta porción secuencial inicial limita la máxima aceleración obtenida con computación paralela.
Los programas paralelizados típicamente se ejecutan sobre tamaños de entrada en los miles o millones. Si ejecutamos este programa con miles de imágenes, la parte secuencial inicial tomaría una fracción muy pequeña del tiempo, comparada con la parte paralelizada.
Tiempos de ejecución variables
Las operaciones dentro de segmentos paralelizados del programa pueden no siempre tomar el mismo tiempo, especialmente si procesan entradas del programa.
Por ejemplo, la función
detectCat en nuestro ejemplo puede usar un algoritmo cuyo tiempo varía dependiendo del tamaño o complejidad de la imagen. La operación puede tomar solo 10 segundos para una imagen pero 22 segundos para otra. Esta línea de tiempo visualiza esa situación:
El tiempo total ha aumentado ahora a 30 segundos, ya que la porción paralela tarda tanto como la más larga de las operaciones paralelizadas.
Para compensar el hecho de que a menudo hay variaciones en los tiempos de ejecución, el programa puede ser astuto en la manera de enviar trabajo a los procesadores. En lugar de preasignar tareas a los procesos, puede simplemente enviar la siguiente tarea a cualquier procesador que esté listo y esperando.
Por ejemplo, imaginemos que ejecutamos el programa de detección de gatos con siete imágenes y la operación
detectCat() tardó mucho tiempo en la tercera imagen. El programa no necesita esperar a que esta termine antes de analizar la séptima imagen; en su lugar, puede enviar esta imagen a un procesador que esté libre:🙋🏽🙋🏻♀️🙋🏿♂️¿Tienes alguna pregunta sobre este tópico? Nos encantaría contestarte; ¡simplemente pregunta en el área de preguntas abajo!
¿Quieres unirte a la conversación?
Sin publicaciones aún.