Evaluación de objetivos al planificar y asignar trabajos paralelos en un sistema de multicomputadoras

Objective evaluation to plan and allocate parallel tasks in multicomputer system

En este trabajo se propone un método que realiza una evaluación de cada uno de los objetivos que se contraponen en la planificación y la asignación de los trabajos a ser procesados en un sistema de multicomputadoras en malla 2D, como los tiempos de espera, de procesamiento, de transferencia e inanición de tareas. El método propuesto utiliza un algoritmo de selección dinámica de tareas de la cola de espera para determinar cuáles tareas son susceptibles de ser asignadas en las submallas libres de procesadores del sistema objetivo, una vez que el algoritmo de asignación detecta los procesadores libres en la malla. Para seleccionar los procesadores en donde las tareas serán asignadas y evaluar los objetivos contrapuestos, el método utiliza el algoritmo de la estimación de la distribución, para determinar cuáles son los procesadores que ofrecen las mejores soluciones de asignación en cuanto a los objetivos evaluados, así como también la incidencia que cada uno de ellos tiene en el desempeño del sistema. Los resultados obtenidos en las experimentaciones con el método propuesto muestran una mejoría en los tiempos de procesamiento y de espera de las tareas, en comparación con los resultados que producen las técnicas de asignaciones de tareas: lineal y las curvas de Hilbert.

INTRODUCCIÓN

De las diferentes arquitecturas paralelas desarrolladas, los sistemas de multicomputadoras con arquitecturas en malla, con topologías de interconexión 2D y 3D con fines comerciales y de investigación, han sido dos de las redes más comunes debido a su simplicidad, escalabilidad, regularidad estructural y facilidad de implementación [1-3].

A diferencia de la programación para sistemas secuenciales, los sistemas paralelos deben dividir los problemas (tarea) en subproblemas (subtareas) para permitir la distribución de la carga computacional entre los procesadores libres (recursos computacionales disponibles) [3]. No es fácil descomponer todos los problemas grandes en subproblemas, debido a la dependencia de los datos entre los subproblemas. Debido a esta dependencia los procesadores deben estar comunicados entre sí cuando ejecutan una tarea en forma paralela. Es importante resaltar que el tiempo consumido por la comunicación entre dos procesadores es muy alto comparado con el tiempo de procesamiento. Debido a esto, el esquema de comunicación debe ser planeado cuidadosamente para obtener un algoritmo paralelo eficiente [2, 4].

Una vez realizada la división de un trabajo paralelo, la tarea con sus subtareas son puestas en la cola de espera, donde un algoritmo de planificación determina el orden de ejecución de las mismas, después un algoritmo de asignación de tareas es el responsable de colocar dichas tareas en la malla de procesadores, donde se colocan hasta que terminan su ejecución [1, 5-7].