As a consequence of the CPU and GPU's architectures advance, in the last years there was a raise of the number of parallel programming APIs for both devices. While OpenMP is used to make parallel programs for the CPU, CUDA and OpenACC are employed in the parallel processing in the GPU. In the programming for the GPU, CUDA presents a model based on functions that make the source code extensive and prone to errors, in addition to leading to low development productivity. OpenACC emerged aiming to solve these problems and to be an alternative to the utilization of CUDA. Similar to OpenMP, this API has policies that ease the development of parallel applications that run on the GPU only. To further increase performance and take advantage of the parallel aspects of both CPU and GPU, it is possible to develop hybrid algorithms that split the processing on the two devices. In that sense, the main objective of this work is to verify if the advantages that OpenACC introduces are also positively reflected on the hybrid programming using OpenMP, if compared to the OpenMP + CUDA model. A second objective of this work is to identify aspects of the two programming models that could limit the performance or on the applications' development. As a way to accomplish these goals, this work presents the development of three hybrid parallel algorithms that are based on the Rodinia's benchmark algorithms, namely, RNG, Hotspot and SRAD, using the hybrid models OpenMP + CUDA and OpenMP + OpenACC. In these algorithms, the CPU part of the code is programmed using OpenMP, while it's assigned for the CUDA and OpenACC the parallel processing on the GPU. After the execution of the hybrid algorithms, the performance, efficiency and the processing's splitting in each one of the devices were analyzed. It was verified, through the hybrid algorithms' runs, that, in the two proposed programming models it was possible to outperform the performance of a parallel application that runs on a single API and in only one of the devices. In addition to that, in the hybrid algorithms RNG and Hotspot, CUDA's performance was superior to that of OpenACC, while in the SRAD algorithm OpenACC was faster than CUDA. / Como consequência do avanço das arquiteturas de CPU e GPU, nos últimos anos houve um aumento no número de APIs de programação paralela para os dois dispositivos. Enquanto que OpenMP é utilizada no processamento paralelo em CPU, CUDA e OpenACC são empregadas no processamento paralelo em GPU. Na programação para GPU, CUDA apresenta um modelo baseado em funções que deixam o código fonte extenso e propenso a erros, além de acarretar uma baixa produtividade no desenvolvimento. Objetivando solucionar esses problemas e sendo uma alternativa à utilização de CUDA surgiu o OpenACC. Semelhante ao OpenMP, essa API disponibiliza diretivas que facilitam o desenvolvimento de aplicações paralelas, porém para execução em GPU. Para aumentar ainda mais o desempenho e tirar proveito da capacidade de paralelismo de CPU e GPU, é possível desenvolver algoritmos híbridos que dividam o processamento nos dois dispositivos. Nesse sentido, este trabalho objetiva verificar se as facilidades que o OpenACC introduz também refletem positivamente na programação híbrida com OpenMP, se comparado ao modelo OpenMP + CUDA. Além disso, o trabalho visa relatar as limitações nos dois modelos de programação híbrida que possam influenciar no desempenho ou no desenvolvimento de aplicações. Como forma de cumprir essas metas, este trabalho apresenta o desenvolvimento de três algoritmos paralelos híbridos baseados nos algoritmos do benchmark Rodinia, a saber, RNG, Hotspot e SRAD, utilizando os modelos híbridos OpenMP + CUDA e OpenMP + OpenACC. Nesses algoritmos é atribuída ao OpenMP a execução paralela em CPU, enquanto que CUDA e OpenACC são responsáveis pelo processamento paralelo em GPU. Após as execuções dos algoritmos híbridos foram analisados o desempenho, a eficiência e a divisão da execução em cada um dos dispositivos. Verificou-se através das execuções dos algoritmos híbridos que nos dois modelos de programação propostos foi possível superar o desempenho de uma aplicação paralela em uma única API, com execução em apenas um dos dispositivos. Além disso, nos algoritmos híbridos RNG e Hotspot o desempenho de CUDA foi superior ao desempenho de OpenACC, enquanto que no algoritmo SRAD a API OpenACC apresentou uma execução mais rápida, se comparada à API CUDA.

[pt] Nos últimos anos, as linguagens de script ganharam muita importância em diversas áreas da computação. Uma das áreas onde essas linguagens ainda são pouco exploradas é na área de computação paralela. A computação paralela sempre foi fortemente associada a computação científica, mas recentemente ela ganhou uma nova importância com a popularização de processadores multi-core. Com esse crescimento se torna necessário o surgimento de novos paradigmas de programação paralela para facilitar o desenvolvimento e dinamizar as aplicações, e linguagens de script podem ser usadas para isso, trazendo dinamismo, simplicidade e flexibilidade às aplicações. Esta dissertação visa estudar um modelo híbrido de programação entre duas linguagens de programação, Lua e Charm plus plus. / [en] Recently, scripting languages have become very important in many fields of computer science. One area in which these languages have not been explored is paralel programming. Paralel programming has always been strongly associated with scientific usage, but recently, with the growth in popularity of multi core systems, it has gained a new field of action. With this change, the development of new programming paradigms of paralel programming become necessary in order to make development easier and applications more dynamic. Scripting languages may be used for this, bringing dynamics, flexibility and simplicity to aplications. This dissertation aims to study a hybrid programming model with two programming languages, Charm plus plus and Lua.

La Radio Logicielle (SDR) est une radio dont les transformations de la forme d’onde, modulation, démodulation des signaux d’un système radio sont mises en œuvre par du logiciel plutôt que par du matériel à fonctionnalité spécifique. Avec cette approche, l’adaptation du système à une autre norme de communication, ou même l’évolution vers une technologie plus récente peuvent être réalisés par mise à jour du logiciel sans remplacement du matériel qui serait long et coûteux. L’architecture de communication logicielle (Software Communication Architecture, SCA), est une architecture ouverte largement acceptée pour les projets de SDR. La spécification SCA minimise le coût de portage des applications en fournissant une couche d’abstraction qui rend transparentes les méthodes spécifiques de chaque système. Dans cette thèse, on s’intéresse au développement et à la programmation d’une plateforme SDR conforme à SCA.Les nouvelles plateformes de SDR sont en général implémentées sur des plateformes multiprocesseurs système sur puce (MPSoC) exploitant ses importantes ressources de calculs avec une bonne efficacité énergique. Les possibilités d’un rapide développement, déploiement et vérification des logiciels embarqués parallèles sur ces nouvelles plateformes MPSoC sont autant de points clés pour satisfaire les objectifs de performance tout en respectant les délais de mise à disposition sur le marché et le coût de développement.On a proposé un flot de conception pour la SDR avec l’exploration architecturale systématique et l’optimisation multi-objective utilisant le modèle de programmation hybride (distribué client/serveur + parallèle).On a étudié aussi la synthèse de topologie de réseau-sur-puce (PSTRP) qui est une partie du flot de conception. Le problème de la synthèse de la topologie du réseau-sur-puce peut se modéliser sous forme de programme linéaire en nombres entiers. Les résultats montrent que les contraintes d’implémentation, comme la hiérarchie du réseau sur puce, doivent être prises en compte pour obtenir un résultat à la fois mathématiquement optimisé et électroniquement réalisable. / The Software Defined Radio (SDR) is a reconfigurable radio whose functionality is controlled by software, which greatly enhances the reusability and flexibility of waveform applications. The system update is also made easily achievable through software update instead of hardware replacement. The Software Communication Architecture (SCA), on the other hand, is an open architecture framework which specifies an Operating Environment (OE) in which waveform applications are executed. A SCA compliant SDR greatly improves the portability, reusability and interoperability of waveforms applications between different SDR implementations.The multiprocessor system on chip (MPSoC) consisting of large, heterogeneous sets of embedded processors, reconfiguration hardware and network-on-chip (NoC) interconnection is emerging as a potential solution for the continued increase in the data processing bandwidth, as well as expenses for the manufacturing and design of nanoscale system-on-chip (SoC) in the face of continued time-to-market pressures.We studied the challenges of efficiently deploying a SCA compliant platform on an MPSoC. We conclude that for realizing efficiently an SDR system with high data bandwidth requirement, a design flow with systematic design space exploration and optimization, and an efficient programming model are necessary. We propose a hybrid programming model combining distributed client/server model and parallel shared memory model. A design flow is proposed which also integrates a NoC topology synthesis engine for applications that are to be accelerated with parallel programming and multiple processing elements (PEs). We prototyped an integrated SW/HW development environment in which a CORBA based integrated distributed system is developed which depends on the network-on-chip for protocol/packet routing, and software components are deployed with unified interface despite the underlying heterogeneous architecture and os; while the hardware components (processors, IPs, etc) are integrated through interface conforming to the Open Core Protocol (OCP).

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.

Orientador: Guido Costa Souza de Araújo / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-22T08:27:32Z (GMT). No. of bitstreams: 1 Nicacio_DanielHenricusdeKnegtDutra_D.pdf: 2579331 bytes, checksum: b8e15a6f91203b98455f39d63d63a634 (MD5) Previous issue date: 2012 / Resumo: Sistemas de Memória Transacional em Software (MTS) têm sido usados como uma abordagem para melhorar o desempenho ao permitir a execução concorrente de blocos atômicos. Porém, em cenários com alta contenção, sistemas baseados em MTS podem diminuir o desempenho consideravelmente, já que a taxa de conflitos aumenta. Políticas de gerenciamento de contenção têm sido usadas como uma forma de selecionar qual transação abortar quando um conflito ocorre. No geral, gerenciadores de contenção não são capazes de evitar conflitos, tendo em vista que eles apenas selecionam qual transação abortar e o momento em que ela deve reiniciar. Como gerenciadores de contenção agem somente após a detecção de um conflito, é difícil aumentar a taxa de transações finalizadas com sucesso. Abordagens mais pró-ativas foram propostas, focando na previsão de quando uma transação deve abortar e atrasando o início de sua execução. Contudo, as técnicas pró-ativas continuam sendo limitadas, já que elas não substituem a transação fadada a abortar por outra transação com melhores probabilidades de sucesso, ou quando o fazem, dependem do sistema operacional para essa tarefa, tendo pouco ou nenhum controle de qual transação será a substituta. Esta tese apresenta o LUTS, Lightweight User-Level Transaction Scheduler, um escalonador de transação de baixo custo em nível de usuário. Diferente de outras técnicas, LUTS provê maneiras de selecionar outra transação a ser executada em paralelo, melhorando o desempenho do sistema. Nós discutimos o projeto do LUTS e propomos uma heurística dinâmica, com o objetivo de evitar conflitos, que foi construída utilizando os métodos disponibilizados pelo LUTS. Resultados experimentais, conduzidos com os conjuntos de aplicações STAMP e STMBench7, e executando nas bibliotecas TinySTM e SwissTM, mostram como nossa heurística para evitar conflitos pode melhorar efetivamente o desempenho de sistema de MTS em aplicações com alta contenção / Abstract: Software Transaction Memory (STM) systems have been used as an approach to improve performance, by allowing the concurrent execution of atomic blocks. However, under high-contention workloads, STM-based systems can considerably degrade performance, as transaction conflict rate increases. Contention management policies have been used as a way to select which transaction to abort when a conflict occurs. In general, contention managers are not capable of avoiding conflicts, as they can only select which transaction to abort and the moment it should restart. Since contention manager's act only after a conflict is detected, it becomes harder to effectively increase transaction throughput. More proactive approaches have emerged, aiming at predicting when a transaction is likely to abort, postponing its execution. Nevertheless, most of the proposed proactive techniques are limited, as they do not replace the doomed transaction by another or, when they do, they rely on the operating system for that, having little or no control on which transaction to run. This article proposes LUTS, a Lightweight User-Level Transaction Scheduler. Unlike other techniques, LUTS provides the means for selecting another transaction to run in parallel, thus improving system throughput. We discuss LUTS design and propose a dynamic conflict-avoidance heuristic built around its scheduling capabilities. Experimental results, conducted with the STAMP and STMBench7 benchmark suites, running on TinySTM and SwissTM, show how our conflict-avoidance heuristic can effectively improve STM performance on high contention applications / Doutorado / Ciência da Computação / Doutor em Ciência da Computação

Orientador: Luiz Otávio Saraiva Ferreira / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Mecânica / Made available in DSpace on 2018-08-27T02:13:59Z (GMT). No. of bitstreams: 1 Oliveira_FabiolaMartinsCamposde_M.pdf: 13513306 bytes, checksum: fd54d4a28df68e3217dbd8316b6aeadd (MD5) Previous issue date: 2015 / Resumo: Recentes avanços na tecnologia de processadores multinúcleos e vários-núcleos popularizaram a computação paralela, acelerando a execução de programas e possibilitando a simulação de domínios maiores. Dentre os problemas complexos que requerem alta velocidade de processamento, os problemas de fluidodinâmica computacional se destacam, já que suas simulações tendem a ter um alto custo computacional e exigem grandes domínios de simulação. O método baseado nas Redes de Boltzmann é um método de fluidodinâmica computacional apropriado para o uso de paralelismo que vem ganhando destaque na comunidade científica. Embora haja trabalhos que explorem o paralelismo em GPU nesse método, um simulador eficiente na execução e visualização interativa ainda não foi explorado adequadamente. Assim, a proposta deste trabalho é implementar em GPU um simulador interativo de fluidodinâmica com o método das Redes de Boltzmann. Inicialmente, o simulador foi desenvolvido em linguagem C e foi paralelizado em CPU usando MPI. Em seguida, foi paralelizado em GPU usando CUDA e convertido para linguagem orientada a objetos em C++. Depois, a visualização interativa foi acrescentada utilizando técnicas como interoperabilidade entre CUDA e OpenGL, texturização 3D, fluxo programável da GPU, além de funções de interação com o usuário. O simulador foi validado para casos 2D e 3D em fluxos monocomponentes monofásicos. Além disso, para demonstrar o ganho de desempenho em velocidade de processamento de problemas paralelizados em relação a execuções sequenciais, um conjunto de testes com tamanhos crescentes de domínio foi desenvolvido. O resultado dessa comparação indicou que o simulador implementado em GPU com visualização interativa teve desempenho 71.3 vezes maior em relação à versão sequencial em CPU sem visualização interativa. Dessa forma, a abordagem de paralelização em GPU com visualização interativa mostrou-se muito adequada à execução de simulações fluidodinâmicas, sendo uma ferramenta útil no estudo de escoamentos fluídicos, capaz de executar inúmeros cálculos e lidar com a grande quantidade de memória exigida por simulações fluídicas / Abstract: Recent advances on multicore and many-core processor technology have popularized the parallel computing, accelerating program execution and enabling the simulation of larger domains. Within the complex problems that require a high processing speed, the computational fluid dynamics problems stand out, since their simulations tend to have high computational cost and demand large simulation domains. The method based on the Lattice Boltzmann is an appropriate computational fluid dynamics algorithm to explore parallelism that has been noteworthy in scientific community. Although there are several works that approach GPU parallelism in this method, an efficient simulator implementation and interactive visualization have not been explored adequately. Thus, the purpose of this work is to implement in GPU an interactive fluid dynamics simulator based on the Lattice Boltzmann method. First, the simulator was developed in C language and was parallelized in CPU using MPI. Next, it was parallelized in GPU using CUDA and converted into C++ object-oriented language. Then, the interactive visualization was added using techniques such as CUDA-OpenGL interoperability, 3D texturing, GPU programmable pipeline, and interaction features. The simulator was validated for 2D and 3D cases in single component, single phase flows. Besides that, to show the performance gain in processing velocity of parallelized problems in relation to sequential executions, a test set with increasing domain sizes was developed. This comparison result indicated the GPU-implemented interactive simulator was 71.3 times faster in relation to sequential CPU version without interactive visualization. Thereby, the GPU parallelization approach with interactive visualization showed to be very adequate to fluid dynamics simulations, being a useful tool in fluid flow study, capable of simulating numerous calculations and dealing with the large amount of memory required in fluidic simulations / Mestrado / Mecanica dos Sólidos e Projeto Mecanico / Mestra em Engenharia Mecânica

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

The project, Spider III, presents architecture and protocol of a multi-agent-based internet distributed computing system, which provides a convenient development and execution environment for transparent task distribution, load balancing, and fault tolerance. Spider is an on going distribution computing project in the Department of Computer Science, California State University San Bernardino. It was first proposed as an object-oriented distributed system by Han-Sheng Yuh in his master's thesis in 1997. It has been further developed by Koping Wang in his master's project, of where he made large contribution and implemented the Spider II System.

This thesis presents the developed taxonomy of the agent-based distributed computing systems. Based on this taxonomy, a design, implementation, analysis and distribution protocol of a multi-agent architecture for internet-based distributed computing system was developed. A prototype of the designed architecture was implemented on Spider III using the IBM Aglets software development kit (ASDK 2.0) and the language Java.

O principal objetivo deste estudo é propor uma nova metodologia para lidar com o problema de Planejamento da Expansão de Redes de Transmissão de Energia Elétrica com Múltiplos Cenários de Geração (PERTEEG). Com a metodologia proposta neste trabalho almeja-se construir planos de expansão de redes de transmissão de energia elétrica que sejam capazes de, no menor custo de investimento possível, satisfazer às novas exigências dos sistemas elétricos modernos, tais como construção de redes de transmissão livres de congestionamento e robustas à incerteza em relação aos cenários de geração futuros. Através de estudos realizados na literatura do problema, verificou-se que novos modelos e metodologias de abordagem do PERTEEG se fazem necessários. Ao se modelar o PERTEEG visando construir redes de transmissão que contornem as incertezas em relação aos cenários de geração futuros e concomitantemente minimizar o custo de investimento para a expansão do sistema, o planejador se depara com um problema de otimização multiobjetivo. Existem na literatura da pesquisa operacional diversos algoritmos que visam lidar com problemas multiobjetivos. Nesta tese, foram aplicados dois desses algoritmos: Nondominated Sorting Genetic Algorithms-II (NSGA-II) e SPEA2: Strength Pareto Evolutionary Algorithm (SPEA2). Em primeira análise, se destacou uma das maiores dificuldade de lidar com o PERTEEG, a saber, o esforço computacional elevado. Por isso, vislumbrou-se que uma possível solução para contornar esta dificuldade esteja na computação paralela. Para se confirmar esta suspeita, nesta tese foram implementadas versões paralelas dos algoritmos sequenciais testados. A qualidade das soluções encontradas pelos algoritmos foram bastante superiores às soluções encontradas pelos algoritmos sequenciais. Neste trabalho também será mostrado que as soluções ótimas clássicas considerando somente o objetivo de m´mínimo custo são incapazes de atender às novas necessidades dos sistemas elétricos de potência. Testes computacionais foram realizados e analisados neste trabalho. Considerando as metodologias conhecidas na literatura para medição da qualidade das soluções encontradas por algoritmos multiobjetivo, se pode afirmar de que a proposta de abordagem do problema de PERTEEG pode ser viável tanto do ponto de vista de engenharia como do ponto de vista da computação matemática. / The main objective of this study is to propose a new methodology to deal with the long-term transmission system expansion planning with multiple generation dispatch scenarios problem (TEP-MDG). With the methodology proposed in this thesis we aim to build expansion plans with minimum investment cost and also capable of meeting the new demands of modern electrical systems, such as uncertainty about the future generation scenarios and congestion in the transmission systems. By modeling the TEP-MDG aiming to build transmission networks that circumvent the uncertainties regarding the future generation scenarios and simultaneously minimize the cost of investment for transmission networks expansion, the planner faces a multiobjective optimization problem. One can find various algorithms that aim to deal with multiobjective problems in the literature of operations research. In this thesis, we apply two of these algorithms: Nondominated Sorting Genetic Algorithms-II (NSGA-II) and SPEA2: Strength Pareto Evolutionary Algorithm (SPEA2). In a first analysis, we have found that the most critical issue with the TEP-MOG is the high computational demand. Therefore, in order to circumvent this difficulty we have implemented parallel versions of the sequential algorithms tested. In performed tests, the parallel algorithms have found solutions of superior quality than the solutions found by the sequential algorithms. In this thesis we also show that optimal solutions considering only the classical least cost objective are unable to meet the electric power systems new demands. Tests have been performed and analyzed in this work. By considering the methods known in the literature convinced to measure the quality of solutions found by multiobjective algorithms, we concluded that the proposed approach to TEP-MDG may be feasible from the point of view of both engineering and computational mathematics.