Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
1997-10-06
2002-08-20
Siek, Vuthe (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C716S030000, C716S030000
Reexamination Certificate
active
06438734
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to circuit or system simulators and synthesis systems, and more particularly, to an improved method for finding elementary loops in a graph representing a circuit or system.
BACKGROUND OF THE INVENTION
One step in the analysis of a circuit or system involves the generation of a directed graph that represents the circuit. Consider the class of systems that can be described graphically by a block diagram in which each element of the system can be represented by a block and the connection between two elements can be represented by a line. Electronic circuits or systems fall into this class of systems. In order to analyze the system topology, the system block diagram can be mapped to a graph consisting of a plurality of vertices connected by “edges”. Each vertex corresponds to one of the blocks in the block diagram, each edge in the graph corresponds to a connection between the blocks.
Many circuit simulation and synthesis problems require that all of the elementary loops (circuits or cycles) of the directed graph representing the circuit be located. A directed graph is a graph in which the edges specify a direction. In the case of a circuit, the direction represents the direction in which signals travel from one element (block) to the adjacent element. For example, to schedule a hierarchical communication system all of the feed back loops in the system must be found. One method for solving high-level DSP synthesis problems requires that all loops in a directed graph must be located.
Prior art methods for locating the loops in a directed graph are computationally to expensive to be applied to many problems of interest. For example, Taian's method (R. Tajan, “Depth-First Search and Linear Graph Algorithm”, SIAM J. Comput. Vol.1, No.2, June, 1972 for more details) requires a time that is proportional to (C+1)(VE), where V is the number of vertices in the graph, E is the number of edges, and C is the number of loops in the graph. In the worst case, C approaches E, and V is of order E. Hence the computational work load can be of order V
3
. This workload is unacceptable for many practical applications.
Broadly, it is the object of the present invention to provide an improved method for finding the elementary loops of a directed graph representing a circuit.
It is a further object of the present invention to provide a method for finding the elementary loops of a graph which imposes a lower computational workload then prior art methods.
These and other objects of the present invention will become apparent to those skilled in the art from the following detailed description of the invention and the accompanying drawings.
SUMMARY OF THE INVENTION
The present invention is a method for operating a computer to find elementary loops in a strongly connected component of a graph. In the basic method, the computer identifies a starting vertex from the vertices of the strongly connected component. The potential vertices are those that have not been examined as a possible starting vertex for an elementary loop and which are not contained in any elementary loop discovered thus far. The vertices of the strongly connected component are then searched for a path starting and ending on the identified vertex. If the search finds a path starting and ending of the identified vertex, the path is recorded as an elementary loop. This process is repeated until no starting vertex can be identified. To improve the efficiency of the search process, the computer identifies vertices that are the starting vertex for paths that are shared by more than one elementary loop. The shared paths are stored separately and used to avoid searching the vertices of the path more than once.
REFERENCES:
patent: 5375074 (1994-12-01), Greenberg et al.
patent: 5555270 (1996-09-01), Sun et al.
patent: 5857097 (1999-01-01), Henzinger et al.
Johnson, D.B., “Finding All the Elementary Circuits of a Directed Graph”, SIAM Journal of Computing, vol. 4, Mar. 1975, pp. 77-84.*
Shih, H., Kovijanic, P.G., Razdan, R., “A Global Feedback Detection Algorithm for VLSI Circuits,” Proceedings of IEEE International Conference on Computer Design: VLSI in Computers and Processors, Sep. 19, 1990, pp. 37-40.*
Jiang, B., “A Suitable Algorithm for Computing Partial Transitive Closures in Databases,” Proceddings of the Sixth International Conference on Data Engineering, Feb. 9, 1990, pp. 264-271.*
Shih, H.-C.; Kovijanic, P.G.; Razdan, R., “A Global Feedback Detection Algorithm for VLSI Circuits”, Computer Design: VLSI in Computers and Processors, 1990. ICCD '90. Proceedings, 1990 IEEE International Conference on, pp. 37-40.*
Jiang, B., “A Suitable Algorithm for Computing Partial Transitive Closures in Databases”, Data Engineering, 1990. Proceedings, Sixth International Conference on, pp. 264-271.*
Hudli, R.V.; Seth, S.C., “Testability Analysis of Synchronous Sequential Circuits Based on Structural Data”, Test Conference, 1989. Proceedings. Meeting the Tests of Time., International, pp. 364-372.
LandOfFree
Fast search method for enabling a computer to find... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Fast search method for enabling a computer to find..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fast search method for enabling a computer to find... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2972116