Neste trabalho, apresenta-se uma adaptação dos procedimentos utilizados nos códigos computacionais seqüenciais advindos do MEF, para utilizá-los em multicomputadores. Desenvolve-se uma rotina para a montagem do sistema linear particionado entre os diversos processadores. Resolve-se o sistema de equações lineares geradas mediante a rotina do PIM (Parallel Iterative Method). São feitas adaptações deste pacote para se aproveitar as características comuns do sistema linear gerado pelo MEF: esparsidade e simetria. A técnica de resolução do sistema em paralelo é otimizada com o uso de dois tipos de pré-condicionadores: a decomposição incompleta de Cholesky (IC) generalizado e o POLY(0) ou Jacobi. É feita uma aplicação para a solução de pavimento com o algoritmo-base totalmente paralelizado. Também é avaliada a solução do sistema de equações de uma treliça. Mostram-se resultados de speed-up, de eficiência e de tempo para estes dois modelos estruturais. Além disso, é feito um estudo em processamento seqüencial da performance dos pré-condicionadores genéricos (IC) e do advindo de uma série truncada de Neumann, também generalizada, utilizando-se modelos estruturais de placa e chapa. / This work presents an adaptation of conventional finite element method (FEM) computing procedures to multicomputers. It is presented the procedure which the linear system of equations is split among the processor and its solution. It was improved a public software called PIM (Parallel Iterative Method) is used to solve this system of equations. These improvements explore efficiently the usual features of the FEM systems of equations: sparseness and symmetry. To improve the solution of the system, two different preconditioners are used: a generic Incomplete Cholesky (IC) and the Polynomial preconditioning (POLY(0) or Jacobi). It is carried out a full adaptation of the method to parallel computing with a program developed to analyse floor structures. The improved PIM is also used to solve the system of equations of a tri-dimensional truss. It is presented the speed-up, the efficiency and the time used in the resolution of the systems of equations for the floor and for the truss. It is also presented a study of performance in sequential processing of the generic (IC) and the generic Neumann series preconditioners in the analysis of plates in bending and in plane actions.

Submitted by Renata Lopes (renatasil82@gmail.com) on 2016-07-20T13:53:44Z No. of bitstreams: 1 rafaelbrunodasilvabrandi.pdf: 3504861 bytes, checksum: 82d36b1bf645c59e92876390b55e996b (MD5) / Approved for entry into archive by Adriana Oliveira (adriana.oliveira@ufjf.edu.br) on 2016-07-22T15:19:11Z (GMT) No. of bitstreams: 1 rafaelbrunodasilvabrandi.pdf: 3504861 bytes, checksum: 82d36b1bf645c59e92876390b55e996b (MD5) / Made available in DSpace on 2016-07-22T15:19:11Z (GMT). No. of bitstreams: 1 rafaelbrunodasilvabrandi.pdf: 3504861 bytes, checksum: 82d36b1bf645c59e92876390b55e996b (MD5) Previous issue date: 2011-03-30 / CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / O Sistema Elétrico Brasileiro (SEB) apresenta características peculiares devido às grandes dimensões do país e pelo fato da geração elétrica ser proveniente predominantemente de usinashidráulicasqueproporcionamaosistemaacapacidadedeumaregularizaçãoplurianualdos seusreservatórios. Asafluênciasnestasusinassãoestocásticasemuitasvezesapresentamcomportamentos complementares entre as diversas regiões do país, o que incentiva a existência de grandes intercâmbios energéticos entre os subsistemas através do Sistema Interligado Nacional (SIN). O planejamento da operação no horizonte de médio/longo prazo no país (que compreende a um período de 5 a 10 anos à frente com discretização mensal) é realizado por uma cadeia de modelos computacionais validados pelos principais agentes que atuam no SEB (comercialização, geração, transmissão e distribuição de energia). O principal modelo desta cadeia, a qual é desenvolvida pelo Centro de Pesquisas de Energia Elétrica/ELETROBRÁS, é o modelo NEWAVE que baseia-se na técnica de Programação Dinâmica Dual Estocástica (PDDE) para a determinação da política eletroenergética de médio prazo. O objetivo deste trabalho é implementar um modelo computacional para o planejamento da operação de médio prazo utilizando a metodologia de Programação Dinâmica Estocástica conjuntamente ao algoritmo de fechos convexos (PDE-ConvexHull) de uma forma computacionalmente eficiente (Fast-PDE-ConvexHull). Isto porque observou-se que quando utiliza-se a técnicadaPDE-ConvexHull,umnúmeroelevadodehiperplanossãoobtidosnacomposiçãodas funçõesdecustofuturoe,comisto,osdiversosproblemasdeprogramaçãolinearaseremresolvidos durante o processo iterativo podem tornar-se maiores, aumentando consideravelmente o tempodaexecuçãodocálculodapolíticaoperativa. Sendoassim,aprincipalcontribuiçãodeste trabalho é apresentar uma nova metodologia para a representação da função de custo futuro no problema de programação linear na qual o tempo computacional se torne menos sensível ao númerodehiperplanosobtidospeloalgoritmodefechosconvexos. Ressalta-sequetambémsão utilizadas técnicas de computação paralela com o objetivo de tornar o processo mais eficiente. A metodologia foi utilizada para o cálculo do planejamento de médio prazo do SEB, baseando-se em subsistemas equivalentes de energia. A metodologia Fast-PDE-ConvexHull foi incorporada a uma plataforma computacional, desenvolvida em C++/Java, capaz de considerar o mesmo conjunto de dados utilizado pelos modelos oficiais do SEB, compondo assim um modelo robusto para a resolução do problema. Primeiramente, para fins de validação da metodologia proposta, comparou-se os resultados obtidos pela metodologia da Fast-PDE-ConvexHull com os resultados obtidos pela utilização da técnica da PDE-ConvexHull com o objetivo verificar o ganho computacional e a aderência dos resultados. Por fim, como a plataforma computacional desenvolvida é capaz de utilizar o conjunto de dados oficiais disponibilizados para o SIN, fez-se o uso do Programa Mensal de Operação (PMO) de janeiro de 2011, disponibilizado pelo Operador Nacional do Sistema (ONS), como caso de estudo para comparação dos resultados obtidos pela metodologia proposta com os resultados obtidos pelo modelo NEWAVE. / The Brazilian National Grid (BNG) presents peculiar characteristics due to the huge territory dimensions and by the fact that the electricity generation is predominantly originated from hydraulic plants that provide for the system the capacity of a pluriannual regularization of the reservoirs. The water inflows to these plants are stochastic and often present complementary behavior among the regions of the country, stimulating the existence of big amounts of energy exchanges between the subsystems through the national grid. The long term operation planning problem (that includes a period of 5 to 10 years ahead with monthly discretization) is made by a chain of computational models that are validated by the main agents that act on BNG (commercialization, generation, transmition and distribution of energy). The primary model of this chain, which is developed by Electric Energy Research Center/ELETROBRÁS, is the NEWAVE model, which is based on the Stochastic Dual Dynamic Programming (SDDP) for electroenergetic policy determination on a long term horizon. Thisworkhastheobjectiveofimplementacomputationalmodelforthemid/longtermoperation planning using the Stochastic Dynamic Programming (SDP) together with the Convex Hull algorithm (PDE-ConvexHull) in a computationally efficient way (Fast-PDE-ConvexHull). This is because it was observed that when utilizing the PDE-ConvexHull technique, an elevated amount of hyperplanes are obtained for the composition of the cost-to-go function. So, the different linear programming problems to be solved during the iterative process can be turned larger, increasing the execution time for the operational policy calculus in a considerably manner. Thus, the main contribution of this work is to present a new methodology (FastPDE-ConvexHull) for the representation of the cost-to-go function on the linear programming problems where the computational time become less sensible to the number of hyperplanes obtained from the Convex Hull algorithm. It is highlighted that techniques of parallel computing was employed in order to turn the process more efficient. The methodology was utilized for the BNG’s long term planning calculus, based on the equivalent subsystems of energy. The methodology Fast-PDE-ConvexHull was incorporated to a computational platform, developed in C++/Java programming language, that is able to consider the same data set used by the official models acting on the BNG, compounding a robust model for the resolution of the problem. Firstly, in order to validate the proposed methodology, the results obtained from the FastPDE-ConvexHullarecomparedwiththoseobtainedfromtheutilizationofthePDE-ConvexHull technique aiming to verify the computational gain and the adherence between both results. Finally, as the elaborated computational platform is capable to use the official data set availablefortheNG,itwaspossibletheutilizationoftheMonthlyOperationalProgram(MOP) of January 2011, released by the Independent System Operator (ISO), as the study case for comparingtheresultsobtainedbytheproposedmethodologywiththeresultsobtainedfromthe NEWAVE model.

Submitted by isabela.moljf@hotmail.com (isabela.moljf@hotmail.com) on 2017-04-27T13:44:40Z No. of bitstreams: 1 julianamainentileallopes.pdf: 2178130 bytes, checksum: ac4968430d3e36932e81380861925cd4 (MD5) / Approved for entry into archive by Adriana Oliveira (adriana.oliveira@ufjf.edu.br) on 2017-05-12T15:49:17Z (GMT) No. of bitstreams: 1 julianamainentileallopes.pdf: 2178130 bytes, checksum: ac4968430d3e36932e81380861925cd4 (MD5) / Made available in DSpace on 2017-05-12T15:49:17Z (GMT). No. of bitstreams: 1 julianamainentileallopes.pdf: 2178130 bytes, checksum: ac4968430d3e36932e81380861925cd4 (MD5) Previous issue date: 2015-03-03 / CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / CNPq - Conselho Nacional de Desenvolvimento Científico e Tecnológico / FAPEMIG - Fundação de Amparo à Pesquisa do Estado de Minas Gerais / Estudos recentes sugerem que a duplicação completa dos genomas é muito mais comum do que sua estabilidade, ocorrendo em todas as angiospermas. Nesse contexto, Lippia alba (Mill.) N.E.Br. (Verbenaceae) constitui um modelo interessante de estudo, pois além de ser a espécie mais estudada dentro do gênero Lippia, é amplamente utilizada na medicina popular apresentando importância econômica, sobretudo em função da riqueza de seus óleos essenciais. Estudos recentes demonstraram a existência de pelo menos cinco diferentes níveis de ploidia em Lippia alba, revelando grande plasticidade do genoma. A fim de contribuir para entender a variação genética e o processo de poliploidização em Lippia alba, o presente trabalho objetivou identificar novos marcadores genéticos do tipo microssatélite e estimar a diversidade genética em 100 acessos de Lippia alba. Foram avaliados nove loci já descritos e 16 novos marcadores. O tamanho dos fragmentos foi detectado por eletroforese capilar usando o sequenciador MegaBACE1000 (GE Healthcare, Buckinghamshire, UK). A identificação dos alelos foi inferida utilizando o software Fragment Profile (GE Healthcare, Buckinghamshire, UK). Os dados finais foram exportados para uma planilha do Excel® e foram transformados nos arquivos de entrada específicos para cada programa computacional. Os valores de PIC (polymorphism information content) e heterozigosidade foram calculados por meio do programa Cervus v3.0.7. Os coeficientes de similaridades de Jaccard e Dice foram calculados para construir um dendrograma de acordo com o algoritmo UPGMA (Unweighted Pair Group Method with Arithmetic Mean) por meio dos softwares NTSYS e PAST. Para a análise por inferência Bayesiana, foi utilizado o programa STRUCTURE v 2.3.4. Foi possível observar a formação de grupos de acordo com o nível de ploidia e inferir a possível origem de alguns citótipos baseada na similaridade genética entre os acessos. Os resultados contribuem para fortalecer a hipótese de que os acessos tenham surgido por autopoliploidia. / Recent studies suggest that complete genome duplication is much more common than its stability, occurring in almost all angiosperms. Lippia alba (Mill.) N.E.Br. (Verbenaceae), is the most studied species within the genus Lippia, and it is widely used in folk medicine presenting economic importance mainly due to the richness of their essential oils. Recent studies have demonstrated the existence of at least five different ploidy levels in Lippia alba revealing a large genome plasticity making the species an interesting model of study. To better understand the genetic variation and the polyploidization process in Lippia alba, this study aimed to identify new genetic microsatellite markers and estimate the genetic diversity for 100 Lippia alba accessions. We assessed 9 loci already described and 16 new markers. The size of the fragments was detected by capillary electrophoresis using MegaBACE1000 sequencer (GE Healthcare, Buckinghamshire, UK). The identification of alleles was inferred using the Fragment Profile software (GE Healthcare, Buckinghamshire, UK). Final data were exported to an Excel spreadsheet according to the input files of each software used. PIC values (polymorphism information content) and heterozygosity were calculated using Cervus v3.0.7 software. Jaccard and Dice similarity coefficient were calculated to construct a dendrogram according to UPGMA algorithm (Unweighted Pair Group Method with Arithmetic Mean) using NTSYS and PAST softwares. Bayesian inference analysis was performed using STRUCTURE v 2.3.4 program. It was possible to observe the formation of groups according to the ploidy level and infer the possible origin of some cytotypes based on genetic similarity among accessions. Results contribute to support the hypothesis that the cytotypes have emerged by autopolyploidy.

Submitted by isabela.moljf@hotmail.com (isabela.moljf@hotmail.com) on 2017-08-18T10:44:31Z No. of bitstreams: 1 aryanecamposreis.pdf: 2882567 bytes, checksum: 1a13439227f336c21faf2248369b319c (MD5) / Rejected by Adriana Oliveira (adriana.oliveira@ufjf.edu.br), reason: on 2017-08-18T12:29:10Z (GMT) / Submitted by isabela.moljf@hotmail.com (isabela.moljf@hotmail.com) on 2017-08-18T13:17:38Z No. of bitstreams: 1 aryanecamposreis.pdf: 2882567 bytes, checksum: 1a13439227f336c21faf2248369b319c (MD5) / Rejected by Adriana Oliveira (adriana.oliveira@ufjf.edu.br), reason: on 2017-08-24T11:27:59Z (GMT) / Submitted by isabela.moljf@hotmail.com (isabela.moljf@hotmail.com) on 2017-08-24T15:19:15Z No. of bitstreams: 0 / Approved for entry into archive by Adriana Oliveira (adriana.oliveira@ufjf.edu.br) on 2017-08-30T14:32:15Z (GMT) No. of bitstreams: 0 / Made available in DSpace on 2017-08-30T14:32:15Z (GMT). No. of bitstreams: 0 Previous issue date: 2017-03-03 / Lippia alba (Verbenaceae), é uma espécie herbácea tropical com grande plasticidade fenotípica e genômica, amplamente utilizada na medicina popular. Recentemente, a espécie foi descrita como um novo complexo autopoliploide contendo cinco números cromossômicos (2x=30, 2x=30+8, 3x=45, 4x=60 e 6x=90), e esforços têm sido feitos a fim de entender sua origem e evolução. No presente trabalho, foram descritos perfis cariotípicos mais detalhados da espécie, por meio de mapeamento cromossômico utilizando sondas espécie-específicas e análises do comportamento meiótico e de viabilidade polínica. A partir do sequenciamento genômico de baixa cobertura (IIlumina MiSeq), foram desenvolvidos novos marcadores citogenéticos (denominados CL66 e CL98) os quais foram utilizados para o mapeamento cromossômico em acessos representando os cinco citótipos do complexo. Para a análise meiótica, seis estágios da divisão (metáfase I; anáfase I + telófase I; metáfase II; anáfase II + telófase II) foram quantificados, e aproximadamente, 100 células foram avaliadas para cada estágio. Os mesmos acessos foram avaliados quanto à viabilidade polínica (1.000 grãos de pólen foram quantificados para cada indivíduo). Os resultados da Hibridização Fluorescente in situ (FISH) revelaram que ambas as repetições satélite estão localizadas na porção terminal dos cromossomos. Em geral, a repetição CL98 mostrou um padrão uniforme nos diferentes acessos. Foram observados dois, três, quatro e seis cromossomos marcados em diploides, triploides, tetraploides e hexaploide, respectivamente, revelando que o número de cromossomos marcados variou proporcionalmente, de acordo com o nível de ploidia do acesso. Por outro lado, a repetição CL66 apresentou-se polimórfica. Variações foram observadas entre os acessos, principalmente, entre os indivíduos diploides. Com relação às análises meióticas, alto percentual de irregularidade foi observado nos citótipos poliploides. Entretanto, alguns acessos 2x também mostraram consideráveis erros durante a microsporogênese. Entre as irregularidades encontradas, destacam-se: pareamento cromossômico anormal; segregação cromossômica desigual; cromossomos perdidos; tríades e políades. Os resultados da viabilidade polínica corroboraram os dados da meiose. A partir do conjunto de dados obtidos foi possível concluir que 1) a metodologia para o desenvolvimento de marcadores cromossômicos específicos para L. alba mostrou-se eficiente; 2) as repetições satélite exibiram diferentes comportamentos (estável e dinâmico) no genoma de L. alba; 3) a ocorrência de microsporogênese irregular em diploides, associada à viabilidade polínica, sugerem que os acessos 2x sejam elementos importantes na formação do complexo poliploide e 4) a ampla variação cariotípica observada na espécie pode ser consequência de múltiplos e independentes eventos de duplicação genômica, aliado a rearranjos cromossômicos. Possivelmente, L. alba encontra-se em processo de estabilização do seu cariótipo tornando a espécie, um importante modelo para estudos de poliploides naturais nos trópicos. / Lippia alba (Verbenaceae) is a tropical aromatic shrub with extensive phenotypical and genomic plasticity widely used in traditional medicine. Recently, the species was described as a new natural autopolyploid complex with five distinct chromosome numbers (2x=30, 2x=30+8, 3x=45, 4x=60 and 6x=90). Strides have been done in order to understand the cytotypes origin and species evolution. In this study, a detailed karyotype of L. alba using Fluorescence in situ Hybridization (FISH) with species-specific probes was described. We also report the meiosis behavior and pollen viability in sixty accessions. Using massive parallel sequencing (IIlumina MiSeq platform) new cytogenetic landmarks (CL66 and CL98) were chosen for probing all cytotypes described for the species. For meiotic analysis, the percentage of abnormalities was quantified, evaluating around 100 cells in six stages (metaphase I; anaphase I + telophase I; metaphase II; anaphase II + telophase II). Around 1,000 pollen per accession were used to estimate pollen viability. FISH results revealed that both satDNA arrays are located preferentially on terminal sites of the chromosomes. In general, the CL98 repeat showed a uniform pattern in different accessions. We observed 2, 3, 4, and 6 marked chromosomes respectively in diploid, triploid, tetraploid and hexaploid accessions revealing that the number of depicted chromosomes varied proportionally according to the ploidy level. On the other hand, the CL66 repeat was polymorphic. Great variations were observed among the accessions mainly within the diploids. In general, the meiotic analysis revealed higher index of abnormalities in polyploid cytotypes. However, some 2x accessions also showed considerable irregularities during the microsporogenesis. Desynapsis, unequal segregation, lost chromosomes, triads and polyads were the most common irregularities observed. Pollen viability analysis corroborated the meiosis data. It was possible to conclude that 1) the development of specific landmarks for L. alba was efficient; 2) the karyotypic profiles of both satDNA revealed different behavior; 3) microsporogenesis analysis and pollen viability of 2x accessions suggest that diploids are the key point for the origin of the polyploid complex and 4) independent and multiples events of genome duplication associated to chromosome rearrangements may have generated great karyotypic variation in the species. L. alba karyotype is possibly under stabilization process making the species an important model to study natural polyploids in the tropics.

Orientador : Marconi Kolm Madrid / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-01T22:14:40Z (GMT). No. of bitstreams: 1 Nicolato_Fabricio_M.pdf: 2370208 bytes, checksum: 486d02d15c91ef4a0e5f5d0a6937ff81 (MD5) Previous issue date: 2002 / Mestrado

Dans cette thèse , nous proposons d’étudier des questions sur le parallélism de tâche avec dépendance de données dans le cadre de machines multicoeur avec des accélérateurs. La solution proposée a été développée en utilisant l’interface de programmation haute niveau XKaapi du projet MOAIS de l’INRIA Rhône-Alpes. D’abord nous avons étudié des questions liés à une approche d’exécution totalement asyncrone et l’ordonnancement par vol de travail sur des architectures multi-GPU. Le vol de travail avec localité de données a montré des résultats significatifs, mais il ne prend pas en compte des différents ressources de calcul. Ensuite nous avons conçu une interface et une modèle de coût qui permettent d’écrire des politiques d’ordonnancement sur XKaapi. Finalement on a évalué XKaapi sur un coprocesseur Intel Xeon Phi en mode natif. Notre conclusion est double. D’abord nous avons montré que le modèle de programmation data-flow peut être efficace sur des accélérateurs tels que des GPUs ou des coprocesseurs Intel Xeon Phi. Ensuite, le support à des différents politiques d’ordonnancement est indispensable. Les modèles de coût permettent d’obtenir de performance significatifs sur des calculs très réguliers, tandis que le vol de travail permet de redistribuer la charge en cours d’exécution. / Esta tese investiga os desafios no uso de paralelismo de tarefas com dependências de dados em arquiteturas multi-CPU com aceleradores. Para tanto, o XKaapi, desenvolvido no grupo de pesquisa MOAIS (INRIA Rhône-Alpes), é a ferramenta de programação base deste trabalho. Em um primeiro momento, este trabalho propôs extensões ao XKaapi a fim de sobrepor transferência de dados com execução através de operações concorrentes em GPU, em conjunto com escalonamento por roubo de tarefas em multi-GPU. Os resultados experimentais sugerem que o suporte a asincronismo é importante à escalabilidade e desempenho em multi-GPU. Apesar da localidade de dados, o roubo de tarefas não pondera a capacidade de processamento das unidades de processamento disponíveis. Nós estudamos estratégias de escalonamento com predição de desempenho em tempo de execução através de modelos de custo de execução. Desenvolveu-se um framework sobre o XKaapi de escalonamento que proporciona a implementação de diferentes algoritmos de escalonamento. Esta tese também avaliou o XKaapi em coprocessodores Intel Xeon Phi para execução nativa. A conclusão desta tese é dupla. Primeiramente, nós concluímos que um modelo de programação com dependências de dados pode ser eficiente em aceleradores, tais como GPUs e coprocessadores Intel Xeon Phi. Não obstante, uma ferramenta de programação com suporte a diferentes estratégias de escalonamento é essencial. Modelos de custo podem ser usados no contexto de algoritmos paralelos regulares, enquanto que o roubo de tarefas poder reagir a desbalanceamentos em tempo de execução. / In this thesis, we propose to study the issues of task parallelism with data dependencies on multicore architectures with accelerators. We target those architectures with the XKaapi runtime system developed by the MOAIS team (INRIA Rhône-Alpes). We first studied the issues on multi-GPU architectures for asynchronous execution and scheduling. Work stealing with heuristics showed significant performance results, but did not consider the computing power of different resources. Next, we designed a scheduling framework and a performance model to support scheduling strategies over XKaapi runtime. Finally, we performed experimental evaluations over the Intel Xeon Phi coprocessor in native execution. Our conclusion is twofold. First we concluded that data-flow task programming can be efficient on accelerators, which may be GPUs or Intel Xeon Phi coprocessors. Second, the runtime support of different scheduling strategies is essential. Cost models provide significant performance results over very regular computations, while work stealing can react to imbalances at runtime.

Orientadores: Guido Costa Souza de Araújo, José Nelson Amaral / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-27T10:12:59Z (GMT). No. of bitstreams: 1 Pereira_MarcioMachado_D.pdf: 2922376 bytes, checksum: 9775914667eadf354d7e256fb2835859 (MD5) Previous issue date: 2015 / Resumo: Nos últimos anos, Memórias Transacionais (Transactional Memories ¿ TMs) têm-se mostrado um modelo de programação paralela que combina, de forma eficaz, a melhoria de desempenho com a facilidade de programação. Além disso, a recente introdução de extensões para suporte a TM por grandes fabricantes de microprocessadores, também parece endossá-la como um modelo de programação para aplicações paralelas. Uma das questões centrais na concepção de sistemas de TM em Software (STM) é identificar mecanismos ou heurísticas que possam minimizar a contenção decorrente dos conflitos entre transações. Apesar de já terem sido propostos vários mecanismos para reduzir a contenção, essas técnicas têm um alcance limitado, uma vez que o conflito é evitado por interrupção ou serialização da execução da transação, impactando consideravelmente o desempenho do programa. Este trabalho explora uma abordagem complementar para melhorar o desempenho de STM através da utilização de escalonadores. Um escalonador de TM é um componente de software que decide quando uma determinada transação deve ser executada ou não. Sua eficácia é muito sensível às métricas usadas para prever o comportamento das transações, especialmente em cenários de alta contenção. Este trabalho propõe um novo escalonador, Dynamic Transaction Scheduler ¿ DTS, para selecionar a próxima transação a ser executada. DTS é baseada em uma política de "recompensa pelo sucesso" e utiliza uma métrica que mede com melhor precisão o trabalho realizado por uma transação. Memórias Transacionais em Hardware (HTMs) são mecanismos interessante para implementar TM porque integram o suporte a transações no nível da arquitetura. Por outro lado, aplicações que usam HTM podem ter o seu desempenho dificultado pela falta de escalabilidade e transbordamento da cache de dados. Este trabalho apresenta um extenso estudo de desempenho de aplicações que usam HTM na arquitetura Haswell da Intel. Ele avalia os pontos fortes e fracos desta nova arquitetura, realizando uma exploração das várias características das aplicações de TM. Este estudo detalhado revela as restrições impostas pela nova arquitetura e introduz uma política de serialização simples, porém eficaz, para garantir o progresso das transações, além de proporcionar melhor desempenho / Abstract: In the last few years, Transactional Memories (TMs) have been shown to be a parallel programming model that can effectively combine performance improvement with ease of programming. Moreover, the recent introduction of (H)TM-based ISA extensions, by major microprocessor manufacturers, also seems to endorse TM as a programming model for today¿s parallel applications. One of the central issues in designing Software TM (STM) systems is to identify mechanisms or heuristics that can minimize contention arising from conflicting transactions. Although a number of mechanisms have been proposed to tackle contention, such techniques have a limited scope, because conflict is avoided by either interrupting or serializing transaction execution, thus considerably impacting performance. This work explores a complementary approach to boost the performance of STM through the use of schedulers. A TM scheduler is a software component that decides when a particular transaction should be executed. Their effectiveness is very sensitive to the accuracy of the metrics used to predict transaction behaviour, particularly in high-contention scenarios. This work proposes a new Dynamic Transaction Scheduler ¿ DTS to select a transaction to execute next, based on a new policy that rewards success and an improved metric that measures the amount of effective work performed by a transaction. Hardware TMs (HTM) are an interesting mechanism to implement TM as they integrate the support for transactions at the lowest, most efficient, architectural level. On the other hand, for some applications, HTMs can have their performance hindered by the lack of scalability and by limitations in cache store capacity. This work presents an extensive performance study of the implementation of HTM in the Haswell generation of Intel x86 core processors. It evaluates the strengths and weaknesses of this new architecture by exploring several dimensions in the space of TM application characteristics. This detailed performance study provides insights on the constraints imposed by the Intel¿s Transaction Synchronization Extension (Intel¿s TSX) and introduces a simple, but efficient, serialization policy for guaranteeing forward progress on top of the best-effort Intel¿s HTM which was critical to achieving performance / Doutorado / Ciência da Computação / Doutor em Ciência da Computação

Com o avanço tecnológico dos últimos anos passou a ser normal vermos microprocessadores com múltiplos núcleos (cores). A expectativa é de que o crescimento da quantidade de núcleos passe a ser maior do que o crescimento da velocidade desses núcleos. Assim, além de se preocuparem em otimizar algoritmos sequenciais, os programadores começaram a dar mais atenção às possibilidades de aproveitamento de toda a capacidade oferecida pelos diversos cores. Existem alguns modelos de programação que permitem uma abordagem concorrente. O modelo de programação concorrente mais adotado atualmente é o baseado em threads, que utiliza memória compartilhada e é adotado em Java. Um outro modelo é o baseado em troca de mensagens, no qual as entidades computacionais ativas são denominadas atores. Nesse trabalho, estudamos a linguagem Scala e seu modelo de atores. Além disso, implementamos em Scala uma versão paralela de um algoritmo de classicação que simula o sistema imunológico dos animais, o AIRS paralelo, e comparamos seu desempenho com a versão em Java. / With the technological advance of the last years it has been normal to see microprocessors with multiple cores. The expectation is that the growth of number of cores becomes greater than the growth of the speed of these cores. This way, besides worrying about optimizing sequential algorithms, developers started to give more attention to the possibilities of proting from all capacity offered by the cores. There exists a few programming models that allow a concurrent approach. In these days, the most adopted concurrent programming model is the one based on threads, which uses shared memory and is adopted in Java. Other model is based on message passing, on which the active computational entities are called actors. In this project, we studied Scala language and its model based on actors. Besides that, we implemented in Scala a parallel version of a classification algorithm that simules the immune system of the animals, parallel AIRS, and compared its performance with the Java version.

Modelagem e controle de execução são duas abordagens do gerenciamento de processos de negócio que, embora complementares, têm se desenvolvido independentemente. Por um lado, a modelagem é normalmente conduzida por especialistas de negócio e explora aspectos semânticos do processo. Por outro lado, o controle de execução estuda mecanismos consistentes e eficientes de implementação. Este trabalho apresenta um método algorítmico que relaciona modelagem e controle de execução, por meio da geração de expressões algébricas a partir de digrafos acíclicos. Por hipótese, assumimos que modelos de processos de negócio são formados por estruturas baseadas em grafos, e mecanismos de controle de execução são baseados na interpretação de expressões de álgebra de processos. Para a geração de expressões algébricas, esta tese apresenta as propriedades topológicas de digrafos série-paralelo e define um sistema de transformação baseado em redução de digrafos. Além disso, um algoritmo de identificação de digrafos série-paralelo e geração de expressões algébricas é apresentado. O texto também discute o tratamento de digrafos que não são série-paralelo e apresenta, para alguns desses casos, soluções baseadas em mudanças topológicas. Finalmente, o algoritmo é ilustrado com o estudo de caso de uma aplicação real. / Modeling and execution control are complementary approaches of business process management that have been developed independently. On one hand, modeling is usually performed by business specialists and explores semantical aspects of the business process. On other hand, execution control studies consistent and efficient mechanisms for implementation. This work presents an algorithmic method which joins modeling and execution control through algebraic expression generation from acyclic digraphs. By hypothesis, we assume that business process models are defined by graph structures, and execution control mechanisms are based on interpretation of process algebra expressions. For algebraic expression generation, this thesis presents the topological properties of series-parallel digraphs and defines a transformation system based on digraph reduction. Therefore, we present an algorithm for identification of series-parallel digraphs and generation of algebraic expressions. This work also discusses the treatment of non-series-parallel digraphs and presents solutions based on topological changing for some cases. Finally, the algorithm is illustrated with a case study based on a real system.

Nesta tese é apresentado um novo workflow de simulação para avaliar o desempenho do balanceamento de carga dinâmico baseado em sobre-decomposição aplicado a aplicações paralelas iterativas. Seus objetivos são realizar essa avaliação com modificações mínimas da aplicação e a baixo custo em termos de tempo e de sua necessidade de recursos computacionais. Muitas aplicações paralelas sofrem com desbalanceamento de carga dinâmico (temporal) que não pode ser tratado a nível de aplicação. Este pode ser causado por características intrínsecas da aplicação ou por fatores externos de hardware ou software. Como demonstrado nesta tese, tal desbalanceamento é encontrado mesmo em aplicações cujo código não aparenta qualquer dinamismo. Portanto, faz-se necessário utilizar mecanismo de balanceamento de carga dinâmico a nível de runtime. Este trabalho foca no balanceamento de carga dinâmico baseado em sobre-decomposição. No entanto, avaliar e ajustar o desempenho de tal técnica pode ser custoso. Isso geralmente requer modificações na aplicação e uma grande quantidade de execuções para obter resultados estatisticamente significativos com diferentes combinações de parâmetros de balanceamento de carga Além disso, para que essas medidas sejam úteis, são usualmente necessárias grandes alocações de recursos em um sistema de produção. Simulated Adaptive MPI (SAMPI), nosso workflow de simulação, emprega uma combinação de emulação sequencial e replay de rastros para reduzir os custos dessa avaliação. Tanto emulação sequencial como replay de rastros requerem um único nó computacional. Além disso, o replay demora apenas uma pequena fração do tempo de uma execução paralela real da aplicação. Adicionalmente à simulação de balanceamento de carga, foram desenvolvidas técnicas de agregação espacial e rescaling a nível de aplicação, as quais aceleram o processo de emulação. Para demonstrar os potenciais benefícios do balanceamento de carga dinâmico com sobre-decomposição, foram avaliados os ganhos de desempenho empregando essa técnica a uma aplicação iterativa paralela da área de geofísica (Ondes3D). Adaptive MPI (AMPI) foi utilizado para prover o suporte a balanceamento de carga dinâmico, resultando em ganhos de desempenho de até 36.58% em 288 cores de um cluster Essa avaliação também é usada pra ilustrar as dificuldades encontradas nesse processo, assim justificando o uso de simulação para facilitá-la. Para implementar o workflow SAMPI, foi utilizada a interface SMPI do simulador SimGrid, tanto no modo de emulação, como no de replay de rastros. Para validar esse simulador, foram comparadas execuções simuladas (SAMPI) e reais (AMPI) da aplicação Ondes3D. As simulações apresentaram uma evolução do balanceamento de carga bastante similar às execuções reais. Adicionalmente, SAMPI estimou com sucesso a melhor heurística de balanceamento de carga para os cenários testados. Além dessa validação, nesta tese é demonstrado o uso de SAMPI para exploração de parâmetros de balanceamento de carga e para planejamento de capacidade computacional. Quanto ao desempenho da simulação, estimamos que o workflow completo é capaz de simular a execução do Ondes3D com 24 combinações de parâmetros de balanceamento de carga em 5 horas para o nosso cenário de terremoto mais pesado e 3 horas para o mais leve. / In this thesis we present a novel simulation workflow to evaluate the performance of dynamic load balancing with over-decomposition applied to iterative parallel applications at low-cost. Its goals are to perform such evaluation with minimal application modification and at a low cost in terms of time and of resource requirements. Many parallel applications suffer from dynamic (temporal) load imbalance that can not be treated at the application level. It may be caused by intrinsic characteristics of the application or by external software and hardware factors. As demonstrated in this thesis, such dynamic imbalance can be found even in applications whose codes do not hint at any dynamism. Therefore, we need to rely on runtime dynamic load balancing mechanisms, such as dynamic load balancing based on over-decomposition. The problem is that evaluating and tuning the performance of such technique can be costly. This usually entails modifications to the application and a large number of executions to get statistically sound performance measurements with different load balancing parameter combinations. Moreover, useful and accurate measurements often require big resource allocations on a production cluster. Our simulation workflow, dubbed Simulated Adaptive MPI (SAMPI), employs a combined sequential emulation and trace-replay simulation approach to reduce the cost of such an evaluation Both sequential emulation and trace-replay require a single computer node. Additionally, the trace-replay simulation lasts a small fraction of the real-life parallel execution time of the application. Besides the basic SAMPI simulation, we developed spatial aggregation and applicationlevel rescaling techniques to speed-up the emulation process. To demonstrate the real-life performance benefits of dynamic load balance with over-decomposition, we evaluated the performance gains obtained by employing this technique on a iterative parallel geophysics application, called Ondes3D. Dynamic load balancing support was provided by Adaptive MPI (AMPI). This resulted in up to 36.58% performance improvement, on 288 cores of a cluster. This real-life evaluation also illustrates the difficulties found in this process, thus justifying the use of simulation. To implement the SAMPI workflow, we relied on SimGrid’s Simulated MPI (SMPI) interface in both emulation and trace-replay modes.To validate our simulator, we compared simulated (SAMPI) and real-life (AMPI) executions of Ondes3D. The simulations presented a load balance evolution very similar to real-life and were also successful in choosing the best load balancing heuristic for each scenario. Besides the validation, we demonstrate the use of SAMPI for load balancing parameter exploration and for computational capacity planning. As for the performance of the simulation itself, we roughly estimate that our full workflow can simulate the execution of Ondes3D with 24 different load balancing parameter combinations in 5 hours for our heavier earthquake scenario and in 3 hours for the lighter one.