Made available in DSpace on 2014-06-12T15:58:27Z (GMT). No. of bitstreams: 2 arquivo4484_1.pdf: 6966497 bytes, checksum: 24a281b3de8ed514a81a117af5c76238 (MD5) license.txt: 1748 bytes, checksum: 8a4605be74aa9ea9d79846c1fba20a33 (MD5) Previous issue date: 2004 / A maioria dos sistemas electrônicos modernos consiste em hardware dedicado e componentes programáveis (chamados componentes de software). Ao longo dos últimos anos, o número de metodologias que aplicaram simultaneamente técnicas de diferentes áreas para desenvolver sistemas mistos de hardware e software tem crescido consideravelmente. Projetos concorrentes de sistemas mistos de hardware/software têm mostrado ser vantajoso quando considerado como um todo ao invés de se considerar entidades independentes. Hoje em dia, o mercado eletrônico demanda sistemas de alto desempenho e de baixo custo. Estes requisitos são essenciais para a competitividade de mercado. Além disso, um curto time-to-market é um fator importante. A demora no lançamento do produto causa sérias reduções no lucro, desde que é mais simples vender um produto quando se tem pouca ou nenhuma competição. Isto significa que facilitando o re-uso de projetos anteriores, uma rápida exploração de projeto, análise/verificação qualitativa em fases iniciais do projeto, prototipação e a redução do tempo requerido para testes, reduzem o tempo global exigido de uma especificação até o produto final. Ao projetar tais sistemas mistos de hardware/software, a análise de alternativas de projeto e a decisão de onde implementar cada parte de sistema, isto é, em hardware ou em software, são tarefas muito importantes. A estimativa de métricas de qualidade permite a exploração do espaço de projeto e pode guiar a decisão de implementação de partes do sistema. Tais métricas são calculadas no nível de sistema, ou seja, sem implementação real. Conseqüentemente, tais estimativas também aceleraram o projeto do sistema e permitem a análise de restrições de projeto, fornecendo uma retroalimetação para decisões de projeto. As redes de Petri são técnicas de especificação formal que permitem uma representação gráfica e matemática. Têm métodos poderosos que permitem aos projetistas realizar análises qualitativa e quantitativa. Redes de Petri Timed, são extensões de redes de Petri nas quais as informações de tempo são expressas por duração (rede com tempo determinístico, política de disparo em três fases) e são associadas às transições. Para uma descrição comportamental de alto nível, o projeto de hardware é dividido em classes de blocos funcionais: caminho de dados e controladores. O caminho de dados consiste em três tipos de componentes RT: unidades de armazenamento (registradores e latches), unidades funcionais (ALUS e comparadores), e unidades de interconexão (multiplexadores e barramentos). As unidades de armazenamento são requeridas para armazenar valores de dados como constantes, variáveis e vetores no comportamento. As unidades funcionais são necessárias para implementar as operações no comportamento. Após todas as variáveis e operações no comportamento terem sido mapeadas às unidades de armazenamento e funcionais, respectivamente, podemos estimar o número de unidades de interconexão, como os barramentos e multiplexadores, os quais são requeridos para interligar as unidades de armazenamento e funcionais. Este trabalho propõe uma abordagem para estimar a área de hardware a partir do número de unidades de armazenamento, funcionais e de interconexão, levando-se em consideração restrições de tempo e dependência de dados, e estende alguns trabalhos anteriores com o objetivo de melhorar a precisão dos métodos de estimativa de área. Isto é, o método proposto considera uma rede de fluxo de dados que captura dependência de dados e calcula a área do caminho de dados a partir do número e tipo dos seus componentes, considerando a relação de dependência temporal

Dans cette thèse , nous proposons d’étudier des questions sur le parallélism de tâcheavec dépendance de données dans le cadre de machines multicoeur avec des accélérateurs.La solution proposée a été développée en utilisant l’interface de programmation hauteniveau XKaapi du projet MOAIS de l’INRIA Rhône-Alpes.D’abord nous avons étudié des questions liés à une approche d’exécution totalementasyncrone et l’ordonnancement par vol de travail sur des architectures multi-GPU. Le volde travail avec localité de données a montré des résultats significatifs, mais il ne prend pasen compte des différents ressources de calcul. Ensuite nous avons conçu une interface etune modèle de coût qui permettent d’écrire des politiques d’ordonnancement sur XKaapi.Finalement on a évalué XKaapi sur un coprocesseur Intel Xeon Phi en mode natif.Notre conclusion est double. D’abord nous avons montré que le modèle de programma-tion data-flow peut être efficace sur des accélérateurs tels que des GPUs ou des coproces-seurs Intel Xeon Phi. Ensuite, le support à des différents politiques d’ordonnancement estindispensable. Les modèles de coût permettent d’obtenir de performance significatifs surdes calculs très réguliers, tandis que le vol de travail permet de redistribuer la charge encours d’exécution. / In this thesis, we propose to study the issues of task parallelism with data dependencies onmulticore architectures with accelerators. We target those architectures with the XKaapiruntime system developed by the MOAIS team (INRIA Rhône-Alpes).We first studied the issues on multi-GPU architectures for asynchronous execution andscheduling. Work stealing with heuristics showed significant performance results, but didnot consider the computing power of different resources. Next, we designed a schedulingframework and a performance model to support scheduling strategies over XKaapi runtime.Finally, we performed experimental evaluations over the Intel Xeon Phi coprocessor innative execution.Our conclusion is twofold. First we concluded that data-flow task programming canbe efficient on accelerators, which may be GPUs or Intel Xeon Phi coprocessors. Second,the runtime support of different scheduling strategies is essential. Cost models providesignificant performance results over very regular computations, while work stealing canreact to imbalances at runtime. / Esta tese investiga os desafios no uso de paralelismo de tarefas com dependências dedados em arquiteturas multi-CPU com aceleradores. Para tanto, o XKaapi, desenvolvidono grupo de pesquisa MOAIS (INRIA Rhône-Alpes), é a ferramenta de programação basedeste trabalho.Em um primeiro momento, este trabalho propôs extensões ao XKaapi a fim de sobre-por transferência de dados com execução através de operações concorrentes em GPU, emconjunto com escalonamento por roubo de tarefas em multi-GPU. Os resultados experimen-tais sugerem que o suporte a asincronismo é importante à escalabilidade e desempenho emmulti-GPU. Apesar da localidade de dados, o roubo de tarefas não pondera a capacidadede processamento das unidades de processamento disponíveis. Nós estudamos estratégiasde escalonamento com predição de desempenho em tempo de execução através de modelosde custo de execução. Desenvolveu-se um framework sobre o XKaapi de escalonamentoque proporciona a implementação de diferentes algoritmos de escalonamento. Esta tesetambém avaliou o XKaapi em coprocessodores Intel Xeon Phi para execução nativa.A conclusão desta tese é dupla. Primeiramente, nós concluímos que um modelo deprogramação com dependências de dados pode ser eficiente em aceleradores, tais comoGPUs e coprocessadores Intel Xeon Phi. Não obstante, uma ferramenta de programaçãocom suporte a diferentes estratégias de escalonamento é essencial. Modelos de custo podemser usados no contexto de algoritmos paralelos regulares, enquanto que o roubo de tarefaspoder reagir a desbalanceamentos em tempo de execução.