Técnicas estándares para paralelismo anidados de datos

Abstract

Desarrollar programas paralelos no es una tarea simple [Gar95]. Dependiendo del problema a paralelizar, distintos tipos de paralelismo pueden ser considerados. Los tipos de paralelismo mas comunes son el paralelismo de Datos y el paralelismo de Tareas o de Control [Akl89] [Qui94] [Fos94]. Cada uno de ellos tiene sus ventajas. El paralelismo de Datos es uno de los esfuerzos más exitosos para introducir paralelismo explícito en lenguaje de alto nivel. Este tipo de paralelismo es conveniente particularmente por dos razones: es fácil de programar y en problemas de gran tamaño escala muy bien. Si bien varias implementaciones de lenguajes de datos paralelos existen, la mayoría se centra en la explotación del paralelismo de datos no estructurado, es decir en el paralelismo chato. Por su parte el paralelismo de Tareas es más eficiente y adecuado en problemas con estructura de datos irregulares. Combinar ambos tipos de paralelismo implica tener un lenguaje con la capacidad de realizar invocaciones paralelas anidadas. Esta capacidad implica la combinación, por un lado de la facilidad de programación sobre un modelo de datos paralelo y por el otro de la eficiencia del modelo de paralelismo de control en la ejecución sobre estructuras de datos irregulares. Este tipo de paralelismo se llama Paralelismo Anidado de Datos [Ble94] [Ble96] y se lo puede considerar una extensión del paralelismo de datos estándar ya que se le suma a éste la capacidad de anidar invocaciones paralelas. Dicho paralelismo, entonces, combina la habilidad de aplicar una función en paralelo sobre cada elemento de una colección de datos y la habilidad de anidar tales llamadas recursivas. La línea de investigación está centrada en la determinación de metodologías o técnicas para desarrollar programas paralelos que apliquen paralelismo anidado de datos en algún lenguaje paralelo [Gon00a] [Gon00b]. Para lograr establecer una metodología adecuada, es preciso considerar en primer lugar el modelo de computación paralela que se aplica y en segundo lugar el lenguaje paralelo utilizado.