Se dice que un software exhibe paralelismo escalable si puede hacer uso de procesadores adicionales para resolver problemas más grandes, es decir, este término se refiere al software para el cual se cumple la ley de Gustafson . Considere un programa cuyo tiempo de ejecución está dominado por uno o más bucles, cada uno de los cuales actualiza cada elemento de una matriz; por ejemplo, el siguiente cálculo de la ecuación de calor en diferencias finitas :
para t := 0 a T hacer para i := 1 a N-1 hacer nuevo(i) := (A(i-1) + A(i) + A(i) + A(i+1)) * .25 // diferencia hacia adelante explícita con R = 0,25 fin para i := 1 a N-1 hacer A(i) := nuevo(i) fin fin
En el código anterior, podemos ejecutar todas las iteraciones de cada bucle "i" simultáneamente, es decir, convertir cada una de ellas en un bucle paralelo . En tales casos, a menudo es posible hacer un uso efectivo del doble de procesadores para un problema de tamaño de matriz 2N que para un problema de tamaño de matriz N. Como en este ejemplo, el paralelismo escalable es típicamente una forma de paralelismo de datos . Esta forma de paralelismo es a menudo el objetivo de la paralelización automática de bucles .
Los sistemas informáticos distribuidos y las arquitecturas de acceso a memoria no uniforme suelen ser los más fáciles de escalar a grandes cantidades de procesadores y, por lo tanto, parecerían un objetivo natural para el software que exhibe paralelismo escalable. Sin embargo, las aplicaciones con paralelismo escalable pueden no tener un paralelismo de grano suficientemente grueso para ejecutarse de manera efectiva en tales sistemas (a menos que el software sea vergonzosamente paralelo ). En nuestro ejemplo anterior, el segundo bucle "i" es vergonzosamente paralelo, pero en el primer bucle cada iteración requiere resultados producidos en varias iteraciones anteriores. Por lo tanto, para el primer bucle, la paralelización puede implicar una amplia comunicación o sincronización entre procesadores y, por lo tanto, solo dar como resultado una aceleración neta si dichas interacciones tienen una sobrecarga muy baja, o si el código se puede transformar para resolver este problema (es decir, mediante la optimización combinada de localidad escalable /paralelismo escalable [1] ).