[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. / [en] The logical test of integrated VLSI circuits is one of the main phases of their design and fabrication. The pseudo-exhaustive approach for the logical test of integrated circuits consists in partitioning the original circuit to be tested into non-overlapping subcircuits with a small, bounded number of subcircuits, which are then exhaustively tested in parallel. In this work we present an approximate algorithm for the problem of partitioning integrated combinational circuits, based on the tabu search metaheuristic. The proposed algorithm presents several original features, such as: the use of a reduced neighborhood, obtained from moves involving only a subset of boundary nodes; complex moves which entail several resulting moves, although the variations in the cost function are very easily computable; a bi-criteria cost function combining the number of subcircuits and the number of cuts, which simultaneously adds a diversification strategy to the search; and the use of a bin-packing heuristic as a post-optimization step. The behavior of the proposed algorithm was evaluated through its application to a set of benchmark ISCAS combinational circuits. The computational results have been compared with those obtained by the other algorithms in the literature, with significant improvements. The average reduction rates have been of the order of 30% in the number of subcircuits in the partition, and of the order of 40% in the number of cuts.
| Identifer | oai:union.ndltd.org:puc-rio.br/oai:MAXWELL.puc-rio.br:14096 |
| Date | 10 September 2009 |
| Creators | ALEXANDRE ALBINO ANDREATTA |
| Contributors | CELSO DA CRUZ CARNEIRO RIBEIRO, CELSO DA CRUZ CARNEIRO RIBEIRO |
| Publisher | MAXWELL |
| Source Sets | PUC Rio |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | TEXTO |
Page generated in 0.0022 seconds