Performance groups-based fast simulated annealing for improving speed and quality of VLSI circuit placement
AssigneeInternational Business Machines Corporation
InventorsPrahlada B Rao, Srinivasa R Patil
Life of this patent
Estimating the term…
Abstract
The present invention provides Performance groups based Simulated Annealing (PGSA) for VLSI circuit placement. This method reduces the computation time required for VLSI circuit placement using Simulated Annealing by reducing the size of the placement problem by forming Performance groups while maintaining a high quality of the final placement solution. Performance groups are formed by picking circuits connected by a net and counting their local-net-count. These circuits are then grouped based on certain pre-determined conditions and placed suitably using simulated annealing based placement approach.
Claims33
A method for VLSI circuit placement providing improved quality and enhanced speed, comprising the steps of:
- a. defining a target objective cost function and an initial value for a control parameter for circuit placement,
- b. grouping selected circuit elements of the VLSI circuit to form performance groups,
- c. selecting an initial placement configuration of the performance groups,
- d. increasing the value of the initial control parameter to a predetermined level,
- e. perturbing the placement configuration randomly to get a new configuration,
- f. determining an objective cost of the new configuration using the objective cost-function,
- g. accepting the new configuration when it has a lower objective cost as compared to the previous configuration, otherwise probabilistically accepting the new configuration when it has a higher objective cost,
- h. decreasing the value of the control parameter, and
- i. repeating steps (e) to (h) until a configuration having a lower objective cost is not detected for a predetermined number of iterations.
A system for VLSI circuit placement, comprising:
- a processor and a storage device, wherein the storage device stores certain computer software and the processor is operable to access the computer software from the storage device and in response to the computer software to perform functions comprising:
- a. defining a target objective cost function and an initial value for a control parameter for circuit placement;
- b. grouping selected circuit elements of the VLSI circuit to form performance groups;
- c. selecting an initial placement configuration of the performance groups;
- d. increasing the value of the initial control parameter to a predetermined level;
- e. perturbing the placement configuration randomly to get a new configuration;
- f. determining an objective cost of the new configuration using the objective cost-function;
- g. accepting the new configuration when it has a lower objective cost as compared to the previous configuration, otherwise probabilistically accepting the new configuration when it has a higher objective cost;
- h. decreasing the value of the control parameter;
- and
- i. repeating steps (e) to (h) until a configuration having a lower objective cost is not detected for a predetermined number of iterations.
A computer program product comprising computer readable program code stored on computer readable storage medium embodied therein for VLSI circuit placement providing improved quality and enhanced speed, comprising:
- computer readable program code means configured for defining a target objective cost function and an initial value for a control parameter for circuit placement;
- computer readable program code means configured for grouping selected circuit elements of the VLSI circuit to form performance groups;
- computer readable program code means configured for selecting an initial placement configuration of the performance groups;
- computer readable program code means configured for increasing the value of the initial control parameter to a predetermined level;
- computer readable program code means configured for perturbing the placement configuration randomly to get a new configuration;
- computer readable program code means configured for determining an objective cost of the new configuration using the objective cost-function;
- computer readable program code means configured for accepting the new configuration when it has a lower objective cost as compared to the previous configuration, otherwise probabilistically accepting the new configuration when it has a higher objective cost;
- computer readable program code means configured for decreasing the value of the control parameter;
- and
- computer readable program code means configured for repeating steps (e) to (h) until a configuration having a lower objective cost is not detected for a predetermined number of iterations.
Dependencies are inferred from the claim text.