Error detection/correction and fault detection/recovery – Data processing system error or fault handling – Reliability and availability
Reexamination Certificate
1997-12-31
2001-05-15
Wiley, David (Department: 2155)
Error detection/correction and fault detection/recovery
Data processing system error or fault handling
Reliability and availability
C700S001000
Reexamination Certificate
active
06233703
ABSTRACT:
TECHNICAL FIELD
The present invention relates generally to programmable controllers and other computing devices, and more generally to the apparatus and associated method for facilitating the programming of such a device by automatically generating an order for evaluating functions and function blocks in a function block diagram and for automatically detecting errors associated with the evaluation order.
BACKGROUND
Function block diagrams for use with programmable controllers are defined in IEC standard 1131-3, which is hereby incorporated by reference. Other programming languages covered by that standard include Ladder Diagrams (based on diagrammatic conventions typically used to represent relay-based systems) and Structured Text (based on text conventions typically used to represent sequential operations in a digital computer).
A function block diagram is a normalized two dimension representation of an executable program such as may be implemented in a digital process control system or other digital computer, and typically consists of one or more disconnected networks, each comprising a number of connected inputs, outputs, function blocks and functions.
A function block exists as a particular instance associated with one or more specified variables which persist from one evaluation of that instance to the next, while a function has no such persistent variables. In turn, a higher level function block may include not only inputs and outputs, but also one or more functions and lower level function blocks, and a higher level function may contain one or more lower level functions. Accordingly, a function block diagram typically represents an ongoing process that involves multiple executions of related processes and outputs that vary in response to not only changes in external inputs, but also the passage of time.
One specific application of an IEC 1131-3 function block diagram or other 1131-3 programming language is to provide an application programmer with a convenient means to define a program for operating the three redundant programmable controller modules of a critical control and safety system such as the Tricon™ Version 9 single chassis safety control system in which the same application program is developed and downloaded to three isolated parallel digital processors. Since digital control processors operate in a sequential fashion and all three processors must produce the same output at any given time, a sequential evaluation order must be assigned to the individual blocks and functions such that each iteration of the program produces a predictable set of output values. In particular, a valid IEC 1131-3 Function Block Diagram cannot include any closed loops (feedback) within a single evaluation cycle, although any persistent variable evaluated during a particular evaluation cycle can be used as an input variable during a subsequent evaluation cycle.
A topological sort is a known mathematical process for mapping a partially ordered set (which may be represented by a multi-dimensional graph of nodes connected by directional paths) onto a completely ordered (i.e., one-dimensional) set of relationships. These and other related techniques are discussed at length in
Discrete Mathematics in Computer Science
by Donald F. Stanat and David F. McAllister, which is hereby incorporated by reference.
SUMMARY
In accordance with an overall objective of the present invention, the programming of programmable controllers and other sequential computing devices is facilitated by automatically generating an order for evaluating function blocks in a function block diagram
A more specific objective is to automatically detect any errors in a function block diagram which would adversely affect the generation of a unique evaluation order.
Another more specific objective is to provide a graphical interface to facilitate the identification and correction of an error in the form of a closed loop.
In a presently preferred embodiment, a graphical user interface is used to define a number of nodes including program inputs, program outputs, function blocks, and logic functions, and to connect those nodes to form a function block diagram network. The network is then checked for the presence of various errors, such as illegal cycles, disconnected subnetworks, and/or wired-OR connections. Preferably, the nodes affected by the noted errors are graphically displayed to the user, who then may use the graphical interface to edit the network until all the noted errors have been corrected. Once any noted errors have been corrected and a fixed sequence has been assigned to all the external outputs (or the external inputs), a recursive procedure analogous to a topological sort may be used to automatically generate a unique evaluation order based only on the assigned fixed sequence and on the defined connections. Assuming that the topological sort starts at the network outputs, those outputs are automatically assigned a definite sequence, which may be based upon the physical location on the diagram of their associated function blocks and the order in which they are connected to the terminals in those function blocks. The blocks upstream from each output are then visited recursively from the input of one block to the output of a preceding block until a “minimal” node is reached which either is not preceded by other blocks or is preceded only by blocks which have already been visited and assigned sequence numbers, whereupon the current block is assigned the next available sequence number and the same procedure is used to process any nodes that are upstream from the next downstream output. The process is repeated until all network outputs have been processed or an error condition has been detected.
Those skilled in computational science will recognize that the constraint that there are no closed cycles guarantees that the associated digraph and all sub-digraphs of the original digraph will always have at least one “minimal” node and at least one “maximal” node, and will also recognize that the ordering process could have equally well commenced at the first input of a fixed sequence of inputs. Similarly, the constraint that all the nodes (blocks) in a given network are connected guarantees that the ordering process will not terminate until all nodes have been assigned an evaluation sequence number.
Other constraints, such as the prohibition on wired-OR connections and the requirement for a fixed sequencing of external inputs (or outputs), are preferably included not to guarantee that the network can be evaluated, but rather to ensure that the resultant evaluation order is predictable a priori. Otherwise, exactly the same diagram could produce different instruction sequences producing different intermediate results, thereby introducing an element of chance and sacrificing the reliability and serviceability possible only when every step of every process is both redundant and predictable.
In accordance with another aspect of the invention, a process somewhat analogous to a topological sort is used to recursively identify both minimal and maximal nodes until only a core having no minimal or maximal elements is left. By following successive directed paths from one node of that core until a previously visited node is reached, an illegal closed loop may be identified which includes not only that previously visited node, but also all the other nodes visited between the two successive visits to that node.
Any disconnected network is preferably also identified before the evaluation order is assigned.
REFERENCES:
patent: 5168441 (1992-12-01), Onarheim et al.
patent: 5243511 (1993-09-01), Zifferer et al.
patent: 5297257 (1994-03-01), Struger et al.
patent: 5349518 (1994-09-01), Zifferer
patent: 5371895 (1994-12-01), Bristol
patent: 5444843 (1995-08-01), Nilsson et al.
patent: 5485620 (1996-01-01), Sadre et al.
patent: 5526268 (1996-06-01), Tkacs et al.
patent: 5576946 (1996-11-01), Bender et al.
patent: 5841654 (1998-11-01), Verissimo et al.
patent: 5867382 (1999-02-01), McLaughlin
patent: 5909368 (1999-06-01), Nixon et al.
pa
Fulbright & Jaworski L.L.P.
Triconex Corporation
Wiley David
LandOfFree
Automatic generation of evaluation order for a function... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Automatic generation of evaluation order for a function..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Automatic generation of evaluation order for a function... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2459415