Method and apparatus for simulation system compiler Number:7,080,365 from the United States Patent and Trademark Office (PTO) owispatent A method for compiling a cycle-based design involves generating a parsed cycle-based design from the cycle-based design, elaborating the parsed cycle-based design to an annotated syntax tree, translating the annotated syntax tree to an intermediate form, and converting the intermediate form to an executable form.<H simulation, apparatus, Method, and, appa, 7080365.html, Patent, pto, 7080365

Title: Method and apparatus for simulation system compiler

Abstract: A method for compiling a cycle-based design involves generating a parsed cycle-based design from the cycle-based design, elaborating the parsed cycle-based design to an annotated syntax tree, translating the annotated syntax tree to an intermediate form, and converting the intermediate form to an executable form.

Patent Number: 7,080,365 Issued on 07/18/2006 to Broughton, et al.

Inventors: Broughton; Jeffrey M. (Palo Alto, CA); Chen; Liang T. (Saratoga, CA); Lam; William kwei-cheung (Newark, CA); Pappas; Derek E. (Union City, CA); Chen; Ihao (San Jose, CA); McWilliams; Thomas M. (Menlo Park, CA); Narang; Ankur (New Delhi, IN); Rubin; Jeffrey B. (Pleasanton, CA); Cohen; Earl T. (Fremont, CA); Parkin; Michael W. (Palo Alto, CA); Saulsbury; Ashley N. (Los Gatos, CA); Ball; Michael S. (La Mesa, CA)
Assignee: Sun Microsystems, Inc. (Santa Clara, CA)

Appl. No.: 10/113,582

Filed: March 29, 2002

Current U.S. Class: 717/146 ; 703/15; 716/1

Current International Class: G06F 9/45 (20060101)

Field of Search: 714/49 717/149,124,152,146,161,131 703/15,16,26 716/1 715/771,762

References Cited [Referenced By]

U.S. Patent Documents


4885684	December 1989	Austin et al.
5274818	December 1993	Vasilevsky et al.
5960171	September 1999	Rotman et al.
6421808	July 2002	McGeer et al.
2004/0019883	January 2004	Banerjee et al.

Foreign Patent Documents


1 107 116	Jun., 2001	EP

Other References

Yu-Kwong Kwok and Ishfaq Ahmad; "Dynamic Critical-Path Scheduling: An Effective Technique for Allocating Task Graphs to Multiprocessors;" May 1996, pp. 506-521; vol. 7, No. 5, IEEE Transactions On Parallel and Distributed Systems. cited by other .
Min-You Wu and Daniel D. Gajski; "Hypertool: A Programming Aid For Message-Passing Systems;" Jul. 1990, pp. 330-343, vol. 1, No. 3, IEEE Transactions On Parallel and Distributed Systems. cited by other .
Jing-Jang Hwang, Yuan-Chieh Chow, Frank D. Anger, and Chung-Yee Lee; "Scheduling Precedence Graphs In Systems With Interprocessor Communication Times;" Apr. 1989, pp. 244-257, vol. 18, No. 2, Siam Journal Computing. cited by other .
Gilbert C. Sih and Edward A. Lee; "A Compile-Time Scheduling Heuristic for Interconnection-Constrained Heterogeneous Processor Architectures;" Feb. 1993, pp. 175-187; vol. 4, No. 2, IEEE Transactions On Parallel and Distributed Systems. cited by other .
Tao Yang and Apostolos Gerasoulis; "DSC: Scheduling Parallel Tasks on an Unbounded Number of Processors;" pp. 1-36, IEEE Transactions On Parallel and Distributed Systems, 1994. cited by other .
Charles J. Alpert and Andrew B. Kahng; "Recent Directions in Netlist Partitioning: A Survey;" pp. 1-93, UCLA Computer Science Department, 1995. cited by other .
William J. Dally, J. A. Stuart Fiske, John S. Keen, Richard A. Lethin, Michael D. Noakes, Peter R. Nuth, Roy E. Davison and Gregory A. Fyler; "The Message-Driven Processor: A Multicomputer Processing Node with Efficient Mechanisms;" Apr. 1992; pp. 24-39, IEEE Micro. cited by other .
F. W. Howell, R. Williams, and R. N. Ibbett; Hierarchical Architecture Design and Stimulation Environment; University of Edinburgh, 1994, pp. 363-366. cited by other .
Quickturn Cobalt Webpage; "Quickturn Boosts Speed, Flexibility In CoBalt 2.0;" Apr. 20, 1998; pp. 1-4. cited by other .
Vivek Sarkar; "Partitioning and Scheduling Parallel Programs for Multiprocessors;" Copyright 1989, pp. 1-201, The MIT Press. cited by othe- r .
C. Ajluni; "Advanced Emulation Tool Targets High-Speed Functional Verification"; vol. 45, No. 5, pp. 80, 82; Mar. 3, 1997; Electronic Design, Penton Publishing, USA. cited by other .
European Search Report dated Apr. 21, 2004 (5 pgs.). cited by other.

Primary Examiner: Dam; Tuan
Assistant Examiner: chow; Chih-Ching
Attorney, Agent or Firm: Osha Liang LLP

Parent Case Text

CROSS-REFERENCE TO RELATED APPLICATIONS

This application claims benefit of U.S. Provisional Application Ser. No. 60/313,762, filed Aug. 20, 2001, entitled "Phasers-Compiler Related Inventions," in the names of Liang T. Chen, Jeffrey Broughton, Derek Pappas, William Lam, Thomas M. McWilliams, Ihao Chen, Ankur Narang, Jeffrey Rubin, Earl T. Cohen, Michael Parkin, Ashley Saulsbury, and David R. Emberson.

This application claims benefit to Provisional Application Ser. No. 60/313,217, filed Aug. 17, 2001, entitled "Phaser System Architecture," and invented by Thomas M. McWilliams; Jeffrey B. Rubin; Derek Pappas; Kunle Olukotun; Jeffrey Broughton; David R. Emberson; William Lam; Liang T. Chen; Ihao Chen; Earl T. Cohen; and Michael Parkin.

Claims

What is claimed is:

1. A computer implemented method for compiling a cycle-based design in a simulation system comprising: generating a parsed cycle-based design from the cycle-based design; elaborating the parsed cycle-based design to an annotated syntax tree of component objects constituting the cycle-based design; translating the annotated syntax tree to a language independent intermediate form; and converting the intermediate form to an executable form.

2. The method of claim 1, wherein the cycle-based design represents a hardware description language.

3. The method of claim 2, wherein the hardware description language comprises a hierarchical collection of modules.

4. The method of claim 3, wherein a plurality of variables at different levels of the hierarchical collection of modules represent a common variable.

5. The method of claim 2, wherein the hardware description language is Verilog.

6. The method of claim 5, wherein the cycle-based design comprises a clocked logic design having at least one periodic clock source.

7. The method of claim 5, wherein the cycle-based design allows an initialization of a variable defined by the hardware description language.

8. The method of claim 7, wherein the initialization of the variable is performed by an external control system.

9. The method of claim 1, further comprising: representing the cycle-based design in an annotated symbol table.

10. The method of claim 9, further comprising: using the annotated symbol table with an external control system.

11. The method of claim 1, wherein converting the intermediate form to an executable form comprises: applying predicates for control conversion to transform the intermediate form into a straight-line process; mapping at least one node of the intermediate form to an operation of an execution processor; applying flow optimization to the intermediate form; scheduling the sequence of a plurality of instructions associated with the intermediate form; mapping intermediate form operations of the intermediate form to instructions of the execution processor; assembling instructions of the execution processor.

12. The method of claim 11, further comprising: partitioning the intermediate form into a plurality of parallel segments.

13. The method of claim 12, wherein partitioning comprises a coarsening phase, an initial partitioning phase, and an uncoarsening and refinement phase.

14. The method of claim 12, further comprising: adding a message passing instruction to the plurality of parallel segments.

15. The method of claim 14, further comprising: generating routing instructions for the message passing instruction to traverse a multiprocessor system.

16. The method of claim 11, further comprising: allocating storage for variables associated with the intermediate form.

17. The method of claim 1, wherein the parsed cycle-based design models a logic design as an object-oriented data structure having reference objects and instance objects, the reference objects providing static attributes, the instance objects providing attributes of at least one point of invocation, and wherein a plurality of the instance objects share the attributes of one of the reference objects.

18. The method of claim 4, further comprising: combining the plurality of variables into a single variable.

19. The method of claim 11, wherein applying predicates for control conversion comprises: eliminating at least one internal branch in the intermediate form.

20. The method of claim 1, wherein converting the intermediate form to the executable form further comprises: recognizing a three state subset of a four state logic computation; and producing executable code specialized for the three state subset.

21. The method of claim 1, wherein converting the intermediate form to the executable form further comprises: recognizing a two state subset of a four state logic computation; and producing executable code specialized for the two state subset.

22. The method of claim 1, wherein the cycle-based design models a design net having multiple driving sources, further comprising: inserting a phantom gate, wherein the phantom gate resolves multiple signal logic states.

23. The method of claim 1, further comprising: levelizing the annotated syntax tree; and sorting the annotated syntax tree.

24. The method of claim 23, wherein sorting allows a single evaluation of logical components.

25. The method of claim 23, wherein sorting comprises: sorting the annotated syntax tree into a clock logic design class, a sequential logic design class, and a combinatorial logic design class.

26. The method of claim 1, wherein elaborating comprises: examining a plurality of modules; marking any module used by any other module as a child module; and identifying a root module candidate, if one of the plurality of modules is unmarked.

27. The method of claim 1, wherein the cycle-based design comprises a plurality of design logic instructions.

28. The method of claim 27, wherein the compiler partitions the design logic instructions among a plurality of memory elements in a hardware simulation system.

29. The method of claim 1, wherein the cycle-based design has a plurality of bit level operations, and wherein the compiler generates executable code to evaluate the plurality of bit level operations simultaneously.

30. The method of claim 1, further comprising: detecting a procedure call outside the cycle-based design; and recording in a data structure required at run time to interpret the procedure call.

31. A computer implemented method for compiling a cycle-based design in a simulation system comprising: generating a parsed cycle-based design from the cycle-based design; elaborating the parsed cycle-based design to an annotated syntax tree of component objects constituting the cycle-based design; translating the annotated syntax tree to an intermediate form; converting the intermediate form to an executable form; representing the cycle-based design in an annotated symbol table; levelizing the annotated syntax tree; sorting the annotated syntax tree; detecting a procedure call outside the cycle-based design; and recording in a data structure required at run time to interpret the procedure call.

32. A computer implemented method for compiling a cycle-based design in a simulation system comprising: generating a parsed annotated syntax tree of component objects constituting the cycle-based design; inferring a logic type from parsed annotated syntax tree for each of a plurality of logic components; elaborating the plurality of logic components to construct a design logic comprising a hierarchical design tree and a flattened design connectivity; levelizing the design logic to schedule execution order of logical components using the flattened design connectivity; translating the parsed annotated syntax tree and levelized flattened design connectivity into an intermediate form operation; assigning each intermediate form operation to an execution processor; ordering of the intermediate form operation within the assigned execution processor; generating routing instructions for a message passing instruction to traverse a multiprocessor system; converting the intermediate form operation into an annotated symbol table; and converting the intermediate operation into executable form.

33. The method of claim 32, wherein the cycle-based design represents a hardware description language.

34. The method of claim 33, wherein the hardware description language comprises a hierarchical collection of modules.

35. The method of claim 33, wherein the hardware description language is Verilog.

36. The method of claim 32, wherein the logic type comprises clock logic, sequential logic, data logic, and initial logic.

37. A computer implemented method for levelization of a cycle-based design in a simulation system, comprising collecting a plurality of simulated components by a logic type; identifying a design constraint violation in the cycle-based design; and sorting the plurality of simulated components according to the logic type into a component list; wherein sorting determines an execution order of the plurality of simulated components whereby each of the plurality of simulated components are evaluated only once per simulation clock cycle.

38. The method of claim 37, further comprising: correcting the cycle-based design if the design constraint violation is identified in the cycle-based design.

39. The method of claim 37, wherein the logic type comprises clock logic, sequential logic, data logic, and initial logic.

40. A compiler on a computer based simulation system comprising: a design analyzer configured to generate a parsed cycle-based design from a cycle-based design; a design elaborator configured to expand the parsed cycle-based design to an annotated syntax tree of component objects constituting the cycle-based design; a translator configured to translate the annotated syntax tree to a language independent intermediate form; and a code generator configured to convert the intermediate form to an executable form.

41. The compiler of claim 40, wherein the cycle-based design is represented as a hierarchical collection of modules.

42. The compiler of claim 41, wherein a plurality of variables at different levels of the hierarchical collection of modules represent a common variable.

43. The compiler of claim 40, wherein the cycle-based design is written in a hardware description language.

44. The compiler of claim 43, wherein the hardware description language is Verilog.

45. The compiler of claim 40, wherein the cycle-based design represents a clocked logic design having at least one periodic clock source.

46. The compiler of claim 43, wherein the cycle-based design allows an initialization of a variable defined by the hardware description language.

47. The compiler of claim 46, wherein the initialization of the variable is performed by an external control system.

48. The compiler of claim 46, wherein a value assigned to the variable automatically propagates to at least one dependent variable.

49. The compiler of claim 40, further comprising: an annotated symbol table configured to represent the cycle-based design.

50. The compiler of claim 49, further comprising: an external control system configured to be used with the annotated symbol table.

51. The compiler of claim 40, wherein the code generator further comprises: a control flow converter configured to transform the intermediate form into a straight-line process; a node mapper configured to map at least one node of the intermediate form to an operation of an execution processor; a flow optimizer configured to apply flow optimization to the intermediate form; a scheduler configured to schedule a sequence of a plurality of instructions associated with the intermediate form; an instruction mapper configured to map intermediate form operations of the intermediate form to instructions of the execution processor; and an assembler configured to assemble instructions for the execution processor.

52. The compiler of claim 51, further comprising: a partitioner configured to partition the intermediate form into a plurality of parallel segments.

53. The compiler of claim 52, wherein the partitioner uses a multilevel approach comprising a coarsening phase, an initial partitioning phase, and an uncoarsening and refinement phase.

54. The compiler of claim 51, further comprising: message passing instructions configured to be added to the segments.

55. The compiler of claim 54, further comprising: routing instructions configured to be generated for the messages to traverse a multiprocessor system.

56. The compiler of claim 51 further comprising: storage for variables associated with the intermediate form configured to be allocated.

57. The compiler of claim 40, wherein the parsed cycle-based design models a logic design as an object-oriented data structure having reference objects and instance objects, the reference objects providing static attributes, the instance objects providing attributes of at least one point of invocation, and wherein a plurality of the instance objects share the attributes of one of the reference objects.

58. The compiler of claim 40, wherein the cycle-based design models a design net having multiple driving sources, further comprising: a phantom gate configured to be inserted, wherein the phantom gate resolves multiple signal logic states.

59. The compiler of claim 40, wherein the elaborator comprises: an examiner configured to examine a plurality of modules; a marker configured to mark at least one child module; a root module configured to be identified, if one of the plurality of modules is unmarked; and a determiner configured to determine a hierarchical depth of a plurality of unmarked modules, if more than one of the plurality of modules is unmarked.

60. The compiler of claim 40, wherein the cycle-based design represents a memory.

61. The compiler of claim 60, wherein the compiler partitions the memory among a plurality of memory elements in a target system.

62. The compiler of claim 40, wherein the cycle-based design has a plurality of bit level operations, and wherein the compiler generates executable code to evaluate the plurality of bit level operations simultaneously.

63. A computer based simulation system to compile a cycle-based design, comprising: a processor; a memory; an input means; a display device; and software instructions stored in the memory for enabling the computer system under control of the processor, to perform: generating a parsed cycle-based design from the cycle-based design; elaborating the parsed cycle-based design to an annotated syntax tree of component objects constituting the cycle-based design; translating the annotated syntax tree to an intermediate form; and converting the intermediate form to an executable form.

64. A computer based simulation system to compile a cycle-based design, comprising: a processor; a memory; an input means; a display device; and software instructions stored in the memory for enabling the computer system under control of the processor, to perform: generating a parsed annotated syntax tree of component objects constituting the cycle-based design; inferring a logic type from parsed annotated syntax tree for each of a plurality of logic components; elaborating the plurality of logic components to construct a design logic comprising a hierarchical design tree and a flattened design connectivity; levelizing the design logic to schedule execution order of logical components using the flattened design connectivity; translating the parsed annotated syntax tree and levelized flattened design connectivity into an intermediate form operation; assigning each intermediate form operation to an execution processor; ordering of the intermediate form operation within the assigned execution processor; generating routing instructions for a message passing instruction to traverse a multiprocessor system; converting the intermediate form operation into an annotated symbol table; and converting the intermediate operation into executable form.

65. A computer based simulation system for levelization of a cycle-based design, comprising: a processor; a memory; an input means; a display device; and software instructions stored in the memory for enabling the computer system under control of the processor, to perform: collecting a plurality of simulated components by a logic type; identifying a design constraint violation in the cycle-based design; and sorting the plurality of simulated components according to the logic type into a component list; wherein sorting determines an execution order of the plurality of simulated components whereby each of the plurality of simulated components are evaluated only once per simulation clock cycle.

66. An apparatus for compiling a cycle-based design in a simulation system comprising: means for generating a parsed cycle-based design from the cycle-based design; means for elaborating the parsed cycle-based design to an annotated syntax tree of component objects constituting the cycle-based design; means for translating the annotated syntax tree to an intermediate form; and means for converting the intermediate form to an executable form.

67. An apparatus for compiling a cycle-based design in a simulation system comprising: means for generating a parsed annotated syntax tree of component objects constituting the cycle-based design; means for inferring a logic type from parsed annotated syntax tree for each of a plurality of logic components; means for elaborating the plurality of logic components to construct a design logic comprising a hierarchical design tree and a flattened design connectivity; means for levelizing the design logic to schedule execution order of logical components using the flattened design connectivity; means for translating the parsed annotated syntax tree and levelized flattened design connectivity into an intermediate form operation; means for assigning each intermediate form operation to an execution processor; means for ordering of the intermediate form operation within the assigned execution processor; means for generating routing instructions for a message passing instruction to traverse a multiprocessor system; means for converting the intermediate form operation into an annotated symbol table; and means for converting the intermediate operation into executable form.

68. An apparatus for levelization of a cycle-based design in a simulation system, comprising means for collecting a plurality of simulated components by a logic type; means for identifying a design constraint violation in the cycle-based design; and means for sorting the plurality of simulated components according to the logic type into a component list; wherein sorting determines an execution order of the plurality of simulated components whereby each of the plurality of simulated components are evaluated only once per simulation clock cycle.

Description

BACKGROUND OF INVENTION

The invention relates to simulation of microprocessor performance. Modern high performance microprocessors have an ever-increasing number of circuit elements and an ever-rising clock frequency. Also, as the number of circuits that can be used in a CPU has increased, the number of parallel operations has risen. Examples of efforts to create more parallel operations include increased pipeline depth and an increase in the number of functional units in super-scalar and very-long-instruction-word architectures. As CPU performance continues to increase, the result has been a larger number of circuits switching at faster rates. Thus, from a design perspective, important considerations such as the time needed to complete a simulation and the time needed to debug a CPU must be taken into account.

As each new CPU design uses more circuit elements, each often operating at increased frequencies, the time required to simulate the design increases. Due to the increased time for simulation, the number of tests, and consequently the test coverage, decreases. In general, the result has been a dramatic increase in the logic errors that escape detection before the CPU is manufactured.

After a CPU prototype is initially manufactured and failure modes are uncovered, the time required to determine failure mechanisms is generally increasing due to the increased CPU complexity. Failure modes may be the result of logic errors or poor manufacturability of a circuit element. In both cases, circuit simulation helps to confirm or refute the existence of a logic error. If a logic error does not exist, the manufacturability of a circuit element may be the root cause. Even after a logic error failure mechanism is discovered and a solution is proposed, the time required to satisfactorily determine that the proposed solution fixes the logic error and does not generate any new logic errors has increased. Circuit simulation is key to the design and debugging of increasingly complex and faster CPUs.

CPU simulation may occur at a "switch-level." Switch-level simulations typically include active circuit elements (e.g., transistors) and passive circuit elements (e.g., resistors, capacitors, and inductors). A typical switch-level circuit simulator is "SPICE", which is an acronym for Simulation Program with Integrated Circuit Emphasis. SPICE typically models each element using an equation or lookup table. SPICE can model accurately the voltage and/or current of each circuit element across time.

CPU simulation also may occur at a "behavioral level." Behavioral level simulations typically use a hardware description language (HDL) that determines the functionality of a single circuit element or group of circuit elements. A typical behavioral level simulation language is "Verilog", which is an Institute of Electrical and Electronics Engineers standard. Verilog HDL uses a high-level programming language to describe the relationship between the input and output of one or more circuit elements. The Verilog HDL describes on what conditions the outputs should be modified and what effect the inputs have. Verilog HDL programs may also be used for logic simulation at the "register transfer level" (RTL).

Using the Verilog HDL, for example, digital systems are described as a set of modules. Each module has a port interface, which defines the inputs and outputs for the module. The interface describes how the given module connects to other modules. Modules can represent elements of hardware ranging from simple gates to complete systems. Each module can be described as an interconnection of sub-modules, as a list of terminal elements, or a mixture of both. Terminal elements within a module can be described behaviorally, using traditional procedural programming language constructs such as "if" statements and assignments, and/or structurally as Verilog primitives. Verilog primitives include, for example, truth tables, Boolean gates, logic equation, and pass transistors (switches).

HDL languages such as Verilog are designed for efficient representation of hardware designs. Verilog has support for handling signals of arbitrary widths, not only for defining and using an arbitrary width signal, but for treating any sub-field of such a signal as a signal in its own right.

Cycle-based logic simulation is applicable to synchronous digital systems and may be used to verify the functional correctness of a digital design. Cycle-based simulators use algorithms that eliminate unnecessary calculations to achieve improved performance in verifying system functionality. Typically, in a cycle-based logic simulator the entire system is evaluated once at the end of each clock cycle. Discrete component evaluations and re-evaluations are typically unnecessary upon the occurrence of every event.

HDL simulations may be event-driven or cycle-based. Event-driven simulations propagate a change in state from one set of circuit elements to another. Event-driven simulators may record relative timing information of the change in state so that timing and functional correctness may be verified. Cycle-based HDL simulations also simulate a change in state from one set of circuit elements to another. Cycle-based HDL simulations, however, evaluate the state of the system once at the end of each clock cycle. While specific intra-cycle timing information is not available, simulation speed is improved.

HDL simulations may be executed on reconfigurable hardware, such as a field programmable gate array (FPGA) chip. The FPGA allows dedicated hardware to be configured to match the HDL code. FPGA hardware provides a method to improve the simulation time. As the design changes, the time required to reconfigure the FPGA arrangement may prohibit many iterations. Also, the number of FPGA chips required for complex designs may be relatively large.

HDL simulations also may be executed on general purpose processors. General purpose processors, including parallel general purpose processors, are not designed specifically for HDL simulations. HDL simulations require a large number of operations of inputs and outputs that use bit-wise operations.

Large logic simulations are frequently executed on parallel or massively parallel computing systems. For example, parallel computing systems may be specifically designed parallel processing systems or a collection, or "farm," of connected general purpose processing systems. FIG. 1 shows a block diagram of a typical parallel computing system (100) used to simulate an HDL logic design. Multiple processor arrays (112, 113, 129) are available to simulate the HDL logic design. A host computer (116), with associated data store (117), controls a simulation of the logic design that executes on one or more of the processor arrays (112, 113, 129) through an interconnect switch (118). The processor arrays (112, 113, 129) may be a collection of processing elements or multiple general purpose processors. The interconnect switch (118) may be a specifically designed interconnect or a general purpose communication system, for example, an Ethernet network.

A general purpose computer (120) with a human interface (122), such as a GUI or a command line interface, together with the host computer (116) support common functions of a simulation environment. These functions typically include an interactive display, modification of the simulation state, setting of execution breakpoints based on simulation times and states, use of test vectors files and trace files, use of HDL modules that execute on the host computer and are called from the processor arrays, check pointing and restoration of running simulations, the generation of value change dump files compatible with waveform analysis tools, and single execution of a clock cycle.

SUMMARY OF INVENTION

In general, in one aspect, the invention relates to a method for compiling a cycle-based design. The method comprises generating a parsed cycle-based design from the cycle-based design, elaborating the parsed cycle-based design to an annotated syntax tree, translating the annotated syntax tree to an intermediate form, and converting the intermediate form to an executable form.

In general, in one aspect, the invention relates to a method for compiling a cycle-based design. The method comprises generating a parsed cycle-based design from the cycle-based design, elaborating the parsed cycle-based design to an annotated syntax tree, translating the annotated syntax tree to an intermediate form, converting the intermediate form to an executable form, representing the cycle-based design in an annotated symbol table, levelizing the annotated syntax tree, sorting the annotated syntax tree, detecting a procedure call outside the cycle-based design, and recording in a data structure required at run time to interpret the procedure call.

In general, in one aspect, the invention relates to a method for compiling a cycle-based design. The method comprises generating a parsed annotated syntax tree from the cycle-based design, inferring a logic type from parsed annotated syntax tree for each of a plurality of logic components, elaborating the plurality of logic components to construct a design logic comprising a hierarchical design tree and a flattened design connectivity, levelizing the design logic to schedule execution order of logical components using the flattened design connectivity, translating the parsed annotated syntax tree and levelized flattened design connectivity into an intermediate form operation, assigning each intermediate form operation to an execution processor, ordering of the intermediate form operation within the assigned execution processor, generating routing instructions for a message passing instruction to traverse a multiprocessor system, converting the intermediate form operation into an annotated symbol table, and converting the intermediate operation into executable form.

In general, in one aspect, the invention relates to a method for levelization of a cycle-based design. The method comprises collecting a plurality of simulated components by a logic type, identifying a design constraint violation in the cycle-based design, and sorting the plurality of simulated components according to the logic type into a component list. Sorting determines an execution order of the plurality of simulated components whereby each of the plurality of simulated components are evaluated only once per simulation clock cycle.

In general, in one aspect, the invention relates to a compiler. The compiler comprises a design analyzer configured to generate a parsed cycle-based design from a cycle-based design, a design elaborator configured to expand the parsed cycle-based design to an annotated syntax tree, a translator configured to translate the annotated syntax tree to an intermediate form, and a code generator configured to convert the intermediate form to an executable form.

In general, in one aspect, the invention relates to a computer system to compile a cycle-based design. The computer system comprises a processor, a memory, an input means, a display device, and software instructions. The software instructions are stored in the memory for enabling the computer system under control of the processor, to perform generating a parsed cycle-based design from the cycle-based design, elaborating the parsed cycle-based design to an annotated syntax tree, translating the annotated syntax tree to an intermediate form, and converting the intermediate form to an executable form.

In general, in one aspect, the invention relates to a computer system to compile a cycle-based design. The computer system comprises a processor, a memory, an input means, a display device, and software instructions. The software instructions are stored in the memory for enabling the computer system under control of the processor, to perform generating a parsed annotated syntax tree from the cycle-based design, inferring a logic type from parsed annotated syntax tree for each of a plurality of logic components, elaborating the plurality of logic components to construct a design logic comprising a hierarchical design tree and a flattened design connectivity, levelizing the design logic to schedule execution order of logical components using the flattened design connectivity, translating the parsed annotated syntax tree and levelized flattened design connectivity into an intermediate form operation, assigning each intermediate form operation to an execution processor, ordering of the intermediate form operation within the assigned execution processor, generating routing instructions for a message passing instruction to traverse a multiprocessor system, converting the intermediate form operation into an annotated symbol table, and converting the intermediate operation into executable form.

In general, in one aspect, the invention relates to a computer system for levelization of a cycle-based design. The computer system comprises a processor, a memory, an input means, a display device, and software instructions. The software instructions are stored in the memory for enabling the computer system under control of the processor, to perform collecting a plurality of simulated components by a logic type, identifying a design constraint violation in the cycle-based design, and sorting the plurality of simulated components according to the logic type into a component list. Sorting determines an execution order of the plurality of simulated components whereby each of the plurality of simulated components are evaluated only once per simulation clock cycle.

In general, in one aspect, the invention relates to an apparatus for compiling a cycle-based design. The apparatus comprises means for generating a parsed cycle-based design from the cycle-based design, means for elaborating the parsed cycle-based design to an annotated syntax tree, means for translating the annotated syntax tree to an intermediate form, and means for converting the intermediate form to an executable form.

In general, in one aspect, the invention relates to an apparatus for compiling a cycle-based design. The apparatus comprises means for generating a parsed annotated syntax tree from the cycle-based design, means for inferring a logic type from parsed annotated syntax tree for each of a plurality of logic components, means for elaborating the plurality of logic components to construct a design logic comprising a hierarchical design tree and a flattened design connectivity, means for levelizing the design logic to schedule execution order of logical components using the flattened design connectivity, means for translating the parsed annotated syntax tree and levelized flattened design connectivity into an intermediate form operation, means for assigning each intermediate form operation to an execution processor, means for ordering of the intermediate form operation within the assigned execution processor, means for generating routing instructions for a message passing instruction to traverse a multiprocessor system, means for converting the intermediate form operation into an annotated symbol table, and means for converting the intermediate operation into executable form.

In general, in one aspect, the invention relates to an apparatus for levelization of a cycle-based design. The apparatus comprises means for collecting a plurality of simulated components by a logic type, means for identifying a design constraint violation in the cycle-based design, and means for sorting the plurality of simulated components according to the logic type into a component list. Sorting determines an execution order of the plurality of simulated components whereby each of the plurality of simulated components are evaluated only once per simulation clock cycle.

Other aspects and advantages of the invention will be apparent from the following description and the appended claims.

BRIEF DESCRIPTION OF DRAWINGS

FIG. 1 shows a typical parallel computer system.

FIG. 2 shows a parallel computer system in accordance with an embodiment of the present invention.

FIG. 3 shows a process of preparing a simulation of a cycle-based logic design to run on a cycle-based system in accordance with an embodiment of the present invention.

FIG. 4 is a flow diagram of a simulation compiler in accordance with an embodiment of the invention.

FIG. 5 is a flow diagram of design analysis in accordance with an embodiment of the invention.

FIG. 6 is a flow diagram of a module compiler process in accordance with an embodiment of the invention.

FIG. 7 is a flow diagram of a design elaboration process in accordance with an embodiment of the invention.

FIGS. 8 and 9 illustrate the insertion of a "phantom gate" in accordance with one embodiment of the present invention.

FIG. 10 is a flow diagram of a levelization process in accordance with an embodiment of the invention.

FIG. 11 illustrates a combinatorial logic loop.

FIG. 12 is a flow diagram of a translator in accordance with an embodiment of the invention.

FIG. 13 is a timing diagram of a multiple clock domain simulation clock in accordance with an embodiment of the invention.

FIG. 14 is a flow diagram of a clock generation implementation in accordance with an embodiment of the invention.

FIG. 15 is a flow diagram of a code generation process in accordance with an embodiment of the invention.

FIG. 16 is a flow diagram of a process for performing scheduling in accordance with an embodiment of the invention.

DETAILED DESCRIPTION

Specific embodiments of the invention will now be described in detail with reference to the accompanying figures. Like elements in the various figures are denoted by like reference numerals for consistency.

The present invention is a method and apparatus for compiling a cycle-based design in a simulation system. In the following detailed description of the invention, numerous specific details are set forth in order to provide a more thorough understanding of the invention. However, it will be apparent to one of ordinary skill in the art that the invention may be practiced without these specific details. In other instances, well-known features have not been described in detail to avoid obscuring the invention.

A compiler provides a method and apparatus by which instructions to a computer are transformed from a human understandable representation to a computer understandable representation. An embodiment of the present compiler is configured to receive cycle-based design instructions. One embodiment receives HDL instructions in the Verilog language. Once the HDL instructions are received, the compiler is configured to transform the HDL instructions into a form, which can execute in a computing environment. In one embodiment, the computing environment is highly paralleled, which allows the environment to handle the code generated by the compiled HDL instructions efficiently.

Embodiment of Computer Execution and Simulation System Environment

Before describing in further detail cycle-based computation in a simulation system, a computer execution environment and a class of simulation systems (e.g., multiple instruction, multiple data (MIMD)) used with one or more embodiments of the invention is described below.

In an embodiment of the present invention, the computer execution environment may use execution processors to execute execution processor code on a general purpose computer, such as a SPARC.TM. workstation produced by Sun Microsystems, Inc., or specialized hardware for performing cycle-based computations, e.g. a Phaser system.

The system of the invention is a massively parallel, cycle-based computing system. The system uses an array of execution processors arranged to perform cycle-based computations. One example of cycle-based computation is simulation of a cycle-based design written in a computer readable language, such as HDL (e.g., Verilog, etc.), or a high-level language (e.g., Occam, Modula, C, etc.).

FIG. 2 shows exemplary elements of a system (200), in accordance with one or more embodiments of the present invention. Cycle-based computation, such as a logic simulation on the system (200), involves one or more host computers (202, 204) managing the logic simulation(s) executing on one or more system boards (220, 222, 224). Each system board contains one or more Application Specific Integrated Circuits (ASIC). Each ASIC contains multiple execution processors. The host computers (202, 204) may communicate with the system boards (220, 222, 224) using one of several pathways. The host computers (202, 204) include interface hardware and software as needed to manage a logic simulation. A high speed switch (210) connects the host computers (202, 204) to the system boards (220, 222, 224). The high speed switch (210) is used for loading and retrieval of state information from the execution processors located on ASICs on each of the system boards (220, 222, 224). The connection between the host computers (202, 204) and system boards (220, 222, 224) also includes an Ethernet connection (203). The Ethernet connection (203) is used for service functions, such as loading a program and debugging. The system also includes a backplane (207). The backplane (207) allows the ASICs on one system board to communicate with the ASICs of another system board (220, 222, 224) without having to communicate with an embedded controller located on each system board. Additional system boards may be added to the system by connecting more system boards to the backplane (207).

Simulation of the cycle-based logic design in the cycle-based system occurs on a processor array in two modes: a run mode segment and a control mode segment. Run mode segment is the basic simulation running mode. In the run mode segment, there is no communication necessary between the host and simulation system besides basic runtime control and the execution of any user-provided C coded routines. In the control mode segment, the host sends commands to the simulation hardware and waits for responses. This mode is typically used in debugging and initialization of the simulation system.

A processor array may exist as specialized hardware, such as a massively parallel computer system designed for simulation using cycle-based computation, or as part of an appropriate computer system, such as a SPARC.TM. workstation produced by Sun Microsystems, Inc. Cycle-based logic design may also be simulated on a processor array, or a portion of the processor array. Thus, references herein to the processor array may refer to a portion of the processor array, or to multiple processor arrays.

In accordance with one or more embodiments of the present invention, FIG. 3 shows a process of preparing a simulation of a cycle-based logic design to run on a Cycle-based system. The process includes three separate phases. The first phase is a verification phase (324). This phase includes a style checker (326), which parses and checks high level design code of a program (329) representing the cycle-based design. The program is checked for adherence to a cycle-based design standard, e.g., synchronous logic design, no combinatorial logic loops, etc. An error action during this phase results from nonconformance to the defined cycle-based design standards. A clock file input (328) defines clocks cycles for the simulation. The output of the verification phase (324) produces a verified cycle-based design.

The second phase is a compilation phase (330), which receives the verified cycle-based design as input from the verification phase (324). The compilation phase (330) uses a translation component, such as a compiler (332), to compile the verified cycle-based design of the verification phase (324). The compiler (332) decomposes the verified cycle-based design into execution processor code that may be executed in parallel on a processor array of the Cycle-based system by one or more execution processors. The compiler also produces routing tables and other information, such as routing processor code, interface code and an annotated symbol table. Routing tables enable static routing of messages sent during run mode segment. An annotation symbol table involves recording physical locations where the values of nets and registers have been stored, so that user interface and Programming Language Interface (PLI) routines may access values of nets and registers during runtime. Input files (334), e.g., PLI and TVI files, etc., provide functionality for items such as system task calls and trace vectors. A user system task call enables a host computer to execute an appropriate portion of a simulation, A trace vector typically contains test input data and expected outputs for testing. Errors in cycle-based designs input into the compiler (332) causes an error action. The compiler and code generation includes a scheme for routing of messages and placement of compiled execution processor code so that there is some optimization in the choice of which of the parallel execution processors of the simulation hardware to use for certain tasks. This is because the time required for delivery of a message from one processor to another depends upon the data connection component between those execution processors, (i.e., the number of hops the message takes in traversing the data connection component from source processor to destination processor). One skilled in the art can appreciate that compilation of a program may be targeted to a specific execution environment and/or platform, e.g., Phaser system hardware or an appropriate computer, such as a SPARC.TM. workstation produced by Sun Microsystems, Inc.

The third phase is the simulation phase (336), which receives input in the form of execution processor code from the compilation phase (330). A PHaser SIMulator (338) (PHSIM) typically runs on a host computer and controls and monitors execution of simulations executing on the Cycle-based system. The host computer includes such hardware and software mechanisms as are needed to manage simulation, e.g., loading execution processor code onto a processor array. PHSIM (338) enables user interaction with a simulation using a graphical user interface (GUI) or with a command line interface, interactive modification of simulation state, breakpointing, test vector use, system task functionality, signal tracing, single-stepping on clock cycles, and other functionalities. A simulation cycle begins with one or more simultaneous clock edges and completes when every dependent event has completed evaluation. The simulation phase (336) may run on system hardware (340), which is designed for cycle-based computation, or on an appropriate computer, such as a SPARC.TM. workstation (342) produced by Sun Microsystems, Inc.

The computer systems described above are for purposes of example only. An embodiment of the invention may be implemented in any type of computer system or programming or processing environment.

Compiler

As illustrated in FIG. 4, in one or more embodiments of the invention, the simulation compiler includes a design analyzer (401), a translator (403), and a code generator (405). The design analyzer 401 receives input in the form of HDL source files (400) (e.g., Verilog modules) and generates a high-level representation (402) of the simulation design, ordered for single-pass execution in a cycle-based system. This high-level representation (402) may include, for example, a component reference data structure (i.e., an object-oriented data structure) containing shared information for component types; a component instance data structure containing information for specific component instances as well as flattened connectivity information, components (instances) collected by type, a list of simulation variables; and a sorted component list, in which the sort order corresponds to the execution order for single-pass, cycle-based execution. The translator (403) receives the high level representation (402) and translates the operations into a sequential representation (or intermediate form) (404) that describes the simulation operations. The sequential representation (404) is transformed by code generation process (405) into executable code (406) for a target simulation system.

It will be apparent to one skilled in the art that the techniques described in association with the design analyzer (401) render an elaborated logic design suitable for use with all classes of computer-aided logic design tools (e.g., the cycle-based simulation system described herein, a power-analysis tool, or a fault-grading tool).

Furthermore, the translator (403) may direct execution of the program through a variety of mechanisms, including production of a sequential representation (404) described herein, production of a program in a language such as C, production of assembly language or binary instructions for the target simulation system, or by direct interpretation of the prescribed operations.

The design analyzer (401), translator (403), and code generator (405), mechanisms may be used with any target simulation system. For example, the sequential representation (404) may be transformed into a sequential program for execution on a general purpose or application specific computer, or may be partitioned into a plurality of threads for execution on an MIMD simulation system.

Design Analyzer

The flow of an embodiment of the design analyzer (401) is illustrated in the flow diagram of FIG. 5. One or more HDL modules (500) are provided to HDL parser (501). The modules are then parsed to generate the component reference data structure (502). Component reference data structure (502) contains, for example, one component object definition for each module submitted. Those component object definitions provide the basis for component instantiation in later stages. The module compiler (503) expands the object definitions from reference data structure (502) and extracts the logic modeling and pin information for each component. A logic inference function is applied to each component to determine the logic content. A complete reference data structure (504) in a high-level abstract representation, referred to herein as Hierarchical Intermediate Form (HIF) or Verilog Intermediate Form (VIF), is generated after the module compilation.

In the design elaboration phase (505), the compiled design modules are linked together into a hierarchical design tree, from which instances of component objects are recursively generated. Binding is performed and simulation variables are created for local nets. The output of the design elaboration phase is an elaborated instance data structure (506) with flattened connectivity information. Design levelization phase (507) operates upon instance data structure (506) to collect all components by logic type and formulates a hierarchical design tree, a sorted list of components in execution order, a list of simulation variables, and a flattened design connectivity (508). The following description discusses the above compilation stops in greater detail.

Module Compilation

The module compiler (503) operates upon the initial design reference data structure (502) to build a more complete logic model for each module, now expressed as a component object type. The module compilation process, in accordance with one or more embodiments of the invention, is illustrated in the flow diagram of FIG. 6.

The module compilation process begins in Step 600 with design expansion. Design expansion includes three operations: function/task inlining (Step 600A), complex expression translation (Step 600B), and loop unrolling (Step 600C). Function inlining (Step 600A) involves replacing function calls within each module with the actual code statements of the function. The function is thus evaluated explicitly "inline" with the rest of the module, removing any branching entailed by the original function call. Take, for example, the following function written in pseudo-code:

TABLE-US-00001 function increment (i) begin return i+1; end.

Inlining would then transform the statement:

TABLE-US-00002 assign x = increment (y). into: assign x = y+1;

Complex expression expansion (Step 600B) addresses the issue of complex expressions within module instantiations. For example, given a module "decrement( )" defined as:

TABLE-US-00003 decrement (x,y) assign x = y-1 end

and a module instantiation as follows:

TABLE-US-00004 decrement (d, a & b & c)

an example of expression expansion is to replace the module instantiation with the following code:

TABLE-US-00005 assign temp = a & b & c; decrement (d, temp);

This expansion facilitates later binding/aliasing optimizations during the elaboration phase. When binding is performed based upon module port information, bound variables may share common storage. For example, when two wire references are bound together, the wires may be implemented with separate aliases to a common simulation variable. However, complex expressions complicate the binding issue, as pins cannot be bound to, and share storage with, complex expressions. Thus, the use of a temporary component simplifies binding operations and facilitates storage sharing. In the above example, without expansion, pin y would be bound to the complex expression (a & b & c). After expression expansion, however, pin y would be bound to the temporary variable "temp" rather than the complex expression, permitting aliasing optimizations.

In Step 600C, all loop structures within a module are unrolled for inline evaluation. For example, given a set of statements, A, B, C coded to execute within a loop for m iterations, the loop would be replaced with m inline sets of statements A, B, C. This step removes any backward branching due to loop structures.

A component models a hardware device in HDL. A component is also a basic concurrent execution unit in simulation. In Verilog, a component is defined to be a gate, a primitive, a continuous assign statement, or a process. A component pin is defined as a terminal point of the component that connects to the external environment. If the component is a primitive, the component pins are the primitive pins. If the component is a continuous assign statement, the component pins are the Verilog variables or part selected variables of the statement left hand side (LHS) and right hand side (RHS) expressions. If the component is a process, the component pins are the Verilog variables or part selected variables of each statement in the process, except the variables that are used only internally to the process.

Still referring to FIG. 6 and following design expansion (600), the component modeling information is extracted from the component in Step 601. This extraction step includes, for example, the extraction of pin information from the component. Pin information may be gathered from the arguments or expressions of the component. For example, x and y may be variables in an expression of a continuous assign statement (e.g., assign x=y). The type of pin (e.g., in, out, inout, etc.) may be determined from the internal code of the component.

In Step 602, the software analyzes the statement content of the component to infer the logic content of the component. The object is to classify a component as a sequential logic component or a combinatorial logic component. A sequential logic component is defined as a component that can store logic states across cycle boundaries. If not, the component is a combinatorial logic component.

In Step 602, logic inferences are drawn from component statements to determine whether a component may be classified as a sequential logic component or a combinatorial logic component. If a component is classified as a sequential logic component, the clock pin, data input pin (D) and data output pin (Q) are identified. If the component is a combinatorial component, the input/output pin dependencies are determined. Once the sequential/combinatorial logic classification is performed on a component reference, the classification for any component instances referencing that component is also known. Similarly, other information obtained during the steps of module compilation is applicable to all instances of the modules in the simulation design. The reference data structure contains module information in a high-level hierarchical intermediate form (HIF), such as a collection of a reference simulation component objects.

Abstract Class Descriptions

A number of abstract object class definitions are provided in one embodiment of the invention. These include vSobj Class, vComponent Class, and vExpr Class. vSobj Class objects represent possible candidates for a simulation object in the simulation engine. A simulation object is a simulation variable that is used to store logic state in the simulation engine. This could represent a simulation net or a state variable in the compiled desi