El presente trabajo propone la investigación e implementación de nuevas estrategias de despacho de tareas distribuidas, con el objetivo de mejorar el desempeño global de programas desarrollados bajo el paradigma de ejecución paralela. Las nuevas estrategias se basan en optimizar el balance de cargas sobre la red utilizada usando estimaciones sobre la carga futura de los nodos del sistema.

El software actualmente disponible para manejar aplicaciones distribuidas no se preocupa en determinar la carga futura de las computadoras de la red. Simplemente despacha las tareas asignándolas a una CPU libre (en el caso de una red dedicada) o a la menos cargada (en redes no dedicadas).

Nuestra propuesta consiste en mejorar las estrategias estándar de despacho de tareas provistas por los lenguajes y bibliotecas para programación paralela, implementando nuevos algoritmos de despacho. Los nuevos algoritmos serán capaces de escoger la Estación de Trabajo (ET) más apropiada para despachar una tarea luego de predecir la carga de los componentes de la red, utilizando información de los datos de carga y técnicas estadísticas de predicción. Las aplicaciones distribuidas existentes podrán tomar ventaja de este nuevo servicio sin modificación alguna, salvo una recompilación.

Una comparación justa entre los diferentes algoritmos de despacho de tareas solamente puede realizarse sobre las mismas condiciones de carga externa. Para realizar la comparación, fue diseñado un programa que permite replicar una carga histórica arbitraria mientras se ejecutan las aplicaciones utilizando las diferentes estrategias de despacho. Los nuevos algoritmos fueron ensayados y comparados en ese entorno para cuantificar la mejora de desempeño sobre las estrategias de despacho disponibles. El desempeño global del sistema desarrollado fue evaluado con modelos numéricos diseñados en el Centro de Cálculo, resultando en mejoras del orden del 6% en tiempo de ejecución en relación con el tiempo requerido por la versión estándar de PVM.

El proyecto aquí descrito se conecta con otros esfuerzos realizados en el Centro de Cálculo orientados a difundir y simplificar el uso de las técnicas de programación paralela y distribuida utilizando componentes de bajo costo en el ámbito científico, académico y comercial.

El documento se organiza como sigue: el capítulo 1 introduce brevemente al lector sobre los objetivos generales y específicos del proyecto. El capítulo 2 está en parte orientado al lector no especialista, introduciendo las definiciones, conceptos y tecnologías asociadas a este proyecto. También se pone a este trabajo en contexto con los antecedentes del equipo de investigación. El capítulo 3 se concentra en la problemática específica del despacho de cargas. Se discute en detalle el proceso lógico que llevó a seleccionar el parámetro de carga más significativo, y los experimentos asociados.

El capítulo 4 describe el trabajo realizado con la serie histórica de cargas, incluyendo recolección y análisis preliminar. Se describen los métodos a implementar en la modelación de las series. El capítulo 5 reseña el ambiente de simulación experimental implementado, sus características así como los resultados específicos a esta simulación. El capítulo 6 analiza los métodos de predicción de la series temporales comparados, las simulaciones realizadas y los resultados obtenidos. En el capítulo 7 se presentan los resultados experimentales obtenidos con los diferentes criterios de despacho. El capítulo 8 resume las conclusiones y propuestas de trabajo futuro, y a continuación se adjunta la bibliografía y anexos.
 
 

Resumen ejecutivo

El proyecto, de nombre "Despacho mejorado de cálculo científico distribuido en redes de computadoras no dedicadas utilizando PVM" fue propuesto y desarrollado por Carlos López (responsable científico del proyecto), Antonio López y Sergio Nesmachnow, en el período Marzo 1998 - Octubre 1999, en el Centro de Cálculo, Facultad de Ingeniería.

Los resultados relevantes obtenidos en el marco de este proyecto comprenden:

El diseño e implementación de nuevos algoritmos de despacho de tareas, integrados al ambiente PVM. Estos algoritmos intentan lograr una mejora en el desempeño de una aplicación distribuida mediante la utilización de información estadística de datos históricos de carga.

El diseño e implementación de algoritmos de predicción de valores futuros de carga, a partir de un conjunto de datos históricos. Alguno de ellos quedaron integrados totalmente al código PVM, y otros sólo parcialmente.

La realización de experimentos preliminares, que mostraron que las tecnologías aplicadas lograron disminuir en un 6,25% el tiempo de cálculo necesario utilizando los criterios estándar de PVM, para el caso de un cálculo científico típico. Este número debe compararse con la mejora alcanzable conociendo perfectamente la carga futura, que es del 14%.

Se comprobó que las diferentes Estaciones de Trabajo (ET) podían agruparse y clasificarse de acuerdo a su patrón de uso, encontrando similitudes muy notorias. Eso permitió utilizar las Redes Neuronales de una máquina sobre otra previamente declarada como "similar" sin perjuicios significativos, y con una obvia economía de cálculo.

Como subproductos del proyecto, se realizaron actividades no mencionadas antes que resultaron en:

• El diseño e implementación de un programa capaz de replicar la carga de una red de computadoras a partir de una serie temporal de datos de carga.
• El estudio de técnicas no tradicionales de modelización y predicción, basadas en Redes Neuronales.

 
Aquí está el informe completo (en formato Word 97)

Para ver el informe completo por este medio haga click aquí.
Para ver el proyecto original por este medio haga click aquí.