Aplicaciones Single Program Multiple Data (SPMD) en ambientes distribuidos

Un reto al ejecutar las aplicaciones en un cluster es lograr mejorar las prestaciones utilizando los recursos de manera eficiente, y este reto es mayor al utilizar un ambiente distribuido. Teniendo en cuenta este reto, se proponen un conjunto de reglas para realizar el cómputo en cada uno de los nodos, basado en el análisis de cómputo y comunicaciones de las aplicaciones, se analiza un esquema de mapping de celdas y un método para planificar el orden de ejecución, tomando en consideración la ejecución por prioridad, donde las celdas de fronteras tienen una mayor prioridad con respecto a las celdas internas. En la experimentación se muestra el solapamiento del computo interno con las comunicaciones de las celdas fronteras, obteniendo resultados donde el Speedup aumenta y los niveles de eficiencia se mantienen por encima de un 85%, finalmente se obtiene ganancias de los tiempos de ejecución, concluyendo que si se puede diseñar un esquemas de solapamiento que permita que la ejecución de las aplicaciones SPMD en un cluster se hagan de forma eficiente.

Xarxes ad hoc cooperatives

Estudi sobre la cooperació entre els nodes que formen una xarxa mòbil ad hoc, analitzant la distància entre aquests per conèixer la capacitat de transmissió d’informació entre el node origen i el node destí.

Entorno de desarrollo para clusters

El presente trabajo expone los entornos de desarrollo de aplicaciones paralelas en sistemas distribuidos. Se ha dedicado especial atención a los entornos gráficos, como plataforma de acceso al cluster. Dada la cantidad de alternativas a seleccionar en este tipo de entornos, como puede ser la parametrización de las aplicaciones, especificación de la arquitectura a utilizar de los nodos, caracterización de la carga, políticas de planificación, etc, hace que este trabajo pueda servir de punto inicial de partida a usuarios que deseen iniciarse en este tipo de entornos.

Clúster creatius en entorns urbans: 22@Bcn i Shoreditch East London

La localització de les empreses de nova economia en zones urbanes, a pesar que el factor distància no sigui important, no deixa de ser considerable pels seus avantatges que els suposa estar situades conjuntament en relació amb les infraestructures, consum, beneficis socioculturals, i facilitat en les transaccions cara a cara. És inevitable que el primer quart del segle vint-i-un estigui lligat a l’economia creativa de forma similar amb que el començament del segle vint estava íntimament lligat a l’economia industrial i la invenció del sistema de producció en massa. La ciutat també va jugar un dels papers més importants per al desenvolupament de “la nova economia industrial” a les albors del segle vint, com ho és la ciutat del coneixement que acull “la nova economia creativa” al segle vint-i-un. És evident que els resultats morfològics, socials, econòmics i urbans són ben diferents en ambdós fenòmens, però l’impacte a les ciutats és molt gran. L’objectiu d’aquest estudi és analitzar els mecanismes d’aglomeració (clustering) d’activitats competitives basades en creació de coneixement i de serveis avançats que estan al darrera de desenvolupaments punters a ciutats com Barcelona, el projecte 22@bcn, i East London, el projecte Shoreditch. L’esforç que han posat les autoritats locals en crear l’entorn apropiat per atreure i crear empreses innovadores, com a motor de desenvolupament d’algunes ciutats modernes europees ha resultat en el sorgiment de nuclis o centres urbans molt dinàmics que suposadament estan preparats i acullen punts de creació de coneixement (“Urban Knowledge Hubs”), amb una demanda i llocs de treball altament qualificats. Aquest és el cas dels projectes de Barcelona (22@bcn) i East London (Shoreditch).

Deadlock avoidance with virtual channels

High Performance Computing is a rapidly evolving area of computer science which attends to solve complicated computational problems with the combination of computational nodes connected through high speed networks. This work concentrates on the networks problems that appear in such networks and specially focuses on the Deadlock problem that can decrease the efficiency of the communication or even destroy the balance and paralyze the network. Goal of this work is the Deadlock avoidance with the use of virtual channels, in the switches of the network where the problem appears. The deadlock avoidance assures that will not be loss of data inside network, having as result the increased latency of the served packets, due to the extra calculation that the switches have to make to apply the policy.

Análisis de rendimiento de aplicaciones paralelas de memoria compartida: problema N-body

Este trabajo analiza el rendimiento de cuatro nodos de cómputo multiprocesador de memoria compartida para resolver el problema N-body. Se paraleliza el algoritmo serie, y se codifica usando el lenguaje C extendido con OpenMP. El resultado son dos variantes que obedecen a dos criterios de optimización diferentes: minimizar los requisitos de memoria y minimizar el volumen de cómputo. Posteriormente, se realiza un proceso de análisis de las prestaciones del programa sobre los nodos de cómputo. Se modela el rendimiento de las variantes secuenciales y paralelas de la aplicación, y de los nodos de cómputo; se instrumentan y ejecutan los programas para obtener resultados en forma de varias métricas; finalmente se muestran e interpretan los resultados, proporcionando claves que explican ineficiencias y cuellos de botella en el rendimiento y posibles líneas de mejora. La experiencia de este estudio concreto ha permitido esbozar una incipiente metodología de análisis de rendimiento, identificación de problemas y sintonización de algoritmos a nodos de cómputo multiprocesador de memoria compartida.

Análisis y sintonización de aplicaciones paralelas/distribuidas de bioinformática: caso de estudio mpiBLAST

En termes de temps d'execució i ús de dades, les aplicacions paral·leles/distribuïdes poden tenir execucions variables, fins i tot quan s'empra el mateix conjunt de dades d'entrada. Existeixen certs aspectes de rendiment relacionats amb l'entorn que poden afectar dinàmicament el comportament de l'aplicació, tals com: la capacitat de la memòria, latència de la xarxa, el nombre de nodes, l'heterogeneïtat dels nodes, entre d'altres. És important considerar que l'aplicació pot executar-se en diferents configuracions de maquinari i el desenvolupador d'aplicacions no port garantir que els ajustaments de rendiment per a un sistema en particular continuïn essent vàlids per a d'altres configuracions. L'anàlisi dinàmica de les aplicacions ha demostrat ser el millor enfocament per a l'anàlisi del rendiment per dues raons principals. En primer lloc, ofereix una solució molt còmoda des del punt de vista dels desenvolupadors mentre que aquests dissenyen i evaluen les seves aplicacions paral·leles. En segon lloc, perquè s'adapta millor a l'aplicació durant l'execució. Aquest enfocament no requereix la intervenció de desenvolupadors o fins i tot l'accés al codi font de l'aplicació. S'analitza l'aplicació en temps real d'execució i es considra i analitza la recerca dels possibles colls d'ampolla i optimitzacions. Per a optimitzar l'execució de l'aplicació bioinformàtica mpiBLAST, vam analitzar el seu comportament per a identificar els paràmetres que intervenen en el rendiment d'ella, com ara: l'ús de la memòria, l'ús de la xarxa, patrons d'E/S, el sistema de fitxers emprat, l'arquitectura del processador, la grandària de la base de dades biològica, la grandària de la seqüència de consulta, la distribució de les seqüències dintre d'elles, el nombre de fragments de la base de dades i/o la granularitat dels treballs assignats a cada procés. El nostre objectiu és determinar quins d'aquests paràmetres tenen major impacte en el rendiment de les aplicacions i com ajustar-los dinàmicament per a millorar el rendiment de l'aplicació. Analitzant el rendiment de l'aplicació mpiBLAST hem trobat un conjunt de dades que identifiquen cert nivell de serial·lització dintre l'execució. Reconeixent l'impacte de la caracterització de les seqüències dintre de les diferents bases de dades i una relació entre la capacitat dels workers i la granularitat de la càrrega de treball actual, aquestes podrien ser sintonitzades dinàmicament. Altres millores també inclouen optimitzacions relacionades amb el sistema de fitxers paral·lel i la possibilitat d'execució en múltiples multinucli. La grandària de gra de treball està influenciat per factors com el tipus de base de dades, la grandària de la base de dades, i la relació entre grandària de la càrrega de treball i la capacitat dels treballadors.

Seguretat en xarxes i aplicacions distribuïdes: MANET routing

L’objectiu del projecte és tractar de donar solució al problema d’interconnexió de dispositius mòbils, en concret de PDAs Nokia 810, en una situació on no es disposa d’un punt d’accès fixe. Per a fer-ho possible es forma una xarxa MANET, és a dir una xarxa Ad-hoc mòbil, on els nodes són els propis dispositius. Un cop establerta la connexió, s’obté un llistat actualitzat amb les adreces IP de tots els nodes visibles de la xarxa.

The analysis of approximate quickselect and related problems

Approximate Quickselect, a simple modification of the well known Quickselect algorithm for selection, can be used to efficiently find an element with rank k in a given range [i..j], out of n given elements. We study basic cost measures of Approximate Quickselect by computing exact and asymptotic results for the expected number of passes, comparisons and data moves during the execution of this algorithm. The key element appearing in the analysis of Approximate Quickselect is a trivariate recurrence that we solve in full generality. The general solution of the recurrence proves to be very useful, as it allows us to tackle several related problems, besides the analysis that originally motivated us. In particular, we have been able to carry out a precise analysis of the expected number of moves of the ith element when selecting the jth smallest element with standard Quickselect, where we are able to give both exact and asymptotic results. Moreover, we can apply our general results to obtain exact and asymptotic results for several parameters in binary search trees, namely the expected number of common ancestors of the nodes with rank i and j, the expected size of the subtree rooted at the least common ancestor of the nodes with rank i and j, and the expected distance between the nodes of ranks i and j.

Theoretical aspects of graph models for MANETs

We survey the main theoretical aspects of models for Mobile Ad Hoc Networks (MANETs). We present theoretical characterizations of mobile network structural properties, different dynamic graph models of MANETs, and finally we give detailed summaries of a few selected articles. In particular, we focus on articles dealing with connectivity of mobile networks, and on articles which show that mobility can be used to propagate information between nodes of the network while at the same time maintaining small transmission distances, and thus saving energy.

El impacto de las aplicaciones intensivas de E/S en la planificación de trabajos en clusters no-dedicados

Con la mayor capacidad de los nodos de procesamiento en relación a la potencia de cómputo, cada vez más aplicaciones intensivas de datos como las aplicaciones de la bioinformática, se llevarán a ejecutar en clusters no dedicados. Los clusters no dedicados se caracterizan por su capacidad de combinar la ejecución de aplicaciones de usuarios locales con aplicaciones, científicas o comerciales, ejecutadas en paralelo. Saber qué efecto las aplicaciones con acceso intensivo a dados producen respecto a la mezcla de otro tipo (batch, interativa, SRT, etc) en los entornos no-dedicados permite el desarrollo de políticas de planificación más eficientes. Algunas de las aplicaciones intensivas de E/S se basan en el paradigma MapReduce donde los entornos que las utilizan, como Hadoop, se ocupan de la localidad de los datos, balanceo de carga de forma automática y trabajan con sistemas de archivos distribuidos. El rendimiento de Hadoop se puede mejorar sin aumentar los costos de hardware, al sintonizar varios parámetros de configuración claves para las especificaciones del cluster, para el tamaño de los datos de entrada y para el procesamiento complejo. La sincronización de estos parámetros de sincronización puede ser demasiado compleja para el usuario y/o administrador pero procura garantizar prestaciones más adecuadas. Este trabajo propone la evaluación del impacto de las aplicaciones intensivas de E/S en la planificación de trabajos en clusters no-dedicados bajo los paradigmas MPI y Mapreduce.

Predictive and distributed routing balancing (PR-DRB): high speed interconnection networks

Current parallel applications running on clusters require the use of an interconnection network to perform communications among all computing nodes available. Imbalance of communications can produce network congestion, reducing throughput and increasing latency, degrading the overall system performance. On the other hand, parallel applications running on these networks posses representative stages which allow their characterization, as well as repetitive behavior that can be identified on the basis of this characterization. This work presents the Predictive and Distributed Routing Balancing (PR-DRB), a new method developed to gradually control network congestion, based on paths expansion, traffic distribution and effective traffic load, in order to maintain low latency values. PR-DRB monitors messages latencies on intermediate routers, makes decisions about alternative paths and record communication pattern information encountered during congestion situation. Based on the concept of applications repetitiveness, best solution recorded are reapplied when saved communication pattern re-appears. Traffic congestion experiments were conducted in order to evaluate the performance of the method, and improvements were observed.

Multi-level SLA-driven resource management on Cloud Providers

Nowadays, service providers in the Cloud offer complex services ready to be used as it was a commodity like water or electricity to their customers with any other extra effort for them. However, providing these services implies a high management effort which requires a lot of human interaction. Furthermore, an efficient resource management mechanism considering only provider's resources is, though necessary, not enough, because the provider's profit is limited by the amount of resources it owns. Dynamically outsourcing resources to other providers in response to demand variation avoids this problem and makes the provider to get more profit. A key technology for achieving these goals is virtualization which facilitates provider's management and provides on-demand virtual environments, which are isolated and consolidated in order to achieve a better utilization of the provider's resources. Nevertheless, dealing with some virtualization capabilities implies an effort for the user in order to take benefit from them. In order to avoid this problem, we are contributing the research community with a virtualized environment manager which aims to provide virtual machines that fulfils with the user requirements. Another challenge is sharing resources among different federated Cloud providers while exploiting the features of virtualization in a new approach for facilitating providers' management. This project aims for reducing provider's costs and at the same time fulfilling the quality of service agreed with the customers while maximizing the provider's revenue. It considers resource management at several layers, namely locally to each node in the provider, among different nodes in the provider, and among different federated providers. This latter layer supports the novel capabilities of outsourcing when the local resources are not enough to fulfil the users demand, and offering resources to other providers when the local resources are underused.

Disseny i optimització metològica de sistemes telemàtics interactius per a la millora de la docència universitària : l'entorn BSCW i nous recursos docents

Aquest projecte de dos anys de durada, ha tingut com a objectius: el disseny i la creació de recursos multimèdia, així com, l’optimització de metodologies d'aplicació de sistemes telemàtics interactius per a la millora de la docència universitària. Com a entorn telemàtic s’ha utilitzat la plataforma de treball cooperatiu BSCW (Basic Support for Cooperative Work). S'ha dissenyat i produït un recurs multimèdia enfocat a l'alumnat de l'assignatura troncal Ciències naturals i la seva didàctica de la diplomatura de Mestre d'Educació Primària, que porta per títol 'Alimentació i nutrició humanes i la seva didàctica’ i es pot consultar a: http://www.ub.edu/didactica_ciencies/mqd06/. Aquest material està format per dues unitats: a) Alimentació i nutrició; b) L'ensenyament-aprenentatge de la digestió humana des d'una perspectiva constructivista. Les unitats s'han orientat a la millora de la formació inicial dels futurs mestres i tenen un enfocament de clar caire constructivista, amb exercicis interactius de detecció de concepcions alternatives, així com organitzadors previs, posteriors nodes expositius i d'obtenció d'informació, exercicis interactius destinats al canvi conceptual i una interactivitat d'avaluació final amb un cert caràcter sumatiu. Cada unitat es tanca amb un mapa conceptual dels continguts tractats. La metodologia emprada en la seva elaboració és una evolució de la que l'equip de la Universitat Pompeu Fabra va encetar en la web ‘Aracné. Ciència en xarxa’: http://www.edu365.com/aulanet/aracne/ (usuari i contrasenya: guest100), i va perfeccionar a 'Idees i vincles en el segle XX. La ciència': http://www.xtec.es/aulanet/seglexx/ (cal permetre que s'obrin finestres emergents), en ambdós casos hi ha col·laborat professorat del nostre grup d'innovació docent de la UB.

Alineamiento de secuencias genéticas en procesadores multicore

Este trabajo analiza el rendimiento del algoritmo de alineamiento de secuencias conocido como Needleman-Wunsch, sobre 3 sistemas de cómputo multiprocesador diferentes. Se analiza y se codifica el algoritmo serie usando el lenguaje de programación C y se plantean una serie de optimizaciones con la finalidad de minimizar el volumen y el tiempo de cómputo. Posteriormente, se realiza un análisis de las prestaciones del programa sobre los diferentes sistemas de cómputo. En la segunda parte del trabajo, se paraleliza el algoritmo serie y se codifica ayudándonos de OpenMP. El resultado son dos variantes del programa que difieren en la relación entre la cantidad de cómputo y la de comunicación. En la primera variante, la comunicación entre procesadores es poco frecuente y se realiza tras largos periodos de ejecución (granularidad gruesa). En cambio, en la segunda variante las tareas individuales son relativamente pequeñas en término de tiempo de ejecución y la comunicación entre los procesadores es frecuente (granularidad fina). Ambas variantes se ejecutan y analizan en arquitecturas multicore que explotan el paralelismo a nivel de thread. Los resultados obtenidos muestran la importancia de entender y saber analizar el efecto del multicore y multithreading en el rendimiento.