Análise da performance do algoritmo d

Abstract

A geração de testes para circuitos combinacionais com fan-outs recovergentes é um problema NP-completo. Com o rápido crescimento da complexidade dos circuitos fabricados, a geração de testes passou a ser um sério problema para a indústria de circuitos integrados. Muitos algoritmos de ATPG (Automatic Test Pattern Generation) baseados no algoritmo D, usam heurísticas para guiar o processo de tomada de decisão na propagação n e na justificação das constantes de forma a aumentar sua eficiencia. Existem heurísticas baseadas em medidas funcionais, estruturais e probabilísticas. Estas medidas são normalmente referidas como observabilidade e controlabilidade que fazem parte de um conceito mais geral, a testabilidade. As medidas que o algoritmo utiliza podem ser calculadas apenas uma vez, durante uma etapa de pré-processamento (medidas de testabilidade estáticas - STM's), ou dinamicamente, recalculando estas medidas durante o processamento sempre que elas forem necessárias (medidas de testabilidade dinâmicas — DTM's). Para alguns circuitos, o use de medidas dinâmicas ao invés de medidas estáticas diminui o número de backtrackings pcir vetor gerado. Apesar disto, o tempo total de CPU por vetor aumenta. Assim, as DTM's só devem ser utilizadas quando as STM's não apresentam uma boa performance. Isto pode ser feito utilizando-se as medidas estáticas ate um certo número de backtrackings. Se o padrão de teste não for encontrado, então medidas dinâmicas são utilizadas. Entretanto, a necessário ainda buscar formas de melhorar o processo dinâmico, diminuindo o custo computacional. A proposta original do calculo das DTM's apresenta algumas técnicas, baseadas em selective tracing, com o objetivo de reduzir o custo computacional. Este trabalho analisa o use combinado de heurísticas e propõe técnicas alternativas, na forma das heurísticas de recalculo parcial e recalculo de linhas não free, que visam minimizar o overhead do calculo das DTM's. E proposta ainda a técnica de Pré-implicação que transfere a complexidade do algoritmo para a memória. Isto é feito através de um preprocessamento que armazena informações necessárias para a geração de todos os vetores de teste. De outra forma estas informações teriam de ser calculadas na geração de cada um destes vetores. A implementação do algoritmo D com as várias heurísticas permitiu a realização de um experimento pratico. Isto possibilitou a análise quantitativa da performance do algoritmo D para vários tipos de circuitos e demonstrou a eficiência de uma das heurísticas propostas neste trabalho.

The test generation for combinational circuits that contain reconvergence is a NP-complete problem. With the rapid increase in the complexity of the fabricated circuits, the generation of test patterns poses a serious problem to the IC industry. A number of existing ATPG algorithms based on the D algorithm use heuristics to guide the decision process in the D-propagation and justification to improve the efficiency. The heuristics used by ATPG algorithm are based on structural, functional and probabilistics measures. These measures are commonly referred to as line controllability and observability and they are combined under the , more general notion of testability. The measures used by ATPG algorithms can be computed only once, during a preprocessing stage (static testability measures - STM's) or can be calculated dinamically, updating the testability measures during the test generation process (dymanic testability measures - DTM's). For some circuits, replacing STM's by DTM's decreases the average number of backtrackings per generated vector. Despite these decrease, the total CPU time per generated vector is greater when using DTM's instead of STM's. So, DTM's only must be used if the STM's don't present a good performance. This can be done by STM's until a certain number of backtrackings. If a test pattern has still not been found, then DTM's are used. Therefore, it is yet necessary to search for ways to improve the dynamic process and decrease the CPU time requirements. In the original approach some techniques for reducing the computational overhead of DTM's based on the well-know technique of selective path tracing are presented. In this work, the combined use of heuristics are analised and alternative techniques — the heuristics of partial recalculus and not free lines recalculus — are proposed. These alternative techniques were developed in order to minimize the overhead of the DTM's calculus. It is yet proposed the pre-implication technique which transfers to memory the algorithm complexity. It includes a preprocessing stage which storages all necesary informations to the generation of all test vectors. So, these informations don't need be computed in the generation of each test vector. The implementation of the D-Algorithm with diferent heuristics has possibilited a practical experiment. It was possible to analise the performance of the D-Algorithm on diferent circuit types and to demonstrate the efficiency of one of the proposed heuristics.