A global feedback detection algorithm for VLSI circuits

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.

Full Article in ICCD'90 Proceedings, 1990 IEEE International Conference on Computer Design: VLSI in Computers and Processors, 1990