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
