 |
Description  |
|
|
RELATED APPLICATION DATA
This application is related to U.S. Pat. No. 4,868,785 entitled BLOCK
DIAGRAM EDITOR SYSTEM AND METHOD FOR CONTROLLING ELECTRONIC INSTRUMENTS,
issued Sep. 19, 1989 to Jordan and Stubbs, et al.; and to U.S. Pat. No.
4,812,996 entitled SIGNAL VIEWING INSTRUMENTATION CONTROL SYSTEM, issued
Mar. 14, 1989 to Stubbs.
BACKGROUND OF THE INVENTION
Field of the Invention
The present invention relates to computer control of electronic test and
measurement systems and, more particularly, includes methods and apparatus
for generating properly interleaved software to implement a system of
multi-state resources topologically interconnected to perform a data flow
process, and methods of executing the software.
Data Flow Systems
Electronic instruments and other devices may conveniently be modeled and
controlled with the use of computers. For example, interactive control of
a measurement instrument may be accomplished through a graphic user
interface designed to eliminate direct sequential manipulation of, and
obviate detailed familiarity with, the front panel of the instrument.
Test and measurement systems typically comprise a stimulus device, a device
under test (DUT), and a measurement instrument for measuring the response
of the DUT to the stimulus. A system of this type may conveniently be
modeled and controlled using a block diagram editor and electronic
instrument control system designed for this purpose, as described in the
above-referenced U.S. Pat. Nos. 4,812,996 and 4,868,785.
Simple topologies are conveniently modeled, in a steady state, using
conventional sequential control-flow programming techniques. Thus, the
automated control of individual instruments, or test setups including
several instruments or devices, usually begins with all physical
connections in place, power applied, devices warmed up (i.e., at steady
state), and the system generally ready to begin capturing data.
The concurrency of operation of electronic system components also is
usefully modeled, and their simulation and control effectively programmed,
using data flow systems. Data flow systems are characterized in pertinent
part by (1) data-activated, asynchronous executions of operations; (2)
operands consumed by operators; and (3) the absence of internal state or
explicit storage. See Hughes, J. "A High-Level Representation for
Implementing Control-Flow Structures in Dataflow Programs," Center for
Reliable Computing, Computer Systems Laboratory, Stanford University (CSL
Technical Report No. 82-4, May, 1982).
Data flow diagrams can be understood as programs. In these diagrams, blocks
represent functions performed on data and connections represent the
transmission of data between the functions. When the resources in a data
flow diagram represent only computer-based transformations or
transmissions of data, a simple rule determines when each can run:
upstream resources function before downstream resources. For example, in
performing simulations, it may be assumed that all functions are in a
steady state, ready to operate in response to inputs.
Multi-state Resources
The simple rule is inadequate when resources represent external devices
that have multiple states such as test instruments, devices-under-test, or
physical signal paths. For example, a power supply can be off or on. A
signal path can be made or broken.
When resources can be in different states, their states must change to
perform the computation expressed in the program. Continuing the
instrumentation example, each physical device should be in a quiescent, or
safe state when not in use. When the computation or measurement is
completed, the device should be returned to the safe state.
In a data flow diagram, for instance, that shows "data" (a physical signal)
flowing from a power supply to some other physical (e.g., measurement)
device, the power supply must be turned on and remain on while the next
(i.e., "downstream") device performs its function. These kinds of
relationships among state changes in resources are termed "dependencies."
The power supply can be turned off only when all of the downstream
functions that depend on the power supply signal have completed their
functions. Likewise, the signal path between the power supply and the next
device must be made before the signal is applied and broken only after it
has been removed. Thus, execution of a power supply block (i.e., function)
could have two parts (or state-changing "tasks"): turning it on and
turning it off. A physical connection function also has two related tasks:
making the path and breaking it. Finally, the measurement device, such as
a multimeter, may require Set-up, such as selecting an appropriate range
of measurement, before it properly can "function," i.e., measure the
signal. This state change, from a quiescent or standby mode to an active
"measure" mode, is particularly important to protect the measurement
device from out-of-range inputs.
Programmers implementing data flow diagrams using conventional, text-based
programming languages (e.g., BASIC, C, Pascal, etc.) not only must
identify the relevant tasks and dependencies, but also must order the
tasks in a strictly linear way. Most data flow programming systems have
been implemented to support parallel computation of numeric algorithms
(e.g., digital signal processing) (Dennis, J. B., Broy, M., "Control Flow
and Data Flow: Concepts of Distributed Programming," Proceedings of NATO
Advanced Study Institute International Summer School, Marktoberdorf,
Germany, 1984, at 345-98.) and do not address resources having multiple
states. In these systems, the simple ordering rule is sufficient. Other
Products
"LabVIEW" is a graphic, interactive test and measurement instrument control
product available from National Instruments. In LabVIEW, "virtual
instruments" are created and stored to repeatedly look up and program
machine-specific mnemonics for instrument control.
Using the "frame" concept in LabVIEW, programmers create multiple diagrams
that explicitly implement each resource's state changes and interleave
these diagrams within the frame structure. The frame structure provides
sequential execution of the individual data flow diagrams thus achieving
the proper state change sequence. This technique prevents programmers from
using a single data flow block to represent a multiple-state resource in
cases where the resource's state changes must be interleaved with those of
other resources.
Signal processing simulation software entitled "Signal Processing
WorkSystem" (SPW) provides data paths for control tokens and logic
components (e.g., counter, AND, OR, NOT, etc.) to control their flow. (See
Signal Processing WorkSystem.TM. Technical Backgrounder, Tektronix CAE
Systems Division, 1987). All blocks in SPW, including instrument blocks,
can be built with control token inputs and outputs. Programmers must
explicitly connect control logic to processing blocks to achieve proper
ordering of block functions, as well as make connections representing data
flow. Each time a block executes, it behaves according to the pattern of
externally-applied control information.
Present Need
The need remains for a method and apparatus for creating programs in which
single blocks can represent multiple state resources that, upon execution,
automatically will perform their state changes in a properly interleaved
order, obviating the need to provide control logic or to split and
interleave tasks manually.
SUMMARY OF THE INVENTION
Overview
An object of the present invention is to implicitly order tasks in a
computer controlled test and measurement system so that users need not
explicitly do so. Another object of the invention is to automatically
generate an executable sequence of computer instructions to control a
system of resources topologically interconnected and operable to implement
a dataflow process. Yet another object of the present invention is to
protect the input circuitry of sensitive measurement instruments used in
computer-controlled test and measurement systems. An additional object of
the invention is to automatically control a test system so as to ensure
that collected data is valid.
The present invention provides a method of automatically generating a
sequence of computer instructions to control a system of resources
topologically interconnected and operable to implement a data flow
process. The resources include blocks and connections. The system of
resources may conveniently be represented as a block diagram and,
preferably, created and manipulated as disclosed in the above-referenced
co-pending patents.
The method includes providing a computer system including prestored code
blocks or drivers for implementing the resources. A user inputs into the
computer system data defining a desired data flow process, the data
including an identification of each resource used in the process and the
topological interconnection of the resources used in the process.
For each code block corresponding to a resource used in the process,
instructions for implementing each of a set of tasks are identified, as
well as a portion of the code block associated with each task. For an
electronic test and measurement system, as well as many other systems, the
set of tasks associated with a given resource can include no task, or one
or more of the tasks: Set-up, Function and Terminate.
The tasks thus identified are ordered or positioned in accordance with the
topological interconnection of the resources and in accordance with a
predetermined set of task-positioning rules to form a network of
dependencies among the tasks. The resulting network is an acyclic graph.
It may be represented pictorially, as shown e.g. in FIG. 12. The network
is used to generate code for controlling the data flow process as more
fully explained below.
General Task-Positioning Rules
For many systems, the tasks can be suitably ordered by application of a
predetermined set of generaI task-positioning rules. The task positioning
rules in their simplest form include the following internal task
positioning rules:
Set-up precedes Function;
Function precedes Terminate; and
Set-up precedes Terminate (if no Function task).
These rules determine the order of execution of a single resource's tasks.
An order of execution of tasks relative to the tasks of other resources is
determined by external task-positioning rules. A set of such rules is as
follows:
downstream block's Set-up precedes upstream blocks' Function;
downstream block's Function follows upstream blocks' Function;
downstream block's Terminate follows upstream blocks' Terminate;
connection's Set-up precedes upstream block's Function;
connection's Function follows upstream block's Function; and
connection's Terminate follows upstream block's Terminate.
Refined Task-Positioning Rules
More complex positioning rules may be required to properly order tasks in
networks having certain combinations of resources and topology. For
example, Appendix A includes a refined set of rules which distinguish
among different types of connections (hardware and software) and
distinguish among types of inputs (software inputs, hardware inputs and
parameter inputs). The refined rule list shown in Appendix A subsumes the
general rules set forth above.
Input Ordering Restrictions
The invention further provides for properly interleaving tasks for systems
in which one or more resources has multiple inputs and the sequence of
applying and/or removing input signals is restricted. For example, a
device (or resource) may have a power supply input and a signal input.
Power must be applied to the power supply input before a signal is applied
to the signal input.
In systems that require them, input ordering restrictions can be included
in the prestored code block for implementing the resource, or may be
specified as part of data defining the requirements of a particular block.
General rules are provided for implementing such restrictions. Application
of these rules to the input ordering restrictions defines additional
dependencies among tasks, thereby affecting the resulting sorted list of
tasks. Ordering rules are provided for enforcing separate restrictions on
data application and signal application and/or removal.
Data Structures
In a preferred embodiment, hierarchic data structures are provided for
representing in the computer a block diagram representative of a data flow
process. At its highest level, the data structure includes an object
called BlockDiagram having variables including a list of the block
diagram's blocks, a list of the block diagram's connections, and an empty
structure called "sortList" to be filled in with an ordered list of the
tasks of the block diagram.
Each block data structure in turn has associated data structures including
a list of inputs and outputs and a list of the block's associated tasks.
Proceeding down the hierarchy, each task has data structures including a
component for identifying the associated block, an object identifying the
type of task, a list of predecessor tasks, a reference count, and a list
of successor tasks. The last three structures are empty prior to carrying
out the task ordering procedure.
Application of the ordering rules defines a number of dependencies among
the tasks. Each such dependency, for example, that a first task precedes a
second task, results in the first task being added to the second task's
list of predecessors and, conversely, the second task being added to the
first task's list of successors. The reference count is the number of
predecessors. Thus, it is incremented for each predecessor added to the
list. The foregoing data structures facilitate sorting the tasks to
produce a partially ordered list for execution or code transmission as
further explained in the next section.
Methods of Execution
Code blocks corresponding to the identified tasks can be executed to carry
out the process on a physical system modeled by the data flow. The
preferred embodiment includes screen "animation" such that resources in a
data flow diagram are highlighted when their underlying software is
executed.
The list of tasks and their dependencies can be used to link the
instructions or drivers together in a proper sequence for executing the
tasks. The identified tasks are executed using either of two techniques, a
linearization technique and/or multiprocessing technique.
In the linearization execution technique, the network of dependencies is
partially ordered by a technique called "topological sorting." (Knuth,
Donald E., Fundamental Algorithms, Addison-Wesley, 1973, Page 258.) The
sorting procedure produces a sequence of lists of tasks called "interior
lists." Each interior list is considered in order. (See text below
describing FIG. 14.) Within each interior list, the tasks are executed
sequentially in any order. Their execution changes the state of the
resources, often producing data for their successor tasks. The resulting
order of execution is one of many that assure correct execution of the
data flow program.
The corresponding sequence of code may be executed directly to control the
data flow process in an integrated system, i.e., one including both a
computer programmed with block diagram editor software and data
flow-to-sequential conversion software (as disclosed herein) and apparatus
for controlling the physical data flow process. Alternatively, source code
in any convenient language may be generated by known techniques and ported
to another computer. The generated code may be written to a portable
storage medium, such as magnetic tape or floppy disk, for subsequent
execution on a target system. For example, a target system may be a
computer-controlled manufacturing test facility located at a manufacturing
site where product (DUT) testing is required.
The target system may be a relatively simple and inexpensive one, as it
need only have the capabilities of interfacing with the physical resources
and executing the code. It need have only a single process operating
system, for example, MS DOS (TM), to execute the linear code. The target
system need not have the interactive graphics capabilities of the block
diagram editor, nor the other elements included in a system adapted for
implementing the present invention.
The invention includes use of an alternative execution technique on systems
having multiprocessing capability, in which linearization is unnecessary.
The multiprocessing execution may be carried out directly in an integrated
multiprocessor system, as above. Alternatively, appropriate code may be
generated for subsequent execution on a target machine having a
multiprocessing operating system.
In the multiprocessing technique, each task is made into a standard
operating system process. Upon execution, these processes are linked using
some operating system message-passing system (e.g., semaphores) according
to the dependencies. Processes that do not depend on others (i.e. those
having no predecessors), the root processes, (i.e., no predecessors) are
executed. As they complete, they signal their successors. When a waiting
process has been signaled by all the upstream processes on which it
depends, the waiting process then executes. The program is completed when
no process remains to be executed.
The foregoing and other objects, features and advantages of the invention
will become more readily apparent from the following detailed description
of a preferred embodiment which proceeds with reference to the drawings.
BRIEF DESCRIPTION OF THE DRAWINGS
FIG. 1 is a diagram of an example of a computer-controlled electronic test
system in which the invention is embodied.
FIG. 2A is a first illustrative data flow diagram created using a block
diagram editor for computer-controlled implementation of a data flow
process in the test system of FIG. 1.
FIG. 2B is a diagram illustrating the conceptual relationship between a
selected portion of the physical test system of FIG. 1 and its
corresponding data flow diagram representation.
FIG. 3 is a second illustrative data flow diagram and corresponding state
diagrams and resource table.
FIG. 4 is a diagram of the dependencies resulting from application of the
general task-positioning rules to the tasks associated with the data flow
process of FIG. 3.
FIG. 5 is a directed, acyclic graph (DAG) of the tasks of the data flow
diagram of FIG. 3 ordered in accordance with the dependencies shown in
FIG. 4.
FIG. 6 is a third illustrative data flow diagram and corresponding resource
table.
FIG. 7 is an unsorted diagram of the tasks associated with the data flow of
FIG. 6 and the dependencies among those tasks.
FIG. 8 is a fourth illustrative data flow diagram depicting a system which
is implemented solely in software to display the product of two numbers.
FIG. 9 is a diagram of a portion of the data structure associated with the
block diagram of FIG. 8.
FIG. 10 is a diagram of a portion of the data structure of the multiply
block of FIG. 8.
FIG. 11 is a diagram of the data structure of the Function task of the
multiply block of FIG. 8.
FIG. 12 is a network of tasks of the data flow of FIG. 8 as related by the
applicable ordering rules shown in Appendix A.
FIG. 13 is a diagram of the FIG. 11 multiply block's Function task data
structure after the ordering rules shown in Appendix A have been applied.
FIG. 14 is a diagram of a portion of the data structure of the block
diagram of FIG. 8 after topologic sorting of the blocks' tasks and the
connections' tasks.
FIG. 15 is a fifth illustrative data flow diagram including blocks
representing hardware instrument resources and connections representing
physical data paths.
FIG. 16 is the network of tasks of the data flow diagram of FIG. 15 as
related by the applicable ordering rules.
FIG. 17 is a diagram of the sortList portion of the data structure of the
data flow diagram of FIG. 15, showing the diagram's sorted task list.
FIG. 18 is a diagram of another portion of the data structure for the
diagram of FIG. 15, showing the DUT block's data structure including
location of input ordering information.
FIG. 19 is a sorted network showing dependencies among the tasks of the
data flow diagram of FIG. 15 with the DUT's turn-on and turn-off ordering
enforced.
FIG. 20 is a diagram of the FIG. 15 data flow diagram's sorted task list as
derived from the network of tasks of FIG. 19.
FIG. 21 is a C++ listing, with comments in italics, of code for executing
the data flow diagram of FIG. 15 based on the sorted task list of FIG. 20.
FIG. 22 is a diagram generally illustrating the operation of a
computer-controlled test system in accordance with the present invention.
APPENDIX A is a list of task-positioning rules incorporated in a preferred
embodiment of the invention including Smalltalk-80 (TM) code segments
implementing each rule. References such as "R1", "R6" etc. in the FIGURES
refer to the corresponding rules set forth in Appendix A. The number
following the R refers to the numbering used in Appendix A.
Appendix B is a list of selected segments of Smalltalk-80 (TM) code
incorporated in a preferred embodiment of the invention including comments
describing the operation of each code segment. The appendices form a part
of this disclosure.
DETAILED DESCRIPTION
State-changing and Data Producing Tasks
FIG. 1 depicts a diagram of a system for testing a device-under-test 71
under computer control. The diagram shows the layout and interconnection
of a computer and programmable test instrumentation system for stimulating
the device-under-test (DUT) 71, such as an AM modulator, and detecting and
analyzing the response.
The system depicted in FIG. 1 includes a computer system 50; protocol
converter 64 for connecting the computer system to an interface bus 66
(IEEE-488); three signal generating instruments 68, 70 and 72, all
connected to the bus 66; the DUT 71 connected to receive stimuli from the
signal generating instruments; and a measurement instrument 74, connected
via connection 73 to receive a signal of interest from the DUT and
connected to the bus 66 to communicate with the computer system 50. The
computer system 50 of FIG. 1 includes block diagram editor software for
creating and editing block diagrams representing data flow, or simply
"data flow diagrams." This hardware and software are described in detail
in U.S. Pat. No. 4,868,875.
FIG. 2A illustrates a display screen image generated by the computer system
50 including a data flow diagram corresponding to the test system shown in
FIG. 1. The diagram is created using the block diagram editor system
described in Jordan and Stubbs, et al, Ser. No. 07/007,234, and provides
the user an interactive means for controlling a hardware system such as
that of FIG. 1.
Referring to FIG. 2A, each instrument, or "resource", is represented by a
block. Blocks 75, 76 and 77 correspond to the signal generators 68, 70 and
72, respectively in FIG. 1. Block 78 corresponds to the DUT 71 in FIG. 1,
and block 79 represents the measurement instrument 74 in FIG. 1.
Additionally, each physical connection between resources is itself a
resource. Thus, connections 80, 81, 82 and 78A are resources. In summary,
the data flow diagram shown in FIG. 2A shows a set of resources
topologically interconnected to model the test system of FIG. 1. The
resources (signal generator blocks 75, 76 and 77) generate data to
stimulate the DUT block 78; transmit data (connections 80, 81, 82 and
78A); respond to data (DUT block 78); and sense data (measurement
instrument block 79).
FIG. 2B shows the relationship between three of the physical elements of
the test system of FIG. 1, and its virtual implementation as a network of
blocks and connections in a system according to the present invention. The
physical DUT 71 is represented by block 78. The physical connection 73
from the output of the DUT to the measurement instrument 74, which may
included a switch matrix indicated by dashed box 73A, is represented by
connection 78A in the virtual implementation. Finally, the physical
measurement instrument 74 is represented by block 79. The computer system
provides the user interactive control of the physical devices, over the
GPIB bus 66, through the medium of the blocks and connections.
"Tasks" are operations which change the state of a resource or cause it to
generate data. Though any number of task types may be identified, three
types or classes of tasks are sufficient for common instrument control
situations. These three tasks are denominated "Set-up," "Function," and
"Terminate. The classes are defined generally as follows:
Set-up: A Set-up task uses parameters to prepare a resource to function,
placing it in a state ready to produce an output, or ready for the arrival
of data (including physical signals).
In a system with test instruments, for example, blocks representing
measurement devices usually have Set-up tasks.
Function: A Function task produces output data, transforms input data
making output data available, or consumes input data to produce some
external effect, for example, producing a display, writing to a file, or
printing a report. Stated differently, the function task drives a resource
from a quiescent, standby state to an active, functioning state.
A resource might not have a function task where it has no way of
controlling its output. This is the case where an input signal is applied
and an output signal is immediately present, as across a resistor.
Terminate: A Terminate task makes an output physical signal unavailable,
disconnects a resource from an input signal, or returns a resource to a
quiescent, ready, or safe state.
In many test and measurement systems, resources representing external,
physical devices often require a combination of tasks. In effect, these
tasks drive the physical device through state transitions taking it from a
quiescent or safe state to an active, functioning state, and then back.
Other types of resources may require no tasks at all because they have but
one state. An example is a passive electronic component such as a
resistor. Typical task combinations and representative examples include:
<no tasks> (passive device, e.g., filter)
Set-up (programmable passive device, e.g., programmable filter bank)
Set-up, Function (measurement device, e.g., multi-meter, digitizer)
Set-up, Terminate (physical connection, e.g., switch matrix)
Function (simple software function, e.g., fft, add)
Set-up, Function, Terminate (device that can control its input, e.g.,
digitizer with input coupling)
Simple Illustration of Data Flow Diagram
Application of the concept of Tasks is illustrated in the following simple
example. FIG. 3 depicts a second illustrative data flow diagram 83
consisting of Stimulus Block A connected to a Sensor B by a physical
Connection C. The stimulus A, such as a signal generator, may be in either
of two states, ON or OFF. This is represented by a state diagram 84 shown
below block A in FIG. 3, in which the letter S stands for Set-up, F for
Function and T for Terminate.
Block A accordingly has associated with it a set of tasks including Set-up,
Function and Terminate. Set-up generally is conducted with the device in
an off or quiescent state and does not change that state, as indicated by
arrow 87. Set-up may include setting parameters such as the output voltage
swing or waveform to be generated. In test systems such as that described
in Jordan, et al, these parameters may be set through a graphic interface.
Block A's Function task, indicated by arrow 89, takes the signal generator
from the OFF state to the ON state, i.e. an active state where the signal
generated by A is present at its output. Finally, the Terminate task,
indicated by arrow 88, changes the device from the ON state to the OFF
state.
The hardware connection C has two states, it simply is made or broken. It
may be considered ON when the connection is made, i.e. an electrically
conductive path is established between its input and its output, and OFF
when the connection is broken. The Set-up task changes the state of
connection from OFF to ON and the Terminate tasks changes it from ON to
OFF again. These state changes are illustrated in state diagram 85 in FIG.
3.
Finally, the sensor B, e.g., a measurement device, has a standby or
quiescent state and a functioning or active state. Its parameters are set
up during the standby or quiescent state. In the active state, it measures
the signal at its input and generates data. This sequence is important to
avoid abusing the instrument by changing measurement parameters while an
upstream device is applying a signal. Once the device is set up, the
Function task changes it to ON or active state and the Terminate task
returns it to standby state. These state changes are indicated in state
diagram 86, shown below the sensor B in FIG. 3.
GENERAL RULES FOR ORDERING TASKS
Ordering the tasks with respect to an individual resource is determined
according to the following general internal task-positioning rules:
Set up precedes Function;
Function precedes Terminate; and
Set up precedes Terminate (if no Function task).
Identification of these rules is essential to the "interleaving" of
different resources' tasks. Interleaving refers to an ordering among all
of the tasks associated with a data flow system (for example, among the 7
tasks shown in Table 90 in FIG. 3). The interleaving is accomplished in
accordance with the internal task-positioning rules set forth above and,
additionally, for each resource relative to another in accordance with the
following general external task-positioning rules:
Downstream block's Set-up precedes upstream blocks' Function.
Downstream block's Function follows upstream blocks' Function.
Downstream block's Terminate follows upstream blocks' Terminate.
Connection's set up precedes upstream block's Function.
Connection's Function follows upstream block's Function.
Connection's Terminate follows upstream block's Terminate.
Downstream Block's Function precedes upstream Block's Terminate.
More complex rules may be required depending on the nature of the resources
and tasks involved. Refined rules are set forth below and in APPENDIX A.
First, however, application of the general rules to the example of FIG. 3
is described.
APPLICATION OF THE GENERAL RULES
Referring to FIG. 3, assume that the stimulus (Block A) is a signal
generator and that the sensor (Block B) is a digital multimeter (DMM). The
signal generator is a physical resource having associated tasks Set-up;
Function and Terminate. The DMM is a physical resource having associated
tasks Set-up and Function. The connection C, as noted above, is a physical
connection, having associated tasks Set-up and Terminate.
Resource table 90 in FIG. 3 summarizes the three resources A, B and C
comprising the data flow diagram 83 and their respective tasks. In the
resource table 90, each resource is listed in a first column 92, each
resource is identified in a second column 94, and the respective tasks
associated with each resource are abbreviated in a third column 96. In
column 96 (and in FIGS. 3-7), the abbreviation "s" stands for Set-up, "f"
stands for Function, and "t" refers to Terminate.
Referring now to FIG. 4, the collection of tasks to be interleaved to
implement the data flow of FIG. 3 are shown randomly arranged on the page.
Lines are drawn between the tasks showing dependencies in accordance with
the general rules set forth above. The solid lines are dependencies
arising from general external positioning rules. The dashed lines show
examples of dependencies arising from the general internal positioning
rules. The dependency lines terminate in arrowheads which indicate the
sequence of control flow prescribed by the rules.
To illustrate, the first general external rule set forth above is,
"Downstream block's Set-up precedes upstream blocks' Function." Referring
to FIG. 3, B is the downstream block and A is the upstream block.
Application of this rule requires that B's Set-up task precede A's
Function task. Physically, this means that the DMM must be set up, i.e.,
set to an appropriate range, before the signal generator functions, i.e.,
produces a signal. This restriction protects the DMM input circuitry. This
requirement is modeled as a dependency represented by line 98.
FIG. 5 shows a sorted, directed graph of the tasks and dependencies of FIG.
4 in which control flows from left to right. It illustrates pictorially a
partially ordered list of tasks for execution, discussed below. The tasks
are properly interleaved to protect the test instrument and produce valid
measurement data.
APPLICATION OF A REFINED RULE LIST
FIG. 6 depicts a third data flow diagram 110 and corresponding resource
table 112. Specifically, the data flow diagram 110 includes three resource
blocks, labeled A, B, and C respectively, and interconnections x and y.
The resource table 112 sets forth the specific nature of the resources
comprising the diagram and their respective tasks, shown within
parentheses. Note the presence of a software connection x between resource
A and a first input 116 to resource C. The letter p adjacent the input 116
designates a parameter input. A hardware or physical connection y connects
resource B to resource C.
This example is typical of many test and instrumentation applications. Such
applications often include a device producing a physical output, such as a
device-under-test, shown here as resource B. Resource C may be a
measurement or data acquisition instrument, such as a programmable
multimeter. The multimeter has two inputs, the signal to be measured,
produced by resource B and provided to the multimeter via physical
connection y, and a parameter input which is provided over software
connection X from a driver A in the computer system. The parameter might
be, for example, range or sensitivity selection.
In FIG. 6, C is downstream of both resources A and B. Application of the
general rule "downstream block's Set-up precedes upstream block's
Function," to resources C and A would have the DMM Set-up before the
Set-up parameter is available, i.e., before upstream block A functions.
This is plainly incorrect. It illustrates that the basic general rules set
forth above are insufficient to properly order and interleave the tasks of
the data flow represented by diagram 110. The general rules fail to
account for this type of network where a resource, in this case C, must
have a parameter provided in order to perform its Set-up task.
Referring now to Appendix A, note that rule 4 of the refined rule list
applies to this system. It provides, "A block's Set-up task follows
software connections' Function [tasks] upstream of parameter inputs."
Referring now to FIG. 7, the directed graph 114 includes the tasks of data
flow diagram 110 properly ordered in accordance with the refined rule
list. The rule number which dictates each dependency is indicated with an
R adjacent the line indicating that dependency. In particular, note that
A.sub.f (A's Function, i.e., providing the parameter to Set-up C) precedes
C.sub.s (C's Set-up), in accordance with the quoted rule.
In a preferred embodiment, all positioning rules are applied (if they can
be applied) to every data flow diagram. This results in redundant
dependencies on occasion, but they cause no harm in practice and allowing
them obviates substantial additional code necessary to identify and remove
such redundant dependencies.
The DAG 114 illustrates the resulting partially ordered list of tasks. The
code segments corresponding to the tasks are linked sequentially in
accordance with the list. The resulting code may be written to a file or
compiled for execution.
ILLUSTRATIVE DATA STRUCTURES
FIGS. 8-20 include illustrative data structures for implementing the
present invention in an object-oriented programming environment. The
description proceeds through the use of two illustrative data flow block
diagrams, shown in FIG. 8 and FIG. 15. FIGS. 8-14 illustrate a preferred
implementation of the invention in a simple software example by means of
hierarchic data structures. FIGS. 15-21 extend the principles of the
invention to input ordering in an example of a test system.
Referring first to FIG. 8, a fourth illustrative data flow block diagram
130 shows a data flow system which may be implemented in software
exclusively. This data flow system multiplies two constants, 2 and 5, and
displays the resulting product. The diagram consists of blocks 132, 134,
136 and 138 and connections 133, 135 and 137.
FIG. 9 shows the data structure of the block diagram of FIG. 8. Here and in
subsequent data structure illustrations, angled lines such as line 142 in
FIG. 9 illustrate the hierarchic relationship from one data structure to a
descendent data structure, generally shown to the right of its parent. The
data structure 140 of the block diagram includes a list of blocks which is
itself an ordered collection, a list of connections which is also an
ordered collection and an empty list of sorted tasks, also an ordered
collection, here labeled "sortList." In Smalltalk-80.RTM. parlance
(Smalltalk-80 is a registered trademark of Xerox Corpor | | |
