Um algoritmo formal para remoção de redundâncias

• Ano de defesa: 2003
• Autor(a) principal: Marques, Felipe de Souza
• Orientador(a): Reis, Andre Inacio
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Palavras-chave em Português: Microeletrônica; BBDs; Remocao : Redundancias
• Palavras-chave em Inglês: Redundancy removal; False paths; Stuck-at faults; Path delay faults; BDD; VPBDD; Unate functions
• Link de acesso: http://hdl.handle.net/10183/8498

Os algoritmos para síntese de circuitos digitais em geral visam a melhoria de uma função de custo composta de quatro critérios: área, desempenho, potência e testabilidade. Normalmente estes algoritmos conseguem uma relação de compromisso para a otimização de dois critérios. Efeitos indesejáveis também podem surgir com a otimização de um destes critérios. Por exemplo, as otimizações de desempenho podem introduzir falhas de colagem não testáveis (redundâncias) em um circuito, reduzindo a sua testabilidade. Muitos algoritmos de síntese lógica exploram propriedades específicas de determinadas funções a serem sintetizadas. Um exemplo de função com propriedades específicas são as funções ditas unate. Um exemplo deste tipo de função é o sinal de carry de um somador completo. Este tipo de função exige cuidados especiais para evitar a introdução de redundâncias. Muitos dos algoritmos para síntese lógica empregam a decomposição de Shannon para melhorar o desempenho de um circuito. A equação geral da decomposição de Shannon é expressa através de uma função binate. As redundâncias sempre serão introduzidas nos circuitos quando uma equação binate é utilizada para representar uma função unate. Diagramas de Decisão Binária (BDDs) são um tipo estruturas de dados muito utilizadas em algoritmos para síntese lógica. A decomposição de Shannon também é utilizada para derivar circuitos a partir de BDDs. Este tipo de estrutura representa uma função lógica, mas não mantém uma representação sem redundâncias da mesma. Infelizmente, os circuitos derivados a partir desta estrutura poderão ser redundantes, principalmente quando a decomposição de Shannon for utilizada. Existem estruturas de dados capazes de representar uma função sem redundâncias. Este é o caso dos VPBDDs , que possuem propriedades especiais que preservam características de testabilidade da função representada. Baseando-se nas propriedades dos VPBDDs, um novo algoritmo para remoção de redundâncias foi proposto. Este algoritmo é capaz de gerar circuitos sem redundâncias, mesmo quando a função, que é representada pelo VPBDD, é unate. Além da geração de circuitos sem redundâncias, o algoritmo garante que o atraso do circuito não aumenta após a remoção de redundâncias. A área dos circuitos resultantes pode aumentar, diminuir ou permanecer a mesma, considerando o número de portas lógicas utilizadas. Todos os resultados obtidos neste trabalho mostram que o algoritmo consegue realizar a remoção de redundâncias, sem prejudicar o atraso do circuito. Além disso, todos os caminhos redundantes do circuito têm seu atraso reduzido, pois com a remoção de redundâncias o número de portas lógicas em série é reduzido. A aplicação deste algoritmo apresenta bons resultados para circuitos aritméticos. Isto se deve principalmente ao fato do carry ser uma função unate, o que pode introduzir redundâncias no circuito se esta propriedade (de ser unate) não for tratada adequadamente. O algoritmo proposto também abre possibilidades para a criação de outras ferramentas de CAD, como por exemplo: uma ferramenta para análise de timing, um gerador de circuitos aritméticos sem redundâncias, ou ainda uma ferramenta para geração de teste, incluindo lista de falhas, vetores de teste e cobertura de falhas.