System for and method of allocating processing tasks of a control program configured to control a distributed control system

• US 6,104,962 A
• Filed: 03/26/1998
• Issued: 08/15/2000
• Est. Priority Date: 03/26/1998
• Status: Expired due to Term

• Current Assignee: Rockwell Technologies, LLC (Teledyne Technologies Incorporated)
• Original Assignee: Rockwell Technologies, LLC (Teledyne Technologies Incorporated)
• Inventors: Sastry, Shivakumar
• Primary Examiner(s): Palys, Joseph E.
• Assistant Examiner(s): Mai, Rijue
• Application Number:
  US09/048,915
• Time in Patent Office: 873 Days
• Field of Search: 700/86, 700/2, 700/3, 700/4, 700/8, 700/9, 700/10, 700/17, 700/20, 700/19, 700/87-89, 700/99, 709/1, 709/100, 709/104, 709/105, 709/201-205, 709/217-219, 709/220, 709/221, 709/222, 709/223, 709/224, 709/225, 709/226, 709/229, 709/251, 714/21, 714/717
• US Class Current: 700/86
• CPC Class Codes: G05B 19/0426 Programming the control sequence
• CPC Class Codes: G05B 2219/23292 Use of model of process, divided in part models with IN, OUT and actuator
• CPC Class Codes: G05B 2219/25086 Assign functions to group of complete or partial cells, modules
• CPC Class Codes: G05B 2219/25232 DCS, distributed control system, decentralised control unit

Abstract

A method and system for allocating programming objects of a control program configured to control a distributed control system having a plurality of distributed control modules. A graph model of the distributed control system is constructed which represents all the possible allocations of the control program'"'"'s virtual programming objects to the processing resources associated with the system'"'"'s control modules. A maximum matching algorithm is applied to the graph model to determine an optimum allocation, which, for instance, may be the allocation that provides the maximum benefit. The system and method also provide for intervention by the user to refine or "tune" the allocation process. Further, the system and method provide for iteratively solving the graph matching problem, thus reducing the computation time for allocating the programming objects of a complex distributed control system

Claims

1. A method for allocating a plurality of programming objects of a control program configured to control a distributed control system, wherein the control system includes a plurality of controller nodes connected to a communications link, and the control program includes program code corresponding to the plurality of programming objects, the plurality of programming objects including virtual objects and non-virtual objects, the method comprising:

identifying logical relationships among the plurality of programming objects;

identifying a processing resource associated with each controller node;

determining possible allocations of the virtual objects to the controller nodes based on at least the identified processing resources and the logical relationships among the plurality of programming objects;

constructing a graph model representing at least a portion of the possible allocations, the graph model including a first set of vertices representing at least a first portion of the virtual objects, a second set of vertices representing the processing resources compatible with the at least first portion of virtual objects, and a set of edges interconnecting the first and second set of vertices; and

applying a maximum matching algorithm to the graph model to determine an allocation of the at least first portion of virtual objects to the controller nodes.

2. The method of claim 1, further comprising:

determining an allocation of the non-virtual objects to the controller nodes; and

partitioning the program code of the control program based on the allocations of the virtual objects and the non-virtual objects.

3. The method of claim 2, wherein a user determines the allocation of the non-virtual objects.

4. The method of claim 1, further comprising assigning a weight to each edge of the set of edges of the graph model, and wherein the maximum matching algorithm is a weighted maximum matching algorithm.

5. The method of claim 4, wherein the magnitudes of the weights assigned to the edges are equal.

6. The method of claim 4, wherein

the magnitude of the weight assigned to each edge interconnecting one of the virtual objects to one of the processing resources represents a benefit associated with allocating that virtual object to that processing resource, and

applying the weighted maximum matching algorithm to the graph model includes determining a matching representing the allocation having an optimum benefit.

7. The method of claim 6, wherein the optimum benefit is the maximum benefit.

8. The method of claim 1, wherein applying the maximum matching algorithm includes iteratively determining a matching until an augmenting path along the set of edges cannot be found.

9. The method of claim 4, further comprising:

defining a weighting function related to one of a cost and a benefit associated with the possible allocations; and

determining the magnitudes of the assigned weights based on the weighting function.

10. The method of claim 9, wherein the weighting function includes at least one tunable parameter and the value of the tunable parameter is selected by a user.

11. The method of claim 10, wherein the tunable parameter represents one of a percentage load balance offset among the processing resources, a percentage utilization of the processing resources, a speed of allocating the virtual objects, and a response time for the distributed control system.

12. The method of claim 1, further comprising:

defining at least one allocation rule,

wherein the possible allocations of the virtual objects are determined further in accordance with the allocation rule.

13. The method of claim 1, wherein identifying the processing resources includes identifying:

a type of microprocessor located at each controller node,

a type of programming object supported by each controller node,

a maximum number of each type of programming object supported by each controller, and

an execution time for each controller node for executing the program code associated with each type of programming object.

14. The method of claim 1, further comprising:

constructing a second graph model representing at least a portion of remaining possible allocations, the second graph model including a first set of vertices representing a second portion of the virtual objects, a second set of vertices representing the processing resources compatible with the second portion of virtual objects, and a set of edges interconnecting the first and second set of vertices; and

applying the maximum matching algorithm to the second graph model to determine an allocation of the second portion of virtual objects to the controller nodes.

15. A method for configuring a distributed control system, wherein the system includes a plurality of control modules communicating via a communications link, and each control module includes a memory circuit for storing program code corresponding to at least one of a plurality of programming objects of a control program configured to control the distributed control system, the method comprising:

identifying logical relationships among the plurality of programming objects;

identifying a processing resource associated with each control module;

determining possible allocations of the programming objects to the control modules based on at least the identified processing resources and the logical relationships among the plurality of programming objects;

constructing a graph model representing at least a portion of the possible allocations, the graph model including a first set of vertices representing at least a first portion of the programming objects, a second set of vertices representing the processing resources compatible with the at least first portion of programming objects, and a set of edges interconnecting the first and second set of vertices;

applying a maximum matching algorithm to the graph model to determine an allocation of the at least first portion of programming objects to the controller nodes;

partitioning the program code of the control program based on the allocation; and

storing the partitioned program code in the memory circuits of the control modules, wherein the program code stored in a particular memory circuit corresponds to the programming object allocated to the respective control module.

16. The method of claim 15, further comprising:

classifying each of the programming objects as one of a virtual object and a non-virtual object, wherein each non-virtual object is associated with a physical component having a physical location in the distributed control system;

identifying the physical location of the physical component associated with each non-virtual object; and

allocating the non-virtual objects to the processing resources based at least on the identified physical locations;

wherein the first set of vertices of the graph model represents virtual objects only.

17. The method of claim 16, wherein the non-virtual objects are allocated by a user.

18. The method of claim 15, further comprising assigning a weight to each edge of the set of edges of the graph model, and wherein the maximum matching algorithm is a weighted maximum matching algorithm.

19. The method of claim 18, wherein the magnitudes of the weights assigned to the edges are equal.

20. The method of claim 18, wherein

the magnitude of the weight assigned to each edge interconnecting one of the programming objects to one of the processing resources represents a benefit associated with allocating that programming object to that processing resource, and

applying the weighted maximum matching algorithm to the graph model includes determining a matching representing an allocation having an optimum benefit.

21. The method of claim 20, wherein the optimum benefit is the maximum benefit.

22. The method of claim 18, further comprising:

defining a weighting function related to one of a cost and a benefit associated with the possible allocations; and

determining the magnitudes of the assigned weights based on the weighting function.

23. The method of claim 15, further comprising:

constructing a second graph model representing at least a portion of remaining possible allocations, the second graph model including a first set of vertices representing a second portion of the virtual objects, a second set of vertices representing the processing resources compatible with the second portion of virtual objects, and a set of edges interconnecting the first and second set of vertices; and

applying the maximum matching algorithm to the second graph model to determine an allocation of the second portion of virtual objects to the controller nodes.

24. A distributed control system, comprising:

a host controller including a memory to store a control program, the control program including program code corresponding to a plurality of programming objects having logical interrelationships; and

a plurality of control modules in communication with the host controller via a communications link, each of the control modules having a processing capability sufficient to execute the program code associated with at least one of the programming objects;

wherein the host controller is configured to determine possible allocations of the programming objects to the control modules based at least on the logical interrelationships of the programming objects and the processing capabilities of the control modules, and

the host controller is further configured to execute a maximum matching algorithm on the possible allocations to determine a resulting allocation of at least a portion of the programming objects to the control modules.

25. The system of claim 24, wherein the programming objects include virtual objects and non-virtual objects, and a user determines a resulting allocation of the non-virtual objects to the control modules.

26. The system of claim 25, wherein the host controller is further configured to construct a graph model representing the possible allocations of at least a first portion of the virtual objects, the graph model including a first set of vertices representing the at least first portion of virtual objects, a second set of vertices representing the processing capabilities sufficient to execute the program code associated with the at least first portion of virtual objects, and a set of edges interconnecting the first and second set of vertices, and wherein the host controller executes the maximum matching algorithm on the graph model to determine the resulting allocation of the at least first portion of virtual objects to the control modules.

27. The system of claim 26, wherein each edge of the set of edges has a weight and the maximum matching algorithm is a weighted maximum matching algorithm.

28. The system of claim 27, wherein the magnitudes of the weights of the edges are equal.

29. The system of claim 27, wherein the magnitude of the weight of each edge interconnecting one of the virtual objects to one of the processing capabilities represents a benefit associated with allocating that virtual object to that processing capability, and the resulting allocation determined by the host controller has an optimum benefit.

30. The system of claim 29, wherein the optimum benefit is the maximum benefit.

31. The system of claim 24, wherein each control module further includes a memory circuit, and the host controller is further configured to determine partitions of the program code based on the resulting allocation, and to transfer the program code contained within the partitions to the memory circuits of the control modules, wherein the program code transferred to a particular memory circuit corresponds to the programming object allocated to the respective control module.

32. The system of claim 26, wherein the host controller further constructs a second graph model representing the possible allocations of a second portion of the virtual objects, the graph model including a first set of vertices representing the second portion of virtual objects, a second set of vertices representing the processing capabilities sufficient to execute the program code associated with the second portion of virtual objects, and a set of edges interconnecting the first and second set of vertices, and wherein the host controller executes the maximum matching algorithm on the second graph model to determine a resulting allocation of the second portion of virtual objects to the control modules.

33. The system of claim 27, wherein the memory of the host controller further stores a weighting function related to one of a cost and a benefit associated with the possible allocations of the programming objects to the control modules, wherein the weighting function determines the magnitude of the weight of each edge of the set of edges.

34. The system of claim 33, further comprising a user interface in communication with the host controller, wherein the weighting function includes at least one tunable parameter and a user inputs the value of the tunable parameter via the user interface.

35. A method for allocating a plurality of programming objects of a control program configured to control a distributed control system, wherein the control system includes a host controller and a plurality of controller nodes connected to a communications link, and the control program includes program code corresponding to the plurality of programming objects, the plurality of programming objects including virtual objects, the method comprising:

providing data files accessible to the host controller, the data files containing information regarding processing capabilities associated with each of said plurality of controller nodes;

identifying a processing resource associated with each of said plurality of controller nodes;

determining possible allocations of the virtual objects to the controller nodes by applying allocation rules;

constructing a graph model representing at least a portion of the possible allocations;

assigning a weight to at least a set of edges of the graph model;

applying a weighted maximum matching algorithm to the graph model to determine allocations of at least a portion of the virtual objects to processing resources; and

preparing assignments of the allocations of the at least a portion of the virtual objects to processing resources for partitioning the program code to the plurality of controller nodes.

36. The method of claim 35, wherein the step of assigning a weight includes the steps of providing a user interface operatively connected with the control system, accepting a value received from a user through said user interface, said value corresponding to a parameter associated with the information regarding processing capabilities, and assigning a weight to an edge of the graph model corresponding to the value received from the user.