[en] A GRAPH PARTITIONING HEURISTIC FOR THE PARALLEL PSEUDO-EXHAUSTIVE LOGICAL TEST OF VLSI COMBINATIONAL CIRCUITS

• Ano de defesa: 2009
• Autor(a) principal: ALEXANDRE ALBINO ANDREATTA
• Tipo de documento: Tese
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: MAXWELL
• Palavras-chave em Português: [pt] BUSCA TABU; [pt] TESTE LOGICO; [pt] CIRCUITOS INTEGRADOS; [en] TABU SEARCH
• Link de acesso: https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=14096&idi=1; https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=14096&idi=2; http://doi.org/10.17771/PUCRio.acad.14096

[pt] 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.