A GRAPH PARTITIONING HEURISTIC FOR THE PARALLEL PSEUDO-EXHAUSTIVE LOGICAL TEST OF VLSI COMBINATIONAL CIRCUITS / UMA HEURÍSTICA DE PARTICIONAMENTO DE GRAFOS PARA O TESTE LÓGICO PSEUDO-EXAUSTIVO EM PARALELO DE CIRCUITOS COMBINACIONAIS VLSI
AUTOR(ES)
ALEXANDRE ALBINO ANDREATTA
DATA DE PUBLICAÇÃO
1994
RESUMO
O teste lógico de circuitos integrados VLSI é parte indispensável de sua fabricação e projeto. O enfoque pseudo-exaustivo para o teste lógico de circuitos integrados consiste em particionar o circuito original a ser testado em subcircuitos com um reduzido número de entradas, que são então testados em paralelo de forma exaustiva. Neste trabalho apresenta-se um algoritmo aproximado para o problema de particionamento de circuitos integrados combinacionais, baseado na metaheurística de busca tabu. O algoritmo proposto apresenta diversas características originais, tais como: o conceito de vizinhança reduzida, obtida por movimentos envolvendo apenas um subconjunto de nós de fronteira; movimentos complexos que induzem diversos movimentos resultantes, embora as variações na função de custo sejam facilmente calculáveis; uma função objetivo bi-critério combinando o número de circuitos e o número de cortes, que simultaneamente adiciona uma estratégia de diversificação à busca; e o uso de uma heurística de empacotamento como passo de pós-otimização. O desempenho do algoritmo proposto foi avaliado através de sua aplicação a um conjunto de circuitos computacionais ISCAS padronizados. Os resultados computacionais foram comparados com aqueles fornecidos pelos algoritmos conhecidos na literatura, obtendo-se melhorias significativas. As taxas de médias de redução foram da ordem de 30% para o número de subcircuitos na partição e de 40% para o número de cortes.
