Dans la course vers l’exascale, les architectures des supercalculateurs évoluent vers des nœuds massivement multicœurs, sur lesquels les accès mémoire sont non-uniformes et les registres de vectorisation toujours plus grands. Ces évolutions entraînent une baisse de l’efficacité des applications homogènes (MPI simple), et imposent aux développeurs l’utilisation de fonctionnalités de bas-niveau afin d’obtenir de bonnes performances.Dans le contexte de la dynamique moléculaire (DM) appliqué à la physique de la matière condensée, les études du comportement des matériaux dans des conditions extrêmes requièrent la simulation de systèmes toujours plus grands avec une physique de plus en plus complexe. L’adaptation des codes de DM aux architectures exaflopiques est donc un enjeu essentiel.Cette thèse propose la conception et l’implémentation d’une plateforme dédiée à la simulation de très grands systèmes de DM sur les futurs supercalculateurs. Notre architecture s’organise autour de trois niveaux de parallélisme: décomposition de domaine avec MPI, du multithreading massif sur chaque domaine et un système de vectorisation explicite. Nous avons également inclus une capacité d’équilibrage dynamique de charge de calcul. La conception orienté objet a été particulièrement étudiée afin de préserver un niveau de programmation utilisable par des physiciens sans altérer les performances.Les premiers résultats montrent d’excellentes performances séquentielles, ainsi qu’une accélération quasi-linéaire sur plusieurs dizaines de milliers de cœurs. En production, nous constatons une accélération jusqu’à un facteur 30 par rapport au code utilisé actuellement par les chercheurs du CEA. / In the exascale race, supercomputer architectures are evolving towards massively multicore nodes with hierarchical memory structures and equipped with larger vectorization registers. These trends tend to make MPI-only applications less effective, and now require programmers to explicitly manage low-level elements to get decent performance.In the context of Molecular Dynamics (MD) applied to condensed matter physics, the need for a better understanding of materials behaviour under extreme conditions involves simulations of ever larger systems, on tens of thousands of cores. This will put molecular dynamics codes among software that are very likely to meet serious difficulties when it comes to fully exploit the performance of next generation processors.This thesis proposes the design and implementation of a high-performance, flexible and scalable framework dedicated to the simulation of large scale MD systems on future supercomputers. We managed to separate numerical modules from different expressions of parallelism, allowing developers not to care about optimizations and still obtain high levels of performance. Our architecture is organized in three levels of parallelism: domain decomposition using MPI, thread parallelization within each domain, and explicit vectorization. We also included a dynamic load balancing capability in order to equally share the workload among domains.Results on simple tests show excellent sequential performance and a quasi linear speedup on several thousands of cores on various architectures. When applied to production simulations, we report an acceleration up to a factor 30 compared to the code previously used by CEA’s researchers.

En raison de la capacité et de l'amélioration des performances informatiques, les représentations structurelles sont devenues de plus en plus populaires dans le domaine de la reconnaissance de formes (RF). Quand les objets sont structurés à base de graphes, le problme de la comparaison d'objets revient à un problme d'appariement de graphes (Graph Matching). Au cours de la dernière décennie, les chercheurs travaillant dans le domaine de l'appariement de graphes ont porté une attention particulière à la distance d'édition entre graphes (GED), notamment pour sa capacité à traiter différent types de graphes. GED a été ainsi appliquée sur des problématiques spécifiques qui varient de la reconnaissance de molécules à la classi fication d'images. / Due to the inherent genericity of graph-based representations, and thanks to the improvement of computer capacities, structural representations have become more and more popular in the field of Pattern Recognition (PR). In a graph-based representation, vertices and their attributes describe objects (or part of them) while edges represent interrelationships between the objects. Representing objects by graphs turns the problem of object comparison into graph matching (GM) where correspondences between vertices and edges of two graphs have to be found.

With increasing demands on network reliability and speed, network suppliers need to effectivize their communications algorithms. Frequency measurements are a core part of mobile network communications, increasing their effectiveness would increase the effectiveness of many network processes such as handovers, load balancing, and carrier aggregation. This study examines the possibility of using supervised learning to predict the signal of inter-frequency measurements by investigating various learning algorithms and pre-processing techniques. We found that random forests have the highest predictive performance on this data set, at 90.7\% accuracy. In addition, we have shown that undersampling and varying the discriminator are effective techniques for increasing the performance on the positive class on frequencies where the negative class is prevalent. Finally, we present hybrid algorithms in which the learning algorithm for each model depends on attributes of the training data set. These algorithms perform at a much higher efficiency in terms of memory and run-time without heavily sacrificing predictive performance.

The numerical simulation of fluid flow involving complex geometries is greatly limited by the required spatial grid resolution. These flows often contain small regions with complex motions, while the remaining flow is relatively smooth. Adaptive mesh refinement (AMR) enables the spatial grid to be refined in local regions that require finer grids to resolve the flow. This work describes an approach to parallelization of a structured adaptive mesh refinement (SAMR) algorithm. This type of methodology is based on locally refined grids superimposed on coarser grids to achieve the desired resolution in numerical simulations. Parallel implementations of SAMR methods offer the potential for accurate simulations of high complexity fluid flows. However, they present interesting challenges in dynamic resource allocation, data-distribution and load-balancing. The overall efficiency of parallel SAMR applications is limited by the ability to partition the underlying grid hierarchies at run-time to expose all inherent parallelism, minimize communication and synchronization overheads, and balance load. The methodology is based on a message passing interface model (MPI) using the recursive coordinate bisection (RCB) for domain partition. For this work, a semi-implicit projection method has been implemented to solve the incompressible Navier Stokes equations. All numerical implementations are an extension of a sequential Fortran 90 code, called "AMR3D", developed in the work of Nós (2007) .The efficiency and robustness of the applied methodology are verified via convergence analysis using the method of manufactured solutions. Validations were performed by simulating an incompressible jet flow and a lid driven cavity flow. / A simulação numérica de escoamentos envolvendo geometrias complexas é fortemente limitada pela resolução da malha espacial. Na grande maioria dos escoamentos, há pequenas regiões do domínio onde o fluido se movimenta de forma complexa gerando gradientes elevados, enquanto que no restante do domínio o escoamento é relativamente calmo". O Refinamento Adaptativo de Malhas (Adaptive Mesh Refinement - AMR), possibilita que o refinamento da malha espacial seja mais apurado em regiões especificas, enquanto que nas demais regiões o refinamento pode ser mais grosseiro. O presente trabalho consiste no desenvolvimento de uma metodologia de paralelização para a solução das equações de Navier-Stokes em malhas adaptativas bloco-estruturadas (Structured Adaptive Mesh Refinement - SAMR) utilizando a interface MPI (Message Passing Interface) e o método de bisseção por coordenadas RCB (Recursive Coordinate Bisection) para o balanço de carga. Implementações de métodos SAMR em processamento paralelo oferecem a possibilidade de simulações precisas de escoamentos de elevada complexidade. No entanto, apresentam desafios interessantes quanto à dinamicidade na alocação e distribuição dos dados e no balanceamento de carga. Cabe ressaltar que a é ciência total das aplicações envolvendo métodos SAMR em processamento paralelo é fortemente dependente da qualidade do particionamento dinâmico de domínio, efetuado em tempo de execução, para que se garanta os menores custos de comunicação e sincronização possíveis, além de uma boa distribuição da carga computacional. Neste trabalho, utilizou-se o esquema semi-implícito proposto por Ceniceros et al. (2010) para avanço temporal. Todas as implementações foram efetuadas como uma extensão do código AMR3D", proposto por Nós (2007). A é ciência e a robustez do método proposto são verificadas por meio do método das soluções manufaturadas. As validações foram feitas por meio da simulação do escoamento em uma cavidade com tampa deslizante e de um jato incompressível. / Doutor em Engenharia Mecânica

Un réseau sans fil multi-saut est un ensemble d’entités mobiles et/ou fixes formant un réseau dynamique temporaire avec ou sans l’aide de toute administration centralisée. Cette particularité rend le routage problématique en cas d’instabilité des éléments qui composent les communications non directes. Afin de palier ces problèmes, de nouvelles formes de routage sont utilisées comme le routage multi-chemin (MC). Le routage MC permet d’envoyer les données sur des chemins multiples et semble être une solution efficace pour ces réseaux. Le but de cette thèse est d’étudier les techniques de routage MC dans un contexte sans fil multi-saut en vue d’obtenir de meilleures performances. Nous avons choisi pour notre étude une extension MC du protocole OLSR, appelée MP-OLSR. Nous évaluons ses performances sous divers scénarios sous NS-2. Ces tests d’évaluation nous ont amenés à mettre en ´evidence deux problèmes dans MP-OLSR : la réactivité du protocole de routage MC suite à des ruptures de route et la stratégie de répartition des données sur les chemins multiples. Nous avons étudié la réactivité de tels mécanismes dans MP-OLSR. Nous avons proposé trois nouvelles techniques de réparation de pannes qui diminuent les temps de rétablissement d’une route et réduisent le taux de perte des flux transmis. Nous proposons aussi un mécanisme qui détecte la dégradation de la qualité des liens durant le transfert d’un trafic de données. Les informations déduites de ce mécanisme servent à adapter la proportion de trafic à affecter à chaque chemin selon les conditions réseaux. Cette nouvelle variante du protocole MP-OLSR est évaluée par simulation. / Wireless multi-hop networks consist of a collection of mobile and/or fixed nodes which dynamically exchange data with (or without) reliance on a (any) centralized administration. They are by definition self-organized. The frequent topological changes make multi-hop routing a crucial issue for these networks. To overcome these problems, new forms of routing schemes are used as the multipath routing (MP). MP routing uses multiple paths to send data and can be regarded as an effective solution for these networks. The purpose of this PhD thesis is to study the MP routing techniques in a wirelessmulti-hop context for better performance. We choose for our study a MP extension of OLSR, called MP-OLSR. We evaluate its performance under various scenarios in NS-2. These tests have led us to highlight two problems in MP-OLSR : the long recovery delays when facing network failure situations and the allocation strategy of data on multiple paths. We define and seek to evaluate the latency introduced by both protocols OLSR and MP-OLSR to find a new path after a link failure. We propose three new different recovery schemes and accordingly extend these original protocols in order to decrease theexpected latency and reduce the packet loss rate of transmitted flow. We also propose a mechanism which is able to detect the deterioration of the link quality during the transfer of data traffic. The information derived from this mechanism is used to adjust the proportion of traffic to be assigned to each path according to network conditions. This new version of MP-OLSR protocol is evaluated by simulation.

Fundação de Apoio a Pesquisa e à Inovação Tecnológica do Estado de Sergipe - FAPITEC/SE / With the popularity of the Internet and the emergence of new services, it has become increasingly necessary to make a network planning, in order to ensure that each of the elements that compose it are used e ciently. Moreover, it is necessary to control and monitor the network, making sure that everything is running the way it was planned. In networks using the SDN paradigm, by introducing a network controller, is possible the separation between the data plane (hardware) and control plane (software) existing on the network devices, allowing that new protocols and technologies are implemented and tested on any network device, regardless of its manufacturer. In contrast with it, the following question arises: how to apply tra c monitoring in an SDN network ahead of his centralized control architecture without causing delays or inconsistencies? This work proposed a tra c monitoring service for SDN networks based on the OpenFlow protocol, called SDNMonitor, which aims to provide a view of network data tra c at three levels of granularity, for each port of each switch, for each flow and for each network service. Additionally, it was also proposed a load balancing service based on the use of Round-Robin and Bandwidth-Based algorithms. The experimental evaluation of these services was conducted through controlled experiments, which were generated and monitored some tra c. The results showed that the SDNMonitor service could monitor the network tra c in the three levels of granularity without impacting negatively on its operation, and that the load balancing service has been able to improve network tra c. / Com a popularidade da Internet e a emergência de novos serviços, tornou-se cada vez mais necessário fazer um planejamento da rede, com o objetivo de assegurar que cada um dos elementos que a compõem sejam utilizados de forma eficiente. Além disso, é necessário controlar e monitorar a rede, verificando se tudo está sendo executando da maneira que foi planejada. Em redes que utilizam o paradigma SDN, através da introdução de um controlador de rede, é possível a separação entre o plano de dados (hardware) e o plano de controle (software) existentes nos dispositivos de rede, permitindo que novos protocolos e novas tecnologias sejam implementadas e testadas em qualquer dispositivo de rede, independente do seu fabricante. Em contrapartida, surge o seguinte questionamento: como aplicar monitoramento de tráfego em uma rede SDN diante da sua arquitetura de controle centralizada sem causar atrasos ou inconsistências? Este trabalho propôs um serviço de monitoramento de tráfego em redes SDN baseado no protocolo OpenFlow, chamado SDNMonitor, que tem como principal objetivo prover uma visão do tráfego de dados da rede em três níveis de granularidade, por cada porta de cada switch, por cada fluxo e por cada serviço de rede. Adicionalmente, também foi proposto um serviço de balanceamento de carga, baseado na utilização dos algoritmos Round-Robin e Bandwidth-Based. A avaliação experimental destes serviços foi realizada através de experimentos controlados, onde foram gerados e monitorados alguns tráfegos. Os resultados demonstraram que o serviço SDNMonitor conseguiu monitorar o tráfego da rede nos três níveis de granularidade sem impactar de forma negativa no seu funcionamento, e que o serviço de balanceamento de carga foi capaz de melhorar o tráfego da rede.

Submitted by Luciana Ferreira (lucgeral@gmail.com) on 2015-03-05T15:35:28Z No. of bitstreams: 2 Dissertação - Micael Oliveira Massula Carvalho de Mello - 2014.pdf: 489311 bytes, checksum: 15900b2c2d82201091cb1f73eeb459f4 (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Approved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2015-03-06T10:37:11Z (GMT) No. of bitstreams: 2 Dissertação - Micael Oliveira Massula Carvalho de Mello - 2014.pdf: 489311 bytes, checksum: 15900b2c2d82201091cb1f73eeb459f4 (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Made available in DSpace on 2015-03-06T10:37:11Z (GMT). No. of bitstreams: 2 Dissertação - Micael Oliveira Massula Carvalho de Mello - 2014.pdf: 489311 bytes, checksum: 15900b2c2d82201091cb1f73eeb459f4 (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Previous issue date: 2014-12-19 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / Wireless Mesh Networks (WMNs) are infrastructures with autonomic properties, such as self-organization and self-recovery, which can be developed with widely available technologies and low cost solutions. Besides their current applications, such as community networks and broad-band Internet access, WMNs can offer contributions in the context of the Internet of Things and help to build robust infrastructures to smart energy networks, among other uses. However, WMNs usually have performance issues due to overload in certain parts of the network and interference in wireless links. In this context, it is important that solutions are used to promote load-balancing and to mitigate interference between wireless links. Research in this area shows that one of the most promising approaches are in the subject of the joint routing and channel assignment. However, most of the previous works depends on the knowledge of the network traffic and handle flows with low granularity. In this thesis, we handle the performance problem in WMNs, in particular those having multiple radios and multiple available channels, using a joint approach, but without the mentioned restrictions. Our proposal is a joint heuristic, whose main contribution is the routing, which pursues the compromise between load-balancing and the path length of the network flows. We have developed our proposal in the Network Simulator 3 (ns-3) and have compared it with other works in literature. We found that our heuristic provides throughput improvements in most of the analyzed scenarios, besides promote greater justice between the flows that compete for resources. / Redes em Malha Sem Fio - Wireless Mesh Networks (WMNs) são infraestruturas com propriedades autonômicas, como auto-organização e autorrecuperação, que podem ser implementadas com tecnologias amplamente disponíveis e de custo acessível. Além de suas aplicações atuais, como redes comunitárias e redes de acesso à Internet, as WMNs podem auxiliar na comunicação de Internet das Coisas e constituir infraestruturas robustas para redes inteligentes de energia, dentre outros usos. No entanto, WMNs geralmente apresentam questões relativas a desempenho devido a fatores como sobrecarga em determinadas partes da rede e interferências nos enlaces sem fio. Nesse contexto, é importante que sejam utilizadas soluções que promovam balanceamento de carga na rede e que minimizem as interferências entre os enlaces sem fio. A pesquisa nessa área tem mostrado que uma das abordagens mais promissoras consiste em tratar de maneira conjunta o roteamento e a atribuição de canais. Porém, a maior parte dos trabalhos dependem de conhecimento prévio do tráfego da rede e tratam fluxos com baixa granularidade. Nesta dissertação, tratamos o problema de desempenho em WMNs, em especial as que possuem múltiplos rádios e múltiplos canais disponíveis, utilizando uma abordagem conjunta, mas sem as restrições anteriores. Nossa proposta é uma heurística conjunta, cuja principal contribuição está no roteamento, o qual persegue um compromisso entre o balanceamento de carga e o comprimento dos caminhos seguidos pelos fluxos. Implementamos nossa proposta no Network Simulator 3 (ns-3) e a comparamos com outros trabalhos da literatura. Verificamos que nossa heurística apresenta ganhos de vazão na maior parte dos cenários avaliados, além de promover maior justiça entre os fluxos que concorrem pelos recursos.

Orientadores: Edmundo Roberto Mauro Madeira, Luiz Eduardo Buzato / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-21T19:31:37Z (GMT). No. of bitstreams: 1 Nakai_AlanMassaru_D.pdf: 3199160 bytes, checksum: b939ce461412f42df4f371a7cf37d2db (MD5) Previous issue date: 2012 / Resumo: A distribuição de carga é um problema intrínseco a sistemas distribuídos. Esta tese aborda este problema no contexto de servidores web geograficamente distribuídos. A replicação de servidores web em datacenters distribuídos geograficamente provê tolerância a falhas e a possibilidade de fornecer melhores tempos de resposta aos clientes. Uma questão chave em cenários como este é a eficiência da solução de distribuição de carga empregada para dividir a carga do sistema entre as réplicas do servidor. A distribuição de carga permite que os provedores façam melhor uso dos seus recursos, amenizando a necessidade de provisão extra e ajudando a tolerar picos de carga até que o sistema seja ajustado. O objetivo deste trabalho foi estudar e propor novas soluções de distribuição de carga para servidores web geograficamente distribuídos. Para isso, foram implementadas duas ferramentas para apoiar a análise e o desenvolvimento de novas soluções, uma plataforma de testes construída sobre a implementação real de um serviço web e um software de simulação baseado em um modelo realístico de geração de carga para web. As principais contribuições desta tese são as propostas de quatro novas soluções de distribuição de carga que abrangem três diferentes tipos: soluções baseadas em DNS, baseadas em clientes e baseadas em servidores / Abstract: Load balancing is a problem that is intrinsic to distributed systems. In this thesis, we study this problem in the context of geographically distributed web servers. The replication of web servers on geographically distributed datacenters allows the service provider to tolerate failures and to improve the response times perceived by clients. A key issue for achieving good performance in such a deployment is the efficiency of the load balancing solution used to distribute client requests among the replicated servers. The load balancing allows providers to make better use of their resources, soften the need for over-provision, and help tolerate abrupt load peaks until the system can be adjusted. The objective of this work was to study and propose load balancing solutions for geographically distributed web servers. In order to accomplish this objective, we have implemented two tools that support the analysis and development of load balancing solutions, a testbed that was built on top of a real web service implementation and simulation software that is based on a realistic model for web load generation. The main contributions of this thesis are the proposals of four new load balancing solutions that comprehend three types: DNS-based, client-based, and server-based / Doutorado / Ciência da Computação / Doutor em Ciência da Computação

Denna rapport behandlar en undersökning av olika lastbalanseringsalgoritmer i Linux Virtual Server. Undersökningen har gjorts i ett webbkluster (Apache var webbservern som användes) med tre heterogena noder, där operativsystemet var den detalj som skiljde dem åt. Operativsystemen som ingick i undersökningen var Windows Server 2008 R2, CentOS 6.2 och FreeBSD 9.0. De faktorer som undersöktes mellan de olika algoritmerna var klustrets genomsnittliga svarstid vid olika belastning och hur många anslutningar som kunde hanteras av klustret, detta gjordes med verktyget httperf. Undersökningen ger svar på hur ett heterogent webbklusters genomsnittligasvarstid och arbetskapacitet kan skilja sig åt beroende på vilken algoritm som används för lastbalansering. Resultatet visar att den genomsnittliga svarstiden håller sig låg tills en hastig stigning inträffar. Shortest Expected Delay och Weighted Least-Connection Scheduling kunde hantera störst antal anslutningar. / This report covers an investigation of different load balancing algorithms in Linux Virtual Server. The investigation was done in a web cluster (with Apache as the software being used) consisting of three heterogeneous nodes, where the operating system was the detail that differentiated the nodes. The operating systems that were used in the investigation were Windows Server 2008 R2, CentOS 6.2 and FreeBSD 9.0. The factors examined were average response time at different load and how many connections the cluster could cope with, these factors were examined by measurements taken with the tool httperf. The investigation gives an answer to how a heterogeneous web clustersaverage response time and working capacity can be affected by the choice of load balancing algorithm. The result shows that the average response time stays low until a sudden rise occurs. Shortest Expected Delay and Weighted Least-Connection Scheduling could handle the largest number of connections.

Dans cette thèse, on s’intéresse à la tâche de diffusion dans les réseaux de capteurs sans fils dynamiques RCSF. C'est une tache essentielle et primordiale puisqu'elle est nécessaire pour réaliser la découverte de voisinage, le routage, la distribution d’informations dans tout le réseau, la localisation des nœuds et la synchronisation du temps.[...] / In this thesis, we are interested in the task of diffusion in networks of dynamic wireless sensors RCSF. This is an essential and primordial task, since it is necessary for neighbor discovery, routing, information distribution throughout the network, node location and time synchronization.[...]