Arquitetura de software e teste de software são importantes áreas com o objetivo comum de prover meios para que sistemas de software sejam desenvolvidos com alta qualidade. Foi constatado, por meio de um mapeamento sistemático, que existem poucos estudos relacionando essas duas áreas de modo que uma possa contribuir para a outra, principalmente em arquiteturas de referência e teste de software. Esse projeto tem por objetivo estender o modelo para arquiteturas de referência (RAModel), para que arquiteturas de referência sejam estabelecidas com informações de teste de software. Assim, além de promover padronização, uniformização e reúso a informações relacionadas a arquiteturas de software, promove-se também o reúso, a padronização e a uniformização das informações de teste de software no desenvolvimento das soluções para um dado domínio de aplicação. Para isso, elementos de teste relacionados ao planejamento de teste foram extraídos do TMMi e da norma ISO/IEC/IEEE 29119 e inseridos no RAModel, definindo, assim, o RAModelT . Dessa forma, a atividade de teste é incorporada aos estágios iniciais do desenvolvimento de software. Um estudo de viabilidade realizado para avaliar a extensão do RAModelT e um exemplo de aplicação são apresentados. / Software architecture and software testing are important areas with the common goal of providing the means to develop high-quality software systems. It was found through a systematic mapping that there are few studies relating these two areas so that one can contribute to the other, especially in reference architectures and software testing. This project aims at extending the Reference Architecture Model (RAModel), so that reference architectures are established with software test information. Thus, in addition to promoting standardization, standardization, and reuse of information related to software architectures, it is also promoted the reuse, standardization, and standardization of software test information in the development of solutions for a given application domain. For this, test elements related to the test planning were extracted from the TMMi and the ISO/IEC/IEEE 29119 standard and inserted into the RAModel, thus defining the RAModelT . In this way, the test activity is incorporated into the early stages of software development. A feasibility study performed to evaluate the extent of the RAModelT and an application example are presented.

Atualmente, pode-se observar que a Lei de Moore vem estagnando. A freqüência de operação já não cresce da mesma forma, e a potência consumida aumenta drasticamente em processadores de propósito geral. Ao mesmo tempo, sistemas embarcados vêm se tornando cada vez mais heterogêneos, caracterizados por uma grande quantidade de modelos computacionais diferentes, sendo executados em um mesmo dispositivo. Desta maneira, como novas tecnologias que irão substituir totalmente ou parcialmente o silício estão surgindo, novas soluções arquiteturais são necessárias. Apesar de sistemas reconfiguráveis já terem demonstrado serem candidatos em potencial para os problemas supracitados, ganhos significativos de desempenho são alcançados apenas em programas que manipulam dados massivamente, não representando a realidade dos sistemas atuais. Ademais, o seu uso em alta escala ainda está limitado à utilização de ferramentas ou compiladores que, claramente, não mantêm a compatibilidade de software e a reutilização do código binário já existente. Baseando-se nestes fatos, a presente tese propõe uma nova técnica para, utilizando um sistema reconfigurável, otimizar tanto programas orientados a dados como aqueles orientados a controle, sem a necessidade de modificação do código fonte ou binário. Para isto, um algoritmo de Tradução Binária, que trabalha em paralelo ao processador, foi desenvolvido. O mecanismo proposto é responsável pela transformação de seqüências de instruções, em tempo de execução, para serem executadas em uma unidade funcional reconfigurável de granularidade grossa, suportando execução especulativa. Desta maneira, é possível aproveitar as vantagens do uso da lógica combinacional para aumentar o desempenho e reduzir o gasto de energia, mantendo a compatibilidade binária em um processo totalmente transparente. Três diferentes estudos de caso foram feitos: os processadores Java e MIPS R3000 – representando o campo de sistemas embarcados – e o conjunto de ferramentas Simplescalar, que simula um processador superescalar baseado no MIPS R10000 – representando o mercado de processadores de propósito geral. / As Moore’s law is losing steam, one already sees the phenomenon of clock frequency reduction caused by the excessive power dissipation in general purpose processors. At the same time, embedded systems are getting more heterogeneous, characterized by a high diversity of computational models coexisting in a single device. Therefore, as innovative technologies that will completely or partially replace silicon are arising, new architectural alternatives are necessary. Although reconfigurable computing has already shown to be a potential solution for such problems, significant speedups are achieved just in very specific dataflow oriented software, not representing the reality of nowadays systems. Moreover, its wide spread use is still withheld by the need of special tools and compilers, which clearly preclude software portability and reuse of legacy code. Based on all these facts, this thesis presents a new technique using reconfigurable systems to optimize both control and dataflow oriented software without the need of any modification in the source or binary codes. For that, a Binary Translation algorithm has been developed, which works in parallel to the processor. The proposed mechanism is responsible for transforming sequences of instructions at runtime to be executed on a dynamic coarse-grain reconfigurable array, supporting speculative execution. This way, it is possible to take advantage of using pure combinational logic to speed up the execution, maintaining full binary compatibility in a totally transparent process. Three different case studies were evaluated: a Java Processor and a MIPS R3000 – representing the embedded systems field – and the Simplescalar Toolset, a widely used toolset that simulates a superscalar architecture based on the MIPS R10000 processor – representing the general-purpose market.

Esta tese apresenta DCE, ou Execução Dinâmica Condicional, como uma alternativa para reduzir o custo da previsão incorreta de desvios. A idéia básica do modelo apresentado é buscar e executar todos os caminhos de desvios que obedecem à certas restrições no que diz respeito a complexidade e tamanho. Como resultado, tem-se um número menor de desvios sendo previstos e consequentemente um número menor de desvios previstos incorretamente. DCE busca todos os caminhos dos desvios selecionados evitando quebras no fluxo de busca quando estes desvios são buscados. Os caminhos buscados dos desvios selecionados são então executados mas somente o caminho correto é completado. Nesta tese nós propomos uma arquitetura para executar múltiplos caminhos dos desvios selecionados. A seleção dos desvios ocorre baseada no tamanho do desvio e em outras condições. A seleção de desvios simples e complexos permite a predicação dinâmica destes desvios sem a necessidade da existência de um conjunto específico de instruções nem otimizações especiais por parte do compilador. Além disso, é proposta também uma técnica para reduzir a sobrecarga gerada pela execução dos múltiplos caminhos dos desvios selecionados. O desempenho alcançado atinge níveis de até 12% quando um previsor de desvios Local é usado no DCE e um previsor Global é usado na máquina de referência. Quando ambas as máquinas empregam previsão Local, há um aumento de desempenho da ordem de 3-3.5%. / This thesis presents DCE, or Dynamic Conditional Execution, as an alternative to reduce the cost of mispredicted branches. The basic idea is to fetch all paths produced by a branch that obey certain restrictions regarding complexity and size. As a result, a smaller number of predictions is performed, and therefore, a lesser number of branches are mispredicted. DCE fetches through selected branches avoiding disruptions in the fetch flow when these branches are fetched. Both paths of selected branches are executed but only the correct path commits. In this thesis we propose an architecture to execute multiple paths of selected branches. Branches are selected based on the size and other conditions. Simple and complex branches can be dynamically predicated without requiring a special instruction set nor special compiler optimizations. Furthermore, a technique to reduce part of the overhead generated by the execution of multiple paths is proposed. The performance achieved reaches levels of up to 12% when comparing a Local predictor used in DCE against a Global predictor used in the reference machine. When both machines use a Local predictor, the speedup is increased by an average of 3-3.5%.

Na presente tese, apresentamos uma nova abordagem para combinar reuso e prvisão de seqüências dinâmicas de instruções, chamada Reuso por Especulação em traces (RST). Esta técnica permite a identificação dinâmica de traces de instruções redundantes ou previsíveis e o reuso (especulativo ou não) desses traces. RST procura resolver a questão de traces que não são reusados por seus valores de entradas de Traces (DTM). Em estudo anteriores, esses traces foram contabilizados como sendo cerca de 69% de todos os traces reusáveis. Uma das maiores vantagens de RST sobre a combinação de um mecanismo de previsão com uma técnica de reuso de valores em que mecanismos não são relacionados é que RST não necessita de tabelas adicionais para o armazenamento dos valores a serem previstos. A aplciação de reuso e previsão de valores pela simples combinação de mecanismos pode necessitar de uma quantidade proibitiva de espaço de armazenamento. No mecanismo RST, os valores já estão presentes na Tabela de Memorização de Traces, não incorrendo em custos adicionais para lê-los se comparado com uma técnica não-especulativa de reuso de traces. O contexto de entrada de cada trace (os valores de entrada de todas as instruções contidas no trace) já armazenam os valores para o teste de reuso, os quais podem ser também utilizados para previsão de valores para o teste de reuso, os quais podem ser também utilizados para previsão de valores. As principais contribuições de nosso trabalho incluem: (i) um framework de reuso especulativo de traces que pode ser modificado para diferentes arquiteturas de processadores; (ii) definição das modificações necessárias em um processador superescalar e superpipeline para implementar nosso mecanismo; (iii) estudo de questões de implementação relacionadas à essa arquitetura; (iv) estudo dos limites de desempenho da nossa técnica; (v) estudo de uma implementação RST limitada por fatores realísticos; e (vi) ferramentas de simulação que podem ser utilizadas em outros estudos, representando um processador superescalar e superpipeline em detalhes. Salientamos que, em uma arquitetura utilizando mecanismos realistas de estimativa de confiança das previsões, nossa técnica RST consegue atingir speedups médios (médias harmônicas) de 1.29 sobre uma arquitetura sem reuso e 1.09 sobre uma técnica não-especulativa de reuso de traces (DTM). / In this thesis, we present a novel approach to combine both reuse and prediction of dynamic sequences of instructions called Reuse through Speculation on Traces (RST). Our technique allows the dynamic identification of instruction traces that are redundant or predictable, and the reuse (speculative or not) of these traces. RST addresses the issue, present on Dynamic Trace Memoization (DTM), of traces not being reused because some of their inputs are not ready for the reuse test. These traces were measured to be 69% of all reusable traces in previous studies. One of the main advantages of RST over just combining a value prediction technique with an unrelated reuse technique is that RST does not require extra tables to store the values to be predicted. Applying reuse and value prediction in unrelated mechanisms but at the same time may require a prohibitive amount of storage in tables. In RST, the values are already stored in the Trace Memoization Table, and there is no extra cost in reading them if compared with a non-speculative trace reuse technique. . The input context of each trace (the input values of all instructions in the trace) already stores the values for the reuse test, which may also be used for prediction. Our main contributions include: (i) a speculative trace reuse framework that can be adapted to different processor architectures; (ii) specification of the modifications in a superscalar, superpipelined processor in order to implement our mechanism; (iii) study of implementation issues related to this architecture; (iv) study of the performance limits of our technique; (v) a performance study of a realistic, constrained implementation of RST; and (vi) simulation tools that can be used in other studies which represent a superscalar, superpipelined processor in detail. In a constrained architecture with realistic confidence, our RST technique is able to achieve average speedups (harmonic means) of 1.29 over the baseline architecture without reuse and 1.09 over a non-speculative trace reuse technique (DTM).

A Execução Condicional Dinâmica (DCE) é uma alternativa para redução dos custos relacionados a desvios previstos incorretamente. A idéia básica é buscar todos os fluxos produzidos por um desvio que obedecem algumas restrições relativas à complexidade e tamanho. Como conseqüência, um número menor de previsões é executado, e assim, um número mais baixo de desvios é incorretamente previsto. Contudo, tal como outras soluções multi-fluxo, o DCE requer uma estrutura de controle mais complexa. Na arquitetura DCE, é observado que várias réplicas da mesma instrução são despachadas para as unidades funcionais, bloqueando recursos que poderiam ser utilizados por outras instruções. Essas réplicas são geradas após o ponto de convergência dos diversos fluxos em execução e são necessárias para garantir a semântica correta entre instruções dependentes de dados. Além disso, o DCE continua produzindo réplicas até que o desvio que gerou os fluxos seja resolvido. Assim, uma seção completa do código pode ser replicado, reduzindo o desempenho. Uma alternativa natural para esse problema é reusar essas seções (ou traços) que são replicadas. O objetivo desse trabalho é analisar e avaliar a efetividade do reuso de valores na arquitetura DCE. Como será apresentado, o princípio do reuso, em diferentes granularidades, pode reduzir efetivamente o problema das réplicas e levar a aumentos de desempenho. / The Dynamic Conditional Execution (DCE) is an alternative to reduce the cost of mispredicted branches. The basic idea is to fetch all paths produced by a branch that obey certain restrictions regarding complexity and size. As a consequence, a smaller number of predictions is performed, and therefore, a lower number branches is mispredicted. Nevertheless, as other multipath solutions, DCE requires a more complex control engine. In a DCE architecture, one may observe that several replicas of the same instruction are dispatched to the functional units, blocking resources that might be used by other instructions. Those replicas are produced after the join point of the paths and are required to guarantee the correct semantic among data dependent instructions. Moreover, DCE continues producing replicas until the branch that generated the paths is resolved. Thus, a whole section of code may be replicated, harming performance. A natural alternative to this problem is the attempt to reuse those replicated sections, namely the replicated traces. The goal of this work is to analyze and evaluate the effectiveness of value reuse in DCE architecture. As it will be presented, the principIe of reuse, in different granularities, can reduce effectively the replica problem and lead to performance improvements.

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.

Este trabalho apresenta um novo modelo de busca especulativa de múltiplos fluxos de instruções em arquiteturas superescalares. A avaliação de desempenho de uma arquitetura superescalar com esta característica é também apresentada como forma de validar o modelo proposto e comparar seu desempenho frente a uma arquitetura superescalar real. O modelo em questão pretende eliminar a latência de busca de instruções introduzida pela ocorrência de comandos de desvio em pipelines superescalares. O desempenho de uma arquitetura superescalar dotada de escalonamento dinâmico de instruções, previsão de desvios e execução especulatva é bastante inferior ao desempenho máximo teórico esperado. Como demonstrado em outros trabalhos, isto ocorre devido às constantes quebras de fluxo, derivadas de instruções de desvio, e do conseqüente esvaziamento da fila de instruções. O emprego desta técnica permite encadear instruções pertencentes a diferentes fluxos lógicos, logo após a identificação de uma instrução de desvio, disponibilizando um maior número de instruções ao mecanismo de escalonamento dinâmico e diminuindo o número de ciclos com despacho nulo devido as quebras de fluxo. Algumas considerações sobre a implementação do modelo descrito são apresentadas ao final do trabalho assim como sugestões para trabalhos futuros. / This work presents a new model to fetch instructions along multiple streams in superscalar pipelines. Also, the performance evaluation of a superscalar architecture including this feature is presented in order to validate the model and to compare its performance with a real superscalar architecture. The proposed technique intents to eliminate the instruction fetch latency introduced by branch instructions in superscalar pipelines. The performance delivered by a superscalar architecture which incorporate dynamic instruction scheduling, branch prediction and speculative execution is not the expected one which should be at least proportional to the number of functional units. Related works have shown that constant stream breaks caused by disruptions in the sequential flow of control reduce the amount of instructions into the instruction queue. This technique allows instruction fetch through different logic streams, as soon as the branch instruction has been detected during the fetch. The scheduler needs a large instruction window to be able to schedule efficiently consequently the instructions window should hold as many instructions as possible to allow an efficient schedule. The improvement realized by the proposed scheme is to increase the size of the instruction window by putting there more instructions avoiding interruptions on the event of branch occurrence. Some considerations about the implementation of this model are presented at final as well as suggestions to future works.

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.

Atualmente, pode-se observar que a Lei de Moore vem estagnando. A freqüência de operação já não cresce da mesma forma, e a potência consumida aumenta drasticamente em processadores de propósito geral. Ao mesmo tempo, sistemas embarcados vêm se tornando cada vez mais heterogêneos, caracterizados por uma grande quantidade de modelos computacionais diferentes, sendo executados em um mesmo dispositivo. Desta maneira, como novas tecnologias que irão substituir totalmente ou parcialmente o silício estão surgindo, novas soluções arquiteturais são necessárias. Apesar de sistemas reconfiguráveis já terem demonstrado serem candidatos em potencial para os problemas supracitados, ganhos significativos de desempenho são alcançados apenas em programas que manipulam dados massivamente, não representando a realidade dos sistemas atuais. Ademais, o seu uso em alta escala ainda está limitado à utilização de ferramentas ou compiladores que, claramente, não mantêm a compatibilidade de software e a reutilização do código binário já existente. Baseando-se nestes fatos, a presente tese propõe uma nova técnica para, utilizando um sistema reconfigurável, otimizar tanto programas orientados a dados como aqueles orientados a controle, sem a necessidade de modificação do código fonte ou binário. Para isto, um algoritmo de Tradução Binária, que trabalha em paralelo ao processador, foi desenvolvido. O mecanismo proposto é responsável pela transformação de seqüências de instruções, em tempo de execução, para serem executadas em uma unidade funcional reconfigurável de granularidade grossa, suportando execução especulativa. Desta maneira, é possível aproveitar as vantagens do uso da lógica combinacional para aumentar o desempenho e reduzir o gasto de energia, mantendo a compatibilidade binária em um processo totalmente transparente. Três diferentes estudos de caso foram feitos: os processadores Java e MIPS R3000 – representando o campo de sistemas embarcados – e o conjunto de ferramentas Simplescalar, que simula um processador superescalar baseado no MIPS R10000 – representando o mercado de processadores de propósito geral. / As Moore’s law is losing steam, one already sees the phenomenon of clock frequency reduction caused by the excessive power dissipation in general purpose processors. At the same time, embedded systems are getting more heterogeneous, characterized by a high diversity of computational models coexisting in a single device. Therefore, as innovative technologies that will completely or partially replace silicon are arising, new architectural alternatives are necessary. Although reconfigurable computing has already shown to be a potential solution for such problems, significant speedups are achieved just in very specific dataflow oriented software, not representing the reality of nowadays systems. Moreover, its wide spread use is still withheld by the need of special tools and compilers, which clearly preclude software portability and reuse of legacy code. Based on all these facts, this thesis presents a new technique using reconfigurable systems to optimize both control and dataflow oriented software without the need of any modification in the source or binary codes. For that, a Binary Translation algorithm has been developed, which works in parallel to the processor. The proposed mechanism is responsible for transforming sequences of instructions at runtime to be executed on a dynamic coarse-grain reconfigurable array, supporting speculative execution. This way, it is possible to take advantage of using pure combinational logic to speed up the execution, maintaining full binary compatibility in a totally transparent process. Three different case studies were evaluated: a Java Processor and a MIPS R3000 – representing the embedded systems field – and the Simplescalar Toolset, a widely used toolset that simulates a superscalar architecture based on the MIPS R10000 processor – representing the general-purpose market.

Dada a grande diversidade de aplicações embarcadas presentes nos atuais dispositivos portáveis, ambos os paralelismos em nível de threads e de instruções devem ser explorados para obter ganhos de desempenho e energia. Enquanto MPSoCs (sistemas em chip de múltiplos núcleos) são amplamente usados para esse propósito, estes falham quando consideramos produtividade de software, já que eles são compostos de chips com diferentes arquiteturas que precisam ser programados separadamente. Por outro lado, processadores multi núcleos de propósito geral implementam a mesma arquitetura, mas são compostos de núcleos homogêneos de processadores superescalares que consomem muita potência. Nesta dissertação, propõe-se um novo sistema, que tira proveito de circuitos reconfiguráveis para criar diferentes organizações que implementam a mesma arquitetura, capazes de apresentar alto desempenho com baixo custo energético. Para garantir a compatibilidade binária, usa-se um mecanismo de tradução binária que transforma o código a ser executado no circuito reconfigurável durante a execução. Usando aplicações representativas, mostra-se que uma versão do sistema heterogêneo pode ganhar da sua versão homogênea em média de 59% em desempenho e 10% em energia, com melhoras em EDP (Energy-Delay Product – Produto da energia pelo tempo de execução) em quase todos os cenários. Além disso, este trabalho também propõe e avalia seis escalonadores para este sistema heterogêneo: dois algoritmos estáticos, os quais alocam as threads no primeiro núcleo livre, onde elas permanecerão durante toda a execução; um escalonador direcionado por contagem de instruções, o qual realoca as threads durante pontos de sincronização de acordo com a sua contagem de instruções; um escalonador de Feedback, que usa dados de dentro da unidade reconfigurável para realocar threads; o PC-Feedback, que adiciona um mecanismo de reuso de dados ao último escalonador; e um escalonador Oráculo, que é capaz de decidir a melhor alocação de threads possível. Mostra-se que o algoritmo estático pode ter alto desempenho em aplicações com alto paralelismo, contudo para um desempenho mais uniforme em todas as aplicações os algoritmos de Feedback e PC-Feedback são mais indicados. / Given the large diversity of embedded applications one can find in current portable devices, for energy and performance reasons one must exploit both Thread- and Instruction Level Parallelism. While MPSoCs (Multiprocessor system-on-chip) are largely used for this purpose, they fail when one considers software productivity, since it comprises different ISAs (Instruction Set Architecture) that must be programmed separately. On the other hand, general purpose multicores implement the same ISA, but are composed of a homogeneous set of very power consuming superscalar processors. In this dissertation, we show how one can effectively use a reconfigurable unit to provide a number of different possible heterogeneous configurations while still sustaining the same ISA, capable of reaching high performance with low energy cost. To ensure ISA compatibility, we use a binary translation mechanism that transforms code to be executed on the fabric at run-time. Using representative benchmarks, we show that one version of the heterogeneous system can outperform its homogenous counterpart in average by 59% in performance and 10% in energy, with EDP (Energy-Delay Product) improvements in almost every scenario. Furthermore, this work also proposes and evaluates six schedulers for the heterogeneous system: two static algorithms, which allocate the threads on the first free core, where they will run during the entire execution; an Instruction Count (IC) Driven scheduler, which reallocates threads during synchronization points accordingly to their instruction count; a Feedback scheduler, which uses data from inside the reconfigurable unit to reallocate threads; the PCFeedback scheduler, that adds a reuse mechanism to the last one; and an Oracle scheduler, which is capable of deciding the best thread allocation possible. We show that the static algorithm can reach high performance in applications with high parallelism, however for uniform performance in all applications, the Feedback and PC-Feedback algorithms are better designated.