La
supercomputadora Cray-2 fue la más
rápida del mundo desde 1985 hasta 1989.
La
supercomputadora paralela Blue Gene de IBM.
La computación
paralela es una forma de cómputo en la que muchas instrucciones se
ejecutan simultáneamente,1 operando sobre el principio de que
problemas grandes, a menudo se pueden dividir en unos más pequeños, que luego
son resueltos simultáneamente (en paralelo). Hay varias formas diferentes de
computación paralela: paralelismo a nivel de bit, paralelismo a nivel de
instrucción, paralelismo de datos y paralelismo de tareas.
El paralelismo se ha empleado durante muchos años, sobre todo en la computación
de altas prestaciones, pero el interés en ella ha crecido últimamente debido a
las limitaciones físicas que impiden el aumento de la frecuencia.n. 12Como el consumo de energía —y por
consiguiente la generación de calor— de las computadoras constituye una
preocupación en los últimos años,n. 23 la computación en paralelo se ha convertido
en el paradigma dominante en la arquitectura
de computadores, principalmente en forma de procesadores multinúcleo.n. 34
Las computadoras
paralelas pueden clasificarse según el nivel de paralelismo que admite su hardware: equipos con procesadores multinúcleo y multi-procesador que
tienen múltiples elementos de procesamiento dentro de una sola máquina y
los clústeres, MPPS y gridsque
utilizan varios equipos para trabajar en la misma tarea. Muchas veces, para
acelerar tareas específicas, se utilizan arquitecturas especializadas de
computación en paralelo junto a procesadores tradicionales.
Los programas informáticos
paralelos son más difíciles de escribir que los secuenciales,5 porque la concurrencia introduce
nuevos tipos de errores de software,
siendo las condiciones de carrera los
más comunes. La comunicación y sincronizaciónentre diferentes subtareas son
algunos de los mayores obstáculos para obtener un buen rendimiento del programa
paralelo.
La máxima
aceleración posible de un programa como resultado de la paralelización se
conoce como la ley de Amdahl.
Índice
·
7Notas
Conceptos básicos[editar]
Tradicionalmente,
los programas informáticos se
han escrito para el cómputo en serie. Para resolver un problema, se construye
un algoritmo y se implementa como un flujo
en serie de instrucciones.
Estas instrucciones se ejecutan en una unidad
central de procesamiento en un ordenador. Sólo puede ejecutarse
una instrucción a la vez y un tiempo después de que la instrucción ha
terminado, se ejecuta la siguiente.6
La computación
en paralelo, por el contrario, utiliza simultáneamente múltiples elementos de
procesamiento para resolver un problema. Esto se logra mediante la división del
problema en partes independientes de modo que cada elemento de procesamiento
pueda ejecutar su parte del algoritmo de manera simultánea con los otros. Los
elementos de procesamiento son diversos e incluyen recursos tales como una
computadora con múltiples procesadores, varios ordenadores en red,
hardware especializado, o cualquier combinación de los anteriores.6
El aumento de
la frecuencia fue la razón dominante de las
mejoras en el rendimiento de las computadoras desde mediados de 1980 hasta
el año 2004. El tiempo de ejecución de un programa es
igual al número de instrucciones multiplicado por el tiempo promedio por
instrucción. Manteniendo todo lo demás constante, el aumento de la frecuencia de relojreduce
el tiempo medio que tarda en ejecutarse una instrucción, por tanto un aumento
en la frecuencia reduce el tiempo de ejecución de los programas de cómputo.7
Sin embargo, el
consumo de energía de un chip está dada por la
ecuación P = C × V2 × F, donde P es la potencia, C
es el cambio de capacitancia por ciclo de reloj —proporcional al número
de transistores cuyas entradas cambian—, V
es la tensión,
y F es la frecuencia del procesador (ciclos
por segundo).8Un aumento en la frecuencia aumenta la
cantidad de energía utilizada en un procesador. El aumento del consumo de energía del
procesador llevó a Intel en mayo del 2004 a
la cancelación de sus procesadores Tejas y Jayhawk, este hecho generalmente se
cita como el fin del escalado de frecuencia como el paradigma dominante
de arquitectura
de computadores.9
La ley de Moore es la observación empírica
de que la densidad de transistores en un microprocesador se duplica cada 18 a
24 meses.10 A pesar de los problemas de consumo
de energía, y las repetidas predicciones de su fin, la ley de Moore sigue
vigente. Con el fin del aumento de la frecuencia, estos transistores
adicionales —que ya no se utilizan para el aumento de la frecuencia— se pueden
utilizar para añadir hardware adicional que permita la computación paralela.
Ley de Amdahl y ley
de Gustafson[editar]
Representación
gráfica de la ley de Amdahl. La
mejora en la velocidad de ejecución de un programa como resultado de la
paralelización está limitada por la porción del programa que no se puede
paralelizar. Por ejemplo, si el 10% del programa no puede paralelizarse, el
máximo teórico de aceleración utilizando la computación en paralelo sería de
10x no importa cuántos procesadores se utilicen.
Idealmente, la aceleración a partir
de la paralelización es lineal, doblar el número de elementos de procesamiento
debe reducir a la mitad el tiempo de ejecución y
doblarlo por segunda vez debe nuevamente reducir el tiempo a la mitad. Sin
embargo, muy pocos algoritmos paralelos logran una aceleración óptima. La
mayoría tienen una aceleración casi lineal para un pequeño número de elementos
de procesamiento, y pasa a ser constante para un gran número de elementos de
procesamiento.
La aceleración potencial de un
algoritmo en una plataforma de cómputo en paralelo está dada por la ley de Amdahl, formulada originalmente
por Gene Amdahl en la década de 1960.11 Esta señala que una pequeña porción
del programa que no pueda paralelizarse va a limitar la aceleración que se
logra con la paralelización. Los programas que resuelven problemas matemáticos
o ingenieriles típicamente consisten en varias partes paralelizables y varias
no paralelizables (secuenciales). Si es la fracción de
tiempo que un programa gasta en partes no paralelizables, luego
es la máxima aceleración que se puede
alcanzar con la paralelización del programa. Si la parte secuencial del
programa abarca el 10% del tiempo de ejecución,
se puede obtener no más de 10× de aceleración, independientemente de cuántos
procesadores se añadan. Esto pone un límite superior a la utilidad de añadir
más unidades de ejecución paralelas. «Cuando una tarea no puede divididirse
debido a las limitaciones secuenciales, la aplicación de un mayor esfuerzo no
tiene efecto sobre la programación. La gestación de un niño toma nueve meses,
no importa cuántas mujeres se le asigne».12
La ley de Gustafson es otra ley en
computación que está en estrecha relación con la ley de Amdahl.13 Señala que el aumento de velocidad
con procesadores
es
Supongamos que una tarea tiene dos partes independientes, A y B. B tarda
aproximadamente 25% del tiempo total. Con esfuerzo adicional, un programador
puede hacer esta parte cinco veces más rápida, pero esto reduce el tiempo de
cálculo global por muy poco. Por otro lado, puede que sea necesario poco
trabajo para hacer que la parte A sea doble de rápida. Esto haría el cálculo
mucho más rápido que mediante la optimización de la parte B, a pesar de que B
tiene una mayor aceleración (5x frente a 2×).
Ambas leyes asumen que el tiempo de
funcionamiento de la parte secuencial del programa es independiente del número
de procesadores. La ley de Amdahl supone que todo el problema es de tamaño
fijo, por lo que la cantidad total de trabajo que se hará en paralelo también
es independiente del número de procesadores, mientras que la ley de Gustafson
supone que la cantidad total de trabajo que se hará en paralelo varía
linealmente con el número de procesadores.
Dependencias[editar]
Entender la dependencia de datos es
fundamental en la implementación de algoritmos paralelos.
Ningún programa puede ejecutar más rápidamente que la cadena más larga de
cálculos dependientes (conocida como la ruta crítica),
ya que los cálculos que dependen de cálculos previos en la cadena deben
ejecutarse en orden. Sin embargo, la mayoría de los algoritmos no consisten
sólo de una larga cadena de cálculos dependientes; generalmente hay
oportunidades para ejecutar cálculos independientes en paralelo.
Sea Pi y Pj dos
segmentos del programa. Las condiciones de Bernstein14 describen cuando los dos segmentos
son independientes y pueden ejecutarse en paralelo. Para Pi,
sean Ii todas las variables de entrada y Oi las
variables de salida, y del mismo modo para Pj. P i y Pj son
independientes si satisfacen
·
·
·
Una violación de la primera condición
introduce una dependencia de flujo, correspondiente al primer segmento que
produce un resultado utilizado por el segundo segmento. La segunda condición
representa una anti-dependencia, cuando el segundo segmento (Pj)
produce una variable que necesita el primer segmento (Pi). La
tercera y última condición representa una dependencia de salida: Cuando dos
segmentos escriben en el mismo lugar, el resultado viene del último segmento
ejecutado.15
Considere las siguientes funciones,
que demuestran varios tipos de dependencias:
1: función Dep(a, b)
2: c: = a · b
3: d: = 3 · c
4: fin función
La operación 3 en Dep(a, b) no puede
ejecutarse antes de —o incluso en paralelo con— la operación 2, ya que en la
operación 3 se utiliza un resultado de la operación 2. Esto viola la condición
1, y por tanto introduce una dependencia de flujo.
1: función NoDep (a, b)
2: c: = a · b
3: d: b = 3 ·
4: e: = a + b
5: fin función
En este ejemplo, no existen
dependencias entre las instrucciones, por lo que todos ellos se pueden ejecutar
en paralelo.
Las condiciones de Bernstein no
permiten que la memoria se comparta entre los diferentes procesos. Por esto son
necesarios algunos medios que impongan un ordenamiento entre los accesos tales
como semáforos, barreras o
algún otro método de sincronización.
No hay comentarios:
Publicar un comentario