Logic synthesis of multi-level domino asynchronous pipelines

• US 20060120189A1
• Filed: 11/10/2005
• Published: 06/08/2006
• Est. Priority Date: 11/22/2004
• Status: Active Grant

• Current Assignee: Intel Corporation
• Original Assignee: Fulcrum Microsystems, Inc. (Intel Corporation)
• Inventors: Lines, Andrew, Davies, Michael, Beerel, Peter
• Granted Patent: US 7,584,449 B2
• Time in Patent Office: Days
• US Class Current: 365/203
• CPC Class Codes: G06F 30/35 Delay-insensitive circuit design, e.g. asynchronous or self-timed

Abstract

Methods and apparatus are described for optimizing a circuit design. A gate level circuit description corresponding to the circuit design is generated. The gate level circuit description includes a plurality of pipelines across a plurality of levels. Using a linear programming technique, a minimal number of buffers is added to selected ones of the pipelines such that a performance constraint is satisfied.

Claims

1. A computer-implemented method for optimizing a circuit design, comprising:

generating a gate level circuit description corresponding to the circuit design, the gate level circuit description comprising a plurality of pipelines across a plurality of levels; and

using a linear programming technique, adding a first number of buffers to selected stages of the pipelines such that the pipelines are balanced, at least one performance constraint is satisfied, and an objective function characterizing the circuit design is minimized.

2. The method of claim 1 wherein the linear programming technique employs real and integer variables subject to linear constraints.

3. The method of claim 2 wherein the objective function is one of linear and nonlinear.

4. The method of claim 2 wherein the linear programming technique comprises one of an integer linear programming (ILP) technique, a mixed-integer linear programming (MILP) technique, or a linear programming (LP) technique.

5. The method of claim 1 wherein the gate level circuit description comprises a hierarchical description comprising leaf cells, mid-level cells, and channels interconnecting the leaf cells and the mid-level cells, the channels having channel cycle times associated therewith, and wherein adding the first number of buffers comprises formulating a mixed integer linear programming (MILP) formulation with reference to the hierarchical description and a target cycle time, and solving the MILP formulation using an MILP solver to identify where the first number of buffers should be added to the circuit design.

6. The method of claim 1 further comprising converting the linear programming technique to perform a performance analysis of the circuit design.

7. The method of claim 1 wherein the linear programming technique requires that each pipeline have at least one gate in each pipeline stage through which it passes.

8. The method of claim 1 wherein the circuit design comprises one of asynchronous multi-level domino logic and latency-insensitive synchronous logic.

9. The method of claim 1 wherein the circuit design comprises a slack-elastic asynchronous system.

10. The method of claim 1 wherein adding the first number of buffers comprises adding a second number of buffers to balance the pipelines to achieve a performance target, and removing selected ones of the second number of buffers while still substantially achieving the performance target.

11. The method of claim 1 wherein the objective function comprises at least one of throughput, area, power dissipation, cost of additional leaf cell types, and a total number of buffers.

12. The method of claim 1 wherein the circuit design has a plurality of modes of operation, each mode of operation corresponding to a subset of the pipelines being active during the corresponding mode, and wherein application of the linear programming technique to add the first number of buffers is done considering all modes of operation.

13. The method of claim 12 wherein each of the modes of operation has a corresponding frequency of occurrence, and wherein successive application of the linear programming technique for the modes of operation is done in order of the frequency of occurrence associated with each.

14. The method of claim 13 wherein a result of a previous application of the linear programming technique for a corresponding one of the modes of operation is used as input for a subsequent application of the linear programming technique for another one of the modes of operation.

15. The method of claim 14 wherein the performance constraint comprises an average of a plurality of performance constraints each of which is associated with application of the linear programming technique for a corresponding one of the modes of operation.

16. The method of claim 15 wherein the performance constraint associated with a first one of the modes of operation is relaxed with respect to the performance constraint associated with a second one of the modes of operation, application of the linear programming technique for the first mode of operation being subsequent to application of the linear programming technique for the second mode of operation.

17. The method of claim 15 wherein a selected one of the pipelines is active in more than one of the modes of operation, and wherein application of the linear programming technique for each of the more than one of the modes of operation employs a cycle time for the selected pipeline which is associated with a most constrained one of the more than one of the modes of operation.

18. The method of claim 15 wherein a subset of the pipelines is active in more than one of the modes of operation, and wherein application of the linear programming technique for each of the more than one of the modes of operation employs independent token arrival time variables to model time behavior for each of the more than one of the modes of operation.

19. The method of claim 1 wherein the gate level circuit description comprises at least one of a plurality of full-buffer asynchronous cells and a plurality of half-buffer asynchronous cells.

20. The method of claim 1 wherein the linear programming technique models free slack in each channel in the pipelines such that a local cycle time of each channel meets the at least one performance constraint.

21. The method of claim 1 wherein the linear programming technique constrains arrival times of tokens at asynchronous leaf cells in the pipeline stages such that modeled time behavior of the circuit design includes delay associated with the asynchronous leaf cells.

22. The method of claim 1 wherein the linear programming technique employs a mathematically equivalent representation of modeling free slack in each channel in the pipelines such that a local cycle time of each channel meets the at least one performance constraint.

23. The method of claim 1 wherein the linear programming technique employs a mathematically equivalent representation of constraining arrival times of tokens at asynchronous leaf cells in the pipeline stages such that modeled time behavior of the circuit design includes delay associated with the asynchronous leaf cells.

24. At least one computer-readable medium having data structures stored therein resulting from the method of claim 1 and representative of the circuit.

25. The at least one computer-readable medium of claim 24 wherein the data structures comprise a simulatable representation of the circuit.

26. The at least one computer-readable medium of claim 25 wherein the simulatable representation comprises a netlist.

27. The at least one computer-readable medium of claim 24 wherein the data structures comprise a code description of the circuit.

28. The at least one computer-readable medium of claim 27 wherein the code description corresponds to a hardware description language.

34. The method of claim 1 further comprising selecting portions of synchronous logic represented by the netlist for conversion to the asynchronous logic.

29. A computer-implemented method for synthesizing a circuit which includes asynchronous logic from a netlist generated by a synchronous computer-aided design tool, comprising:

converting synchronous logic gates represented by the netlist to asynchronous logic gates;

replacing clock circuitry represented by the netlist with asynchronous control circuitry and completion control circuitry thereby generating a plurality of asynchronous pipelines including the asynchronous logic gates;

inserting a plurality of buffers corresponding to a specific design template into selected ones of the asynchronous pipelines to normalize path lengths through the asynchronous pipelines thereby achieving a level of performance; and

removing selected ones of the buffers in a manner dependent on the specific design template to reduce overhead associated with the asynchronous logic with substantially no impact on the level of performance.

30. The method of claim 29 wherein removal of the selected buffers is accomplished using one of an integer linear programming (ILP) technique, a mixed-integer linear programming (MILP) technique, and a linear programming (LP) technique.

31. The method of claim 29 further comprising generating the netlist using the synchronous CAD tool.

32. The method of claim 31 wherein the netlist originates from a register transfer language (RTL) specification.

33. The method of claim 29 further comprising performing logic synthesis on the netlist to generate the synchronous logic gates.

35. The method of claim 29 wherein converting the synchronous logic gates to the asynchronous logic gates comprises replacing single-rail logic gates with dual-rail equivalents.

36. The method of claim 35 further comprising deriving the single-rail logic gates from a library of dual-rail logic gates.

37. The method of claim 36 wherein deriving the single-rail logic gates from the library of dual-rail logic gates comprises mapping dual-rail timing arcs to synchronous equivalents.

38. The method of claim 29 wherein the asynchronous logic gates comprise domino logic gates, and the asynchronous logic comprises multi-level domino logic.

39. At least one computer-readable medium having data structures stored therein resulting from the method of claim 29 and representative of the circuit.

40. The at least one computer-readable medium of claim 39 wherein the data structures comprise a simulatable representation of the circuit.

41. The at least one computer-readable medium of claim 40 wherein the simulatable representation comprises a netlist.

42. The at least one computer-readable medium of claim 39 wherein the data structures comprise a code description of the circuit.

43. The at least one computer-readable medium of claim 42 wherein the code description corresponds to a hardware description language.