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.

Download do Trabalho