A presente tese trata o problema do reescalonamento de processos durante a execução da aplicação, oferecendo rebalanceamento dinâmico de carga entre os recursos disponíveis. Uma vez que os cenários da computação distribuída envolvem cada vez mais recursos e aplicações dinâmicas, a carga é uma medida variável e um mapeamento inicial processos-recursos pode não permanecer eficiente no decorrer do tempo. O estado dos recursos e da rede podem variar no decorrer da aplicação, bem como a quantidade de processamento e a interação entre os processos. Consequentemente, o remapeamento de processos para novos recursos é pertinente para aumentar o uso dos recursos e minimizar o tempo de execução da aplicação. Nesse contexto, essa tese de doutorado apresenta um modelo de reescalonamento chamado MigBSP, o qual controla a migração de processos de aplicações BSP (Bulk Synchronous Parallel). O modelo de aplicação BSP foi adotado visto que torna a programação paralela mais fácil e é muito comum nos cenários de desenvolvimento de aplicações científicas. Considerando o escopo de aplicações BSP, as novas idéias de MigBSP são em número de três: (i) combinação de três métricas - Memória, Computação e Comunicação - em uma outra escala com o intuito de medir o Potencial de Migração de cada processo BSP; (ii) emprego de um Padrão de Computação e outro Padrão de Comunicação para controlar a regularidade dos processos e; (iii) adatação eficiente na freqüência do lançamento do reescalonamento de processos. A infra-estrutura de máquina paralela considera sistemas distribuídos heterogêneos (diferentes velocidades de processador e de rede). Os processos podem passar mensagens entre si e a máquina paralela pode agregar redes locais e clusters. O modelo de reescalonamento provê um formalismo matemático para decidir as seguintes questões: (i) Quando lançar o reescalonamento dos processos; (ii) Quais processos são candidatos a migração e; (iii) Para onde os processos selecionados serão migrados. A técnica de simulação foi usada para validar MigBSP. Além do próprio MigBSP, três aplicações científicas foram foram desenvolvidas e executadas usando o simulador Simgrid. Os resultados mostraram que MigBSP oferece oportunidade de ganhar desempenho sem alterações no código fonte da aplicação. MigBSP torna possível ganhos de desempenho na casa de 20%, bem como produz uma baixa sobrecarga quando migrações são inviáveis. Sua sobrecarga média ficou abaixo de 8% do tempo de execução normal da aplicação. Essa taxa foi obtida desabilitando quaisquer migrações indicadas por MigBSP. Os resultados mostraram que a união das métricas consideradas é uma boa solução para o controle de migração de processos. Além disso, eles revelaram que as adaptações desenvolvidas na freqüência do reescalonamento são cruciais para tornar a execução de MigBSP viável, principalmente em ambientes desbalanceados. / This thesis treats the processes rescheduling problem during application runtime, offering dynamic load rebalancing among the available resources. Since most distributed computing scenarios involve more and more resources and dynamic applications, the load is a variable measure and an initial processes-processors deployment may not remain efficient with time. The resources and the network states can vary during application execution, as well as the amount of processing and the interactions among the processes. Consequently, the remapping of processes to new processors is pertinent to improve resource utilization and to minimize application execution time. In this context, this thesis presents a rescheduling model called MigBSP, which controls the processes migration of BSP (Bulk Synchronous Parallel) applications. BSP application model was adopted because it turns parallel programming easier and is very common in scientific applications development scenarios. Considering the scope of BSP applications, the novel ideas of MigBSP are threefold: (i) combination of three metrics - Memory, Computation and Communication - in a scalar one in order to measure the potential of migration of each BSP process; (ii) employment of both Computation and Communication Patterns to control processes’ regularity and; (iii) efficient adaptation regarding the periodicity to launch processes rescheduling. In our infrastructure, we are considering heterogeneous (different processor and network speed) distributed systems. The processes can pass messages among themselves and the parallel machine can gather local area networks and clusters. The proposed model provides a mathematical formalism to decide the following questions about load (BSP processes) balancing: (i) When to launch the processes rescheduling; (ii) Which processes will be candidates for migration and; (iii) Where to put the processes that will be migrated actually. We used the simulation technique to validate MigBSP. Besides MigBSP, three scientific application were developed and executed using Simgrid simulator. In general, the results showed that MigBSP offers an opportunity to get performance in an effortless manner to the programmer since its does not need modification on application code. MigBSP makes possible gains of performance up to 20% as well as produces a low overhead when migrations do not take place. Its mean overhead is lower than 8% of the normal application execution time. This rate was obtained disabling any processes migration indicated by MigBSP. The results show that the union of considered metrics is a good solution to control processes migration. Moreover, they revealed that the developed adaptations are crucial to turn MigBSP execution viable, mainly on unbalanced environments.

PINHO, Eduardo Gurgel. Uma Linguagem de Programação Paralela Orientada a Objetos para Arquiteturas Distribuídas. 2012. 71 f. : Dissertação (mestrado) - Universidade Federal do Ceará, Centro de Ciências, Departamento de Computação, Fortaleza-CE, 2012. / Submitted by guaracy araujo (guaraa3355@gmail.com) on 2016-06-21T19:17:42Z No. of bitstreams: 1 2012_dis_egpinho.pdf: 1247267 bytes, checksum: b2db45af231441771b82531797f8c819 (MD5) / Approved for entry into archive by guaracy araujo (guaraa3355@gmail.com) on 2016-06-21T19:19:30Z (GMT) No. of bitstreams: 1 2012_dis_egpinho.pdf: 1247267 bytes, checksum: b2db45af231441771b82531797f8c819 (MD5) / Made available in DSpace on 2016-06-21T19:19:30Z (GMT). No. of bitstreams: 1 2012_dis_egpinho.pdf: 1247267 bytes, checksum: b2db45af231441771b82531797f8c819 (MD5) Previous issue date: 2012 / In object-oriented programming (OOP) languages, the ability to encapsulate software concerns of the dominant decomposition in objects is the key to reaching high modularity and loss of complexity in large scale designs. However, distributed-memory parallelism tends to break modularity, encapsulation, and functional independence of objects, since parallel computations cannot be encapsulated in individual objects, which reside in a single address space. For reconciling object-orientation and distributed-memory parallelism, this work introduces OOPP (Object-Oriented Parallel Programming), a style of OOP where objects are distributed by default. As an extension of C++, a widespread language in HPC, the PObC++ language has been designed and protoyped, incorporating the ideas of OOPP / Em programação orientadas a objetos (POO) , a habilidade de encapsular interesses de software da dominante decomposição em objetos é a chave para alcançar alto nível de modularidade e diminuição de complexidade em projetos de larga escala. Entretanto, o paralelismo de memória distribuída tende a quebrar modularidade, encapsulamento e a independência de objetos, uma vez que as computações paralelas não podem ser encapsuladas em objetos individuais, os quais residem em um espaço de endereçamento único. Para reconciliar orientação a objetos e paralelismo em memória distribuída, esse trabalho introduz a PPOO (Programação Paralela Orientada a Objetos), um estilo de POO onde objetos são distribuídos por padrão. Como uma estensão do C++, uma linguagem consolidada em CAD, a linguagem PObC++ foi projetada e prototipada, incorporando as ideias da PPOO.

Orientador: Prof. Dr. Márcio Katsumi Oikawa / Dissertação (mestrado) - Universidade Federal do ABC, Programa de Pós-Graduação em Ciência da Computação, 2015. / Este trabalho utiliza conceitos de Séries Históricas e Método dos Mínimos Quadrados para realização de estudo evolutivo da Doença de Alzheimer. Com estas técnicas, foram elaboradas a apresentação do panorama atual de um grupo de pacientes e, posteriormente, a previsão de resultados a partir de dados históricos obtidos do exame neuropsicológico denonimado Mini Exame do Estado Mental. Foram geradas trajetórias representadas pela unidade tempo (em anos) de cada um dos pacientes contidos na base de dados. Os resultados sugerem que a modelagem por meio de Séries Históricas e Método dos Mínimos Quadrados pode ser considerada adequada para o acompanhamento e previsão da progressão/estagnação da Doença de Alzheimer. / This study attempted of the concepts of Time Series and the Least Squares Method for accomplishment of evolutive study of Alzheimer¿s disease. With these techniques were development the presentation of the current situation of a group of patients and subsequently the prediction from historical data results of neuropsychological test called Mini Mental State Examination. For each of the patients in the database, it was generated trajectories represented by unit time (in years). The findings suggests that the modeling using Time Series associated with the Least Squares Method can be considered suitable for monitoring and prediction of the progression/stagnation of the Alzheimer¿s disease.

A presente tese trata o problema do reescalonamento de processos durante a execução da aplicação, oferecendo rebalanceamento dinâmico de carga entre os recursos disponíveis. Uma vez que os cenários da computação distribuída envolvem cada vez mais recursos e aplicações dinâmicas, a carga é uma medida variável e um mapeamento inicial processos-recursos pode não permanecer eficiente no decorrer do tempo. O estado dos recursos e da rede podem variar no decorrer da aplicação, bem como a quantidade de processamento e a interação entre os processos. Consequentemente, o remapeamento de processos para novos recursos é pertinente para aumentar o uso dos recursos e minimizar o tempo de execução da aplicação. Nesse contexto, essa tese de doutorado apresenta um modelo de reescalonamento chamado MigBSP, o qual controla a migração de processos de aplicações BSP (Bulk Synchronous Parallel). O modelo de aplicação BSP foi adotado visto que torna a programação paralela mais fácil e é muito comum nos cenários de desenvolvimento de aplicações científicas. Considerando o escopo de aplicações BSP, as novas idéias de MigBSP são em número de três: (i) combinação de três métricas - Memória, Computação e Comunicação - em uma outra escala com o intuito de medir o Potencial de Migração de cada processo BSP; (ii) emprego de um Padrão de Computação e outro Padrão de Comunicação para controlar a regularidade dos processos e; (iii) adatação eficiente na freqüência do lançamento do reescalonamento de processos. A infra-estrutura de máquina paralela considera sistemas distribuídos heterogêneos (diferentes velocidades de processador e de rede). Os processos podem passar mensagens entre si e a máquina paralela pode agregar redes locais e clusters. O modelo de reescalonamento provê um formalismo matemático para decidir as seguintes questões: (i) Quando lançar o reescalonamento dos processos; (ii) Quais processos são candidatos a migração e; (iii) Para onde os processos selecionados serão migrados. A técnica de simulação foi usada para validar MigBSP. Além do próprio MigBSP, três aplicações científicas foram foram desenvolvidas e executadas usando o simulador Simgrid. Os resultados mostraram que MigBSP oferece oportunidade de ganhar desempenho sem alterações no código fonte da aplicação. MigBSP torna possível ganhos de desempenho na casa de 20%, bem como produz uma baixa sobrecarga quando migrações são inviáveis. Sua sobrecarga média ficou abaixo de 8% do tempo de execução normal da aplicação. Essa taxa foi obtida desabilitando quaisquer migrações indicadas por MigBSP. Os resultados mostraram que a união das métricas consideradas é uma boa solução para o controle de migração de processos. Além disso, eles revelaram que as adaptações desenvolvidas na freqüência do reescalonamento são cruciais para tornar a execução de MigBSP viável, principalmente em ambientes desbalanceados. / This thesis treats the processes rescheduling problem during application runtime, offering dynamic load rebalancing among the available resources. Since most distributed computing scenarios involve more and more resources and dynamic applications, the load is a variable measure and an initial processes-processors deployment may not remain efficient with time. The resources and the network states can vary during application execution, as well as the amount of processing and the interactions among the processes. Consequently, the remapping of processes to new processors is pertinent to improve resource utilization and to minimize application execution time. In this context, this thesis presents a rescheduling model called MigBSP, which controls the processes migration of BSP (Bulk Synchronous Parallel) applications. BSP application model was adopted because it turns parallel programming easier and is very common in scientific applications development scenarios. Considering the scope of BSP applications, the novel ideas of MigBSP are threefold: (i) combination of three metrics - Memory, Computation and Communication - in a scalar one in order to measure the potential of migration of each BSP process; (ii) employment of both Computation and Communication Patterns to control processes’ regularity and; (iii) efficient adaptation regarding the periodicity to launch processes rescheduling. In our infrastructure, we are considering heterogeneous (different processor and network speed) distributed systems. The processes can pass messages among themselves and the parallel machine can gather local area networks and clusters. The proposed model provides a mathematical formalism to decide the following questions about load (BSP processes) balancing: (i) When to launch the processes rescheduling; (ii) Which processes will be candidates for migration and; (iii) Where to put the processes that will be migrated actually. We used the simulation technique to validate MigBSP. Besides MigBSP, three scientific application were developed and executed using Simgrid simulator. In general, the results showed that MigBSP offers an opportunity to get performance in an effortless manner to the programmer since its does not need modification on application code. MigBSP makes possible gains of performance up to 20% as well as produces a low overhead when migrations do not take place. Its mean overhead is lower than 8% of the normal application execution time. This rate was obtained disabling any processes migration indicated by MigBSP. The results show that the union of considered metrics is a good solution to control processes migration. Moreover, they revealed that the developed adaptations are crucial to turn MigBSP execution viable, mainly on unbalanced environments.

O aumento crescente no número de processadores das arquiteturas paralelas que estão no topo dos rankings de desempenho, apesar de permitir uma maior capacidade de processamento, também traz consigo um aumento na taxa de falhas diretamente proporcional ao número de processadores. Atualmente, as técnicas de tolerância a falhas com recuperação retroativa são as mais empregadas em aplicações MPI, principalmente a técnica de checkpoint coordenado. No entanto, previsões afirmam que essa última técnica será inadequada para as arquiteturas emergentes. Em contrapartida, as técnicas de log de mensagens possuem características que as tornam mais apropriadas no novo cenário que se estabelece. O presente trabalho consiste em uma proposta de log de mensagens pessimista remoto com checkpoint não-coordenado e a avaliação de desempenho da comunicação MPI sobre Publish/Subscriber no qual se baseia o log de mensagens. O trabalho compreende: um estudo das técnicas de tolerância a falhas mais empregadas em ambientes de alto desempenho e a motivação para a escolha dessa variante de log de mensagens; a proposta de log de mensagens; uma implementação de comunicação Open MPI sobre OpenAMQ e sua respectiva avaliação de desempenho com comunicação tradicional TCP/IP e com o log de mensagens pessimista local da distribuição do Open MPI. Os benchmarks utilizados foram o NetPIPE, o NAS Parallel Benchmarks e a aplicação Virginia Hydrodynamics (VH-1). / The growing number of processors in parallel architectures at the top of performance rankings allows a higher processing capacity. However, it also brings an increase in the fault rate which is directly proportional to the number of processors. Nowadays, coordinated checkpoint is the most widely used rollback technique for system recovery in the occurrence of faults in MPI applications. Nevertheless, projections point that this technique will be inappropriate for the emerging architectures. On the other hand, message logging seems to be more appropriate to this new scenario. This work consists in a proposal of pessimistic message logging (remote based) with non-coordinated checkpoint and the performance evaluation of an MPI communication mechanism that works over Publish/Subscriber channels in which the proposed message logging is based. The work is organized as following: an study of fault tolerant techniques used in HPC and the motivation for choosing this variant of message logging; a message logging proposal; an implementation of Open MPI communication over OpenAMQ; performance evaluation and comparision with the tradicional TCP/IP communication and a pessimistic message logging (sender based) from Open MPI distribution. The benchmark set is composed of NetPIPE, NAS Parallel Benchmarks and Virginia Hydrodynamics (VH-1).

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / Parallel architectures has been ubiquitous for some time now. However, the word ubiquitous can’t be applied to parallel programs, because there is a greater complexity to code them comparing to ordinary programs. This fact is aggravated when the programming also involves accelerators, like GPUs, which demand the use of tools with scpecific resources. Considering this setting, there are programming models that make easier the codification of parallel applications to explore accelerators, nevertheless, we don’t know APIs that allow implementing programs with parallel loops that can be processed simultaneously by multiple CPUs and multiple GPUs. This works presents a high-level C++ API called HPSM aiming to make easier and more efficient the codification of parallel programs intended to explore multi-CPU and multi-GPU architectures. Following this idea, the desire is to improve performance through the sum of resources. HPSM uses parallel loops and reductions implemented by three parallel back-ends, being Serial, OpenMP and StarPU. Our hypothesis estimates that scientific applications can explore heterogeneous processing in multi-CPU and multi-GPU to achieve a better performance than exploring just accelerators. Comparisons with other parallel programming interfaces demonstrated that HPSM can reduce a multi-CPU and multi-GPU code in more than 50%. The use of the new API can introduce impact to program performance, where experiments showed a variable overhead for each application, that can achieve a maximum value of 16,4%. The experimental results confirmed the hypothesis, because the N-Body, Hotspot e CFD applications achieved gains using just CPUs and just GPUs, as well as overcame the performance achieved by just accelerators (GPUs) through the combination of multi-CPU and multi-GPU. / Arquiteturas paralelas são consideradas ubíquas atualmente. No entanto, o mesmo termo não pode ser aplicado aos programas paralelos, pois existe uma complexidade maior para codificálos em relação aos programas convencionais. Este fato é agravado quando a programação envolve também aceleradores, como GPUs, que demandam o uso de ferramentas com recursos muito específicos. Neste cenário, apesar de existirem modelos de programação que facilitam a codificação de aplicações paralelas para explorar aceleradores, desconhece-se a existência de APIs que permitam a construção de programas com laços paralelos que possam ser processados simultaneamente em múltiplas CPUs e múltiplas GPUs. Este trabalho apresenta uma API C++ de alto nível, denominada HPSM, visando facilitar e tornar mais eficiente a codificação de programas paralelos voltados a explorar arquiteturas com multi-CPU e multi-GPU. Seguindo esta ideia, deseja-se ganhar desempenho através da soma dos recursos. A HPSM é baseada em laços e reduções paralelas implementadas por meio de três diferentes back-ends paralelos, sendo Serial, OpenMP e StarPU. A hipótese deste estudo é que aplicações científicas podem valer-se do processamento heterogêneo em multi-CPU e multi-GPU para alcançar um desempenho superior em relação ao uso de apenas aceleradores. Comparações com outras interfaces de programação paralela demonstraram que o uso da HPSM pode reduzir em mais de 50% o tamanho de um programa multi-CPU e multi-GPU. O uso da nova API pode trazer impacto no desempenho do programa, sendo que experimentos demonstraram que seu sobrecusto é variável de acordo com a aplicação, chegando até 16,4%. Os resultados experimentais confirmaram a hipótese, pois as aplicações N-Body, Hotspot e CFD, além de alcançarem ganhos ao utilizar somente CPUs e somente GPUs, também superaram o desempenho obtido por somente aceleradores (GPUs) através da combinação de multi-CPU e multi-GPU.

Orientador: Alexandro José Baldassin / Banca: Rodolfo Jardim de Azevedo / Banca: Daniel Carlos Guimarães Pedronette / Resumo: O conceito de Memória Transacional foi criado para simplificar a sincronização de dados em memória, necessária para evitar a computação de dados inconsistentes por processadores multinúcleos, que se tornaram padrão devido às limitações encontradas em processadores de um núcleo. Em evolução constante pela busca de desempenho, os escalonadores de transação foram criados como alternativa aos gerenciadores de contenção presentes nos Sistemas de Memória Transacional. O consumo de energia é preocupação crescente, desde os grandes data centers até os disposítivos móveis que dependem de tempo de bateria, sendo também explorado no contexto de sistemas com Memória Transacional. Trabalhos anteriores consideraram, em sua maioria, somente o uso de gerenciadores de contenção, sendo o objetivo deste trabalho uma análise sobre o uso de escalonadores de transação. Desta forma, são exploradas nesta dissertação as técnicas de escalonamento dinâmico de tensão e frequência (DVFS) para a criação de uma heurística para a redução do consumo de energia utilizando o escalonador LUTS como base. Com o uso de aplicações do benchmark STAMP e biblioteca de memória transacional TinySTM, este trabalho faz uma análise sobre a eficiência energética dos escalonadores de referência ATS e LUTS, enquanto propõe uma nova heurística com o objetivo de reduzir o consumo de energia, denominada LUTSDynamic-Serializer, que alterna entre o uso de spinlock e de trava mutex de forma dinâmica. O uso desta heurística reduziu o EDP em até 17% e 61% em valores de EDP (Eenergy-Delay Product), e 4,95% e 15,8% na média geométrica das aplicações estudadas, em comparação aos escalonadores LUTS e ATS respectivamente, quando se utilizou a configuração de 8 threads, que é a limitação física de threads do processador utilizado no ambiente de experimento / Abstract: The Transactional Memory concept was created to simplify the synchronization of data in memory, needed to avoid computation of inconsistent data in multicore processors, which became standard due to limitations in single core processors. In constant search for performance, transactional schedulers were created as a alternative to contention managers present in transactional memory systems. The energy consumption is a crescent worry, ranging from big data centers to mobile devices which are dependent on battery life, and also being studied in Transactional Memory systems. Past works only considered the use of contention managers, and therefore this work seeks to analyse the impact of transactional schedulers. The techniques involving Dynamic Frequency-Voltage Scaling (DVFS) were explored with the motivation to create a heuristic to reduce energy consumption using the LUTS scheduler as a start. Utilizing the STAMP benchmark and the TinySTM transactional memory library, this work does an analysis about the energy efficiency of the reference scheduler ATS and LUTS, while proposing a new heuristic, named LUTSDynamic-Serializer, with the aim to reduce energy consumption by making a choice between spin-lock and mutex lock in a dynamic manner. We achieve with our heuristic up to 17% and 61% in EDP (Energy-Delay Product), and 4,95% and 15,8% considering the geometric mean among the applications studied, compared against the schedulers LUTS and ATS respectively, when we used the configuration with 8 threads, which is the physical limit of threads in the processor used in the experiments / Mestre

O problema da predição da estrutura de proteínas (PPEP) é bastante conhecido na bioinformática. A identificação da conformação nativa de uma proteína permite predizer a sua função no organismo. Este conhecimento também é útil no desenvolvimento de novos fármacos ou na compreensão do mecanismo de várias doenças. Várias técnicas tem sido propostas para resolver este problema. Porém, o alto custo envolvido levou ao surgimento de vários modelos que simplificam, em parte, as estruturas protéicas. No entanto, mesmo com os modelos mais simplificados, a complexidade do problema traz inúmeros desafios computacionais na busca da sua conformação nativa. Este trabalho utiliza o algoritmo evolucionário denominado Evolução Diferenciada (ED) para solucionar o PPEP, representando as proteínas com o modelo AB (toy model), em duas e três dimensões (2D e 3D). O trabalho apresenta a implementação de duas versões da ED, paralelizadas num ambiente de processo em cluster, com Message Passing Interface e arquitetura mestre-escravo. Para a configuração dos operadores do algoritmo de ED, foram realizados vários estudos com diferentes configurações para ambos os modelos, e análises estatísticas determinaram quais os melhores valores. Além disso, foram criados dois operadores especiais: dizimação e mutação espelhada. O primeiro poder ser considerado um operador genérico, que pode ser utilizado em qualquer problema; o segundo é específico para o problema em questão. Além do algoritmo de ED básico, também foi proposta uma versão auto-adaptável, em que alguns de seus parâmetros são atualizados no decorrer da evolução. Os experimentos realizados utilizaram 4 sequências de aminoácidos de benchmark geradas a partir da sequência de Fibonacci, contendo entre 13 e 55 aminoácidos. Os resultados dos algoritmos de ED paralelos foram comparados com os resultados obtidos em outros trabalhos. O algoritmo de ED é capaz de obter resultados excelentes, competitivos com os métodos especializados, apesar de não atingir o ótimo conhecido em algumas instâncias. Os resultados promissores obtidos nesse trabalho mostram que o algoritmo de ED é adequado para o problema. Em trabalhos futuros poderão ser estudados novos operadores especiais ou outras técnicas de inspiração biológica, buscando melhorar os resultados. / Protein structure prediction is a well-known problem in bioinformactis. Identifying protein native conformation makes it possible to predict its function within the organism. Knowing this also helps in the development of new medicines and in comprehending how some illnesses work and act. During the past year some techniques have been proposed to solve this problem, but its high cost made it necessary to build models that simplify the protein structures. However, even with the simplicity of these models identifying the protein native conformation remains a highly complex, computationally challenging problem. This paper uses an evolutionary algorithm known as Differential Evolution (DE) to solve the protein structure prediction problem. The model used to represent the protein structure is the Toy Model (also known as the AB Model) in both 2D and 3D. This work implements two versions of the ED algorithm using a parallel architecture (master-slave) based on Message Passing interface in a cluster. A large number of tests were executed to define the final configuration of the DE operators for both models. A new set of special operators were developed: explosion and mirror mutation. We can consider the first as generic, because it can be used in any problem. The second one is more specific because it requires previous knowledge of the problem. Of the two DE algorithm implemented, one is a basic DE algorithm and the second is a self-adaptive DE. All tests executed in this work used four benchmark amino acid sequences generated from the Fibonacci sequence. Each sequence has 13 to 55 amino acids. The results for both parallel DE algorithms using both 2D and 3D models were compared with other works. The DE algorithm achieved excellent results. It did not achieve the optimal known values for some sequences, but it was competitive with other specialized methods. Overall results encourage further research toward the use of knowledge-based operators and biologically inspired techniques to improve DE algorithm performance.

CAPES / Este trabalho propõe uma modificação da meta-heurística Busca Harmônica (HS) a partir de uma nova abordagem baseada em população, empregando, também, algumas estratégias inspiradas em outras meta-heurísticas. Este novo modelo foi implementado utilizando a arquitetura de programação paralela CUDA em uma GPU. O uso de placas de processamento gráficas (GPU) para processamento de propósito geral está crescendo, e estas têm sido utilizadas por muitos pesquisadores para processamento científico. Seu uso se mostra interessante para meta-heurísticas populacionais, podendo realizar muitas operações simultaneamente. A HS é uma meta-heurística inspirada no objetivo de um músico em buscar uma harmonia perfeita. modelo proposto incluiu-se uma população de harmonias temporárias que são geradas a cada nova iteração, permitindo a realização simultânea de diversas avaliações de função. Assim aumenta-se o grau de paralelismo da HS, possibilitando maiores ganhos de velocidade com o uso de arquiteturas paralelas. O novo modelo proposto executado em GPU foi denominado Mega Harmony Search (MHS). Na implementação em GPU cada passo do algoritmo é tratado individualmente em forma de kernels com configurações particulares para cada um. Para demonstrar a eficácia do modelo proposto foram selecionados alguns problemas de benchmark, como a otimização de estruturas de proteínas, a otimização de treliças e problemas matemáticos. Através de experimentos fatoriais foi identificado um conjunto de parâmetros padrão, o qual foi utilizado nos outros experimentos. As análises realizadas sobre resultados experimentais mostram que o MHS apresentou solução de qualidade equivalente à HS e ganhos de velocidade, com a sua execução em GPU, superiores a 60x quando comparado a implementação em CPU. Em trabalhos futuros poderão ser estudadas novas modificações ao algoritmo, como a implementação de nichos e estudos de estratégias de interação entre eles. / This work propose a new approach for the metaheuristic Harmonic Search (HS), by using a population of solutiona and other strategies inspired in another metaheuristics. This new model was implemented using a parallel architecture of a graphical processing unity (GPU). The use of GPU for general-purpose processing is growing, specially for scientific processing. Its use is particularly interesting for populational metaheuristics, where multiple operations are executed simultaneously. The HS is a metaheuristic inspired by the way jazz musicians search for a perfect harmony. In the proposed model a population of temporary harmonies was included. Such population was generated at each iteration, enabling simultaneous evaluation of the objective function being optimized, and thus, increasing the level of parallelism of HS. The new approach implemented in GPU was named Mega Harmony Search (MHS), and each step of the algorithm is handled in the form of kernels with particular configurations for each one. To show the efficiency of MHS some benchmark problems were selected for testing, including mathematical optimization problems, protein structure prediction, and truss structure optimization. Factorial experiments were done so as to find the best set of parameters for the MHS. The analyzes carried out on the experimental results show that the solutions provided by MHS have comparable quality to those of the simple Harmony Search. However, by using GPU, MHS achieved a speedup of 60x, compared with the implementation in regular CPU. Future work will focus other improvements in the algorithm, such as the use of niches and species, as well a study of the interactions between them.

CAPES / Este trabalho propõe uma modificação da meta-heurística Busca Harmônica (HS) a partir de uma nova abordagem baseada em população, empregando, também, algumas estratégias inspiradas em outras meta-heurísticas. Este novo modelo foi implementado utilizando a arquitetura de programação paralela CUDA em uma GPU. O uso de placas de processamento gráficas (GPU) para processamento de propósito geral está crescendo, e estas têm sido utilizadas por muitos pesquisadores para processamento científico. Seu uso se mostra interessante para meta-heurísticas populacionais, podendo realizar muitas operações simultaneamente. A HS é uma meta-heurística inspirada no objetivo de um músico em buscar uma harmonia perfeita. modelo proposto incluiu-se uma população de harmonias temporárias que são geradas a cada nova iteração, permitindo a realização simultânea de diversas avaliações de função. Assim aumenta-se o grau de paralelismo da HS, possibilitando maiores ganhos de velocidade com o uso de arquiteturas paralelas. O novo modelo proposto executado em GPU foi denominado Mega Harmony Search (MHS). Na implementação em GPU cada passo do algoritmo é tratado individualmente em forma de kernels com configurações particulares para cada um. Para demonstrar a eficácia do modelo proposto foram selecionados alguns problemas de benchmark, como a otimização de estruturas de proteínas, a otimização de treliças e problemas matemáticos. Através de experimentos fatoriais foi identificado um conjunto de parâmetros padrão, o qual foi utilizado nos outros experimentos. As análises realizadas sobre resultados experimentais mostram que o MHS apresentou solução de qualidade equivalente à HS e ganhos de velocidade, com a sua execução em GPU, superiores a 60x quando comparado a implementação em CPU. Em trabalhos futuros poderão ser estudadas novas modificações ao algoritmo, como a implementação de nichos e estudos de estratégias de interação entre eles. / This work propose a new approach for the metaheuristic Harmonic Search (HS), by using a population of solutiona and other strategies inspired in another metaheuristics. This new model was implemented using a parallel architecture of a graphical processing unity (GPU). The use of GPU for general-purpose processing is growing, specially for scientific processing. Its use is particularly interesting for populational metaheuristics, where multiple operations are executed simultaneously. The HS is a metaheuristic inspired by the way jazz musicians search for a perfect harmony. In the proposed model a population of temporary harmonies was included. Such population was generated at each iteration, enabling simultaneous evaluation of the objective function being optimized, and thus, increasing the level of parallelism of HS. The new approach implemented in GPU was named Mega Harmony Search (MHS), and each step of the algorithm is handled in the form of kernels with particular configurations for each one. To show the efficiency of MHS some benchmark problems were selected for testing, including mathematical optimization problems, protein structure prediction, and truss structure optimization. Factorial experiments were done so as to find the best set of parameters for the MHS. The analyzes carried out on the experimental results show that the solutions provided by MHS have comparable quality to those of the simple Harmony Search. However, by using GPU, MHS achieved a speedup of 60x, compared with the implementation in regular CPU. Future work will focus other improvements in the algorithm, such as the use of niches and species, as well a study of the interactions between them.