Dissertação de Mestrado:
Síntese Evolucionária de Circuitos Seqüenciais Inspirada na Computação Quântica
Marcos Paulo Mello Araujo
- PEL
- Orientador
Profa. Nadia Nedjah , Ph.D., 1997, UMIST, Grã-Bretanha - k- Coorientador
Profa. Luiza De Macedo Mourelle , Ph.D., 1998, UMIST, Grã-Bretanha - k- Banca
* Profa. Nadia Nedjah , Ph.D., 1997, UMIST, Grã-Bretanha - k
* Profa. Luiza De Macedo Mourelle , Ph.D., 1998, UMIST, Grã-Bretanha - k
* Profa. Marley Maria B.R.Vellasco , Ph.D em Ciência da Computação, University College London, Inglaterra, 1992. - k
* Prof.Dr.Leandro dos Santos Coelho - PUC-PR
- Data - hora da defesa
- 04/12/2008
- Resumo
- Esta disserta¸c˜ao investiga a aplica¸c˜ao dos algoritmos evolucion´arios inspirados na computa¸c˜ao quˆantica na s´ıntese de circuitos sequenciais. Os sistemas digitais seq ¨ uenciais represen- ¨
tam uma classe de circuitos que ´e capaz de executar opera¸c˜oes em uma determinada sequˆencia. ¨
Nos circuitos sequenciais, os valores dos sinais de sa´ıda dependem n˜ao s´o d ¨ os valores dos sinais
de entrada como tamb´em do estado atual do sistema. Os requisitos cada vez mais exigentes
quanto `a funcionalidade e ao desempenho dos sistemas digitais exigem projetos cada vez mais
eficientes. O projeto destes circuitos, quando executado de forma manual, se tornou demorado
e, com isso, a importˆancia das ferramentas para a s´ıntese autom´atica de circuitos cresceu rapidamente. Estas ferramentas conhecidas como ECAD (Electronic Computer-Aided Design) s˜ao
programas de computador normalmente baseados em heur´ısticas. Recentemente, os algoritmos
evolucion´arios tamb´em come¸caram a ser utilizados como base para as ferramentas ECAD. Estas aplica¸c˜oes s˜ao referenciadas na literatura como eletrˆonica evolucion´aria. Os algoritmos mais
comumente utilizados na eletrˆonica evolucion´aria s˜ao os algoritmos gen´eticos e a programa¸c˜ao
gen´etica. Este trabalho apresenta um estudo da aplica¸c˜ao dos algoritmos evolucion´arios inspirados na computa¸c˜ao quˆantica como uma ferramenta para a s´ıntese autom´atica de circuitos
sequenciais. Esta classe de algoritmos utiliza os princ´ıpios ¨ da computa¸c˜ao quˆantica para melhorar o desempenho dos algoritmos evolucion´arios. Tradicionalmente, o projeto dos circuitos
sequenciais ´e dividido em cinco etapas principais: ¨ (i) Especifica¸c˜ao da m´aquina de estados;
(ii) Redu¸c˜ao de estados; (iii) Atribui¸c˜ao de estados; (iv) S´ıntese da l´ogica de controle e (v)
Implementa¸c˜ao da m´aquina de estados. O Algoritmo Evolucion´ario Inspirado na Computa¸c˜ao
Quˆantica (AEICQ) proposto neste trabalho ´e utilizado na etapa de atribui¸c˜ao de estados. A
escolha de uma atribui¸c˜ao de estados ´otima ´e tratada na literatura como um problema ainda
sem solu¸c˜ao. A atribui¸c˜ao de estados escolhida para uma determinada m´aquina de estados
tem um impacto direto na complexidade da sua l´ogica de controle. Os resultados mostram que
as atribui¸c˜oes de estados obtidas pelo AEICQ de fato conduzem `a implementa¸c˜ao de circuitos
de menor complexidade quando comparados com os circuitos gerados a partir de atribui¸c˜oes
obtidas por outros m´etodos. O AEICQ ´e utilizado tamb´em na etapa de s´ıntese da l´ogica de
controle das m´aquinas de estados. Os circuitos evolu´ıdos pelo AEICQ s˜ao otimizados segundo
a ´area ocupada e o atraso de propaga¸c˜ao. Estes circuitos s˜ao compat´ıveis com os circuitos
obtidos por outros m´etodos e em alguns casos at´e mesmo superior em termos de ´area e de
desempenho, sugerindo que existe um potencial de aplica¸c˜ao desta classe de algoritmos no
projeto de circuitos eletrˆonicos.
Palavras-chave: computa¸c˜ao quˆantica, computa¸c˜ao evolucion´aria, sistemas digitais, sistemas
sequenciais, m´aquina de estados, atribui¸c˜ao de estados, el ¨ etrˆonica evolucion´aria.