A global feedback detection algorithm for VLSI circuits
- 4 December 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
A global feedback detection algorithm for VLSI circuits is presented. It can identify all the global feedback loops within reasonable computational time. The overall algorithm is as follows: First, all the strongly connected components (SCC) are found using a modified version of the Tarjan algorithm which can handle circuits with flip-flops and latches. Second, each SCC recursively cuts the loops based on heuristic criteria to reduce computation time and space until all loops inside this SCC are out. The modified Tarjan algorithm for finding SCCs in circuits consisting of functional primitive elements such as flip-flops and latches is described. A recursive loop-cutting algorithm for strongly connected components is presented, and a top-level partitioning scheme to reduce memory requirements and computation time for finding global feedback loops is proposed.<>Keywords
This publication has 8 references indexed in Scilit:
- An interactive sequential test pattern generation systemPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Diagnosis & Reliable Design of Digital SystemsPublished by Springer Nature ,1976
- Finding All the Elementary Circuits of a Directed GraphSIAM Journal on Computing, 1975
- The identification of a minimal feedback vertex set of a directed graphIEEE Transactions on Circuits and Systems, 1975
- Enumeration of the Elementary Circuits of a Directed GraphSIAM Journal on Computing, 1973
- Depth-First Search and Linear Graph AlgorithmsSIAM Journal on Computing, 1972
- A Heuristic Algorithm for the Testing of Asynchronous CircuitsIEEE Transactions on Computers, 1971
- Minimum Feedback Arc Sets for a Directed GraphIEEE Transactions on Circuit Theory, 1963