Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
1999-05-17
2002-01-22
Phan, Trong (Department: 2818)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
Reexamination Certificate
active
06341364
ABSTRACT:
BACKGROUND OF THE INVENTION
In circuit simulations of very large circuits, i.e. of circuits with a very large number of elements, a serial processing, i.e. calculation of the circuit parameters by a computer, is very time consuming. Even vector processors, which are rather expensive in their operation, require an immense demand in computing capacity and in time for calculating the electrical descriptive parameters for a circuit comprising a few 100,000 transistors.
For this reason, to avoid the serial execution of a circuit simulation, the electrical circuit can be divided into a plurality of parts, which are then respectively processed by different computers, or respectively, processors, which leads to a parallel execution of the circuit simulation.
However, in order to achieve an optimally good parallelization of the calculation of an electrical circuit descriptive parameters for the electrocircuit, it is very advantageous to consider two criteria in the partitioning of the electrical circuit into a plurality of parts. It is of considerable importance that all formed partitions of the electrical circuit are optimally equally large, in order to thereby enhance the effect that can be achieved by the parallelization. If one partition is larger than the other partitions by orders of magnitude, then the processing of the significantly larger partition in turn requires a much greater computing outlay than the processing of the other partitions. It is also important in the partitioning that optimally only a small number of connections exists between the individual partitions, since in the known methods for “parallelized” circuit simulation, the required transmission capacity, i.e. the required communication between the computers, or respectively, processors which respectively process a partition, rises with an increasing number of existing connections between the partitions.
A language for the textual description of an electrical circuit which can be processed by a computer is the circuit simulation language SPICE. One document disclosing SPICE is I. Hoefer, et al.,
SPICE Analyseprogramm fur electronische Schaltungen,
Springer, Berlin (1985), pp. 7-22.
The documents U. Kleis, et al.,
Doman Decomposition Methods for Circuit Simulation,
Proceedings of the 8
th
Workshop on Parrallel and Distributed Simulation, PADS, Edinburgh, UK (July, 1994), pp. 183-86 U. Wever, et al.,
Parallel Transient Analysis for Circuit Simulation,
Proceedings of the 29
th
Annual Hawaii International Conference on System Sciences (1946), pp. 442-47 teach how a parallelized circuit simulation can be executed, provided there is an arbitrary number of partitions of the electrical circuit. The manner in which partitions can be calculated is not described in these documents.
The documents B. Reiss,
Partitioning Very Large Circuits Using Analytical Placement Techniques,
Proceedings of the 31
st
ACM/IEEE Design Automation Conference (1994), pp. 646-51 J. Li, et al.,
New Spectral Linear Placement and Clustering Approach,
33
rd
Design Automation Conference, Las Vegas Jun. 3-7, 1996), pp. 88-93 teach a global partitioning method on what is known as the logic level, which is also referred to as the gate level.
On the logic level, discrete events are described with which it is not possible, however, to describe constantly dynamic characteristics of an electrical circuit on what is known as the transistor level, i.e. on the actual physical level of the electrical circuit.
The results of a circuit simulation which occurs on the logic level are thus unreliable and imprecise for some applications, since an exact time characteristic, which occurs in the electrical circuit, of the electrical signals cannot be taken into account either.
Furthermore, a model description of the individual gates is needed for the circuit simulation on the gate level, whereby the circuit description with transistor models is already present for the simulation on the transistor level. The model description must be calculated before the method can be executed on the gate level.
What is known as the conjugation gradient method is taught by document G. Sigl,
Analytical Placement: A Linear or a Quadratic Objective Function
?, Proceedings of the 28
th
ACM/IEEE DAC (1991), pp. 427-432.
An overview of various partitioning specifications can be found in P. Johannes,
Partioning of VLSI Circuits and Systems,
33
rd
Design and Automation Conference, Las Vegas (Jun. 3-7, 1996), pp. 83-87.
SUMMARY OF THE INVENTION
An object of the present invention is to provide a method for partitioning an electrical circuit which directly accounts for the elements of the electrical circuit on the transistor level.
To that end, in an embodiment in the invention provides a computer supported method for partitioning an electrical circuit,
wherein the electrical circuit is mapped on a graph having the same topology as the electrical circuit,
wherein nodes and/or edges of the graph are assigned weight values with which a required computing outlay, for the calculation of electrical descriptive parameters for elements of the electrical circuit which are represented by the respective node and/or by the respective edge, is described,
wherein a method for placing the elements of the electrical circuit is applied to the elements.
wherein, in the method for placing the elements, a total length of couplings between the elements is minimized, the weight values that are assigned to the nodes and/or edges being taken into account,
wherein, for the electrical circuit, a measure is calculated of a number of arising cut edges and/or arising margin nodes of partitions of the electrical circuit in the partitioning, and
wherein the elements are grouped in partitions depending on the measure.
In this method, the electrical circuit is mapped on a graph which comprises the same topology as the electrical circuit. The edges and/or nodes of the graph are weighted with weight values which describe an approximately required computing outlay for the calculation of electrical descriptive parameters for the electrical circuit element that is respectively represented by the edge and/or node.
The partitions for the electrical circuit in the graph are formed in such a way that a method for placing the elements of the electrical circuit is applied to the elements, in which method a total length of couplings between the elements in the electrical circuit is minimized. In addition, a measure of the number of appearing edge nodes and/or cut edges of partitions which would respectively appear given the partitioning is calculated for the electrical circuit. The partitions are formed depending on the measure in that the elements are grouped into the individual partitions.
The method has some appreciable advantages compared to the method set forth in B. Reiss,
Partitioning Very Large Circuits Using Analytical Placement Techniques,
Proceedings of the 31
st
ACM/EEE Design Automation Conference (1994) pp. 664-651.
Since the method operates directly on the transistor level of the electrical circuit, the results achieved by the method in a later circuit simulation using the inventively calculated partitions are appreciably more precise and more reliable.
In an embodiment of the invention, at the beginning of the method, a grouping of elements of the electrical circuit is executed, for which it is specified that these elements are jointly assigned to one partition.
In an embodiment of the invention, in the grouping of the elements of the electrical circuit, at least one of the following specifications is applied:
elements of a controlled source, at least one controlling element, and the controlled source are jointly assigned to one partition,
connection loops in the electrical circuit, they are jointly assigned to one partition, shorts must not arise due to the partitioning and/or due to a modelling of an interface.
In an embodiment of the invention, a plurality of nodes and/or edges of the graph are assigned a common weight value.
In an embodiment of the invention, the graph of the partition is ma
Fröhlich Norbert
Wever Utz
Zheng Qinghua
Phan Trong
Schiff & Hardin & Waite
Siemens Aktiengesellschaft
LandOfFree
Computer assisted method of partitioning an electrical circuit does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Computer assisted method of partitioning an electrical circuit, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Computer assisted method of partitioning an electrical circuit will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2829016