Submitted by Irene Nascimento (irene.kessia@ufpe.br) on 2016-07-12T18:32:53Z
No. of bitstreams: 2
license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5)
Tese_Final_bib.pdf: 4325542 bytes, checksum: 5cafa644d256b743ce0f06490e4d5920 (MD5) / Made available in DSpace on 2016-07-12T18:32:53Z (GMT). No. of bitstreams: 2
license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5)
Tese_Final_bib.pdf: 4325542 bytes, checksum: 5cafa644d256b743ce0f06490e4d5920 (MD5)
Previous issue date: 2015-08-20 / Atualmente, a evolução na arquitetura dos FPGAs (Field programable gate
arrays) permite que os mesmos sejam empregados em aplicações que vão desde a
prototipação rápida de circuitos digitais simples a coprocessadores para computação de
alto desempenho. Entretanto, a utilização eficiente dessas arquiteturas é fortemente
dependente, entre outros fatores, da ferramenta de síntese empregada.
O desafio das ferramentas de síntese está em converter a lógica do projetista em
circuitos que utilizem de maneira efetiva a área do chip, não degradem a frequência de
operação e que, sobretudo, sejam eficientes em reduzir o consumo de energia. Nesse
sentido, pesquisadores e grandes fabricantes de FPGA estão, frequentemente,
desenvolvendo novas ferramentas com vistas a esses objetivos, que se caracterizam por
serem conflitantes. O fluxo de síntese de projetos baseados em FPGAs engloba as
etapas de otimização lógica, mapeamento, agrupamento, posicionamento e roteamento.
Essas fases são dependentes, de forma que, otimizações nas etapas iniciais produzem
impactos positivos nas etapas posteriores. No âmbito deste trabalho de doutorado,
estamos propondo uma metodologia para otimização do fluxo de síntese,
especificamente, nas etapas de mapeamento e agrupamento.
Classicamente, a etapa de mapeamento é realizada mediante heurísticas que
determinam uma solução para o problema, mas que, não permitem a busca por soluções
ótimas, ou que beneficiam um objetivo em detrimento de outros. Desta forma, estamos
propondo a utilização de uma abordagem multiobjetivo baseada em algoritmo genético
e de uma abordagem multiobjetivo baseada em colônia artificial de abelhas que,
associadas a heurísticas específicas do problema, permitem que sejam obtidas soluções
de melhor qualidade e que resultam em circuitos finais com área reduzida, ganhos na
frequência de operação e com menor consumo de potência dinâmica.
Além disso, propomos uma nova abordagem de agrupamento multiobjetivo que
se diferencia do estado da arte, por utilizar uma técnica de predição e por considerar
características dinâmicas do problema, produzindo circuitos mais eficientes e que
facilitam a tarefa das etapas de posicionamento e roteamento.
Toda a metodologia proposta foi integrada ao fluxo acadêmico do VTR (Verilog
to routing), um projeto código aberto e colaborativo que conta com múltiplos grupos de
pesquisa, conduzindo trabalhos nas áreas de desenvolvimento de arquitetura de FPGAs
e de novas ferramentas de síntese. Além disso, utilizamos como benchmark, um
conjunto dos 20 maiores circuitos do MCNC (Microelectronics Center of North
Carolina) que são frequentemente utilizados em pesquisas da área.
O resultado do emprego integrado das ferramentas frutos da metodologia
proposta permite a redução de importantes aspectos pós-roteamento avaliados. Em
comparação ao estado da arte, são obtidas, em média, redução na área dos circuitos de
até 19%, além da redução do caminho crítico em até 10%, associada à diminuição na
potência dinâmica total estimada de até 18%.
Os experimentos também mostram que as metodologias de mapeamento
propostas são computacionalmente mais custosas em comparação aos métodos
presentes no estado da arte, podendo ser até 4,7x mais lento. Já a metodologia de
agrupamento apresentou pouco ou nenhum overhead em comparação ao metodo
presente no VTR. Apesar do overhead presente no mapeamento, os métodos propostos,
quando integrados ao fluxo completo, podem reduzir o tempo de execução da síntese
em cerca de 40%, isto é o resultado da produção de circuitos mais simples e que,
consequentemente, favorecem as etapas de posicionamento e roteamento. / Nowadays, the evolution of FPGAs (Field Programmable Gate Arrays) allows
them to be employed in applications from rapid prototyping of digital circuits to
coprocessor of high performance computing. However, the efficient use of these
architectures is heavily dependent, among other factors, on the employed synthesis tool.
The synthesis tools challenge is in converting the designer logic into circuits
using effectively the chip area, while, do not degrade the operating frequency and,
especially, are efficient in reducing power consumption. In this sense, researchers and
major FPGA manufacturers are often developing new tools to achieve those goals,
which are characterized by being conflicting. The synthesis flow of projects based on
FPGAs comprises the steps of logic optimization, mapping, packing, placement and
routing. These steps are dependent, such that, optimizations in the early stages bring
positive results in later steps. As part of this doctoral work, we propose a methodology
for optimizing the synthesis flow, specifically, on the steps of mapping and grouping.
Classically, the mapping step is performed by heuristics which determine a
solution to the problem, but do not allow the search for optimal solutions, or that benefit
a goal at the expense of others. Thus, we propose the use of a multi-objective approach
based on genetic algorithm and a multi-objective approach based on artificial bee
colony that, combined with problem specific heuristics, allows a better quality of
solutions are obtained, yielding circuits with reduced area, operating frequency gains
and lower dynamic power consumption.
In addition, we propose a new multi-objective clustering approach that differs
from the state-of-the-art, by using a prediction technique and by considering dynamic
characteristics of the problem, producing more efficient circuits and that facilitate the
tasks of placement and routing steps .
The proposal methodology was integrated into the VTR (Verilog to routing)
academic flow, an open source and collaborative project that has multiple research
groups, conducting work in the areas of FPGA architecture development and new
synthesis tools. Furthermore, we used a set of the 20 largest MCNC (Microelectronics
Center of North Carolina) benchmark circuits that are often used in research area.
The results of the integrated use of tools based on the proposed methodology
allow the reduction of important post-routing aspects evaluated. Compared to the stateof-
the-art, are achieved, on average, 19% reduction in circuit area, besides 10%
reduction in critical path, associated with 18% decrease in the total dynamic estimated
power.
The experiments also reveal that proposed mapping methods are
computationally more expensive in comparison to methods in the state-of-the-art, and
may even be 4.7x slower. However, the packing methodology presented little or no
overhead compared to the method in VTR. Although the present overhead mapping, the
proposed methods, when integrated into the complete flow, can reduce the running time
of the synthesis by approximately 40%, which is the result of more simple circuits and
which, consequently, favor the steps of placement and routing.
| Identifer | oai:union.ndltd.org:IBICT/oai:repositorio.ufpe.br:123456789/17339 |
| Date | 20 August 2015 |
| Creators | SOUZA, Viviane Lucy Santos de |
| Contributors | http://lattes.cnpq.br/2423716176251719, SILVA FILHO, Abel Guilhermino da |
| Publisher | Universidade Federal de Pernambuco, Programa de Pos Graduacao em Ciencia da Computacao, UFPE, Brasil |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | English |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/doctoralThesis |
| Source | reponame:Repositório Institucional da UFPE, instname:Universidade Federal de Pernambuco, instacron:UFPE |
| Rights | Attribution-NonCommercial-NoDerivs 3.0 Brazil, http://creativecommons.org/licenses/by-nc-nd/3.0/br/, info:eu-repo/semantics/openAccess |
Page generated in 0.0027 seconds