Despacho Mejorado de Cálculo Científico Distribuido en Redes de Computadoras
No Dedicadas Usando PVM
 
 
 
 

Dr. Ing. Carlos López Vázquez
Ing. Antonio López Arredondo
Bach. Sergio Nesmachnow Cánovas

Colaboraron:
Ing. Nelson Calero
Bach. Felipe Mendívil
 

Informe final
Octubre 1999
Financiado por la Comisión Sectorial de Investigación Científica
Universidad de la República
 
 


Índice

    Capítulo 1: Introducción *
                1.1 – Procesamiento paralelo y distribuido *
                1.2 – Introducción a los objetivos generales del proyecto *
                1.3 – Objetivos específicos del proyecto *
                1.4 – Especificación de las preguntas que planteó responder el proyecto *
                1.5 – Actividades específicas *

    Capítulo 2: Procesamiento Paralelo en Redes de Computadoras *
                2.1 – Computación Paralela *
                2.2 – Tipos de Máquinas Paralelas *
                        2.2.1 - Memoria Compartida *
                            2.2.2 - Memoria Distribuida *
                            2.2.3 - Redes de Computadoras *
                2.3 – Paradigmas de Programación Paralela *
                2.4 – Antecedentes en el Centro de Cálculo *
                            2.4.1 - Creación de máquinas paralelas *
                            2.4.2 - Desarrollo de Aplicaciones Distribuidas *
                            2.4.3 - Mejoras de Herramientas de Desarrollo *
                2.5 – Conclusiones *

    Capítulo 3: El problema del Balance de Cargas *
                3.1 – Balance de cargas en una red *
                3.2 – Parámetros relevantes en la determinación de la carga de una ET *
                3.3 – Análisis del consumo de CPU como factor preponderante en la demora de ejecución. *
                3.4 – Otros parámetros de carga *

    Capítulo 4: Análisis y modelización de datos históricos de carga *
                4.1 – Recolección de datos de carga *
                4.2 – Análisis y modelización de datos *
                        4.2.1 - Presentación *
                            4.2.2 - Análisis individual de datos para cada componente de la red *
                            4.2.3 - Análisis de correlaciones entre parámetros de carga. *
                            4.2.4 - Análisis de correlaciones entre valores de carga de diferentes equipos de la red. *
                4.3 – Métodos de predicción basados en Series Temporales *
                        4.3.1 - Introducción *
                            4.3.2 - Métodos determinísticos lineales *
                            4.3.3 - Métodos no lineales (basados en redes neuronales artificiales) *

    Capítulo 5: Replicación de Datos de Carga *
                5.1 – Necesidad de replicar la carga de la red *
                5.2 – Universo de parámetros factibles de ser replicados *
                5.3 – Elección de parámetros a replicar *
                5.4 – Proceso de réplica *
                5.5 – Réplica de CPU *
                            5.5.1 - Introducción *
                            5.5.2 - Lista de procesos *
                            5.5.3 - Único proceso *
                5.6 – Réplica de disco *
                5.7 – Réplica de red *
                5.8 – Conclusiones *

    Capítulo 6: Métodos de predicción de la serie temporal de datos de carga *
                6.1 – Introducción *
                6.2 – Método de predicción naive *
                6.3 – Método de predicción basado en el Método de Mínimos Cuadrados *
                6.4 – Métodos basados en Redes Neuronales Artificiales (ANN). *
                        6.4.1 - Caso univariado *
                            6.4.2 - Caso multivariado *
                            6.4.3 - Conclusiones *
                6.5 – Pruebas de los algoritmos de predicción *

    Capítulo 7: El desempeño de los diferentes métodos de despacho *
                7.1 – Nuevos algoritmos de despacho de tareas *
                        7.1.1 - Introducción *
                            7.1.2 - Descripción de los nuevos algoritmos de despacho *
                            7.1.3 - Integración al sistema PVM *
                7.2 – Experimento de evaluación del desempeño de los nuevos métodos de despacho *
                        7.2.1 - Introducción *
                            7.2.2 - Ensayo preliminar *
                            7.2.3 - Ensayo de fuerza *

    Capítulo 8: Conclusiones y trabajo futuro *
            8.1 – Conclusiones *
            8.2 – Trabajo futuro *

    Bibliografía *

    Anexo I  -   Cronograma de actividades
    Anexo II -  Towards Proactive Network Load Management For Parallel Distributed Programming
    Anexo III - Artificial Replication of Network Load Environment for Distributed Algorithms Comparison
 
 


Resumen

 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.

  •  

    Reconocimientos

    Nelson Calero colaboró en el diseño e implementación del programa replicador de carga y Felipe Mendivil colaboró en el diseño e implementación de los algoritmos de despacho. Elías Kaplan es el autor de los programas utilizados en la etapa de ensayo de los programas diseñados.
     
     

    Actividades de difusión

    Las actividades de difusión del trabajo comprendieron:




     

        Capítulo1: Introducción
               1.1 – Procesamiento paralelo y distribuido

      1.2 – Introducción a los objetivos generales del proyecto 1.3 – Objetivos específicos del proyecto
       
        Los objetivos específicos del proyecto involucraron:
    Los archivos disponibles abarcaban datos de 14 meses de duración y consistían en muestras cada cinco minutos de las máquinas de una red de 40 CPUs. También estaban disponibles (para un período de tiempo más corto) registros tomados cada minuto.

    Una vez cumplido con los puntos anteriores, se realizó un ensayo comparativo de los diferentes métodos de despacho propuestos, y se evaluaron los resultados en términos del tiempo requerido de cálculo, utilizando como problemas de testeo modelos numéricos existentes escrito en FORTRAN y C.
     

      1.4 – Especificación de las preguntas que planteó responder el proyecto
    Desde el punto de vista científico, el proyecto propuso hallar respuestas plausibles a las siguientes cuestiones fundamentales.
      1.5 – Actividades específicas
        Capítulo 2:Procesamiento Paralelo en Redes de Computadoras Un conjunto de computadoras conectadas en red puede considerarse como un sistema híbrido entre los multiprocesadores de memoria compartida y los multiprocesadores de memoria distribuida. En una red, cada procesador dispone de su propia memoria pero las comunicaciones entre procesadores se realizan a través de un recurso compartido (la red), el cual es además bastante más lento que un bus de datos tradicional.

    Este caso particular de multiprocesador, si bien adolece de problemas serios (comparado con las dos arquitecturas antes mencionadas) tiene las siguientes dos grandes ventajas:

    En el Centro de Cálculo (CeCal) se ha trabajado a través de los años sobre una arquitectura de este tipo para aprovechar las ventajas del procesamiento paralelo. El modelo de procesamiento utilizado a lo largo de este proyecto se encuentra basada en ella. A continuación se describen los modelos de programación existentes para desarrollar aplicaciones paralelas, y posteriormente se describen los proyectos realizados en el CeCal sobre este tema, para finalmente dejar planteado el tema central de este proyecto.

                Figura 2.2: en una arquitectura de memoria distribuida,
                cada procesador administra su propia memoria privada
     


    Figura 2.3: en una red de computadoras, cada procesador dispone de su
    propia memoria privada y se comunica con los demás procesadores
    a través de la red compartida.

      2.3 – Paradigmas de Programación Paralela
    Existen varios modelos de programación para los diferentes tipos de máquinas paralelas que mencionamos. En todos los casos, se trata de comunicar y sincronizar procesos que están siendo ejecutados en diferentes procesadores. Sin entrar en una descripción exhaustiva de todos los modelos y en sus variantes aplicadas a cada arquitectura de multiprocesador, profundizaremos solamente en el de pasaje de mensajes aplicado a multiprocesadores basados en redes de computadoras, que constituye la infraestructura informática sobre la que se basa este trabajo.

    PVM (Parallel Virtual Machine) es un proyecto nacido en 1989 en el Oak Ridge National Laboratory para uso interno. En 1991 trasciende dicho laboratorio y se difunde su utilización, básicamente en ambientes académicos y dedicado a resolver aplicaciones científicas que demandaban gran consumo de procesador. Con la información obtenida de dichas experiencias, en 1993 PVM es re-escrito completamente y se transforma en un software de dominio público de uso masivo [PVM93].

    PVM provee al desarrollador una capa de servicios de alto nivel que simplifican el armado de aplicaciones distribuidas. Las funcionalidades más importantes son:

    Figura 2.4: PVM permite ver un conjunto de computadoras heterogéneas conectadas
    en red como si fueran una única gran fuente de recursos informáticos
    Existen varias técnicas de programación que se pueden utilizar para implementar aplicaciones distribuidas usando el paradigma de pasaje de mensajes. Las más conocidas son la Descomposición Funcional y la Descomposición de Dominio.

    En la técnica de Descomposición Funcional, la aplicación distribuida ejecuta en diferentes procesadores diferentes porciones de código en forma simultánea. O sea, en cada instante de tiempo se ejecutan en varios procesadores diferentes programas. Por ejemplo, un cajero automático, mientras solicita el número de cuenta corriente, puede estar comunicándose con la computadora del banco para validar un dato anteriormente ingresado; o sea, estaría ejecutando dos programas distintos al mismo tiempo (ingreso de datos y validación de datos).

    En la técnica de Descomposición de Dominio, la aplicación distribuida ejecuta en los diferentes procesadores la misma porción de código, pero trabajando sobre diferentes conjuntos de datos. Citando un ejemplo, para realizar el procesamiento de una imagen, ésta puede ser dividida en tres partes iguales y procesada en forma independiente por tres procesadores distintos que ejecuten el mismo programa (situación típica en el proceso de filtrado de imágenes).
     

    Figura 2.5: Ejemplo de aplicación distribuida utilizando la técnica
    de descomposición de dominio

    Si bien PVM es una excelente herramienta que facilitar el desarrollo de aplicaciones distribuidas a ser ejecutadas en redes de computadoras, es una herramienta de bajo nivel. Esto significa que es una herramienta que se puede utilizar no sólo para implementar aplicaciones distribuidas "llave en mano", sino que además puede ser utilizada para desarrollar herramientas o utilitarios (de más alto nivel) que a su vez sirvan para simplificar aún más el desarrollo de aplicaciones distribuidas.

    En el Centro de Cálculo se trabaja con esta herramienta desde sus orígenes, y se tiene una muy buena experiencia, tanto en desarrollo de aplicaciones distribuidas, como en el desarrollo de herramientas. Yendo aún más lejos, y aprovechando el carácter de dominio público de PVM, en el Centro de Cálculo se ha modificado el mismo código fuente de PVM para mejorar algunas características que originalmente tenían una implementación efectiva pero muy simple. En lo que sigue se presenta la experiencia existente en el Centro de Cálculo al respecto.

      2.4 – Antecedentes en el Centro de Cálculo
    Cuando una aplicación distribuida decide lanzar un proceso en otro procesador, se debe de tomar una decisión importante: en qué procesador se asignará la tarea en cuestión. Dicha decisión es crucial para el desempeño final de la aplicación. La elección incorrecta de uno de los tantos procesadores utilizados por una aplicación distribuida perjudicará el desempeño de todo el sistema.

     

    Figura 2.8: Mejoras de tiempo obtenidos para diferentes densidades de la grilla de datos,
    utilizando cuatro procesadores en lugar de un único procesador.

    Si además de la información de carga instantánea se tuviera en cuenta la información histórica de carga de cada máquina, y ésta se utilizara a los efectos de predecir la carga futura de las computadoras que componen la máquinas virtual, la elección podría ser más fina.

    Aquí entran en juego dos temas: por un lado, será necesario que el algoritmo de despacho pueda administrar (recolectar, almacenar y explotar) información histórica de la carga de cada computadora de la red, y además se deberán implementar y comparar varios algoritmos de predicción. Este proyecto creará la infraestructura necesaria, absolutamente integrada a PVM, que permita crear y probar nuevos algoritmos de despacho de tareas.

      2.5 – Conclusiones
    La experiencia mundial ha demostrado que las arquitecturas de memoria distribuida son las que tienen la relación costo/beneficio y posibilidades reales de escalabilidad a mayor cantidad de procesadores. Ello ha propiciado la proliferación de multiprocesadores de este tipo construidos con hardware legado (redes de computadoras existentes) o con procesadores económicos (proyectos Beowulf).

    La experiencia en el Centro de Cálculo, además de ser muy extensa, ha sido muy rica en este sentido. Los resultados obtenidos en los variados proyectos ejecutados han sido más que satisfactorios, lo que motivó e impulsó a seguir investigando en el estudio para mejorar las herramientas de software existentes con el fin de dar soporte a la programación de multiprocesadores utilizando el pasaje de mensajes.

    La elección de las máquinas más apropiadas para despachar tareas es uno de los parámetros determinados en tiempo de ejecución que más influencia tienen en el desempeño final de una aplicación distribuida. El objetivo de este proyecto es mejorar el muy sencillo algoritmo de despacho de tareas de PVM, y cuantificar la mejora obtenida en algún caso representativo.
     

        Capítulo 3: El problema del Balance de Cargas Con la idea de determinar la relación entre el consumo de CPU y el tiempo de ejecución de una tarea casi-determinística, se diseñó un experimento estadístico. La propuesta consistió en analizar el desempeño de una ET específica, representativa de la red sobre la cual se trabaja, y determinar de qué modo el uso normal de CPU afecta el tiempo de ejecución de una tarea individual bien definida. Se midió la historia de cargas de la máquina y el tiempo requerido para la tarea determinística. Este experimento se repetiría varias veces sobre la misma máquina con diferentes estados de carga, y luego sobre un conjunto de ET para verificar la generalidad de la relación hallada.

    La tarea individual utilizada estuvo compuesta por un conjunto de instrucciones estándar del cálculo científico (operaciones aritméticas de punto flotante, iteraciones y recursiones, compilación de programas extensos, etc.), destinadas a realizar un considerable consumo de CPU. El comportamiento casi determinístico de esta tarea fue determinado a partir de su ejecución repetida sobre una máquina dedicada (sin otra carga base presente).

    Los resultados obtenidos se comentan a continuación:

    Mediante la ejecución del programa test sobre condiciones de carga base nula fue posible determinar que el tiempo de ejecución no variaba sustancialmente. Este comportamiento fue corroborado mediante la repetición del experimento sobre otras máquinas de diferentes arquitecturas que componen nuestra máquina paralela virtual.

    Al obtener pequeñas diferencias en los tiempos de ejecución, fue posible concluir que el programa test tenía un comportamiento casi determinístico. A continuación se ofrecen ejemplos de los resultados obtenidos con datos recolectados de las máquinas maserati.fing.edu.uy y volvo.fing.edu.uy. Los histogramas de las figuras 3.2 y 3.3 ofrecen la distribución de los tiempos de demora de ejecución para la tarea en cuestión, sobre un total de 300 experimentos.

    Figura 3.2: Comportamiento casi determinístico del programa test.
    Datos obtenidos luego de 300 ejecuciones en volvo.fing.edu.uy


    En el primer caso el tiempo de ejecución promedio fue de 795.75s, y la desviación estándar fue de 30.92s lo cual representa un 4,07% sobre el tiempo promedio de ejecución. En el segundo caso el tiempo de ejecución promedio fue de 810.05s, la desviación estándar fue de 31.67s lo cual representa un 3,91% sobre el tiempo promedio de ejecución.

    Cabe considerar que si bien los resultados deberían haber sido obtenidos bajo condiciones nulas de carga, éste es un caso ideal en nuestro entorno (donde no es posible eliminar todos los procesos del sistema), por lo cual es factible que la precisión pueda ser mejorada utilizando máquinas dedicadas para tal fin.

    Ejecutando repetidamente el programa test con diferentes condiciones de carga externa en varias máquinas de la red, mediante análisis estadísticos se llegó a la conclusión de la existencia de una relación casi lineal entre el consumo externo de CPU y la demora de ejecución de la tarea. El programa test aumenta su tiempo de ejecución al ejecutar en una máquina cargada, y la demora de ejecución toma la forma de una función lineal respecto a la carga de CPU bajo condiciones no extremas de carga.
    Figura 3.3: Comportamiento casi determinístico del programa test.
    Datos obtenidos luego de 300 ejecuciones en maserati.fing.edu.uy


    La figura 3.4 resume algunos resultados obtenidos con datos procedentes de la máquina volvo.fing.edu.uy.
    Figura 3.4: Relación casi lineal entre el consumo externo del CPU
    y el tiempo total de ejecución del programa test


    El eje de las abscisas determina el promedio del porcentaje de consumo externo de CPU (evaluado cada 5 segundos) durante el intervalo de ejecución del programa test, mientras que el eje de las ordenadas indica el tiempo total de demora de ejecución de la tarea.

    Resultados como el anterior fueron corroborados en máquinas de diferentes arquitecturas que forman nuestra red, como petunia.fing.edu.uy (Dell), maserati.fing.edu.uy (Sun Sparc) y nautilus.fing.edu.uy (Bull DPX/20 490 Workstation).
     
     

    Los experimentos realizados ofrecen dos consideraciones importantes a tener en cuenta:
          1)Para determinar si una estrategia de despacho de tareas es mejor que otra, el desempeño del sistema (medida por el tiempo medio de ejecución de una tarea distribuida) debe variar en un múltiplos de la desviación estándar observada cuando se utilice el nuevo método de despacho.
          2)Fue verificada una relación funcional casi lineal entre el consumo externo de CPU y la demora de ejecución de una tarea compuesta por instrucciones estándar del cálculo científico. Como consecuencia, el consumo de CPU se revela como un parámetro importante para lograr una mejora en el balance de cargas de un sistema distribuido. El consumo de CPU será un parámetro a predecir para lograr un despacho optimizado por medio de nuevos algoritmos, con la idea de determinar la ET más apropiada sobre la que se despachará una tarea.
      3.4 – Otros parámetros de carga
    Del estudio realizado sobre los parámetros de carga se decidió que los parámetros más representativos de la carga total de una computadora son el consumo de CPU, el consumo de disco y el tráfico de red.

    El experimento de la sección precedente permitió determinar la relación directa entre el consumo de CPU y el tiempo requerido para la ejecución de una aplicación típica de cálculo científico. Con respecto a los restantes parámetros a priori relevantes, es conveniente realizar algunas puntualizaciones.

    La utilización de disco se mide mediante la cantidad de bloques de datos que se transfieren desde el núcleo del sistema operativo al dispositivo. Para el tipo de aplicaciones objetivo con las cuales se propone trabajar en el presente proyecto (aplicaciones de cálculo científico) el consumo de disco no aporta una carga significativa para la computadora, salvo en instancias de inicialización o almacenamiento de los resultados. Generalmente las aplicaciones de éste tipo tienden a utilizar principalmente la CPU, y es razonable determinar que la utilización de disco no tiene la misma importancia para la mejora de desempeño que el uso de CPU.

    Además, el consumo de disco usualmente viene acompañado de un aumento significativo en la utilización de CPU, la cual se encarga del manejo de los datos a transferir, tanto en el caso de lectura como de almacenamiento. Es de esperar que la utilización de disco se vea reflejada en un aumento en el consumo de CPU, parámetro que se modeló para intentar predecir los valores de carga futura.

    De todos modos se recolectaron valores de utilización de disco de las máquinas de la red, utilizando llamadas al sistema operativo UNIX, con la idea de procesarlos mediante el análisis estadísticos de series temporales.

    Para el caso de utilización de disco, el estudio determinó una relación directa respecto a la demora de ejecución, pero no fue posible verificar proporcionalidad alguna, o expresar la demora como una función sencilla de la utilización de disco. Obviamente repercuten los factores anteriormente mencionados, y por lo tanto se decidió trabajar primariamente con el consumo de CPU como parámetro de determinación de la carga.

    Con respecto al tráfico de red, el cual mide la cantidad de paquetes transferidos entre una ET y el resto, se pudo comprobar que constituye un parámetro importante para la determinación de la carga. Pero para el caso de una aplicación de cálculo científico distribuido, la relevancia fundamental consiste en el tráfico de paquetes producto de la comunicación entre las tareas que ejecutan en paralelo. Usualmente dicha comunicación se realiza al comienzo de la tarea (inicialización), al final de la misma (devolución de resultados) y eventualmente en algún punto de sincronización intermedio. Intuitivamente, el tráfico de red que ocurre en el intervalo comprendido entre estos instantes no tiene una repercusión directa sobre el tiempo de ejecución total de la tarea, que constituye la medida de desempeño adoptada. Además, se puede argumentar que ese tráfico es sensiblemente independiente de la ET a la que se despachó la tarea.

    La recolección de los datos de tráfico de red permitió determinar a priori la dificultad de trabajar con este parámetro. La disposición física de los equipos, la forma de comunicación entre los mismos, e imponderables que no es posible modelar, ocasionan a menudo la saturación de segmentos de la red, obligando a modificar el ruteo de paquetes.

    Como resultado del análisis de los parámetros representativos, se decidió trabajar solamente con el consumo de CPU, el cual se mostró como el más representativo de la carga de una máquina, y con incidencia directa sobre la demora de ejecución. Los datos de uso de disco y de red fueron de todos modos recolectados para aplicarles la teoría de modelización de series temporales, pero sabiendo desde un principio que la dificultad de trabajar con estos parámetros no sería menor.

    También fueron realizados experimentos análogos al realizado para el consumo de CPU para el caso de uso de disco y red. Fue virtualmente imposible determinar una correlación entre los valores de tráfico de red y la demora de ejecución de la tarea casi determinística. Los valores de tráfico de red mostraron grandes picos, y variaciones importantes en períodos cortos de tiempo. Dependiendo de las características de la aplicación, la optimización de tráfico de red entre los procesos de la aplicación distribuida puede lograrse mediante una correcta estrategia de división del problema, evitando la granularidad excesiva. [CHIE97]

    La utilización de los datos de consumo de disco y tráfico de red, así como de algún otro parámetro de los disponibles por el sistema operativo, ha quedado planteado como un trabajo futuro. Además, la propuesta inicial preveía trabajar con bloques de variables para determinar posibles correlaciones. Este trabajo fue realizado para el caso de consumo de CPU - uso de disco tal como se describe en el siguiente capítulo, pero ha quedado pendiente el estudio de otros bloques de parámetros de carga.
     

        Capítulo 4: Análisis y modelización de datos históricos de carga La propuesta del proyecto consiste en mejorar el despacho de tareas utilizando la información histórica de carga de los componentes de la máquina virtual con el fin de predecir la carga de dichos componentes en el futuro inmediato. Simplificadamente, el problema principal consiste en cómo predecir la carga de una ET para un instante de tiempo en el futuro, utilizando los datos históricos disponibles y la información actual (en el instante del despacho). Antes de realizar la modelización de datos, en necesario analizarlos con el fin de detectar regularidades y/o variaciones explicables en los mismos.

    Las técnicas utilizadas para el procesamiento se denominan genéricamente como Análisis de Series Temporales. Una Serie Temporal consiste en un conjunto de datos cronológicamente ordenados. En este caso, los datos tomados en cuenta corresponden a los parámetros indicados como relevantes para la determinación de la carga, que son: uso de CPU, uso de disco y tráfico de red.

    El cometido del análisis previo a la modelización consistió en:

    Se estimó que las conclusiones del análisis serían elementos útiles a considerar en las fases posteriores de modelización y predicción de datos futuros.

    El enfoque seguido para el análisis permitió dividir el trabajo en tres partes: a) el análisis individual de datos para cada componente de la red (análisis univariado), b) el estudio de las correlaciones entre parámetros y c) entre equipos de la red (análisis multivariado).
     
     

      4.2.2 Análisis individual de datos para cada componente de la red
    El análisis individual propone dejar de lado las posibles correlaciones existentes entre los diferentes parámetros de carga. Asimismo, se ignora en este enfoque la posibilidad de que algunas máquinas tengan su carga relacionada con otras que compartan, por ejemplo, el mismo perfil de usuario.

    Las variables consideradas para el análisis fueron el uso de CPU, y el uso de disco. En el capítulo anterior se comentó la dificultad existente para determinar una relación entre los datos de tráfico de red y la demora de ejecución. El análisis de datos de tráfico se propone como una actividad a desarrollar en el futuro.

    La metodología aplicada en esta parte del análisis de datos se basó en los modelos ARMA y ARIMA para el análisis de series estacionarias y series no estacionarias reducibles a estacionarias mediante transformaciones. Para el caso de series afectadas por variaciones abruptas las cuales contienen datos que escapan de los valores razonables, fueron utilizadas técnicas de detección de outliers.

    Las gráficas siguientes ofrecen resultados representativos de los valores de carga recolectados, en horarios diurnos. La figura 4.2 muestra los datos de carga de la máquina dynsys.fing.edu.uy, representativa de un conjunto de máquinas muy utilizadas, con valores de carga considerables. La máquina dynsys.fing.edu.uy funciona como servidor de disco. La serie temporal de datos de carga tiene la forma indicada en la gráfica y se clasifica dentro de las series estacionarias con respecto a la media. Los valores aparentan fluctuar alrededor de un cierto valor medio no nulo.

    Figura 4.2: Serie temporal de datos de carga
    de la máquina dynsys.fing.edu.uy

    La figura 4.3 resume los datos de carga de la máquina guille.fing.edu.uy. La serie temporal muestra valores bajos de carga, e inclusive algunos valores nulos. Pero además, se manifiesta la presencia de valores discordantes, los cuales no siguen el patrón de comportamiento global. Estos valores son conocidos como outliers y corresponden, en nuestro caso, a variaciones instantáneas de la carga, generalmente por efecto de la ejecución esporádica de procesos del sistema. Este tipo de series temporales se denominan no estacionarias.

    El análisis individual de las series temporales de carga permitió arribar a algunas conclusiones, las cuales se detallan a continuación:

    Figura 4.3: Serie temporal de datos de carga
    de la máquina guille.fing.edu.uy. Tiempo medido en minutos

      4.2.3 Análisis de correlaciones entre parámetros de carga.
        El objetivo principal de este análisis consistía en determinar la existencia de una relación entre el consumo de disco por parte de una aplicación estándar de cálculo científico y el uso de CPU. El resultado anterior había sido formulado empíricamente en el capítulo precedente y la verificación de la idea planteada determinaría el curso del proyecto.

        En caso de verificarse una relación directa, era suficiente trabajar con el consumo de CPU como único parámetro representativo, despreciando la contribución del consumo de disco a la carga de la ET.

        Por otra parte, en caso de no identificar una relación sencilla entre los parámetros mencionados, sería necesario continuar con el desarrollo de la modelación por separado, considerando los parámetros uso de disco y uso de CPU como variables independientes.

        Los resultados del experimento mostraron una relación directa entre el aumento de uso de disco y el consumo de CPU. Al realizar operaciones de transferencia de datos, los procesos que controlan la transferencia consumen un considerable porcentaje de CPU. Obviamente la relación recíproca no se verifica, puesto que el uso de la CPU no involucra transferencia de datos a memoria secundaria, dado que generalmente se trabaja con los datos en memoria.

        Algunos resultados de los análisis se ofrecen en la figura 4.4, con datos de saddle.fing.edu.uy. Puede observarse que el uso intensivo de disco (cuantificado por la cantidad de bloques transferidos) es acompañado de un incremento sustancial en el consumo de CPU. El resultado ha sido corroborado para otras máquinas de la red ejecutando diversas aplicaciones de cálculo.

      4.2.4 Análisis de correlaciones entre valores de carga de diferentes equipos de la red.
    Complementariamente al estudio descrito en la sección anterior, se realizó un análisis estadístico de los datos de carga de diferentes equipos de la red para determinar si existían correlaciones entre algunas de las ET constituyentes de la máquina paralela virtual.

    Figura 4.4:Correlación entre consumo de CPU y uso de disco para
    la máquina maserati.fing.edu.uy. Tiempo medido en minutos

    El resultado obtenido condicionaría el desarrollo de los métodos de modelización y aún más, de los algoritmos de despacho. En caso de determinar una relación entre los valores de carga de diferentes máquinas, sería necesario desarrollar e implementar métodos multivariados de predicción de valores futuros. De no ser así, los métodos de predicción solamente deberían considerar los datos de la ET cuya carga se desea predecir.

    El experimento estadístico planteado consistió en determinar si los datos de carga de las ET consideradas en el transcurso de este proyecto (saddle.fing.edu.uy, canada.fing.edu.uy, cecal.fing.edu.uy, dynsys.fing.edu.uy, guille.fing.edu.uy) correspondían a una misma distribución de probabilidad. Se utilizó para ello el test de Kolmogorov-Smirnov, el cual permite determinar si dos muestras corresponden a poblaciones con funciones de densidad de probabilidad diferentes o en su defecto, si los conjuntos son consistentes con una función de distribución que puede ser conocida de antemano o no.

    Los resultados determinaron la existencia de correlaciones entre subconjuntos del conjunto de máquinas estudiado. Los valores de carga de saddle.fing.edu.uy y dynsys.fing.edu.uy probaron tener una similitud significativa, cuantificada por el nivel de confianza de 95% ofrecido por el test. La ET cecal.fing.edu.uy mostró una distribución diferente a la ofrecida por las máquinas mencionadas anteriormente, aún cuando las mismas son de su misma arquitectura (Sun Sparc/Sun OS). El motivo fundamental se vincula con el perfil de los usuarios de los equipos y los servicios brindados. Tanto cecal.fing.edu.uy como guille.fing.edu.uy son máquinas con bajo consumo de CPU en horas diarias, y prácticamente nulo en horario nocturno.

    Por su parte, otras máquinas de la misma arquitectura (canada.fing.edu.uy, guille.fing.edu.uy) mostraron una correlación similar entre los valores de CPU. El nivel de confianza alcanzado fue del 90%.

      4.3 – Métodos de predicción basados en Series Temporales 4.3.1 Introducción 4.3.2 Métodos determinísticos lineales
    Debido a su simplicidad, estos métodos son ampliamente utilizados y difundidos. A continuación se ofrece una descripción de algunos de ellos: El vector w se obtiene resolviendo el sistema MTMw = MTm, b=0.

    Debido a la sensibilidad del método a la presencia de outliers, debe realizarse un preprocesamiento de los datos de carga con el fin de removerlos, o el método carecerá de la precisión necesaria como método de predicción. Este problema podría resolverse utilizando métodos que son inherentemente resistentes (en realidad, indiferentes) a la existencia de una fracción predeterminada de outliers en los registros disponibles. Estos métodos se describen a continuación, pero no han sido implementados en los experimentos debido a los altos requerimientos de cálculo de los coeficientes. A su favor (y como se verá luego, en forma similar a los métodos no lineales) puede decirse que esos cálculos pesados son realizados en forma previa al uso, por lo que pueden hacerse fuera de línea.

    Los métodos mencionados utilizan la información histórica de modo de obtener los parámetros y para la predicción utilizan simplemente los valores del instante de tiempo de despacho. Esto se realiza bajo el supuesto de que el sistema es de algún modo estacionario, dado que los valores de los parámetros w y b permanecen constantes, sin recalcularse en cada paso. Este hecho puede no ajustarse completamente a lo observado en la práctica. En la realidad de una red no dedicada, los usuarios usualmente comienzan con aplicaciones pesadas, detienen otras previamente en ejecución, etc. Este comportamiento afecta el típico uso de una ET determinada. Los administradores del sistema podrían transferir servicios desde una máquina a otra, todo lo cual tiene un impacto sobre la utilización de la ET en cuestión.

    El comportamiento descrito no puede ser modelado eficientemente mediante algoritmos estáticos de predicción, y el alto consumo de CPU necesario en la implementación de algunos métodos hace impracticable su implementación adaptativa.

    Fueron investigados métodos lineales adaptativos, los cuales pueden modificar el valor de los parámetros utilizando la información reciente. Ellos permiten contemplar cambios de configuración, de disposición física de los equipos, etc., sin necesidad de considerar un gran volumen de información histórica. Otra ventaja de un algoritmo adaptativo consiste en que puede comenzar la predicción en forma prácticamente instantánea, dado que considera pocos valores históricos para la predicción. Como desventaja, debe citarse la dificultad de implementación dentro del PVM de todo el código necesario, motivo por el cual sólo se realizaron análisis preliminares.

    La idea del método se explica en el desarrollo siguiente, basado en Ljung [LJUNG95], capítulo 10.

    Un algoritmo recursivo típico se implementa basado en la fórmula

    (2)
    en la cual es el parámetro estimado en el tiempo t y el valor  es el valor de salida observado en el tiempo t . El valor consiste en la predicción del valor , realizada considerando las observaciones en el tiempo t-1 y utilizando un método como el que se describe, o eventualmente alguno de los mencionados anteriormente.

    El valor determina de que manera el error cometido en el tiempo t afecta al cálculo del nuevo valor del parámetro estimado. Típicamente se elige , siendo  una aproximación del gradiente respecto a  de , es decir de la predicción de  de acuerdo al modelo descrito por .

    Se utilizaron métodos lineales de múltiples entrada y una única salida, basados en la función rpem.m de Ljung [LJUNG95]. Los parámetros del modelo genérico

    (3)
    se estiman utilizando un método recursivo de predicción de error.

    son polinomios en el operador de demora q, por ejemplo:

    donde na es el orden del polinomio . Los términos representan al error en la predicción y a los valores de carga históricos de otras máquinas consideradas, respectivamente.

    La ecuación (3) contempla el caso multivariado, donde y los coeficientes  son matrices de dimensión ny por ny. Los métodos ARX, ARMAX y Box-Jenkins pueden ser considerados como casos especiales del método general expresado por la ecuación.

    Utilizando todos los datos históricos disponibles es posible hallar los coeficientes  (contenidos en la matriz A) para lograr un mejor ajuste de los datos con el modelo. Sin embargo, para permitir que los parámetros del sistema cambien sus valores con el tiempo solamente fue considerada la estimación recursiva de parámetros.

    Una descripción detallada de los métodos de análisis basados en Series Temporales puede hallarse en [WEI89].

      4.3.3 Métodos no lineales (basados en redes neuronales artificiales)
    Los métodos lineales descritos han sido usados con éxito en un gran número de aplicaciones, en los que se enfatiza en la predicción a corto plazo. En nuestro caso, era necesario contar con una predicción apropiada también en el mediano y largo plazo, para lo cual se propuso considerar como alternativa las redes neuronales artificiales.

    El problema de elegir el "mejor" método de predicción no es nuevo. Ya trabajos como los de Makridakis ([MAKR82]; [MAKR93]) lo han intentado y desafortunadamente la conclusión es que no hay un método que sea universalmente óptimo para cualquier serie. En particular, el trabajo de Makridakis descrito en [MAKR82], también denominada "Competencia M" comparó 24 métodos con 1001 series de datos diferentes, llegando a la conclusión que la ventaja de los métodos de Box y Jenkins (1970) para series univariadas que resultaba de los experimentos previos no era tal.

    Por otra parte, algunos métodos más modernos surgidos con posterioridad fueron contrastados con éxito con la misma base de datos. Así, Sharda and Patil [SHAR90] compararon el desempeño de las Redes Neuronales con los métodos de Box y Jenkins en 75 de los casos de la Competencia M, llegando a la conclusión que las primeras pueden mejorar significativamente el desempeño de las últimas en algunos casos. Similares resultados fueron obtenidos por Chang y Fishwick [CHAN91]. En los experimentos realizados pudieron verificar que incluso en varios de los casos en que Sharda y Patil declaraban que las Redes Neuronales tenían un resultado comparable al método de Box y Jenkins las redes no habían sido suficientemente entrenadas, o los parámetros no habían sido convenientemente elegidos. Ellos mostraron que las Redes Neuronales podían rendir mejores resultados que los informados, pero que ello requería un análisis mas detallado de los datos.

    Este resultado no es sorprendente. En los últimos 10 años (a partir del trabajo de Rumhelhart [RUMH86]) se ha avanzado mucho en el tema, y la técnica se ha aplicado con éxito en muchos más casos que los cubiertos por la Competencia M. Sólo a modo de ejemplo pueden citarse: estudio de la demanda en redes eléctricas ([ISLA95]; [SRIN95]; [MIYA95], de contaminantes en la atmósfera [BOZN93], toma de decisiones [MARQ94] y recientemente por parte de nuestro equipo en el tema de series temporales de lluvia diaria [LOPE97b]. En particular éste resultado nos orientó a la aplicación de las Redes Neuronales para realizar la predicción de datos de carga. Para el lector interesado, en [NYCH96], [STER96], [WARN96]. se describen el concepto y el uso de Redes Neuronales como herramientas estadísticas, aunque más abajo se da una pequeña introducción.

    Chang y Fishwick ([CHAN91]) también observaron que las Redes Neuronales tenían un mejor desempeño cuando se las utilizaba para extrapolar directamente 12 meses a partir de los 12 anteriores, en lugar de aplicar 12 veces una extrapolación de un mes (como requiere Box y Jenkins o como podría hacerse también con Redes Neuronales). Ello tiene implicancias inmediatas para un problema como el nuestro, ya que fijado el horizonte de la predicción, lo que interesa es minimizar el error conjunto y no necesariamente hacer una predicción óptima para los primeros instantes en desmedro de los posteriores.

    Al igual que en el caso de los métodos tradicionales, para la aplicación de las Redes Neuronales se realizaron dos etapas. La primera consistió en evaluar la posibilidad de producir estimaciones razonables basándose únicamente en la historia de la CPU particular en la que se requiere la predicción. Este enfoque univariado se manifestó como imprescindible, porque podría ocurrir que la misma diera resultados razonables, evitándose por tanto la complejidad de las redes multivariadas (que tienen más parámetros a entrenar).

    La segunda etapa se orientó a realizar la predicción basándose en la información temporal de la CPU dada, y de las demás de la red. Para el entrenamiento, se esperaba que sólo un número limitado de muestras fuese suficiente, lo que permitiría manejar eficientemente eventuales cambios en la red (aparición de una nueva máquina, salida de servicio de otras, etc.). Cualquier cambio de configuración de la red requiere un período de entrenamiento (necesariamente breve) para la Red Neuronal.

    La utilización de Redes Neuronales en el diseño de algoritmos proactivos para mejorar el balance de cargas de un sistema distribuido consiste en una idea original, planteada por este proyecto.

    La principal desventaja de los métodos estadísticos tradicionales consiste en imponer restricciones inherentes a cada método, lo cual limita su aplicabilidad. Como ejemplo, los Métodos de Regresión Lineal solamente serán efectivos si la relación funcional subyacente en los datos consiste en una función lineal. La introducción de este tipo de restricciones usualmente hace más rígido al método, disminuyendo su capacidad de predicción.

    Los métodos basados en Redes Neuronales proporcionan una alternativa robusta para el análisis de datos. Estos métodos no consideran restricciones de ningún tipo para la relación funcional subyacente, ya que se ha probado que modificando la estructura de la Red Neuronal es posible ajustar datos a prácticamente cualquier función.

    Una Red Neuronal se organiza en capas, la primera de las cuales es directamente estimulada por (es decir, recibe como entrada) los datos disponibles u observados (ver figura 4.5). Cada capa restante se compone de un conjunto de neuronas, cada una de ellas estimulada por una combinación lineal de las salidas de la capa precedente. La salida de la neurona es obtenida aplicando una función de transferencia a su entrada.

    La función de transferencia puede elegirse entre un conjunto amplio, ya que la teoría no plantea más que moderadas restricciones para la misma. Usualmente tienen como dominio el eje real, y como codominio un rango determinado (normalmente [0,1] ó [-1,1]). Una de las funciones de activación más utilizada es la función logsig ([DEBE94]), determinada por:

    donde los parámetros wij (llamadosconexiones sinápticas) deben ser determinados para cada neurona. Dos propiedades importantes han difundido el uso de esta función: el escalado de valores al rango [0,1] y el hecho de que su derivada varíe suavemente en los extremos del intervalo y tenga variaciones considerables en el centro del mismo. Para escalar los valores al rango [-1,1] se utiliza como función de transferencia la función tanh (tangente hiperbólica), la cual mantiene la propiedad de las derivadas anteriormente mencionada. Este último hecho brinda a las gráficas de las funciones una forma de "S", por lo cual se les conoce como funciones sigmoides de transferencia. La elección de la función de transferencia no impone ninguna restricción sobre la función a ajustar y ha sido demostrado ([CYBE89]) que el desempeño de la red no es afectada por la elección de la función de transferencia.

    Figura 4.5: Diagrama de la organización de una Red Neuronal típica. La información fluye de izquierda a derecha. Hay cuatro entradas p, una capa oculta con cinco neuronas y función de transferencia F1, una segunda capa oculta con tres neuronas y función de transferencia F2, la cual produce tres valores de salida. El símbolo de sumatoria representa una combinación lineal de las salidas de la capa anterior, a la que se suma un término ni(j).
     
    El número de capas ocultas y la cantidad de neuronas en cada capa es una cantidad que debe ser determinada empíricamente para cada problema a resolver. Usualmente se experimenta con diferentes arquitecturas de Redes para hallar aquella que optimice el desempeño de la Red sobre un conjunto de prueba (el denominado conjunto de validación)

    El uso de Redes Neuronales para el ajuste de datos requiere un proceso de entrenamiento. Este proceso consiste en la determinación de los coeficientes aij y de los valores ni(j), el cual se realiza sobre un conjunto representativo de datos. El objetivo de esta etapa es minimizar el Error Medio Cuadrático (EMC) del valor de salida de la Red:

    Donde incluye simbólicamente a todos los pesos (parámetros) asociados las neuronas de la red. N es el número de casos en el proceso de entrenamiento, y ai y RNi representan al valor real y al valor predecido para el evento i-ésimo, respectivamente. El conjunto de parámetros que minimiza el EMC es comúnmente hallado por medio de una estrategia iterativa (gradiente conjugado, máxima pendiente, etc.). El principal inconveniente de este enfoque es que los métodos iterativos son usualmente incapaces de determinar si el mínimo hallado consiste en un mínimo local o global. Diversas estrategias de entrenamiento han sido desarrolladas recientemente para evitar este problema, entre ellas pueden citarse las técnicas basadas en Algoritmos Genéticos, las que serán útiles en caso de implementarse el método dentro del código PVM.

    El número N es en sí mismo parte de la estrategia de entrenamiento. Dado que Cybenko [CYBE89] ha probado que la Red Neuronal es capaz (bajo hipótesis muy generales) de ajustar arbitrariamente bien cualquier función, se corre el riesgo que lograr excelentes resultados con los datos disponibles, y fracasar estrepitosamente con otros datos. La capacidad de lograr buenos resultados con datos que no participaron en el proceso de determinación de los pesos w se denomina generalización. Para lograr un buen ajuste preservando aún la capacidad de generalización, se procede de la siguiente forma. Se subdivide el conjunto de datos disponibles en dos partes, denominados conjunto de entrenamiento y conjunto de validación. El primero (de N elementos) es utilizado tal como se ha descrito, tratando de encontrar los pesos óptimos. Una vez hallados los mismos, se enfrenta a la red a los datos del conjunto de validación, y se evalúa su capacidad de estimarlos. Si el EMC(w) da valores comparables en ambos conjuntos, se acepta el w obtenido. Si no es así, se puede indistintamente: a) intentar comprobar que el w hallado sólo correspondía a un mínimo local de EMC(w), y/o b) modificar la arquitectura de la red, variando el número y tipo de las neuronas o incluso el número de capas ocultas, reiniciando todo el proceso.

    En la práctica, lo que se hace es repetir la opción a) muchas veces, y sólo en último caso ir a b). Usualmente, los algoritmos de minimización parten de un punto inicial elegido al azar, por lo que repetir la opción a) consiste simplemente en correr varias veces el algoritmo de optimización y quedarse con el mejor de los resultados. Así se procedió en este trabajo.
     

        Capítulo 5: Replicación de Datos de Carga Los procesos creados para la réplica de CPU, disco y red tienen una estructura general, aplicable a cualquier otro parámetro, y que se ilustra en la figura 5.4.

    La misma consiste en leer la carga actual e histórica, y en función de estos valores tomar la decisión de cargar, descargar o no hacer nada. Luego de invocar a la rutina correspondiente, espera hasta el siguiente intervalo de lectura.

    El procedimiento de descarga no siempre dará resultado. El enfoque elegido para esto, como se comentó anteriormente, tiene como fin disminuir carga artificial generada previamente por el proceso de réplica, y no intentar disminuir la carga presente en el sistema por otros procesos de usuario.

     
    Chequear parámetros
    Acceder a la región de memoria compartida (SMR)
    Loop
                Leer carga actual (c_actual)
                Leer carga histórica a replicar (c_hist)
                Si (c_hist – c_actual) > 0
                                Invocar procedimiento de carga
                Sino
                                Invocar procedimiento de descarga
                Esperar (siguiente intervalo de réplica T_REPLICA)
                Si (llegó siguiente T_LECTURA)
                                Paso al siguiente valor histórico
    Fin loop
    Figura 5.4 – Esquema general del proceso de réplica
    Es posible definir el valor mínimo de carga para realizar la operación de carga/descarga. Esto puede ser útil para evitar intentos de adaptar la réplica a cargas muy pequeñas, donde probablemente se genere más carga que la deseada cuando se ajuste la misma.

    Un detalle adicional puede presentarse con réplicas prologadas. El esquema planteado supone despreciable el tiempo perdido en realizar las operaciones del loop, antes de realizar la espera. Experimentalmente se obtuvieron valores del orden de 5 milisegundos en dichas operaciones en sistemas Linux. Esto indica que cada 200 iteraciones hay un desfasaje de un segundo de la carga generada con respecto a la histórica.

    Se puede mejorar esta demora, tomando el tiempo antes de cada espera y calculando cuando será el próximo intervalo, en función de T_REPLICA. Antes de esperar hay que recalcular el tiempo de espera como la diferencia entre la hora leída y la hora del próximo intervalo, y utilizar ésta diferencia como intervalo a esperar en vez de T_REPLICA. De esta forma, la espera descuenta el tiempo perdido en las operaciones dentro del loop.

    Este ajuste es incluido en el programa de réplica implementado. El programa específico de carga de cada parámetro se describe a continuación.

      5.5 – Réplica de CPU 5.5.1 Introducción 5.5.2 Lista de procesos 5.5.3- Único proceso
        5.6 – Réplica de disco 5.7 – Réplica de red 5.8 – Conclusiones
    Los programas creados replican la carga equipos seleccionados de una red, con una precisión del orden del 99% por segundo en promedio, monitoreando la carga cada un minuto. Esto permite probar los algoritmos de despachos de tareas prácticamente con los mismos valores de carga en los distintos experimentos.

    La decisión de diseño de usar un proceso por cada parámetro a replicar fue buena, según muestran los experimentos de carga de cada parámetro por separado. Cada proceso se adapta a la carga de otros que pueda afectar el parámetro que está siendo replicando por el primero.

    A su vez, utilizando distintos intervalos de lectura de datos, se obtienen mejores resultados con intervalos grandes (varios segundos). Esto indica que las hipótesis tomadas para el diseño del proceso de réplica fueron acertadas. Confirma también las suposiciones hechas en cuanto a la dificultad para lograr una buena réplica ‘al milisegundo’ con este diseño, en comparación con los resultados a obtener con intervalos mayores.

    En definitiva, los resultados obtenidos por el sistema de replicación de carga pueden considerarse como muy buenos, y si bien fue ideado como un subproducto imprescindible para cuantificar la bondad de los nuevos algoritmos de despacho desarrollados en este proyecto en particular, su utilización seguramente trascenderá a este proyecto.

        Capítulo 6: Métodos de predicción de la serie temporal de datos de carga     Capítulo 7: El desempeño de los diferentes métodos de despacho     Capítulo 8: Conclusiones y trabajo futuro Debido al carácter estadístico de los experimentos realizados, no es posible afirmar de manera concluyente que el valor de mejora alcanzado sea el mejor posible. En particular, el resultado depende de varios factores: la aplicación en particular, la configuración de la red, etc. El trabajo futuro a desarrollar siguiendo el camino de este proyecto se vincula con el estudio de nuevas técnicas de modelización estadísticas y algoritmos de predicción, así como de optimización de la operación de una red.

    En este aspecto debe señalarse que se utilizó como criterio de despacho elegir la ET cuya estimación de carga media a un horizonte de 5 minutos fuese mínima. Ese criterio puede mejorarse, y ensayarse otros bajo la hipótesis del método de predicción perfecto, ya que el ambiente de simulación desarrollado ahora lo permite. Este es un problema de optimización de difícil abordaje, que sería imposible de no contarse con el replicador elaborado en este proyecto. Así, sería posible encontrar el criterio de despacho óptimo dada una estimación de carga futura, y ensayarlo y validarlo en un sistema operando.

    El nuevo algoritmo de despacho basado en la estrategia de predicción de Mínimos Cuadrados no ofreció buenos resultados. Este hecho motiva a plantear diferentes alternativas del método y realizar el estudio de técnicas más robustas de predicción.

    Con respecto al método basado en Redes Neuronales, se abren muchas más posibilidades. La red denominada bp11 utiliza únicamente información del instante inmediatamente anterior al momento de despacho. Es factible que ello pueda mejorarse utilizando más información disponible, sin costo sensible al momento de predecir, pero en contrapartida con un costo significativo al momento de calcular los parámetros. El enfoque basado en Redes Neuronales admite con naturalidad la incorporación de otros parámetros (uso de disco, red, etc.) a la hora de predecir la carga de un equipo. En contrapartida, la fase de entrenamiento de la red es costosa, y la configuración de la máquina virtual debe ser decidida en forma estática en ese momento (por la vía de mencionar todos las ET involucradas). En nuestro trabajo se realizó el entrenamiento en ambiente Matlab, y sólo se programó en PVM el uso de la red una vez entrenada.

    Dado que la red es entrenada una única vez, no se adapta a cambios en las características de uso de las máquina. En este respecto, es posible (aunque significativamente más complejo) utilizar Redes Adaptativas. Las mismas van aprendiendo de la historia a medida que ésta ocurre, y podrían, por ejemplo reaccionar ponderando con mayor peso información reciente de eventos transitorios (como una gran compilación en una máquina en la que ello no es típico), y de este modo asignarle menor prioridad a esa ET.

    El análisis de un bloque de variables de carga ha sido propuesto como una idea de trabajo futuro. En el transcurso del proyecto se decidió trabajar exclusivamente con el consumo de CPU como parámetro relevante para la determinación de la carga. Al considerar nuevas variables es posible que aumente el factor de mejora de desempeño, bajo el costo de técnicas más complejas de modelización.
     
     


    Bibliografía
     

        Para acceder a los anexos haga click.
    Anexo I  -   Cronograma de actividades
    Anexo II -  Towards Proactive Network Load Management For Parallel
                        Distributed Programming
    Anexo III - Artificial Replication of Network Load Environment for
                        Distributed Algorithms Comparison