Conforme o paralelismo a nível de threads aumenta nas arquiteturas modernas devido ao aumento do número de núcleos por processador e processadores por sistema, a complexidade da hierarquia de memória também aumenta. Tais hierarquias incluem diversos níveis de caches privadas ou compartilhadas e tempo de acesso não uniforme à memória. Um desafio importante em tais arquiteturas é a movimentação de dados entre os núcleos, caches e bancos de memória primária, que ocorre quando um núcleo realiza uma transação de memória. Neste contexto, a redução da movimentação de dados é um dos pilares para futuras arquiteturas para manter o aumento de desempenho e diminuir o consumo de energia. Uma das soluções adotadas para reduzir a movimentação de dados é aumentar a localidade dos acessos à memória através do mapeamento de threads e dados. Mecanismos de mapeamento do estado-da-arte aumentam a localidade de memória mapeando threads que compartilham um grande volume de dados em núcleos próximos na hierarquia de memória (mapeamento de threads), e mapeando os dados em bancos de memória próximos das threads que os acessam (mapeamento de dados). Muitas propostas focam em mapeamento de threads ou dados separadamente, perdendo oportunidades de ganhar desempenho. Outras propostas dependem de traços de execução para realizar um mapeamento estático, que podem impor uma sobrecarga alta e não podem ser usados em aplicações cujos comportamentos de acesso à memória mudam em diferentes execuções. Há ainda propostas que usam amostragem ou informações indiretas sobre o padrão de acesso à memória, resultando em informação imprecisa sobre o acesso à memória. Nesta tese de doutorado, são propostas soluções inovadoras para identificar um mapeamento que otimize o acesso à memória fazendo uso da unidade de gerência de memória para monitor os acessos à memória. As soluções funcionam dinamicamente em paralelo com a execução da aplicação, detectando informações para o mapeamento de threads e dados. Com tais informações, o sistema operacional pode realizar o mapeamento durante a execução das aplicações, não necessitando de conhecimento prévio sobre o comportamento da aplicação. Como as soluções funcionam diretamente na unidade de gerência de memória, elas podem monitorar a maioria dos acessos à memória com uma baixa sobrecarga. Em arquiteturas com TLB gerida por hardware, as soluções podem ser implementadas com pouco hardware adicional. Em arquiteturas com TLB gerida por software, algumas das soluções podem ser implementadas sem hardware adicional. As soluções aqui propostas possuem maior precisão que outros mecanismos porque possuem acesso a mais informações sobre o acesso à memória. Para demonstrar os benefícios das soluções propostas, elas são avaliadas com uma variedade de aplicações usando um simulador de sistema completo, uma máquina real com TLB gerida por software, e duas máquinas reais com TLB gerida por hardware. Na avaliação experimental, as soluções reduziram o tempo de execução em até 39%. O ganho de desempenho se deu por uma redução substancial da quantidade de faltas na cache, e redução do tráfego entre processadores. / As thread-level parallelism increases in modern architectures due to larger numbers of cores per chip and chips per system, the complexity of their memory hierarchies also increase. Such memory hierarchies include several private or shared cache levels, and Non-Uniform Memory Access nodes with different access times. One important challenge for these architectures is the data movement between cores, caches, and main memory banks, which occurs when a core performs a memory transaction. In this context, the reduction of data movement is an important goal for future architectures to keep performance scaling and to decrease energy consumption. One of the solutions to reduce data movement is to improve memory access locality through sharing-aware thread and data mapping. State-of-the-art mapping mechanisms try to increase locality by keeping threads that share a high volume of data close together in the memory hierarchy (sharing-aware thread mapping), and by mapping data close to where its accessing threads reside (sharing-aware data mapping). Many approaches focus on either thread mapping or data mapping, but perform them separately only, losing opportunities to improve performance. Some mechanisms rely on execution traces to perform a static mapping, which have a high overhead and can not be used if the behavior of the application changes between executions. Other approaches use sampling or indirect information about the memory access pattern, resulting in imprecise memory access information. In this thesis, we propose novel solutions to identify an optimized sharing-aware mapping that make use of the memory management unit of processors to monitor the memory accesses. Our solutions work online in parallel to the execution of the application and detect the memory access pattern for both thread and data mappings. With this information, the operating system can perform sharing-aware thread and data mapping during the execution of the application, without any prior knowledge of their behavior. Since they work directly in the memory management unit, our solutions are able to track most memory accesses performed by the parallel application, with a very low overhead. They can be implemented in architectures with hardwaremanaged TLBs with little additional hardware, and some can be implemented in architectures with software-managed TLBs without any hardware changes. Our solutions have a higher accuracy than previous mechanisms because they have access to more accurate information about the memory access behavior. To demonstrate the benefits of our proposed solutions, we evaluate them with a wide variety of applications using a full system simulator, a real machine with software-managed TLBs, and a trace-driven evaluation in two real machines with hardware-managed TLBs. In the experimental evaluation, our proposals were able to reduce execution time by up to 39%. The improvements happened to a substantial reduction in cache misses and interchip interconnection traffic.

Este trabalho propõe um modelo hierárquico para coleta de dados de monitoramento em sistemas distribuídos. Seu objetivo é proporcionar a análise on-line do comportamento de sistemas e programas distribuídos. O meio escolhido para realizar essa análise foi a visualização. Inicialmente é apresentada uma contextualização sobre monitoramento de sistemas distribuídos. Também são abordados aspectos específicos ao monitoramento de Grid. Após, é analisado um conjunto de ferramentas de monitoramento. Então tem-se a apresentação do modelo proposto. Esse é composto por coletores locais, por uma hierarquia de agregadores e por clientes. É utilizado o modelo push de transmissão de dados e há um mecanismo de subscrição aos coletores. Foi implementado um protótipo do modelo de coleta proposto, que foi utilizado na implementação de um protótipo de ferramenta de monitoramento on-line. Nessa, os dados coletados são fornecidos ao DIMVisual, que é um modelo de integração de dados para visualização. Para visualização, o protótipo utiliza a ferramenta TRIVA, que recebe os dados integrados como entrada. Essa ferramenta foi modificada para gerar uma visualização que é atualizada de maneira on-line. Também foram realizados experimentos para avaliar o tempo necessário para enviar mensagens com diferentes hierarquias e configurações dos coletores. Além disso, foi avaliada a capacidade de o cliente implementado processar os dados recebidos, gerando sua visualização. / This work proposes a hierarchical model for collecting monitoring data from distributed systems. Its goal is to allow the on-line analysis of the behavior of distributed systems and applications. The means we chose to perform this analysis is to generate a visualization of the collected information. In the beginning of this dissertation we present an overview of the monitoring of distributed systems. Aspects that are specific to the monitoring of Grid systems are also reviewed. Next, we have an analysis of a set of monitoring tools. Then we present the proposed model, which is composed by local collectors, an hierarchical structure of aggregators and clients. A push data transmission model is used in the model and it also has a subscription mechanism. A prototype monitoring tool was implemented, integrating the data collection model with DIMVisual and TRIVA. The former is a data integration model whose output is formatted to be used as input for a visualization tool. The later is a visualization tool which, in the prototype, receives the integrated data from DIMVisual. TRIVA generates a visualization of the received information, which is updated in an on-line fashion. In order to evaluate the model, we performed a set of experiments using the prototype. One of the experiments measured the time spent to send data though different hierarchies. In these tests we have also varied the quantity and the configuration of the collectors. In another experiment we evaluated the capacity of the client to process the received data.

Submitted by Cleide Dantas (cleidedantas@ufpa.br) on 2014-11-14T13:29:37Z No. of bitstreams: 2 license_rdf: 22974 bytes, checksum: 99c771d9f0b9c46790009b9874d49253 (MD5) Dissertacao_ModelagemMcsemDominio.pdf: 2587982 bytes, checksum: 128281a90d0470ea7eb6ca5d50968966 (MD5) / Approved for entry into archive by Ana Rosa Silva (arosa@ufpa.br) on 2014-11-14T17:15:28Z (GMT) No. of bitstreams: 2 license_rdf: 22974 bytes, checksum: 99c771d9f0b9c46790009b9874d49253 (MD5) Dissertacao_ModelagemMcsemDominio.pdf: 2587982 bytes, checksum: 128281a90d0470ea7eb6ca5d50968966 (MD5) / Made available in DSpace on 2014-11-14T17:15:28Z (GMT). No. of bitstreams: 2 license_rdf: 22974 bytes, checksum: 99c771d9f0b9c46790009b9874d49253 (MD5) Dissertacao_ModelagemMcsemDominio.pdf: 2587982 bytes, checksum: 128281a90d0470ea7eb6ca5d50968966 (MD5) Previous issue date: 2009 / CNPq - Conselho Nacional de Desenvolvimento Científico e Tecnológico / A modelagem do mCSEM é feita normalmente no domínio da frequência, desde sua formulação teórica até a análise dos resultados, devido às simplificações nas equações de Maxwell, possibilitadas quando trabalhamos em um regime de baixa frequência. No entanto, a abordagem através do domínio do tempo pode em princípio fornecer informação equivalente sobre a geofísica da subsuperfície aos dados no domínio da frequência. Neste trabalho, modelamos o mCSEM no domínio da frequência em modelos unidimensionais, e usamos a transformada discreta de Fourier para obter os dados no domínio do tempo. Simulamos ambientes geológicos marinhos com e sem uma camada resistiva, que representa um reservatório de hidrocarbonetos. Verificamos que os dados no domínio do tempo apresentam diferenças quando calculados para os modelos com e sem hidrocarbonetos em praticamente todas as configurações de modelo. Calculamos os resultados considerando variações na profundidade do mar, na posição dos receptores e na resistividade da camada de hidrocarbonetos. Observamos a influência da airwave, presente mesmo em profundidades oceânicas com mais de 1000m, e apesar de não ser possível uma simples separação dessa influência nos dados, o domínio do tempo nos permitiu fazer uma análise de seus efeitos sobre o levantamento. Como parte da preparação para a modelagem em ambientes 2D e 3D, fazemos também um estudo sobre o ganho de desempenho pelo uso do paralelismo computacional em nossa tarefa. / The mCSEM modelling is usually done in the frequency domain, from its theoretical formulation to the analysis of the results. However, the time domain approach is, in principle, capable of providing equivalent information about the geo-electric structure of the subsurface. In this work, we model frequency domain mCSEM data in 1-D environments, then we perform the discrete Fourier transform to obtain time domain results. We simulated marine geological environments with and without the resistive layer that represents the hydrocarbon reservoir. We verified that the time domain data are significantly different when calculated for models with and without hydrocarbons in almost all model configurations. We calculated the results considering variations in the sea depth, in the position of the receivers and in the resistivity of the hydrocarbon layer. We observed the influence of the airwave, even at sea depths greater than 1000m, and although a simple separation of this influence on data is not possible, the time domain allowed us to do an analysis of its effects on the survey. As part of the preparation for the 2-D and 3-D modelling, we also have studied the gain in performance from the use of parallel processing in our task.

Estudos recentes apontam para a importância de investigações mais abrangentes sobre o universo da formação médica, ressaltando que essa não é constituída somente de habilidades e procedimentos, mas, principalmente, por um complexo quadro de atitudes. Percebe-se que a carga horária do curso é extenuante e, mesmo assim, muitos estudantes se envolvem com uma infinidade de atividades extras durante a sua formação, construindo vasto currículo paralelo. Este estudo objetivou investigar as concepções dos estudantes de uma Faculdade de Medicina sobre as vivências, peculiaridades e papéis das atividades extracurriculares durante a formação médica. A investigação foi orientada pela abordagem qualitativa e estruturada em três etapas: pré-inquérito por meio da aplicação de questionário aos estudantes do 1º ao 6º ano de Medicina (n=423); entrevistas individuais, segundo roteiro semi-estruturado (n=24) e entrevistas em dois grupos focais constituídos por três encontros (n=14). Na 1ª etapa do estudo, os resultados apontaram que 90% dos participantes do 2º ano até o 4º ano do curso participam de atividades extracurriculares que estão vinculadas ao contexto universitário e despendem, em média, mais de 8h semanais. A participação em ligas acadêmicas foi a atividade mais freqüentemente relatada pelos estudantes do 1º ao 4º ano, sendo que “aproximar da prática médica" foi o principal motivo apontado nesse quesito. Em relação ao 5º e ao 6º ano, as participações em atividades de iniciação científica e monitorias foram as mais relatadas e motivadas pela “contribuição para o currículo". A Atlética, entidade estudantil que objetiva a participação em competições desportivas, obteve o envolvimento constante dos estudantes durante todos os anos do curso. Os dados advindos das entrevistas individuais revelaram que os estudantes de medicina identificam seu envolvimento com atividades extracurriculares como tentativa de preencher lacunas curriculares, suplementar o curso, integrar-se com os colegas de diferentes anos, atenderem indagações profissionais futuras e/ou proporcionar o distanciamento do cotidiano médico. A utilização da estratégia em grupo focal, alicerçada na abordagem do Sociodrama Educacional, possibilitou que conflitos e contradições, relativos ao cotidiano da formação médica, acabassem por emergir. Apesar dos benefícios apontados pelos estudantes, os dados levantados evidenciam sentimentos de insegurança e conflitos decorrentes da dificuldade deles em conciliar as atividades extracurriculares, o lazer e o curso. Além disso, as percepções dos estudantes sugerem a necessidade premente de ocupação do tempo livre, manifestando um antagonismo diante das insatisfações advindas do vulnerável período do curso médico. / Recent studies show the importance of more including inquiries on the universe of the medical formation, standing out that this is not only constituted of abilities and procedures, but, mainly, for a complex group of attitudes. The schedule of the course is exhausting, thus, many students involve themselves with an infinity of extra activities during their formation, constructing a vast parallel curriculum. This study aimed at inquiring the perceptions of students at a Medical School about their experiences and peculiarities, as well as the role of extracurricular activities during the medical formation. The inquiry was guided by the qualitative and structuralized boarding in three stages: pre-inquiry through the questionnaire application from 1st to 6th year of Medicine students (n=423); individual interviews, according to semi-structuralized script (n=24) and interviews in two focal groups consisting by three meetings (n=14). In the 1st stage of the study, the results had pointed that 90% of the participants of 2nd to 4th year of the course participate of extracurricular activities that are tied with the university context and expend, on average, 8h weekly. The participation in academic leagues was the activity more frequently told by the 1st to 4th year students, where “to approach to the medical practice" was the main reason pointed in this question. Regarding the 5th and 6th year, the participation in activities of scientific initiation and monitorized had been told and motivated by the “contribution for the curriculum". The “Atlética", an entity for students that objective the participation in sporting competitions, got the constant envolvement of the students during every year of the course. The resulting data of the individual interviews had disclosed that the medicine students identify their envolvement with extracurricular activities as an attempt to fill curricular gaps, to suplement the course, to combine themselves with the colleagues of different years, to take care of future professional investigations and/or to keep away from the medical routine. The use of the strategy in focal group, based on the approach of the Educational Sociodrama, made possible the appearance of conflicts and contradictions, related to the daily routine of the medical formation. Although the benefits students pointed, data evidence feelings of unreliability and decurrent conflicts because of their difficulty in conciliating the extracurricular activities, the leisure and the course. Moreover, the perceptions of the students suggest the necessity of free time occupation which serves as possible “counterpart" from the contradictions and dissatisfactions of the vulnerable period of the medical course.

Neste trabalho, propomos um método de paralelização de simulações de dinâmica molecular para execução em máquinas de memória distribuída, trabalhando sob passagem de mensagens. Nos limitamos à análise de implementação de sistemas com ensemble microcanônico de partículas de Lennard-Jones, desenvolvendo no entanto um sistema que pode ser expandido para incluir outras características. Mostramos que o sistema apresenta bom desempenho com relação à paralelização, representando uma alternativa viável para a simulação de sistemas com muitas partículas. / A method for parallelization of molecular dynamics simulations in distributed memory machines operating under the message-passing paradigm is proposed. Even though the analysis and implementation presented in this work were primarily restricted to the system model known as microcanonical emsemble of Lennard--Jones particles. the obtained system can easily be adapted for inclusion of other characteristics. It is shown t,hat. the developed system is well suited for parallelization, resulting in a feasible a1ternative for simulation of many-particle systems.

Estágio realizado no CERN, Suiça e orientado por Christian Theis e Eduard Feldbaumer / Tese de mestrado integrado. Engenharia Informátca e Computação. Faculdade de Engenharia. Universidade do Porto. 2008

Tese de doutoramento. Ciências da Engenharia. Faculdade de Engenharia. Universidade do Porto. 1998

Esta Dissertação de Mestrado propõe dois novos algoritmos para tornar mais eficiente o escalonamento on-line de tarefas com dependências estritas em agregados de computadores que usam como middleware para troca de mensagens alguma implementação da MPI (até a versão 2.1). Esses algoritmos foram projetados tendo-se em vista programas construídos no modelo de programação fork/join, onde a operação de fork é usada sobre uma chamada recursiva da função. São eles: 1. O algoritmo RatMD, implementado através de uma biblioteca de primitivas do tipo map-reduce, que funciona para qualquer implementação MPI, com qualquer versão da norma. Utilizado para minimizar o tempo de execução de uma computação paralela; e 2. O algoritmo RtMPD, implementado através de um sistema distribuído sobre daemons gerenciadores de processos criados dinamicamente com a implementação MPICH2 (que implementa a MPI-2). Utilizado para permitir execuções de instâncias maiores de programas paralelos dinâmicos. Ambos se baseiam em roubo de tarefas, que é a estratégia de balanceamento de carga mais difundida na literatura. Para ambos os algoritmos apresenta-se modelagem téorica de custos. Resultados experimentais obtidos ficam dentro dos limites teóricos calculados. RatMD provê uma redução no tempo de execução de até 80% em relação ao algoritmo usual (baseado em round-robin), com manutenção do speedup próximo ao linear e complexidade espacial idêntica à popular implementação com round-robin. RtMPD mantém, no mínimo, o mesmo desempenho que a implementação canônica do escalonamento em MPICH2, dobrando-se o limite físico de processos executados simultaneamente por cada nó. / This Master’s Dissertation proposes two new algorithms for improvement on on-line scheduling of dynamic-created tasks with strict dependencies on clusters of computers using MPI (up to version 2.1) as its middleware for message-passing communication. These algorithms were built targeting programs written on the fork-join model, where the fork operation is always called over an recursive function call. They are: 1. RatMD, implemented as a map-reduce library working for any MPI implementation, on whatever norm’s version. Used for performance gain; and 2. RtMPD, implemented as a distributed system over dynamic-generated processes manager daemons with MPICH2 implentation of MPI. Used for executing larger instances of dynamic parallel programs. Both algorithms are based on the (literature consolidated) work stealing technique and have formal guarantees on its execution time and load balancing. Experimental results are within theoretical bounds. RatMD shows an improvement on the performance up to 80% when paired with more usual algorithms (based on round-robin strategy). It also provides near-linear speedup and just about the same space-complexity on similar implementations. RtMPD keeps, at minimum, the very same performance of the canonical MPICH2 implementation, near doubling the physical limit of simultaneous program execution per cluster node.

Os avanços nas tecnologias de rede e nos componentes computacionais possibilitaram a criação dos sistemas de Computação Voluntária (CV) que permitem que voluntários doem seus ciclos de CPU ociosos da máquina para um determinado projeto. O BOINC é a infra-estrutura mais popular atualmente, composta de mais 5.900.000 máquinas que processam mais de 4.003 TeraFLOP por dia. Os projetos do BOINC normalmente possuem centenas de milhares de tarefas independentes e estão interessados no throughput. Cada projeto tem seu próprio servidor que é responsável por distribuir unidades de trabalho para os clientes, recuperando os resultados e validando-os. Os algoritmos de escalonamento do BOINC são complexos e têm sido usados por muitos anos. Sua eficiência e justiça foram comprovadas no contexto dos projetos orientados ao throughput. Ainda, recentemente, surgiram projetos em rajadas, com menos tarefas e interessados no tempo de resposta. Diversos trabalhos propuseram novos algoritmos de escalonamento para otimizar seu tempo de resposta individual. Entretanto, seu uso pode ser problemático na presença de outros projetos. Neste texto, são estudadas as consequências do comportamento não cooperativo nos ambientes de Computação Voluntária. Para realizar o estudo, foi necessário modificar o simulador SimGrid para melhorar seu desempenho na simulação dos sistemas de CV. A primeira contribuição do trabalho é um conjunto de melhorias no núcleo de simulação do SimGrid para remover os gargalos de desempenho. O resultado é um simulador consideravelmente mais rápido que as versões anteriores e capaz de rodar experimentos nessa área. Ainda, como segunda grande contribuição, apresentou-se como os algoritmos de escalonamento atuais do BOINC são incapazes de garantir a justiça e isolação entre os projetos. Os projetos em rajadas podem impactar drasticamente o desempenho de todos os outros projetos (rajadas ou não). Para estudar tais interações, realizou-se um detalhado, multi jogador e multi objetivo, estudo baseado em teoria dos jogos. Os experimentos e análise realizados proporcionaram um bom entendimento do impacto dos diferentes parâmetros de escalonamento e mostraram que a otimização não cooperativa pode resultar em ineficiências e num compartilhamento injusto dos recursos. / Advances in inter-networking technology and computing components have enabled Volunteer Computing (VC) systems that allows volunteers to donate their computers’ idle CPU cycles to a given project. BOINC is the most popular VC infrastructure today with over 5.900.000 hosts that deliver over 4.003 TeraFLOP per day. BOINC projects usually have hundreds of thousands of independent tasks and are interested in overall throughput. Each project has its own server which is responsible for distributing work units to clients, recovering results and validating them. The BOINC scheduling algorithms are complex and have been used for many years now. Their efficiency and fairness have been assessed in the context of throughput oriented projects. Yet, recently, burst projects, with fewer tasks and interested in response time, have emerged. Many works have proposed new scheduling algorithms to optimize individual response time but their use may be problematic in presence of other projects. In this text, we study the consequences of non-cooperative behavior in volunteer computing environment. In order to perform our study, we needed to modify the SimGrid simulator to improve its performance simulating VC systems. So, the first contribution is a set of improvements in SimGrid’s core simulation to remove its performance bottlenecks. The result is a simulator considerably faster than the previous versions and able to run VC experiments. Also, in the second contribution, we show that the commonly used BOINC scheduling algorithms are unable to enforce fairness and project isolation. Burst projects may dramatically impact the performance of all other projects (burst or non-burst). To study such interactions, we perform a detailed, multi-player and multi-objective game theoretic study. Our analysis and experiments provide a good understanding on the impact of the different scheduling parameters and show that the non-cooperative optimization may result in inefficient and unfair share of the resources.

Com o objetivo de ser portável e eficiente em arquiteturas HPC atuais, a execução de um programa paralelo deve ser adaptável. Este trabalho mostra como isso pode ser atingido utilizando MPI, através de criação dinâmica de processos, integrada com programação Divisão-e-Conquista e uma estratégia Work-Stealing para balancear os processos MPI, em ambientes heterogêneos e/ou dinâmicos, em tempo de execução. Este trabalho explica como implementar uma aplicação segundo o modelo de Divisão-e-Conquista com MPI, bem como a implementação de uma estratégia Work-Stealing. São apresentados resultados experimentais baseados em uma aplicação sintética, o problema das N-Rainhas (N-Queens). Valida-se tanto a adaptabilidade e a eficiência do código. Os resultados mostram que é possível utilizar um padrão amplamente difundido como o MPI, mesmo em plataformas de HPC não tão homogêneas como um cluster. / In order to be portable and efficient on modern HPC architectures, the execution of a parallel program must be adaptable. This work shows how to achieve this in MPI, by the dynamic creation of processes, coupled with Divide-and-Conquer programming and a Work-Stealing strategy to balance the MPI processes, in a heterogeneous and/or dynamic environment, at runtime. The application of Divide and Conquer with MPI is explained, as well as the implementation of a Work-Stealing strategy. Experimental results are provided, based on a synthetic application, the N-Queens computation. Both the adaptability of the code and its efficiency are validated. The results show that it is possible to use widely spread standards such as MPI, even in parallel HPC platforms that are not as homogeneous as a Cluster.