Title :
A global feedback detection algorithm for VLSI circuits
Author :
Shih, Hsi-Ching ; Kovijanic, P.G. ; Razdan, R.
Author_Institution :
Digital Equipment Corp., Andover, MA, USA
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 :
VLSI; automatic testing; circuit analysis computing; integrated circuit testing; logic testing; sequential circuits; Tarjan algorithm; VLSI circuits; computational time; flip-flops; global feedback detection algorithm; global feedback loops; heuristic criteria; latches; memory requirements; recursive loop-cutting algorithm; strongly connected components; top-level partitioning; Automatic testing; Circuit testing; Detection algorithms; Feedback circuits; Feedback loop; Flip-flops; Latches; Partitioning algorithms; Sequential analysis; Very large scale integration;
Conference_Titel :
Computer Design: VLSI in Computers and Processors, 1990. ICCD '90. Proceedings, 1990 IEEE International Conference on
Conference_Location :
Cambridge, MA
Print_ISBN :
0-8186-2079-X
DOI :
10.1109/ICCD.1990.130155
