Doctor en Ciencias, Mención Computación / Esta tesis apunta a entregar las bases para el desarrollo de los algoritmos de balance de carga para el modelo de objetos activos definido por ProActive en el contexto de las redes a gran escala (grillas). ProActive es un middleware implementado en lenguaje Java, de código abierto, para la progra­mación concurrente, en paralelo, distribuido, y emóvil, poniendo el paradigma de objeto-activo en ejecución. En ProActive, cada objeto activo tiene su propio hilo de control y puede decidir indepen­dientemente en qué orden servir los métodos entrantes, las cuales se almacenan automáticamente en una cola de peticiones pendientes. Para agregar eficacia al paradigma de objetos activos, ProActive proporciona un mecanismo del migración, obteniendo localización automática y trans­parencia mediante el uso de forwarders. La migración viene con un costo de comunicación: un objeto activo debe emigrar con su estado completo, consistiendo en sus peticiones pendientes (lla­madas de método), futuros, y sus objetos pasivos. Por lo tanto, las aplicaciones implementadas con ProActive son sensibles a la latencia. Cuando varios objetos activos con funcionalidad idéntica se despliegan, un algoritmo de bal­ance de carga puede ser utilizado para mejorar el funcionamiento de la aplicación utilizando esa funcionalidad. La carga de trabajo puede ser equilibrada a través de varios objetos activos enviando objetos activos de un procesador altamente cargado a uno menos cargado, o bien robando objetos activos de un procesador altamente cargado por uno menos cargado. El ambiente donde funcionan las aplicaciones implementadas usando el modelo de objetos activos se compone generalmente de grupos múltiples de recursos, por ejemplo, un sistema de máquinas interconectadas por una red local de alta velocidad. Por lo tanto, un algoritmo de balance de carga para objetos activos que pertenecen a una apli­cación paralela fue desarrollado y estudiado, fijando las bases para el desarrollo de los algoritmos de balance de carga para el middleware ProActive. Este primer acercamiento se llama el algoritmo Robin-Hood + Nottingham Sheriff. Este algoritmo fue validado en el contexto de una red de alta escala (sobre 1.000 nodos) mediante simulaciones, utilizando nuestro modelo de las grillas basa­dos en la observación y la medición de lo que consideramos las características dominantes para el balance de objetos activos: capacidad de procesamiento y latencia entre recursos. Finalmente, presentamos los contratos de acoplamiento para el despliegue de aplicaciones par­alelas, su forma de utilización en el contexto de balance de carga, por ejemplo, elegir entre un planificador local y el balanceador de carga de ProActive.

El objetivo de este Trabajo Final es comparar el efecto de la distribución de trabajo estática y dinámica sobre arquitecturas de cluster heterogéneo, analizando al mismo tiempo el speedup paralelo teórico y el obtenido experimentalmente para un determinado tipo de problema. En particular, se ha elegido una aplicación clásica (Parallel N-Queens) con un algoritmo de solución paralela en la que predomina el procesamiento sobre el tamaño de los datos, de modo de profundizar en los aspectos del balance de carga (estático o dinámico) sin una distorsión de los resultados producida por aspectos relacionados al uso de la memoria y/o al tamaño de los mensajes a comunicar. Para la experimentación se ha utilizado una combinación de 4 clusters interconectados, donde las máquinas dentro de cada grupo poseen procesadores homogéneos, pero diferentes entre clusters. De este modo el conjunto puede verse como un cluster heterogéneo de 43 procesadores. El problema se ha resuelto utilizando el paradigma master/worker donde el procesamiento se descompone en tareas irregulares que atentan contra el balance de carga entre los procesadores. Por esta razón se han analizado tres estrategias de distribución de trabajo calculando en cada caso el desbalance de carga y el rendimiento obtenido, comparando los resultados para determinar la que tiene mejor comportamiento, y finalmente estudiar la escalabilidad para esa solución. La solución paralela pura (sin tener en cuenta la distribución del trabajo) para el tipo de problemas donde Tp>>Tc, en particular el de N-Reinas requiere mínima comunicación entre máquinas, lo que hace esencial la elección de la distribución de datos entre los procesadores, para alcanzar un speedup cercano al óptimo (es decir un buen rendimiento).