Made available in DSpace on 2014-06-12T15:50:20Z (GMT). No. of bitstreams: 2 arquivo1962_1.pdf: 6205609 bytes, checksum: 86f9f23173b3ed39d6763c36b0c8bda9 (MD5) license.txt: 1748 bytes, checksum: 8a4605be74aa9ea9d79846c1fba20a33 (MD5) Previous issue date: 2008 / Nos últimos anos, assistimos um aumento do interesse pelo uso de FPGAs para aceleração de aplicações que apresentam desempenho limitado em software, devido à complexidade ou grande quantidade de dados a serem processados. Áreas como Processamento Digital de Sinais, Telecomunicações, Processamento de Imagens, Bioinformática e Computação Científica de Alto Desempenho têm tirado proveito desta tecnologia. Este interesse pode ser justificado por diversos fatores: As grandes melhorias introduzidas nos processos de microeletrônica que têm permitido a construção de FPGAs cada vez mais densos, capazes de comportar sistemas muito complexos com milhões de portas lógicas equivalentes. Além disso, estas melhorias têm permitido a construção de dispositivos que podem opera com freqüências de centenas de megahertz, permitindo implementações com altíssimo desempenho. Nos últimos anos, a velocidade dos processadores modernos se estabilizou na casa de 3GHz. Esta estagnação se deve, principalmente, a limitações na capacidade de dissipar o calor gerado em altas freqüências. Com isto, o atendimento das demandas por desempenho deve ser feito por meio da exploração de novas arquiteturas, que visem o paralelismo de tarefas, como são as arquiteturas de CPUs Multi-Cores e FPGAs. As implementações em FPGAs são capazes de realizar mais computação com menos consumo de energia, quando comparados a CPUs convencionais ou Multi-Cores. Isto cria vantagens estratégicas, pelo fato de que o consumo elevado de energia elétrica é um limitador para o aumento da capacidade de processamento em sistemas de alto desempenho, com impacto na viabilidade e custo de instalação, funcionamento e manutenção de sistemas. Sistemas Reconfiguráveis baseados em FPGAs correspondem, atualmente, a uma das arquiteturas alternativas que tem demonstrado bons desempenhos em diversas aplicações experimentais e em um número crescente de casos bem sucedidos de aplicações comerciais. Apesar destas vantagens e da alta capacidade de adaptação às aplicações, com exploração de paralelismo, o grande problema para a popularização do uso destes dispositivos está na dificuldade de programação a partir de descrições em alto nível, como C e C++. Em especial, o particionamento temporal das aplicações consiste em uma etapa fundamental para obtenção de qualidade da implementação. Este trabalho de Tese contribui para a redução da dificuldade de programação dos Sistemas de Computação Reconfiguráveis (SCR), propondo uma Metodologia de Particionamento Temporal que considera o reuso de componentes IP-Cores, escolhidos a partir de várias opções disponíveis em uma biblioteca de componentes, de forma a otimizar a utilização dos recursos do FPGA. Esta metodologia explora diversas possibilidades de implementação para as tarefas em hardware e diversos agrupamentos de tarefas em partições temporais. No melhor do nosso conhecimento, apenas dois métodos foram propostos na literatura, por Vemuri e Ouni, que tentam resolver os problemas de mapeamento de aplicação que são abordados. Entretanto, os resultados experimentais, descritos nesta Tese, demonstram as vantagens da nossa proposta. Além disso, a metodologia apresentada é a primeira, que tem-se notícia, que utiliza o método de busca Tabu Search para realização do particionamento temporal, integrado à escolha de componentes, a partir de uma biblioteca de IP-Cores

Submitted by Nayara Passos (nayara.passos@ufpe.br) on 2015-03-11T18:35:40Z No. of bitstreams: 2 TESE Bruno Otavio Piedade Prado.pdf: 9246891 bytes, checksum: c2ec036981695fc08a08b2eea1294846 (MD5) license_rdf: 1370 bytes, checksum: bd343fdf8e4779e91782baad59c34539 (MD5) / Made available in DSpace on 2015-03-11T18:35:40Z (GMT). No. of bitstreams: 2 TESE Bruno Otavio Piedade Prado.pdf: 9246891 bytes, checksum: c2ec036981695fc08a08b2eea1294846 (MD5) license_rdf: 1370 bytes, checksum: bd343fdf8e4779e91782baad59c34539 (MD5) Previous issue date: 2014 / Com os grandes avanços recentes dos sistemas computacionais, houve a possibilidade de ascensão de dispositivos inovadores, como os modernos telefones celulares e tablets com telas sensíveis ao toque. Para gerenciar adequadamente estas diversas interfaces é necessário utilizar o software dependente do hardware (HdS), que é responsável pelo controle e acesso a estes dispositivos. Além deste complexo arranjo de componentes, para atender a crescente demanda por mais funcionalidades integradas, o paradigma de multiprocessamento vem sendo adotado para aumentar o desempenho das plataformas. Devido à lacuna de produtividade de sistemas, tanto a indústria como a academia têm pesquisado processos mais eficientes para construir e simular sistemas cada vez mais complexos. A premissa dos trabalhos do estado da arte está em trabalhar com modelos com alto nível de abstração e de precisão que permitam ao projetista avaliar rapidamente o sistema, sem ter que depender de lentos e complexos modelos baseados em ISS. Neste trabalho é definido um conjunto de construtores para modelagem de plataformas baseadas em processadores, com suporte para desenvolvimento de HdS e reusabilidade dos componentes, técnicas para estimativa estática de tempo simulado em ambiente nativo de simulação e suporte para plataformas multiprocessadas. Foram realizados experimentos com aplicações de entrada e saída intensiva, computação intensiva e multiprocessada, com ganho médio de desempenho da ordem de 1.000 vezes e precisão de estimativas com erro médio inferior a 3%, em comparação com uma plataforma de referência baseada em ISS.

The increasing demand for energy efficient computing has endorsed the usage of Field-Programmable Gate Arrays to create hardware accelerators for large and complex codes. However, implementing such accelerators involve two complex decisions. The first one lies in deciding which code snippet is the best to create an accelerator, and the second one lies in how to implement the accelerator. When considering both decisions concomitantly, the problem becomes more complicated since the code snippet implementation affects the code snippet choice, creating a combined design space to be explored. As such, a fast design space exploration for the accelerators implementation is crucial to allow the exploration of different code snippets. However, such design space exploration suffers from several time-consuming tasks during the compilation and evaluation steps, making it not a viable option to the snippets exploration. In this work, we focus on the efficient implementation of pipelined hardware accelerators and present our contributions on speeding up the pipelines creation and their design space exploration. Towards loop pipelining, the proposed approaches achieve up to 100× speed-up when compared to the state-uf-the-art methods, leading to 164 hours saving in a full design space exploration with less than 1% impact in the final results quality. Towards design space exploration, the proposed methods achieve up to 9:5× speed-up, keeping less than 1% impact in the results quality. / A demanda crescente por computação energeticamente eficiente tem endossado o uso de Field- Programmable Gate Arrays para a criação de aceleradores de hardware para códigos grandes e complexos. Entretanto, a implementação de tais aceleradores envolve duas decisões complexas. O primeiro reside em decidir qual trecho de código é o melhor para se criar o acelerador, e o segundo reside em como implementar tal acelerador. Quando ambas decisões são consideradas concomitantemente, o problema se torna ainda mais complicado dado que a implementação do trecho de código afeta a seleção dos trechos de código, criando um espaço de projeto combinatorial a ser explorado. Dessa forma, uma exploração do espaço de projeto rápida para a implementação de aceleradores é crucial para habilitar a exploração de diferentes trechos de código. Contudo, tal exploração do espaço de projeto é impedida por várias tarefas que consumem tempo durante os passos de compilação a análise, o que faz da exploração de trechos de códigos inviável. Neste trabalho, focamos na implementação eficiente de aceleradores pipeline em hardware e apresentamos nossas contribuições para o aceleramento da criações de pipelines e de sua exploração do espaço de projeto. Referente à criação de pipelines, as abordagens propostas alcançam uma aceleração de até 100× quando comparadas às abordagens do estado-da-arte, levando à economia de 164 horas em uma exploração de espaço de projeto completa com menos de 1% de impacto na qualidade dos resultados. Referente à exploração do espaço de projeto, as abordagens propostas alcançam uma aceleração de até 9:5×, mantendo menos de 1% de impacto na qualidade dos resultados.

Devido ao grande número de otimizações fornecidas pelos compiladores modernos e à ampla possibilidade de ordenação dessas transformações, uma eficiente Exploração do Espaço de Projeto (DSE) se faz necessária para procurar a melhor sequência de otimização de uma determinada função ou fragmento de código. Como esta exploração é uma tarefa complexa e dispendiosa, apresentamos uma nova abordagem de DSE capaz de reduzir esse tempo de exploração e selecionar sequências de otimização que melhoraram o desempenho dos códigos transformados. Nossa abordagem utiliza um conjunto de funções de referência, para as quais uma representação simbólica do código (DNA) e a melhor sequência de otimização são conhecidas. O DSE de novas funções é baseado em uma abordagem de agrupamento aplicado sobre o código DNA que identifica similaridades entre funções. O agrupamento utiliza três técnicas para a mineração de dados: distância de compressão normalizada, algoritmo de reconstrução de árvores filogenéticas (Neighbor Joining) e identificação de grupos por ambiguidade. As otimizações das funções de referência identificadas como similares formam o espaço que é explorado para encontrar a melhor sequência para a nova função. O DSE pode utilizar o conjunto reduzido de otimizações de duas formas: como o espaço de projeto ou como a configuração inicial do algoritmo. Em ambos os casos, a adoção de uma pré-seleção baseada no agrupamento permite o uso de algoritmos de busca simples e rápidos. Os resultados experimentais revelam que a nova abordagem resulta numa redução significativa no tempo total de exploração, ao mesmo tempo que alcança um desempenho próximo ao obtido através de uma busca mais extensa e dispendiosa baseada em algoritmos genéticos. / Due to the large number of optimizations provided in modern compilers and to compiler optimization specific opportunities, a Design Space Exploration (DSE) is necessary to search for the best sequence of compiler optimizations for a given code fragment (e.g., function). As this exploration is a complex and time consuming task, we present new DSE strategies to reduce the exploration time and still select optimization sequences able to improve the performance of each function. The DSE is based on a clustering approach which groups functions with similarities and then explore the reduced search space provided by the optimizations previously suggested for the functions in each group. The identification of similarities between functions uses a data mining method which is applied to a symbolic representation of the source code. The DSE strategies uses the reduced optimizations set identified by clustering in two ways: as the design space or as the initial configuration of the algorithm. In both ways, the adoption of a pre-selection based on clustering allows the use of simple and fast DSE algorithms. Several experiments for evaluating the effectiveness of the proposed approach address the exploration of compiler optimization sequences. Besides, we investigate the impact of each technique or component employed in the selection process. Experimental results reveal that the use of our new clustering-based DSE approach achieved a significant reduction on the total exploration time of the search space at the same time that obtained performance speedups close to a traditional genetic algorithmbased approach.

Com os grandes avanços recentes dos sistemas computacionais, houve a possibilidade de ascensão de dispositivos inovadores, como os modernos telefones celulares e tablets com telas sensíveis ao toque. Para gerenciar adequadamente estas diversas interfaces é necessário utilizar o software dependente do hardware (HdS), que é responsável pelo controle e acesso a estes dispositivos. Além deste complexo arranjo de componentes, para atender a crescente demanda por mais funcionalidades integradas, o paradigma de multiprocessamento vem sendo adotado para aumentar o desempenho das plataformas. Devido à lacuna de produtividade de sistemas, tanto a indústria como a academia têm pesquisado processos mais eficientes para construir e simular sistemas cada vez mais complexos. A premissa dos trabalhos do estado da arte está em trabalhar com modelos com alto nível de abstração e de precisão que permitam ao projetista avaliar rapidamente o sistema, sem ter que depender de lentos e complexos modelos baseados em ISS. Neste trabalho é definido um conjunto de construtores para modelagem de plataformas baseadas em processadores, com suporte para desenvolvimento de HdS e reusabilidade dos componentes, técnicas para estimativa estática de tempo simulado em ambiente nativo de simulação e suporte para plataformas multiprocessadas. Foram realizados experimentos com aplica- ções de entrada e saída intensiva, computação intensiva e multiprocessada, com ganho médio de desempenho da ordem de 1.000 vezes e precisão de estimativas com erro médio inferior a 3%, em comparação com uma plataforma de referência baseada em ISS._________________________________________________________________________________________ ABSTRACT: The amazing advances of computer systems technology enabled the rise of innovative devices, such as modern touch sensitive cell phones and tablets. To properly manage these various interfaces, it is required the use of the Hardwaredependent Software (HdS) that is responsible for these devices control and access. Besides this complex arrangement of components, to meet the growing demand for more integrated features, the multiprocessing paradigm has been adopted to increase the platforms performance. Due to the system design gap, both industry and academia have been researching for more efficient processes to build and simulate systems with this increasingly complexity. The premise of the state of art works is the development of high level of abstraction and precise models to enable the designer to quickly evaluate the system, without having to rely on slow and complex models based on instruction set simulators (ISS). This work defined a set of constructors for processor-based platforms modeling, supporting HdS development and components reusability, techniques for static simulation timing estimation in native environment and support for multiprocessor platforms. Experiments were carried out with input and output intensive, compute intensive and multiprocessed applications leading to an average performance speed up of about 1,000 times and average timing estimation accuracy of less than 3%, when compared with a reference platform based on ISS.

Devido ao grande número de otimizações fornecidas pelos compiladores modernos e à ampla possibilidade de ordenação dessas transformações, uma eficiente Exploração do Espaço de Projeto (DSE) se faz necessária para procurar a melhor sequência de otimização de uma determinada função ou fragmento de código. Como esta exploração é uma tarefa complexa e dispendiosa, apresentamos uma nova abordagem de DSE capaz de reduzir esse tempo de exploração e selecionar sequências de otimização que melhoraram o desempenho dos códigos transformados. Nossa abordagem utiliza um conjunto de funções de referência, para as quais uma representação simbólica do código (DNA) e a melhor sequência de otimização são conhecidas. O DSE de novas funções é baseado em uma abordagem de agrupamento aplicado sobre o código DNA que identifica similaridades entre funções. O agrupamento utiliza três técnicas para a mineração de dados: distância de compressão normalizada, algoritmo de reconstrução de árvores filogenéticas (Neighbor Joining) e identificação de grupos por ambiguidade. As otimizações das funções de referência identificadas como similares formam o espaço que é explorado para encontrar a melhor sequência para a nova função. O DSE pode utilizar o conjunto reduzido de otimizações de duas formas: como o espaço de projeto ou como a configuração inicial do algoritmo. Em ambos os casos, a adoção de uma pré-seleção baseada no agrupamento permite o uso de algoritmos de busca simples e rápidos. Os resultados experimentais revelam que a nova abordagem resulta numa redução significativa no tempo total de exploração, ao mesmo tempo que alcança um desempenho próximo ao obtido através de uma busca mais extensa e dispendiosa baseada em algoritmos genéticos. / Due to the large number of optimizations provided in modern compilers and to compiler optimization specific opportunities, a Design Space Exploration (DSE) is necessary to search for the best sequence of compiler optimizations for a given code fragment (e.g., function). As this exploration is a complex and time consuming task, we present new DSE strategies to reduce the exploration time and still select optimization sequences able to improve the performance of each function. The DSE is based on a clustering approach which groups functions with similarities and then explore the reduced search space provided by the optimizations previously suggested for the functions in each group. The identification of similarities between functions uses a data mining method which is applied to a symbolic representation of the source code. The DSE strategies uses the reduced optimizations set identified by clustering in two ways: as the design space or as the initial configuration of the algorithm. In both ways, the adoption of a pre-selection based on clustering allows the use of simple and fast DSE algorithms. Several experiments for evaluating the effectiveness of the proposed approach address the exploration of compiler optimization sequences. Besides, we investigate the impact of each technique or component employed in the selection process. Experimental results reveal that the use of our new clustering-based DSE approach achieved a significant reduction on the total exploration time of the search space at the same time that obtained performance speedups close to a traditional genetic algorithmbased approach.