Use este identificador para citar ou linkar para este item: https://locus.ufv.br//handle/123456789/2662
Registro completo de metadados
Campo DCValorIdioma
dc.contributor.authorCardoso, Luciana Rocha
dc.date.accessioned2015-03-26T13:10:38Z-
dc.date.available2014-07-22
dc.date.available2015-03-26T13:10:38Z-
dc.date.issued2013-07-24
dc.identifier.citationCARDOSO, Luciana Rocha. Positioning Polynominal Algorithm for FPGA based-Crossing Graphs. 2013. 86 f. Dissertação (Mestrado em Metodologias e técnicas da Computação; Sistemas de Computação) - Universidade Federal de Viçosa, Viçosa, 2013.por
dc.identifier.urihttp://locus.ufv.br/handle/123456789/2662-
dc.description.abstractO hardware reconfigurável é uma solução intermediária entre software e hardware, oferece a flexibilidade do software e o desempenho do hardware. Nos anos oitenta, os FPGAs surgiram como circuitos reconfiguráveis comerciais e escaláveis. Possuem muita flexibilidade e resolveram com sucesso vários problemas nas últimas décadas com uma aceleração de 2 a 3 ordens de grandeza em relação à versão em software. Além disso, as aplicações são heterogêneas e demandam soluções que se adaptem em tempo de execução. Com a evolução da tecnologia, a complexidade do FPGA aumentou significativamente passando de centenas de blocos lógicos/interconexões para a ordem de milhões. Este avanço possibilita mais desempenho e flexibilidade, entretanto a complexidade para mapear as aplicações aumenta significativamente. Sendo que para soluções geradas em tempo de execução, o tempo para mapear as aplicações é mais crítico. O mapeamento é realizado em dois passos: posicionamento e roteamento. O problema de encontrar a melhor maneira de posicionar uma computação nos blocos lógicos (posicionamento) é NP-Completo. Uma vez posicionados, os blocos devem ser interligados (roteamento) que também é um problema NP-completo. Ambos os problemas são grandes desafios atuais para as ferramentas de FPGA. Esta dissertação tem foco no problema de posicionamento. Várias heurísticas já foram propostas ao longo das três últimas décadas, porém poucas apresentaram um desempenho adequado para posicionar e rotear blocos lógicos em tempo de execução. Este trabalho propõe uma exploração do espaço de projeto de um algoritmo polinomial de posicionamento baseado em travessia em grafos. Variações de travessia (largura e profundidade) são propostas e a qualidade da solução é avaliada medindo o tempo de execução, o caminho crítico e o número total de conexões. As variações tem foco nos pontos com múltiplos fanout e fanouts reconvergentes.pt_BR
dc.description.abstractNowadays, many applications requires high performance solutions, which could not be achieved by a software approach. Problems in bioinformatics, simulations, telecommunications, encryption, compression of large volumes of data are examples of these applications. A hardware approaches are high-performance, however, these approaches have high design costs. The reconfigurable hardware is an intermediate solution between software and hardware, as it offers the flexibility of the software and the performance of the hardware. Since 1980s, FPGA circuits have emerged as commercial and scalable platform for reconfigurable hardware. Several problems have been modeled and implemented by using FPGA with acceleration from 2 to 3 orders of magnitude. However, the FPGA complexity has significantly increased from hundreds of logical blocks/interconnections to the order of millions in last decades. First, the application should be mapped to the FPGA. The mapping consists on two steps: placement and routing. The placement will map the computing elements in logic blocks. This step is NP-Complete. Then, the routing step will perform the interconnections between the logic blocks. It is also a NP-complete problem. Both problems are one of current challenges in FPGA tools. Several heuristics have been proposed, but few of them are suitable for run-time approach. This dissertation proposes an exploration of the design space of a polynomial algorithm based on graph traversal. Depth-first and Breadth-first traversals are evaluated by looking the reconvergent fanout and high fanout nodes. Experimental results analyze the execution time, critical path, distribution degree and total wire length.eng
dc.description.sponsorship
dc.formatapplication/pdfpor
dc.languageporpor
dc.publisherUniversidade Federal de Viçosapor
dc.rightsAcesso Abertopor
dc.subjectFPGApor
dc.subjectPosicionamentopor
dc.subjectTempo de execuçãopor
dc.subjectFPGAeng
dc.subjectPositioningeng
dc.subjectExecution timeeng
dc.titleAlgoritmo de Posicionamento Polinomial para FPGA Baseado em Travessia de Grafospor
dc.title.alternativePositioning Polynominal Algorithm for FPGA based-Crossing Graphseng
dc.typeDissertaçãopor
dc.contributor.authorLatteshttp://lattes.cnpq.br/4768818191466551por
dc.contributor.advisor-co1Santos, André Gustavo dos
dc.contributor.advisor-co1Latteshttp://buscatextual.cnpq.br/buscatextual/visualizacv.do?id=K4796253Z5por
dc.publisher.countryBRpor
dc.publisher.departmentMetodologias e técnicas da Computação; Sistemas de Computaçãopor
dc.publisher.programMestrado em Ciência da Computaçãopor
dc.publisher.initialsUFVpor
dc.subject.cnpqCNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAOpor
dc.contributor.advisor1Ferreira, Ricardo dos Santos
dc.contributor.advisor1Latteshttp://buscatextual.cnpq.br/buscatextual/visualizacv.do?id=K4723626E5por
dc.contributor.referee1Nacif, José Augusto Miranda
dc.contributor.referee1Latteshttp://lattes.cnpq.br/1946315322575953por
Aparece nas coleções:Ciência da Computação

Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
texto completo.pdf2,83 MBAdobe PDFThumbnail
Visualizar/Abrir


Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.