Arquiteturas paralelas modernas têm hierarquias de memória complexas, que consistem de vários níveis de memórias cache privadas e compartilhadas, bem como Non-Uniform Memory Access (NUMA) devido a múltiplos controladores de memória por sistema. Um dos grandes desafios dessas arquiteturas é melhorar a localidade e o balanceamento de acessos à memória de tal forma que a latência média de acesso à memória é reduzida. Dessa forma, o desempenho e a eficiência energética de aplicações paralelas podem ser melhorados. Os acessos podem ser melhorados de duas maneiras: (1) processos que acessam dados compartilhados (comunicação entre processos) podem ser alocados em unidades de execução próximas na hierarquia de memória, a fim de melhorar o uso das caches. Esta técnica é chamada de mapeamento de processos. (2) Mapear as páginas de memória que cada processo acessa ao nó NUMA que ele está sendo executado, assim, pode-se reduzir o número de acessos a memórias remotas em arquiteturas NUMA. Essa técnica é conhecida como mapeamento de dados. Para melhores resultados, os mapeamentos de processos e dados precisam ser realizados de forma integrada. Trabalhos anteriores nesta área executam os mapeamentos separadamente, o que limita os ganhos que podem ser alcançados. Além disso, a maioria dos mecanismos anteriores exigem operações caras, como traços de acessos à memória, para realizar o mapeamento, além de exigirem mudanças no hardware ou na aplicação paralela. Estes mecanismos não podem ser considerados soluções genéricas para o problema de mapeamento. Nesta tese, fazemos duas contribuições principais para o problema de mapeamento. Em primeiro lugar, nós introduzimos um conjunto de métricas e uma metodologia para analisar aplicações paralelas, a fim de determinar a sua adequação para um melhor mapeamento e avaliar os possíveis ganhos que podem ser alcançados através desse mapeamento otimizado. Em segundo lugar, propomos um mecanismo que executa o mapeamento de processos e dados online. Este mecanismo funciona no nível do sistema operacional e não requer alterações no hardware, os códigos fonte ou bibliotecas. Uma extensa avaliação com múltiplos conjuntos de carga de trabalho paralelos mostram consideráveis melhorias em desempenho e eficiência energética. / Reducing the cost of memory accesses, both in terms of performance and energy consumption, is a major challenge in shared-memory architectures. Modern systems have deep and complex memory hierarchies with multiple cache levels and memory controllers, leading to a Non-Uniform Memory Access (NUMA) behavior. In such systems, there are two ways to improve the memory affinity: First, by mapping tasks that share data (communicate) to cores with a shared cache, cache usage and communication performance are improved. Second, by mapping memory pages to memory controllers that perform the most accesses to them and are not overloaded, the average cost of accesses is reduced. We call these two techniques task mapping and data mapping, respectively. For optimal results, task and data mapping need to be performed in an integrated way. Previous work in this area performs the mapping only separately, which limits the gains that can be achieved. Furthermore, most previous mechanisms require expensive operations, such as communication or memory access traces, to perform the mapping, require changes to the hardware or to the parallel application, or use a simple static mapping. These mechanisms can not be considered generic solutions for the mapping problem. In this thesis, we make two contributions to the mapping problem. First, we introduce a set of metrics and a methodology to analyze parallel applications in order to determine their suitability for an improved mapping and to evaluate the possible gains that can be achieved using an optimized mapping. Second, we propose two automatic mechanisms that perform task mapping and combined task/data mapping, respectively, during the execution of a parallel application. These mechanisms work on the operating system level and require no changes to the hardware, the applications themselves or their runtime libraries. An extensive evaluation with parallel applications from multiple benchmark suites as well as real scientific applications shows substantial performance and energy efficiency improvements that are significantly higher than simple mechanisms and previous work, while maintaining a low overhead.

[pt] O desenvolvimento de metaheurísticas paralelas autonômicas para serem executadas eficientemente em ambientes de grid é o objetivo desta tese. A aplicação paralela deve ser capaz de se auto-adaptar às mudanças que ocorrem dinamicamente no ambiente, sem que o usuário precise interferir diretamente no código da mesma. Para isso, a metaheurística autonômica deve ser vista como uma aplicação com dois níveis independentes: middleware e estratégia. O middleware é responsável por gerenciar todo o ambiente de execução, de acordo com as características da aplicação. A estratégia hierárquica distribuída permite a cooperação entre todos os processos envolvidos, sem degradar o desempenho da aplicação devido ao aumento da comunicação entre processos. Para validar esta proposta foram desenvolvidas duas implementações paralelas de metaheurísticas, uma para o problema do torneio com viagens espelhado e a outra para o problema da árvore geradora de custo mínimo com restrição de diâmetro. Para ambos os problemas, as implementações desenvolvidas foram testadas no ambiente grid Sinergia, formado por máquinas localizadas em três diferentes cidades do Estado do Rio de Janeiro. As parelizações foram capazes de melhorar, para várias instâncias, os melhores resultados conhecidos na literatura. / [en] The development of autonomic parallel metaheuristics to be efficiently executed in computational grid is the challenge of this thesis. The parallel application must be able to self-adjust to the changes that occur dynamically in the environment, without the user needing to interfere directly in the code of the application. For this, the autonomic metaheuristic should be seen as an application on two independent levels: middleware and strategy. The middleware is responsible for managing the entire execution environment, according to the characteristics of the application. The distributed hierarchical strategy enables the cooperation between all processes involved, without degrading the performance of the application due to increased communication between processes. To validate this proposal, two parallel implementations of metaheuristics were developed, one for the mirrored traveling tournament problem and the other for the diameter constrained minimum spanning tree problem. For both problems, the developed implementations were tested in the grid Synergy environment, formed by machines located in three different cities in the state of Rio de Janeiro. The paralelizations improved, for several instances, the best known results in the literature.

Dissertação (mestrado)—Universidade de Brasília, Faculdade de Tecnologia, Departamento de Engenharia Florestal, 2008. / Submitted by Kelly Marques (pereira.kelly@gmail.com) on 2009-10-21T17:24:55Z No. of bitstreams: 1 2008_Airton Mauro de Lara Santos.pdf: 729182 bytes, checksum: 85dd5fe8b4b289a97433d412060b9282 (MD5) / Approved for entry into archive by Guimaraes Jacqueline(jacqueline.guimaraes@bce.unb.br) on 2009-11-23T11:49:04Z (GMT) No. of bitstreams: 1 2008_Airton Mauro de Lara Santos.pdf: 729182 bytes, checksum: 85dd5fe8b4b289a97433d412060b9282 (MD5) / Made available in DSpace on 2009-11-23T11:49:04Z (GMT). No. of bitstreams: 1 2008_Airton Mauro de Lara Santos.pdf: 729182 bytes, checksum: 85dd5fe8b4b289a97433d412060b9282 (MD5) Previous issue date: 2008 / Os produtos engenheirados de madeiras (PEM) vêem se expandindo globalmente, estes são produzidos a partir da junção de mais de um composto de madeira, utilizando a melhor propriedade de cada um desses elementos, dando qualidade e eficiência as estruturas. As vigas em “I” pré-fabricadas de madeira, que usam painéis estruturais para o material da alma e a madeira serrada de pequena dimensão ou compostos estruturais de madeira - structural composite lumber (SCL) para os flanges, são consideradas a segunda geração dos PEM. Este produto substitui a utilização de grandes volumes de madeira serrada em aplicações de assoalho e telhado, para os edifícios residenciais e comerciais. Os objetivos do presente trabalho foram de estimar para as vigas em “I” por meio de modelos teóricos a rigidez a flexão (EI), módulo de ruptura (fM) e flecha (δ), e comparar estes valores com os valores obtidos experimentalmente por meio de ensaios de flexão estática; e comparar as vigas em “I” produzidas com diferentes compostos. Foram produzidos dois tipos de vigas em “I” uma com os flanges de painéis de lâminas paralelas (LVL) e alma de compensado e outra com os flanges de LVL e a alma de chapas de fibras orientadas (OSB). A alma e os flanges foram ensaiados para que suas propriedades fossem utilizadas nos modelos teóricos. Depois de realizados os ensaios de flexão estática os valores experimentais foram comparados por análise da variância com os valores teóricos. Para as vigas em “I” com alma de compensado somente para o fM não foi observada diferença significativa entre os valores experimentais e teóricos, para as demais variáveis EM e δ observou diferenças significativas. Para as vigas em “I” com a alma de OSB todas as variáveis estudadas, EM, fM e δ, não apresentaram diferenças significativas entre os valores teóricos e experimentais. As vigas em “I” com a alma de OSB apresentaram valores médios de EM e fM, 14.923e 28,7 MPa, superiores aos valores médios 10.115 e 20,0 MPa para EM e fM das vigas em “I” com alma de compensado. Para as vigas em “I” com alma de OSB foi possível estimar de forma confiável os valores de EM, fM e δ, validando assim os modelos teóricos utilizados, já para as vigas com alma de compensado os modelos não puderam ser validados, por apresentarem diferenças significativas entre os valores teóricos e experimentais. As vigas em “I” com alma de OSB apresentaram melhores propriedades mecânicas do que as vigas em “I” com alma de compensado, além de valores de δ inferiores. _______________________________________________________________________________ ABSTRACT / The engineered wood products (EWPs) are products that have expanded globally. They are produced from the junction of more than one wood composite, using the best property of each one, providing qualified and efficient structures. The wood I-joists are produced using structural panels on the web and lumber or structural wood composite lumber (SCL) on the flanges. They are considered as the second generation of EWPs. This product replaces the use of large quantity of timber in floor and roof applications for both residential and commercial buildings. The aims of the study were to estimate theoretically the bending stiffness (EI), modulus of rupture (fM) and deflection (δ), and compare it with the values obtained experimentally. Further study was done to evaluate the effect of web type on these variables. Two types of I-joist were produced: oriented strand board (OSB) webbed I-joist and plywood webbed I-joist. For plywood webbed I-joist the results pointed out that no significant difference between the experimental and theoretical fM values were observed. However, for EM and δ significant differences were identified. On the other hand, for OSB webbed I-joist significant differences between theoretical and experimental values of the evaluated variables were not identified. The I-joist with the web of OSB showed mean values of EM and fM, 14,923 and 28.7 MPa, above the average values 10,115 and 20.0 MPa for EM and fM the I-joist with web of offset. For I-joist with web of OSB was possible to estimate reliable data of EM, fM and δ, thus validating the theoretical models used. For the plywood webbed I-joits the models could not be validated, due to significant differences between the experimental and theoretical values. The OSB webbed I-joist presented better mechanical properties than the plywood webbed I-joist and also lower values δ.

Este trabalho apresenta um estudo sobre redes ópticas de interconexão aplicadas em arquiteturas paralelas, onde são propostos, simulados e analisados alguns modelos de redes. Essa é uma importante pesquisa, pois, as redes de interconexão influenciam diretamente o custo e desempenho das arquiteturas paralelas de computadores. O primeiro modelo de rede óptica proposto é chamado de SCF (Sistema Circular com Filas). Esse e um sistema sem colisões, onde há um canal exclusivo para controle de comunicação e cada nó possui um canal exclusivo para recepção de dados. Esse sistema tem um desempenho com alta taxa de vazão, alto nível de utilização e pequenas filas. Para a simulação da rede SCF foi desenvolvido um simulador dedicado, cuja adaptação para a simulação de outros modelos de redes, propostos nesse trabalho, foi facilmente realizada. Neste trabalho também foram propostos, simulados e analisados três modelos diferentes de chaves ópticas de distribuição para arquitetura paralela do tipo Dataflow. Os resultados dessas simulações mostram que componentes ópticos relativamente simples podem ser utilizados no desenvolvimento de sistemas de alto desempenho. / This work presents a study about optical interconnection network applied to parallel computer architectures, where is proposed, simulated and analyzed some models of optical interconnection networks. It is an important research because the interconnection networks influence directly the cost and performance of parallel computer architectures. The first optical interconnection network model proposed in this work is called SCF (Sistema Circular com Filas). It is a system without collisions, where there is a dedicated channel for communication control and each node has a fixed channel for data reception. The system has a performance with high throughput, high utilization leve1 and small queue size. For the SCF simulation was developed a dedicated simulator, whose adjust to simulate others optical interconnection network, proposed in this work, was easily performed. In this work also were proposed, simulated and analyzed three different models of optical distributing network for Dataflow computer architecture, whose results shows that single optical devises can ensure the development of high performance systems.

Com o crescente número de usuários de computadores, novas ferramentas têm sido apresentadas com a finalidade de aumentar a eficiência dos computadores, meio para que seus usuários disponham de recursos automatizados. Mais recentemente, máquinas ligadas em rede de computadores e o fenômeno Internet tornaram necessárias ferramentas específicas para este tipo particular de uso. Entre as principais respostas a essas necessidades surgiu a linguagem Java, que tem ganhado adeptos tanto na comunidade científica como no mercado. Surge daí a necessidade de buscar formas alternativas para o uso de computadores em rede. Entre as soluções propostas encontra-se a de arquiteturas e linguagens paralelas. Estas ferramentas, ainda em fase experimental, apresentam soluções que podem a médio e longo prazo serem viáveis, desde que estudos e pesquisas mostrem sua viabilidade. Neste trabalho investiga-se a aplicação do conceito de paralelismo em linguagens para rede, mais especificamente a linguagem Java. A proposta é estudar as possíveis formas para se explorar o paradigma de linguagens paralelas em ambientes Java. Para isto, apresenta-se uma pesquisa relativa as principais linguagens paralelas disponíveis na literatura, de forma a conhecer as melhores soluções apresentadas por essas linguagens. O trabalho apresenta também um estudo realizado em um conjunto de ferramentas Java disponíveis no mercado. Finalmente, propõe-se um novo ambiente que possa disponibilizar ao usuário os melhores recursos da linguagem Java, explorando as melhores soluções encontradas na literatura. / With the increasing number of computer users, new tools have been presented to improve the computers efficiency and to make automated resources available for those users. Nowadays, the use of computers in a network and the Internet phenomenon requires specific tools. Among them, the Java language appears as an important tool, which has been attracting users in both the scientific and commercial communities. At the same time the computer networks are becoming more popular and some problems have emergent concerned to the networks assessment and connections. It is necessary to look for alternative ways of handling the network computer systems. The parallel architectures and languages appear among the proposed solutions. These tools are still in an experimental phase, studies and researches being necessary additional to confirm their feasibility. In this work we investigate the application of parallelism concepts in languages for networks, and particular we deal with the Java language. The aim is to study the possible approaches for exploring the parallel languages paradigm in Java environments. Research about the main parallel languages available in the literature is presented, in order to check the best solutions proposed by those languages. The work also presents an investigation about the Java tools available in the commercial market. Finally a new environment is proposed that makes some of the best resources of language Java available to the users by exploring the best solutions found in the literature.

Existe um crescente aumento nos gastos mundiais em inovação, com maior participação de áreas como a computação, a eletrônica, a saúde, a área automotiva e a área industrial. Mecanismos diferenciados, assimétricos, tais como o estudado neste trabalho, necessitam de maiores investigações, como a realização de ensaios normatizados. Para se contribuir com esse cenário propõe-se a análise de um sistema robótico, de arquitetura paralela, para experimentos de múltiplas finalidades. O presente trabalho aborda desde a construção de uma máquina paralela de topologia assimétrica, passando por seu controle, até a obtenção de informações sobre essa nova arquitetura. A sua construção é dividida em cinco subsistemas, que se interrelacionam: o mecânico, o elétrico, o de atuação, o de controle e o de interface. Sete estratégias de controle foram comparadas de acordo com os seguintes critérios: a exatidão na trajetória, o comprimento controlável, a dispersão das trajetórias em diferentes períodos de tempo, e o consumo de energia. Os resultados foram gerados por meio de registro, em folha de papel, da trajetória do efetuador da máquina. As curvas geradas foram digitalizadas e comparadas entre si. Os resultados mostraram que os controles dinâmicos podem permitir o funcionamento adequado da máquina, sendo possível, inclusive, velocidades maiores que as observadas no controle descentralizado PID. Neste trabalho em particular, o maior desafio observado foi o valor da menor frequência natural amortecida, que se mostrou baixo e resultou em baixos esforços de controle. Em ordem decrescente, os tipos de controle que apresentaram melhores resultados foram o PID descentralizado, o controle por torque computado com feedforward, e o controle por modos deslizantes, também com feedforward. / There is a steady increase in global spending on innovation, with an increased share of areas such as computing, electronics, health, automotive and industrial area. Differentiated, asymmetric mechanisms, such as the one proposed in this work, need further investigations, such as standardized tests. To contribute to this scenario the analysis of a robotic system, with parallel architecture and for multi-purpose experiments, is proposed. This work covers the construction of a parallel machine with asymmetric topology, its control, and the collection of information on this new architecture. Its construction is divided into five sub-systems, which are interrelated: the mechanical, the electrical, the actuation, the control and its interface. Seven control strategies were compared, according to four criteria. The chosen criteria are the following: track accuracy, stability range, dispersion of the paths at different periods and energy consumption. The results were generated by recording, on a sheet of paper, the trajectory of the machine\'s end-effector. The plots were digitalized and compared. The results showed that the dynamic controls can allow the machine to behave appropriately, even at speeds higher than those with the decentralized PID. The main challenge in this case was the lowest damped frequency, with a low value that resulted in low control efforts. In decreasing order, the best results were achieved with the decentralized PID, the feedforward computed torque control and the feedforward sliding modes control.

Nos últimos anos, percebeu-se uma crescente busca por softwares e arquiteturas alternativas. Essa busca acontece porque houve avanços na tecnologia do hardware e estes avanços devem ser complementados por inovações nas metodologias de projetos, testes e verificação para que haja um uso eficaz da tecnologia. Muitos dos softwares e arquiteturas alternativas, geralmente partem para modelos que exploram o paralelismo das aplicações, ao contrário do modelo de von Neumann. Dentre as arquiteturas alternativas de alto desempenho, tem-se a arquitetura a fluxo de dados. Nesse tipo de arquitetura, o processo de execução de programas é determinado pela disponibilidade dos dados. Logo, o paralelismo está embutido na própria natureza do sistema. O modelo a fluxo de dados possui a vantagem de expressar o paralelismo de maneira intrínseca, eliminando a necessidade de o programador explicitar em seu código os trechos onde deve haver paralelismo. As arquiteturas a fluxo de dados voltaram a ser um tema de pesquisa devido aos avanços do hardware, em particular, os avanços da Computação Reconfigurável e os FPGAs (Field-Programmable Gate Arrays). O projeto ChipCflow é uma ferramenta para execução de algoritmos usando o modelo a fluxo de dados dinâmico em FPGA. Este trabalho apresenta o formato para os tagged-tokens do ChipCflow, os operadores de manipulação das tags dos tokens e suas implementações a fim de que se tenha a PROVA-DE-CONCEITOS para tais operadores na arquitetura ChipCflow / The alternative architectures and softwares researches have been growing in the last years. These researches are happening due to the advance of hardware technology and such advances must be complemented by improvements on design methodologies, test and verification techniques in order to use technology effectively. Many of the alternative architectures and softwares, in general, explore the parallelism of applications, differently to von Neumann model. Among high performance alternative architectures, there is the Dataflow Architecture. In this kind of architecture, the execution of programs is determined by data availability, thus the parallelism is intrinsic in these systems. The dataflow architectures become again a highlighted research area due to hardware advances, in particular, the advances of Reconfigurable Computing and FPGAs (Field-Programmable Gate Arrays). ChipCflow project is a tool for execution of algorithms using dynamic dataflow graph in FPGA. The main goal in this module of the ChipCflow project is to define the tagged-token format, the iterative operators that will manipulate the tags of tokens and to implement them

Este trabalho define um modelo de execução para cláusulas Prolog, a partir do modelo abstrato de Máquinas de Cláusulas, e o Projeto de uma arquitetura paralela que suporte o modelo proposto. São também introduzidos alguns aspectos sobre as linguagens Lógicas e as máquinas Prolog visto que estes elementos estão relacionados intimamente tanto com o modelo quanto com a arquitetura propostos. Na proposta do modelo de execução são definidos uma representação para os elementos do modelo abstrato (predicados, arcos e clausulas) e um conjunto de algoritmos que permitem a operacionalização do modelo de forma a que tanto o paralelismo como a concorrência inerentes ao modelo abstrato sejam exploradas de forma integral. Na proposta da arquitetura são, primeiramente, discutidas algumas opções de arquitetura básica e, posteriormente, descrita a arquitetura escolhida tanto a nível de blocos bem como dos seus componentes principais, a saber: interface de mem6ria, processador e rede de interconexão. Para cada um destes componentes são descritas as principais instruções e são apresentados os algoritmos que as implementam. Junto com a descrição da arquitetura é definida uma estrutura de dados que permite a implementação da representação descrita no modelo de execuqao e é definido também o algoritmo de unificação que percorre a estrutura proposta. Na validação é feito o cálculo da largura de banda máxima alcançada pela arquitetura proposta, calculo este baseado no algoritmo de unificação descrito. E também feita uma avaliação do ganho de performance da arquitetura proposta em relação a um processador bem como é justificado o numero de processadores escolhidos comparando a performance alcançada na arquitetura proposta com a performance alcançada por conjuntos maiores e menores de processadores. Por fim na conclusa o são feitos comentários sobre os objetivos atingidos e sobre possíveis extensões a este trabalho. / The present work defines a execution model for Prolog clauses based on the clause machines abstract model and then proposes a parallel architecture for the execution model. Some topics about Logic languages and Prolog machines were therefore introduced because they are closely related with, both, the model and the architecture proposed. In the execution model the representation of the abstract model elements (predicates, arcs and clauses) and the set of algoritms that allow the operation of the model were defined so that the parallelism of the model can be integraly achieved. In the architecture proposal, first some options for the basic architecture were discussed and then the chosen architecture is describeb at block level as much as at its components level. The most importants components reported are the memory interface, the processor and the interconection net, for each one of them the possible instructions were describeb as well as their algoritms. Together with the especification of the architecture, the data estructure that allows the implementation of the execution model representation and the concerning unification algorit that scans the proposed representation were especified too. In the validation the thoughtput permited by the proposal architecture is calculated based on the unification algoritm earlier described. Besides that the performance gain compared with an architecture with only one processor was estimated, as much as the confrontation of the performance of lesser and greater sets of processors elements were made in order to validate the chossen number. At last, in the conclusion, some coments about the fulfilled goals and about eventual extends for the work.

Arquiteturas paralelas modernas têm hierarquias de memória complexas, que consistem de vários níveis de memórias cache privadas e compartilhadas, bem como Non-Uniform Memory Access (NUMA) devido a múltiplos controladores de memória por sistema. Um dos grandes desafios dessas arquiteturas é melhorar a localidade e o balanceamento de acessos à memória de tal forma que a latência média de acesso à memória é reduzida. Dessa forma, o desempenho e a eficiência energética de aplicações paralelas podem ser melhorados. Os acessos podem ser melhorados de duas maneiras: (1) processos que acessam dados compartilhados (comunicação entre processos) podem ser alocados em unidades de execução próximas na hierarquia de memória, a fim de melhorar o uso das caches. Esta técnica é chamada de mapeamento de processos. (2) Mapear as páginas de memória que cada processo acessa ao nó NUMA que ele está sendo executado, assim, pode-se reduzir o número de acessos a memórias remotas em arquiteturas NUMA. Essa técnica é conhecida como mapeamento de dados. Para melhores resultados, os mapeamentos de processos e dados precisam ser realizados de forma integrada. Trabalhos anteriores nesta área executam os mapeamentos separadamente, o que limita os ganhos que podem ser alcançados. Além disso, a maioria dos mecanismos anteriores exigem operações caras, como traços de acessos à memória, para realizar o mapeamento, além de exigirem mudanças no hardware ou na aplicação paralela. Estes mecanismos não podem ser considerados soluções genéricas para o problema de mapeamento. Nesta tese, fazemos duas contribuições principais para o problema de mapeamento. Em primeiro lugar, nós introduzimos um conjunto de métricas e uma metodologia para analisar aplicações paralelas, a fim de determinar a sua adequação para um melhor mapeamento e avaliar os possíveis ganhos que podem ser alcançados através desse mapeamento otimizado. Em segundo lugar, propomos um mecanismo que executa o mapeamento de processos e dados online. Este mecanismo funciona no nível do sistema operacional e não requer alterações no hardware, os códigos fonte ou bibliotecas. Uma extensa avaliação com múltiplos conjuntos de carga de trabalho paralelos mostram consideráveis melhorias em desempenho e eficiência energética. / Reducing the cost of memory accesses, both in terms of performance and energy consumption, is a major challenge in shared-memory architectures. Modern systems have deep and complex memory hierarchies with multiple cache levels and memory controllers, leading to a Non-Uniform Memory Access (NUMA) behavior. In such systems, there are two ways to improve the memory affinity: First, by mapping tasks that share data (communicate) to cores with a shared cache, cache usage and communication performance are improved. Second, by mapping memory pages to memory controllers that perform the most accesses to them and are not overloaded, the average cost of accesses is reduced. We call these two techniques task mapping and data mapping, respectively. For optimal results, task and data mapping need to be performed in an integrated way. Previous work in this area performs the mapping only separately, which limits the gains that can be achieved. Furthermore, most previous mechanisms require expensive operations, such as communication or memory access traces, to perform the mapping, require changes to the hardware or to the parallel application, or use a simple static mapping. These mechanisms can not be considered generic solutions for the mapping problem. In this thesis, we make two contributions to the mapping problem. First, we introduce a set of metrics and a methodology to analyze parallel applications in order to determine their suitability for an improved mapping and to evaluate the possible gains that can be achieved using an optimized mapping. Second, we propose two automatic mechanisms that perform task mapping and combined task/data mapping, respectively, during the execution of a parallel application. These mechanisms work on the operating system level and require no changes to the hardware, the applications themselves or their runtime libraries. An extensive evaluation with parallel applications from multiple benchmark suites as well as real scientific applications shows substantial performance and energy efficiency improvements that are significantly higher than simple mechanisms and previous work, while maintaining a low overhead.

Submitted by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2018-02-07T18:59:59Z No. of bitstreams: 2 Tese_Rainer X. Amorim.pdf: 6271497 bytes, checksum: 42feec49cd385dde2a106aee5c11c269 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Approved for entry into archive by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2018-02-07T19:00:25Z (GMT) No. of bitstreams: 2 Tese_Rainer X. Amorim.pdf: 6271497 bytes, checksum: 42feec49cd385dde2a106aee5c11c269 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Made available in DSpace on 2018-02-07T19:00:25Z (GMT). No. of bitstreams: 2 Tese_Rainer X. Amorim.pdf: 6271497 bytes, checksum: 42feec49cd385dde2a106aee5c11c269 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Previous issue date: 2017-10-06 / FAPEAM - Fundação de Amparo à Pesquisa do Estado do Amazonas / This research investigates scheduling problems with earliness and tardiness penalties on single and parallel machine environments. This problem is also known in the literature as Just-in-Time scheduling, system widely used in industries to reduce inventories and costs, in order to lead product to be produced according to demand. In this work we present a hybrid exact-heuristic algorithmic strategy, based on an arc-time indexed integer programming formulation and a generalized evolutionary heuristic based on a strong local search, to better solve classical parallel machine scheduling problems involving weighted earliness-tardiness penalties, with independent jobs and arbitrary processing times. Selected arcs from local optima solutions generated by a genetic algorithm based on a strong local search (GLS) with generalized pairwise interchanges are given as input to the arc-time formulation, to produce better solutions than those obtained by both methods when used isolated. Computational experiments present competitive results according to the literature. Our proposed method also solves large instances up to 500 jobs in identical parallel machines. / Esta pesquisa investiga problemas de escalonamento com penalidades de antecipação e atraso em ambiente mono e multiprocessado envolvendo máquinas paralelas. Este problema é também conhecido na literatura como escalonamento Just-in-Time, sistema amplamente utilizado em indústrias para reduzir estoques e os custos decorrentes, a fim de que o produto seja produzido de acordo com a demanda. Neste trabalho é proposta uma estratégia algorítmica híbrida exato-heurística, baseada em uma formulação de programação inteira arc-time e um algoritmo evolucionário fortemente baseado em busca local, para melhor resolver problemas clássicos de escalonamento em máquinas paralelas envolvendo penalidades de antecipação e atraso, com tarefas independentes e tempos de processamento arbitrários. Os arcos são selecionados das soluções ótimas locais obtidas pelo algoritmo genético fortemente baseado em busca local (GLS) com movimentos generalizados de troca de pares, que são fornecidos como entrada para a formulação arc-time, para gerar soluções melhores do que as obtidas por ambos os métodos quando utilizados isoladamente. Os experimentos computacionais apresentam resultados competitivos em relação à literatura. O método proposto também resolve instâncias de tamanho maior de até 500 tarefas em máquinas paralelas idênticas.