PROGRAM IN PARALLEL

The present invention relates to an automatic control system, and more particularly to an automatic control system capable of executing a control program in parallel and a method for executing a control program in parallel on the system.

An automatic control system is usually used for processing a certain range of automation tasks. When the tasks processed by the automatic control system exceed the capacity and processing power of the system, the system needs to be updated, that is, the capacity, processing power, and performance of the system are upgraded to satisfy the requirements of the system.

Conventionally, to update the automatic control system, the original one is replaced by a higher-level system with larger capability and stronger processing power, so as to meet the requirements of system updating. However, such a replacement-type updating leads to high cost and complicated operation. For example, the upgrade of a PLC system includes the following steps. First, engineers evaluate the requirements of the automatic control system to be upgraded, and select and purchase a higher-level PLC system to replace the original one. Then, the original PLC system is replaced and the new one is installed. It is also necessary to check wirings of field devices, such as sensors, actuators, panels, and human machine interfaces, of the upgraded PLC system at installation. New panels or human machine interfaces are configured on the upgraded PLC system. Furthermore, the engineers have to reprogram the upgraded PLC system that probably uses a different programming environment. Finally, the engineers adjust hardware and software of the new PLC system and put the updated PLC system into operation. Obviously, the above upgrading process leads to high cost and capacity wastes caused by overcapacity products purchased due to difficulty of getting products with suitable capacity. Moreover, the re-installation, re-configuration, re-programming, and re-adjustment of the upgraded PLC system also result in wastes in cost and manpower.

Accordingly, the present invention is directed to an automatic control system that can be easily upgraded and replaced and a method for executing control tasks on the automatic control system.

In order to achieve the above objectives, the present invention provides an automatic control system capable of executing a control program in parallel. The system includes a plurality of unit controllers, a compiler, and an interconnection network. Each of the unit controllers executes in parallel at least a part of the program to be executed by the automatic control system. The compiler is connected to one of the unit controllers, for converting the program to be executed by the automatic control system into a task executed in parallel on the unit controllers. The interconnection network is used for connecting the unit controllers, such that information on one of the unit controllers is transferred to another of the unit controllers via the interconnection network.

According to an aspect of the present invention, the unit controller has two internal interfaces and a switch. The two internal interfaces are respectively connected to two adjacent unit controllers of the unit controller and both connected to the switch. The switch is connected to a data bus and an address bus of the unit controller.

According to an aspect of the present invention, the internal interfaces are Ethernet interfaces.

According to an aspect of the present invention, the unit controller transfers information to another of the unit controllers in a message transfer manner. According to an aspect of the present invention, the unit controller further includes a CPU for executing a control program in parallel, a system memory for storing system programs and data, a user memory for storing user programs and data, an input circuit, an output circuit, and an expansion connecting component for expanding input/output.

Accordingly, the present invention further provides a method for executing a control program in parallel in a system according to claim 1. The method includes the following steps: (1) The program to be executed by the automatic control system is sliced. (2) A control flow graph (CFG) is built for each slice based on semantic analysis.

(3) A control dependence graph (CDG), a data dependence graph (DDG), and a hardware dependence graph (HDG) are respectively built based on the CFG

(4) A parallelism of the slices is extracted from the CDQ the DDQ and the HDG

According to an aspect of the present invention, in the Step (1), the program to be executed by the automatic control system is sliced according to networks with label (NWL).

According to an aspect of the present invention, in the Step (2), the CFG is a directed graph CFG = (y, E) with a unique starting point and a unique end point, where V is a set of nodes of the NWL, £ is a set of edges formed by any two nodes x, y in the set of nodes V and denoted by E = {(x, yjx, y e v] .

According to an aspect of the present invention, in the Step (3), the CDG CDG = (CV,CE)

is a directed labeled graph CDG = (CV,CE), where CV = V , that is, CV is a set of nodes of the NWL, CE is a set of edges formed by any two nodes x,y in the set of nodes CV and denoted by {x,y)≡ CE . If a dependency between x and y exists, that is, yA x exists and the node x reaches the node y via a node a, a label of the edges formed by the nodes x and y is labeled as x-a. In other words, the existence of the edge from x to y is denoted by yA _p x

and an attribute (or referred to as a weight or value) of the edge from x to y is denoted by x-a.

According to an aspect of the present invention, in the Step (3), the DDG is a directed labeled graph DDG = [DV, DE), where DV = V, that is, DV is a set of nodes of the NWL, DE is a set of edges formed by any two nodes x,y in the set of nodes DV and denoted by (x, y) G DE. The edges (x,y) are labeled as xδ _d y by a label.

According to an aspect of the present invention, in the Step (3), the HDG is a directed labeled graph HDG = [HV, HE), where HV = V , that is, HV is a set of nodes of the NWL, HE is a set of edges formed by any two nodes x,y in the set of nodes HV and denoted by (x,y)ε HE . The edges (x,y) are labeled as xδ _h y by a label.

With the automatic control system for parallel execution according to the present invention, the original old system is upgraded or updated in an expansion manner. Compared with the conventional replacement-type upgrading manner, on one hand, the upgrade can be performed more quickly and easily, and on the other hand, the expense is reduced and the cost of upgrading the system is lowered since only new modules or devices need to be added to the original system.

The present invention will become more fully understood from the detailed description given herein below for illustration only, and thus are not limitative of the present invention, and wherein: FIG. 1 is a schematic structural view of an automatic control system according to the present invention; FIG. 2 is a schematic structural view of a unit controller in the automatic control system according to the present invention;

FIG. 3 is a flow chart of a method for executing a control program in parallel in the automatic control system according to the present invention; FIG. 4 shows a segment of control program described in an engineering language, and a dependence model is built according to the method for executing a control program in parallel of the present invention based on the segment of codes;

FIG. 5 is a control flow graph (CFG) built for the control program shown in FIG. 4; FIG. 6 is a post-dominator tree (PDT) built for the control program shown in FIG. 4; FIG. 7 is a schematic view illustrating a comparison of the automatic control system before upgrade (FIG. 7a) and after upgrade (FIG. 7b) with the present invention; and FIG. 8 is a schematic architectural view of an application of the present invention in an industrial control system.

The present invention is illustrated below in detail with the drawings.

The conventional upgrading method of an automatic control system is replacing the old automatic control system completely with a new one by a replacement-type method, while the present invention adopts a totally different upgrading method from the conventional one, that is, adopts an expansion-type upgrading structure and method. The present invention adopts the expansion-type upgrading structure based on the idea of executing a control program in parallel, i.e., executing multiple program instructions and data concurrently on multiple processors in order to obtain an operation result more quickly.

FIG. 1 is a schematic structural view of an automatic control system according to the present invention. The automatic control system for executing parallel tasks in FIG. 1 includes N unit controllers from a unit controller 1 to a unit controller N, a compiler, and an interconnection network. The N unit controllers are used for executing in parallel a program to be executed by the automatic control system, that is, each of the unit controllers executes a part of the program to be executed by the automatic control system. The compiler is connected to one of the N unit controllers, usually the unit controller 1. The compiler converts a serial program described in an engineering language into codes capable of being executed on the unit controllers, and converts the serial control program into parallel control programs, so as to ensure that the unit controller can execute parallel tasks. The N unit controllers are connected by the interconnection network, such that information on one unit controller can be transferred to another unit controller via the interconnection network.

Each of the unit controllers has two internal interfaces and a switch. The two internal interfaces on the unit controller are Ethernet interfaces, and respectively connected to two adjacent unit controllers before and after the unit controller to form a daisy chain connection. The so-called daisy chain here refers to a concatenation of the unit controllers by the interconnection network such that information is transferred from one unit controller to the next unit controller. The two internal interfaces on each of the unit controllers are both connected to the switch of the unit controller. The switch is located inside the unit controller, and is connected to a data bus and an address bus of the unit controller. After the N unit controllers are connected by the interconnection network into the daisy chain, information is transferred from one unit controller to another unit controller in a message transfer manner.

FIG. 2 is a schematic structural view of the unit controller in the automatic control system according to the present invention. Each of the unit controllers further includes a CPU for executing a control program in parallel, a system memory for storing system programs and data, a user memory for storing user programs and data, an input circuit, an output circuit, an expansion connecting component for expanding input/output, and a power supply. The CPU is the minimum unit on the unit controller for executing the control program in parallel, and executes control tasks assigned by the compiler. The system memory stores programs and data that are usually not changed, for example, an operating system of the unit controller. The system memory may be set as read-only. The user memory stores user programs and data that may be read or modified. When a new segment of user program and data is loaded into the user memory, the old user program and data stored in the user memory is overwritten or deleted. The input circuit is used for providing inputs to the unit controller, and the output circuit is used for providing outputs to the unit controller. The expansion connecting component is used for connecting expansion modules external to the unit controller, for example, expanded input/output circuits. The CPU, the system memory, the user memory, the input circuit, the output circuit, and the expansion connecting component are respectively connected to the data bus and respectively connected to the address bus.

FIG. 3 is a flow chart of a method for executing a control program in parallel in the automatic control system of the present invention. The method includes the following steps:

In Step 301, the program to be executed by the automatic control system is sliced.

In this step, first, the program to be executed by the automatic control system is sliced into some individual parts. Normally, three granularity levels may be used to slice the program: an instruction level, a function level, and a task level. Since in the Programming Languages of Industrial Control Standard IEC 61131-3 formulated by the International Electrotechnical Commission (IEC), control programs written in engineering languages (such as a ladder diagram (LD) and a function block diagram (FBD)) consist of a number of networks with label (NWL), the control programs are naturally sliced by the NWL. Compared with slicing using the instruction level, slicing programs by the NWL can reduce the slicing complexity. Compared with slicing using the task level, slicing programs by the NWL is easier to achieve load balance when one or more tasks exist.

In Step 302, a control flow graph (CFG) is built for each slice based on semantic analysis. The CFG is built based on the NWL. The CFG is a directed graph CFG = {V,E) with a unique starting point START and a unique end point STOP, where V is a set of nodes of the NWL, £ is a set of edges formed by any two nodes x,y in the set of nodes V and denoted by E = {(x, yjx, y e V) .

In Step 303, a control dependence graph (CDG), a data dependence graph (DDG), and a hardware dependence graph (HDG) are respectively built based on the CFG

In order to construct the CDG from the CFQ a post-dominator tree (PDT) is introduced, which may determine whether a dependency in control flow exists between two nodes. The PDT is a tree structure rooted at the end point. If x is an immediate post-dominator of y, y is a direct descendant of x. y is regarded as the post-dominator of x if and only if every path from the node x to the end point STOP (not including x) contains the node y. Then, the relationship between x and y may be denoted by yΔ _p x . The immediate post-dominator is the least

element in the chain of post-dominators of the node x.

The CDG of the CFG CFG = (V, E) is a directed labeled graph CDG = (CV, CE), where CV = V , that is, CV is a set of nodes of the NWL, CE is a set of edges formed by any two nodes x,y in the set of nodes CV and denoted by (ϊj)e ffi . If a dependency

between x and y exists, that is, yA _p x exists and the node x reaches the node y via a node a, a

label of the edges formed by the nodes x and y is labeled as x-a. In other words, the existence of the edge from x to y is denoted by yA _p x and an attribute (or referred to as a weight or

value) of the edge from x to y is denoted by x-a.

Furthermore, if the node x is not an immediate post-dominator of the node y, instead a non-null path P = {x,a,...,y) exists from the node x to the node y and yA _p z holds for any node z e P (excluding the nodes x and y) on the non-null path (i.e., the node z is the post-dominator of the node y), a dependency between y and x exists and is denoted by xδ _c y .

The DDG of the CFG CFG = (V,E) is a directed labeled graph DDG = [DV, DE), where DV = V , that is, DV is a set of nodes of the NWL, DE is a set of edges formed by any two nodes x,y in the set of nodes DV and denoted by [x,y)≡ DE . The edges DE are

labeled as xδ _d y by a label. If a data conflict exists between x,y (i.e., the same variable is

accessed), a data dependency exists between x, y , which is denoted by xδ _d y .

The HDG of the CFG CFG = [V, E) is a directed labeled graph HDG = [HV, HE), where HV = V , that is, HV is a set of nodes of the NWL, HE is a set of edges formed by any two nodes x,y in the set of nodes HV and denoted by [x,y)≡ HE . The edges HE are

labeled as xδ _h y by a label. If a hardware conflict exists between x,y (i.e., the hardware resource on the same unit controller is accessed), a hardware dependency exists between x,y , which is denoted by xδ _h y .

In Step 304, a parallelism of the slices is extracted from the CDQ the DDQ and the HDG

Nodes not mutually dependent are found according to the CDQ the DDQ and the HDQ and may be executed on different unit controllers, while nodes dependent on each other must be executed on the same unit controller in a sequence of the nodes. Since multiple unit controllers are used for concurrent execution, the time for executing the automatic control program is shortened. FIG. 4 shows a segment of control program described in an engineering language, and a dependence model is built according to the method for executing a control program in parallel of the present invention based on the segment of codes. Generally speaking, the nodes in the above CFG and various dependence graphs may be program units, for example, a node is viewed as a function, and the edges in the CFG and various dependence graphs indicate dependencies. A total of 12 NWL, i.e., 12 nodes exist in this segment of control program. A CFG (as shown in FIG. 5), a PDT (as shown in FIG. 6), a CDG (as shown in Table 1), a DDG (as shown in Table 2), and an HDG (as shown in Table 3) are built for the 12 nodes in turn.

Table 1 CDG of 12 nodes shown in FIG. 4

Table 2 DDG of 12 nodes shown in FIG. 4

Table 3 HDG of 12 nodes shown in FIG. 4

FIG. 7 is a schematic view illustrating a comparison of the automatic control system before upgrade (FIG. 7a) and after upgrade (FIG. 7b) with the present invention. In FIG. 7a, before the system is upgraded, the automatic control system only has one unit controller on which a group of control program Gl runs. If the original system before upgrade cannot meet the requirements of newly added applications for processing power and memory space, the original system is upgraded using the present invention, as shown in FIG. 7b. After the upgrade, 2 unit controllers are added to the automatic control system. The 3 unit controllers are connected to one another by the interconnection network. The control program running in the automatic control system is partitioned into 3 groups (respectively Gl, G2, and G3) based on the analysis of the CDQ DDQ and HDG using the method of the present invention. The three groups of control program are respectively run on the three unit controllers.

FIG. 8 is a schematic architectural view of an application of the present invention in an industrial control system. In FIG. 8, the automatic control system of the present invention receives a signal of a sensor or transmitter, runs a control program on each unit controller, and sends a control signal to an executive mechanism. A human machine interface HMI/panel and a compiler are respectively connected to the automatic control system via the interconnection network.

As can be seen from the above embodiments, in the automatic control system and method for parallel execution of the present invention, the original old system is upgraded or updated in an expansion manner. Therefore, the system may be upgraded quickly and conveniently, and the cost of upgrading the system is reduced.

The above merely describes preferred embodiments of the present invention, but not intends to limit the present invention. Any modifications, equivalent substitutions, and variations made within the spirit and scope of the present invention fall within the scope of the present invention.