Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
2002-12-17
2004-04-20
Whitmore, Stacy A. (Department: 2812)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C716S030000, C703S013000, C703S014000
Reexamination Certificate
active
06725437
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to an improved circuit placement in VLSI layout. In particular, it relates to performance groups-based fast simulated annealing for improving the speed and quality of VLSI circuit, placement.
BACKGROUND OF THE INVENTION
A typical VLSI circuit comprises a set of modules, a set of signals (or netlist) interconnecting terminals on the periphery of these modules, and a set of locations where these modules can be placed. The VLSI Placement problem is to assign each module to a unique location, i.e. construct a layout, such that an objective function is optimized. The objective function maximizes circuit performance by minimizing path length interconnecting the various circuit elements, ensuring routing of all nets, within a minimum computational time and system memory usage.
Simulated Annealing (SA) is a probabilistic, iterative improvement technique, used to solve many combinatorial optimization problems. This technique has also been applied to solve the VLSI placement problem. The iterative improvement approach used in this technique always provides a scope for further optimisation once the algorithm determines a local optimal. The SA Approach allows accepting states with higher energy, in the anticipation of improving upon a local optimal, and obtaining a Global Optimal Solution as shown in FIG.
1
.
The inherent problem with Simulated Annealing is that it requires excessive computation time and is therefore, very slow. Several techniques have been adopted to improve the speed of the algorithm while maintaining a good quality of the final solution.
One such technique was proposed by Mallela, and Grover (see Sivanarayana Mallela, L K Grover, Clustering Based Simulated Annealing for Std Cell Placement, In Proc of 25th DAC Conf, pp 312-316, 1988.) to improve the performance of SA-based Standard Cell Placement using Clustering. The clustering technique discussed by Mallela and Grover deals with forming clusters of circuit elements wherein the circuit elements to be clustered are searched based on—number of local nets, common nets, common net fanout, terminal count . . . etc., among all the circuit elements of the design. A cluster of two circuit elements is formed, followed by a cluster of clusters. The method uses SA to find suitable regions on the chip for the clusters, and then to place the circuit elements within clusters. This approach works well for smaller designs having a few thousand circuits, but fails as the design size grows to a few million. The reason for the failure is that the number of comparisons required to pick the circuits for cluster is of the Order of (n
2
). Furthermore, the scope of the search while forming clusters using this method extends to the entire circuit set of the design and therefore, requires significantly greater processing.
Another approach that has been used to speed up the SA algorithm is implementing the algorithm in parallel using multiple processors. One such parallelization approach is described by John A Chandy and P Banerjee in Parallel Simulated Annealing Strategies for VLSI Cell Placement, Proc. of 9th International Conference on VLSI Design, Bangalore, India, January 1996. They discuss parallelizing methods for Simulated Annealing based VLSI Cell Placement problem for reducing the inordinate amount of time taken for VLSI circuit Design. An alternative method for parallelization is described by Jonas Knopman in his paper Parallel Simulated Annealing: an Adaptive Approach, Federal University of Rio de Janeiro—NCE/UFRJ Júlio S. Aude—Federal University of Rio, 1997 http://ipdps.eece.unm.edu/1997/s14/257.pdf. The paper presents a Simulated Annealing algorithm applied to the placement of circuits in VLSI. This algorithm uses different parallelization approaches for high and low temperature values of the annealing process. The algorithm used for low temperatures is an adaptive version of the speculative algorithm. The number of processors allocated to the solution of the placement problem and number of moves evaluated per processor between synchronization points changes with the temperature. But the drawback of the parallel approaches is that SA is inherently a sequential algorithm and therefore, is not amenable for an efficient parallel implementation. As a result, most of these approaches have not been very successful in speeding up the VLSI circuit placement using SA.
U.S. Pat. No. 5,745,735 describes a method of optimizing by SA using a spatial metric to localize the simulated annealing temperature, the move set and the objects on which the moves operate. The method keeps a local history of the optimization process. The localization allows the SA process to adaptively control the annealing schedule of each local region independently. This method optimizes the annealing schedule but does not reduce the problem size seen by the annealing process to reduce the computational time while maintaining the quality of placement.
SUMMARY OF THE INVENTION
The object of this invention is to obviate the above drawbacks in the prior art and improve the speed of VLSI circuit placement by reducing the computational time required.
Another object of the invention is to improve the quality of VLSI circuit placement.
Yet another object of the invention is to enable automatic placement of large VLSI circuit designs. To achieve these objectives the present invention provides a Performance Groups-Based Fast Simulated Annealing method for improving speed and quality of VLSI circuit placement. A target objective cost function incorporating the influence of all the significant parameters is defined along with the initial control parameter for circuit placement. Performance groups are formed using selected circuit elements of the VLSI circuit according to predetermined criteria and an initial placement configuration of these performance groups is done randomly.
Subsequently, the value of the initial control parameter is increased to a pre-determined level according to a predetermined schedule. The placement configuration is then perturbed randomly with a high degree of freedom to get a new configuration by altering the configuration of randomly selected circuits. The cost of the new configuration is determined using the objective cost function and the new configuration is accepted when it has a lower associated cost as compared to the previous configuration while it is probabilistically accepted when it has a higher associated cost. The value of the control parameter is decreased by a pre-determined amount according to a predetermined schedule. These steps are repeated for a pre-determined number of times for each control parameter value until a configuration having a lower cost is not detected or the solution cost does not change for a pre-determined number of iterations.
REFERENCES:
patent: 5745735 (1998-04-01), Cohn et al.
patent: 5796625 (1998-08-01), Scepanovic et al.
patent: 6389582 (2002-05-01), Valainis et al.
patent: 6442743 (2002-08-01), Sarrafzadeh et al.
Mallela and Grover (see Sivanarayana Mallela, LK Grover,ClusteringBased Simulated Annealing for Std Cell Placement, In Proc of 25th DAC Conf, pp 312-316, 1988 ).
John A Chandy and P Banerjee in Parallel Simulated Annealing Strategies for VLSI Cell Placement, Proc. of 9th International Conference on VLSI Design, Bangalore, India, Jan. 1996.
Jonas Knopman, Parallel Simulated Annealing: an Adaptive Approach, Federal University of Rio de Janeiro—NCE/UFRJ Júlio S. Aude—Federal University ofRio, 1997 http.//jpds.eec2.unm.edu/1997/s14/257_pdf.
Patil Srinivasa R
Rao Prahlada B
Coca T. Rao
England Anthony V. S.
Whitmore Stacy A.
LandOfFree
Performance groups-based fast simulated annealing for... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Performance groups-based fast simulated annealing for..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Performance groups-based fast simulated annealing for... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3199320