Method and apparatus for controlling a system using hierarchical state machines

• US 6,374,144 B1
• Filed: 12/22/1998
• Issued: 04/16/2002
• Est. Priority Date: 12/22/1998
• Status: Expired due to Term

• Current Assignee: Varian Semiconductor Equipment Associates Incorporated (Applied Materials Incorporated)
• Original Assignee: Varian Semiconductor Equipment Associates Incorporated (Applied Materials Incorporated)
• Inventors: Callahan, William G., Parisi, Nick A., Viviani, Gary L.
• Primary Examiner(s): Grant, William
• Assistant Examiner(s): RODRIGUEZ, PAUL L
• Application Number:
  US09/219,584
• Time in Patent Office: 1,211 Days
• Field of Search: 700/8, 700/9, 700/12, 700/19, 700/20, 700/96, 700/121, 700/14
• US Class Current: 700/12
• CPC Class Codes: G05B 19/045 using logic state machines, consisting only of a memory or a programmable logic device containing the logic for the controlled machine and in which the state of its outputs is dependent on the state of its inputs or part of its own output states, e.g. binary decision controllers, finite state controllers

Abstract

A method and apparatus for controlling complex systems includes hierarchically coupled subsystems representing operative functions of the system. The hierarchically coupled subsystems are coupled to collect command data from a user and signal data from the system. Each subsystem may include one or more state machines and one or more digital signal processing and conditioning unit (DSPCU) objects. The DSCPU objects accept process commands and convert control system signals into states for further processing by the state machines. Associated with the DSPCUs of each subsystem is a data flow diagram for dictating an order of flow of commands and signals at the DSPCUs. A method of controlling the system represented by the hierarchically coupled subsystems schedules the execution of the subsystems according to an execution protocol. According to the execution protocol, for each cycle of execution of the system, the hierarchically coupled subsystems are first analyzed in ascending order of the hierarchy, with DSPCU objects being analyzed in data flow order before state machine objects, and then in descending order of the hierarchy, with state machine objects being analyzed before DSPCU objects. During the ascending execution of the hierarchy, signal data received from only those objects that are relatively lower in the hierarchy are used to update the state of any given object. During the descending execution of the hierarchy, command data received from only those objects that are relatively higher in the hierarchy are considered when updating the state of any given object.

Claims

1. A system for controlling a device having a plurality of interconnected subsystems coupled in a hierarchy, with subsystems at a given level in the hierarchy being included in a subsystem at an immediately higher level of the hierarchy, the system comprising:

a plurality of hierarchically coupled state machines, with at least one state machine associated with each of the hierarchically coupled subsystems;

means for evaluating the states of the state machines for each of the hierarchically coupled subsystems in an order defined by the hierarchy; and

a scheduler for scheduling an order of execution of the plurality of subsystems during operation of the controlled device and determining the order of execution of the subsystems in the hierarchy in response to a total execution time of each of the subsystems of the device and in response to a selected number of cycles for execution of the device,

wherein a time period is associated with each of the subsystems for indicating how often the associated subsystem is to be evaluated during operation of the controlled device, and wherein the order of execution of the subsystems is determined in response to the associated time period of each of the subsystems.

2. The system according to claim 1 further comprising, for each of the hierarchically coupled subsystems:

a digital signal processing and conditioning object, coupled to the at least one state machine, for transferring signals into and out of the associated subsystem; and

a user interface, coupled to the hierarchically coupled state machines, for transferring commands to the hierarchically coupled state machines.

3. The system according to claim 2, further comprising:

a memory for storing signals associated with each of the plurality of subsystems;

means for evaluating the plurality of hierarchically coupled state machines responsive to signals stored in the memory, wherein state machines that are relatively lower in the hierarchy are evaluated before state machines that are relatively higher in the hierarchy, and wherein the state machines are evaluated using state data received only from state machines relatively lower in the hierarchy and from data flowing into the digital signal processing and conditioning objects;

means for receiving commands from an external user; and

means for evaluating the plurality of hierarchically coupled state machines responsive to the commands from the external user, wherein state machines that are relatively higher in the hierarchy are evaluated before state machines that are relatively lower in the hierarchy, and wherein state machines are evaluated using commands received only from state machines that are relatively higher in the hierarchy.

4. The system according to claim 1, wherein the means for evaluating the states of the state machines operates to evaluate state machines that are relatively lower in the hierarchy before the evaluation of state machines that are relatively higher in the hierarchy.

5. The system according to claim 4, wherein the means for evaluating the states of the state machines evaluates the state of a state machine using state data received only from state machines that are relatively lower in the hierarchy.

6. The system according to claim 4, wherein the means for evaluating the states of the plurality of state machines evaluates the state of a state machine using command data received only from state machines that are relatively higher in the hierarchy.

7. The system according to claim 1, wherein each of the plurality of hierarchically coupled state machines comprises at least one error state for identifying an error in the associated subsystem.

8. The system according to claim 1, wherein each of the plurality of hierarchically coupled state machines further comprises at least one transitional state for identifying a changing state of the associated subsystem.

9. The system according to claim 1, wherein each of the plurality of hierarchically coupled state machines further comprises at least one terminal state for indicating a fixed state of the associated subsystem.

10. The system according to claim 1, wherein each of the plurality of hierarchically coupled subsystems further comprises a data flow diagram, and wherein the at least one state machine and data flow diagram are provided to indicate the operative state of the associated subsystem.

11. The system according to claim 10, wherein the scheduler further comprises:

a first ordered list of state machine pointers to state machines of the hierarchical coupled subsystem, the state machine pointers ordered in ascending hierarchical order of the associated subsystems;

a second ordered list of data flow pointers to the data flow diagrams of the hierarchically coupled subsystem, the data flow pointers being ordered in data flow order and in ascending hierarchical order of the associated subsystems;

an upward execution list, comprising the second list followed by the first list; and

a downward execution list, comprising the first list in reverse order followed by the second list.

12. The system according to claim 11, wherein each of the time periods associated with each of the subsystems is selected from a set of available time periods that are factors of a total number of time periods used for execution of the device.

13. The system according to claim 12, further comprising:

a plurality of sets of upward update lists having a plurality of entries, the sets of upward update lists corresponding in number to a number of time periods in the set of available time periods, each entry of the set of upward update lists for storing a pointer to one of the entries in the upward execution list;

a plurality of sets of downward update lists having a plurality of entries, the sets of downward update lists corresponding in number to a number of time periods in the set of available time periods, each entry of the set of downward update lists for storing a pointer to one of the entries in the downward execution list; and

means for copying the state machine pointers and data flow pointers from the upward execution lists and the downward execution lists to one or more of the plurality of upward update lists and downward update lists, respectively, responsive to an allocated time period for the execution of the subsystem associated with the pointer.

14. The system according to claim 13, further comprising:

a plurality of upward scheduled lists having a plurality of entries, the upward scheduled lists corresponding in number to the total number of time periods used for execution of the device, each of the entries of the upward scheduled lists for storing pointers to the upward update lists;

a plurality of downward scheduled lists having a plurality of entries, the downward scheduled lists corresponding in number to the number of time periods used for execution of the device, each of the entries of the downward scheduled lists for storing pointers to the downward update lists; and

means for copying pointers from the plurality of upward update lists to the plurality of upward scheduled lists, and for copying pointers from the plurality of downward update lists to the plurality of downward scheduled lists, wherein the pointers are selected for copying to an associated one of the plurality of scheduled lists according to the time period of their associated subsystem.

15. The system according to claim 14, further comprising:

a master upward list comprising a plurality of entries corresponding in number to a total number of time periods for execution of the device, the master upward list for storing pointers to subsystems that are analyzed at each associated time period;

a master downward list comprising a plurality of entries corresponding in number to the total number of time periods for execution of the device, the master downward list for storing pointers to subsystems that are executed during the associated time period;

a timer for measuring and controlling the time period; and

means, coupled to the timer, the master upward list, the master downward list, the plurality of upward scheduled lists and the plurality of downward scheduled lists, for storing pointers to the plurality for upward scheduled lists in the master upward list and for storing pointers to the plurality of downward scheduled lists in master downward list responsive to the measured and controlled time period.

16. The method for analyzing a system having a plurality of interconnected subsystems coupled in a hierarchy, with subsystems at a given level in the hierarchy being included in a subsystem at an immediate higher level of the hierarchy, each one of the interconnected subsystems being associated with a corresponding one of a plurality of hierarchically coupled state machines, the method comprising the steps of:

evaluating, for each subsystem, a state of the associated state machine, wherein an order of evaluation of the associated state machines is determined in response to an order defined by the hierarchy of the plurality of interconnected subsystems; and

scheduling the execution of subsystems in the hierarchy of state machines, wherein associated with each of the subsystems is a time period for indicating how often the associated subsystem is to be evaluated, and wherein the step of scheduling includes the step of determining the order of execution of the subsystems in response to the time period of each of the subsystems, and wherein the step of determining the order of execution is firther performed in response to a total execution time of the system.

17. The method according to claim 16 wherein associated with each of the subsystems is a data flow diagram comprising digital signal processing and conditioning objects, and wherein the method further comprises the steps of:

transferring selected external signals into and out of each of the hierarchically coupled subsystems, wherein the external signals that are transferred into and out of each subsystem are those external signals associated with digital signal processing and conditioning objects that are relatively lower in the hierarchy than each state machine; and

transferring commands into each of the hierarchically coupled state machines, wherein the commands transferred into each of the state machines are commands that are received at the each state machine from subsystems that are relatively higher in the hierarchy than the each state machine.

18. The method according to claim 17, wherein the step of evaluating the state of the associated state machine in the order defined by the hierarchy evaluates state machines associated with digital signal processing and conditioning objects that are relatively lower in the hierarchy before the evaluation of state machines associated with digital signal processing and conditioning objects that are relatively higher in the hierarchy.

19. The method according to claim 16, wherein the order of evaluating the state of the state machines is from those state machines associated with subsystems that are relatively lower in the hierarchy to those state machines associated with subsystems that are relatively higher in the hierarchy.

20. The method according to claim 16, wherein the step of evaluating the state of the associated state machine in the order defined by the hierarchy further comprises the steps of:

storing signals received from the plurality of subsystems of the system in a memory;

evaluating state machines associated in an upward direction responsive to the signals stored in the memory, wherein state machines associated with subsystems that are relatively lower in the hierarchy are evaluated before state machines associated with subsystems that are relatively higher in the hierarchy, and wherein each state machine is evaluated using state data received only from state machines associated with subsystems that are relatively lower in the hierarchy than the each state machine;

receiving commands from an external user; and

evaluating the state machines in a downward direction responsive to the commands from the external user, wherein state machines that are associated with subsystems that are relatively higher in the hierarchy are evaluated before state machines that are associated with subsystems that are relatively lower in the hierarchy, and wherein each state machine is evaluated using commands received only from state machines associated with subsystems that are relatively higher in the hierarchy than the each state machine.

21. The method according to claim 20, wherein associated with each of the interconnected subsystems is a data flow diagram, and wherein the step of evaluating the state machines in an upward direction includes the step of evaluating the data flow diagrams of the subsystems in ascending hierarchical order before evaluating the state machines of the associated subsystems in ascending hierarchical order.

22. The method according to claim 21, wherein the step of evaluating the state machines in a downward direction includes the step of evaluating the data flow diagrams of the subsystems in descending hierarchical order after evaluating the state machines of the associated subsystems in descending hierarchical order.

23. The method according to claim 16, wherein each of the state machines comprises at least one error state for identifying an error at the associated subsystem.

24. The method according to claim 16, wherein each of the state machines further comprises at least one transition state for identifying a changing state of the associated subsystem.

25. The method according to claim 16, wherein each of the state machines further comprises at least one terminal state for indicating a fixed state of the associated subsystem.

26. The method according to claim 16, wherein associated with each of the state machines is an error state for indicating an error at the associated subsystem, and wherein the errors for each of the associated subsystems are forwarded to a predetermined level in the hierarchy of subsystems.

27. A control system for controlling a device comprising:

a processor, coupled to the device, the processor comprising;

a memory for storing signals associated with the device, where the signals are received from the device and forwarded to the device during operation of the device;

a hierarchical data structure comprising a plurality of hierarchically interconnected subsystems representative of the operative functions of the device, wherein each of the interconnected subsystems is represented by at least one object;

means for forwarding the signals to the hierarchical data structure;

means, responsive to the signals, for updating states within the hierarchical data structure in a controlled manner, wherein the means for updating the states within the hierarchical data structure in a controlled manner includes means for evaluating states of objects in ascending hierarchical order and in descending hierarchical order during an execution cycle; and

a scheduler, for scheduling the execution of each of the objects of the hierarchical data structure during operation of the device, wherein scheduling is performed in response to an execution protocol of the control system;

wherein each of the at least one objects further includes at least one of either a state machine or a data flow diagram, and wherein the execution protocol of the control system dictates an order of execution of the state machines or data flow diagrams of the hierarchical data structure.

28. The control system according to claim 27, wherein the means for evaluating the states of objects in ascending hierarchical order evaluates the state of each of the objects using information from objects that are relatively lower in the hierarchical data structure than the each object.

29. The control system according to claim 27, wherein the means for evaluating the state of objects in descending hierarchical order evaluates the state of each of the objects using information from objects that are relatively higher in the hierarchical data structure than the each object.

30. The control system according to claim 27, wherein the execution protocol includes four phases of execution comprising an ascending data flow execution phase, an ascending state machine execution phase, a descending state machine execution phase and a descending data flow execution phase.

31. The control system according to claim 27, wherein the device is an ion implantation system.