Neste trabalho apresentamos a metodologia de orientação ao objeto no desenvolvimentos de uma biblioteca de classes para facilitar o processo de programação numérica paralela. Na implementação dos métodos das classes utilizamos as rotinas do pacote ScaLAPACK, sendo que essas classes oferecem métodos para manipulações matriciais básicas e para a diagonalização de matrizes, onde essas matrizes podem ser reais e complexas, de simples e dupla precisão. Este trabalho apresenta detalhes de implementação e uma análise comparativa de desempenho, a fim de mostrarmos a eficiência e as facilidades de uso da orientação ao objeto no desenvolvimento de programas científicos paralelos. / In this work current vs. voltage (I vs. V) and alternating conductivity (ac) measurements were carried out in poly[(2-methoxy- 5-hexyloxy)-pphenylenevinilene] ? MEH-PPV light-emitting diodes having zinc oxide (ZnO) as transparent anode and Al as metallic cathode. MEH-PPV is a PPV derivative, which emits in the red spectral region; ZnO has a work function similar to that of ITO, but it is less aggressive to the polymer, less expensive and easily processed. The retificated I vs. V curves shows that the direct current depends on the temperature. Moreover, the real and imaginary components of alternating conductivity (ac) present typical behavior of somewhat disordered material: the imaginary component grows as a function of the frequency and the real component was observed to be frequency independent for lower frequencies, and follows a power-law above a certain frequency. The Random Energy Free Barrier model approaches and a resistance in series for the interface phenomenon were developed and adjusted for the ac results. From this experimental-theoretical fitting we obtained important parameters of the devices as well as, quantitative informations about the MEH-PPV transport phenomenon.

O método de Kaczmarz é um algoritmo iterativo que soluciona sistemas lineares do tipo Ax = b através de projeções sobre hiperplanos bastante usado em aplicações que envolvem a Tomografia Computadorizada. Recentemente voltou a ser destaque após a publicação de uma versão aleatória apresentada por Strohmer e Vershynin em 2009 a qual foi provada possuir taxa de convergência esperada exponencial. Posteriormente, Eldar e Needell em 2011 sugeriram uma versão modificada do algoritmo de Strohmer e Vershynin, na qual a cada iteração é selecionada a projeção ótima a partir de um conjunto aleatório, utilizando para isto o lema de Johnson-Lindenstrauss. Nenhum dos artigos mencionados apresenta uma técnica para a escolha do parâmetro de relaxação, entretanto, a seleção apropriada deste parâmetro pode ter uma influência substancial na velocidade do método. Neste trabalho apresentamos uma metodologia para a escolha do parâmetro de relaxação, bem como implementações paralelas do algoritmo de Kaczmarz utilizando as ideias de Eldar e Needell. Nossa metodologia para seleção do parâmetro utiliza uma nova generalização dos resultados de Strohmer e Vershynin que agora leva em consideração o parâmetro λ de relaxação e, a partir daí, obtemos uma estimativa da taxa de convergência como função de λ. Escolhemos então, para uso no algoritmo, aquele que otimiza esta estimativa. A paralelização dos métodos foi realizada através da plataforma CUDA e se mostrou muito promissora, pois conseguimos, através dela, um ganho significativo na velocidade de convergência / The Kaczmarz method is an iterative algorithm for finding the solution of a system of linear equations Ax = b by projecting onto the hyperplanes widely used in applications involving Computerized Tomography. It has been recently highlighted after the publication of a random version presented by Strohmer and Vershynin in 2009 that yields probably exponential convergence in expectation. Thereafter, Eldar and Needell in 2011 suggested a modified version of Strohmer and Vershynin algorithm, which at each iteration selects the optimal projection from a random set making use of the Johnson-Lindenstrauss lemma. None of the mentioned articles presents a technique for choosing the relaxation parameter, however, the proper selection of this parameter can achieve a substantial gain on the speed of the method. In this project we present a methodology for finding the relaxation parameter, as well as parallel implementations of Kacmarzs Algorithm using the ideas of Eldar and Needell. Our methodology for parameter selection uses a new generalization on Strohmer and Vershynins results which now regards the relaxation parameter λ. Thenceforward, we obtain an estimate of the convergence rate as a function of λ. Then we use this estimate in the algorithm the optimizer of this estimate. The parallelization of the methods has been implemented through the CUDA platform and appears to be very promising, since it delivers substantial gain in the convergence speed

Algoritmos de balanceamento de carga são utilizados em sistemas distribuídos para homogeneizar a ocupação dos recursos computacionais disponíveis. A homogeneidade na ocupação do ambiente permite otimizar a alocação de recursos e, conseqüentemente, aumentar o desempenho das aplicações. Com o advento dos sistemas distribuídos de alta escala, fazem-se necessárias pesquisas para a construção de algoritmos de balanceamento de carga que sejam capazes de gerir com eficiência esses sistemas. Essa eficiência é medida através do número de mensagens geradas no ambiente, do suporte a ambientes heterogêneos, do uso de políticas que consomem poucos recursos do sistema, da estabilidade em alta carga, da escalabilidade do sistema e dos baixos tempos de resposta. Com o objetivo de atender as necessidades dos sistemas distribuídos de alta escala, este doutorado propõe, apresenta e avalia um novo algoritmo de balanceamento de carga denominado TLBA (Tree Load Balancing Algorithm). Esse algoritmo organiza os computadores do sistema em uma topologia lógica na forma de árvore, sobre a qual são executadas operações de balanceamento de carga. Para validar o TLBA foi construído um simulador que, submetido a testes, permitiu comprovar suas contribuições, que incluem: o baixo número de mensagens geradas pelas operações de balanceamento de carga; a estabilidade em altas cargas; os baixos tempos médios de resposta de processos. Para validar os resultados de simulação, foi construído um protótipo do TLBA. Esse protótipo confirmou os resultados de simulação e, conseqüentemente, as contribuições do algoritmo. / Load balancing algorithms are applied in distributed systems to homogenize the occupation of the available computational resources. The homogeneity of the environment occupation allows optimising the resource allocation and consequently, increasing the application performance. With the advent of the large-scale distributed systems, it was necessary to start researching the construction of load balancing algorithms which are able to manage these systems with efficiency. This efficiency is measured through the number of messages generated on the environment; the support to heterogeneous environments and the load balance policies which should spend the minimal resources time; the stability in overloaded situations; the system scalability; and the processes average response times, that should be small. With the aim to achieve the large-scale distributed systems requirements, this Ph.D. proposes, presents and evaluates a new load balancing algorithm named TLBA (Tree Load Balancing Algorithm). This algorithm arranges the computers on a logical network topology with a tree format. The load balancing operations are executed over this tree. To evaluate the TLBA algorithm, a simulator was built that was submitted to tests that confirmed the following characteristics: the small number of messages generated by the load balancing operations; the stability in overloaded situations; the small average processes response times. To validate the simulation results a TLBA prototype was implemented. This prototype confirmed the simulation results and consequently the contributions of the proposed algorithm.

Diversas políticas de escalonamento para aplicações paralelas voltadas a ambientes computacionais distribuídos têm sido propostas. Embora tais políticas apresentem bons resultados, elas são, geralmente, avaliadas em cenários específicos. Quando o cenário muda, com diferentes ambientes distribuídos e condições de carga, essas políticas podem ter seu desempenho deteriorado. Nesse contexto, este trabalho apresenta um estudo comparativo envolvendo dez políticas de escalonamento avaliadas em diferentes cenários. Cada uma das políticas foi submetida a uma combinação de quatro cargas de trabalho de ocupação da UCP e três variações da taxa de comunicação média entre os processos, utilizando a rede. Foram considerados ainda três sistemas distribuídos distintos: dois clusters, com diferentes quantidades de nós, e um grid computacional. Foi utilizada a simulação com ambientes próximos ao real e cargas de trabalho obtidas de modelos realísticos. Os resultados demonstraram que, embora as políticas sejam voltadas a ambientes computacionais paralelos e distribuídos, quando o cenário muda, o desempenho cai e a ordem de classificação entre as políticas se altera. Os resultados permitiram ainda demonstrar a necessidade de se considerar a comunicação entre os processos durante o escalonamento em grids computacionais. / Several scheduling policies for parallel applications directed to the distributed computational environments have been proposed. Although such policies present good results, they, generally, are evaluated in specific scenarios. When scenario change, by using different distributed environments and workload conditions, these policies can have its performance spoiled. In this context, this work presents a comparative study involving ten scheduling policies evaluated on different scenarios. Each policy was submitted to a combination of four CPU occupation workloads and three variations of interprocess average communication rates, using the network. Three different distributed systems had been yet considered: two clusters, with different amounts of nodes, and one grid computing. Simulation was used with environments near to the real and workloads obtained of realistic models. Although the policies are directed to parallel and distributed environments, the results have demonstrated that when scenario change, the performance falls and the ranking between the policies changes too. The results have still allowed to demonstrate the necessity of considering interprocess communication during the scheduling in a grid computing.

A utilização majoritária da malha ferroviária brasileira para o transporte de cargas e a sua incompatibilidade para desenvolvimento de altas velocidades inviabiliza a oferta de serviços competitivos para o transporte intermunicipal de passageiros. A questão explorada nesta tese é sobre qual tecnologia ferroviária provê melhores resultados socioeconômicos no contexto de uma nova rede para o transporte intermunicipal de passageiros com operação exclusiva de Trens de Alto Desempenho (High Performance Trains - HPTs) ou Trens de Alta Velocidade (High Speed Trains - HSTs), caracterizados por velocidades médias de 150 km/h e 300 km/h respectivamente. Nesse sentido, a hipótese é que a diferença entre benefícios e custos socioeconômicos da oferta de serviços de HSTs resultam em valores positivos e maiores do que aquelas decorrentes da operação de HPTs, mediante parâmetros específicos de avaliação socioeconômica e uma configuração hipotética de rede na Região Sudeste do Brasil. Assim, o objetivo principal da tese é estimar e comparar os custos e benefícios socioeconômicos de uma rede ferroviária pela estimativa dos investimentos para a construção de novos traçados ferroviários, estimativa do número de viagens intermunicipais na Região Sudeste em um horizonte de planejamento estratégico e a propensão à escolha modal, estabelecimento de uma formulação de Análise Custo-Benefício (Cost Benefit Analysis - CBA) e aplicação dos modelos em cenários considerando a operação exclusiva de HPTs ou de HSTs. A resolução do problema de otimização de traçados ferroviários, com uma abordagem de computação paralela aplicada a um Algoritmo Genético, indica que os investimentos em infraestrutura variam majoritariamente em função da topografia, os custos de desapropriações são proporcionalmente pequenos e as restrições geométricas dos traçados não influenciam significativamente nesses resultados. Após a projeção do número de viagens intermunicipais por modelos analíticos, os dados coletados em uma pesquisa de preferência declarada são utilizados para modelagem da propensão à escolha modal. Finalmente, uma proposta de formulação para o cálculo dos principais itens de custos e benefícios de uma avaliação socioeconômica para o transporte ferroviário de passageiros viabiliza a análise de cenários em função de produtividade da construção da infraestrutura, variabilidade dos investimentos estimados e capacidade de atração de demanda reprimida. Os resultados dos cenários indicam que a diferença entre os benefícios estritamente econômicos (receita operacional e valor residual dos investimentos em infraestrutura) e os custos de construção e operacionais são negativos para qualquer tarifa ferroviária, apesar dos resultados para a rede de HSTs serem maiores do que para a de HPTs. Considerando os aspectos sociais, os benefícios totais da operação ferroviária sobrepõem-se aos seus custos em situações tarifárias específicas, novamente com resultados maiores para uma rede de HSTs, cuja tendência também é observada quando apenas os benefícios sociais são relacionados com custos totais através de uma Razão Benefício-Custo (Benefit-Cost Ratio - BCR). Portanto, segundo as premissas desta tese, há indícios que o investimento em uma infraestrutura ferroviária aparentemente não é uma decisão promissora em termos de viabilidade socioeconômica, apesar da operação de HSTs ser mais conveniente do que HPTs nas condições analisadas. / The major use of the Brazilian railway network for freight transport and its incompatibi-lity with high speed trains does not enable running competitive services of intercity passenger transport. The research question of this thesis is which rolling stock technology provides better socioeconomic results on a new intercity passenger network with exclusive operation of High Performance Trains (HPTs) or High Speed Trains (HSTs) with average speeds of 150 km/h and 300 km/h respectively. The hypothesis is that the difference between the socioeconomic benefits and costs of operating HSTs results in positive values and greater than those from the operation of HPTs given specific socioeconomic parameters and a hypothetical network in the Southeastern region of Brazil. The main goal of this research is to estimate and compare the major socioeconomic costs and benefits of a hypothetical railway network by first estimating the required investments of new alignments. Furthermore, the number of trips among cities in the Southeastern Region over a strategic planning horizon and the mode choice are estimated and a Cost-Benefit Analysis formulation is provided to be applied to scenarios of exclusive operation of HPTs or HSTs. The solution of the railway alignment optimization problem with a parallel computing approach applied to a Genetic Algorithm shows that the infrastructure investments vary mainly due to the topography, whereas the expropriation costs are proporti-onally small and the railway geometric constraints do not significantly affect the results. The number of trips by transport mode over a planning horizon is expanded analytically and the collected data of a stated preference survey is applied to a mode choice modeling approach. Finally, a formulation for the major items of costs and benefits of a socioeconomic assessment for a rail passenger transport project is proposed and it is applied to specific scenarios where the effects of the infrastructure building productivity, variability of the estimated investments, and the ability to attract new passengers are analyzed. The results from these scenarios show that the difference between the operating income and the net residual value of investments in infrastructure, construction and operating costs are negative for any rail fare, despite the results for the network of HSTs being higher than for HPTs. Furthermore, the overall benefits of the railway operation outweigh the costs in specific pricing policies with better results for a network operating HSTs. This trend is also noticed when only the social benefits are compared to the total costs by a Benefit-Cost Ratio (BCR). Therefore, there is evidence that the investment in railway infrastructure for passenger transport apparently is not a promising decision in terms of socioeconomic feasibility under the assumptions of this thesis, despite the operation of HSTs being more attractive than HPTs under the specified conditions.

Apesar do aumento constante da largura de banda das tecnologias de rede de computadores as aplicações de processamento paralelo ainda necessitam de uma latência de comunicação mais baixa que a oferecida. Este aspecto não tem sido contemplado por estas tecnologias de rede pois está relacionado à maneira como o sistema operacional utiliza-se dos recursos do hardware com relação aos dados enviados pelas aplicações dos usuários. Neste trabalho apresentamos um estudo da técnica para diminuição desta latência e as características necessárias para implementação deste tipo de sistemas, incluindo mecanismos de transferência de dados, técnicas para tradução de endereços, proteção, transferência de controle, grau de confiabilidade e implementação de \"Multicasting\". Apresentamos também o estudo de um sistema já implementado, chamado M-VIA, comparando seu desempenho com o TCP/IP tradicional. / Despite the constant bandwidth increase in computer networks parallel processing tasks still require a lower communication latency than offered. This necessity has not been addressed by these network technologies because it is related to how operating systems use hardware resources to send user data through network. In this work we present strategies to lower latency and the requirements to implement these systems, including data transfer mechanisms, address translation , security, control transfer, reliability and \"Multicasting\" deployment . We also present a ready to use system, M-VIA, comparing it to traditional TCP/IP performance.

Orientador: Cláudio Nogueira de Meneses / Dissertação (mestrado) - Universidade Federal do ABC. Programa de Pós-Graduação em Ciências da Computação, 2013

Made available in DSpace on 2014-06-12T17:36:05Z (GMT). No. of bitstreams: 2 arquivo2293_1.pdf: 5284544 bytes, checksum: 98b62391a7b9cf3c490a1dd02e905d21 (MD5) license.txt: 1748 bytes, checksum: 8a4605be74aa9ea9d79846c1fba20a33 (MD5) Previous issue date: 2008 / Agência Nacional do Petróleo, Gás Natural e Biocombustíveis / A busca por técnicas de alto desempenho por engenheiros e pesquisadores no campo da simulação numérica em reservatórios de petróleo é um caminho que vem sendo percorrido desde o início da década de 1950 com o advento dos primeiros computadores digitais. Prever o comportamento de um reservatório ao longo de sua vida produtiva e extrair a máxima quantidade de hidrocarbonetos economicamente viável é uma tarefa que exige um conhecimento mais detalhado das características dos fluidos (líquidos e/ou gasosos) e do meio poroso por onde escoam. A modelagem matemática da física envolvida no escoamento de fluidos em meios porosos resulta em equações diferenciais parciais (EDPs) nãolineares que apenas apresentam soluções analíticas em casos muito simplificados. Métodos numéricos como os de diferenças finitas e de volumes finitos, e mais recentemente de elementos finitos, têm sido aplicados neste campo e exigem um tratamento especial quando se deseja empregá-los em simulações com o auxílio de computadores paralelos partindo desde a fase de pré-processamento, passando pela estrutura de dados do simulador, até a resolução das equações discretas. O uso de computadores paralelos de memória distribuída é apresentado como uma ferramenta de alto desempenho que pode permitir uma redução significativa no tempo total de simulação ou pode viabilizar a simulação de problemas de grande porte, ou seja, problemas que excedem a capacidade de memória de uma única máquina devido a enorme quantidade de dados envolvidos. Neste trabalho, é apresentado um simulador de reservatórios de petróleo paralelo desenvolvido em C++ e que faz uso de pacotes gratuitos de código aberto voltados à programação paralela como FMDB, ParMetis e Petsc que desempenham tarefas específicas importantes como o gerenciamento de malhas distribuídas, o balanço de carga entre processadores e a utilização de resolvedores (solvers) iterativos paralelos, respectivamente. Uma formulação de volumes finitos centrada nos vértices e baseadas em uma estrutura de dados por arestas (Carvalho, 2005), aqui chamada de EBFV1 (Edge Based Finite Volume), é utilizada na discretização das equações governantes para simular o escoamento incompressível óleo-água em meios porosos heterogêneos e anisotrópicos tanto em malhas de triângulos quanto de tetraedros. Nesta formulação, a heterogeneidade do meio está associada a subdomínios. O método de integração no tempo IMPES (IMplicit Pressure Explicit Saturation) é adotado nas simulações em conjunto com um procedimento adaptativo no passo de tempo (Hurtado et al., 2006). Uma segunda formulação de volumes finitos (EBFV2) também com volumes de controle centrados nos vértices e onde a heterogeneidade do meio está associada aos elementos da malha é apresentada e comparada com a formulação EBFV1 para tratar problemas elípticos em malhas 2-D. Exemplos obtidos da literatura e tratados por outras formulações de volumes finitos são usados para avaliar o erro e a taxa de convergência para malhas com diferentes níveis de refinamento. Mostram-se como as duas formulações são capazes de lidar com problemas envolvendo meios porosos com razão de heterogeneidade e anisotropia elevada

Este trabalho apresenta uma ferramenta orientada ao objeto para o monitoramento de cargas em sistemas paralelos. O desenvolvimento desta ferramenta surgiu com o intuito de facilitar a programação paralela em sistemas distribuídos como NOWs, Networks of Workstations , e Grids computacionais, pois este tipo de programação é bem mais difícil do que a seqüencial e, por isso, desestimula novos programadores a desenvolver aplicações paralelas. Dentre as razões que tornam a programação paralela difícil destaca-se o balanceamento de cargas em que se quer maximizar a utilização dos recursos computacionais do sistema distribuído. Outro motivo para o programador de aplicações paralelas se preocupar com balanceamento de cargas é o desempenho, que é drasticamente afetado com o desequilíbrio de cargas do sistema. Com relação ao tempo em que as decisões de rebalanceamento de cargas são tomadas, os algoritmos de distribuição de cargas podem ser estáticos, realizados em tempo de compilação, ou dinâmicos, efetuados em tempo de execução. Embora o algoritmo estático não gere sobrecarga em tempo de execução na distribuição de carga, o dinâmico é a melhor escolha, pois se adapta bem em qualquer situação. Assim, o sistema de monitoramento de cargas surge como uma ferramenta de auxílio ao programador que deseje implementar algoritmos de balanceamento dinâmico de cargas nas suas aplicações paralelas, provendo informações de como os recursos computacionais do sistema distribuído estão sendo utilizados. / This work presents an object oriented tool for load monitoring in parallel systems. This tool was developed with intention to easy the parallel programming in distributed systems like NOWs (Networks of Workstations) and Computational Grids, because this type of programming is more difficult than the sequential and, therefore, it does not stimulate new programmers to develop parallel softwares. One of the most important reasons why parallel programming is difficult is the worry about load balancing where the purpose is to maximize the use of the computational resources of the distributed system. Another reason for the programmer of parallel softwares to worry about load balancing is the performance, which is drastically affected with the load imbalance of the system. With respect to the time where the decisions of load balancing are made, the load distribution algorithms can be static, done at compilation time, or dynamic, done at execution time. Although the static algorithm does not generate overhead at execution time, the dynamic one is a better choice, because it adapts well to any situation. Thus, the monitoring system appears as a tool to aid the programmer who desires to implement dynamic load balancing algorithms in his or her parallel softwares, providing information on how the computational resources of the distributed system are being used.

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