Details

Algoritmos de asignación basados en un nuevo modelo de representación de programas paralelos

by Roig Mateu, Concepció

Abstract (Summary)
En el momento de ejecutar una aplicación paralela, el programador (o el usuario) se enfrenta a decisiones importantes para reducir el tiempo de ejecución global, tales como cuántos procesadores ha de usar para ejecutar la aplicación y, dado un número de procesadores, cómo distribuir las tareas de la aplicación aprovechando al máximo su capacidad de concurrencia. Al problema de resolver la distribución de las tareas de una manera global se le conoce como el problema del mapping. En la literatura existen dos formas distintas de abordar el problema del mapping en función del conocimiento que se tiene de la aplicación. Cuando el comportamiento de la aplicación es conocido (o predecible) a priori, la asignación se realiza de forma estática (antes de la ejecución), y las tareas se ejecutan en el procesador asignado hasta que finalizan. Por el contrario, cuando el comportamiento de la aplicación no es predecible, la asignación se realiza de forma dinámica, y las tareas pueden cambiar de procesador durante la ejecución. En el presente trabajo nos centramos en el proceso de mapping estático. Para la realización de este proceso, el programa paralelo se suele representar mediante un modelo de grafo de tareas ponderado, que resume las características más relevantes estimadas del comportamiento de la aplicación. En función del tipo de aplicación, en la literatura se utilizan principalmente dos modelos de grafo. Para aplicaciones cuyas tareas se comunican únicamente por el principio y el final, el modelo, denominado TPG (Task Precedence Graph), refleja las comunicaciones y precedencias entre las tareas y el orden parcial de ejecución de las mismas. Cuando se trata de aplicaciones cuyas tareas tienen comunicaciones en cualquier punto, e incluso comunicaciones bidireccionales, en la literatura se utiliza un modelo simplificado, denominado TIG (Task Interaction Graph), en el que no se contemplan las precedencias y se asume que todas las tareas pueden ser simultáneas. Ahora bien, en los entornos actuales de paso de mensajes, el programador no está sujeto a ninguna restricción en cuanto a la ubicación de las primitivas de comunicación dentro de las tareas. Además, debido al tipo de problemas que se resuelven computacionalmente, existe en los últimos años un creciente interés en el desarrollo de aplicaciones formadas por un conjunto de tareas que realizan distintas funciones y que coordinan su ejecución mediante intercambios de información en cualquier punto dentro de las mismas. Para modelar el comportamiento de las aplicaciones con paralelismo de tareas, con un patrón de interacciones entre tareas arbitrario, se propone un nuevo modelo de grafo, denominado Temporal Task Interaction Graph (TTIG). Dicho modelo incluye un nuevo parámetro, denominado grado de paralelismo, que indica la máxima capacidad de concurrencia de las tareas que se comunican, en función de las dependencias provocadas por dichas comunicaciones. A partir del comportamiento obtenido de la aplicación, se propone un mecanismo para determinar las cotas teóricas mínima y máxima sobre el número de procesadores necesario para realizar su ejecución en un tiempo mínimo. A partir del modelo TTIG se definen nuevas políticas de mapping de distintas complejidades que realizan las asignaciones de tareas teniendo en cuenta la posibilidad de concurrencia entre las mismas que indica el grado de paralelismo. En los entornos actuales de paso de mensajes PVM y MPI, la política de mapping que se usa por defecto es una distribución de las tareas basada en el orden de activación de las mismas. Dada la simplicidad de este mecanismo, dichos entornos se mejoran integrando un proceso automático para la extracción del grafo TTIG y para aplicar una política de mapping basada en dicho modelo.
This document abstract is also available in English.
Bibliographical Information:

Advisor:Ripoll Aracil, Ana

School:Universitat Autónoma de Barcelona

School Location:Spain

Source Type:Master's Thesis

Keywords:401 departament d informatica

ISBN:

Date of Publication:07/24/2002

© 2009 OpenThesis.org. All Rights Reserved.