System and method for integrated circuit design

• US 20030188271A1
• Filed: 09/30/2002
• Published: 10/02/2003
• Est. Priority Date: 04/02/2002
• Status: Abandoned Application

• Current Assignee: Institute of High Performance Computing
• Original Assignee: Institute of High Performance Computing
• Inventors: Zeng, Zheng, Bai, Ping, Peyran, Olivier Laurent, Zhuang, Wenjun
• Application Number:
  US10/261,235
• Publication Number:
  US 20030188271A1
• Time in Patent Office: Days
• US Class Current: 716/2
• CPC Class Codes: G06F 30/30 Circuit design

Abstract

The invention relates to an IC chip-planning system and method to provide automatic creation and optimisation of chip-level design plan alternatives that can meet user-specific target chip area/design density, chip shape/aspect ratio, delay/timing closure, and/or congestion/routability objectives at each level of the design—architectural, RTL, gate, structural and physical levels. By combining global searching and local searching, a multi-objective optimisation process and a single-objective optimisation process, the invention can greatly reduce searching and optimisation time. Flexible system structure allows for generation of the optimised chip-planning solutions via an open optimisation train, a small optimisation loop, and/or a large optimisation loop.

With a function module to extract the topological relationship between blocks or gene structure from existing solutions whether from previous designs or manual designs, the invention may also successfully combine human experience and/or work with other EDA tools. A parallel system structure with redundancy elimination is preferably employed to attain high performance in the chip-planning. The invention has the potential to produce near optimal chip-planning solutions to meet the requirements for system-on-chip IC designs having more than 100 million gates and 1 GHz frequency.

Claims

1. A system for generating optimised chip-planning solutions, including:

a dynamic parallel genetic algorithm (DPGA) module adapted to receive a plurality of input parameters and to generate first-phase chip-planning solutions based on global searching and a multi-objective optimisation process; and

a linear programming (LP) module adapted to refine the first-phase chip-planning solutions based on local searching and a single-objective optimisation process to generate second-phase chip-planning solutions.

2. A system according to claim 1, including at least one optimisation loop by means of which the second-phase chip-planning solutions may be further refined.

3. A system according to claim 2, including:

an evaluation module for evaluating said second-phase chip-planning solutions to determine whether or not said second-phase chip-planning solutions should be further refined, and if so, by which optimisation loop.

4. A system according to claim 3, including:

a critical path/block analysis module adapted to provide further optimisation rules to the LP module to refine said second-phase chip-planning solutions if further optimisation is needed;

whereby the LP, evaluation and critical path/block analysis modules together form a small optimisation loop.

5. A system according to claim 4, including:

a structure extraction module adapted to extract solutions from other EDA tools or manual chip-planning and introduce them into the system.

6. A system according to claim 5, wherein the structure extraction module also extracts topological relationships between blocks or gene structures from the second-phase chip-planning solutions and re-directs them into the DPGA module if further optimisation is needed;

whereby the DPGA, LP, evaluation module and structure extraction module together form a large optimisation loop.

7. A system according to claim 6, further including:

a dynamic controller for automatically controlling the optimisation process, wherein the dynamic controller is adapted to;

follow an open optimisation train if and only if for the top 20% best solutions in the result set, design targets have been met after the result evaluation, or the run time is over a predefined parameter of runtime;

follow the small optimisation loop if and only if for the top 20% best solutions in the result set, chip ratio and chip area/design density have met the design targets and the error of delay/time closure and congestion/routability are within a predefined region; and

follow the large optimisation loop if and only if conditions of following open optimisation train and small optimisation loop cannot be satisfied.

8. A system according to claim 1, wherein the LP module is adapted to remove redundancies in the first-phase chip-planning solutions from the DPGA module.

9. A system according to claim 1, wherein the input parameters for the DPGA module include design constraints and/or placement structures.

10. A system according to claim 9, wherein the design constraints contain flexible blocks and/or pre-fixed parameters.

11. A system according to claim 9, wherein the input parameters for the DPGA module include one or more of:

chip area/design density;

chip shape/aspect ratio;

pin assignment;

delay/timing closure; and

congestion/routability.

12. A system according to claim 11, wherein the DPGA module generates the first-phase chip-planning solutions optimised in terms of chip area/design density, delay/timing closure and congestion/routability.

13. A system according to claim 12, wherein the LP module generates the second-phase chip-planning solutions optimised in terms of chip area/design density.

14. A system according to claim 1, wherein the LP module is able to converge to a set of target solutions through different optimisation paths.

15. A system according to claim 3, wherein the evaluation module is adapted to re-conduct pin assignment and optimisation.

16. A system according to claim 3, wherein the evaluation module is adapted to conduct an evaluation with respect to chip shape/aspect ratio, delay/time closure and/or congestion/routability.

17. A system according to claim 3, wherein the evaluation module is adapted to conduct span or gradient analysis.

18. A system according to claim 4, wherein the critical path/block analysis module is adapted to identify circuit critical paths and/or blocks.

19. A system according to claim 4, wherein the critical path/block analysis module is adapted to analyse the delay/time closure and congestion/routability sensitivity.

20. A system according to claim 4, wherein the critical path/block analysis module is adapted to determine the modified sub-structure or constraints between selected blocks for the LP module in said small optimisation loop.

21. A system according to claim 6, wherein the structure extraction module is adapted to extract the characteristics or gene structure from chip-planning solutions, floorplan solutions or placement solutions.

22. A system according to claim 6, wherein the structure extraction module is adapted to convert said extracted characteristics or gene structure to data with DPGA evolution format.

23. A method of creating optimised chip-planning solutions, including the steps of:

providing a plurality of input parameters for IC design;

executing a global searching and multi-objective optimisation process to generate first-phase chip-planning solutions; and

executing a local searching and single-objective optimisation process to refine the first-phase chip-planning solutions and generate second-phase chip-planning solutions.

24. A method according to claim 23, wherein the global searching and multi-objective optimisation process is executed in a dynamic parallel genetic algorithm (DPGA) module, and wherein the local searching and single-objective optimisation process is executed in a linear programming (LP) module.

25. A method according to claim 24, including the step of evaluating said second-phase chip-planning solutions to determine whether or not they should be further refined, said evaluating step being performed by an evaluation module.

26. A method according to claim 25, including the step of further refining the second-phase chip-planning solutions using at least one optimisation loop.

27. A method according to claim 26, including the step of:

providing a small optimisation loop including a critical path/block analysis module to provide further optimisation rules to the LP module to refine said second-phase chip-planning solutions if further optimisation is needed;

said LP module, evaluation module and critical path/block analysis module together forming the small optimisation loop; and

providing a large optimisation loop including a structure extraction module to extract topological relationships between blocks or gene structures from the second-phase chip-planning solutions and re-direct them to the DPGA module if further optimisation is needed;

said DPGA, LP, evaluation and structure extraction modules together forming the large optimisation loop.

28. A method according to claim 27, including the step of:

dynamically selecting an open optimisation train, or said small optimisation loop, or said large optimisation loop to reach the optimised target solutions in the shortest time.

29. A method according to claim 28, wherein said step of dynamically selecting includes:

following the open optimisation train if and only if for the top 20% best solutions in the result set, design targets have been met after the result evaluation, or the run time is over a predefined parameter of run-time;

following the small optimisation loop if and only If for the top 20% best solutions in the result set, chip ratio and chip area/design density have met the design targets and the error of delay/time closure and congestion/routability are within a predefined region;

following the large optimisation loop If and only if conditions of following open optimisation train and small optimisation loop cannot be satisfied.

30. A method according to claim 28, including selecting solutions for said small optimisation loop by span or gradient analyses.

31. A method according to claim 28, including deciding the final solutions from said large optimisation loop by chip area/design density, chip shape/aspect ratio, delay/timing closure and/or congestion/routability evaluation.

32. A method according to claim 28, including assigning/optimising pin locations and estimating delay/timing closure and congestion/routability.

33. A method according to claim 28, including selecting sub-structure or constraints between sensitive blocks for said small optimisation loop.

34. A method according to claim 28, including extracting characteristics or gene structure from various solutions, said various solutions including said second-phase chip-planning solutions, previous chip-plan solutions and/or placement solutions generated manually or by other EDA tools.

35. A method according to claim 34, including converting said extracted characteristics or gene structure to data with said DPGA evolution format.

36. A method according to claim 23, further including providing non-balanced searching to optimise chip area/design density, chips shape/aspect ratio, delay/timing closure and congestion/routability.

37. A method according to claim 31, further including selecting sub-structure or constraints between sensitive blocks for LP to produce optimisation in delay/timing closure and congestion/routability within said small optimisation loop.

38. A method according to claim 27, including the step of:

incorporating other chip planing tools, such as electronic data automation (EDA) tools, or/and human experience into optimisation processes to reach the best optimisation results.

39. A system for generating optimised chip-planning solutions, including:

a dynamic parallel genetic algorithm (DPGA) module adapted to receive a plurality of input parameters and to generate first-phase chip-planning solutions based on global searching and a multi-objective optimisation process;

a linear programming (LP) module adapted to refine the first-phase chip-planning solutions based on local searching and a single-objective optimisation process to generate second-phase chip-planning solutions;

at least one optimisation loop by means of which the second-phase chip-planning solutions may be further refined;

an evaluation module for evaluating said second-phase chip-planning solutions to determine whether or not said second-phase chip-planning solutions should be further refined, and if so, by which optimisation loop; and

a structure extraction module adapted to extract solutions from other EDA tools or manual chip-planning and introduce them into the system.

40. A system according to claim 39, including:

a critical path/block analysis module adapted to provide further optimisation rules to the LP module to refine said second-phase chip-planning solutions if further optimisation is needed;

whereby the LP, evaluation and critical path/block analysis modules together form a small optimisation loop.

41. A system according to claim 39, wherein the structure extraction module also extracts topological relationships between blocks or gene structures from the second-phase chip-planning solutions and re-directs them into the DPGA module if further optimisation is needed;

whereby the DPGA, LP, evaluation module and structure extraction module together form a large optimisation loop.

42. A method of creating optimised chip-planning solutions, including the steps of:

providing a plurality of input parameters for IC design;

executing a global searching and multi-objective optimisation process in a dynamic parallel genetic algorithm (DPGA) module to generate first-phase chip-planning solutions;

executing a local searching and single-objective optimisation process in a linear programming (LP) module to refine the first-phase chip-planning solutions and generate second-phase chip-planning solutions;

evaluating said second-phase chip-planning solutions to determine whether or not they should be further refined, said evaluating step being performed by an evaluation module;

providing a critical path/block analysis module to provide further optimisation rules to the LP module to refine said second-phase chip-planning solutions if further optimisation is needed;

said LP module, evaluation module and critical path/block analysis module together forming a small optimisation loop;

providing a structure extraction module to extract solutions from other EDA tools or manual chip-planning or to extract topological relationships between blocks or gene structures from the second-phase chip-planning solutions and re-direct them to the DPGA module if further optimisation is needed;

said DPGA, LP, evaluation and structure extraction modules together forming a large optimisation loop; and

if necessary, further refining the second-phase chip-planning solutions using at least one of said optimisation loops.