Planificación y asignación de tareas en un sistema de multicomputadoras usando algoritmos evolutivos multiobjetivo

Abstract

RESUMEN La asignación de tareas en un sistema de multicomputadoras, ha sido un problema tratado con diferentes estrategias que buscan optimizar el uso de los procesadores, sin utilizar métodos de planificación previa de tareas en la cola, produciendo, por tanto largos tiempos de respuesta a los trabajos que esperan por ejecutarse; las investigaciones realizadas se basan en solucionar un solo problema, tal como: optimización de recursos, minimización de costos de comunicación o minimización de la fragmentación externa, pero no buscan conjuntar los diferentes objetivos que tanto la planificación y la asignación presenta. En este trabajo abordamos el problema de la planificación de tareas y el problema de la asignación de tareas en un sistema de Multicomputadoras con arquitectura en malla 2D. La propuesta de solución a este problema, establece como primer paso la identificación de los distintos objetivos involucrados en ambos problemas. En un segundo paso, se plantean un algoritmo de planificación y un algoritmo de asignación de tareas; a través de una búsqueda en la cola de espera, el primer algoritmo realiza una planificación previa a la asignación para identificar la lista de tareas que caben en la malla, y el segundo es un algoritmo de distribución marginal univariante (UMDA Univariate Marginal Distribution Algorithm) para identificar las mejores asignaciones en la malla de procesadores mediante una asignación cuadrática dinámica. Ambos algoritmos permiten una evaluación de los cinco objetivos propuestos, para determinar el frente de Pareto y obtener la mejor planificación de las tareas en la cola de espera, y de esta forma elegir la mejor asignación en la malla de procesadores. Las fases de experimentación del presente trabajo son dos: la primera experimentación es, para obtener los resultados al aplicar la evaluación de los cinco objetivos de manera aislada con diferentes cargas de trabajo en el sistema objetivo, y también para realizar una comparación del método propuesto con dos de los métodos más comunes de asignación de tareas: la asignación lineal y el método de curvas de Hilbert, y una segunda experimentación, presenta un proceso de comparación de las diferentes funciones objetivo, lo que permite evaluar de manera conjunta el problema multiobjetivo. A través de esta evaluación se crea el frente de Pareto que permite realizar una comparación de los resultados de todas las funciones y elegir la que presente los mejores resultados para realizar la asignación en la malla de procesadores. Los resultados obtenidos, que se explican de manera detallada en el capítulo de conclusiones, muestran que el problema debe tratarse como un problema multiobjetivo dinámico, el cual presenta diferentes entornos cada vez que se realiza una planificación y asignación de las tareas en un sistema paralelo.

ABSTRACT Task assignment of a multi-computer system is a problem that has been treated by using di_erent strategies, that look to optimize the use of the processors without using previous task planning in the queue, that causes long wait times in their execution. The recents researches are based on solving one problem at a time, for example; optimizing resources, minimizing costs and communication or minimizing external fragmentation. However, they do not aim to coordinate di_erent objectives, where as planning and assignment do. In this investigation we address the problem of planning and task assignment of a multicomputer system that uses a 2D architectural mesh. The proposed solution to this problem establishes the identi_cation of the distinct objectives that are involved as the _rst step, that in which is de_ned as the following points: 1. Minimize the number of allocations to the processor mesh that carries out the task allocation algorithm. 2. Minimize the task wait time in the queue. 3. Maximize the use of the processor meshes, or in other words, diminish the percentage of processors that remain free after the assignment algortihm has placed one or more tasks in the processor mesh (external fragmentation). 4. Diminish task starvation. Try to avoid a discrimination in the assignment of tasks that require a large amount of processors (large tasks), this happens because tasks that require only a small amount of processors (small tasks) are being continually assigned. 5. Maximize the adjacency between processors, (assign coordination of free processors to those which are closest) in order to minimize the communication route distance and there by avoid interference between them, ideally to obtain a solid parallel algorithm that diminishes communication time and maximizes processing times. Step two. A planning algorithm and a task assignment algorithm are planted by means of a search engine within the queue. The _rst algorithm carries out a planning previous to the assignment, to identify the list of tasks that _t within the mesh. The second one, is a Univariate Marginal Distribution Algorithm (UMDA) that identi_es the best assignments in the mesh processors, by means of a quadratic in the mesh processors by means of a quadratic dynamic assignment. Both algorithms allow for an evaluation of _ve proposed objectives in order to determine the Pareto front, and to obtain the best planning of the tasks in the queue. In this form, they are able to choose the best assignation within the processor mesh. The experimental phases of the present investigation are the following two: the _rst, is to obtain the application results of the _ve objectives in an isolated manner, using di_erent work loads in the objective system and to also carry out a comparison of the method, using two of the most common task assignment methods. The lineal assignment and Hilbert's curve method allow us to show that: 1. Previous plannings can be carried out, the execution ow is agilized and ingression of tasks are made into the queue. 2. We can see that there is a quadratic task assignment within the processor mesh and that external fragmentation can be diminished using an evolutionary algorithm. 3. A di_erent planning policy is used than that of the FIFO, this produces the initiation of tasks that should be treated with a strategy that comes from within the algorithm, to avoid a large number of tasks being put into the initiation. A second experiment presents comparison process of the di_erent objective functions, which allows the multiobjective problem to be evaluated in a coordinated way. Through this evaluation the Pareto front is created, that allows us to carry out a comparison of the results of all the functions, and to be able to choose the one that gives us the best results in order to carry out the assignment within the processor mesh